Skip to main content
main-content

About this book

This book constitutes the refereed proceedings of the 8th International Conference on Decision and Game Theory for Security, GameSec 2017, held in Vienna, Austria, in October 2017.
The 24 revised full papers presented together with 4 short papers were carefully reviewed and selected from 71 submissions.The papers address topics such as Game theory and mechanism design for security and privacy; Pricing and economic incentives for building dependable and secure systems; Dynamic control, learning, and optimization and approximation techniques; Decision making and decision theory for cybersecurity and security requirements engineering; Socio-technological and behavioral approaches to security; Risk assessment and risk management; Security investment and cyber insurance; Security and privacy for the Internet-of-Things (IoT), cyber-physical systems, resilient control systems; New approaches for security and privacy in cloud computing and for critical infrastructure; Security and privacy of wireless and mobile communications, including user location privacy; Game theory for intrusion detection; and Empirical and experimental studies with game-theoretic or optimization analysis for security and privacy.

Table of Contents

Frontmatter

Full Papers

Frontmatter

Optimizing Traffic Enforcement: From the Lab to the Roads

Road accidents are the leading causes of death of youths and young adults worldwide. Efficient traffic enforcement has been conclusively shown to reduce high-risk driving behaviors and thus reduce accidents. Today, traffic police departments use simplified methods for their resource allocation (heuristics, accident hotspots, etc.). To address this potential shortcoming, in [23], we introduced a novel algorithmic solution, based on efficient optimization of the allocation of police resources, which relies on the prediction of accidents. This prediction can also be used for raising public awareness regarding road accidents. However, significant challenges arise when instantiating the proposed solution in real-world security settings. This paper reports on three main challenges: (1) Data-centric challenges; (2) Police-deployment challenges; and (3) Challenges in raising public awareness. We mainly focus on the data-centric challenge, highlighting the data collection and analysis, and provide a detailed description of how we tackled the challenge of predicting the likelihood of road accidents. We further outline the other two challenges, providing appropriate technical and methodological solutions including an open-access application for making our prediction model accessible to the public.

Ariel Rosenfeld, Oleg Maksimov, Sarit Kraus

Incentive Compatibility of Pay Per Last N Shares in Bitcoin Mining Pools

Pay per last N shares (PPLNS) is a popular pool mining reward mechanism on a number of cryptocurrencies, including Bitcoin. In PPLNS pools, miners may stand to benefit by delaying reports of found shares. This attack may entail unfair or inefficient outcomes. We propose a simple but general game theoretical model of delays in PPLNS. We derive conditions for incentive compatible rewards, showing that the power of the most powerful miner determines whether incentives are compatible or not. An efficient algorithm to find Nash equilibria is put forward, and used to show how fairness and efficiency deteriorate with inside-pool inequality. In pools where all players have comparable computational power incentives to deviate from protocol are minor, but gains may be considerable in pools where miner’s resources are unequal. We explore how our findings can be applied to ameliorate delay attacks by fitting real-world parameters to our model.

Yevhen Zolotavkin, Julian García, Carsten Rudolph

Adaptivity in Network Interdiction

We study a network security game arising in the interdiction of fare evasion or smuggling. A defender places a security checkpoint in the network according to a chosen probability distribution over the links of the network. An intruder, knowing this distribution, wants to travel from her initial location to a target node. For every traversed link she incurs a cost equal to the transit time of that link. Furthermore, if she encounters the checkpoint, she has to pay a fine.The intruder may adapt her path online, exploiting additional knowledge gained along the way. We investigate the complexity of computing optimal strategies for intruder and defender. We give a concise encoding of the intruders optimal strategy and present an approximation scheme to compute it. For the defender, we consider two different objectives: (i) maximizing the intruder’s cost, for which we give an approximation scheme, and (ii) maximizing the collected fine, which we show to be strongly NP-hard. We also give a paramterized bound on the worst-case ratio of the intruders best adaptive strategy to the best non-adaptive strategy, i.e., when she fixes the complete route at the start.

Bastián Bahamondes, José Correa, Jannik Matuschke, Gianpaolo Oriolo

Efficient Rational Proofs for Space Bounded Computations

We present new protocols for the verification of space bounded polytime computations against a rational adversary. For such computations requiring sublinear space our protocol requires only a verifier running in sublinear-time. We extend our main result in several directions: (i) we present protocols for randomized complexity classes, using a new composition theorem for rational proofs which is of independent interest; (ii) we present lower bounds (i.e. conditional impossibility results) for Rational Proofs for various complexity classes.Our new protocol is the first rational proof not based on the circuit model of computation, and the first sequentially composable protocols for a well-defined language class.

Matteo Campanelli, Rosario Gennaro

Game-Theoretical Analysis of PLC System Performance in the Presence of Jamming Attacks

In this paper, we investigate the performance of power line communication (PLC) network in the presence of jamming attacks. The legitimate nodes of the PLC network try to communicate with the anchor node of the network while the jamming node attempts to degrade the system performance. The fading, attenuation and colored noise of the PLC channel with dependence on the frequency and transmission distance are taken into account. To investigate the jamming problem, we frame the adversarial interaction into a Bayesian game, where the PLC network tries to maximize the overall expected network capacity and the jammer node has the opposite goal. In the Bayesian game, both players have imperfect knowledge of their opponents. We study effects of total power available to the players on the equilibrium of the game by formulating it into zero-sum and non-zero-sum games, respectively. It is found that under some network setup, there exists a threshold power for which the actual gameplay of the legitimate nodes does not depend upon the actions of the jamming node, and vice versa. This allows us to choose the appropriate power allocation schemes given the total power and the action of the jamming node in some cases.

Yun Ai, Manav R. Bhatnagar, Michael Cheffena, Aashish Mathur, Artem Sedakov

Secure Sensor Design for Cyber-Physical Systems Against Advanced Persistent Threats

We introduce a new paradigm to the field of control theory: “secure sensor design”. Particularly, we design sensor outputs cautiously against advanced persistent threats that can intervene in cyber-physical systems. Such threats are designed for the very specific target systems and seeking to achieve their malicious goals in the long term while avoiding intrusion detection. Since such attacks can avoid detection mechanisms, the controller of the system could have already been intervened in by an adversary. Disregarding such a possibility and disclosing information without caution can have severe consequences. Therefore, through secure sensor design, we seek to minimize the damage of such undetected attacks in cyber-physical systems while impacting the ordinary operations of the system at minimum. We, specifically, consider a controlled Markov-Gaussian process, where a sensor observes the state of the system and discloses information to a controller that can have friendly or adversarial intentions. We show that sensor outputs that are memoryless and linear in the state of the system can be optimal, in the sense of game-theoretic hierarchical equilibrium, within the general class of strategies. We also provide a semi-definite programming based algorithm to design the secure sensor outputs numerically.

Muhammed O. Sayin, Tamer Başar

An Ultimatum Game Model for the Evolution of Privacy in Jointly Managed Content

Content sharing in social networks is now one of the most common activities of internet users. In sharing content, users often have to make access control or privacy decisions that impact other stakeholders or co-owners. These decisions involve negotiation, either implicitly or explicitly. Over time, as users engage in these interactions, their own privacy attitudes evolve, influenced by and consequently influencing their peers. In this paper, we present a variation of the one-shot Ultimatum Game, wherein we model individual users interacting with their peers to make privacy decisions about shared content. We analyze the effects of sharing dynamics on individuals’ privacy preferences over repeated interactions of the game. We theoretically demonstrate conditions under which users’ access decisions eventually converge, and characterize this limit as a function of inherent individual preferences at the start of the game and willingness to concede these preferences over time. We provide simulations highlighting specific insights on global and local influence, short-term interactions and the effects of homophily on consensus.

Sarah Rajtmajer, Anna Squicciarini, Jose M. Such, Justin Semonsen, Andrew Belmonte

The U.S. Vulnerabilities Equities Process: An Economic Perspective

The U.S. Vulnerabilities Equities Process (VEP) is used by the government to decide whether to retain or disclose zero day vulnerabilities that the government possesses. There are costs and benefits to both actions: disclosing the vulnerability allows the vulnerability to be patched and systems to be made more secure, while retaining the vulnerability allows the government to conduct intelligence, offensive national security, and law enforcement activities. While redacted documents give some information about the organization of the VEP, very little is publicly known about the decision-making process itself, with most of the detail about the criteria used coming from a blog post by Michael Daniel, the former White House Cybersecurity Coordinator. Although the decision to disclose or retain a vulnerability is often considered a binary choice—to either disclose or retain—it should actually be seen as a decision about timing: to determine when to disclose. In this paper, we present a model that shows how the criteria could be combined to determine the optimal time for the government to disclose a vulnerability, with the aim of providing insight into how a more formal, repeatable decision-making process might be achieved. We look at how the recent case of the WannaCry malware, which made use of a leaked NSA zero day exploit, EternalBlue, can be interpreted using the model.

Tristan Caulfield, Christos Ioannidis, David Pym

A Stackelberg Game Model for Botnet Data Exfiltration

Cyber-criminals can distribute malware to control computers on a networked system and leverage these compromised computers to perform their malicious activities inside the network. Botnet-detection mechanisms, based on a detailed analysis of network traffic characteristics, provide a basis for defense against botnet attacks. We formulate the botnet defense problem as a zero-sum Stackelberg security game, allocating detection resources to deter botnet attacks taking into account the strategic response of cyber-criminals. We model two different botnet data-exfiltration scenarios, representing exfiltration on single or multiple paths. Based on the game model, we propose algorithms to compute an optimal detection resource allocation strategy with respect to these formulations. Our algorithms employ the double-oracle method to deal with the exponential action spaces for attacker and defender. Furthermore, we provide greedy heuristics to approximately compute an equilibrium of these botnet defense games. Finally, we conduct experiments based on both synthetic and real-world network topologies to demonstrate advantages of our game-theoretic solution compared to previously proposed defense policies.

Thanh Nguyen, Michael P. Wellman, Satinder Singh

Optimal Strategies for Detecting Data Exfiltration by Internal and External Attackers

We study the problem of detecting data exfiltration in computer networks. We focus on the performance of optimal defense strategies with respect to an attacker’s knowledge about typical network behavior and his ability to influence the standard traffic. Internal attackers know the typical upload behavior of the compromised host and may be able to discontinue standard uploads in favor of the exfiltration. External attackers do not immediately know the behavior of the compromised host, but they can learn it from observations.We model the problem as a sequential game of imperfect information, where the network administrator selects the thresholds for the detector, while the attacker chooses how much data to exfiltrate in each time step. We present novel algorithms for approximating the optimal defense strategies in the form of Stackelberg equilibria. We analyze the scalability of the algorithms and efficiency of the produced strategies in a case study based on real-world uploads of almost six thousand users to Google Drive. We show that with the computed defense strategies, the attacker exfiltrates 2–3 times less data than with simple heuristics; randomized defense strategies are up to 30% more effective than deterministic ones, and substantially more effective defense strategies are possible if the defense is customized for groups of hosts with similar behavior.

Karel Durkota, Viliam Lisý, Christopher Kiekintveld, Karel Horák, Branislav Bošanský, Tomáš Pevný

Building Real Stackelberg Security Games for Border Patrols

We present a decision support system to help plan preventive border patrols. The system represents the interaction between defenders and intruders as a Stackelberg security game (SSG) where the defender pools local resources to conduct joint preventive border patrols. We introduce a new SSG that constructs defender strategies that pair adjacent precincts to pool resources that are used to patrol a location within one of the two precincts. We introduce an efficient formulation of this problem and an efficient sampling method to construct an implementable defender strategy.The system automatically constructs the Stackelberg game from geographically located past crime data, topology and cross border information. We use clustering of past crime data and logit probability distribution to assign risk to patrol areas. Our results on a simplified real-world inspired border patrol instance show the computational efficiency of the model proposed, its robustness with respect to parameters used in automatically constructing the instance, and the quality of the sampled solution obtained.

Victor Bucarey, Carlos Casorrán, Óscar Figueroa, Karla Rosas, Hugo Navarrete, Fernando Ordóñez

Strategic Defense Against Deceptive Civilian GPS Spoofing of Unmanned Aerial Vehicles

The Global Positioning System (GPS) is commonly used in civilian Unmanned Aerial Vehicles (UAVs) to provide geolocation and time information for navigation. However, GPS is vulnerable to many intentional threats such as the GPS signal spoofing, where an attacker can deceive a GPS receiver by broadcasting incorrect GPS signals. Defense against such attacks is critical to ensure the reliability and security of UAVs. In this work, we propose a signaling game framework in which the GPS receiver can strategically infer the true location when the attacker attempts to mislead it with a fraudulent and purposefully crafted signal. We characterize the necessary and sufficient conditions of perfect Bayesian equilibrium (PBE) of the game and observe that the equilibrium has a PLASH structure, i.e., pooling in low types and separating in high types. This structure enables the development of a game-theoretic security mechanism to defend against the civil GPS signal spoofing for civilian UAVs. Our results show that in the separating part of the PLASH PBE, the civilian UAV can infer its true position under the spoofing attack while in the pooling portion of the PLASH PBE, the corresponding equilibrium strategy allows the civilian UAV to rationally decide the position that minimizes the deviation from its true position. Numerical experiments are used to corroborate our results and observations.

Tao Zhang, Quanyan Zhu

A Game Theoretical Model for Optimal Distribution of Network Security Resources

Enforcing security in a network always comes with a tradeoff regarding budget constraints, entailing unavoidable choices for the deployment of security equipment over the network. Therefore, finding the optimal distribution of security resources to protect the network is necessary. In this paper, we focus on Intrusion Detection Systems (IDSs), which are among the main components used to secure networks. However, configuring and deploying IDSs efficiently to optimize attack detection and mitigation remain a challenging task. In particular, in networks providing critical services, optimal IDS deployment depends on the type of interdependencies that exists between vulnerable network equipment. In this paper, we present a game theoretical analysis for optimizing intrusion detection in such networks. First, we present a set of theoretical preliminary results for resource constrained network security games. Then, we formulate the problem of intrusion detection as a resource constrained network security game where interdependencies between equipment vulnerabilities are taken into account. Finally, we validate our model numerically via a real world case study.

Ziad Ismail, Christophe Kiennert, Jean Leneutre, Lin Chen

Game-Theoretic Goal Recognition Models with Applications to Security Domains

Motivated by the goal recognition (GR) and goal recognition design (GRD) problems in the artificial intelligence (AI) planning domain, we introduce and study two natural variants of the GR and GRD problems with strategic agents, respectively. More specifically, we consider game-theoretic (GT) scenarios where a malicious adversary aims to damage some target in an (physical or virtual) environment monitored by a defender. The adversary must take a sequence of actions in order to attack the intended target. In the GTGR and GTGRD settings, the defender attempts to identify the adversary’s intended target while observing the adversary’s available actions so that he/she can strengthens the target’s defense against the attack. In addition, in the GTGRD setting, the defender can alter the environment (e.g., adding roadblocks) in order to better distinguish the goal/target of the adversary.We propose to model GTGR and GTGRD settings as zero-sum stochastic games with incomplete information about the adversary’s intended target. The games are played on graphs where vertices represents states and edges are adversary’s actions. For the GTGR setting, we show that if the defender is restricted to playing only stationary strategies, the problem of computing optimal strategies (for both defender and adversary) can be formulated and represented compactly as a linear program. For the GTGRD setting, where the defender can choose K edges to block at the start of the game, we formulate the problem of computing optimal strategies as a mixed integer program, and present a heuristic algorithm based on LP duality and greedy methods. Experiments show that our heuristic algorithm achieves good performance (i.e., close to defender’s optimal value) with better scalability compared to the mixed-integer programming approach.In contrast with our research, existing work, especially on GRD problems, has focused almost exclusively on decision-theoretic paradigms, where the adversary chooses its actions without taking into account the fact that they may be observed by the defender. As such an assumption is unrealistic in GT scenarios, our proposed models and algorithms fill a significant gap in the literature.

Samuel Ang, Hau Chan, Albert Xin Jiang, William Yeoh

Manipulating Adversary’s Belief: A Dynamic Game Approach to Deception by Design for Proactive Network Security

Due to the sophisticated nature of current computer systems, traditional defense measures, such as firewalls, malware scanners, and intrusion detection/prevention systems, have been found inadequate. These technological systems suffer from the fact that a sophisticated attacker can study them, identify their weaknesses and thus get an advantage over the defender. To prevent this from happening a proactive cyber defense is a new defense mechanism in which we strategically engage the attacker by using cyber deception techniques, and we influence his actions by creating and reinforcing his view of the computer system. We apply the cyber deception techniques in the field of network security and study the impact of the deception on attacker’s beliefs using the quantitative framework of the game theory. We account for the sequential nature of an attack and investigate how attacker’s belief evolves and influences his actions. We show how the defender should manipulate this belief to prevent the attacker from achieving his goals and thus minimize the damage inflicted to the network. To design a successful defense based on cyber deception, it is crucial to employ strategic thinking and account explicitly for attacker’s belief that he is being exposed to deceptive attempts. By doing so, we can make the deception more believable from the perspective of the attacker.

Karel Horák, Quanyan Zhu, Branislav Bošanský

A Stochastic Game-Theoretic Model for Smart Grid Communication Networks

The increasing adoption of new information and communication technology assets in smart grids is making smart grids vulnerable to cyber threats, as well as raising numerous concerns about the adequacy of current security approaches. As a single act of penetration is often not sufficient for an attacker to achieve his/her goal, multistage cyber attacks may occur. This paper looks at the stochastic and dynamic nature of multistage cyber attacks in smart grid use cases and develops a stochastic game-theoretic model to capture the interactions between the attacker and the defender in multistage cyber attack scenarios. Due to the information asymmetry of the interactions between the attacker and the defender, neither of both players knows the exact current game state. This paper proposes a belief-updating mechanism for both players to form a common belief about the current game state. In order to assess threats of multistage cyber attacks, it further discusses the computation of Nash equilibria for the designed game model.

Xiaobing He, Hermann de Meer

A Stackelberg Game and Markov Modeling of Moving Target Defense

We propose a Stackelberg game model for Moving Target Defense (MTD) where the defender periodically switches the state of a security sensitive resource to make it difficult for the attacker to identify the real configurations of the resource. Our model can incorporate various information structures. In this work, we focus on the worst-case scenario from the defender’s perspective where the attacker can observe the previous configurations used by the defender. This is a reasonable assumption especially when the attacker is sophisticated and persistent. By formulating the defender’s problem as a Markov Decision Process (MDP), we prove that the optimal switching strategy has a simple structure and derive an efficient value iteration algorithm to solve the MDP. We further study the case where the set of feasible switches can be modeled as a regular graph, where we solve the optimal strategy in an explicit way and derive various insights about how the node degree, graph size, and switching cost affect the MTD strategy. These observations are further verified on random graphs empirically.

Xiaotao Feng, Zizhan Zheng, Prasant Mohapatra, Derya Cansever

Proactive Defense Against Physical Denial of Service Attacks Using Poisson Signaling Games

While the Internet of things (IoT) promises to improve areas such as energy efficiency, health care, and transportation, it is highly vulnerable to cyberattacks. In particular, distributed denial-of-service (DDoS) attacks overload the bandwidth of a server. But many IoT devices form part of cyber-physical systems (CPS). Therefore, they can be used to launch “physical” denial-of-service attacks (PDoS) in which IoT devices overflow the “physical bandwidth” of a CPS. In this paper, we quantify the population-based risk to a group of IoT devices targeted by malware for a PDoS attack. In order to model the recruitment of bots, we develop a “Poisson signaling game,” a signaling game with an unknown number of receivers, which have varying abilities to detect deception. Then we use a version of this game to analyze two mechanisms (legal and economic) to deter botnet recruitment. Equilibrium results indicate that (1) defenders can bound botnet activity, and (2) legislating a minimum level of security has only a limited effect, while incentivizing active defense can decrease botnet activity arbitrarily. This work provides a quantitative foundation for proactive PDoS defense.

Jeffrey Pawlick, Quanyan Zhu

A Large-Scale Markov Game Approach to Dynamic Protection of Interdependent Infrastructure Networks

The integration of modern information and communication technologies (ICTs) into critical infrastructures (CIs) improves its connectivity and functionalities yet also brings cyber threats. It is thus essential to understand the risk of ICTs on CIs holistically as a cyber-physical system and design efficient security hardening mechanisms. To this end, we capture the system behaviors of the CIs under malicious attacks and the protection strategies by a zero-sum game. We further propose a computationally tractable approximation for large-scale networks which builds on the factored graph that exploits the dependency structure of the nodes of CIs and the approximate dynamic programming tools for stochastic Markov games. This work focuses on a localized information structure and the single-controller game solvable by linear programming. Numerical results illustrate the proper tradeoff of the approximation accuracy and computation complexity in the new design paradigm and show the proactive security at the time of unanticipated attacks.

Linan Huang, Juntao Chen, Quanyan Zhu

VIOLA: Video Labeling Application for Security Domains

Advances in computational game theory have led to several successfully deployed applications in security domains. These game-theoretic approaches and security applications learn game payoff values or adversary behaviors from annotated input data provided by domain experts and practitioners in the field, or collected through experiments with human subjects. Beyond these traditional methods, unmanned aerial vehicles (UAVs) have become an important surveillance tool used in security domains to collect the required annotated data. However, collecting annotated data from videos taken by UAVs efficiently, and using these data to build datasets that can be used for learning payoffs or adversary behaviors in game-theoretic approaches and security applications, is an under-explored research question. This paper presents VIOLA, a novel labeling application that includes (i) a workload distribution framework to efficiently gather human labels from videos in a secured manner; (ii) a software interface with features designed for labeling videos taken by UAVs in the domain of wildlife security. We also present the evolution of VIOLA and analyze how the changes made in the development process relate to the efficiency of labeling, including when seemingly obvious improvements surprisingly did not lead to increased efficiency. VIOLA enables collecting massive amounts of data with detailed information from challenging security videos such as those collected aboard UAVs for wildlife security. VIOLA will lead to the development of a new generation of game-theoretic approaches for security domains, including approaches that integrate deep learning and game theory for real-time detection and response.

Elizabeth Bondi, Fei Fang, Debarun Kar, Venil Noronha, Donnabell Dmello, Milind Tambe, Arvind Iyer, Robert Hannaford

On the Economics of Ransomware

While recognized as a theoretical and practical concept for over 20 years, only now ransomware has taken centerstage as one of the most prevalent cybercrimes. Various reports demonstrate the enormous burden placed on companies, which have to grapple with the ongoing attack waves. At the same time, our strategic understanding of the threat and the adversarial interaction between organizations and cybercriminals perpetrating ransomware attacks is lacking.In this paper, we develop, to the best of our knowledge, the first game-theoretic model of the ransomware ecosystem. Our model captures a multi-stage scenario involving organizations from different industry sectors facing a sophisticated ransomware attacker. We place particular emphasis on the decision of companies to invest in backup technologies as part of a contingency plan, and the economic incentives to pay a ransom if impacted by an attack. We further study to which degree comprehensive industry-wide backup investments can serve as a deterrent for ongoing attacks.

Aron Laszka, Sadegh Farhang, Jens Grossklags

Deterrence of Cyber Attackers in a Three-Player Behavioral Game

This study describes a three-player cyber security game involving an attacker, a defender, and a user. An attacker must choose to attack the defender or the user or to forego an attack altogether. Conversely, defender (e.g., system administrator) and user (e.g., individual system user) must choose between either a “standard” or “enhanced” security level. Deterrence is operationalized as a decision by an attacker to forego an attack. We conducted two behavioral experiments in which players were assigned to the cyber attacker role over multiple rounds of a security game and were incentivized based on their performance. The defender and user’s decisions were based on a joint probability distribution over their two options known to the attacker. Coordination between the defender and user is manipulated via the joint probability distribution. Results indicate that attacker deterrence is influenced by coordination between defender and user.

Jinshu Cui, Heather Rosoff, Richard S. John

Information Leakage Games

We consider a game-theoretic setting to model the interplay between attacker and defender in the context of information flow, and to reason about their optimal strategies. In contrast with standard game theory, in our games the utility of a mixed strategy is a convex function of the distribution on the defender’s pure actions, rather than the expected value of their utilities. Nevertheless, the important properties of game theory, notably the existence of a Nash equilibrium, still hold for our (zero-sum) leakage games, and we provide algorithms to compute the corresponding optimal strategies. As typical in (simultaneous) game theory, the optimal strategy is usually mixed, i.e., probabilistic, for both the attacker and the defender. From the point of view of information flow, this was to be expected in the case of the defender, since it is well known that randomization at the level of the system design may help to reduce information leaks. Regarding the attacker, however, this seems the first work (w.r.t. the literature in information flow) proving formally that in certain cases the optimal attack strategy is necessarily probabilistic.

Mário S. Alvim, Konstantinos Chatzikokolakis, Yusuke Kawamoto, Catuscia Palamidessi

Optimal Patrol Planning for Green Security Games with Black-Box Attackers

Motivated by the problem of protecting endangered animals, there has been a surge of interests in optimizing patrol planning for conservation area protection. Previous efforts in these domains have mostly focused on optimizing patrol routes against a specific boundedly rational poacher behavior model that describes poachers’ choices of areas to attack. However, these planning algorithms do not apply to other poaching prediction models, particularly, those complex machine learning models which are recently shown to provide better prediction than traditional bounded-rationality-based models. Moreover, previous patrol planning algorithms do not handle the important concern whereby poachers infer the patrol routes by partially monitoring the rangers’ movements. In this paper, we propose OPERA, a general patrol planning framework that: (1) generates optimal implementable patrolling routes against a black-box attacker which can represent a wide range of poaching prediction models; (2) incorporates entropy maximization to ensure that the generated routes are more unpredictable and robust to poachers’ partial monitoring. Our experiments on a real-world dataset from Uganda’s Queen Elizabeth Protected Area (QEPA) show that OPERA results in better defender utility, more efficient coverage of the area and more unpredictability than benchmark algorithms and the past routes used by rangers at QEPA.

Haifeng Xu, Benjamin Ford, Fei Fang, Bistra Dilkina, Andrew Plumptre, Milind Tambe, Margaret Driciru, Fred Wanyama, Aggrey Rwetsiba, Mustapha Nsubaga, Joshua Mabonga

Short Papers

Frontmatter

Security Games with Probabilistic Constraints on the Agent’s Strategy

This paper considers a special case of security games dealing with the protection of a large area divided in multiple cells for a given planning period. An intruder decides on which cell to attack and an agent selects a patrol route visiting multiple cells from a finite set of patrol routes such that some given operational conditions on the agent’s mobility are met. For example, the agent might be required to patrol some cells more often than others. In order to determine strategies for the agent that deal with these conditions and remain unpredictable for the intruder, this problem is modeled as a two-player zero-sum game with probabilistic constraints such that the operational conditions are met with high probability. We also introduce a variant of the basic constrained security game in which the payoff matrices change over time, to allow for the payoff that may change during the planning period.

Corine M. Laan, Ana Isabel Barros, Richard J. Boucherie, Herman Monsuur

On the Cost of Game Playing: How to Control the Expenses in Mixed Strategies

Game theory typically assumes rational behavior of the players when looking for optimal solutions. Still in case of a mixed equilibrium, it allows players to choose any strategy from the mix in each repetition of the game as long as the optimal frequencies are met in the long run. Which strategy is chosen in a specific round may not be purely random but also depend on what strategy has just been played.In many cases, playing a particular strategy is tied to cost or efforts. For instance, adding a new defensive strategy (e.g., applying a new virus scanner) requires some investment (implementation cost), but playing the strategy may incur some efforts as well (playing cost: a virus scan takes time and consumes resources, so too frequent scanning appears undesirable). If a security system successfully repels an attack, the attacker is most likely coming back using a different attack vector. Thus we here study repeated games in order to respond to changing attacks.The effort to play a strategy may be quite dependent on what has been played before, and the switch from the last strategy to the new one, in the next instance (repetition) of the game, may come at what we call a switching cost. These can create an incentive to not play a certain mixed strategy. In cases when there equilibrium is unique, a player may have an incentive to nonetheless deviate from it to save costs, and thus gain more (only in a different way). So, the strategy plan should depend on the equilibrium and the (switching) cost for playing it.The matter is essentially more complex than only asking for how to play a mixed strategy most efficiently; instead, we need to incorporate the switching costs into the game as an additional goal to be optimized. Those costs are indeed dependent on the equilibrium of the game itself. Thus, the usual dependency of the equilibrium on the payoffs is herein augmented by the converse dependency of the payoffs on the equilibrium. To handle this circular dependency, we will apply a generalized game-theoretic model that allows payoffs to be random variables (rather than real numbers). We show how to solve this new form of game and illustrate the method with an example.

Stefan Rass, Sandra König, Stefan Schauer

Dynamics of Strategic Protection Against Virus Propagation in Heterogeneous Complex Networks

With an increasing number of wide-spreading cyber-attacks on networks such as the recent WannaCry and Petya Ransomware, protection against malware and virus spreading in large scale networks is essential to provide security to network systems. In this paper, we consider a network protection game in which heterogeneous agents decide their individual protection levels against virus propagation over complex networks. Each agent has his own private type which characterizes his recovery rate, transmission capabilities, and perceived cost. We propose an evolutionary Poisson game framework to model the heterogeneous interactions of the agents over a complex network and analyze the equilibrium strategies for decentralized protection. We show the structural results of the equilibrium strategies and their connections with replicator dynamics. Numerical results are used to corroborate the analytical results.

Yezekael Hayel, Quanyan Zhu

Three Layer Game Theoretic Decision Framework for Cyber-Investment and Cyber-Insurance

Cyber-threat landscape has become highly complex, due to which isolated attempts to understand, detect, and resolve cybersecurity issues are not feasible in making a time constrained decisions. Introduction of cyber-threat information (CTI) sharing has potential to handle this issue to some extent, where knowledge about security incidents is gathered, exchanged across organizations for deriving useful information regarding the threat actors and vulnerabilities. Although, sharing security information could allow organizations to make informed decision, it may not completely eliminate the risks. Therefore, organizations are also inclined toward considering cyber-insurance for transferring risks to the insurers. Also, in networked environment, adversaries may exploit the information sharing to successfully breach the participating organizations. In this paper, we consider these players, i.e. organizations, adversary, and insure, to model a three layer game, where players play sequentially to find out their optimal strategies. Organizations determine their optimal self-defense investment to make while participating in CTI sharing and cyber-insurance. The adversary looks for an optimal attack rate while the insurer targets to maximize its profit by offering suitable coverage level to the organizations. Using backward induction approach, we conduct subgame perfect equilibrium analysis to find optimal strategies for the involved players. We observe that when cyber-insurance is not considered, attacker prefers to increase its rate of attack. This motivates the organizations to consider cyber-insurance option for transferring the risks on their critical assets.

Deepak K. Tosh, Iman Vakilinia, Sachin Shetty, Shamik Sengupta, Charles A. Kamhoua, Laurent Njilla, Kevin Kwiat

Backmatter

Additional information

Premium Partner

Neuer Inhalt
image credits