Recent research in cybersecurity has begun to develop active
defense strategies using game-theoretic optimization of the
allocation of limited defenses combined with deceptive
signaling. While effective, the algorithms are optimized against
perfectly rational adversaries. In a laboratory experiment, we
pit humans against the defense algorithm in an online game
designed to simulate an insider attack scenario. Humans attack
far more often than predicted under perfect rationality.
Optimizing against human bounded rationality is vitally
important. We propose a cognitive model based on instancebased learning theory and built in ACT-R that accurately
predicts human performance and biases in the game. We show
that the algorithm does not defend well, largely due to its static
nature and lack of adaptation to the particular individual’s
actions. Thus, we propose an adaptive method of signaling that
uses the cognitive model to trace an individual’s experience in
real time, in order to optimize defenses. We discuss the results
and implications of personalized defense.
Keywords: cyber deception; cognitive models; instance-based
learning; knowledge-tracing; model-tracing
In the real world, real-time data are now widely available, especially in security domains. Security cameras, aerial imagery, and even social media keep defenders informed when protecting important events, locations, and people. Further, advances in artificial intelligence have led to tools that can interpret these data automatically. Game theoretic models, for example, have shown great success in security. However, most of them ignore real-time information. In this paper, we demonstrate the potential to use real-time information from imagery to better inform our decisions in game theoretic models for security. As a concrete example, a conservation group called Air Shepherd uses conservation drones equipped with thermal infrared cameras to locate poachers at night and alert park rangers. They have also used lights aboard the drones, or signaled, to warn poachers of their presence, which often deters the poachers. We propose a system that (i) allocates drones and humans strategically throughout a protected area, (ii) detects poachers in the thermal infrared videos recorded by the conservation drones flying through the protected area in the predetermined location, and (iii) recommends moving to the location and/or signaling to the poacher that a patroller is nearby depending on real-time detections. View the demonstration.
Illegal smuggling is one of the most important issues across countries, where more than $10 billion
a year of illegal wildlife trafficking is conducted
within transnational criminal networks. Governments have tried to deploy inspections at checkpoints to stop illegal smuggling, though the effect
is quite limited due to vast protection areas but limited human resources. We study these problems
from the perspective of network interdiction games
with a boundedly rational attacker. In this paper, we
aim to improve the efficiency of the limited number of checkpoints. The problem involves two main
stages: i) a predictive stage to predict the attacker’s
behavior based on the historical interdiction; ii)
a prescriptive stage to optimally allocate limited
checkpoints to interdict the attacker. In this paper, we propose a novel boundedly rational model
which resolves the issue of exponentially many attacker strategies by making memoryless assumption about the attacker’s behavior. We show that
the attacker’s behavior can be reduced to an absorbing Markov chain, where the success probability of
reaching any target can be computed analytically,
thus optimized via any gradient-based optimization technique. We incorporate graph convolutional
neural networks with K-hops look-ahead to model
the attacker’s reasoning. Our proposed model provides a new perspective to study the boundedly
rationality in traditional interdiction games with
graph structure. This novel model possesses nice
analytical properties and scales up very well by
avoiding enumerating all paths in the graph.
In important domains from natural resource conservation to public safety, real-time information is becoming increasingly important. Strategic deployment of security cameras and mobile sensors such as drones can provide real-time updates on illegal activities. To help plan for such strategic deployments of sensors and human patrollers, as well as warning signals to ward off adversaries, the defender-attacker security games framework can be used. [Zhang et al., 2019] has shown that real-time data (e.g., human view from a helicopter) may be used in conjunction with security game models to interdict criminals. Other recent work relies on real-time information from sensors that can notify the patroller when an opponent is detected [Basilico et al., 2017; Xu et al., 2018]. Despite considering real-time information in all cases, these works do not consider the combined situation of uncertainty in real-time information in addition to strategically signaling to adversaries. In this thesis, we will not only address this gap, but also improve the overall security result by considering security game models and computer vision algorithms together. A major aspect of this work is in applying it to real-world challenges, such as conservation. Although it applies to many environmental challenges, such as protecting forests and avoiding illegal mining, we will focus particularly on reducing poaching of endangered wildlife as an example. To reduce poaching, human patrollers typically search for snares and poaching activity as they patrol, as well as intervene if poaching activity is found. Drones are useful patrolling aids due to their ability to cover additional ground, but they must interpret their environments, notify nearby human patrollers for intervention, and send potentially deceptive signals to the adversary to deter poaching. Rather than treating these as separate tasks, models must coordinate to handle challenges found in real-world conservation scenarios (Fig. 1). We will determine the success of this work both in simulated experiments and through work with conservation agencies such as Air Shepherd to implement the system in the real world.
Defender-attacker Stackelberg security games (SSGs) have been applied for solving many real-world security problems. Recent work in SSGs has incorporated a deceptive signaling scheme into the SSG model, where the defender strategically reveals information about her defensive strategy to the attacker, in order to inuence the attacker’s decision making for the defender’s own benet. In this work, we study the problem of signaling in security games against a boundedly rational attacker.
Controlling recurrent infectious diseases is a vital yet complicated problem. In this paper, we propose a novel active screening model (ACTS) and algorithms to facilitate active screening for recurrent diseases (no permanent immunity) under infection uncertainty. Our contributions are: (1) A new approach to modeling multi-round networkbased screening/contact tracing under uncertainty, which is a common real-life practice in a variety of diseases [10, 30]; (2) Two novel algorithms, Full- and Fast-REMEDY. Full-REMEDY considers the effect of future actions and finds a policy that provides high solution quality, where Fast-REMEDY scales linearly in the size of the network; (3) We evaluate Full- and Fast-REMEDY on several real-world datasets which emulate human contact and find that they control diseases better than the baselines. To the best of our knowledge, this is the first work on multiround active screening with uncertainty for diseases with no permanent immunity.
Real-world applications often combine learning and optimization problems on graphs. For instance, our objective may be to cluster the graph in order to detect meaningful communities (or solve other common graph optimization problems such as facility location, maxcut, and so on). However, graphs or related attributes are often only partially observed, introducing learning problems such as link prediction which must be solved prior to optimization. Standard approaches treat learning and optimization entirely separately, while recent machine learning work aims to predict the optimal solution directly from the inputs. Here, we propose an alternative decision-focused learning approach that integrates a differentiable proxy for common graph optimization problems as a layer in learned systems. The main idea is to learn a representation that maps the original optimization problem onto a simpler proxy problem that can be efficiently differentiated through. Experimental results show that our CLUSTERNET system outperforms both pure end-to-end approaches (that directly predict the optimal solution) and standard approaches that entirely separate learning and optimization. Code for our system is available at https://github.com/bwilder0/clusternet.
Fueled by algorithmic advances, AI algorithms are increasingly being deployed in settings subject to unanticipated challenges with complex social effects. Motivated by real-world deployment of AI driven, social-network based suicide prevention and landslide risk management interventions, this paper focuses on robust graph covering problems subject to group fairness constraints. We show that, in the absence of fairness constraints, state-of-the-art algorithms for the robust graph covering problem result in biased node coverage: they tend to discriminate individuals (nodes) based on membership in traditionally marginalized groups. To mitigate this issue, we propose a novel formulation of the robust graph covering problem with group fairness constraints and a tractable approximation scheme applicable to real-world instances. We provide a formal analysis of the price of group fairness (PoF) for this problem, where we show that uncertainty can lead to greater PoF. We demonstrate the effectiveness of our approach on several real-world social networks. Our method yields competitive node coverage while significantly improving group fairness relative to state-of-the-art methods.
Substance use and abuse is a significant public health problem in the United States. Group-based intervention programs offer a promising means of preventing and reducing substance abuse. While effective, unfortunately, inappropriate intervention groups can result in an increase in deviant behaviors among participants, a process known as deviancy training. This paper investigates the problem of optimizing the social influence related to the deviant behavior via careful construction of the intervention groups. We propose a Mixed Integer Optimization formulation that decides on the intervention groups to be formed, captures the impact of the intervention groups on the structure of the social network, and models the impact of these changes on behavior propagation. In addition, we propose a scalable hybrid meta-heuristic algorithm that combines Mixed Integer Programming and Large Neighborhood Search to find nearoptimal network partitions. Our algorithm is packaged in the form of GUIDE, an AI-based decision aid that recommends intervention groups. Being the first quantitative decision aid of this kind, GUIDE is able to assist practitioners, in particular social workers, in three key areas: (a) GUIDE proposes near-optimal solutions that are shown, via extensive simulations, to significantly improve over the traditional qualitative practices for forming intervention groups; (b) GUIDE is able to identify circumstances when an intervention will lead to deviancy training, thus saving time, money, and effort; (c) GUIDE can evaluate current strategies of group formation and discard strategies that will lead to deviancy training. In developing GUIDE, we are primarily interested in substance use interventions among homeless youth as a high risk and vulnerable population. GUIDE is developed in collaboration with Urban Peak, a homelessyouth serving organization in Denver, CO, and is under preparation for deployment.
Most of the current security models assume that the values of targets/areas are static or the changes (if any) are scheduled and known to the defender. Unfortunately, such models are not sufficient for many domains, where actions of the players modify the values of the targets. Examples include wildlife scenarios, where the attacker can increase value of targets by secretly building supporting facilities. To address such security game domains with player-affected values, we first propose DPOS3G, a novel partially observable stochastic Stackelberg game where target values are determined by the players’ actions; the defender can only partially observe these targets’ values, while the attacker can fully observe the targets’ values and the defender’s strategy. Second, we propose RITA (Reduced game Iterative Transfer Algorithm), which is based on the heuristic search value iteration algorithm for partially observable stochastic game (PG-HSVI) and introduces three key novelties: (a) building a reduced game with only key states (derived from partitioning the state space) to reduce the numbers of states and transitions considered when solving the game; (b) incrementally adding defender’s actions to further reduce the number of transitions of the game; (c) providing novel heuristics for lower bound initialization of the algorithm. Third, we conduct extensive experimental evaluations of the algorithms and the results show that RITA significantly outperforms the baseline PG-HSVI algorithm on scalability while allowing for trade off in scalability and solution quality.
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.