Defending against multiple different attackers

One defender defends, and multiple heterogeneous attackers attack, an asset. Three scenarios are considered: the agents move simultaneously; the defender moves first; or the attackers move first. We show how the agents’ unit costs of defense and attack, their asset evaluations, and the number of attackers influence their investments, profits, and withdrawal decisions. Withdrawal does not occur in one-period (simultaneous) games between two agents, at least with the commonly used ratio-form contest success function, but can occur in two-period games between two agents. The presence of one particularly strong attacker can cause other attackers to withdraw from the contest if the advantaged attacker appropriates so much of the defender’s asset that it is no longer sufficiently attractive to interest other attackers. In such cases, the defender focuses exclusively on the strong attacker. An advantaged defender may be able to deter attacks by moving first, but will continue to suffer from attacks if moving second. This suggests the importance of proactive rather than reactive defense.     

Individual versus overarching protection and attack of assets

Two agents protect and attack a collection of assets overarchingly versus individually. Examples of overarching protection are border security, counter intelligence, and public health measures. Both layers of protection have to be breached for an attack to be successful. We consider a simultaneous game, and a two period game with overarching contest in period 1 and individual contests in period 2 if the attacker wins period 1. With reasonable assumptions, such as contest intensities not exceeding one, the defender prefers two protection layers, while the attacker prefers one protection layer. When the unit effort costs of overarching protection and attack are equal, and the agents’ valuations for each asset are equal, in the simultaneous game defender and attacker efforts are equal in the overarching contest. In contrast, for the two period game, the defender invests more than the attacker in the overarching contest to prevent the occurrence of period 2. If the attacker nevertheless wins period 1, both agents exert larger efforts in period 2 compared with the individual contests in the simultaneous game. Framed within the Colonel Blotto literature, the attacker must win the first battlefield (overarching contest) in order to engage in the contests over the n other battlefields (individual contests).     

Endogenizing the sticks and carrots: modeling possible perverse effects of counterterrorism measures

We present a novel model capable of distinguishing between the effects of negative incentives (“sticks”) and positive incentives (“carrots”) for influencing the behavior of intelligent and adaptable adversaries. Utilities are developed for the defender and the terrorist. The defender is assumed to have a unit cost of defense, and unit costs of providing negative and positive incentives. The terrorist likewise has a unit cost of attack, which may either increase or decrease if the defender provides negative incentives, and enjoys a unit benefit of positive incentives. We show that the potential for perverse effects of counterterrorism (e.g., the emergence of hatred) can cause defenders to rely on positive incentives and decrease their reliance on negative incentives at equilibrium, with use of negative incentives completely eliminated in situations where these would be moderately effective when applied. With low potential for perverse effects of counterterrorism, the defender should rely on effective negative incentives.     

Parallel systems under two sequential attacks with contest intensity variation

Single and double attacks against a system of parallel elements are analyzed. The vulnerability of each element depends on an attacker-defender contest success function. The contest intensity may change from the first to the second attack as determined by a contest intensity variation factor. The defender allocates its resource between deploying elements to provide redundancy, and protecting each element. The attacker allocates its resource optimally across the two attacks, may attack a subset of the elements in the first attack, observes which elements are destroyed in the first attack, and attacks all surviving elements in the second attack. A minmax two period game is analyzed where the defender moves first and the attacker moves second. The paper shows how the contest intensity variation factor affects the defense and attack strategies.     

Separation in homogeneous systems with independent identical elements

The paper considers strategic defense and attack of a system which can be separated into independent identical homogeneous parallel elements. The defender distributes its resource between separation of the elements and their protection from outside attacks. The attacker distributes its effort evenly among all attacked elements. The vulnerability of each element is determined by a contest success function between the attacker and the defender. The defender can choose a subset of the elements to defend. The attacker does not know which elements are protected and can choose a number of randomly chosen elements to attack. Separation efficiency conditions are formulated dependent on the defender’s and attacker’s budgets, separation costs, contest intensity, and system demand. An algorithm for determining the optimal number of protected elements is suggested for the case when both the defender and the attacker can choose the number of protected and attacked elements freely. The article considers both the cases without and with performance redundancy. Illustrative numerical examples are presented.     

Hybrid defensive resource allocations in the face of partially strategic attackers in a sequential defender–attacker game

Many models have been developed to study homeland security games between governments (defender) and terrorists (attacker, adversary, enemy), with the limiting assumption of the terrorists being rational or strategic. In this paper, we develop a novel hybrid model in which a centralized government allocates defensive resources among multiple potential targets to minimize total expected loss, in the face of a terrorist being either strategic or non-strategic. The attack probabilities of a strategic terrorist are endogenously determined in the model, while the attack probabilities of a non-strategic terrorist are exogenously provided. We study the robustness of defensive resource allocations by comparing the government’s total expected losses when: (a) the government knows the probability that the terrorist is strategic; (b) the government falsely believes that the terrorist is fully strategic, when the terrorist could be non-strategic; and (c) the government falsely believes that the terrorist is fully non-strategic, when the terrorist could be strategic. Besides providing six theorems to highlight the general results, we find that game models are generally preferred to non-game model even when the probability of a non-strategic terrorist is significantly greater than 50%. We conclude that defensive resource allocations based on game-theoretic models would not incur too much additional expected loss and thus more preferred, as compared to non-game-theoretic models.     

False targets efficiency in defense strategy

The paper analyzes the efficiency of deploying false targets as part of a defense strategy. It is assumed that the defender has a single object that can be destroyed by the attacker. The defender distributes its resource between deploying false targets and protecting the object from outside attacks. The attacker cannot distinguish the false targets from the defended object (genuine target). Therefore the attacker has no preferences for attacking one target rather than another target. The defender decides how many false targets to deploy whereas the attacker decides how many targets to attack. The article assumes that both the defender and attacker have complete information and full rationality. The optimal number of false targets and the attacked targets are obtained for the case of fixed and variable resources of the defender and the attacker as solutions of a non-cooperative game between the two agents.     

Parallel systems under two sequential attacks with imperfect detection of the first attack outcome

The paper compares the efficiency of single and double attack against a system consisting of identical parallel elements. An attacker maximizes the system vulnerability (probability of total destruction). In order to destroy the system, the attacker distributes its constrained resource optimally across two attacks and chooses the number of elements to be attacked in the first attack. The attacker observes which elements are destroyed and not destroyed in the first attack and allocates its remaining resource into attacking the remaining elements in the second attack. The paper considers two types of identification errors: wrong identification of a destroyed element as not destroyed, and wrong identification of a not destroyed element as destroyed. First, the influence of the identification error probabilities on the optimal attack strategy against a system with a fixed number of elements is analysed. Thereafter, a minmax two-period game between the attacker and the defender is considered, in which the defender in the first period distributes its constrained resource between deploying redundant elements and protecting them against the attack in the second period. It is shown how the identification error probabilities affect the defence strategy.     

Optimal defence of single object with imperfect false targets

The paper considers an object exposed to external intentional attacks. The defender distributes its resource between deploying false targets and protecting the object. The false targets are not perfect and there is a nonzero probability that a false target can be detected by the attacker. Once the attacker has detected a certain number of false targets, it ignores them and chooses such number of undetected targets to attack that maximizes the probability of the object destruction. The defender decides how many false targets to deploy in order to minimize the probability of the object destruction assuming that the attacker uses the most harmful strategy to attack. The optimal number of false targets and the optimal number of attacked targets are obtained for the case of single and multiple types of the false targets. A methodology of finding the optimal defence strategy under uncertain contest intensity is suggested.     

A cutting-plane algorithm for solving a weighted influence interdiction problem

We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or “influence”) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender’s action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t?1. The attacker’s objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker’s problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker’s problem, and develop a tailored cutting-plane algorithm for solving the defender’s problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.     

A Bilevel p-median model for the planning and protection of critical facilities

The bilevel p-median problem for the planning and protection of critical facilities involves a static Stackelberg game between a system planner (defender) and a potential attacker. The system planner determines firstly where to open p critical service facilities, and secondly which of them to protect with a limited protection budget. Following this twofold action, the attacker decides which facilities to interdict simultaneously, where the maximum number of interdictions is fixed. Partial protection or interdiction of a facility is not possible. Both the defender’s and the attacker’s actions have deterministic outcome; i.e., once protected, a facility becomes completely immune to interdiction, and an attack on an unprotected facility destroys it beyond repair. Moreover, the attacker has perfect information about the location and protection status of facilities; hence he would never attack a protected facility. We formulate a bilevel integer program (BIP) for this problem, in which the defender takes on the leader’s role and the attacker acts as the follower. We propose and compare three different methods to solve the BIP. The first method is an optimal exhaustive search algorithm with exponential time complexity. The second one is a two-phase tabu search heuristic developed to overcome the first method’s impracticality on large-sized problem instances. Finally, the third one is a sequential solution method in which the defender’s location and protection decisions are separated. The efficiency of these three methods is extensively tested on 75 randomly generated instances each with two budget levels. The results show that protection budget plays a significant role in maintaining the service accessibility of critical facilities in the worst-case interdiction scenario.     

Strategic defense and attack for series and parallel reliability systems

A system of independent components is defended by a strategic defender and attacked by a strategic attacker. The reliability of each component depends on how strongly it is defended and attacked, and on the intensity of the contest. In a series system, the attacker benefits from a substitution effect since attacker benefits flow from attacking any of the components, while the defender needs to defend all components. Even for a series system, when the attacker is sufficiently disadvantaged with high attack inefficiencies, and the intensity of the contest is sufficiently high, the defender earns maximum utility and the attacker earns zero utility. The results for the defender (attacker) in a parallel system are equivalent to the results for the attacker (defender) in a series system. Hence, the defender benefits from the substitution effect in parallel systems. With budget constraints the ratio of the investments for each component, and the contest success function for each component, are the same as without budget constraints when replacing the system values for the defender and attacker with their respective budget constraints.     

Defence resource distribution between protection and decoys for constant resource stockpiling pace

The paper considers the optimal resource distribution between increasing protection of genuine elements and deploying decoys (false targets) in a situation when the attacker's and defender's resources are stockpiling and the resource increment rate is constant. It is assumed that the system must perform within an exogenously given time horizon and the attack time probability is uniformly distributed over this horizon. Series and parallel systems are considered. The defender optimizes the resource distribution in order to minimize the system vulnerability. The attacker cannot distinguish genuine and false elements and can attack a randomly chosen subset of the elements.     

Modeling secrecy and deception in a multiple-period attacker–defender signaling game

In this paper, we apply game theory to model strategies of secrecy and deception in a multiple-period attacker–defender resource-allocation and signaling game with incomplete information. At each period, we allow one of the three possible types of defender signals—truthful disclosure, secrecy, and deception. We also allow two types of information updating—the attacker updates his knowledge about the defender type after observing the defender’s signals, and also after observing the result of a contest (if one occurs in any given time period). Our multiple-period model provides insights into the balance between capital and expense for defensive investments (and the effects of defender private information, such as defense effectiveness, target valuations, and costs), and also shows that defenders can achieve more cost-effective security through secrecy and deception (possibly lasting more than one period), in a multiple-period game.     

Defence and attack of systems with variable attacker system structure detection probability

A system consists of identical elements. The cumulative performance of these elements should meet a demand. The defender applies three types of defensive actions to reduce a damage associated with system performance reduction caused by an external attack: deploying separated redundant genuine system elements, deploying false elements, and protecting genuine elements. If the attacker cannot distinguish between genuine and false elements, he chooses a number of elements to attack and then selects the elements at random, distributing his resources equally across these elements. By obtaining intelligence data, the attacker can get full information about the system structure and identify false and unprotected genuine elements. The defender estimates the probability that the attacker can identify all system elements. This paper analyses the influence of this probability in a non-cooperative two-period minmax game between the defender and the attacker.     

Heterogeneous surface-to-air missile defense battery location: a game theoretic approach

In the context of an air defense missile-and-interceptor engagement, a challenge for the defender is that surface-to-air missile batteries often must be located to protect high-value targets dispersed over a vast area, subject to which an attacker may observe the disposition of batteries and subsequently develop and implement an attack plan. To model this scenario, we formulate a two-player, extensive form, three-stage, perfect information, zero-sum game that accounts for, respectively, a defender’s location of batteries, an attacker’s launch of missiles against targets, and a defender’s assignment of interceptor missiles from batteries to incoming attacker missiles. The resulting trilevel math programming formulation cannot be solved via direct optimization, and it is not suitable to solve via full enumeration for realistically-sized instances. We instead adapt the game tree search technique Double Oracle, within which we embed either of two alternative heuristics to solve an important subproblem for the attacker. We test and compare these solution methods to solve a designed set of 52 instances having parametric variations, from which we derive insights regarding the nature of the underlying problem. Enhancing the solution methods with alternative initialization strategies, our superlative methodology attains the optimal solution for over 75% of the instances tested and solutions within 3% of optimal, on average, for the remaining 25% of the instances, and it is promising for realistically-sized instances, scaling well with regard to computational effort.     

Secure sets and their expansion in cubic graphs

Consider a graph whose vertices play the role of members of the opposing groups. The edge between two vertices means that these vertices may defend or attack each other. At one time, any attacker may attack only one vertex. Similarly, any defender fights for itself or helps exactly one of its neighbours. If we have a set of defenders that can repel any attack, then we say that the set is secure. Moreover, it is strong if it is also prepared for a raid of one additional foe who can strike anywhere. We show that almost any cubic graph of order n has a minimum strong secure set of cardinality less or equal to n/2 + 1. Moreover, we examine the possibility of an expansion of secure sets and strong secure sets.     

An attrition game on a network ruled by Lanchester’s square law

We consider two-person zero-sum attrition games in which an attacker and a defender are in combat with each other on a network. The attacker marches from a starting node to a destination node, hoping that the initial members survive the march. The defender deploys his forces on arcs in order to intercept the attacker. If the attacker encounters the defender on an arc, the attacker incurs casualties according to Lanchester’s square law. We consider two models: a one-shot game in which the two players have no information about their opponents, and a two-stage game in which both players have some information about their opponents. For both games, the payoff is defined as the number of survivors for the attacker. The attacker’s strategy is to choose a path, and the defender’s is to deploy the defending forces on arcs. We propose a numerical algorithm, in which nonlinear programming is embedded, to derive the equilibrium of the game.     

Incorporating the threat of terrorist attacks in the design of public service facility networks

In this paper, we consider the design problem of a public service facility network with existing facilities when there is a threat of possible terrorist attacks. The aim of the system planner, who is responsible for the operation of the network, is to open new facilities, relocate existing ones if necessary, and protect some of the facilities to ensure a maximum coverage of the demand that is assumed to be aggregated at customer zones. By doing so, the system planner anticipates that a number of unprotected facilities will be rendered out-of-service by terrorist attacks. It is assumed that the sum of the fixed cost of opening new facilities, the relocation costs, and the protection costs cannot exceed a predetermined budget level. Adopting the approach of gradual (or partial) coverage, we formulate a bilevel programming model where the system planner is the leader and the attacker is the follower. The objective of the former is the maximization of the total service coverage, whereas the latter wants to minimize it. We propose a heuristic solution procedure based on tabu search where the search space consists of the decisions of the system planner, and the corresponding objective value is computed by optimally solving the attacker??s problem using CPLEX. To assess the quality of the solutions produced by the tabu search (TS) heuristic, we also develop an exhaustive enumeration method, which explores all the possible combinations of opening new facilities, relocating existing ones, and protecting them. Since its time complexity is exponential, it can only be used for relatively small instances. Therefore, to be used as a benchmark method, we also implement a hill climbing procedure employed with the same type of moves as the TS heuristic. Besides, we carry out a sensitivity analysis on some of the problem parameters to investigate their effect on the solution characteristics.     

The budget constrained r-interdiction median problem with capacity expansion

In this article, we elaborate on a budget constrained extension of the r-interdiction median problem with fortification (RIMF). The objective in the RIMF is to find the optimal allocation of protection resources to a given service system consisting of p facilities so that the disruptive effects of r possible attacks to the system are minimized. The defender of the system needs to fortify q facilities of the present system to offset the worst-case loss of r non-fortified facilities due to an interdiction in which the attacker’s objective is to cause the maximum possible disruption in the service level of the system. The defender-attacker relationship fits a bilevel integer programming (BIP) formulation where the defender and attacker take on the respective roles of the leader and the follower. We adopt this BIP formulation and augment it with a budget constraint instead of a predetermined number of facilities to be fortified. In addition, we also assume that each facility has a flexible service capacity, which can be expanded at a unit cost to accommodate the demand of customers who were serviced by some other interdicted facility before the attack. First, we provide a discrete optimization model for this new facility protection planning scenario with a novel set of closest assignment constraints. Then, to tackle this BIP problem we use an implicit enumeration algorithm performed on a binary tree. For each node representing a different fortification scheme, the attacker’s problem is solved to optimality using Cplex 11. We report computational results obtained on a test bed of 96 randomly generated instances. The article concludes with suggestions for future research.