Protecting an organization’s cyber assets from intrusions and breaches due to attacks by malicious actors is an increasingly challenging and complex problem. Companies and organizations (hereon referred to as the defender) who operate enterprise networks employ the use of numerous protection measures to intercept these attacks, such as Intrusion and Detection Systems (IDS) and along with dedicated Cyber Emergency Readiness Teams (CERT) composed of cyber analysts tasked with the general protection of an organization’s cyber assets. In order to optimize the use of the defender’s limited resources and protection mechanisms, we can look to game theory which has been successfully used to handle complex resource allocation problems and has several deployed real-world applications in physical security domains. Applying previous research on security games to cybersecurity domains introduce several novel challenges which I address in my thesis to create models that deceive cyber adversaries and provide the defender with an alert prioritization strategy for IDS. My thesis provides three main contributions to the emerging body of research in using game theory for cyber and physical security , namely (i) the first game theoretic framework for cyber deception of a defender’s network, (ii) the first gametheoretic framework for cyber alert allocation and (iii) algorithms for extending these frameworks to general-sum domains.
In regards to the first contribution, I introduce a novel game model called the Cyber Deception Game (CDG) model which captures the interaction between the defender and adversary during the recon phase of a network attack. The CDG model provides the first game-theoretic framework for deception in cybersecurity and allows the defender to devise deceptive strategies that deceptively alters system responses on the network. I study two different models of cyber adversaries and provide algorithms to solve CDGs that handle the computational complexities stemming from the adversary’s static view of the defender’s network and the varying differences between adversary models. The second major contribution of my thesis is the first game theoretic model for cyber alert prioritization for a network defender. This model, the Cyber-alert Allocation Game, provides an approach which balances intrinsic characteristics of incoming alerts from an IDS with the defender’s analysts that are available to resolve alerts. Additionally, the aforementioned works assume the games are zero-sum which is not true in many real-world domains. As such, the third contribution in my thesis extends CAGs to general-sum domains. I provide scalable algorithms that have additional applicability to other physical screening domains (e.g., container screening, airport passenger screening).
This thesis considers the following question: in systems with self-interested agents (a.k.a., games), how does information — i.e., what each agent knows about their environment and other agents’ preferences — affect their decision making? The study of the role of information in games has a rich history, and in fact forms the celebrated field of information economics. However, different from previous descriptive study, this thesis takes a prescriptive approach and examines computational questions pertaining to the role of information. In particular, it illustrates the double-edged role of information through two threads of research: (1) how to utilize information to one’s own advantage in strategic interactions; (2) how to mitigate losses resulting from information leakage to an adversary. In each part, we study the algorithmic foundation of basic models and also develop efficient solutions to real-world problems arising from physical security domains. Besides pushing the research frontier, the work of this thesis is also directly impacting several real-world applications, resulting in delivered software for improving the scheduling of US federal air marshals and the design of patrolling routes for wildlife conservation. More concretely, the first part of this thesis studies an intrinsic phenomenon in human endeavors termed persuasion — i.e., the act of exploiting an informational advantage in order to influence the decisions of others. We start with two real-world motivating examples, illustrating how security agencies can utilize an informational advantage to influence adversaries’ decisions and deter potential attacks. Afterwards, we provide a systematic algorithmic study for the foundational economic models underlying these examples. Our analysis not only fully resolves the complexity of these models, but also leads to new economic insights. We then leverage the insights and algorithmic ideas from our theoretical analysis to develop new models and solutions for concrete real-world security problems. The second part of this thesis studies the other side of the double-edged sword, namely, how to deal with disadvantages due to information leakage. We also start with real-world motivating examples to illustrate how classified information about security measures may leak to the adversary and cause significant loss to security agencies. We then propose different models to capture information leakage based on how much the security agency is aware of the leakage situation, and provide thorough algorithmic analysis for these models. Finally, we return to the real-world problems and design computationally efficient algorithms tailored to each security domain.
In the presence of an intelligent adversary, game theoretic models such as security games, have proven to be effective tools for mitigating risks from exploitable gaps in protection and security protocols, as they model the strategic interaction between an adversary and defender, and allow the defender to plan the use of scarce or limited resources in the face of such an adversary. However, standard security game models have limited expressivity in the types of planning they allow the defender to perform, as they look only at the deployment and allocation of a fixed set of security resources. This ignores two very important planning problems which concern the strategic design of the security system and resources to deploy as well as the usability and implementation of the security protocols. When these problems appear in real world systems, significant losses in utility and efficiency of security protocols can occur if they are not dealt with in a principled way. To address these limitations, in this thesis I introduce a new hierarchical structure of planning problems for security games, dividing the problem into three levels of planning (i) Strategic Planning, which considers long term planning horizons, and decisions related to game design which constrain the possible defender strategies, (ii) Tactical Planning, which considers shorter term horizons, dealing with the deployment of resources, and selection of defender strategies subject to strategic level constraints and (iii) Operational Planning, dealing with implementation of strategies in real world setting. First, focusing on Strategic Planning, I address the design problem of selecting a set of resource and schedule types. I introduce a new yet fundamental problem, the Simultaneous Optimization of Resource Teams and Tactics (SORT) which models the coupled problem of both strategic and tactical planning, optimizing over both game design with respect to selection of resource types, as well as their deployment actual in the field. I provide algorithms for efficiently solving the SORT problem, which use hierarchical relaxations of the optimization problem to compute these strategic level investment decisions. I show that this more expressive model allows the defender to perform more fine grained decision making that results in significant gains in utility. Second, motivated by the relevance and hardness of security games with resource heterogeneity, I also address challenges in tactical planning by providing a framework for computing adaptive strategies with heterogeneous resources. Lastly, I look at the problem of operational planning, which has never been formally studied in the security game literature. I propose a new solution concept of operationalizable strategies, which randomize over an optimally chosen subset of pure strategies whose cardinality is selected by the defender. I show hardness of computing such operationalizable strategies and provide an algorithm for computing -optimal equilibria which are operationalizable. In all of these problems, I am motivated by real world challenges, and developing solution methods that are usable in the real world. As such, much of this work has been in collaboration with organizations such as Panthera, WWF and other non-governmental organizations (NGOs), to help protect the national parks and wildlife against deforestation and poaching, and the TSA, to protect critical infrastructure such as our airports from terrorist attacks. Because of this, in addressing these three levels of planning, I develop solutions which are not only novel and academically interesting, but also deployable with a real world impact.
Elizabeth Bondi, Debadeepta Dey, Ashish Kapoor, Jim Piavis, Shital Shah, Fei Fang, Bistra Dilkina, Robert Hannaford, Arvind Iyer, Lucas Joppa, and Milind Tambe. 6/20/2018. “AirSim-W: A Simulation Environment for Wildlife Conservation with UAVs.” In In COMPASS ’18: ACM SIGCAS Conference on Computing and Sustainable Societies (COMPASS), June 20–22, 2018, . Menlo Park and San Jose, CA, USA. ACM, New York, NY, USA.Abstract
Increases in poaching levels have led to the use of unmanned aerial vehicles (UAVs or drones) to count animals, locate animals in parks, and even find poachers. Finding poachers is often done at night through the use of long wave thermal infrared cameras mounted on these UAVs. Unfortunately, monitoring the live video stream from the conservation UAVs all night is an arduous task. In order to assist in this monitoring task, new techniques in computer vision have been developed. This work is based on a dataset which took approximately six months to label. However, further improvement in detection and future testing of autonomous flight require not only more labeled training data, but also an environment where algorithms can be safely tested. In order to meet both goals efficiently, we present AirSim-W, a simulation environment that has been designed specifically for the domain of wildlife conservation. This includes (i) creation of an African savanna environment in Unreal Engine, (ii) integration of a new thermal infrared model based on radiometry, (iii) API code expansions to follow objects of interest or fly in zig-zag patterns to generate simulated training data, and (iv) demonstrated detection improvement using simulated data generated by AirSim-W. With these additional simulation features, AirSim-W will be directly useful for wildlife conservation research.
The potential of Artificial Intelligence (AI) to tackle challenging problems that afflict society is
enormous, particularly in the areas of healthcare, conservation and public safety and security.
Many problems in these domains involve harnessing social networks of under-served communities to enable positive change, e.g., using social networks of homeless youth to raise awareness
about Human Immunodeficiency Virus (HIV) and other STDs. Unfortunately, most of these realworld problems are characterized by uncertainties about social network structure and influence
models, and previous research in AI fails to sufficiently address these uncertainties, as they make
several unrealistic simplifying assumptions for these domains.
This thesis addresses these shortcomings by advancing the state-of-the-art to a new generation of algorithms for interventions in social networks. In particular, this thesis describes the
design and development of new influence maximization algorithms which can handle various uncertainties that commonly exist in real-world social networks (e.g., uncertainty in social network
structure, evolving network state, and availability of nodes to get influenced). These algorithms
utilize techniques from sequential planning problems and social network theory to develop new
kinds of AI algorithms. Further, this thesis also demonstrates the real-world impact of these algorithms by describing their deployment in three pilot studies to spread awareness about HIV
among actual homeless youth in Los Angeles. This represents one of the first-ever deployments
of computer science based influence maximization algorithms in this domain. Our results show
that our AI algorithms improved upon the state-of-the-art by ∼ 160% in the real-world. We discuss research and implementation challenges faced in deploying these algorithms, and lessons
that can be gleaned for future deployment of such algorithms. The positive results from these
deployments illustrate the enormous potential of AI in addressing societally relevant problems.
Conservation of our planet’s natural resources is of the utmost
importance and requires constant innovation. This project focuses on innovation for one aspect of conservation: the reduction of wildlife poaching. Park rangers patrol parks to decrease poaching by searching for poachers and animal snares
left by poachers. Multiple strategies exist to aid in these patrols, including adversary behavior prediction and planning
optimal ranger patrol strategies. These research efforts suffer
from a key shortcoming: they fail to integrate real-time data,
and rely on historical data collected during ranger patrols.
Recent advances in unmanned aerial vehicle (UAV) technology have made UAVs viable tools to aid in park ranger
patrols. There is now an opportunity to augment the input
for these strategies in real time using computer vision, by (i)
automatically detecting both animals and poachers in UAV
videos, (ii) using these detections to learn future poaching locations and to plan UAV patrol routes in real time, and (iii)
using poaching location predictions to determine where to fly
for the next patrol. In other words, detection is done on realtime data captured aboard a UAV. Detection will then be used
to learn adversaries’ behaviors, or where poaching may occur
in the future, in future work. This will then be used to plan
where to fly in the long term, such as the next mission. Finally, planning where to fly next during the current flight will
depend on the long term plan and the real-time detections.
This proposed system directly improves wildlife security.
Through our collaboration with Air Shepherd, a program of
the Charles A. and Anne Morrow Lindbergh Foundation, we
have already begun deploying poacher detection prototypes
in Africa and will deploy further advances there in the future
(Fig. 1). Furthermore, this also applies to similar surveillance
tasks, such as locating people after natural disasters.
Election control considers the problem of an adversary who attempts
to tamper with a voting process, in order to either ensure that their
favored candidate wins (constructive control) or another candidate
loses (destructive control). As online social networks have become
significant sources of information for potential voters, a new tool
in an attacker’s arsenal is to effect control by harnessing social
influence, for example, by spreading fake news and other forms of
misinformation through online social media.
We consider the computational problem of election control via
social influence, studying the conditions under which finding good
adversarial strategies is computationally feasible. We consider two
objectives for the adversary in both the constructive and destructive
control settings: probability and margin of victory (POV and MOV,
respectively). We present several strong negative results, showing,
for example, that the problem of maximizing POV is inapproximable
for any constant factor. On the other hand, we present approximation algorithms which provide somewhat weaker approximation
guarantees, such as bicriteria approximations for the POV objective
and constant-factor approximations for MOV. Finally, we present
mixed integer programming formulations for these problems. Experimental results show that our approximation algorithms often
find near-optimal control strategies, indicating that election control
through social influence is a salient threat to election integrity.
An important way cyber adversaries find vulnerabilities in modern networks is through reconnaissance, in which they attempt to
identify configuration specifics of network hosts. To increase uncertainty of adversarial reconnaissance, the network administrator
(henceforth, defender) can introduce deception into responses to
network scans, such as obscuring certain system characteristics.
We introduce a novel game-theoretic model of deceptive interactions of this kind between a defender and a cyber attacker, which
we call the Cyber Deception Game. We consider both a powerful
(rational) attacker, who is aware of the defender’s exact deception
strategy, and a naive attacker who is not. We show that computing
the optimal deception strategy is NP-hard for both types of attackers.
For the case with a powerful attacker, we provide a mixed-integer
linear program solution as well as a fast and effective greedy algorithm. Similarly, we provide complexity results and propose exact
and heuristic approaches when the attacker is naive. Our extensive experimental analysis demonstrates the effectiveness of our
We consider the problem of designing fair, efficient, and interpretable policies for prioritizing heterogeneous homeless youth on a
waiting list for scarce housing resources of different types. We focus on
point-based policies that use features of the housing resources (e.g., permanent supportive housing, rapid rehousing) and the youth (e.g., age,
history of substance use) to maximize the probability that the youth will
have a safe and stable exit from the housing program. The policies can
be used to prioritize waitlisted youth each time a housing resource is
procured. Our framework provides the policy-maker the flexibility to select both their desired structure for the policy and their desired fairness
requirements. Our approach can thus explicitly trade-off interpretability
and efficiency while ensuring that fairness constraints are met. We propose a flexible data-driven mixed-integer optimization formulation for
designing the policy, along with an approximate formulation which can
be solved efficiently for broad classes of interpretable policies using Bender’s decomposition. We evaluate our framework using real-world data
from the United States homeless youth housing system. We show that
our framework results in policies that are more fair than the current policy in place and than classical interpretable machine learning approaches
while achieving a similar (or higher) level of overall efficiency.
We define a class of zero-sum games with combinatorial
structure, where the best response problem of one player is
to maximize a submodular function. For example, this class
includes security games played on networks, as well as the
problem of robustly optimizing a submodular function over
the worst case from a set of scenarios. The challenge in computing equilibria is that both players’ strategy spaces can be
exponentially large. Accordingly, previous algorithms have
worst-case exponential runtime and indeed fail to scale up on
practical instances. We provide a pseudopolynomial-time algorithm which obtains a guaranteed (1 − 1/e)
mixed strategy for the maximizing player. Our algorithm only
requires access to a weakened version of a best response oracle for the minimizing player which runs in polynomial time.
Experimental results for network security games and a robust
budget allocation problem confirm that our algorithm delivers near-optimal solutions and scales to much larger instances
than was previously possible.
Significant research effort in security games has focused in devising
strategies that perform well even when the attacker deviates from
optimal (rational) behavior. In most of these frameworks, a price
needs to be paid to ensure robustness against this unpredictability. However, equilibrium refinement is an attractive alternative to
boost solution robustness at no cost even though it has not received
as much attention in security game literature. In this framework,
resources are strategically allocated to secure an optimal outcome
against a rational adversary while simultaneously protecting other
targets to ensure good outcomes against boundedly rational or
constrained attackers. Unfortunately, existing approaches for equilibrium refinement in security games cannot effectively address
scheduling constraints that arise frequently in real-world applications. In this paper, we aim to fill this gap and make several key
contributions. First, we show that existing approaches for equilibrium refinement can fail in the presence of scheduling constraints.
Second, we investigate the properties of the best response of the attacker. Third, we leverage these properties to devise novel iterative
algorithms to compute the optimally refined equilibrium, with polynomially many calls to an LP oracle for zero-sum games. Finally, we
conduct extensive experimental evaluations that showcase i) the
superior performance of our approach in the face of a boundedly
rational attacker and ii) the attractive scalability properties of our
algorithm that can solve realistic-sized instances.
There are nearly 2 million homeless youth in the United
States each year. Coordinated entry systems are being used to provide
homeless youth with housing assistance across the nation. Despite these
efforts, the number of youth still homeless or unstably housed remains
very high. Motivated by this fact, we initiate a first study to understand and analyze the current governmental housing systems for homeless youth. In this paper, we aim to provide answers to the following questions: (1) What is the current governmental housing system for assigning
homeless youth to different housing assistance? (2) Can we infer the current assignment guidelines of the local housing communities? (3) What
is the result and outcome of the current assignment process? (4) Can we
predict whether the youth will be homeless after receiving the housing
assistance? To answer these questions, we first provide an overview of the
current housing systems. Next, we use simple and interpretable machine
learning tools to infer the decision rules of the local communities and
evaluate the outcomes of such assignment. We then determine whether
the vulnerability features/rubrics can be used to predict youth’s homelessness status after receiving housing assistance. Finally, we discuss the
policy recommendations from our study for the local co
Colluding adversaries is a crucial challenge for defenders in many
real-world applications. Previous literature has provided Collusive Security Games
(COSG) to model colluding adversaries, and provided models and algorithms to
generate defender strategies to counter colluding adversaries, often by devising
strategies that inhibit collusion . Unfortunately, this previous work focused
exclusively on situations with perfectly matched adversaries, i.e., where their
rewards were symmetrically distributed. In the real world, however, defenders
often face adversaries where their rewards are asymmetrically distributed. Such
inherent asymmetry raises a question as to whether human adversaries would attempt to collude in such situations, and whether defender strategies to counter
such collusion should focus on inhibiting collusion. To address these open questions, this paper: (i) explores and theoretically analyzes Imbalanced Collusive
Security Games (ICOSG) where defenders face adversaries with asymmetrically
distributed rewards; (ii) conducts extensive experiments of three different adversary models involving 1800 real human subjects and (iii) derives novel analysis
of the reason behind why bounded rational attackers models outperform perfectly
rational attackers models. The key principle discovered as the result of our experiments is that: careful modeling of human bounded rationality reveals a key difference (when compared to a model using perfect rationality) in defender strategies
for handling colluding adversaries which face symmetric vs asymmetric rewards.
Whereas a model based on perfect rationality always attempts to break collusion
among adversaries, a bounded rationality model acknowledges the inherent difficulty of breaking such collusion in symmetric situations and focuses only on
breaking collusion in asymmetric situation, and only on damage control from
collusion in the symmetric situation.
Strong Stackelberg equilibrium (SSE) is the standard solution concept
of Stackelberg security games. The SSE assumes that the follower
breaks ties in favor of the leader and this is widely acknowledged
and justified by the assertion that the defender can often induce the
attacker to choose a preferred action by making an infinitesimal
adjustment to her strategy. Unfortunately, in security games with
resource assignment constraints, the assertion might not be valid.
To overcome this issue, inspired by the notion of inducibility and
the pessimistic Stackelberg equilibrium [20, 21], this paper presents
the inducible Stackelberg equilibrium (ISE), which is guaranteed
to exist and avoids overoptimism as the outcome can always be
induced with infinitesimal strategy deviation. Experimental evaluation unveils the significant overoptimism and sub-optimality of
SSE and thus, verifies the advantage of the ISE as an alternative
To improve cyber defense, researchers have developed
algorithms to allocate limited defense resources optimally.
Through signaling theory, we have learned that it is possible to
trick the human mind when using deceptive signals. The
present work is an initial step towards developing a
psychological theory of cyber deception. We use simulations
to investigate how humans might make decisions under various
conditions of deceptive signals in cyber-attack scenarios. We
created an Instance-Based Learning (IBL) model of the
attacker decisions using the ACT-R cognitive architecture. We
ran simulations against the optimal deceptive signaling
algorithm and against four alternative deceptive signal
schemes. Our results show that the optimal deceptive algorithm
is more effective at reducing the probability of attack and
protecting assets compared to other signaling conditions, but it
is not perfect. These results shed some light on the expected
effectiveness of deceptive signals for defense. The implications
of these findings are discussed.
Youth homelessness has reached a concerning level of prevalence in the United States. Many communities have attempted to address this problem by creating coordinated community responses, typically referred to as Coordinated Entry Systems (CES). In such systems, agencies within a community pool their housing resources in a centralized system. Youth seeking housing are first assessed for eligibility and vulnerability and then linked to appropriate housing resources. The most widely adopted tool for assessing youth vulnerability is the Transition Age Youth-Vulnerability Index-Service Prioritization Decision Assistance Tool (TAY-VI-SPDAT): Next Step Tool (NST) for homeless youth. To date, no evidence has been amassed to support the value of using this tool or its proposed scoring schematic to prioritize housing resources. Similarly, there is little evidence on the outcomes of youth whose placements are determined by the tool. This article presents the first comprehensive and rigorous evaluation of the connection between vulnerability scores, housing placements, and stability of housing outcomes using data from the Homeless Management Information System (HMIS) collected between 2015 and 2017 from 16 communities across the United States. The two primary aims are (1) to investigate the degree to which communities are using the tool’s recommendations when placing youth into housing programs, and (2) to examine how effectively NST scores distinguish between youth in greater need of formal housing interventions from youth who may be able to self-resolve or return to family successfully. High vulnerability scores at intake were associated with higher odds of continued homelessness without housing intervention, suggesting the tool performs well in predicting youth that need to be prioritized for housing services in the context of limited resources. The majority of low scoring youth appear to return home or self-resolve and remain stably exited from homelessness. Youth placed in permanent supportive housing (PSH) had low recorded returns to homelessness, regardless of their NST score. Youth with vulnerability scores up to 10 who were placed in rapid rehousing (RRH) also had low returns to homelessness, but success was much more variable for higher-scoring youth.
The unrelenting threat of poaching has led to increased development of new technologies to combat it. One such example is the use of thermal infrared cameras mounted on unmanned aerial vehicles (UAVs or drones) to spot poachers at night and report them to park rangers before they are able to harm any animals. However, monitoring the live video stream from these conservation UAVs all night is an arduous task. Therefore, we discuss SPOT (Systematic POacher deTector), a novel application that augments conservation drones with the ability to automatically detect poachers and animals in near real time [Bondi et al., 2018b]. SPOT illustrates the feasibility of building upon state-of-the-art AI techniques, such as Faster RCNN, to address the challenges of automatically detecting animals and poachers in infrared images. This paper reports (i) the design of SPOT, (ii) efficient processing techniques to ensure usability in the field, (iii) evaluation of SPOT based on historical videos and a real-world test run by the end-users, Air Shepherd, in the field, and (iv) the use of AirSim for live demonstration of SPOT. The promising results from a field test have led to a plan for larger-scale deployment in a national park in southern Africa. While SPOT is developed for conservation drones, its design and novel techniques have wider application for automated detection from UAV videos.
More than 1 million homicides, robberies, and aggravated assaults occur in the United States each year. These crimes are
often further classified into different types based on the circumstances surrounding the crime (e.g., domestic violence,
gang-related). Despite recent technological advances in AI
and machine learning, these additional classification tasks are
still done manually by specially trained police officers. In this
paper, we provide the first attempt to develop a more automatic system for classifying crimes. In particular, we study
the question of classifying whether a given violent crime
is gang-related. We introduce a novel Partially Generative
Neural Networks (PGNN) that is able to accurately classify
gang-related crimes both when full information is available
and when there is only partial information. Our PGNN is
the first generative-classification model that enables to work
when some features of the test examples are missing. Using
a crime event dataset from Los Angeles covering 2014-2016,
we experimentally show that our PGNN outperforms all other
typically used classifiers for the problem of classifying gangrelated violent crimes.
A wealth of algorithms centered around (integer) linear programming have been proposed to compute equilibrium strategies in security games with discrete states and actions. However, in practice many domains possess continuous state and
action spaces. In this paper, we consider a continuous space
security game model with infinite-size action sets for players and present a novel deep learning based approach to extend the existing toolkit for solving security games. Specifically, we present (i) OptGradFP, a novel and general algorithm that searches for the optimal defender strategy in a parameterized continuous search space, and can also be used
to learn policies over multiple game states simultaneously;
(ii) OptGradFP-NN, a convolutional neural network based
implementation of OptGradFP for continuous space security
games. We demonstrate the potential to predict good defender
strategies via experiments and analysis of OptGradFP and
OptGradFP-NN on discrete and continuous game settings.
Treatable infectious diseases are a critical challenge for public health. Outreach campaigns can encourage undiagnosed
patients to seek treatment but must be carefully targeted to
make the most efficient use of limited resources. We present
an algorithm to optimally allocate limited outreach resources
among demographic groups in the population. The algorithm
uses a novel multiagent model of disease spread which both
captures the underlying population dynamics and is amenable
to optimization. Our algorithm extends, with provable guarantees, to a stochastic setting where we have only a distribution over parameters such as the contact pattern between
agents. We evaluate our algorithm on two instances where
this distribution is inferred from real world data: tuberculosis
in India and gonorrhea in the United States. Our algorithm
produces a policy which is predicted to avert an average of
least 8,000 person-years of tuberculosis and 20,000 personyears of gonorrhea annually compared to current policy.