Decision and Game Theory for Security

An often useful way to think of security is as a game between an adversary and the “good” participants in the protocol. Game theorists try to understand games in terms of solution concepts; essentially, this is a rule for predicting how the game will be played. The most commonly used solution concept in game theory is Nash equilibrium. Intuitively, a Nash equilibrium is a strategy profile (a collection of strategies, one for each player in the game) such that no player can do better by deviating. The intuition behind Nash equilibrium is that it represent a possible steady state of play. It is a fixed point where each player holds correct beliefs about what other players are doing, and plays a best response to those beliefs. Part of what makes Nash equilibrium so attractive is that in games where each player has only finitely many possible deterministic strategies, and we allow mixed (i.e., randomized) strategies, there is guaranteed to be a Nash equilibrium [11] (this was, in fact, the key result of Nash’s thesis).

Computer and information networks are a prime example of an environment where negative externalities abound, particularly when it comes to implementing security defenses. A typical example is that of denial-of-service prevention: ingress filtering, where attack traffic gets discarded by routers close to the perpetrators, is in principle an excellent remedy, as it prevents harmful traffic not only from reaching the victims, but also from burdening the network situated between attacker and target. However, with ingress filtering, the entities (at the ingress) that have to invest in additional filtering are not the ones (at the egress) who mostly benefit from the investment, and, may not have any incentive to participate in the scheme. As this example illustrates, it is important to understand the incentives of the different participants to a network, so that we can design schemes or intervention mechanisms to re-align them with a desirable outcome.

Intrusion Detection Systems (IDSs) are becoming essential to protecting modern information infrastructures. The effectiveness of an IDS is directly related to the computational resources at its disposal. However, it is difficult to guarantee especially with an increasing demand of network capacity and rapid proliferation of attacks. On the other hand, modern intrusions often come as sequences of attacks to reach some predefined goals. It is therefore critical to identify the best default IDS configuration to attain the highest possible overall protection within a given resource budget. This paper proposes a game theory based solution to the problem of optimal signature-based IDS configuration under resource constraints. We apply the concepts of indices of power, namely, Shapley value and Banzhaf-Coleman index, from cooperative game theory to quantify the influence or contribution of libraries in an IDS with respect to given attack graphs. Such valuations take into consideration the knowledge on common attack graphs and experienced system attacks and are used to configure an IDS optimally at its default state by solving a knapsack optimization problem.

At present much of the research which proposes to provide solutions to Imperfect Information Non-Cooperative games provides superficial analysis which then requires a priori knowledge of the game to be played. We propose that High Card, a simple Multiplayer Imperfect Information Adversarial game, provides a more robust model for such games, and further, that these games may model situations of real world security and international interest. We have formulated two such real world models, and have created a modeling bot, which when facing adversaries with equal or better performing risk profiles, achieves a 7-fold increase in win performance.

We address an anti-jamming strategy of channel access for secondary user in a cogntive radio network when some idle channels of the primary user are being jammed in each time slot. Given the secondary does not know what idle bands are under attack, using our method it tries to choose the best possible channel in each time slot to avoid the jammer. We show this problem can be formulated as a multi-armed bandit process and compare the results of different approaches for channel selection including ε-greedy, ε-first, and random. Simulatons verify that our method results in selecting channels with an average of almost 50% improved signal to noise ratio (SNR) over randomly selected channels.

Unattended wireless sensor networks are susceptible to node capture attacks, where the adversary physically compromises a node, creates functional copies (clones) of it and deploys such clones back into the network, in order to impact the network’s functionality. In the absence of a centralized authority, distributed clone detection methods have been developed to mitigate this attack. In this paper, we show that the node capture attack and the network response can be modeled as a simultaneous, noncooperative, two-player game. In developing the game-theoretic framework, we consider a deterministic, linear dynamical model of the attack, as well as a general, stochastic model. For the deterministic model, we develop three games, all of which have quadratic utility for the valid network, whereas the adversary’s utility depends on the assumptions about ist abilities. For the stochastic model, we develop a game with convex utility functions. For each game, we prove the existence of a pure strategy Nash Equilibrium and present an efficient way of solving the game. These equilibria can then be used in choosing the appropriate parameters for detecting and responding to the attack. Simulations are provided to illustrate our approach.

The paper deals with a mathematical model of a surveillance system based on a net of sensors. The signals acquired by each node of the net are Markovian process, have two different transition probabilities, which depends on the presence or absence of a intruder nearby. The detection of the transition probability change at one node should be confirmed by a detection of similar change at some other sensors. Based on a simple game the model of a fusion center is then constructed. The aggregate function defined on the net is the background of the definition of a non-cooperative stopping game which is a model of the multivariate disorder detection.

Network users can choose among different security solutions to protect their data. Those solutions are offered by competing providers, with possibly different performance and price levels. In this paper, we model the interactions among users as a noncooperative game, with a negative externality coming from the fact that attackers target popular systems to maximize their expected gain. Using a nonatomic weighted congestion game model for user interactions, we prove the existence and uniqueness of a user equilibrium, and exhibit the tractability of its computation, as a solution of a convex problem. We also compute the corresponding Price of Anarchy, that is the loss of efficiency due to user selfishness, and investigate some consequences for the (higher-level) pricing game played by security providers.

To formulate a network security problem, Mavronicholas et al. [6] introduced a strategic game on an undirected graph whose nodes are exposed to infection by attackers, and whose edges are protected by a defender. Subsequently, MedSalem et al. [9] generalized the model so that they have many defenders instead of a single defender. Then in [1], we introduced a new network game with the roles of players interchanged, and obtained a graph-theoretic characterization of its pure Nash equilibria. In this paper we study mixed Nash equilibria for stochastic strategies in this new game, and then we generalize our network game to an asynchronous game, where two players repeatedly execute simultaneous games. Although the asynchronous game is formally an infinite game, we show that it has a stable solution by reducing it to a finite game.

In his 1961 monograph on Game Theory, Melvin Dresher considered a high-low guessing game on N numbers. The game was solved for N ≤ 11 by Selmer Johnson but solutions for higher values of N have never been reported in the literature. In this paper we derive an asymptotic formula for the value of the game as N → ∞ and we present an algorithm that allows us to numerically solve the game for N ≤ 256.

Security games are characterized by multiple players who strategically adjust their defenses against an abstract attacker, represented by realizations of nature. The defense strategies include both actions where security generates positive externalities and actions that do not. When the players are assumed to be risk averse, market insurance enters as a third strategic option. We formulate a one-shot security game with market insurance, characterize its pure equilibria, and describe how the equilibria compare to established results. Simplifying assumptions include homogeneous players, fair insurance premiums, and complete information except for realizations of nature. The results add more realism to the interpretation of analytical models of security games and might inform policy makers on adjusting incentives to improve network security and foster the development of a market for cyber-insurance.

Recent works on Internet risk management have proposed the idea of cyber-insurance to eliminate risks due to security threats, which cannot be tackled through traditional means such as by using antivirus and antivirus softwares. In reality, an Internet user faces risks due to security attacks as well as risks due to non-security related failures (e.g., reliability faults in the form of hardware crash, buffer overflow, etc.). These risk types are often indistinguishable by a naive user. However, a cyber-insurance agency would most likely insure risks only due to security attacks. In this case, it becomes a challenge for an Internet user to choose the right type of cyber-insurance contract as traditional optimal contracts, i.e., contracts for security attacks only, might prove to be sub-optimal for himself.

In this paper, we address the problem of analyzing cyber-insurance solutions when a user faces risks due to both, security as well as non-security related failures. We propose Aegis, a simple and novel cyber-insurance model in which the user accepts a fraction (strictly positive) of loss recovery on himself and transfers rest of the loss recovery on the cyber-insurance agency. We mathematically show that only under conditions when buying cyber-insurance is mandatory, given an option, risk-averse Internet users would prefer Aegis contracts to traditional cyber-insurance contracts, under all premium types. This result firmly establishes the non-existence of traditional cyber-insurance markets when Aegis contracts are offered to users. We also derive an interesting counterintuitive result related to the Aegis framework: we show that an increase(decrease) in the premium of an Aegis contract may not always lead to decrease(increase) in its user demand. In the process, we also state the conditions under which the latter trend and its converse emerge. Our work proposes a new model of cyber-insurance for Internet security that extends all previous related models by accounting for the extra dimension of non-insurable risks. Aegis also incentivizes Internet users to take up more personal responsibility for protecting their systems.

Ideas, ranging from product preferences to political views, spread through social interactions. These interactions may determine how ideas are adopted within a market and which, if any, become dominant. In this paper, we introduce a model for Dynamic Influence in Competitive Environments (DICE). We show that existing models of influence propagation, including linear threshold and independent cascade models, can be derived as special cases of DICE. Using DICE, we explore two scenarios of competing ideas, including the case where a newcomer competes with a leader with an already-established idea, as well as the case where multiple competing ideas are introduced simultaneously. We formulate the former as a Stackelberg game and the latter as a simultaneous-move game of complete information. Moreover, we show that, in both cases, the payoff functions for both players are submodular, leading to efficient algorithms for each player to approximate his optimal strategy. We illustrate our approach using the Wiki-vote social network dataset.

Recent smartphones incorporate embedded GPS devices that enable users to obtain geographic information about their surroundings by providing a location-based service (LBS) with their current coordinates. However, LBS providers collect a significant amount of data from mobile users and could be tempted to misuse it, by compromising a customer’s location privacy (her ability to control the information about her past and present location). Many solutions to mitigate this privacy threat focus on changing both the architecture of location-based systems and the business models of LBS providers. MobiCrowd does not introduce changes to the existing business practices of LBS providers, rather it requires mobile devices to communicate wirelessly in a peer-to-peer fashion. To lessen the privacy loss, users seeking geographic information try to obtain this data by querying neighboring nodes, instead of connecting to the LBS. However, such a solution will only function if users are willing to share regional data obtained from the LBS provider. We model this collaborative location-data sharing problem with rational agents following threshold strategies. Initially, we study agent cooperation by using pure game theory and then by combining game theory with an epidemic model that is enhanced to support threshold strategies to address a complex multi-agent scenario. From our game-theoretic analysis, we derive cooperative and non-cooperative Nash equilibria and the optimal threshold that maximizes agents’ expected utility.

An experimental study of the digital trust game in [2] is presented. The study consists of an initial survey followed by a four-part dynamic experiment investigating various aspects of digital trust decisions. Digital trust in online environments differs from its offline variants due to its unique characteristics such as near instantaneous communication, transient and impersonal nature of interactions, immediate access to opinions of others, and availability of high amount of (but often low quality) information. It is observed that while the game theory provides a suitable analytical framework for quantitative analysis of digital trust decisions, the model in [2] has its shortcomings. Firstly, the subjects do not seem to adopt an iterative best or gradient response strategy. They exhibit significant (mental) inertia and only respond to new information or significant situation changes. Secondly, they take into account signals from their social circle much more than aggregate signals such as average scores. Both of these results and additional insights gained have important implications for future game theoretic modeling efforts of digital trust.

Phishing exhibits characteristics of asymmetric conflict and guerrilla warfare. Phishing sites, upon detection, are subject to removal by takedown specialists. In response, phishers create large numbers of new phishing attacks to evade detection and stretch the resources of the defenders. We propose the Colonel Blotto Phishing (CBP) game, a two-stage Colonel Blotto game with endogenous dimensionality and detection probability. We find that the optimal number of new phishes to create, from the attacker’s perspective, is influenced by the degree of resource asymmetry, the cost of new phishes, and the probability of detection. Counter-intuitively, we find that it is the less resourceful attacker who would create more phishing attacks in equilibrium. And depending on the detection probability, an attacker will vary his strategies to either create even more phishes, or to focus on raising his resources to increase the chance he will extend the lifetime of his phishes. We discuss the implications to anti-phishing strategies and point out that the game is also applicable to web security problems more generally.

Entrepreneurs face investment decisions on privacy-preserving technology (PPT) adoption as privacy-concerned consumers may decide whether to use firms’ services based on the extent of privacy that firms are able to provide. Kantarcioglu et.al. (2010) [9] contributes to guidelines for entrepreneurs’ adoption decisions through a novel framework, which combines copula functions and a Stackelberg leader-follower game with consumers taking the role of the follower (referred as static-copula-game model hereafter). The valuation requires a clearly defined bivariate distribution function of two random variables, the consumer’s valuation of private information and the consumer’s profitability to a firm. Copula functions are used to construct the bivariate distribution function from arbitrarily univariate marginals with various dependence structures fitting into different market/industry segments. This study extends the static-copula-game model to include project value uncertainty, simultaneously considering different market competition structures and the regulatory promise of random arrival of government mandatory adoption. The project value from the static-copula-game model is used as an estimate of the initial (current) project value for the stochastic evolution. By doing so, we retain the advantages of applying copulas and preserve the established valuation property exclusively applicable to the valuation of PPT adoption. The extension model makes several improvements including: (1) Reduce concerns about myopic PPT adoption decisions that may result when static valuation is employed. (2) Overcome the potential biased PPT adoption decision that may arise due to negligence of market competition impact. (3) Understand the regulatory influence of government mandatory adoption with uncertainty. We find that: (1) If one can link univariate marginals and dependence structures to industry groups, one can determine for which industries project value uncertainty has no impact on the entrepreneur’s immediate PPT adoption decision. For these industries, there is no need for government intervention/regulation to accelerate/induce PPT adoption even though the project value is uncertain. (2) Under project value uncertainty, competition may suggest either a later or an earlier PPT adoption compared with the monopoly case. (3) The promise of government mandatory adoption has the potential to accelerate PPT adoption. The PPT adoption guidelines considering competition and regulatory promises of government mandatory adoption when the project value is uncertain bring useful recommendations to both entrepreneurs and policymakers.

Modern distributed communication networks like the Internet are characterized by nodes (Internet users) interconnected with one another via communication links. In this regard, the security of individual nodes depend not only on their own efforts, but also on the efforts and underlying connectivity structure of neighboring network nodes. By the term ‘effort’, we imply the amount of investments made by a user in security mechanisms like antivirus softwares, firewalls, etc., to improve his security. However, often due to the large magnitude of such networks, it is not always possible for nodes to have complete effort and connectivity structure information about all their neighbor nodes. Added to this is the fact that in many applications, the Internet users are selfish and are not willing to co-operate with other users on sharing effort information.