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.     

Improved cryptanalysis of rank metric schemes based on Gabidulin codes

We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck’s structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way corrects less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender. Consequently, an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometric transformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existing techniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed.     

Critique of the related-key attack concept

In a related-key attack, an attacker seeks to discover the secret key by requesting encryptions under keys related to the secret key in a manner chosen by the attacker. We describe a new related-key attack against generic ciphers, requiring just O(1) work to distinguish a cipher from random, and O(key length) to completely recover the secret key. This attack applies within a model which was not previously known to be vulnerable, undermining the theoretical foundation of the related-key attack concept. We propose a new definition of related-key security, which prevents all known generic attacks including this new attack. We discuss the theoretical consequences of this new definition.     

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).     

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.     

The timing and deterrence of terrorist attacks due to exogenous dynamics

In this paper, we develop a model for the timing and deterrence of terrorist attacks due to exogenous dynamics. The defender moves first and the attacker second in a two-stage game which is repeated over T periods. We study the effects of dynamics of several critical components of counter-terrorism games, including the unit defence costs (eg, immediately after an attack, the defender would easily acquire defensive funding), unit attack costs (eg, the attacker may accumulate resources as time goes), and the asset valuation (eg, the asset valuation may change over time). We study deterministic dynamics and conduct simulations using random dynamics. We determine the timing of terrorist attacks and how these can be deterred.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Fault analysis of Trivium

As a hardware-oriented stream cipher, Trivium is on the edge of low cost and compactness. In this paper we discuss how brittle Trivium is under fault attack. Our fault model is based on the following two assumptions: (1) We can make fault injection on the state at a random time and (2) after each fault injection, the fault positions are from random one of three registers, and from a random area within eight neighboring bits. Our fault model has extremely weak assumptions for effective attack , and much weaker than that of Hojsík and Rudolf, in their fault attack on Trivium. We present a checking method such that, by observing original key-stream segment and fault injected key-stream segment, the injecting time and fault positions can be determined. Then, for several distributions of the injecting time, our random simulations always show that the attacker can break Trivium by a small number of repeated fault injections. For example, suppose that the injecting time has an uniform distribution over {0, 1, . . . , 32}, then averagely no more than 16 repeated fault injection procedures will break Trivium, by averagely observing no more than 195 × 17 key-stream bits.     

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.     

基于多目标双层规划的智能电网虚假数据注入攻击研究

相对于传统电网,智能电网引入了先进的信息通信技术能显著提高企业生产效率和电力数据处理效率,但由于传统状态估计的漏洞,智能电网易受到虚假数据注入的攻击。现有的研究仅追求电力系统运营成本的最大化或攻击资源的最小化,没有考虑两者之间的均衡。基于此,本文考虑建立智能电网虚假数据注入攻击双层多目标规划模型,其中多目标表示电力系统运营成本与攻击成本之间的均衡,并结合IEEE 14总线算例进行分析,针对攻击者不同的攻击倾向给出了相应的虚假数据注入攻击策略。