# Multistage Attack Graph Security Games: Heuristic Strategies, with Empirical Game-Theoretic Analysis

Authors: Thanh H. Nguyen; Mason Wright; Michael P. Wellman; Satinder Singh
Journal: Security and Communication Networks
 (2018)

---

## Abstract

We study the problem of allocating limited security countermeasures to protect network data from cyber-attacks, for scenarios modeled by Bayesian attack graphs. We consider multistage interactions between a network administrator and cybercriminals, formulated as a security game. This formulation is capable of representing security environments with significant dynamics and uncertainty and very large strategy spaces. We propose parameterized heuristic strategies for the attacker and defender and provide detailed analysis of their time complexity. Our heuristics exploit the topological structure of attack graphs and employ sampling methods to overcome the computational complexity in predicting opponent actions. Due to the complexity of the game, we employ a simulation-based approach and perform empirical game analysis over an enumerated set of heuristic strategies. Finally, we conduct experiments in various game settings to evaluate the performance of our heuristics in defending networks, in a manner that is robust to uncertainty about the security environment.


---

## Body

## 1. Introduction

Attack graphs are graphical models used in cybersecurity research to decompose complex security scenarios into a hierarchy of simple and quantifiable actions [1–3]. Many research efforts have employed attack graphs or related graphical security models to analyze complex security scenarios [4, 5]. In particular, attack graph models have been used to evaluate network hardening strategies, where a network administrator (the defender) deploys security countermeasures to protect network data from cybercriminals (the attacker) [6–13].Attack graphs are particularly suitable for modeling scenarios in moving target defense (MTD) [14], where the defender employs proactive tactics to dynamically change network configurations, limiting the exposure of vulnerabilities. MTD techniques are most useful in thwarting progressive attacks [15–17], where system reconfiguration by the defender prevents the attacker from exploiting knowledge accumulated over time. Attack graphs naturally represent the progress of an attack, and the defense actions in our model can incorporate MTD methods.We build on prior works that represent security problems with attack graphs, and we take a game-theoretic approach to reasoning about the strategic interaction between the defender and the attacker. Building on an existing Bayesian attack graph formalism [11, 18], we model the problem as a simultaneous multistage attack graph security game. Nodes in a Bayesian attack graph represent security conditions of the network system. For example, an SSH buffer overflow vulnerability in an FTP server can be considered a security condition, as can user privileges achieved as a result of exploiting that vulnerability. The defender attempts to protect a set of goal nodes (critical security conditions) in the attack graph. Conversely, the attacker, starting from some initial security conditions, follows paths through the graph to undermine these goal nodes. At every time step, the defender and the attacker simultaneously take actions. Given limited security resources, the defender has to decide for which nodes of the attack graph to deploy security countermeasures. Meanwhile, the attacker selects nodes to attack in order to progress toward the goals. The outcome of the players’ actions (whether the attacker succeeds) follows a stochastic process, which represents the success probability of the actions taken. These outcomes are only imperfectly observed by the defender, adding further uncertainty which must be considered in its strategic reasoning.Based on our game model, we propose various parameterized strategies for both players. Our attack strategies assess the value of each possible attack action at a given time step by examining the future attack paths they enable. These paths are sequences of nodes which could feasibly be attacked in subsequent time steps (as a result of attack actions in the current time step) in order to reach goal nodes. Since there are exponentially many possible attack paths, it is impractical to evaluate all of them. Therefore, our attack heuristics incorporate two simplifying approximations. First, we estimate the attack value for each individual node locally, based on the attack values of neighboring nodes. Attack values of goal nodes, in particular, correspond to the importance of each goal node. Second, we consider only a small subset of attack paths, selected by random sampling, according to the likelihood that the attacker will successfully reach a goal node by following each path. We present a detailed analysis of the polynomial time complexity of our attack heuristics.Likewise, our heuristic defense strategies employ simplifying assumptions. At each time step, the defense strategies: (i) update the defender’s belief about the outcome of players’ actions in the previous time step and (ii) generate a new defense action based on the updated belief and the defender’s assumption about the attacker’s strategy. For stage (i), we apply particle filtering [19] to deal with the exponential number of possible outcomes. For stage (ii), we evaluate defense candidate actions using concepts similar to those employed in the attack strategies. We show that the running time of our defense heuristics is also polynomial.Finally, we employ a simulation-based methodology calledempirical game-theoretic analysis (EGTA) [20], to construct and analyze game models over the heuristic strategies. We present a detailed evaluation of the proposed strategies based on this game analysis. Our experiments are conducted over a variety of game settings with different attack graph topologies. We show that our defense strategies provide high solution quality compared to multiple baselines. Furthermore, we examine the robustness of defense strategies to uncertainty about game states and about the attacker’s strategy.


## 2. Related Work

Attack graphs are commonly used to provide a convenient representation for analysis of network vulnerabilities [1–3]. In an attack graph, nodes represent attack conditions of a system, and edges represent relationships among these conditions: specifically, how the achievement of specific conditions through an attacker’s actions can enable other conditions. Various graph-based security models related to attack graphs have been proposed to represent and analyze complex security scenarios [5]. For example, Wang et al. [21] introduced such a model for correlating, hypothesizing, and predicting intrusion alerts.Temporal attack graphs, introduced by Albanese and Jajodia [4], extend the attack graph model of Wang et al. [21] with additional temporal constraints on the unfolding of attacks.Augmented attack trees were introduced by Ray and Poolsapassit [22] to probabilistically measure the progression of an attacker’s actions toward compromising the system. This concept of augmented attack trees was later used to perform a forensic analysis of log files [23]. Vidalis et al. [24] presentedvulnerability trees to capture the interdependency between different vulnerabilities of a system.Bayesian attack graphs [25] combine attack graphs with quantified uncertainty on attack states and relations. Revised versions of Bayesian attack graphs incorporate other security aspects such as dynamic behavior and mitigation strategies [18, 26]. Our work is based on the specific formulation of Bayesian attack graphs by Poolsappasit et al. [18]. The basic ideas of our game model and heuristic strategies would also apply to variant forms of graph-based security models with reasonable modifications. In particular, our work might be extended to handle zero-day attacks captured by zero-day attack graphs [27–30] by incorporatingpayoff uncertainty as a result of unknown locations and impacts of zero-day vulnerabilities. In the scope of this work, we consider known payoffs of players.Though many attack graph models attempt to analyze different progressive attack scenarios without considering countermeasures of a defender, there is an important line of work on graph-based models covering both attacks and defenses [5]. For example, Wu et al. introducedintrusion DAGs to represent the underlying structure of attacker goals in an adaptive, intrusion-tolerant system. Each node of an intrusion DAG is associated with an alert from the intrusion-detection framework, allowing the system to automatically trigger a response.Attack-Response Trees (ARTs), introduced by Zonouz et al. [13], extend attack trees to incorporate possible response actions against attacks.Given the prominence of graph-based security models, previous work has proposed different game-theoretic solutions for finding an optimal defense policy based on those models. Durkota et al. [8, 9] study the problem of hardening the security of a network by deploying honeypots to the network to deceive the attacker. They model the problem as a Stackelberg security game in which the attacker’s plans are compactly represented using attack graphs. Zonouz et al. [13] present an automated intrusion-response system which models the security problem on an attack-response tree as a two-player, zero-sum Stackelberg stochastic game. Besides Stackelberg games, single-stage simultaneous games are also applied to model the security problem on attack-defense trees, and Nash equilibrium is used to find an optimal defense policy [6, 7, 10].Game theory has been applied for solving various cybersecurity problems [31–38]. Previous work has modeled these security problems as a dynamic (complete/incomplete/imperfect) game and analyzed equilibrium solutions of those games. Our game model (to represent security problems with attack graphs) belongs to the class of partially observable stochastic games. Since the game is too complex for analytic solution, we focus on developing heuristic strategies for players and employing the simulation-based methodology EGTA to evaluate these strategies.Similar to our work, the non-game-theoretic solution proposed by Miehling et al. [11] is also built on the attack graph formalism of Poolsappasit et al. [18]. In their work, the attacker’s behavior is modeled by a probabilistic spreading process, which is known by the defender. In our model, on the other hand, both the defender and the attacker dynamically decide on which actions to take at every time step, depending on their knowledge with respect to the game.


## 3. Game Model

### 3.1. Game Definition

Definition 1 (Bayesian attack graph [18]).
ABayesian attack graph is a directed acyclic graph, denoted by G=V,s0,E,θ,p. (i)
V is a nonempty set of nodes, representing security-related attributes of the network systems including (i) system vulnerabilities; (ii) insecure system properties such as corrupted files or memory access permissions; (iii) insecure network properties such as unsafe network conditions or unsafe firewall properties; and (iv) access privilege conditions such as user account or root account.(ii)
At timet, each node v has astatest(v)∈{0,1}, where 0 means v isinactive (i.e., a security state not compromised by the attacker) and 1 means it isactive (compromised). Theinitial states0(v) represents the initial setting of node v. For example, suppose a node (representing the root access privilege on a machine) is active; this means the attacker has the root access privilege on that machine.(iii)
E is a set of directed edges between nodes in V, with each edge representing anatomic attack action or anexploit. For edge e=(u,v)∈E, u is called aprecondition and v is called apostcondition. For example, suppose a node u represents the SSHD BOF vulnerability on machine A and node v represents the root access privilege on A. Then the exploit (u,v) indicates that the attacker can exploit the SSHD BOF vulnerability on A to obtain the root access privilege on A. We denote by π-(v)={u∣(u,v)∈E} the set of preconditions and by π+(v)={u∣(v,u)∈E} the set of postconditions associated with node v∈V. An exploit e=(u,v)∈E isfeasible when its precondition u is active.(iv)
NodesVr={v∈V∣π-(v)=∅} without preconditions are calledroot nodes. Nodes Vl={v∈V∣π+(v)=∅} without postconditions are calledleaf nodes.(v)
Each nodev∈V is assigned anode typeθ(v)∈{∨,∧}. An ∨-type node v can be activated via any of the feasible exploits into v. Activating an ∧-type node v requires all exploits into v to be feasible and taken. Root nodes (∧-type nodes without preconditions) have no prerequisite exploits and so can be activated directly. We denote by V∧ the set of all ∧-type nodes and by V∨ the set of all ∨-type nodes. The sets of edges into ∨-type nodes and ∧-type nodes, respectively, are denoted by E∨={(u,v)∈E∣v∈V∨} and E∧={(u,v)∈E∣v∈V∧}.(vi)
Theactivation probabilityp(e)∈(0,1] of edge e=(u,v)∈E∨ represents the probability that the ∨-node v becomes active when the exploit e is taken (assuming v is not defended, u is active, and no other exploit (u′,v) is attacked). ∧-type nodes are also associated with activation probabilities; p(v)∈(0,1] is the probability that v∈V∧ becomes active when all exploits into v are taken (assuming v is not defended and all parent nodes of v are active).An example of a Bayesian attack graph based on this definition is shown in Figure1. Our multistage Bayesian attack graph security game model is defined as follows.Figure 1
Portion of Bayesian attack graph for testbed network of Poolsappasit et al. [18]. The node with exploits connected by an arc is ∧-type; the rest are ∨-type. Dotted edges indicate excluded portions of the graph. In this graph portion, there are four nodes representing system vulnerabilities and access privileges. The attacker can exploit the heap corruption in OpenSSH at the gateway server to obtain root access privileges. Then the attacker can exploit root access privileges at the gateway server and the network topology leakage at the mail server to cause the stack BOF in the MS SMV service of the admin machine.Definition 2 (attack graph game).
A Bayesian attack graph security game is defined on a Bayesian attack graphG=V,s0,E,θ,p by elements Ψ=(T,Vg,S,O,D,A,R,C): (i)
Time step: T={0,…,T} where T is the time horizon.(ii)
Player goal: A nonempty subset Vg⊆V of nodes are distinguished ascritical security conditions. The attacker aims to activate thesegoal nodes while the defender attempts to keep them inactive.(iii)
Graph state: S={S0,…,ST} where St={v∈V∣st(v)=1} represents the active nodes at time step t.(iv)
Defender observation: O={O0,…,OT}, where Ot associates each node v with one of the signals {0v,1v}. Signal 1v (0v) indicates v is active (inactive). If v is active at t, signal 1v is generated with probability p(1v∣st(v)=1)∈(0,1], and if v is inactive, signal 1v is generated with probability p(1v∣st(v)=0)<p(1v∣st(v)=1). Otherwise, signal 0v is generated. The signals are independently distributed, over time and nodes.(v)
Player action: D={D0,…,DT} where defender action Dt⊆V comprises a set of nodes which the defenderdisables at time step t. A={A0,…,AT} where attacker action At⊆V∧∪E∨ consists of (i) ∧-type nodes v∈V∧, meaning that the attacker takes all exploits into v to activate that node at time step t, and (ii) exploits into ∨-type nodes (u,v)∈E∨, meaning that attacker takes exploit (u,v) to activate the ∨-type node v at time step t.(vi)
Goal reward: R assigns a reward for the players to each goal node v∈Vg. ra(v)>0 is the attacker reward and rd(v)<0 is the defender reward (i.e., a penalty) if v is active. For inactive goal nodes, both receive zero.(vii)
Action cost: C assigns a cost to each action the players take. In particular, ca(e)<0 is the attacker’s cost to attempt exploit e∈E∨ and ca(v) is the attacker’s cost to attempt all exploits into ∧-type node v∈V∧. The defender incurs cost cd(v)<0 to disable node v∈V.(viii)
Discount factor: γ∈(0,1].Initially,D0≡∅, A0≡∅, and S0≡∅. We assume the defender knows only the initial graph state S0, whereas the attacker is fully aware of graph states at every time step. Thus, we can set O0=∅. At each time step t+1∈{1,…,T}, the attacker decides which feasible exploits to attempt. At time step 1, in particular, the attacker can choose any root nodes v∈Vr to activate directly with a success probability p(v). Simultaneously, the defender decides which nodes to disable to prevent the attacker from intruding further. An example attack graph is shown in Figure 2.Figure 2
Bayesian attack graph example. Nodes with incoming edges connected by black curves are∧-type. The others are ∨-type. For instance, activating ∧-type node 4 requires all exploits from nodes 0, 1, and 3 to 4 to be feasible and taken by the attacker. At the current time step, red nodes 1, 2, and 5 are active. Other grey and green nodes are inactive. Thus, the attacker’s action can be any subset of green nodes and green exploits. For example, the attacker can directly activate the root nodes 0 and 3. The attacker can also activate node 9 by taking the feasible exploit (1,9). Conversely, the defender can choose any subset of nodes to protect. Suppose the attacker decides to activate node 0 and node 9 (via exploit (1,9)) while the defender decides to protect nodes 0 and 7. Then node 0 remains inactive. Node 9 becomes active with an activation probability associated with exploit (1,9).


### 3.2. Network Example

We first briefly present the testbed network introduced by Poolsappasit et al. [18]. We then describe a portion of the corresponding Bayesian attack graph with security controls of the network. Our security game model and proposed heuristic strategies for both the defender and attacker are built based on their model.Overall, the testbed network consists of eight hosts located within two different subnets: DMZ zone and Trusted zone. The DMZ zone includes a mail server, a DNS server, and a web server. The Trusted zone has two local desktops, an administrative server, a gateway server, and an SQR server. There is an installed trihomed DMZ firewall with a set of policies to separate servers in the DMZ network from the local network. The attacker has to pass the DMZ firewall to attack the network. The web server in the DMZ zone can send SQL queries to the SQL server in the Trusted zone on a designated channel. In the Trusted zone, there is a NAT firewall such that local machines (located behind NAT) have to communicate with external parties through the gateway server. Finally, the gateway server monitors remote connections through SSHD.There are several vulnerabilities associated with each machine which can be exploited by the attacker in the testbed network. For example, the gateway server has to faceheap corruption in OpenSSH andimproper cookie handler in OpenSSH. In addition, SQL and DNS servers have to deal with theSQR injection andDNS cache poisoning vulnerabilities, respectively. The defender can deploy security controls such aslimit access to DNS server to tackle the vulnerabilityDNS cache poisoning [18].A portion of the Bayesian attack graph of the testbed network is shown in Figure3. A complete Bayesian attack graph can be found in Poolsappasit et al. [18]. Each grey rectangle represents a security attribute of the network. For example, the attacker can exploit thestack BOF at local desktops to obtain theroot access privilege at those desktops. Then by exploiting theroot access privilege, the attacker can achieve theerror message leakage at the mail server and theDNS cache poisoning at the DNS server. Finally, the attacker can obtain theidentity theft andinformation leakage by exploiting theerror message leakage at the mail server, etc. To prevent such attack progression, the defender can deploy theMS workaround to deal with the vulnerabilitystack BOF. The defender can also deployPOP3 andlimit access to DNS server to address the vulnerabilitieserror message leakage andDNS cache poisoning, respectively. Finally,encryption anddigital signature could be used to resolve theidentity theft issues at the DNS and mail server.Figure 3
A portion of the Bayesian attack graph of the testbed network in Poolsappasit et al. [18].


### 3.3. Timing of Game Events

The game proceeds in discrete time steps,t+1∈{1,…,T}, with both players aware of the current time. At each time step t+1, the following sequence of events occurs.(1)
Observations:
(i)
The attacker observesSt.(ii)
The defender observesOt~O(St).(2)
The attacker and defender simultaneously select actionsAt+1 and Dt+1 according to their respective strategies.(3)
The environment transitions to its next state according to the transition functionSt+1~T(St,At+1,Dt+1) (Algorithm 1).(4)
The attacker and defender assess rewards (and/or costs) for the time step.Algorithm 1:State transition for node v, according to T(St,At+1,Dt+1).
1 Initialize st+1(v)←st(v); 2  if  v∈Dt+1  then 3  s t + 1 ( v ) ← 0; // defender overrules attacker 4  else 5  if  v∈At+1∩V∧  and  π-(v)⊆St  then 6 with probability p(v), st+1(v)←1 7  else 8  for  (u,v)∈At+1∩E∨  and  u∈St  do 9 with probability p(u,v), st+1(v)←1When an active node is disabled by the defender, that node becomes inactive. If a node is activated by the attacker at the same step it is being disabled by the defender, the node remains inactive.


### 3.4. Payoff Function

We denote byΩT={(A0,D0,S0),…,(AT,DT,ST)} the game history, which consists of all actions and resulting graph states at each time step. At time t, St is a resulting graph state when the attacker plays At, the defender plays Dt, and the previous graph state is St-1. The defender and attacker’s payoffs with respect to ΩT, which comprise goal rewards and action costs, are computed as follows: (1)UdΩT=∑t=1Tγt-1∑v∈Dtcdv+∑v∈Vg∩StrdvUaΩT=∑t=1Tγt-1∑e∈At∩E∨cae+∑v∈At∩V∧cav+∑v∈Vg∩Strav.Both players aim to maximize expected utility with respect to the distribution of ΩT. Since the game is too complex for analytic solution, we propose heuristic strategies for both players and employ the simulation-based methodology EGTA to evaluate these strategies. Our heuristic strategies for each player are categorized based on (i) the assumptions regarding their opponent’s strategies and (ii) heuristic methods used to generate actions for the players to take at each time step. In particular, our proposed heuristic strategies can be explained in the following hierarchical view.


## 3.1. Game Definition

Definition 1 (Bayesian attack graph [18]).
ABayesian attack graph is a directed acyclic graph, denoted by G=V,s0,E,θ,p. (i)
V is a nonempty set of nodes, representing security-related attributes of the network systems including (i) system vulnerabilities; (ii) insecure system properties such as corrupted files or memory access permissions; (iii) insecure network properties such as unsafe network conditions or unsafe firewall properties; and (iv) access privilege conditions such as user account or root account.(ii)
At timet, each node v has astatest(v)∈{0,1}, where 0 means v isinactive (i.e., a security state not compromised by the attacker) and 1 means it isactive (compromised). Theinitial states0(v) represents the initial setting of node v. For example, suppose a node (representing the root access privilege on a machine) is active; this means the attacker has the root access privilege on that machine.(iii)
E is a set of directed edges between nodes in V, with each edge representing anatomic attack action or anexploit. For edge e=(u,v)∈E, u is called aprecondition and v is called apostcondition. For example, suppose a node u represents the SSHD BOF vulnerability on machine A and node v represents the root access privilege on A. Then the exploit (u,v) indicates that the attacker can exploit the SSHD BOF vulnerability on A to obtain the root access privilege on A. We denote by π-(v)={u∣(u,v)∈E} the set of preconditions and by π+(v)={u∣(v,u)∈E} the set of postconditions associated with node v∈V. An exploit e=(u,v)∈E isfeasible when its precondition u is active.(iv)
NodesVr={v∈V∣π-(v)=∅} without preconditions are calledroot nodes. Nodes Vl={v∈V∣π+(v)=∅} without postconditions are calledleaf nodes.(v)
Each nodev∈V is assigned anode typeθ(v)∈{∨,∧}. An ∨-type node v can be activated via any of the feasible exploits into v. Activating an ∧-type node v requires all exploits into v to be feasible and taken. Root nodes (∧-type nodes without preconditions) have no prerequisite exploits and so can be activated directly. We denote by V∧ the set of all ∧-type nodes and by V∨ the set of all ∨-type nodes. The sets of edges into ∨-type nodes and ∧-type nodes, respectively, are denoted by E∨={(u,v)∈E∣v∈V∨} and E∧={(u,v)∈E∣v∈V∧}.(vi)
Theactivation probabilityp(e)∈(0,1] of edge e=(u,v)∈E∨ represents the probability that the ∨-node v becomes active when the exploit e is taken (assuming v is not defended, u is active, and no other exploit (u′,v) is attacked). ∧-type nodes are also associated with activation probabilities; p(v)∈(0,1] is the probability that v∈V∧ becomes active when all exploits into v are taken (assuming v is not defended and all parent nodes of v are active).An example of a Bayesian attack graph based on this definition is shown in Figure1. Our multistage Bayesian attack graph security game model is defined as follows.Figure 1
Portion of Bayesian attack graph for testbed network of Poolsappasit et al. [18]. The node with exploits connected by an arc is ∧-type; the rest are ∨-type. Dotted edges indicate excluded portions of the graph. In this graph portion, there are four nodes representing system vulnerabilities and access privileges. The attacker can exploit the heap corruption in OpenSSH at the gateway server to obtain root access privileges. Then the attacker can exploit root access privileges at the gateway server and the network topology leakage at the mail server to cause the stack BOF in the MS SMV service of the admin machine.Definition 2 (attack graph game).
A Bayesian attack graph security game is defined on a Bayesian attack graphG=V,s0,E,θ,p by elements Ψ=(T,Vg,S,O,D,A,R,C): (i)
Time step: T={0,…,T} where T is the time horizon.(ii)
Player goal: A nonempty subset Vg⊆V of nodes are distinguished ascritical security conditions. The attacker aims to activate thesegoal nodes while the defender attempts to keep them inactive.(iii)
Graph state: S={S0,…,ST} where St={v∈V∣st(v)=1} represents the active nodes at time step t.(iv)
Defender observation: O={O0,…,OT}, where Ot associates each node v with one of the signals {0v,1v}. Signal 1v (0v) indicates v is active (inactive). If v is active at t, signal 1v is generated with probability p(1v∣st(v)=1)∈(0,1], and if v is inactive, signal 1v is generated with probability p(1v∣st(v)=0)<p(1v∣st(v)=1). Otherwise, signal 0v is generated. The signals are independently distributed, over time and nodes.(v)
Player action: D={D0,…,DT} where defender action Dt⊆V comprises a set of nodes which the defenderdisables at time step t. A={A0,…,AT} where attacker action At⊆V∧∪E∨ consists of (i) ∧-type nodes v∈V∧, meaning that the attacker takes all exploits into v to activate that node at time step t, and (ii) exploits into ∨-type nodes (u,v)∈E∨, meaning that attacker takes exploit (u,v) to activate the ∨-type node v at time step t.(vi)
Goal reward: R assigns a reward for the players to each goal node v∈Vg. ra(v)>0 is the attacker reward and rd(v)<0 is the defender reward (i.e., a penalty) if v is active. For inactive goal nodes, both receive zero.(vii)
Action cost: C assigns a cost to each action the players take. In particular, ca(e)<0 is the attacker’s cost to attempt exploit e∈E∨ and ca(v) is the attacker’s cost to attempt all exploits into ∧-type node v∈V∧. The defender incurs cost cd(v)<0 to disable node v∈V.(viii)
Discount factor: γ∈(0,1].Initially,D0≡∅, A0≡∅, and S0≡∅. We assume the defender knows only the initial graph state S0, whereas the attacker is fully aware of graph states at every time step. Thus, we can set O0=∅. At each time step t+1∈{1,…,T}, the attacker decides which feasible exploits to attempt. At time step 1, in particular, the attacker can choose any root nodes v∈Vr to activate directly with a success probability p(v). Simultaneously, the defender decides which nodes to disable to prevent the attacker from intruding further. An example attack graph is shown in Figure 2.Figure 2
Bayesian attack graph example. Nodes with incoming edges connected by black curves are∧-type. The others are ∨-type. For instance, activating ∧-type node 4 requires all exploits from nodes 0, 1, and 3 to 4 to be feasible and taken by the attacker. At the current time step, red nodes 1, 2, and 5 are active. Other grey and green nodes are inactive. Thus, the attacker’s action can be any subset of green nodes and green exploits. For example, the attacker can directly activate the root nodes 0 and 3. The attacker can also activate node 9 by taking the feasible exploit (1,9). Conversely, the defender can choose any subset of nodes to protect. Suppose the attacker decides to activate node 0 and node 9 (via exploit (1,9)) while the defender decides to protect nodes 0 and 7. Then node 0 remains inactive. Node 9 becomes active with an activation probability associated with exploit (1,9).


## 3.2. Network Example

We first briefly present the testbed network introduced by Poolsappasit et al. [18]. We then describe a portion of the corresponding Bayesian attack graph with security controls of the network. Our security game model and proposed heuristic strategies for both the defender and attacker are built based on their model.Overall, the testbed network consists of eight hosts located within two different subnets: DMZ zone and Trusted zone. The DMZ zone includes a mail server, a DNS server, and a web server. The Trusted zone has two local desktops, an administrative server, a gateway server, and an SQR server. There is an installed trihomed DMZ firewall with a set of policies to separate servers in the DMZ network from the local network. The attacker has to pass the DMZ firewall to attack the network. The web server in the DMZ zone can send SQL queries to the SQL server in the Trusted zone on a designated channel. In the Trusted zone, there is a NAT firewall such that local machines (located behind NAT) have to communicate with external parties through the gateway server. Finally, the gateway server monitors remote connections through SSHD.There are several vulnerabilities associated with each machine which can be exploited by the attacker in the testbed network. For example, the gateway server has to faceheap corruption in OpenSSH andimproper cookie handler in OpenSSH. In addition, SQL and DNS servers have to deal with theSQR injection andDNS cache poisoning vulnerabilities, respectively. The defender can deploy security controls such aslimit access to DNS server to tackle the vulnerabilityDNS cache poisoning [18].A portion of the Bayesian attack graph of the testbed network is shown in Figure3. A complete Bayesian attack graph can be found in Poolsappasit et al. [18]. Each grey rectangle represents a security attribute of the network. For example, the attacker can exploit thestack BOF at local desktops to obtain theroot access privilege at those desktops. Then by exploiting theroot access privilege, the attacker can achieve theerror message leakage at the mail server and theDNS cache poisoning at the DNS server. Finally, the attacker can obtain theidentity theft andinformation leakage by exploiting theerror message leakage at the mail server, etc. To prevent such attack progression, the defender can deploy theMS workaround to deal with the vulnerabilitystack BOF. The defender can also deployPOP3 andlimit access to DNS server to address the vulnerabilitieserror message leakage andDNS cache poisoning, respectively. Finally,encryption anddigital signature could be used to resolve theidentity theft issues at the DNS and mail server.Figure 3
A portion of the Bayesian attack graph of the testbed network in Poolsappasit et al. [18].


## 3.3. Timing of Game Events

The game proceeds in discrete time steps,t+1∈{1,…,T}, with both players aware of the current time. At each time step t+1, the following sequence of events occurs.(1)
Observations:
(i)
The attacker observesSt.(ii)
The defender observesOt~O(St).(2)
The attacker and defender simultaneously select actionsAt+1 and Dt+1 according to their respective strategies.(3)
The environment transitions to its next state according to the transition functionSt+1~T(St,At+1,Dt+1) (Algorithm 1).(4)
The attacker and defender assess rewards (and/or costs) for the time step.Algorithm 1:State transition for node v, according to T(St,At+1,Dt+1).
1 Initialize st+1(v)←st(v); 2  if  v∈Dt+1  then 3  s t + 1 ( v ) ← 0; // defender overrules attacker 4  else 5  if  v∈At+1∩V∧  and  π-(v)⊆St  then 6 with probability p(v), st+1(v)←1 7  else 8  for  (u,v)∈At+1∩E∨  and  u∈St  do 9 with probability p(u,v), st+1(v)←1When an active node is disabled by the defender, that node becomes inactive. If a node is activated by the attacker at the same step it is being disabled by the defender, the node remains inactive.


## 3.4. Payoff Function

We denote byΩT={(A0,D0,S0),…,(AT,DT,ST)} the game history, which consists of all actions and resulting graph states at each time step. At time t, St is a resulting graph state when the attacker plays At, the defender plays Dt, and the previous graph state is St-1. The defender and attacker’s payoffs with respect to ΩT, which comprise goal rewards and action costs, are computed as follows: (1)UdΩT=∑t=1Tγt-1∑v∈Dtcdv+∑v∈Vg∩StrdvUaΩT=∑t=1Tγt-1∑e∈At∩E∨cae+∑v∈At∩V∧cav+∑v∈Vg∩Strav.Both players aim to maximize expected utility with respect to the distribution of ΩT. Since the game is too complex for analytic solution, we propose heuristic strategies for both players and employ the simulation-based methodology EGTA to evaluate these strategies. Our heuristic strategies for each player are categorized based on (i) the assumptions regarding their opponent’s strategies and (ii) heuristic methods used to generate actions for the players to take at each time step. In particular, our proposed heuristic strategies can be explained in the following hierarchical view.


## 4. Level-0 Heuristic Strategies

We define alevel-0 strategy as one that does not explicitly invoke an assumption about its opponent’s strategy. Higher-level strategies do invoke such assumptions, generally that the others play one level below, in the spirit of cognitive hierarchy models [39]. In our context, level-0 heuristic strategies directly operate on the topological structure of the Bayesian attack graph to decide on actions to take at each time step.


### 4.1. Level-0 Defense Strategies

We introduce four level-0 defense strategies. Each targets a specific group of nodes to disable at each time stept+1. These groups of nodes are chosen solely based on the topological structure of the graph.


#### 4.1.1. Level-0 Uniform Defense Strategy

The defender chooses nodes in the graph to disable uniformly at random. The number of nodes chosen is a certain fraction of the total number of nodes in the graph.


#### 4.1.2. Level-0 Min-Cut Uniform Defense Strategy

The defender chooses nodes in the min-cut set to disable uniformly at random. The min-cut set is the minimum set of edges such that removing them disconnects the root nodes from the goal nodes. The number of chosen nodes is a certain fraction of the cardinality of the min-cut set.


#### 4.1.3. Level-0 Root-Node Uniform Defense Strategy

The defender chooses root nodes to disable uniformly at random. The number of nodes chosen is a certain fraction of the total number of root nodes in the graph.


#### 4.1.4. Level-0 Goal-Node Defense Strategy

The defender randomly chooses goal nodes to disable with probabilities depending on the rewards and costs associated with these goal nodes. The probability of disabling each goal nodev∈Vg is based on the conditional logistic function: (2)pv∣t+1=exp⁡ηdγt-rdv+cdv∑u∈Vgexp⁡ηdγt-rdu+cdu,where γt(-rd(v)+cd(v)) indicates the potential value the defender receives for disabling v. In addition, ηd is the parameter of the logistic function which is predetermined. This parameter governs how strictly the choice follows assessed defense values. In particular, if ηd=0, the goal-node defense strategy chooses to disable each goal node uniformly at random. On the other hand, if ηd=+∞, this strategy only disables nodes with highest γt(-rd(v)+cd(v)). The number of nodes chosen will be a certain fraction of the number of goal nodes. Then we draw that many nodes from the distribution.


### 4.2. Level-0 Attack Strategies

#### 4.2.1. Attack Candidate Set

At time stept+1, based on the graph state St, the attacker needs to consider only ∨-exploits in E∨ and ∧-nodes in V∧ that can change the graph state at t+1. We call this set of ∨-exploits and ∧-nodes theattack candidate set at time t+1, denoted by Ψa(St) and defined as follows.(3)ΨaSt=u,v∈E∨∣u∈St,v∉St∪v∈V∧\St∣π-v⊆StEssentially, Ψa(St) consists of (i) ∨-exploits from active preconditions to inactive ∨-postconditions and (ii) inactive ∧-nodes for which all preconditions are active. Each ∧-node or ∨-exploit in Ψa(St) is considered as a candidate attack at t+1. An attack action at t+1 can be any subset of this candidate set. For example, in Figure 2, the current graph state is St={1,2,5}. The attack candidate set thus consists of (i) all green edges and (ii) all green nodes. In particular, the attacker can perform exploit (1,9) to activate the currently inactive node 9. The attacker can also attempt to activate the root nodes 0 and 3.To find an optimal attack action to take att+1, we need to determine the attack value of each possible attack action at time step t+1, which represents the attack action’s impact on activating the goal nodes by the final time step T. However, exactly computing the attack value of each attack action requires taking into account all possible future outcomes regarding this attack action, which is computationally expensive. In the following, we propose a series of heuristic attack strategies, of increasing complexity.


#### 4.2.2. Level-0 Uniform Attack Strategy

Under this strategy, the attacker chooses a fixed fraction of the candidate setΨa(St), uniformly at random.


#### 4.2.3. Level-0 Value-Propagation Attack Strategy

Attack Value Propagation. The value-propagation strategy chooses attack actions based on a quantitative assessment of each attack in the candidate set Ψa(St). The main idea of this strategy is to approximate the attack value of each individual inactive node locally based on attack values of its inactive postconditions. Attack values of the inactive goal nodes, in particular, correspond to the attacker’s rewards at these nodes. So essentially, the attacker rewards ra(w)>0 at inactive goal nodes w∈Vg\St are propagated backward to other nodes. The cost of attacking and the activation probabilities are incorporated accordingly. In the propagation process, there are multiple paths from goal nodes to each node. The attack value of a node is computed as the maximum value among propagation paths reaching that node. This propagation process is illustrated in Algorithm 2, which approximates attack values of every inactive node in polynomial time.Algorithm 2:Compute Attack Value.
1  Input: t+1, St, and inverse topological order of G,  itopo(G); 2  Initialize node values rw(v,t′)←0 and rw(w,t+1)←ra(w) for inactive goal nodes w ∈ V g \ S t, all inactive nodes v∈V\({w}∪St), and time step t′≥t+1; 3  for  u∈itopo(G)\St  do 4  for v ∈ π + ( u ) \ S t  do 5  for  w∈Vg\(St∪{u}),t′←t+1,…,T-1  do 6  if  v∈V∧  then 7  r w ( v → u , t ′ + 1 ) ← c a ( v ) + p ( v ) r w ( v , t ′ ) π - ( v ) \ S t α; 8  else 9  r w ( v → u , t ′ + 1 ) ← c a ( u , v ) + p ( u , v ) r w ( v , t ′ ); 10  if  rw(u,t′+1)<γrw(v→u,t′+1)  then 11 Update rw(u,t′+1)←γrw(v→u,t′+1); 12  Return r^(u)←maxw∈Vg\Stmaxt′∈t+1,…,Trw(u,t′), ∀u∈V\St;Algorithm2 leverages the directed acyclic topological structure of the Bayesian attack graph to perform the goal-value propagation faster. We sort nodes according to the graph’s topological order and start the propagation from leaf nodes following the inverse direction of the topological order. By doing so, we ensure that when a node is examined in the propagation process, all postconditions of that node have already been examined. As a result, we need to examine each node only once during the whole propagation process.In Algorithm2, line 1 specifies the input of the algorithm which includes the current time step t+1, the graph state in previous time step St, and the inverse topological order of the graph G, itopo(G). Line 2 initializes attack values rw(v,t′) of inactive nodes v with respect to each inactive goal node w and time step t′. Intuitively, rw(v,t′) indicates the attack value of node v with respect to propagation paths of length t′-t-1 from the inactive goal node w∈Vg\St to v. Given the time horizon T={0,…,T}, we consider only paths of length up to T-t-1. At each iteration of evaluating a particular inactive node u, Algorithm 2 examines all inactive postconditions v of u and estimates the attack value propagated from v to u, rw(v→u,t′+1). If node v is of ∧-type, the propagated attack value with respect to v, ca(v)+p(v)rw(v,t′), is equally distributed to all of its inactive preconditions including u (line 7). The propagation parameter α regulates the amount of distributed value. When α=1.0, in particular, that value is equally divided among these inactive preconditions. If node v is of ∨-type, u receives the propagated attack value of ca(u,v)+p(u,v)rw(v,t′) from v (line 9). Since there are multiple propagation paths reaching node u, Algorithm 2 keeps the maximum propagated value (line 11). Finally, the attack value r^(u) of each inactive node u is computed as the maximum over inactive goal nodes and time steps (line 12). An example of Algorithm 2 is illustrated in Figure 4.Figure 4
Level-0 value-propagation attack strategy. In this example, the discount factor isγ=0.9. The attacker rewards at goal nodes are ra(10)=10,ra(11)=7,ra(12)=15. If the attacker performs exploits (8,10) and (9,10) to activate the ∧-node 10, he has to pay a cost of ca(10)=-3 and the corresponding activation probability is p(10)=0.85. In addition, if the attacker performs the exploit (9,11) to activate the goal node 11, his cost is ca(9,11)=-2 and the activation probability is p(9,11)=0.7. Algorithm 2 works as follows. Suppose that the propagation parameter α=1, then Algorithm 2 estimates the propagated attack value from postconditions 10 and 12 to precondition 8 as r10(10→8,t+2)=-3+0.85×10/2 and r12(12→8,t+2)=-4+0.90×15/4. Similarly, Algorithm 2 estimates the propagated attack value from postconditions 10, 11, and 12 to precondition 9 as r10(10→9,t+2)=-3+0.85×10/2, r11(11→9,t+2)=-2+0.7×7, and r12(12→9,t+2)=-4+0.90×15/4. The attack values of other nodes of which postconditions are the goal nodes are estimated similarly. The attack value of node 6 will be computed based on the attack value of its postconditions 7, 8, 9, and so on. This process will continue until all inactive nodes are examined.Proposition 3.
The time complexity of Algorithm2 is O((V+E)×Vg×T).Proof.
In Algorithm2, line 2 initializes attack values of inactive nodes of the attack graph with respect to each inactive goal node and time step. The time complexity of this step is O(T×V×Vg). Algorithm 2 then iteratively examines each inactive node once following the inverse direction of the topological order. The attack value of each node with respect to each inactive goal node and time step is estimated locally based on its neighboring nodes. In other words, Algorithm 2 iterates over each edge of the graph once to compute this attack value. The time complexity of this step is thus O(E×Vg×T). Finally, line 12 computes the maximum propagated attack value for each node, which takes O(T×V×Vg) time. Therefore, the total time complexity of Algorithm 2 is O((V+E)×Vg×T).Probabilistic Selection of Attack Action. Based on attack values of inactive nodes, we approximate the value of each candidate attack in Ψa(St) taking into account the cost of this attack and the corresponding activation probability, as follows: (4)re=γtcae+per^u,∀e=v,u∈ΨaStru=γtcau+pur^u,∀u∈ΨaSt,and, finally, the attack strategy selects attacks to execute probabilistically, based on the assessed attack value. It first determines the number of attacks to execute. The strategy then selects that number of attacks using a conditional logistic function. The probability each exploit e∈Ψa(St) is selected and computed as follows:(5)Pe=exp⁡ηare∑e′∈ΨaSt∩E∨exp⁡ηare′+∑u∈ΨaSt∩V∧exp⁡ηaru.The probability for a ∧-node in Ψa(St) is defined similarly. The model parameter ηa∈[0,+∞) governs how strictly the choice follows assessed attack values.


#### 4.2.4. Level-0 Sampled-Activation Attack Strategy

Like the value-propagation strategy, the sampled-activation attack strategy selects actions based on a quantitative assessment of relative value. Rather than propagating backward from goal nodes, this strategy constructs estimates by forward sampling from the current candidatesΨa(St).Random Activation Process. The sampled-activation attack strategy aims to sample paths of activation from the current graph state St to activate each inactive goal node. For example, in Figure 4, given the current graph state is St={1,2,5}, a possible path or sequence of nodes in order to activate the inactive goal node 10 is as follows: (i) activate node 0; (ii) if 0 becomes active, perform exploits (0,6) and (5,6) to activate node 6; (iii) if 6 becomes active, perform exploits (6,8) and (6,9) to activate nodes 8 and 9; and (iv) if nodes 8 and 9 become active, perform exploits (8,10) and (9,10) to activate goal node 10. In fact, there are many possible paths which can be selected to activate each inactive goal node of the graph. Therefore, the sampled-activation attack strategy selects each path probabilistically based on the probability that each inactive goal node will become active if the attacker follows that path to activate the goal node.In particular, for each nodev, the sampled-activation attack strategy keeps track of a set of preconditions pre(v) which are selected in the sampled-activation process to activate v. If v is a ∧-node, the set pre(v) consists of all preconditions of v. If v is a ∨-node, we randomly select a precondition pre(v) to use to activate v. We select only one precondition to activate each inactive ∨-node to simplify the computation of the probability that a node becomes active in the random activation. This randomized selection is explained below. Each inactive node v is assigned an activation probability pact(v) and an activation time step tact(v) according to the random action the attacker takes. The activation probability pact(v) and the activation time step tact(v) represent the probability, and the time step node v becomes active if the attacker follows the sampled action sequence to activate v. These values are computed under the assumptions that the defender takes no action and the attacker attempts to activate each node on activation paths once.The random activation process is illustrated in Algorithm3. In this process, we use the topological order of the attack graph to perform random activation. Following this order ensures that all preconditions are visited before any corresponding postconditions and thus we only need to examine each node once. When visiting an inactive ∨-node v∈V∨\St, the attacker randomly chooses a precondition u∈π-(v) (from which to activate that ∨-node) with a probability pra(u,v). This probability is computed based on activation probability p(u,v) and activation probability pact(u) of the associated precondition u (line 6). Intuitively, pact(u)p(u,v) is the probability that v becomes active if the attacker chooses the exploit (u,v) to activate v in the random activation. Accordingly, the higher the pact(u)p(u,v), the higher the chance that u is the selected precondition for v. We update v with respect to the selected u (lines 7–9).Algorithm 3:Random Activation.
1 Input: t+1, St, and topological order of G, topo(G); 2 Initialize pact(v)←1.0, tact(v)←t, and pre(v)←∅, for all active nodes v∈St; 3 Initialize pact(v)←p(v), tact←t+1, and pre(v)←∅ for all inactive root nodes v∈Vr\St; 4  for  v∈topo(G)\St  do 5  if  v∈V∨  then 6 Randomly choose a precondition u to activate v with probability p r a ( u , v ) ∝ p a c t ( u ) p ( u , v ) , ∀ u ∈ π - ( v ); 7 Update pact(v)←pact(u)p(u,v); 8 Update tact(v)←tact(u)+1; 9 Update pre(v)←{u}; 10  else 11 Update pact(v) with respect to all preconditions π-(v); 12 Update tact(v)←maxu∈π-(v)tact(u)+1; 13 Update pre(v)←π-(v); 14 Return {(pact(v),tact(v),pre(v))};When visiting an inactive∧-node v, all preconditions of v are required to activate v (line 13). Thus, the activation time step of v must be computed based on the maximum activation time step of v’s preconditions (line 12). Furthermore, v can become active only when all of its preconditions are active. Thus, the activation probability pact(v) of the inactive ∧-node v involves the activation probability pact(u) of all of its preconditions u∈π-(v). These activation probabilities {pact(u)∣u∈π-(v)} depend on the sequences of nodes (which may not be disjoint) chosen in the random activation process to activate all the preconditions u of v. Therefore, we need to backtrack over all nodes in the activation process of v to compute pact(v). We denote this sequence of nodes as seq(v) which can be defined as follows. (6)seqv≡v∪prev∪preprev⋯For example, in Figure 4, given the current graph state is St={1,2,5}, we suppose that the sequence of nodes chosen to activate the inactive goal node 10 is as follows: (i) activate node 0; (ii) if 0 becomes active, perform exploits (0,6) and (5,6) to activate nodes 6; (iii) if 6 becomes active, perform exploits (6,8) and (6,9) to activate nodes 8 and 9; and (iv) if nodes 8 and 9 become active, perform exploits (8,10) and (9,10) to activate goal node 10. Thus, seq(10)={10}∪{8,9}∪{6}∪{0,5}. Essentially, following the random activation process, v can be activated only when all nodes in seq(v)\{v} are active. Therefore, the activation probability, pact(v), is computed as follows, which comprises the activation probabilities of all edges and nodes involved in activating v: (7)pactv=∏u∈seq∨vppreu,u∏u∈seq∧vpu.Here seq(v)=seq∨(v)∪seq∧(v), seq∨(v) consists of ∨-nodes only, and seq∧(v) consists of ∧-nodes.Proposition 4.
The time complexity of Algorithm3 is O(V×(V+E)).Proof.
In the random activation process, for each visited nodev∈V∨, Algorithm 3 updates the activation probability pact(v) and activation time tact(v) based on the preconditions of v. The complexity of updating all nodes v∈V∨ is thus O(V∨+E∨). On the other hand, for each visited node v∈V∧, Algorithm 3 backtracks all nodes in the sequence of activating v, of which complexity is O(V+E). Updating all nodes v∈V∧ is thus O(V∧×(V+E)). Therefore, the time complexity of Algorithm 3 is O(V×(V+E)).Expected Utility of the Attacker. At the end of a random activation, we obtain a sequence of nodes chosen to activate each inactive goal node. Thus, we estimate the attack value of each subset V^g⊆Vg\St of inactive goal nodes according to the random activation based on Proposition 5.Proposition 5.
At time stept+1, given the graph state St, we suppose the attacker follows a random activation process to activate a subset of goal nodes V^g⊆Vg\St. If the defender takes no further action, the attacker obtains an expected utility which is computed as follows: (8)rV^g=∑v∈V^gpactvravγtactv-1+∑v∈seq∧V^gpactvpvcavγtactv-1+∑v∈seq∨V^gpactvpprev,vcaprev,vγtactv-1where seq∧(V^g)=⋃v∈V^gseq∧(v) and seq∨(V^g)=⋃v∈V^gseq∨(v) consist of all ∧-nodes and ∨-nodes in the sequences chosen by the random activation process to activate inactive goal nodes in V^g.Proof.
In this equation, the first term accounts for the expected rewards of the goal nodes in the subset. In particular, for each goal nodev∈V^g, the probability that v becomes active at time step tact(v) if the attacker follows the random activation process is pact(v). Conversely, node v remains inactive. Therefore, the attacker receives an expected reward of pact(v)ra(v)γtact(v)-1 regarding each goal node v∈V^g. Furthermore, second and third terms account for the costs of activating inactive nodes in the corresponding sampled-activation sequences. The probability pact(v)/p(v) indicates the probability that all preconditions of the ∧-node v become active and thus the attacker can activate v with a cost ca(v). Similarly, pact(v)/p(pre(v),v) is the probability that the chosen precondition of the ∨-node v becomes active and thus the attacker can activate v with a cost ca(pre(v),v).Greedy Attack. For each random activation, the sampled-activation attack strategy aims to find a subset of inactive goal nodes to activate, which maximizes the attack value. However, finding an optimal subset of inactive goal nodes is computationally expensive, because there is an exponential number of subsets of inactive goal nodes to consider. Therefore, we use the greedy approach to find a reasonable subset of inactive goal nodes to attempt to activate. Given the current subset of selected inactive goal nodes V^g (which was initially empty), we iteratively find the next best inactive goal node u∈Vg\St such that the attack value r(V^g∪{u}) is maximized and add u to V^g. This greedy process continues until the attack value stops increasing: r(V^g∪{u})-r(V^g)≤0. Based on the chosen V^g, we obtain a corresponding candidate subset: (9)v∣v∈seq∧V^g,prev⊆St∪u,v∣v∈seq∨V^g,prev=u,u∈Stwhich need to be activated in current time step t+1 according to the sampled-activation process in order to activate the goal subset V^g subsequently. We assign the value of the goal subset to this candidate subset.Finally, by running random activation multiple times, we obtain a set of candidate subsets, each associated with an estimated attack value. The attacker action att+1 is randomly chosen among these subsets of candidates following a conditional logistic distribution with respect to the attack values of these subsets.Proposition 6.
Suppose that the sampled-activation attack strategy runs random activationNr times; the time complexity of this attack strategy is ONr×(V+E)×(Vg2+V).Proof.
For each random activation, it takesO(V×(V+E)) time to sample activation paths for the attacker to activate each goal node (Proposition 4). Furthermore, at each iteration of the greedy attack heuristic, given current chosen goal subset V^g, the strategy examines all inactive goal nodes to find the next best goal node u. Each such examination of an inactive goal node u requires computing the expected utility of the attacker to follow the random activation to activate goal nodes in V^g∪{u}, which takes O(V+E) time (Proposition 5). Thus, the time complexity of each iteration of the greedy attack heuristic is O((V+E)×Vg). As a result, the time complexity of the greedy attack heuristic is O(V+E)×Vg2. The sampled-activation attack strategy comprises Nr pairs of executing random activation and greedy attack heuristic. Therefore, the complexity of this attack strategy is ONr×(V+E)×(Vg2+V).While level-0 heuristic strategies of each player do not take into account their opponent’s strategies, we introduce level-1 heuristic strategies, assuming the opponents play level-0 strategies. In the scope of this work, we focus on studying level-1 heuristic defense strategies.


## 4.1. Level-0 Defense Strategies

We introduce four level-0 defense strategies. Each targets a specific group of nodes to disable at each time stept+1. These groups of nodes are chosen solely based on the topological structure of the graph.


### 4.1.1. Level-0 Uniform Defense Strategy

The defender chooses nodes in the graph to disable uniformly at random. The number of nodes chosen is a certain fraction of the total number of nodes in the graph.


### 4.1.2. Level-0 Min-Cut Uniform Defense Strategy

The defender chooses nodes in the min-cut set to disable uniformly at random. The min-cut set is the minimum set of edges such that removing them disconnects the root nodes from the goal nodes. The number of chosen nodes is a certain fraction of the cardinality of the min-cut set.


### 4.1.3. Level-0 Root-Node Uniform Defense Strategy

The defender chooses root nodes to disable uniformly at random. The number of nodes chosen is a certain fraction of the total number of root nodes in the graph.


### 4.1.4. Level-0 Goal-Node Defense Strategy

The defender randomly chooses goal nodes to disable with probabilities depending on the rewards and costs associated with these goal nodes. The probability of disabling each goal nodev∈Vg is based on the conditional logistic function: (2)pv∣t+1=exp⁡ηdγt-rdv+cdv∑u∈Vgexp⁡ηdγt-rdu+cdu,where γt(-rd(v)+cd(v)) indicates the potential value the defender receives for disabling v. In addition, ηd is the parameter of the logistic function which is predetermined. This parameter governs how strictly the choice follows assessed defense values. In particular, if ηd=0, the goal-node defense strategy chooses to disable each goal node uniformly at random. On the other hand, if ηd=+∞, this strategy only disables nodes with highest γt(-rd(v)+cd(v)). The number of nodes chosen will be a certain fraction of the number of goal nodes. Then we draw that many nodes from the distribution.


## 4.1.1. Level-0 Uniform Defense Strategy

The defender chooses nodes in the graph to disable uniformly at random. The number of nodes chosen is a certain fraction of the total number of nodes in the graph.


## 4.1.2. Level-0 Min-Cut Uniform Defense Strategy

The defender chooses nodes in the min-cut set to disable uniformly at random. The min-cut set is the minimum set of edges such that removing them disconnects the root nodes from the goal nodes. The number of chosen nodes is a certain fraction of the cardinality of the min-cut set.


## 4.1.3. Level-0 Root-Node Uniform Defense Strategy

The defender chooses root nodes to disable uniformly at random. The number of nodes chosen is a certain fraction of the total number of root nodes in the graph.


## 4.1.4. Level-0 Goal-Node Defense Strategy

The defender randomly chooses goal nodes to disable with probabilities depending on the rewards and costs associated with these goal nodes. The probability of disabling each goal nodev∈Vg is based on the conditional logistic function: (2)pv∣t+1=exp⁡ηdγt-rdv+cdv∑u∈Vgexp⁡ηdγt-rdu+cdu,where γt(-rd(v)+cd(v)) indicates the potential value the defender receives for disabling v. In addition, ηd is the parameter of the logistic function which is predetermined. This parameter governs how strictly the choice follows assessed defense values. In particular, if ηd=0, the goal-node defense strategy chooses to disable each goal node uniformly at random. On the other hand, if ηd=+∞, this strategy only disables nodes with highest γt(-rd(v)+cd(v)). The number of nodes chosen will be a certain fraction of the number of goal nodes. Then we draw that many nodes from the distribution.


## 4.2. Level-0 Attack Strategies

### 4.2.1. Attack Candidate Set

At time stept+1, based on the graph state St, the attacker needs to consider only ∨-exploits in E∨ and ∧-nodes in V∧ that can change the graph state at t+1. We call this set of ∨-exploits and ∧-nodes theattack candidate set at time t+1, denoted by Ψa(St) and defined as follows.(3)ΨaSt=u,v∈E∨∣u∈St,v∉St∪v∈V∧\St∣π-v⊆StEssentially, Ψa(St) consists of (i) ∨-exploits from active preconditions to inactive ∨-postconditions and (ii) inactive ∧-nodes for which all preconditions are active. Each ∧-node or ∨-exploit in Ψa(St) is considered as a candidate attack at t+1. An attack action at t+1 can be any subset of this candidate set. For example, in Figure 2, the current graph state is St={1,2,5}. The attack candidate set thus consists of (i) all green edges and (ii) all green nodes. In particular, the attacker can perform exploit (1,9) to activate the currently inactive node 9. The attacker can also attempt to activate the root nodes 0 and 3.To find an optimal attack action to take att+1, we need to determine the attack value of each possible attack action at time step t+1, which represents the attack action’s impact on activating the goal nodes by the final time step T. However, exactly computing the attack value of each attack action requires taking into account all possible future outcomes regarding this attack action, which is computationally expensive. In the following, we propose a series of heuristic attack strategies, of increasing complexity.


### 4.2.2. Level-0 Uniform Attack Strategy

Under this strategy, the attacker chooses a fixed fraction of the candidate setΨa(St), uniformly at random.


### 4.2.3. Level-0 Value-Propagation Attack Strategy

Attack Value Propagation. The value-propagation strategy chooses attack actions based on a quantitative assessment of each attack in the candidate set Ψa(St). The main idea of this strategy is to approximate the attack value of each individual inactive node locally based on attack values of its inactive postconditions. Attack values of the inactive goal nodes, in particular, correspond to the attacker’s rewards at these nodes. So essentially, the attacker rewards ra(w)>0 at inactive goal nodes w∈Vg\St are propagated backward to other nodes. The cost of attacking and the activation probabilities are incorporated accordingly. In the propagation process, there are multiple paths from goal nodes to each node. The attack value of a node is computed as the maximum value among propagation paths reaching that node. This propagation process is illustrated in Algorithm 2, which approximates attack values of every inactive node in polynomial time.Algorithm 2:Compute Attack Value.
1  Input: t+1, St, and inverse topological order of G,  itopo(G); 2  Initialize node values rw(v,t′)←0 and rw(w,t+1)←ra(w) for inactive goal nodes w ∈ V g \ S t, all inactive nodes v∈V\({w}∪St), and time step t′≥t+1; 3  for  u∈itopo(G)\St  do 4  for v ∈ π + ( u ) \ S t  do 5  for  w∈Vg\(St∪{u}),t′←t+1,…,T-1  do 6  if  v∈V∧  then 7  r w ( v → u , t ′ + 1 ) ← c a ( v ) + p ( v ) r w ( v , t ′ ) π - ( v ) \ S t α; 8  else 9  r w ( v → u , t ′ + 1 ) ← c a ( u , v ) + p ( u , v ) r w ( v , t ′ ); 10  if  rw(u,t′+1)<γrw(v→u,t′+1)  then 11 Update rw(u,t′+1)←γrw(v→u,t′+1); 12  Return r^(u)←maxw∈Vg\Stmaxt′∈t+1,…,Trw(u,t′), ∀u∈V\St;Algorithm2 leverages the directed acyclic topological structure of the Bayesian attack graph to perform the goal-value propagation faster. We sort nodes according to the graph’s topological order and start the propagation from leaf nodes following the inverse direction of the topological order. By doing so, we ensure that when a node is examined in the propagation process, all postconditions of that node have already been examined. As a result, we need to examine each node only once during the whole propagation process.In Algorithm2, line 1 specifies the input of the algorithm which includes the current time step t+1, the graph state in previous time step St, and the inverse topological order of the graph G, itopo(G). Line 2 initializes attack values rw(v,t′) of inactive nodes v with respect to each inactive goal node w and time step t′. Intuitively, rw(v,t′) indicates the attack value of node v with respect to propagation paths of length t′-t-1 from the inactive goal node w∈Vg\St to v. Given the time horizon T={0,…,T}, we consider only paths of length up to T-t-1. At each iteration of evaluating a particular inactive node u, Algorithm 2 examines all inactive postconditions v of u and estimates the attack value propagated from v to u, rw(v→u,t′+1). If node v is of ∧-type, the propagated attack value with respect to v, ca(v)+p(v)rw(v,t′), is equally distributed to all of its inactive preconditions including u (line 7). The propagation parameter α regulates the amount of distributed value. When α=1.0, in particular, that value is equally divided among these inactive preconditions. If node v is of ∨-type, u receives the propagated attack value of ca(u,v)+p(u,v)rw(v,t′) from v (line 9). Since there are multiple propagation paths reaching node u, Algorithm 2 keeps the maximum propagated value (line 11). Finally, the attack value r^(u) of each inactive node u is computed as the maximum over inactive goal nodes and time steps (line 12). An example of Algorithm 2 is illustrated in Figure 4.Figure 4
Level-0 value-propagation attack strategy. In this example, the discount factor isγ=0.9. The attacker rewards at goal nodes are ra(10)=10,ra(11)=7,ra(12)=15. If the attacker performs exploits (8,10) and (9,10) to activate the ∧-node 10, he has to pay a cost of ca(10)=-3 and the corresponding activation probability is p(10)=0.85. In addition, if the attacker performs the exploit (9,11) to activate the goal node 11, his cost is ca(9,11)=-2 and the activation probability is p(9,11)=0.7. Algorithm 2 works as follows. Suppose that the propagation parameter α=1, then Algorithm 2 estimates the propagated attack value from postconditions 10 and 12 to precondition 8 as r10(10→8,t+2)=-3+0.85×10/2 and r12(12→8,t+2)=-4+0.90×15/4. Similarly, Algorithm 2 estimates the propagated attack value from postconditions 10, 11, and 12 to precondition 9 as r10(10→9,t+2)=-3+0.85×10/2, r11(11→9,t+2)=-2+0.7×7, and r12(12→9,t+2)=-4+0.90×15/4. The attack values of other nodes of which postconditions are the goal nodes are estimated similarly. The attack value of node 6 will be computed based on the attack value of its postconditions 7, 8, 9, and so on. This process will continue until all inactive nodes are examined.Proposition 3.
The time complexity of Algorithm2 is O((V+E)×Vg×T).Proof.
In Algorithm2, line 2 initializes attack values of inactive nodes of the attack graph with respect to each inactive goal node and time step. The time complexity of this step is O(T×V×Vg). Algorithm 2 then iteratively examines each inactive node once following the inverse direction of the topological order. The attack value of each node with respect to each inactive goal node and time step is estimated locally based on its neighboring nodes. In other words, Algorithm 2 iterates over each edge of the graph once to compute this attack value. The time complexity of this step is thus O(E×Vg×T). Finally, line 12 computes the maximum propagated attack value for each node, which takes O(T×V×Vg) time. Therefore, the total time complexity of Algorithm 2 is O((V+E)×Vg×T).Probabilistic Selection of Attack Action. Based on attack values of inactive nodes, we approximate the value of each candidate attack in Ψa(St) taking into account the cost of this attack and the corresponding activation probability, as follows: (4)re=γtcae+per^u,∀e=v,u∈ΨaStru=γtcau+pur^u,∀u∈ΨaSt,and, finally, the attack strategy selects attacks to execute probabilistically, based on the assessed attack value. It first determines the number of attacks to execute. The strategy then selects that number of attacks using a conditional logistic function. The probability each exploit e∈Ψa(St) is selected and computed as follows:(5)Pe=exp⁡ηare∑e′∈ΨaSt∩E∨exp⁡ηare′+∑u∈ΨaSt∩V∧exp⁡ηaru.The probability for a ∧-node in Ψa(St) is defined similarly. The model parameter ηa∈[0,+∞) governs how strictly the choice follows assessed attack values.


### 4.2.4. Level-0 Sampled-Activation Attack Strategy

Like the value-propagation strategy, the sampled-activation attack strategy selects actions based on a quantitative assessment of relative value. Rather than propagating backward from goal nodes, this strategy constructs estimates by forward sampling from the current candidatesΨa(St).Random Activation Process. The sampled-activation attack strategy aims to sample paths of activation from the current graph state St to activate each inactive goal node. For example, in Figure 4, given the current graph state is St={1,2,5}, a possible path or sequence of nodes in order to activate the inactive goal node 10 is as follows: (i) activate node 0; (ii) if 0 becomes active, perform exploits (0,6) and (5,6) to activate node 6; (iii) if 6 becomes active, perform exploits (6,8) and (6,9) to activate nodes 8 and 9; and (iv) if nodes 8 and 9 become active, perform exploits (8,10) and (9,10) to activate goal node 10. In fact, there are many possible paths which can be selected to activate each inactive goal node of the graph. Therefore, the sampled-activation attack strategy selects each path probabilistically based on the probability that each inactive goal node will become active if the attacker follows that path to activate the goal node.In particular, for each nodev, the sampled-activation attack strategy keeps track of a set of preconditions pre(v) which are selected in the sampled-activation process to activate v. If v is a ∧-node, the set pre(v) consists of all preconditions of v. If v is a ∨-node, we randomly select a precondition pre(v) to use to activate v. We select only one precondition to activate each inactive ∨-node to simplify the computation of the probability that a node becomes active in the random activation. This randomized selection is explained below. Each inactive node v is assigned an activation probability pact(v) and an activation time step tact(v) according to the random action the attacker takes. The activation probability pact(v) and the activation time step tact(v) represent the probability, and the time step node v becomes active if the attacker follows the sampled action sequence to activate v. These values are computed under the assumptions that the defender takes no action and the attacker attempts to activate each node on activation paths once.The random activation process is illustrated in Algorithm3. In this process, we use the topological order of the attack graph to perform random activation. Following this order ensures that all preconditions are visited before any corresponding postconditions and thus we only need to examine each node once. When visiting an inactive ∨-node v∈V∨\St, the attacker randomly chooses a precondition u∈π-(v) (from which to activate that ∨-node) with a probability pra(u,v). This probability is computed based on activation probability p(u,v) and activation probability pact(u) of the associated precondition u (line 6). Intuitively, pact(u)p(u,v) is the probability that v becomes active if the attacker chooses the exploit (u,v) to activate v in the random activation. Accordingly, the higher the pact(u)p(u,v), the higher the chance that u is the selected precondition for v. We update v with respect to the selected u (lines 7–9).Algorithm 3:Random Activation.
1 Input: t+1, St, and topological order of G, topo(G); 2 Initialize pact(v)←1.0, tact(v)←t, and pre(v)←∅, for all active nodes v∈St; 3 Initialize pact(v)←p(v), tact←t+1, and pre(v)←∅ for all inactive root nodes v∈Vr\St; 4  for  v∈topo(G)\St  do 5  if  v∈V∨  then 6 Randomly choose a precondition u to activate v with probability p r a ( u , v ) ∝ p a c t ( u ) p ( u , v ) , ∀ u ∈ π - ( v ); 7 Update pact(v)←pact(u)p(u,v); 8 Update tact(v)←tact(u)+1; 9 Update pre(v)←{u}; 10  else 11 Update pact(v) with respect to all preconditions π-(v); 12 Update tact(v)←maxu∈π-(v)tact(u)+1; 13 Update pre(v)←π-(v); 14 Return {(pact(v),tact(v),pre(v))};When visiting an inactive∧-node v, all preconditions of v are required to activate v (line 13). Thus, the activation time step of v must be computed based on the maximum activation time step of v’s preconditions (line 12). Furthermore, v can become active only when all of its preconditions are active. Thus, the activation probability pact(v) of the inactive ∧-node v involves the activation probability pact(u) of all of its preconditions u∈π-(v). These activation probabilities {pact(u)∣u∈π-(v)} depend on the sequences of nodes (which may not be disjoint) chosen in the random activation process to activate all the preconditions u of v. Therefore, we need to backtrack over all nodes in the activation process of v to compute pact(v). We denote this sequence of nodes as seq(v) which can be defined as follows. (6)seqv≡v∪prev∪preprev⋯For example, in Figure 4, given the current graph state is St={1,2,5}, we suppose that the sequence of nodes chosen to activate the inactive goal node 10 is as follows: (i) activate node 0; (ii) if 0 becomes active, perform exploits (0,6) and (5,6) to activate nodes 6; (iii) if 6 becomes active, perform exploits (6,8) and (6,9) to activate nodes 8 and 9; and (iv) if nodes 8 and 9 become active, perform exploits (8,10) and (9,10) to activate goal node 10. Thus, seq(10)={10}∪{8,9}∪{6}∪{0,5}. Essentially, following the random activation process, v can be activated only when all nodes in seq(v)\{v} are active. Therefore, the activation probability, pact(v), is computed as follows, which comprises the activation probabilities of all edges and nodes involved in activating v: (7)pactv=∏u∈seq∨vppreu,u∏u∈seq∧vpu.Here seq(v)=seq∨(v)∪seq∧(v), seq∨(v) consists of ∨-nodes only, and seq∧(v) consists of ∧-nodes.Proposition 4.
The time complexity of Algorithm3 is O(V×(V+E)).Proof.
In the random activation process, for each visited nodev∈V∨, Algorithm 3 updates the activation probability pact(v) and activation time tact(v) based on the preconditions of v. The complexity of updating all nodes v∈V∨ is thus O(V∨+E∨). On the other hand, for each visited node v∈V∧, Algorithm 3 backtracks all nodes in the sequence of activating v, of which complexity is O(V+E). Updating all nodes v∈V∧ is thus O(V∧×(V+E)). Therefore, the time complexity of Algorithm 3 is O(V×(V+E)).Expected Utility of the Attacker. At the end of a random activation, we obtain a sequence of nodes chosen to activate each inactive goal node. Thus, we estimate the attack value of each subset V^g⊆Vg\St of inactive goal nodes according to the random activation based on Proposition 5.Proposition 5.
At time stept+1, given the graph state St, we suppose the attacker follows a random activation process to activate a subset of goal nodes V^g⊆Vg\St. If the defender takes no further action, the attacker obtains an expected utility which is computed as follows: (8)rV^g=∑v∈V^gpactvravγtactv-1+∑v∈seq∧V^gpactvpvcavγtactv-1+∑v∈seq∨V^gpactvpprev,vcaprev,vγtactv-1where seq∧(V^g)=⋃v∈V^gseq∧(v) and seq∨(V^g)=⋃v∈V^gseq∨(v) consist of all ∧-nodes and ∨-nodes in the sequences chosen by the random activation process to activate inactive goal nodes in V^g.Proof.
In this equation, the first term accounts for the expected rewards of the goal nodes in the subset. In particular, for each goal nodev∈V^g, the probability that v becomes active at time step tact(v) if the attacker follows the random activation process is pact(v). Conversely, node v remains inactive. Therefore, the attacker receives an expected reward of pact(v)ra(v)γtact(v)-1 regarding each goal node v∈V^g. Furthermore, second and third terms account for the costs of activating inactive nodes in the corresponding sampled-activation sequences. The probability pact(v)/p(v) indicates the probability that all preconditions of the ∧-node v become active and thus the attacker can activate v with a cost ca(v). Similarly, pact(v)/p(pre(v),v) is the probability that the chosen precondition of the ∨-node v becomes active and thus the attacker can activate v with a cost ca(pre(v),v).Greedy Attack. For each random activation, the sampled-activation attack strategy aims to find a subset of inactive goal nodes to activate, which maximizes the attack value. However, finding an optimal subset of inactive goal nodes is computationally expensive, because there is an exponential number of subsets of inactive goal nodes to consider. Therefore, we use the greedy approach to find a reasonable subset of inactive goal nodes to attempt to activate. Given the current subset of selected inactive goal nodes V^g (which was initially empty), we iteratively find the next best inactive goal node u∈Vg\St such that the attack value r(V^g∪{u}) is maximized and add u to V^g. This greedy process continues until the attack value stops increasing: r(V^g∪{u})-r(V^g)≤0. Based on the chosen V^g, we obtain a corresponding candidate subset: (9)v∣v∈seq∧V^g,prev⊆St∪u,v∣v∈seq∨V^g,prev=u,u∈Stwhich need to be activated in current time step t+1 according to the sampled-activation process in order to activate the goal subset V^g subsequently. We assign the value of the goal subset to this candidate subset.Finally, by running random activation multiple times, we obtain a set of candidate subsets, each associated with an estimated attack value. The attacker action att+1 is randomly chosen among these subsets of candidates following a conditional logistic distribution with respect to the attack values of these subsets.Proposition 6.
Suppose that the sampled-activation attack strategy runs random activationNr times; the time complexity of this attack strategy is ONr×(V+E)×(Vg2+V).Proof.
For each random activation, it takesO(V×(V+E)) time to sample activation paths for the attacker to activate each goal node (Proposition 4). Furthermore, at each iteration of the greedy attack heuristic, given current chosen goal subset V^g, the strategy examines all inactive goal nodes to find the next best goal node u. Each such examination of an inactive goal node u requires computing the expected utility of the attacker to follow the random activation to activate goal nodes in V^g∪{u}, which takes O(V+E) time (Proposition 5). Thus, the time complexity of each iteration of the greedy attack heuristic is O((V+E)×Vg). As a result, the time complexity of the greedy attack heuristic is O(V+E)×Vg2. The sampled-activation attack strategy comprises Nr pairs of executing random activation and greedy attack heuristic. Therefore, the complexity of this attack strategy is ONr×(V+E)×(Vg2+V).While level-0 heuristic strategies of each player do not take into account their opponent’s strategies, we introduce level-1 heuristic strategies, assuming the opponents play level-0 strategies. In the scope of this work, we focus on studying level-1 heuristic defense strategies.


## 4.2.1. Attack Candidate Set

At time stept+1, based on the graph state St, the attacker needs to consider only ∨-exploits in E∨ and ∧-nodes in V∧ that can change the graph state at t+1. We call this set of ∨-exploits and ∧-nodes theattack candidate set at time t+1, denoted by Ψa(St) and defined as follows.(3)ΨaSt=u,v∈E∨∣u∈St,v∉St∪v∈V∧\St∣π-v⊆StEssentially, Ψa(St) consists of (i) ∨-exploits from active preconditions to inactive ∨-postconditions and (ii) inactive ∧-nodes for which all preconditions are active. Each ∧-node or ∨-exploit in Ψa(St) is considered as a candidate attack at t+1. An attack action at t+1 can be any subset of this candidate set. For example, in Figure 2, the current graph state is St={1,2,5}. The attack candidate set thus consists of (i) all green edges and (ii) all green nodes. In particular, the attacker can perform exploit (1,9) to activate the currently inactive node 9. The attacker can also attempt to activate the root nodes 0 and 3.To find an optimal attack action to take att+1, we need to determine the attack value of each possible attack action at time step t+1, which represents the attack action’s impact on activating the goal nodes by the final time step T. However, exactly computing the attack value of each attack action requires taking into account all possible future outcomes regarding this attack action, which is computationally expensive. In the following, we propose a series of heuristic attack strategies, of increasing complexity.


## 4.2.2. Level-0 Uniform Attack Strategy

Under this strategy, the attacker chooses a fixed fraction of the candidate setΨa(St), uniformly at random.


## 4.2.3. Level-0 Value-Propagation Attack Strategy

Attack Value Propagation. The value-propagation strategy chooses attack actions based on a quantitative assessment of each attack in the candidate set Ψa(St). The main idea of this strategy is to approximate the attack value of each individual inactive node locally based on attack values of its inactive postconditions. Attack values of the inactive goal nodes, in particular, correspond to the attacker’s rewards at these nodes. So essentially, the attacker rewards ra(w)>0 at inactive goal nodes w∈Vg\St are propagated backward to other nodes. The cost of attacking and the activation probabilities are incorporated accordingly. In the propagation process, there are multiple paths from goal nodes to each node. The attack value of a node is computed as the maximum value among propagation paths reaching that node. This propagation process is illustrated in Algorithm 2, which approximates attack values of every inactive node in polynomial time.Algorithm 2:Compute Attack Value.
1  Input: t+1, St, and inverse topological order of G,  itopo(G); 2  Initialize node values rw(v,t′)←0 and rw(w,t+1)←ra(w) for inactive goal nodes w ∈ V g \ S t, all inactive nodes v∈V\({w}∪St), and time step t′≥t+1; 3  for  u∈itopo(G)\St  do 4  for v ∈ π + ( u ) \ S t  do 5  for  w∈Vg\(St∪{u}),t′←t+1,…,T-1  do 6  if  v∈V∧  then 7  r w ( v → u , t ′ + 1 ) ← c a ( v ) + p ( v ) r w ( v , t ′ ) π - ( v ) \ S t α; 8  else 9  r w ( v → u , t ′ + 1 ) ← c a ( u , v ) + p ( u , v ) r w ( v , t ′ ); 10  if  rw(u,t′+1)<γrw(v→u,t′+1)  then 11 Update rw(u,t′+1)←γrw(v→u,t′+1); 12  Return r^(u)←maxw∈Vg\Stmaxt′∈t+1,…,Trw(u,t′), ∀u∈V\St;Algorithm2 leverages the directed acyclic topological structure of the Bayesian attack graph to perform the goal-value propagation faster. We sort nodes according to the graph’s topological order and start the propagation from leaf nodes following the inverse direction of the topological order. By doing so, we ensure that when a node is examined in the propagation process, all postconditions of that node have already been examined. As a result, we need to examine each node only once during the whole propagation process.In Algorithm2, line 1 specifies the input of the algorithm which includes the current time step t+1, the graph state in previous time step St, and the inverse topological order of the graph G, itopo(G). Line 2 initializes attack values rw(v,t′) of inactive nodes v with respect to each inactive goal node w and time step t′. Intuitively, rw(v,t′) indicates the attack value of node v with respect to propagation paths of length t′-t-1 from the inactive goal node w∈Vg\St to v. Given the time horizon T={0,…,T}, we consider only paths of length up to T-t-1. At each iteration of evaluating a particular inactive node u, Algorithm 2 examines all inactive postconditions v of u and estimates the attack value propagated from v to u, rw(v→u,t′+1). If node v is of ∧-type, the propagated attack value with respect to v, ca(v)+p(v)rw(v,t′), is equally distributed to all of its inactive preconditions including u (line 7). The propagation parameter α regulates the amount of distributed value. When α=1.0, in particular, that value is equally divided among these inactive preconditions. If node v is of ∨-type, u receives the propagated attack value of ca(u,v)+p(u,v)rw(v,t′) from v (line 9). Since there are multiple propagation paths reaching node u, Algorithm 2 keeps the maximum propagated value (line 11). Finally, the attack value r^(u) of each inactive node u is computed as the maximum over inactive goal nodes and time steps (line 12). An example of Algorithm 2 is illustrated in Figure 4.Figure 4
Level-0 value-propagation attack strategy. In this example, the discount factor isγ=0.9. The attacker rewards at goal nodes are ra(10)=10,ra(11)=7,ra(12)=15. If the attacker performs exploits (8,10) and (9,10) to activate the ∧-node 10, he has to pay a cost of ca(10)=-3 and the corresponding activation probability is p(10)=0.85. In addition, if the attacker performs the exploit (9,11) to activate the goal node 11, his cost is ca(9,11)=-2 and the activation probability is p(9,11)=0.7. Algorithm 2 works as follows. Suppose that the propagation parameter α=1, then Algorithm 2 estimates the propagated attack value from postconditions 10 and 12 to precondition 8 as r10(10→8,t+2)=-3+0.85×10/2 and r12(12→8,t+2)=-4+0.90×15/4. Similarly, Algorithm 2 estimates the propagated attack value from postconditions 10, 11, and 12 to precondition 9 as r10(10→9,t+2)=-3+0.85×10/2, r11(11→9,t+2)=-2+0.7×7, and r12(12→9,t+2)=-4+0.90×15/4. The attack values of other nodes of which postconditions are the goal nodes are estimated similarly. The attack value of node 6 will be computed based on the attack value of its postconditions 7, 8, 9, and so on. This process will continue until all inactive nodes are examined.Proposition 3.
The time complexity of Algorithm2 is O((V+E)×Vg×T).Proof.
In Algorithm2, line 2 initializes attack values of inactive nodes of the attack graph with respect to each inactive goal node and time step. The time complexity of this step is O(T×V×Vg). Algorithm 2 then iteratively examines each inactive node once following the inverse direction of the topological order. The attack value of each node with respect to each inactive goal node and time step is estimated locally based on its neighboring nodes. In other words, Algorithm 2 iterates over each edge of the graph once to compute this attack value. The time complexity of this step is thus O(E×Vg×T). Finally, line 12 computes the maximum propagated attack value for each node, which takes O(T×V×Vg) time. Therefore, the total time complexity of Algorithm 2 is O((V+E)×Vg×T).Probabilistic Selection of Attack Action. Based on attack values of inactive nodes, we approximate the value of each candidate attack in Ψa(St) taking into account the cost of this attack and the corresponding activation probability, as follows: (4)re=γtcae+per^u,∀e=v,u∈ΨaStru=γtcau+pur^u,∀u∈ΨaSt,and, finally, the attack strategy selects attacks to execute probabilistically, based on the assessed attack value. It first determines the number of attacks to execute. The strategy then selects that number of attacks using a conditional logistic function. The probability each exploit e∈Ψa(St) is selected and computed as follows:(5)Pe=exp⁡ηare∑e′∈ΨaSt∩E∨exp⁡ηare′+∑u∈ΨaSt∩V∧exp⁡ηaru.The probability for a ∧-node in Ψa(St) is defined similarly. The model parameter ηa∈[0,+∞) governs how strictly the choice follows assessed attack values.


## 4.2.4. Level-0 Sampled-Activation Attack Strategy

Like the value-propagation strategy, the sampled-activation attack strategy selects actions based on a quantitative assessment of relative value. Rather than propagating backward from goal nodes, this strategy constructs estimates by forward sampling from the current candidatesΨa(St).Random Activation Process. The sampled-activation attack strategy aims to sample paths of activation from the current graph state St to activate each inactive goal node. For example, in Figure 4, given the current graph state is St={1,2,5}, a possible path or sequence of nodes in order to activate the inactive goal node 10 is as follows: (i) activate node 0; (ii) if 0 becomes active, perform exploits (0,6) and (5,6) to activate node 6; (iii) if 6 becomes active, perform exploits (6,8) and (6,9) to activate nodes 8 and 9; and (iv) if nodes 8 and 9 become active, perform exploits (8,10) and (9,10) to activate goal node 10. In fact, there are many possible paths which can be selected to activate each inactive goal node of the graph. Therefore, the sampled-activation attack strategy selects each path probabilistically based on the probability that each inactive goal node will become active if the attacker follows that path to activate the goal node.In particular, for each nodev, the sampled-activation attack strategy keeps track of a set of preconditions pre(v) which are selected in the sampled-activation process to activate v. If v is a ∧-node, the set pre(v) consists of all preconditions of v. If v is a ∨-node, we randomly select a precondition pre(v) to use to activate v. We select only one precondition to activate each inactive ∨-node to simplify the computation of the probability that a node becomes active in the random activation. This randomized selection is explained below. Each inactive node v is assigned an activation probability pact(v) and an activation time step tact(v) according to the random action the attacker takes. The activation probability pact(v) and the activation time step tact(v) represent the probability, and the time step node v becomes active if the attacker follows the sampled action sequence to activate v. These values are computed under the assumptions that the defender takes no action and the attacker attempts to activate each node on activation paths once.The random activation process is illustrated in Algorithm3. In this process, we use the topological order of the attack graph to perform random activation. Following this order ensures that all preconditions are visited before any corresponding postconditions and thus we only need to examine each node once. When visiting an inactive ∨-node v∈V∨\St, the attacker randomly chooses a precondition u∈π-(v) (from which to activate that ∨-node) with a probability pra(u,v). This probability is computed based on activation probability p(u,v) and activation probability pact(u) of the associated precondition u (line 6). Intuitively, pact(u)p(u,v) is the probability that v becomes active if the attacker chooses the exploit (u,v) to activate v in the random activation. Accordingly, the higher the pact(u)p(u,v), the higher the chance that u is the selected precondition for v. We update v with respect to the selected u (lines 7–9).Algorithm 3:Random Activation.
1 Input: t+1, St, and topological order of G, topo(G); 2 Initialize pact(v)←1.0, tact(v)←t, and pre(v)←∅, for all active nodes v∈St; 3 Initialize pact(v)←p(v), tact←t+1, and pre(v)←∅ for all inactive root nodes v∈Vr\St; 4  for  v∈topo(G)\St  do 5  if  v∈V∨  then 6 Randomly choose a precondition u to activate v with probability p r a ( u , v ) ∝ p a c t ( u ) p ( u , v ) , ∀ u ∈ π - ( v ); 7 Update pact(v)←pact(u)p(u,v); 8 Update tact(v)←tact(u)+1; 9 Update pre(v)←{u}; 10  else 11 Update pact(v) with respect to all preconditions π-(v); 12 Update tact(v)←maxu∈π-(v)tact(u)+1; 13 Update pre(v)←π-(v); 14 Return {(pact(v),tact(v),pre(v))};When visiting an inactive∧-node v, all preconditions of v are required to activate v (line 13). Thus, the activation time step of v must be computed based on the maximum activation time step of v’s preconditions (line 12). Furthermore, v can become active only when all of its preconditions are active. Thus, the activation probability pact(v) of the inactive ∧-node v involves the activation probability pact(u) of all of its preconditions u∈π-(v). These activation probabilities {pact(u)∣u∈π-(v)} depend on the sequences of nodes (which may not be disjoint) chosen in the random activation process to activate all the preconditions u of v. Therefore, we need to backtrack over all nodes in the activation process of v to compute pact(v). We denote this sequence of nodes as seq(v) which can be defined as follows. (6)seqv≡v∪prev∪preprev⋯For example, in Figure 4, given the current graph state is St={1,2,5}, we suppose that the sequence of nodes chosen to activate the inactive goal node 10 is as follows: (i) activate node 0; (ii) if 0 becomes active, perform exploits (0,6) and (5,6) to activate nodes 6; (iii) if 6 becomes active, perform exploits (6,8) and (6,9) to activate nodes 8 and 9; and (iv) if nodes 8 and 9 become active, perform exploits (8,10) and (9,10) to activate goal node 10. Thus, seq(10)={10}∪{8,9}∪{6}∪{0,5}. Essentially, following the random activation process, v can be activated only when all nodes in seq(v)\{v} are active. Therefore, the activation probability, pact(v), is computed as follows, which comprises the activation probabilities of all edges and nodes involved in activating v: (7)pactv=∏u∈seq∨vppreu,u∏u∈seq∧vpu.Here seq(v)=seq∨(v)∪seq∧(v), seq∨(v) consists of ∨-nodes only, and seq∧(v) consists of ∧-nodes.Proposition 4.
The time complexity of Algorithm3 is O(V×(V+E)).Proof.
In the random activation process, for each visited nodev∈V∨, Algorithm 3 updates the activation probability pact(v) and activation time tact(v) based on the preconditions of v. The complexity of updating all nodes v∈V∨ is thus O(V∨+E∨). On the other hand, for each visited node v∈V∧, Algorithm 3 backtracks all nodes in the sequence of activating v, of which complexity is O(V+E). Updating all nodes v∈V∧ is thus O(V∧×(V+E)). Therefore, the time complexity of Algorithm 3 is O(V×(V+E)).Expected Utility of the Attacker. At the end of a random activation, we obtain a sequence of nodes chosen to activate each inactive goal node. Thus, we estimate the attack value of each subset V^g⊆Vg\St of inactive goal nodes according to the random activation based on Proposition 5.Proposition 5.
At time stept+1, given the graph state St, we suppose the attacker follows a random activation process to activate a subset of goal nodes V^g⊆Vg\St. If the defender takes no further action, the attacker obtains an expected utility which is computed as follows: (8)rV^g=∑v∈V^gpactvravγtactv-1+∑v∈seq∧V^gpactvpvcavγtactv-1+∑v∈seq∨V^gpactvpprev,vcaprev,vγtactv-1where seq∧(V^g)=⋃v∈V^gseq∧(v) and seq∨(V^g)=⋃v∈V^gseq∨(v) consist of all ∧-nodes and ∨-nodes in the sequences chosen by the random activation process to activate inactive goal nodes in V^g.Proof.
In this equation, the first term accounts for the expected rewards of the goal nodes in the subset. In particular, for each goal nodev∈V^g, the probability that v becomes active at time step tact(v) if the attacker follows the random activation process is pact(v). Conversely, node v remains inactive. Therefore, the attacker receives an expected reward of pact(v)ra(v)γtact(v)-1 regarding each goal node v∈V^g. Furthermore, second and third terms account for the costs of activating inactive nodes in the corresponding sampled-activation sequences. The probability pact(v)/p(v) indicates the probability that all preconditions of the ∧-node v become active and thus the attacker can activate v with a cost ca(v). Similarly, pact(v)/p(pre(v),v) is the probability that the chosen precondition of the ∨-node v becomes active and thus the attacker can activate v with a cost ca(pre(v),v).Greedy Attack. For each random activation, the sampled-activation attack strategy aims to find a subset of inactive goal nodes to activate, which maximizes the attack value. However, finding an optimal subset of inactive goal nodes is computationally expensive, because there is an exponential number of subsets of inactive goal nodes to consider. Therefore, we use the greedy approach to find a reasonable subset of inactive goal nodes to attempt to activate. Given the current subset of selected inactive goal nodes V^g (which was initially empty), we iteratively find the next best inactive goal node u∈Vg\St such that the attack value r(V^g∪{u}) is maximized and add u to V^g. This greedy process continues until the attack value stops increasing: r(V^g∪{u})-r(V^g)≤0. Based on the chosen V^g, we obtain a corresponding candidate subset: (9)v∣v∈seq∧V^g,prev⊆St∪u,v∣v∈seq∨V^g,prev=u,u∈Stwhich need to be activated in current time step t+1 according to the sampled-activation process in order to activate the goal subset V^g subsequently. We assign the value of the goal subset to this candidate subset.Finally, by running random activation multiple times, we obtain a set of candidate subsets, each associated with an estimated attack value. The attacker action att+1 is randomly chosen among these subsets of candidates following a conditional logistic distribution with respect to the attack values of these subsets.Proposition 6.
Suppose that the sampled-activation attack strategy runs random activationNr times; the time complexity of this attack strategy is ONr×(V+E)×(Vg2+V).Proof.
For each random activation, it takesO(V×(V+E)) time to sample activation paths for the attacker to activate each goal node (Proposition 4). Furthermore, at each iteration of the greedy attack heuristic, given current chosen goal subset V^g, the strategy examines all inactive goal nodes to find the next best goal node u. Each such examination of an inactive goal node u requires computing the expected utility of the attacker to follow the random activation to activate goal nodes in V^g∪{u}, which takes O(V+E) time (Proposition 5). Thus, the time complexity of each iteration of the greedy attack heuristic is O((V+E)×Vg). As a result, the time complexity of the greedy attack heuristic is O(V+E)×Vg2. The sampled-activation attack strategy comprises Nr pairs of executing random activation and greedy attack heuristic. Therefore, the complexity of this attack strategy is ONr×(V+E)×(Vg2+V).While level-0 heuristic strategies of each player do not take into account their opponent’s strategies, we introduce level-1 heuristic strategies, assuming the opponents play level-0 strategies. In the scope of this work, we focus on studying level-1 heuristic defense strategies.


## 5. Level-1 Defense Strategies

### 5.1. Defender Strategic Reasoning

Level-1 defense strategies assume the attacker plays level-0 attack strategies. At each time step, because the defender does not know the true graph state, it is important for it to reason about possible graph states before choosing defense actions. An overview of the defender belief update is shown in Figure5.Figure 5
Overview of the defender belief update on graph states.As mentioned before, in our game, the defender knows the initial graph state, in which all nodes are inactive. As the game evolves, at the end of each time stept, the defender updates her belief on possible graph states, taking into account (i) her belief on graph states at the end of time step t-1; (ii) her action at time step t; (iii) her observations at time step t after the players’ actions at t are taken; and (iv) the assumed attacker strategy. Finally, based on the defender’s belief update on graph states at the end of time step t and the assumption of which heuristic strategy the attacker plays, the defender decides on which defense action to take at time step t+1. In the following, we first study the defender’s belief update on graph states at each time step and then propose different defense heuristic strategies.


### 5.2. Defender Belief Update

#### 5.2.1. Exact Inference

We denote bybt={bt(St)} the defender’s belief at the end of time step t, where bt(St) is the probability that the graph state at time step t is St, and ∑Stbt(St)=1.0. At time step 0, b0(∅)=1.0. Based on the defender’s belief at time step t-1, bt-1, her action at t, Dt, and her observation at t, Ot, we can update the defender’s belief bt based on Bayes’ rule as follows:(10)btSt=pSt∣bt-1,Dt,Ot∝pSt,bt-1,Dt,Ot∝pOt∣St∑St-1∈Sbt-1bt-1St-1∑At∈ASt-1pSt∣At,Dt,St-1pAt∣St-1where p(Ot∣St) is the probability that the defender receives observation Ot given the graph state is St at time step t. Because the alerts with respect to each node are independent of other nodes, we can compute this observation probability based on the observation probability of each node, as follows: (11)pOt∣St=∏v∈Vpotv∣stv.In addition, S(bt-1) is the belief state set associated with the defender’s belief bt-1 at time step t-1: S(bt-1)={St-1∣bt-1(St-1)>0}. The probability of state transition p(St∣At,Dt,St-1) is computed based on the state transition of every node: (12)pSt∣At,Dt,St-1=∏vpstv∣At,Dt,St-1,where pst(v)∣At,Dt,St-1 is the transition probability computed in Algorithm 1. The set A(St-1) consists of all possible attack actions with respect to the graph state St-1. Finally, p(At∣St-1) is the probability that the attacker takes action At at time step t given the graph state at the end of time step t-1 is St-1.


#### 5.2.2. Approximate Inference

Exactly computing the defender’s belief (10) over all possible graph states at each time step is impractical. Indeed, there are exponentially many graph states to explore, as well as an exponential number of possible attack actions. To overcome this computational challenge, we apply particle filtering [19], a Monte Carlo sampling method for performing state inference, given noisy observations at each time step. This approach allows us to limit the number of graph states and attack actions considered. The overview of the particle filtering method is shown in Figure 6.Figure 6
Overview of the defender belief update on graph states.Essentially, the method samples particles (each particle is a sample of the graph state at time stept). Given belief bt-1, which provides a probability distribution over graph state set S(bt-1), we randomly sample a graph state St-1 at t-1 based on this distribution. Given the sampled graph state St-1, we sample an attack action At, according to St-1 and the assumption of the defender about which level-0 heuristic strategy the attacker plays. We then sample a new graph state St at time step t based on (i) sampled graph state St-1; (ii) sampled attack action At; and (iii) the defender’s action Dt. Finally, we update the defender’s belief bt(St) for the sampled graph state St based on the defender’s observation Ot at time step t.Finding an optimal defense action att+1 given the defender’s updated belief bt(St) requires taking into account an assumption regarding the attacker’s strategy and all possible future outcomes of the game as a result of the defender’s action at t+1, which is computationally expensive. Therefore, we propose two different heuristic strategies for the defender. In the following section, we propose two new attack-modeling-based defense strategies that take into account the defender’s belief, called thevalue-propagation andsampled-activation defense strategies. These two defense strategies use concepts similar to the value-propagation and sampled-activation attack strategies.


### 5.3. Defense Candidate Set

At each time stept+1, the defender has belief bt on possible graph states at the end of time step t. For each state in the belief set St∈S(bt), we define the defense candidate set, Ψd(St), which consists of active goal nodes, ∧-nodes, and ∨-postconditions of exploits in the attack candidate set Ψa(St). We aim to disable not only active goal nodes but also nodes in Ψa(St), to prevent the attacker from intruding further. (13)ΨdSt=Vg∩St∪ΨaSt∩V∧∪postΨaSt,where post(Ψa(St)) consists of ∨-postconditions of exploits in Ψa(St).


### 5.4. Level-1 Value-Propagation Defense Strategy

The overview of the level-1 value-propagation defense strategy is illustrated in Figure7. For each graph state St in the belief set St∈S(bt), based on the assumption of which heuristic strategy is played by the attacker, the defense strategy first samples Na attack actions {Ak} for k∈{1,2,…,Na}. The strategy then estimates the defense value r(u∣St) of each node u in the defense set u∈Ψd(St) based on the graph state St and the set of sampled attack actions {Ak} following the value-propagation approach, which will be explained later. This process is repeated for all graph states in the belief set S(bt). Finally, the value-propagation defense strategy computes the expected defense value r¯(u) for candidate nodes u∈⋃StΨd(St) based on the defender’s belief bt and then probabilistically selects nodes to disable based on this expected defense value.Figure 7
Overview of the value-propagation defense strategy.For each possible graph stateSt∈S(bt), we first estimate the propagated defense reward r^(u∣St) of each node u∈V by propagating the defender’s rewards rd(w)<0 at inactive goal nodes w∈Vg\St to u. Intuitively, the propagated defense reward associated with each node accounts for the potential loss the defender can prevent for blocking that node. The complete procedure is presented as Algorithm 4. The idea of computing propagated defense rewards is similar to computing propagated attack values. In lines 3–12 of Algorithm 4, we compute the propagated defense reward r^(u∣St) for all nodes u∈V. In particular, rw(v→u,t′+1) is the defense reward the postcondition v propagates to the precondition u with respect to the inactive goal node w and time step t′+1.Algorithm 4:Compute Propagated Defense Reward.
1 Input: time step, t+1, graph state, St, inverse topological order of G, itopo(G); 2Initialize defense reward rw(v,t′)=+∞ and rw(w,t′)=rd(w) for all nodes v∈V\{w} and inactive goals w∈Vg\St, for all time steps t′∈{t+1,…,T}; 3  for  u∈itopo(G)  do 4  for  v∈π+(u)\St  do 5  for  w∈Vg\(St∪{u}),t′∈{t+1…T-1}  do 6  if  v∈V∧  then 7  r w ( v → u , t ′ + 1 ) ← p ( v ) r w ( v , t ′ ); 8  else 9  r w ( v → u , t ′ + 1 ) ← p ( u , v ) r w ( v , t ′ ); 10  if  rw(u,t′+1)>γrw(v→u,t′+1)  then 11 Update rw(u,t′+1)←γrw(v→u,t′+1); 12  Return r^(u∣St)=minw∈Vg\St⁡mint′∈t+1,…,T⁡rw(u,t′)≠+∞, ∀u;Based on computed propagated defense rewards, given the set of sampled attack actions{Ak}, we then can estimate the defense values, r(u∣St), for defense candidate nodes u∈Ψd(St) as follows. (14)ru∣St=cdu+-r^u∣St-rdu,ifu∈St∩Vg-∑kpst+1u=1∣Ak,StNar^u∣St,otherwiseIn particular, for active goal nodes u∈Vg∩St, r(u∣St) comprises not only the cost cd(u) but also the propagated defense reward r^(u∣St) and the defender’s reward, rd(u), at u. For other defense candidate nodes, r(u∣St) takes into account the attack strategy to compute the probability that u becomes active as a result of the attacker’s action at t+1. Essentially, the higher the probability that a candidate node u becomes active, the higher the defense value for the defender to disable that node. The defense value for each node u (which is not an active goal node) takes into account the probability that u becomes active (as a result of sampled attack actions), denoted by pst+1(u)=1∣Ak,St, which is equal to (15)pst+1u=1∣Ak,St=Iu∈postAk1-∏e∈Ak∣poste=u1-pe,ifu∈postΨaStIu∈Akpu,ifu∈ΨaSt∩V∧,where IΦ is a binary indicator for condition Φ. Finally, the probability that the defender will choose each node u to disable is computed according to the conditional logistic function of the expected defense values. The number of chosen nodes to disable is a certain fraction of the cardinality of ⋃StΨd(St).


### 5.5. Level-1 Sampled-Activation Defense Strategy

In this defense strategy, we leverage the random activation process as described in Section4.2.4 to reason about potential attack paths the attacker may follow to attack goal nodes. Based on this reasoning, we can estimate the defense value for each possible defense action. The defense value of each defense action indicates the impact of the defender’s action on preventing the attacker from attacking goal nodes. We then select the action which leads to the highest defense value. An overview of the sampled-activation defense strategy is illustrated in Figure 8. The details of the strategy are explained in the following Sections 5.5.1, 5.5.2, and 5.5.3.Figure 8
Overview of the sampled-activation defense strategy.


#### 5.5.1. Sample Attack Plans

We first sample attack plans of the attacker at time stept+1. Each plan refers to a pair of an attack action at t+1 and a corresponding attack path the attacker may take to reach inactive goal nodes in future. At time step t+1, for each possible graph state St∈S(bt), we sample Nr random activation, each resulting in sampled-activation sequences toward inactive goal nodes. We also sample a set of Na attack actions, {Ak}, where k=1,2,…,Na, according to the defender’s assumption about the attacker’s strategy. For each Ak, we select the best random activation among the Nr sampled-activation samples such that performing Ak at t+1 can lead to the activation of the subset of inactive goal nodes with the highest attack value according to that random activation (Section 4.2.4). We denote by ra(Ak) the sequence of nodes (sorted according to the topological order of the graph) which can be activated in future time steps based on Ak and the corresponding selected random activation. We call each pair (Ak,ra(Ak)) an attack plan for the attacker.


#### 5.5.2. Estimate Defense Values

For each possible graph stateSt∈S(bt), based on sampled attack plans (Ak,ra(Ak)),∀k=1,2,…,Na, we can estimate the defense value of any defense action Dt+1⊆Ψd(St) with respect to St as follows: (16)rDt+1∣St=∑krDt+1∣St,Ak,raAkNa,where r(Dt+1∣St,Ak,ra(Ak)) is the defender’s value for playing action Dt+1 against (Ak,ra(Ak)) which is determined based on which goal nodes can potentially become active given players’ actions Dt+1 and (Ak,ra(Ak)). To determine these goal nodes, we iteratively examine nodes in ra(Ak) to find which goal nodes v∈Vg∩ra(Ak) of which sequence seq(v) are not blocked by the defender’s action Dt+1. Recall that seq(v) is a sequence of nodes to activate in the chosen random activation to activate v.This search process is shown in Algorithm5, where isBlocked(u) indicates if the attack sequence to node u according to (Ak,ra(Ak)) is blocked by the defender (isBlocked(u)=1) or not (isBlocked(u)=0). Initially, isBlocked(v)=0 for all nodes v in ra(Ak)\Dt+1 while isBlocked(v)=1 for all v∈Dt+1. While examining non-root nodes in ra(Ak), an ∨-node u is updated to isBlocked(u)=1 if all preconditions of u in pre(u) are blocked. On the other hand, an ∧-node u becomes blocked when any of its preconditions is blocked. Given {isBlocked(v)}, we can estimate the defense value r(Dt+1∣St,Ak,ra(Ak)) at time step t+1 as follows:(17)rDt+1∣St,Ak,raAk=∑v∈Dt+1cdvγt+∑v∈Vg∩raAk∪Stpactvrdvγtactv-11-isBlockedvwhere the first term is the cost of performing Dt+1. The second term accounts for the potential loss of the defender which comprises the blocked status, the activation probability, the activation time step, and the rewards of all the goal nodes which either are active or will be activated based on the attack plan (Ak,ra(Ak)). Finally, based on the defense value r(Dt+1∣St) with respect to the graph state St, the expected defense value of each Dt+1 over the defender’s belief is computed as follows. (18)rDt+1∣bt=∑StbtStrDt+1∣StAlgorithm 5:Find blocked nodes.
1 Input: St,Dt+1,Ak,ra(Ak); 2 Initialize block status isBlocked(v)←0 for all v∈ra(Ak)∪St\Dt+1 and isBlocked(v)←1 for all v ∈ D t + 1; 3  for  u∈ra(Ak)\Vr with isBlocked(u)=0do 4  if  u∈V∨  then 5  if  isBlockedpreu  then 6  i s B l o c k e d ( u ) ← 1; 7  else 8  if  isBlocked(v)forsomev∈pre(u)  then 9  i s B l o c k e d ( u ) ← 1; 10 Return {isBlocked(u)}.Proposition 7.
Given a graph stateSt∈S(bt), a defense action Dt+1, and a set of Na sampled attack plans {(Ak,ra(Ak))}, the time complexity of the estimation of the defense value of Dt+1 is O(V+E)×Na.Proof.
Given a graph stateSt∈S(bt), a defense action Dt+1, and a sampled attack plan (Ak,ra(Ak)), Algorithm 5 iterates over each node u in the attack sequence ra(Ak) to update the blocked status of u based on the preconditions of this node. Because of the directed acyclic topological structure of the graph, Algorithm 5 has to examine each node in the sequence and its incoming edges once. Therefore, the time complexity of Algorithm 5 is O(V+E). In addition, given the blocked status of the graph computed by Algorithm 5, we estimate the defense value r(Dt+1∣St,Ak,ra(Ak)) based on the cost of disabling nodes in Dt+1 and the potential loss regarding goal nodes of which attack paths are not blocked. The time complexity of this estimation is O(V) since Dt+1+Vg≤2×V. Since there are Na sampled attack plans, the time complexity of computing the defense value r(Dt+1∣St) is O(V+E)×Na.


#### 5.5.3. Greedy Defense Strategy

Finding an optimal defense action according to the expected defense valuer(Dt+1∣bt) is computationally expensive, because there is an exponential number of possible defense actions. Therefore, we propose two different greedy heuristics to overcome this computational challenge.Static Greedy Heuristic. This heuristic greedily finds a reasonable set of nodes to disable over the defender’s belief bt. These nodes are chosen from the defense candidate set with respect to the defender’s belief bt, which is defined as ⋃St∈S(bt)Ψd(St) where Ψd(St) is the defense candidate set with respect to the graph state St. Given the current set of selected nodes Dt+1 (which was initially empty), the heuristic finds the next best node u such that r(Dt+1∪{u}∣bt) is maximized. The iteration process stops when disabling new nodes does not increase the defender’s value: r(Dt+1∪{u}∣bt)-r(Dt+1∣bt)≤0 for all u.Proposition 8.
Suppose that the number of graph states to sample in particle filtering isNs (which means that S(bt)=Ns). The time complexity of the static greedy heuristic is O(V2×Ns×(V+E)×Na).Proof.
The size of the defense candidate set⋃St∈S(bt)Ψd(St) is at most V. Therefore, there are at most V iterations of finding next best node in the static greedy heuristic. In each iteration of the heuristic, given the current set of selected nodes Dt+1, for each candidate node u, we compute the defense value r(Dt+1∪{u}∣bt); this step takes O(Ns×(V+E)×Na) time according to Proposition 7. Since there are at most V nodes in the candidate set, the time complexity of static greedy heuristic is O(V2×Ns×(V+E)×Na).In addition, we propose a randomized greedy heuristic to select a defense action from a set of greedy defense actions probabilistically. These greedy defense actions are generated based on eachSt in S(bt).Randomized Greedy Heuristic. This heuristic greedily finds a reasonable set of nodes Dt+1(St) to disable with respect to each St in S(bt). For each St∈S(bt), given the current set of selected nodes Dt+1(St) (which was initially empty), the heuristic finds the next best node u such that r(Dt+1(St)∣St) is maximized. As a result, we obtain multiple greedy defense actions {Dt+1(St)} corresponding to possible game states St in S(bt). The defender then randomizes its choice over {Dt+1(St)} according to a conditional logistic distribution with respect to the defense value {r(Dt+1(St)∣bt)} computed based on the defender belief bt. The following proposition provides the time complexity of the randomized greedy heuristic. This proposition can be proved in a similar way to the complexity of the static greedy heuristic.Proposition 9.
The time complexity of the randomized greedy heuristic isO(V2×Ns×(V+E)×Na).


## 5.1. Defender Strategic Reasoning

Level-1 defense strategies assume the attacker plays level-0 attack strategies. At each time step, because the defender does not know the true graph state, it is important for it to reason about possible graph states before choosing defense actions. An overview of the defender belief update is shown in Figure5.Figure 5
Overview of the defender belief update on graph states.As mentioned before, in our game, the defender knows the initial graph state, in which all nodes are inactive. As the game evolves, at the end of each time stept, the defender updates her belief on possible graph states, taking into account (i) her belief on graph states at the end of time step t-1; (ii) her action at time step t; (iii) her observations at time step t after the players’ actions at t are taken; and (iv) the assumed attacker strategy. Finally, based on the defender’s belief update on graph states at the end of time step t and the assumption of which heuristic strategy the attacker plays, the defender decides on which defense action to take at time step t+1. In the following, we first study the defender’s belief update on graph states at each time step and then propose different defense heuristic strategies.


## 5.2. Defender Belief Update

### 5.2.1. Exact Inference

We denote bybt={bt(St)} the defender’s belief at the end of time step t, where bt(St) is the probability that the graph state at time step t is St, and ∑Stbt(St)=1.0. At time step 0, b0(∅)=1.0. Based on the defender’s belief at time step t-1, bt-1, her action at t, Dt, and her observation at t, Ot, we can update the defender’s belief bt based on Bayes’ rule as follows:(10)btSt=pSt∣bt-1,Dt,Ot∝pSt,bt-1,Dt,Ot∝pOt∣St∑St-1∈Sbt-1bt-1St-1∑At∈ASt-1pSt∣At,Dt,St-1pAt∣St-1where p(Ot∣St) is the probability that the defender receives observation Ot given the graph state is St at time step t. Because the alerts with respect to each node are independent of other nodes, we can compute this observation probability based on the observation probability of each node, as follows: (11)pOt∣St=∏v∈Vpotv∣stv.In addition, S(bt-1) is the belief state set associated with the defender’s belief bt-1 at time step t-1: S(bt-1)={St-1∣bt-1(St-1)>0}. The probability of state transition p(St∣At,Dt,St-1) is computed based on the state transition of every node: (12)pSt∣At,Dt,St-1=∏vpstv∣At,Dt,St-1,where pst(v)∣At,Dt,St-1 is the transition probability computed in Algorithm 1. The set A(St-1) consists of all possible attack actions with respect to the graph state St-1. Finally, p(At∣St-1) is the probability that the attacker takes action At at time step t given the graph state at the end of time step t-1 is St-1.


### 5.2.2. Approximate Inference

Exactly computing the defender’s belief (10) over all possible graph states at each time step is impractical. Indeed, there are exponentially many graph states to explore, as well as an exponential number of possible attack actions. To overcome this computational challenge, we apply particle filtering [19], a Monte Carlo sampling method for performing state inference, given noisy observations at each time step. This approach allows us to limit the number of graph states and attack actions considered. The overview of the particle filtering method is shown in Figure 6.Figure 6
Overview of the defender belief update on graph states.Essentially, the method samples particles (each particle is a sample of the graph state at time stept). Given belief bt-1, which provides a probability distribution over graph state set S(bt-1), we randomly sample a graph state St-1 at t-1 based on this distribution. Given the sampled graph state St-1, we sample an attack action At, according to St-1 and the assumption of the defender about which level-0 heuristic strategy the attacker plays. We then sample a new graph state St at time step t based on (i) sampled graph state St-1; (ii) sampled attack action At; and (iii) the defender’s action Dt. Finally, we update the defender’s belief bt(St) for the sampled graph state St based on the defender’s observation Ot at time step t.Finding an optimal defense action att+1 given the defender’s updated belief bt(St) requires taking into account an assumption regarding the attacker’s strategy and all possible future outcomes of the game as a result of the defender’s action at t+1, which is computationally expensive. Therefore, we propose two different heuristic strategies for the defender. In the following section, we propose two new attack-modeling-based defense strategies that take into account the defender’s belief, called thevalue-propagation andsampled-activation defense strategies. These two defense strategies use concepts similar to the value-propagation and sampled-activation attack strategies.


## 5.2.1. Exact Inference

We denote bybt={bt(St)} the defender’s belief at the end of time step t, where bt(St) is the probability that the graph state at time step t is St, and ∑Stbt(St)=1.0. At time step 0, b0(∅)=1.0. Based on the defender’s belief at time step t-1, bt-1, her action at t, Dt, and her observation at t, Ot, we can update the defender’s belief bt based on Bayes’ rule as follows:(10)btSt=pSt∣bt-1,Dt,Ot∝pSt,bt-1,Dt,Ot∝pOt∣St∑St-1∈Sbt-1bt-1St-1∑At∈ASt-1pSt∣At,Dt,St-1pAt∣St-1where p(Ot∣St) is the probability that the defender receives observation Ot given the graph state is St at time step t. Because the alerts with respect to each node are independent of other nodes, we can compute this observation probability based on the observation probability of each node, as follows: (11)pOt∣St=∏v∈Vpotv∣stv.In addition, S(bt-1) is the belief state set associated with the defender’s belief bt-1 at time step t-1: S(bt-1)={St-1∣bt-1(St-1)>0}. The probability of state transition p(St∣At,Dt,St-1) is computed based on the state transition of every node: (12)pSt∣At,Dt,St-1=∏vpstv∣At,Dt,St-1,where pst(v)∣At,Dt,St-1 is the transition probability computed in Algorithm 1. The set A(St-1) consists of all possible attack actions with respect to the graph state St-1. Finally, p(At∣St-1) is the probability that the attacker takes action At at time step t given the graph state at the end of time step t-1 is St-1.


## 5.2.2. Approximate Inference

Exactly computing the defender’s belief (10) over all possible graph states at each time step is impractical. Indeed, there are exponentially many graph states to explore, as well as an exponential number of possible attack actions. To overcome this computational challenge, we apply particle filtering [19], a Monte Carlo sampling method for performing state inference, given noisy observations at each time step. This approach allows us to limit the number of graph states and attack actions considered. The overview of the particle filtering method is shown in Figure 6.Figure 6
Overview of the defender belief update on graph states.Essentially, the method samples particles (each particle is a sample of the graph state at time stept). Given belief bt-1, which provides a probability distribution over graph state set S(bt-1), we randomly sample a graph state St-1 at t-1 based on this distribution. Given the sampled graph state St-1, we sample an attack action At, according to St-1 and the assumption of the defender about which level-0 heuristic strategy the attacker plays. We then sample a new graph state St at time step t based on (i) sampled graph state St-1; (ii) sampled attack action At; and (iii) the defender’s action Dt. Finally, we update the defender’s belief bt(St) for the sampled graph state St based on the defender’s observation Ot at time step t.Finding an optimal defense action att+1 given the defender’s updated belief bt(St) requires taking into account an assumption regarding the attacker’s strategy and all possible future outcomes of the game as a result of the defender’s action at t+1, which is computationally expensive. Therefore, we propose two different heuristic strategies for the defender. In the following section, we propose two new attack-modeling-based defense strategies that take into account the defender’s belief, called thevalue-propagation andsampled-activation defense strategies. These two defense strategies use concepts similar to the value-propagation and sampled-activation attack strategies.


## 5.3. Defense Candidate Set

At each time stept+1, the defender has belief bt on possible graph states at the end of time step t. For each state in the belief set St∈S(bt), we define the defense candidate set, Ψd(St), which consists of active goal nodes, ∧-nodes, and ∨-postconditions of exploits in the attack candidate set Ψa(St). We aim to disable not only active goal nodes but also nodes in Ψa(St), to prevent the attacker from intruding further. (13)ΨdSt=Vg∩St∪ΨaSt∩V∧∪postΨaSt,where post(Ψa(St)) consists of ∨-postconditions of exploits in Ψa(St).


## 5.4. Level-1 Value-Propagation Defense Strategy

The overview of the level-1 value-propagation defense strategy is illustrated in Figure7. For each graph state St in the belief set St∈S(bt), based on the assumption of which heuristic strategy is played by the attacker, the defense strategy first samples Na attack actions {Ak} for k∈{1,2,…,Na}. The strategy then estimates the defense value r(u∣St) of each node u in the defense set u∈Ψd(St) based on the graph state St and the set of sampled attack actions {Ak} following the value-propagation approach, which will be explained later. This process is repeated for all graph states in the belief set S(bt). Finally, the value-propagation defense strategy computes the expected defense value r¯(u) for candidate nodes u∈⋃StΨd(St) based on the defender’s belief bt and then probabilistically selects nodes to disable based on this expected defense value.Figure 7
Overview of the value-propagation defense strategy.For each possible graph stateSt∈S(bt), we first estimate the propagated defense reward r^(u∣St) of each node u∈V by propagating the defender’s rewards rd(w)<0 at inactive goal nodes w∈Vg\St to u. Intuitively, the propagated defense reward associated with each node accounts for the potential loss the defender can prevent for blocking that node. The complete procedure is presented as Algorithm 4. The idea of computing propagated defense rewards is similar to computing propagated attack values. In lines 3–12 of Algorithm 4, we compute the propagated defense reward r^(u∣St) for all nodes u∈V. In particular, rw(v→u,t′+1) is the defense reward the postcondition v propagates to the precondition u with respect to the inactive goal node w and time step t′+1.Algorithm 4:Compute Propagated Defense Reward.
1 Input: time step, t+1, graph state, St, inverse topological order of G, itopo(G); 2Initialize defense reward rw(v,t′)=+∞ and rw(w,t′)=rd(w) for all nodes v∈V\{w} and inactive goals w∈Vg\St, for all time steps t′∈{t+1,…,T}; 3  for  u∈itopo(G)  do 4  for  v∈π+(u)\St  do 5  for  w∈Vg\(St∪{u}),t′∈{t+1…T-1}  do 6  if  v∈V∧  then 7  r w ( v → u , t ′ + 1 ) ← p ( v ) r w ( v , t ′ ); 8  else 9  r w ( v → u , t ′ + 1 ) ← p ( u , v ) r w ( v , t ′ ); 10  if  rw(u,t′+1)>γrw(v→u,t′+1)  then 11 Update rw(u,t′+1)←γrw(v→u,t′+1); 12  Return r^(u∣St)=minw∈Vg\St⁡mint′∈t+1,…,T⁡rw(u,t′)≠+∞, ∀u;Based on computed propagated defense rewards, given the set of sampled attack actions{Ak}, we then can estimate the defense values, r(u∣St), for defense candidate nodes u∈Ψd(St) as follows. (14)ru∣St=cdu+-r^u∣St-rdu,ifu∈St∩Vg-∑kpst+1u=1∣Ak,StNar^u∣St,otherwiseIn particular, for active goal nodes u∈Vg∩St, r(u∣St) comprises not only the cost cd(u) but also the propagated defense reward r^(u∣St) and the defender’s reward, rd(u), at u. For other defense candidate nodes, r(u∣St) takes into account the attack strategy to compute the probability that u becomes active as a result of the attacker’s action at t+1. Essentially, the higher the probability that a candidate node u becomes active, the higher the defense value for the defender to disable that node. The defense value for each node u (which is not an active goal node) takes into account the probability that u becomes active (as a result of sampled attack actions), denoted by pst+1(u)=1∣Ak,St, which is equal to (15)pst+1u=1∣Ak,St=Iu∈postAk1-∏e∈Ak∣poste=u1-pe,ifu∈postΨaStIu∈Akpu,ifu∈ΨaSt∩V∧,where IΦ is a binary indicator for condition Φ. Finally, the probability that the defender will choose each node u to disable is computed according to the conditional logistic function of the expected defense values. The number of chosen nodes to disable is a certain fraction of the cardinality of ⋃StΨd(St).


## 5.5. Level-1 Sampled-Activation Defense Strategy

In this defense strategy, we leverage the random activation process as described in Section4.2.4 to reason about potential attack paths the attacker may follow to attack goal nodes. Based on this reasoning, we can estimate the defense value for each possible defense action. The defense value of each defense action indicates the impact of the defender’s action on preventing the attacker from attacking goal nodes. We then select the action which leads to the highest defense value. An overview of the sampled-activation defense strategy is illustrated in Figure 8. The details of the strategy are explained in the following Sections 5.5.1, 5.5.2, and 5.5.3.Figure 8
Overview of the sampled-activation defense strategy.


### 5.5.1. Sample Attack Plans

We first sample attack plans of the attacker at time stept+1. Each plan refers to a pair of an attack action at t+1 and a corresponding attack path the attacker may take to reach inactive goal nodes in future. At time step t+1, for each possible graph state St∈S(bt), we sample Nr random activation, each resulting in sampled-activation sequences toward inactive goal nodes. We also sample a set of Na attack actions, {Ak}, where k=1,2,…,Na, according to the defender’s assumption about the attacker’s strategy. For each Ak, we select the best random activation among the Nr sampled-activation samples such that performing Ak at t+1 can lead to the activation of the subset of inactive goal nodes with the highest attack value according to that random activation (Section 4.2.4). We denote by ra(Ak) the sequence of nodes (sorted according to the topological order of the graph) which can be activated in future time steps based on Ak and the corresponding selected random activation. We call each pair (Ak,ra(Ak)) an attack plan for the attacker.


### 5.5.2. Estimate Defense Values

For each possible graph stateSt∈S(bt), based on sampled attack plans (Ak,ra(Ak)),∀k=1,2,…,Na, we can estimate the defense value of any defense action Dt+1⊆Ψd(St) with respect to St as follows: (16)rDt+1∣St=∑krDt+1∣St,Ak,raAkNa,where r(Dt+1∣St,Ak,ra(Ak)) is the defender’s value for playing action Dt+1 against (Ak,ra(Ak)) which is determined based on which goal nodes can potentially become active given players’ actions Dt+1 and (Ak,ra(Ak)). To determine these goal nodes, we iteratively examine nodes in ra(Ak) to find which goal nodes v∈Vg∩ra(Ak) of which sequence seq(v) are not blocked by the defender’s action Dt+1. Recall that seq(v) is a sequence of nodes to activate in the chosen random activation to activate v.This search process is shown in Algorithm5, where isBlocked(u) indicates if the attack sequence to node u according to (Ak,ra(Ak)) is blocked by the defender (isBlocked(u)=1) or not (isBlocked(u)=0). Initially, isBlocked(v)=0 for all nodes v in ra(Ak)\Dt+1 while isBlocked(v)=1 for all v∈Dt+1. While examining non-root nodes in ra(Ak), an ∨-node u is updated to isBlocked(u)=1 if all preconditions of u in pre(u) are blocked. On the other hand, an ∧-node u becomes blocked when any of its preconditions is blocked. Given {isBlocked(v)}, we can estimate the defense value r(Dt+1∣St,Ak,ra(Ak)) at time step t+1 as follows:(17)rDt+1∣St,Ak,raAk=∑v∈Dt+1cdvγt+∑v∈Vg∩raAk∪Stpactvrdvγtactv-11-isBlockedvwhere the first term is the cost of performing Dt+1. The second term accounts for the potential loss of the defender which comprises the blocked status, the activation probability, the activation time step, and the rewards of all the goal nodes which either are active or will be activated based on the attack plan (Ak,ra(Ak)). Finally, based on the defense value r(Dt+1∣St) with respect to the graph state St, the expected defense value of each Dt+1 over the defender’s belief is computed as follows. (18)rDt+1∣bt=∑StbtStrDt+1∣StAlgorithm 5:Find blocked nodes.
1 Input: St,Dt+1,Ak,ra(Ak); 2 Initialize block status isBlocked(v)←0 for all v∈ra(Ak)∪St\Dt+1 and isBlocked(v)←1 for all v ∈ D t + 1; 3  for  u∈ra(Ak)\Vr with isBlocked(u)=0do 4  if  u∈V∨  then 5  if  isBlockedpreu  then 6  i s B l o c k e d ( u ) ← 1; 7  else 8  if  isBlocked(v)forsomev∈pre(u)  then 9  i s B l o c k e d ( u ) ← 1; 10 Return {isBlocked(u)}.Proposition 7.
Given a graph stateSt∈S(bt), a defense action Dt+1, and a set of Na sampled attack plans {(Ak,ra(Ak))}, the time complexity of the estimation of the defense value of Dt+1 is O(V+E)×Na.Proof.
Given a graph stateSt∈S(bt), a defense action Dt+1, and a sampled attack plan (Ak,ra(Ak)), Algorithm 5 iterates over each node u in the attack sequence ra(Ak) to update the blocked status of u based on the preconditions of this node. Because of the directed acyclic topological structure of the graph, Algorithm 5 has to examine each node in the sequence and its incoming edges once. Therefore, the time complexity of Algorithm 5 is O(V+E). In addition, given the blocked status of the graph computed by Algorithm 5, we estimate the defense value r(Dt+1∣St,Ak,ra(Ak)) based on the cost of disabling nodes in Dt+1 and the potential loss regarding goal nodes of which attack paths are not blocked. The time complexity of this estimation is O(V) since Dt+1+Vg≤2×V. Since there are Na sampled attack plans, the time complexity of computing the defense value r(Dt+1∣St) is O(V+E)×Na.


### 5.5.3. Greedy Defense Strategy

Finding an optimal defense action according to the expected defense valuer(Dt+1∣bt) is computationally expensive, because there is an exponential number of possible defense actions. Therefore, we propose two different greedy heuristics to overcome this computational challenge.Static Greedy Heuristic. This heuristic greedily finds a reasonable set of nodes to disable over the defender’s belief bt. These nodes are chosen from the defense candidate set with respect to the defender’s belief bt, which is defined as ⋃St∈S(bt)Ψd(St) where Ψd(St) is the defense candidate set with respect to the graph state St. Given the current set of selected nodes Dt+1 (which was initially empty), the heuristic finds the next best node u such that r(Dt+1∪{u}∣bt) is maximized. The iteration process stops when disabling new nodes does not increase the defender’s value: r(Dt+1∪{u}∣bt)-r(Dt+1∣bt)≤0 for all u.Proposition 8.
Suppose that the number of graph states to sample in particle filtering isNs (which means that S(bt)=Ns). The time complexity of the static greedy heuristic is O(V2×Ns×(V+E)×Na).Proof.
The size of the defense candidate set⋃St∈S(bt)Ψd(St) is at most V. Therefore, there are at most V iterations of finding next best node in the static greedy heuristic. In each iteration of the heuristic, given the current set of selected nodes Dt+1, for each candidate node u, we compute the defense value r(Dt+1∪{u}∣bt); this step takes O(Ns×(V+E)×Na) time according to Proposition 7. Since there are at most V nodes in the candidate set, the time complexity of static greedy heuristic is O(V2×Ns×(V+E)×Na).In addition, we propose a randomized greedy heuristic to select a defense action from a set of greedy defense actions probabilistically. These greedy defense actions are generated based on eachSt in S(bt).Randomized Greedy Heuristic. This heuristic greedily finds a reasonable set of nodes Dt+1(St) to disable with respect to each St in S(bt). For each St∈S(bt), given the current set of selected nodes Dt+1(St) (which was initially empty), the heuristic finds the next best node u such that r(Dt+1(St)∣St) is maximized. As a result, we obtain multiple greedy defense actions {Dt+1(St)} corresponding to possible game states St in S(bt). The defender then randomizes its choice over {Dt+1(St)} according to a conditional logistic distribution with respect to the defense value {r(Dt+1(St)∣bt)} computed based on the defender belief bt. The following proposition provides the time complexity of the randomized greedy heuristic. This proposition can be proved in a similar way to the complexity of the static greedy heuristic.Proposition 9.
The time complexity of the randomized greedy heuristic isO(V2×Ns×(V+E)×Na).


## 5.5.1. Sample Attack Plans

We first sample attack plans of the attacker at time stept+1. Each plan refers to a pair of an attack action at t+1 and a corresponding attack path the attacker may take to reach inactive goal nodes in future. At time step t+1, for each possible graph state St∈S(bt), we sample Nr random activation, each resulting in sampled-activation sequences toward inactive goal nodes. We also sample a set of Na attack actions, {Ak}, where k=1,2,…,Na, according to the defender’s assumption about the attacker’s strategy. For each Ak, we select the best random activation among the Nr sampled-activation samples such that performing Ak at t+1 can lead to the activation of the subset of inactive goal nodes with the highest attack value according to that random activation (Section 4.2.4). We denote by ra(Ak) the sequence of nodes (sorted according to the topological order of the graph) which can be activated in future time steps based on Ak and the corresponding selected random activation. We call each pair (Ak,ra(Ak)) an attack plan for the attacker.


## 5.5.2. Estimate Defense Values

For each possible graph stateSt∈S(bt), based on sampled attack plans (Ak,ra(Ak)),∀k=1,2,…,Na, we can estimate the defense value of any defense action Dt+1⊆Ψd(St) with respect to St as follows: (16)rDt+1∣St=∑krDt+1∣St,Ak,raAkNa,where r(Dt+1∣St,Ak,ra(Ak)) is the defender’s value for playing action Dt+1 against (Ak,ra(Ak)) which is determined based on which goal nodes can potentially become active given players’ actions Dt+1 and (Ak,ra(Ak)). To determine these goal nodes, we iteratively examine nodes in ra(Ak) to find which goal nodes v∈Vg∩ra(Ak) of which sequence seq(v) are not blocked by the defender’s action Dt+1. Recall that seq(v) is a sequence of nodes to activate in the chosen random activation to activate v.This search process is shown in Algorithm5, where isBlocked(u) indicates if the attack sequence to node u according to (Ak,ra(Ak)) is blocked by the defender (isBlocked(u)=1) or not (isBlocked(u)=0). Initially, isBlocked(v)=0 for all nodes v in ra(Ak)\Dt+1 while isBlocked(v)=1 for all v∈Dt+1. While examining non-root nodes in ra(Ak), an ∨-node u is updated to isBlocked(u)=1 if all preconditions of u in pre(u) are blocked. On the other hand, an ∧-node u becomes blocked when any of its preconditions is blocked. Given {isBlocked(v)}, we can estimate the defense value r(Dt+1∣St,Ak,ra(Ak)) at time step t+1 as follows:(17)rDt+1∣St,Ak,raAk=∑v∈Dt+1cdvγt+∑v∈Vg∩raAk∪Stpactvrdvγtactv-11-isBlockedvwhere the first term is the cost of performing Dt+1. The second term accounts for the potential loss of the defender which comprises the blocked status, the activation probability, the activation time step, and the rewards of all the goal nodes which either are active or will be activated based on the attack plan (Ak,ra(Ak)). Finally, based on the defense value r(Dt+1∣St) with respect to the graph state St, the expected defense value of each Dt+1 over the defender’s belief is computed as follows. (18)rDt+1∣bt=∑StbtStrDt+1∣StAlgorithm 5:Find blocked nodes.
1 Input: St,Dt+1,Ak,ra(Ak); 2 Initialize block status isBlocked(v)←0 for all v∈ra(Ak)∪St\Dt+1 and isBlocked(v)←1 for all v ∈ D t + 1; 3  for  u∈ra(Ak)\Vr with isBlocked(u)=0do 4  if  u∈V∨  then 5  if  isBlockedpreu  then 6  i s B l o c k e d ( u ) ← 1; 7  else 8  if  isBlocked(v)forsomev∈pre(u)  then 9  i s B l o c k e d ( u ) ← 1; 10 Return {isBlocked(u)}.Proposition 7.
Given a graph stateSt∈S(bt), a defense action Dt+1, and a set of Na sampled attack plans {(Ak,ra(Ak))}, the time complexity of the estimation of the defense value of Dt+1 is O(V+E)×Na.Proof.
Given a graph stateSt∈S(bt), a defense action Dt+1, and a sampled attack plan (Ak,ra(Ak)), Algorithm 5 iterates over each node u in the attack sequence ra(Ak) to update the blocked status of u based on the preconditions of this node. Because of the directed acyclic topological structure of the graph, Algorithm 5 has to examine each node in the sequence and its incoming edges once. Therefore, the time complexity of Algorithm 5 is O(V+E). In addition, given the blocked status of the graph computed by Algorithm 5, we estimate the defense value r(Dt+1∣St,Ak,ra(Ak)) based on the cost of disabling nodes in Dt+1 and the potential loss regarding goal nodes of which attack paths are not blocked. The time complexity of this estimation is O(V) since Dt+1+Vg≤2×V. Since there are Na sampled attack plans, the time complexity of computing the defense value r(Dt+1∣St) is O(V+E)×Na.


## 5.5.3. Greedy Defense Strategy

Finding an optimal defense action according to the expected defense valuer(Dt+1∣bt) is computationally expensive, because there is an exponential number of possible defense actions. Therefore, we propose two different greedy heuristics to overcome this computational challenge.Static Greedy Heuristic. This heuristic greedily finds a reasonable set of nodes to disable over the defender’s belief bt. These nodes are chosen from the defense candidate set with respect to the defender’s belief bt, which is defined as ⋃St∈S(bt)Ψd(St) where Ψd(St) is the defense candidate set with respect to the graph state St. Given the current set of selected nodes Dt+1 (which was initially empty), the heuristic finds the next best node u such that r(Dt+1∪{u}∣bt) is maximized. The iteration process stops when disabling new nodes does not increase the defender’s value: r(Dt+1∪{u}∣bt)-r(Dt+1∣bt)≤0 for all u.Proposition 8.
Suppose that the number of graph states to sample in particle filtering isNs (which means that S(bt)=Ns). The time complexity of the static greedy heuristic is O(V2×Ns×(V+E)×Na).Proof.
The size of the defense candidate set⋃St∈S(bt)Ψd(St) is at most V. Therefore, there are at most V iterations of finding next best node in the static greedy heuristic. In each iteration of the heuristic, given the current set of selected nodes Dt+1, for each candidate node u, we compute the defense value r(Dt+1∪{u}∣bt); this step takes O(Ns×(V+E)×Na) time according to Proposition 7. Since there are at most V nodes in the candidate set, the time complexity of static greedy heuristic is O(V2×Ns×(V+E)×Na).In addition, we propose a randomized greedy heuristic to select a defense action from a set of greedy defense actions probabilistically. These greedy defense actions are generated based on eachSt in S(bt).Randomized Greedy Heuristic. This heuristic greedily finds a reasonable set of nodes Dt+1(St) to disable with respect to each St in S(bt). For each St∈S(bt), given the current set of selected nodes Dt+1(St) (which was initially empty), the heuristic finds the next best node u such that r(Dt+1(St)∣St) is maximized. As a result, we obtain multiple greedy defense actions {Dt+1(St)} corresponding to possible game states St in S(bt). The defender then randomizes its choice over {Dt+1(St)} according to a conditional logistic distribution with respect to the defense value {r(Dt+1(St)∣bt)} computed based on the defender belief bt. The following proposition provides the time complexity of the randomized greedy heuristic. This proposition can be proved in a similar way to the complexity of the static greedy heuristic.Proposition 9.
The time complexity of the randomized greedy heuristic isO(V2×Ns×(V+E)×Na).


## 6. Incorporating Uncertainty about the Attack Graph

In the previous sections, we presented our security game model and heuristic strategies of players on the same attack graphG=(V,E)—both the defender and the attacker know the true underlying attack graph of the network system. In this section, we discuss an extension of our model and algorithms to incorporate uncertainty about the attack graph from the players’ perspectives. In other words, both the defender and the attacker have their own attack graphs which are different from the true one.In particular, we denote byG=(V,E) the true attack graph of the network system. Let Ga=(Va,Ea) and Gd=(Vd,Ed) be the attack graphs of the attacker and defender, respectively. Here, Va≠Vd(≠V) and Ea≠Ed(≠E) are the sets of nodes and exploits from the view of the attacker and the defender of the network system. Given this extension, it is straightforward to redefine our heuristic strategies for the attacker and the defender based on Ga and Gd separately. For example, theuniform attack heuristic chooses an attack action from the exploit set Ea uniformly at random. Similarly, thevalue-propagation attack heuristic performs the attack value propagation as well as the probabilistic selection of an attack action based on the attack graph Ga=(Va,Ea) instead of the true G=(V,E).In evaluating the effectiveness of our proposed heuristic strategies, our empirical game-theoretic analysis simulates the attack progression on all three attack graphs: (i) the true attack graph; (ii) the defender’s attack graph; and (iii) the attacker’s attack graph. The whole simulation process is illustrated in Figure9. The states of the attack graphs with respect to the defender and the attacker are determined based on the states of the true attack graphs. The transition of the states on the true attack graphs depends on the actions of the players chosen from our heuristic strategies. For example, if the attacker performs anonexisting exploit, there will be no change of the true graph state. Finally, players’ payoffs are defined based on the true attack graph states, which are used to evaluate the effectiveness of the heuristic strategies.Figure 9
Empirical game-theoretic analysis simulation.


## 7. Experiments

We evaluate the effectiveness of the proposed strategies in various settings with different graph topologies, node type ratios, and levels of defender observation noise. As in prior EGTA treatments of cybersecurity scenarios [40], we employ the simulation data to estimate a two-player normal-form game model of the strategic interaction.


### 7.1. Player Strategies

We tune the strategies for the players by adjusting their parameter values. In our experiments, the fraction of candidates chosen to attack for the attacker’s strategies ispa∈{0.3,0.5} of the total number of attack candidates. The logistic parameter value is ηa∈{1.0,3.0}. As a result, our experiments consist of nine differentattack strategy instances: (i) a No-op (aNoop) instance in which the attacker does not perform any attack action; (ii) two uniform (aUniform) instances with pa∈{0.3,0.5}; (iii) four value-propagation (aVP) instances with pa∈{0.3,0.5} and ηa∈{1.0,3.0}; and (iv) two sampled-activation (aSA) instances with ηa∈{1.0,3.0}.The fraction of nodes chosen to protect for the defender strategies ispd∈{0.3,0.5} of the total number of defense candidate nodes. The logistic parameter value is ηd∈{1.0,3.0}. In addition, the defender’s assumption about the attacker strategy considers the same set of aforementioned attack parameter values. Thus, we evaluate 43 differentdefense strategy instances: (i) a No-op (dNoop) instance in which the defender does not perform any defense action; (ii) two uniform (dUniform), two min-cut uniform (dMincut), and two root-only uniform (dRoot-only) instances with pd∈{0.3,0.5}; (iii) four goal-only (dGoal-only) instances with pd∈{0.3,0.5} and ηd∈{1.0,3.0}; (iv) 16aVP-dVP instances: the defender follows the value-propagation defense strategy while assuming the attacker follows the value-propagation attack strategy; these 16 defense strategy instances correspond to: pd∈{0.3,0.5} and ηd∈{1.0,3.0}, pa∈{0.3,0.5} and ηa∈{1.0,3.0}; (v) eightaSA-dSA instances; these eight strategy instances correspond to ηd∈{1.0,3.0}, ηa∈{1.0,3.0}, and whether the defender uses randomized or static greedy heuristics; and finally (vi) eightaVP-dSA instances; these eight strategies correspond to ηd∈{1.0,3.0}, pa∈{0.3,0.5}, and ηa∈{1.0,3.0}.


### 7.2. Simulation Settings

We consider two types of graph topology: (i) layered directed acyclic graphs (layered DAGs) and (ii) random directed acyclic graphs (random DAGs). Graphs in the former case consist of multiple separate layers with edges connecting only nodes in consecutive layers. We generate 5-layered DAGs. Thekth layer (k=1,…,5) has 25×0.8k-1 nodes. All nodes in the last layer are goal nodes. In addition, edges are generated to connect every node at each layer to 50% of nodes at the next layer (chosen uniformly at random). In the latter case, random DAGs are generated with V=100 and E=300. In addition to leaf nodes, other nodes in random DAGs are selected as goal nodes uniformly at random given a fixed number of goal nodes (which is 15 in our experiments). The proportion of ∧-nodes is either zero or half.The defender’s cost to disable each nodeu∈V, cd(u), is generated within 1.2lmin(u)-1×[-1.0,-0.5] uniformly at random where lmin(u) is the shortest distance from root nodes to u. The attacker’s costs are generated similarly. The attacker reward and the defender’s penalty at each goal node u are generated within 1.2lmin(u)-1×{[10.0,20.0],[-20.0,-10.0]} uniformly at random. Finally, the activation probability associated with each edge with an ∨-postcondition and with each ∧-node is randomly generated within [0.6,0.8] and [0.8,1.0] respectively.We consider three cases of observation noise levels: (i) high noise: the signal probabilitiesp(1v∣s(v)=1) and p(1v∣s(v)=0) are generated within [0.6,0.8] and [0.2,0.4] uniformly at random, respectively; (ii) low noise: p(1v∣s(v)=1) and p(1v∣s(v)=0) are generated within [0.8,1.0] and [0.0,0.2]; and (iii) no noise: p(1v∣s(v)=1)=1.0 and p(1v∣s(v)=0)=0.0. The number of time steps is T=10. The discount factor is γ=0.9.


### 7.3. Strategy Comparison

Based on the aforementioned settings, we generated 10 different games in each of our experiments. For each game, we ran 500 simulations to estimate the payoff of each pair of players’ strategy instances. As a result, we obtain a payoff matrix for each game based on which we can compute Nash equilibria using Gambit [41]. We compute the utility each player obtains for playing the proposed strategy instances (instead of the equilibrium strategy) against the opponent’s equilibrium strategy. We compare that with the utility of the players in the equilibria to evaluate the solution quality of the proposed strategies. Each data point of our results is averaged over the 10 games. In addition, instead of showing results of every individual defense strategy instance (43 in total), we present results of the defense strategies averaged over all corresponding instances.


#### 7.3.1. Results on Layered DAGs

Our first set of experiments is based on layered DAGs, as shown in Figure10 (0%∧-nodes) and Figure 11 (50%∧-nodes). In these figures, the x-axis represents the defender’s or the attacker’s expected utility, and the y-axis represents the corresponding strategy instances played by the players. For the purpose of analysis, we group these strategy instances based on heuristic strategies played, which are represented via the shading on bars. For example, Figures 10(a), 10(b), and 10(c) show the attacker’s utilities for playing the strategies indicated on the y-axis against the defender’s equilibrium strategy, when the percentage of ∧-nodes in graphs is 0%.Figure 10
Strategy evaluation, layered DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseFigure 11
Strategy evaluation, layered DAGs, 50%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseIn Figures10(d), 10(e), 10(f), 11(d), 11(e), and 11(f), the defense sampled-activation strategy (aVP-dSA and aSA-dSA) obtains the defense utility closest to the equilibrium utility (Eq) in all game settings regardless of the assumed attack strategies (i.e., whether the attacker follows the value-propagation or sampled-activation attack strategies with certain parameter values). In fact, when the percentage of ∧-nodes is 0%, the Nash equilibria obtained for all games based on EGTA comprise only the defender’s sampled-activation strategy instances. This result shows that the sampled-activation defense strategy is robust to the defender’s uncertainty about the attacker’s strategy. Furthermore, when the observation noise level increases from no noise to high noise, the defender’s sampled-activation strategies do not suffer from a significant loss in utility. This result implies that the sampled-activation defense strategies are also robust to the defender’s uncertainty about true graph state. Among the no-belief-update strategies, the goal-only strategy outperforms the root-only, min-cut, and uniform strategies in all game settings. This result shows that goal-only is a good candidate strategy when the defender’s belief update is not taken into account. In addition, the goal-only strategy even obtains a higher utility than aVP-dVP in the cases of low and high observation noise.Figures10(a), 10(b), 10(c), 11(a), 11(b), and 11(c) show that in all game settings, the attacker sampled-activation strategy (i.e., aSA-3.0 and aSA-1.0) consistently obtains high attack utility compared with the attacker’s equilibrium strategy (Eq). Even though the defender’s equilibrium strategies focus on competing against the sampled-activation attack strategy, this attack strategy still performs well. The utility obtained by the attacker’s value-propagation strategy (aVP-0.5-3.0, aVP-0.5-1.0, aVP-0.3-3.0, and aVP-0.3-1.0), on the other hand, varies depending on the value of the attack logistic parameter (ηa). In particular, both aVP-0.5-3.0 and aVP-0.3-3.0 with ηa=3.0 obtain a considerably higher utility for the attacker compared with aVP-0.5-1.0 and aVP-0.3-1.0 with ηa=1.0. Compared to all other strategies, the attacker’s uniform strategy (aUniform-0.3 and aUniform-0.5) obtains the lowest attack utility.When the percentage of∧-nodes is 50%, aNoop gets a high probability in the attacker’s equilibrium strategies in all game settings. In Figures 11(a), 11(b), and 11(c), aNoop obtains an attacker utility (which is zero) approximately the same as the equilibrium attack strategy. In fact, when the number of ∧-nodes is large, it is difficult for the attacker to intrude deeply in the attack graph, because compromising ∧-nodes take more effort. Consequently, the defender obtains a significantly higher utility when the percentage of ∧-nodes is 50% (Figures 11(d), 11(e), and 11(f)) than when it is 0% (Figures 10(d), 10(e), and 10(f)). The dNoop strategy is also included in the defender’s equilibrium strategy when the ∧-node percentage is 50%. Finally, in Figure 10(c), the attacker’s equilibrium utility is approximately zero even when all the nodes are of ∨-type. This result shows that when the defender knows the graph state, our sampled-activation defense strategy is highly effective such that the attacker cannot achieve any benefit from attacking.In addition to the results on average in Figures10 and 11, we provide a detailed equilibrium analysis of each individual game. We provide detailed equilibrium results of each individual game with respect to layered directed acyclic graphs with the percentage of ∧-nodes being 0%. In particular, Figures 14 and 15 show equilibria of 10 games in the case of high noise. Figures 16 and 17 show equilibria of 10 games in the case of low noise. Finally, Figures 18 and 19 show equilibria of 10 games in the case of no noise. In addition to the results on the attacker and the defender’s expected utility, we present the equilibrium of each game which consists of the probability that the players play each strategy instance. For example, Figure 14(a) shows the equilibrium analysis of Game 1. In Game 1, the defender’s equilibrium strategy is to play (i) the strategy instance (aVP-0.5-3.0)-(dSA-3.0-ranG) (the defender plays the sampled-activation defense strategy following the randomized greedy heuristic with ηd=3.0, assuming the attacker plays the value-propagation strategy with ηa=3.0 and pa=0.5) with a probability of 0.943; and (ii) the strategy instance (aVP-0.3-3.0)-(dSA-3.0-ranG) (the defender plays the sampled-activation defense strategy following the randomized greedy heuristic with ηd=3.0, assuming the attacker plays the value-propagation strategy with ηa=3.0 and pa=0.3) with a probability of 0.943. On average over all strategy instances according to different parameter values, the defender’s strategy aVP-dSA obtains the expected utility of the defender closest to the equilibrium utility.Overall, the strategy instances of the players involved in each game’s equilibrium vary across different games. Yet, the result of the players’ expected utility for playing each heuristic strategy (averaged over all corresponding strategy instances) is consistent among all games. For example, the sampled-activation defense strategy outperforms other heuristic defense strategies in terms of obtaining an expected utility of the defender closest to the equilibrium utility in all games.


#### 7.3.2. Results on Random DAGs

Our second set of experiments is based on random DAGs (Figure12). This figure shows that the solution quality of the defender’s strategies is similar to the case of layered DAGs. The defender’s sampled-activation strategy obtains a defense utility approximately the same as the equilibrium defense strategy (Eq) (Figures 12(d), 12(e), and 12(f)). For the attacker’s strategies, the sampled-activation attack strategy does not always obtain a high utility for the attacker. In fact, this attack strategy obtains the lowest attack utility in the case of low observation noise (Figure 12(b)). The solution quality of the value-propagation attack strategy, on the other hand, varies depending on the values of both the logistic parameter ηa and the percentage of candidates chosen to attack pa. For example, when there is no observation noise (Figure 12(c)), aVP-0.5-3.0 and aVP-0.3-3.0 with ηa=3.0 obtain a considerably higher attack utility compared to aVP-0.5-1.0 and aVP-0.3-1.0 with ηa=1.0. On the other hand, in the case of low observation noise (Figure 12(b)), aVP-0.5-3.0 and aVP-0.5-1.0 with pera=0.5 obtain the highest attack utility compared with other attack strategies.Figure 12
Strategy evaluation, random DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noise


### 7.4. Strategy Robustness

In our third set of experiments, we evaluate the robustness of the defender’s strategies to the uncertainty about the attacker’s strategy. In particular, in addition to the nine aforementioned attack strategy instances, we consider seven more strategy instances corresponding to new parameter values:pa=0.1 and ηa=5.0. The seven new attack strategy instances include (i) one uniform instance with pa=0.1; (ii) four value-propagation instances with pa=0.1 and ηa=5.0; and (iii) two sampled-activation instances with ηa=5.0. Meanwhile, we use the same 43 defense strategy instances as in the previous sets of experiments. None of these defense strategy instances is based on a model of the attacker using any of the seven new attack strategy instances. We use Nash equilibria of the resulting new games to analyze the solution quality of the proposed strategies. We aim to examine both the attacker’s gain and the defender’s loss in utility with respect to the new attack strategy instances. The experimental results are shown in Figure 13 for layered DAGs with 0%∧-nodes.Figure 13
Robustness evaluation, layered DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseFigure 14
Equilibrium analysis, layered DAGs, 0%∧-nodes, high noise, games 1–5.
(a)
Game 1 (b)
Game 2 (c)
Game 3 (d)
Game 4 (e)
Game 5Figure 15
Equilibrium analysis, layered DAGs, 0%∧-nodes, high noise, games 6–10.
(a)
Game 6 (b)
Game 7 (c)
Game 8 (d)
Game 9 (e)
Game 10Figure 16
Equilibrium analysis, layered DAGs, 0%∧-nodes, low noise, games 11–15.
(a)
Game 11 (b)
Game 12 (c)
Game 13 (d)
Game 14 (e)
Game 15Figure 17
Equilibrium analysis, layered DAGs, 0%∧-nodes, low noise, games 16–20.
(a)
Game 16 (b)
Game 17 (c)
Game 18 (d)
Game 19 (e)
Game 20Figure 18
Equilibrium analysis, layered DAGs, 0%∧-nodes, no noise, games 21–25.
(a)
Game 21 (b)
Game 22 (c)
Game 23 (d)
Game 24 (e)
Game 25Figure 19
Equilibrium analysis, layered DAGs, 0%∧-nodes, no noise, games 26–30.
(a)
Game 26 (b)
Game 27 (c)
Game 28 (d)
Game 29 (e)
Game 30Figures13(a), 13(b), and 13(c) show that the attacker obtains a significantly higher utility on average compared to the corresponding results shown in Figures 10(a), 10(b), and 10(c). On the other hand, the defender suffers a moderate loss in utility (Figures 10(d), 10(e), and 10(f) versus Figures 13(d), 13(e), and 13(f)). For example, in the case of high noise in the defender’s observations, the attacker utility is 20.0, at equilibrium over the original nine attack strategy instances (Figure 10(a)). The attacker’s equilibrium utility is 55.0 (2.75 times higher) when the seven new attack strategy instances are also allowed (Figure 13(a)). Conversely, the defender’s equilibrium utility is approximately -177.0 with the seven new attacker strategies allowed (Figure 13(d)), which is 1.45 times lower than its equilibrium utility of -122.0 for the original, smaller attacker strategy set (Figure 10(d)).The new attacker strategy instances yield significantly higher utility for the attacker than the original set. For example, the sampled-activation instance aSA-5.0 with ηa=5.0 obtains a utility of 32.87 (Figure 13(a)), while aSA-3.0 and aSA-1.0 with ηa=3.0 and ηa=1.0 only get a utility of 20.43 and 10.67, respectively. Figure 13(a) shows that the attacker’s utility achieved by the value-propagation strategy instances with new ηa=5.0, including aVP-0.5-5.0, aVP-0.3-5.0, and aVP-0.1-5.0, is closer to the equilibrium utility than the utility of the earlier value-propagation instances.Although the defender suffers reduced payoffs when the new attack strategy instances are allowed, the relative performance of the defender’s heuristic strategies is consistent with the previous experimental results (Figures10(d), 10(e), and 10(f) versus Figures 13(d), 13(e), and 13(f)). In particular, the sampled-activation defense strategy still obtains the highest utility (which is close to the equilibrium utility) for the defender, regardless of which assumption the defender makes about the attacker’s strategy. Among the graph-based defense strategies, the dGoal-only strategy performs the best in all three cases of the defender’s observation noise level.


## 7.1. Player Strategies

We tune the strategies for the players by adjusting their parameter values. In our experiments, the fraction of candidates chosen to attack for the attacker’s strategies ispa∈{0.3,0.5} of the total number of attack candidates. The logistic parameter value is ηa∈{1.0,3.0}. As a result, our experiments consist of nine differentattack strategy instances: (i) a No-op (aNoop) instance in which the attacker does not perform any attack action; (ii) two uniform (aUniform) instances with pa∈{0.3,0.5}; (iii) four value-propagation (aVP) instances with pa∈{0.3,0.5} and ηa∈{1.0,3.0}; and (iv) two sampled-activation (aSA) instances with ηa∈{1.0,3.0}.The fraction of nodes chosen to protect for the defender strategies ispd∈{0.3,0.5} of the total number of defense candidate nodes. The logistic parameter value is ηd∈{1.0,3.0}. In addition, the defender’s assumption about the attacker strategy considers the same set of aforementioned attack parameter values. Thus, we evaluate 43 differentdefense strategy instances: (i) a No-op (dNoop) instance in which the defender does not perform any defense action; (ii) two uniform (dUniform), two min-cut uniform (dMincut), and two root-only uniform (dRoot-only) instances with pd∈{0.3,0.5}; (iii) four goal-only (dGoal-only) instances with pd∈{0.3,0.5} and ηd∈{1.0,3.0}; (iv) 16aVP-dVP instances: the defender follows the value-propagation defense strategy while assuming the attacker follows the value-propagation attack strategy; these 16 defense strategy instances correspond to: pd∈{0.3,0.5} and ηd∈{1.0,3.0}, pa∈{0.3,0.5} and ηa∈{1.0,3.0}; (v) eightaSA-dSA instances; these eight strategy instances correspond to ηd∈{1.0,3.0}, ηa∈{1.0,3.0}, and whether the defender uses randomized or static greedy heuristics; and finally (vi) eightaVP-dSA instances; these eight strategies correspond to ηd∈{1.0,3.0}, pa∈{0.3,0.5}, and ηa∈{1.0,3.0}.


## 7.2. Simulation Settings

We consider two types of graph topology: (i) layered directed acyclic graphs (layered DAGs) and (ii) random directed acyclic graphs (random DAGs). Graphs in the former case consist of multiple separate layers with edges connecting only nodes in consecutive layers. We generate 5-layered DAGs. Thekth layer (k=1,…,5) has 25×0.8k-1 nodes. All nodes in the last layer are goal nodes. In addition, edges are generated to connect every node at each layer to 50% of nodes at the next layer (chosen uniformly at random). In the latter case, random DAGs are generated with V=100 and E=300. In addition to leaf nodes, other nodes in random DAGs are selected as goal nodes uniformly at random given a fixed number of goal nodes (which is 15 in our experiments). The proportion of ∧-nodes is either zero or half.The defender’s cost to disable each nodeu∈V, cd(u), is generated within 1.2lmin(u)-1×[-1.0,-0.5] uniformly at random where lmin(u) is the shortest distance from root nodes to u. The attacker’s costs are generated similarly. The attacker reward and the defender’s penalty at each goal node u are generated within 1.2lmin(u)-1×{[10.0,20.0],[-20.0,-10.0]} uniformly at random. Finally, the activation probability associated with each edge with an ∨-postcondition and with each ∧-node is randomly generated within [0.6,0.8] and [0.8,1.0] respectively.We consider three cases of observation noise levels: (i) high noise: the signal probabilitiesp(1v∣s(v)=1) and p(1v∣s(v)=0) are generated within [0.6,0.8] and [0.2,0.4] uniformly at random, respectively; (ii) low noise: p(1v∣s(v)=1) and p(1v∣s(v)=0) are generated within [0.8,1.0] and [0.0,0.2]; and (iii) no noise: p(1v∣s(v)=1)=1.0 and p(1v∣s(v)=0)=0.0. The number of time steps is T=10. The discount factor is γ=0.9.


## 7.3. Strategy Comparison

Based on the aforementioned settings, we generated 10 different games in each of our experiments. For each game, we ran 500 simulations to estimate the payoff of each pair of players’ strategy instances. As a result, we obtain a payoff matrix for each game based on which we can compute Nash equilibria using Gambit [41]. We compute the utility each player obtains for playing the proposed strategy instances (instead of the equilibrium strategy) against the opponent’s equilibrium strategy. We compare that with the utility of the players in the equilibria to evaluate the solution quality of the proposed strategies. Each data point of our results is averaged over the 10 games. In addition, instead of showing results of every individual defense strategy instance (43 in total), we present results of the defense strategies averaged over all corresponding instances.


### 7.3.1. Results on Layered DAGs

Our first set of experiments is based on layered DAGs, as shown in Figure10 (0%∧-nodes) and Figure 11 (50%∧-nodes). In these figures, the x-axis represents the defender’s or the attacker’s expected utility, and the y-axis represents the corresponding strategy instances played by the players. For the purpose of analysis, we group these strategy instances based on heuristic strategies played, which are represented via the shading on bars. For example, Figures 10(a), 10(b), and 10(c) show the attacker’s utilities for playing the strategies indicated on the y-axis against the defender’s equilibrium strategy, when the percentage of ∧-nodes in graphs is 0%.Figure 10
Strategy evaluation, layered DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseFigure 11
Strategy evaluation, layered DAGs, 50%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseIn Figures10(d), 10(e), 10(f), 11(d), 11(e), and 11(f), the defense sampled-activation strategy (aVP-dSA and aSA-dSA) obtains the defense utility closest to the equilibrium utility (Eq) in all game settings regardless of the assumed attack strategies (i.e., whether the attacker follows the value-propagation or sampled-activation attack strategies with certain parameter values). In fact, when the percentage of ∧-nodes is 0%, the Nash equilibria obtained for all games based on EGTA comprise only the defender’s sampled-activation strategy instances. This result shows that the sampled-activation defense strategy is robust to the defender’s uncertainty about the attacker’s strategy. Furthermore, when the observation noise level increases from no noise to high noise, the defender’s sampled-activation strategies do not suffer from a significant loss in utility. This result implies that the sampled-activation defense strategies are also robust to the defender’s uncertainty about true graph state. Among the no-belief-update strategies, the goal-only strategy outperforms the root-only, min-cut, and uniform strategies in all game settings. This result shows that goal-only is a good candidate strategy when the defender’s belief update is not taken into account. In addition, the goal-only strategy even obtains a higher utility than aVP-dVP in the cases of low and high observation noise.Figures10(a), 10(b), 10(c), 11(a), 11(b), and 11(c) show that in all game settings, the attacker sampled-activation strategy (i.e., aSA-3.0 and aSA-1.0) consistently obtains high attack utility compared with the attacker’s equilibrium strategy (Eq). Even though the defender’s equilibrium strategies focus on competing against the sampled-activation attack strategy, this attack strategy still performs well. The utility obtained by the attacker’s value-propagation strategy (aVP-0.5-3.0, aVP-0.5-1.0, aVP-0.3-3.0, and aVP-0.3-1.0), on the other hand, varies depending on the value of the attack logistic parameter (ηa). In particular, both aVP-0.5-3.0 and aVP-0.3-3.0 with ηa=3.0 obtain a considerably higher utility for the attacker compared with aVP-0.5-1.0 and aVP-0.3-1.0 with ηa=1.0. Compared to all other strategies, the attacker’s uniform strategy (aUniform-0.3 and aUniform-0.5) obtains the lowest attack utility.When the percentage of∧-nodes is 50%, aNoop gets a high probability in the attacker’s equilibrium strategies in all game settings. In Figures 11(a), 11(b), and 11(c), aNoop obtains an attacker utility (which is zero) approximately the same as the equilibrium attack strategy. In fact, when the number of ∧-nodes is large, it is difficult for the attacker to intrude deeply in the attack graph, because compromising ∧-nodes take more effort. Consequently, the defender obtains a significantly higher utility when the percentage of ∧-nodes is 50% (Figures 11(d), 11(e), and 11(f)) than when it is 0% (Figures 10(d), 10(e), and 10(f)). The dNoop strategy is also included in the defender’s equilibrium strategy when the ∧-node percentage is 50%. Finally, in Figure 10(c), the attacker’s equilibrium utility is approximately zero even when all the nodes are of ∨-type. This result shows that when the defender knows the graph state, our sampled-activation defense strategy is highly effective such that the attacker cannot achieve any benefit from attacking.In addition to the results on average in Figures10 and 11, we provide a detailed equilibrium analysis of each individual game. We provide detailed equilibrium results of each individual game with respect to layered directed acyclic graphs with the percentage of ∧-nodes being 0%. In particular, Figures 14 and 15 show equilibria of 10 games in the case of high noise. Figures 16 and 17 show equilibria of 10 games in the case of low noise. Finally, Figures 18 and 19 show equilibria of 10 games in the case of no noise. In addition to the results on the attacker and the defender’s expected utility, we present the equilibrium of each game which consists of the probability that the players play each strategy instance. For example, Figure 14(a) shows the equilibrium analysis of Game 1. In Game 1, the defender’s equilibrium strategy is to play (i) the strategy instance (aVP-0.5-3.0)-(dSA-3.0-ranG) (the defender plays the sampled-activation defense strategy following the randomized greedy heuristic with ηd=3.0, assuming the attacker plays the value-propagation strategy with ηa=3.0 and pa=0.5) with a probability of 0.943; and (ii) the strategy instance (aVP-0.3-3.0)-(dSA-3.0-ranG) (the defender plays the sampled-activation defense strategy following the randomized greedy heuristic with ηd=3.0, assuming the attacker plays the value-propagation strategy with ηa=3.0 and pa=0.3) with a probability of 0.943. On average over all strategy instances according to different parameter values, the defender’s strategy aVP-dSA obtains the expected utility of the defender closest to the equilibrium utility.Overall, the strategy instances of the players involved in each game’s equilibrium vary across different games. Yet, the result of the players’ expected utility for playing each heuristic strategy (averaged over all corresponding strategy instances) is consistent among all games. For example, the sampled-activation defense strategy outperforms other heuristic defense strategies in terms of obtaining an expected utility of the defender closest to the equilibrium utility in all games.


### 7.3.2. Results on Random DAGs

Our second set of experiments is based on random DAGs (Figure12). This figure shows that the solution quality of the defender’s strategies is similar to the case of layered DAGs. The defender’s sampled-activation strategy obtains a defense utility approximately the same as the equilibrium defense strategy (Eq) (Figures 12(d), 12(e), and 12(f)). For the attacker’s strategies, the sampled-activation attack strategy does not always obtain a high utility for the attacker. In fact, this attack strategy obtains the lowest attack utility in the case of low observation noise (Figure 12(b)). The solution quality of the value-propagation attack strategy, on the other hand, varies depending on the values of both the logistic parameter ηa and the percentage of candidates chosen to attack pa. For example, when there is no observation noise (Figure 12(c)), aVP-0.5-3.0 and aVP-0.3-3.0 with ηa=3.0 obtain a considerably higher attack utility compared to aVP-0.5-1.0 and aVP-0.3-1.0 with ηa=1.0. On the other hand, in the case of low observation noise (Figure 12(b)), aVP-0.5-3.0 and aVP-0.5-1.0 with pera=0.5 obtain the highest attack utility compared with other attack strategies.Figure 12
Strategy evaluation, random DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noise


## 7.3.1. Results on Layered DAGs

Our first set of experiments is based on layered DAGs, as shown in Figure10 (0%∧-nodes) and Figure 11 (50%∧-nodes). In these figures, the x-axis represents the defender’s or the attacker’s expected utility, and the y-axis represents the corresponding strategy instances played by the players. For the purpose of analysis, we group these strategy instances based on heuristic strategies played, which are represented via the shading on bars. For example, Figures 10(a), 10(b), and 10(c) show the attacker’s utilities for playing the strategies indicated on the y-axis against the defender’s equilibrium strategy, when the percentage of ∧-nodes in graphs is 0%.Figure 10
Strategy evaluation, layered DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseFigure 11
Strategy evaluation, layered DAGs, 50%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseIn Figures10(d), 10(e), 10(f), 11(d), 11(e), and 11(f), the defense sampled-activation strategy (aVP-dSA and aSA-dSA) obtains the defense utility closest to the equilibrium utility (Eq) in all game settings regardless of the assumed attack strategies (i.e., whether the attacker follows the value-propagation or sampled-activation attack strategies with certain parameter values). In fact, when the percentage of ∧-nodes is 0%, the Nash equilibria obtained for all games based on EGTA comprise only the defender’s sampled-activation strategy instances. This result shows that the sampled-activation defense strategy is robust to the defender’s uncertainty about the attacker’s strategy. Furthermore, when the observation noise level increases from no noise to high noise, the defender’s sampled-activation strategies do not suffer from a significant loss in utility. This result implies that the sampled-activation defense strategies are also robust to the defender’s uncertainty about true graph state. Among the no-belief-update strategies, the goal-only strategy outperforms the root-only, min-cut, and uniform strategies in all game settings. This result shows that goal-only is a good candidate strategy when the defender’s belief update is not taken into account. In addition, the goal-only strategy even obtains a higher utility than aVP-dVP in the cases of low and high observation noise.Figures10(a), 10(b), 10(c), 11(a), 11(b), and 11(c) show that in all game settings, the attacker sampled-activation strategy (i.e., aSA-3.0 and aSA-1.0) consistently obtains high attack utility compared with the attacker’s equilibrium strategy (Eq). Even though the defender’s equilibrium strategies focus on competing against the sampled-activation attack strategy, this attack strategy still performs well. The utility obtained by the attacker’s value-propagation strategy (aVP-0.5-3.0, aVP-0.5-1.0, aVP-0.3-3.0, and aVP-0.3-1.0), on the other hand, varies depending on the value of the attack logistic parameter (ηa). In particular, both aVP-0.5-3.0 and aVP-0.3-3.0 with ηa=3.0 obtain a considerably higher utility for the attacker compared with aVP-0.5-1.0 and aVP-0.3-1.0 with ηa=1.0. Compared to all other strategies, the attacker’s uniform strategy (aUniform-0.3 and aUniform-0.5) obtains the lowest attack utility.When the percentage of∧-nodes is 50%, aNoop gets a high probability in the attacker’s equilibrium strategies in all game settings. In Figures 11(a), 11(b), and 11(c), aNoop obtains an attacker utility (which is zero) approximately the same as the equilibrium attack strategy. In fact, when the number of ∧-nodes is large, it is difficult for the attacker to intrude deeply in the attack graph, because compromising ∧-nodes take more effort. Consequently, the defender obtains a significantly higher utility when the percentage of ∧-nodes is 50% (Figures 11(d), 11(e), and 11(f)) than when it is 0% (Figures 10(d), 10(e), and 10(f)). The dNoop strategy is also included in the defender’s equilibrium strategy when the ∧-node percentage is 50%. Finally, in Figure 10(c), the attacker’s equilibrium utility is approximately zero even when all the nodes are of ∨-type. This result shows that when the defender knows the graph state, our sampled-activation defense strategy is highly effective such that the attacker cannot achieve any benefit from attacking.In addition to the results on average in Figures10 and 11, we provide a detailed equilibrium analysis of each individual game. We provide detailed equilibrium results of each individual game with respect to layered directed acyclic graphs with the percentage of ∧-nodes being 0%. In particular, Figures 14 and 15 show equilibria of 10 games in the case of high noise. Figures 16 and 17 show equilibria of 10 games in the case of low noise. Finally, Figures 18 and 19 show equilibria of 10 games in the case of no noise. In addition to the results on the attacker and the defender’s expected utility, we present the equilibrium of each game which consists of the probability that the players play each strategy instance. For example, Figure 14(a) shows the equilibrium analysis of Game 1. In Game 1, the defender’s equilibrium strategy is to play (i) the strategy instance (aVP-0.5-3.0)-(dSA-3.0-ranG) (the defender plays the sampled-activation defense strategy following the randomized greedy heuristic with ηd=3.0, assuming the attacker plays the value-propagation strategy with ηa=3.0 and pa=0.5) with a probability of 0.943; and (ii) the strategy instance (aVP-0.3-3.0)-(dSA-3.0-ranG) (the defender plays the sampled-activation defense strategy following the randomized greedy heuristic with ηd=3.0, assuming the attacker plays the value-propagation strategy with ηa=3.0 and pa=0.3) with a probability of 0.943. On average over all strategy instances according to different parameter values, the defender’s strategy aVP-dSA obtains the expected utility of the defender closest to the equilibrium utility.Overall, the strategy instances of the players involved in each game’s equilibrium vary across different games. Yet, the result of the players’ expected utility for playing each heuristic strategy (averaged over all corresponding strategy instances) is consistent among all games. For example, the sampled-activation defense strategy outperforms other heuristic defense strategies in terms of obtaining an expected utility of the defender closest to the equilibrium utility in all games.


## 7.3.2. Results on Random DAGs

Our second set of experiments is based on random DAGs (Figure12). This figure shows that the solution quality of the defender’s strategies is similar to the case of layered DAGs. The defender’s sampled-activation strategy obtains a defense utility approximately the same as the equilibrium defense strategy (Eq) (Figures 12(d), 12(e), and 12(f)). For the attacker’s strategies, the sampled-activation attack strategy does not always obtain a high utility for the attacker. In fact, this attack strategy obtains the lowest attack utility in the case of low observation noise (Figure 12(b)). The solution quality of the value-propagation attack strategy, on the other hand, varies depending on the values of both the logistic parameter ηa and the percentage of candidates chosen to attack pa. For example, when there is no observation noise (Figure 12(c)), aVP-0.5-3.0 and aVP-0.3-3.0 with ηa=3.0 obtain a considerably higher attack utility compared to aVP-0.5-1.0 and aVP-0.3-1.0 with ηa=1.0. On the other hand, in the case of low observation noise (Figure 12(b)), aVP-0.5-3.0 and aVP-0.5-1.0 with pera=0.5 obtain the highest attack utility compared with other attack strategies.Figure 12
Strategy evaluation, random DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noise


## 7.4. Strategy Robustness

In our third set of experiments, we evaluate the robustness of the defender’s strategies to the uncertainty about the attacker’s strategy. In particular, in addition to the nine aforementioned attack strategy instances, we consider seven more strategy instances corresponding to new parameter values:pa=0.1 and ηa=5.0. The seven new attack strategy instances include (i) one uniform instance with pa=0.1; (ii) four value-propagation instances with pa=0.1 and ηa=5.0; and (iii) two sampled-activation instances with ηa=5.0. Meanwhile, we use the same 43 defense strategy instances as in the previous sets of experiments. None of these defense strategy instances is based on a model of the attacker using any of the seven new attack strategy instances. We use Nash equilibria of the resulting new games to analyze the solution quality of the proposed strategies. We aim to examine both the attacker’s gain and the defender’s loss in utility with respect to the new attack strategy instances. The experimental results are shown in Figure 13 for layered DAGs with 0%∧-nodes.Figure 13
Robustness evaluation, layered DAGs, 0%∧-nodes.
(a)
Attacker, high noise (b)
Attacker, low noise (c)
Attacker, no noise (d)
Defender, high noise (e)
Defender, low noise (f)
Defender, no noiseFigure 14
Equilibrium analysis, layered DAGs, 0%∧-nodes, high noise, games 1–5.
(a)
Game 1 (b)
Game 2 (c)
Game 3 (d)
Game 4 (e)
Game 5Figure 15
Equilibrium analysis, layered DAGs, 0%∧-nodes, high noise, games 6–10.
(a)
Game 6 (b)
Game 7 (c)
Game 8 (d)
Game 9 (e)
Game 10Figure 16
Equilibrium analysis, layered DAGs, 0%∧-nodes, low noise, games 11–15.
(a)
Game 11 (b)
Game 12 (c)
Game 13 (d)
Game 14 (e)
Game 15Figure 17
Equilibrium analysis, layered DAGs, 0%∧-nodes, low noise, games 16–20.
(a)
Game 16 (b)
Game 17 (c)
Game 18 (d)
Game 19 (e)
Game 20Figure 18
Equilibrium analysis, layered DAGs, 0%∧-nodes, no noise, games 21–25.
(a)
Game 21 (b)
Game 22 (c)
Game 23 (d)
Game 24 (e)
Game 25Figure 19
Equilibrium analysis, layered DAGs, 0%∧-nodes, no noise, games 26–30.
(a)
Game 26 (b)
Game 27 (c)
Game 28 (d)
Game 29 (e)
Game 30Figures13(a), 13(b), and 13(c) show that the attacker obtains a significantly higher utility on average compared to the corresponding results shown in Figures 10(a), 10(b), and 10(c). On the other hand, the defender suffers a moderate loss in utility (Figures 10(d), 10(e), and 10(f) versus Figures 13(d), 13(e), and 13(f)). For example, in the case of high noise in the defender’s observations, the attacker utility is 20.0, at equilibrium over the original nine attack strategy instances (Figure 10(a)). The attacker’s equilibrium utility is 55.0 (2.75 times higher) when the seven new attack strategy instances are also allowed (Figure 13(a)). Conversely, the defender’s equilibrium utility is approximately -177.0 with the seven new attacker strategies allowed (Figure 13(d)), which is 1.45 times lower than its equilibrium utility of -122.0 for the original, smaller attacker strategy set (Figure 10(d)).The new attacker strategy instances yield significantly higher utility for the attacker than the original set. For example, the sampled-activation instance aSA-5.0 with ηa=5.0 obtains a utility of 32.87 (Figure 13(a)), while aSA-3.0 and aSA-1.0 with ηa=3.0 and ηa=1.0 only get a utility of 20.43 and 10.67, respectively. Figure 13(a) shows that the attacker’s utility achieved by the value-propagation strategy instances with new ηa=5.0, including aVP-0.5-5.0, aVP-0.3-5.0, and aVP-0.1-5.0, is closer to the equilibrium utility than the utility of the earlier value-propagation instances.Although the defender suffers reduced payoffs when the new attack strategy instances are allowed, the relative performance of the defender’s heuristic strategies is consistent with the previous experimental results (Figures10(d), 10(e), and 10(f) versus Figures 13(d), 13(e), and 13(f)). In particular, the sampled-activation defense strategy still obtains the highest utility (which is close to the equilibrium utility) for the defender, regardless of which assumption the defender makes about the attacker’s strategy. Among the graph-based defense strategies, the dGoal-only strategy performs the best in all three cases of the defender’s observation noise level.


## 8. Summary

We study the problem of deploying security countermeasures on Bayesian attack graphs to protect networks from cyber-attacks. We propose a new simultaneous multistage attack graph security game model. Our game model encapsulates security environments with significant dynamics and uncertainty as a stochastic process over multiple time steps. We employ EGTA to analyze this complex security game, as obtaining an analytical solution would be impractical. We propose different parameterized heuristic strategies for both players which leverage the topological structure of attack graphs and employ sampling to overcome the computational complexity. We provide a detailed analysis of the time complexity of our proposed heuristic strategies, which is polynomial. Our EGTA results on various game settings show that our defense heuristics not only outperform several baselines, but also are robust to defender uncertainty about the security environment, including graph states and the attacker’s strategy.



---

*Source: 2864873-2018-12-13.xml*