# New Insights into Approaches to Evaluating Intention and Path for Network Multistep Attacks

Authors: Hao Hu; Yuling Liu; Yingjie Yang; Hongqi Zhang; Yuchen Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The attack graph (AG) is an abstraction technique that reveals the ways an attacker can use to leverage vulnerabilities in a given network to violate security policies. The analyses developed to extract security-relevant properties are referred to as AG-based security evaluations. In recent years, many evaluation approaches have been explored. However, they are generally limited to the attacker’s “monotonicity” assumption, which needs further improvements to overcome the limitation. To address this issue, the stochastic mathematical model called absorbing Markov chain (AMC) is applied over the AG to give some new insights, namely, the expected success probability of attack intention (EAIP) and the expected attack path length (EAPL). Our evaluations provide the preferred mitigating target hosts and the vulnerabilities patching prioritization of middle hosts. Tests on the public datasets DARPA2000 and Defcon’s CTF23 both verify that our evaluations are available and reliable.


---

## Body

## 1. Introduction

Today’s information systems face sophisticated hackers who combine multiple vulnerabilities to penetrate networks with devastating impact. Most network attacks are not single attack actions. They are multistage, multihost attacks, which are composed of a series of attack actions, leading to the network security facing huge threats and challenges. Attack intention and path evaluations aim to model and measure the security-related properties of hacker breaching the enterprise network from the attacker’s perspective, which allows the administrator to quantitatively estimate the overall resilience of network systems against attacksAs a nice tool for modeling multistep attacks, attack graph (AG) [1] represents possible ways in which a potential attacker can break into the target network by exploiting a series of vulnerabilities on various network hosts. When using AG-based metrics, one can analyze security-relevant properties of a network. In particular, evaluations of attack intention and path aim to analyze the vulnerability exploiting relationship among the network nodes in the AG. From the attacker’s perspective, we analyze possible attack paths, identify potential attack intention, and provide an indication of critical attack paths as well as the associated weakest vulnerability links. The estimations offer constructive guidance on security reinforcement and proactive defense.The present AG-based security metrics commonly developed based on the “monotonicity” assumption of attackers, which is firstly proposed in the 2002 ACM Conference on Computer and Communications Security (CCS) [2]. They assumed that the attackers never have to backtrack during the network penetration and each node appears exactly once in any attack path. However, the ideal attack scenario may not be the real scenario launched by the attacker. We recognize that networks commonly have many host interconnections and network privileges obtained in many ways, leading to cycles in an AG. While it is possible to “unfold” the attack graph into an acyclic representation, the approach is impractical because the dramatic increasing in the size of graph structure will likely make the path computing inefficient. To address this issue, we model the complete AG as the absorbing Markov chain (AMC) for expressing the multistep attacks so that we can handle the cycles, and give new insights into measuring intention and path based on this model. It improves the scientificity of metric. More specifically, we give new insights into evaluations towards cyclic attack graph releasing “monotonicity” assumption with two major highlights as follows:(i)
The expected success probabilities of attack intentions (EAIPs) for the attacker to compromise different attack intention nodes are estimated.(ii)
The expected attack path lengths (EAPLs) that the attacker needs to breach different attack intention nodes from different initial state node are calculated.The former enables a manager to determine the prioritization of vulnerability patching regarding different attack intention hosts. The latter can be devoted to giving a better understanding concerning the counter steps the attacker needs to breach the goal and can further optimize the necessary steps to harden the enterprise network from external threats as well.The rest of this paper is organized as follows. Section2 describes related works, which include analysis of attack intention and path evaluations, respectively. Section 3 contains a detailed presentation of the preliminaries about this paper. In addition, the model of AMC-based AG is developed in Section 4. Section 5 performs deep analyses on metrics of attack intention and path using the probability inference over AMC, and two evaluation algorithms are proposed. Section 6 describes the experiments and analyses of the proposed algorithms on two public datasets. Finally, we conclude this paper in Section 7.


## 2. Related Works

Network security evaluation may provide quantifiable evidence to assist security practitioners in securing computer networks, which have received significant attention in recent years. For instance, Pendleton et al. [3] designed a security metrics framework. Behi et al. [4] provided a structure for quantitation of network security and prioritization of significant security metrics. In addition, Ramos et al. [5] presented a deep survey of the state-ofthe-art of existing model-based security metric from the aspects of classifications, advantages/disadvantages, characteristics, and open research issues.Recent works mostly focus on the usage of AG for security metrics and monitoring, which makes it easier for administrators to directly understand the attacking process. In the AG, attack paths are described by using nodes and edges to represent vulnerabilities and exploits, respectively. For attack graph-based security metric, Kantar et al. [1] made a systematical study of potential challenges and open issues of AG. One of the important works related to AG focus on modeling and core building issues. They focus on solving the scalability problem for AG generation. A large number of commercially automatic builders were designed and commonly used in large-scale attacks. These automatic builders extended the limited capability for manual construction, which was tedious, error-prone, and impractical for attack graphs when the enterprise network has a large number of nodes. With the gradual development of construction technology of AG, the application of AG in the aspect of measurement of attack intentions and paths has attracted scholars’ extensive attention.For attack intention evaluation, intention recognition is the process of deducing an invader’s ultimate goal from observed actions. The rapid development of network technologies has helped network attackers to hide their malicious intentions. The conventional Intrusion Prevention System (IPS) is capable of analyzing the actions of an attacker. However, IPS cannot infer intentions and predict a series of exploits. To improve the intelligence level of IPS, Cai et al. [6] constructed an intrusion prevention method based on Weighed Planning Knowledge Graph (WPKG), which is an acyclic graph essentially. Based on alert observations, Zhu et al. [7] identified the attacker’s intention using alert correlation technology. However, it fails to reduce false positive alerts. Noel et al. [8] built a predictive model of possible attack paths and critical vulnerabilities, correlating alerts to known vulnerability paths. The model suggested best courses of action for responding to attacks. Ahmed et al. [9] analyzed attack types and classified them according to their malicious intentions, further used similarity metrics to recognize attacker plans, and predicted their intentions. Concerning that attack likelihoods are propagated through the attack graph, the probabilistic AG is proposed by Ou et al. [10] to calculate the cumulative probability of attack steps in the acyclic graph. Due to the drawback of static analysis in the above methods, Nayot et al. [11] used the dynamic Bayesian Attack Graph (BAG) to represent the causal relationships between preconditions, vulnerability exploits, and postconditions. The superiority is that the proposed approach can dynamically revise the likelihood of compromising intention via encoding the attack events into BAG. Besides, Ghasemigol et al. [12] introduced a comprehensive approach that can predict future attacks with higher precision and dynamically adapt to changes in the environment.Through the above analysis, many works have been investigated from various aspects such as alert correlation, cumulative probability, evidence theory, and Bayesian inference. Although the above reports made significant progress in security metric using attack graph, the major limitation is that they do not allow cycles in attack graphs. Moreover, existing researches focus on analyzing attackers with just one attack intention. Few investigations have been provided on sophisticated scenarios with multiple attack intentions. How to quantify the reachable probabilities of different attack intentions and further rank all intentions to find out the preferred attack intention is still essential.For attack path evaluation, nodes and edges in the AG describe vulnerabilities and their exploits, respectively. Path evaluation aims to analyze the vulnerability exploit relationship among the network nodes. Ritchey et al. [13] developed a mathematics model to determine if an intention state is reachable from the initial state. To identify the path of one-day attack, Sun et al. [14] described a prototype system called ZePro to generate the path by taking a probabilistic approach using the Bayesian network. Wang et al. [15] described a novel security metric for zero-day attacks by counting how many such vulnerabilities are required for compromising network assets. A modified version of Floyd–Warshall and Dijkstra algorithm is proposed by Sarraute et al. [16] to compute the shortest attack path. To explore the fast and accurate solution of finding a potential vulnerable path in the network, Wang et al. [17] used the augmented road algorithm to find optimal attack path within the global paths. To integrate the above security metrics, Idika et al. [18] presented a suite of AG-based security metrics. For instance, the normalized mean of path lengths, the median of path lengths, mode of path lengths, and standard deviation of path lengths. The advantages are that multidimensional measurements of attack paths are achieved. Overall, the above investigations mainly focused on the path metrics upon the ideal attack scenario.While the above achievements on evaluations of intention and path are abundant and useful, most of them miss out one major issue. Major existing metrics rely on the “monotonicity” assumption, which means that an attacker never needs to relinquish any obtained capability. The assumption of “monotonicity” means that an attacker never has to backtrack, which improves the scalability of the AG, but only reflects the ideal attack scenario. Bopche et al. [19] had reported that the ideal security metrics such as the shortest path and the number of paths cannot reflect the security strength of the network accurately. Ammann et al. [2] also explained that “there are certain attacks where monotonicity does not strictly hold”.Within this assumption, all the attack scenarios can be modeled as the ideal acyclic graphs. However, the real-world attackers may not be familiar with the given network topology. We recognize that networks have many host interconnections and network privileges obtained in many ways generally, leading to cycles in AG. When calculating the path length, existing reports omit the appearances of repeated nodes in the path. On the contrary, the action of vulnerability exploitation truly happens even if the attempt fails in the realistic attack scenario. Hence, the estimate of path length in the realistic scenario may be greater.To accurately estimate the attacker’s intention and measure the path length, we borrow a stochastic mathematical model AMC [20] from the attacker’s perspective in this paper. AMC has been widely used in economics, which is capable of analyzing the potential rules of state transition behaviors. Inspired by this, we recognize that multistep and multihost attacks can also be modeled and analyzed using AMC. We analyze the propagation of probabilities along attack paths in the AMC and obtain a suit of metric. In detail, we use automatic tool Multihost Multistage Vulnerability Analysis (MulVAL) [21] to generate logical AG firstly. Then, we design a normalization algorithm with respect to state transition probability and prove that any complete AG can be converted to an AMC. In addition, with the inference process of AMC, we design the relevant matricesB andT for calculating EAIP and EAPL respectively. Additionally, we present two evaluation algorithms, which provide new insights into security metrics of EAIP and EAPL. Finally, we test our algorithms on the CTF and DARPA datasets.


## 3. Preliminaries

Table1 summarizes the primary symbols in this paper.Table 1
Symbols and their descriptions in this paper.
Symbol Description AG Attack graph AMC Absorbing Markov chain S Set of all state nodes O Set of all transient state nodes G Set of all absorbing state nodes A Set of all atomic attack nodes E Set of total edges in AG Δ Set of total edge probabilities n Number of all states t Number of all transient states r Number of all absorbing states S i Thei-th attack state E o u t i Set of out-going edges ofSi e i , j Edge betweenSi and Sj a i , j Dependent atomic attack fromSi to Sj Δ ( e i , j ) Probability ofei,j EAIP Expected success probability of attack intention EAPL Expected attack path length P State transition matrix P m State transition matrix after launchingm steps of atomic attacks Q Transition matrix of transient states R Transition matrix from transient states to absorbing states N Fundamental matrix I Identity matrix C Unit vector B Calculation matrix of EAIP T Calculation matrix of EAPL ProbRank Ranking of absorbing states according to their EAIPs LengRank Ranking of transient states according to their EAPLs


### 3.1. Motivation

In the above section, we explained that the circles in the AG are the key issue in our study. It is possible to unfold any cyclic graph into an equivalent acyclic graph such that each node appears exactly once in any path. However, this procedure is not necessary if we apply a stochastic model to the cyclic nodes so that we can evaluate the same probabilities as on the unfolded graph but without actually unfolding it. The key idea is to model the complete AG as the AMC, which plays an important role in our approach. On the one hand, the Markov property of AMC is in line with the randomness of attack states transition. On the other hand, any network attacks have at least one ultimate state, which corresponds to the absorbing state in the AMC. Hence, we describe, analyze, and estimate the underlying rules of attack behaviors in the framework of AMC in this paper.


### 3.2. Attack Graph

As an effective method for modeling multistep attack behaviors, any real-world attack scenario can be abstracted as a logical AG such as Figure1.Figure 1
An example attack graph.Definition 1.
Atomic attack is a single step that cannot be broken anymore. It may be a host service scanning or an exploit of the vulnerability. Each atomic attack carries the attacker to a new attack stateS.Definition 2.
Attack graph is a tupleAG=(S,E,A,Δ), whereS is the set of state nodes,A is the set of atomic attack nodes,E is the set of directed edges, and Δ is the set of probabilities of state transitions.(1)
S=Si∣i=1,2,…,n is the set of all state nodes in the AG, in which G⊆S is the set of intention state nodes, and O=S-G is the set of residual state nodes.(2)
E⊆S×S, where the element inE is the inner product ofS. ∀ei,j∈E, ei,j is the edge connecting nodes Si and Sj, where Si is the former node of ei,j and Sj is the latter node of ei,j.(3)
An atomic attackai,j∈A allows an attacker to compromise the Sj from Si with a nonzero probability of success. The attacker can reach certain privilege state by exploiting the relevant vulnerability.(4)
Δ(ei,j)∈Δ denotes the attack likelihoods propagated through the edge ei,j. It measures the success probability associated with the atomic attack ai,j. If the state transition ei,j is unreachable, assign Δ(ei,j)=0.The logical attack graph is generated using a network model builder (e.g., MulVAL, TVA, and NETSPA) by taking the network topology, services running logs, and the firewall policy as input. In this paper, we adopt MulVAL to generate the logical AG. The MulVAL is an efficient polynomial-time builder [21]. Given an attack graph, the edge probability can be computed by diverse technologies (e.g., prior domain knowledge, alert sequence, CVSS metric, and data mining). For the specific surveys, the reader can refer to [1].Definition 3.
Attack intention is a certain ultimate state that attacker wants to achieve.Definition 4.
Attack path is the transition sequence of the attacker starting from an initial state to an intention state. The number of edges equals the length of the attack path.Definition 5.
Expected success probability of attack intention (EAIP) is the mathematical expected value of the probability that the attacker can reach his intention. ProbRank denotes the ranking of intentions according to EAIPs.Definition 6.
Expected attack path length (EAPL) is the mathematical expected value of the number of attack steps the attacker needs to take from his initial state to his intention state. LengRank denotes the ranking of state nodes according to their EAPLs.Remarks (1)
Assume that an attacker can exploit a total of two independent attack paths with length 1 and 4 to reach his intention with probability 1/6 and 1/3, respectively; thenEAIP=1/2,EAPL=(1/6)·1+(1/3)·4=3/2. In other words, the attacker will reach the intention node with a sum of probability of 1/2. Meanwhile, the mean number of steps of reaching the intention is 3. (2)
The path in ideal attack scenario does not consider the repeated appearing nodes, so there is no circle in the acyclic scenario graph. The EAPL and EAIP equal the arithmetic mean of statistics. (3)
In a real-world attack scenario, the number of possible paths is uncertain due to the cyclic path. Hence, the calculation of EAPL is difficult. To the best of our knowledge, so far little researches have been devoted to this issue.


### 3.3. Absorbing Markov Chain

Definition 7.
Markov chain (MC) [20] is a discrete sequence satisfying the following condition: MC contains a finite number of random states, and each state is only related to the predecessor state. Formally(1)pxi+1∣xi,xi-1,…,x1=pxi+1∣xi.Definition 8.
State transition matrixP [20] is an n×n adjacency matrix of MC; the (i,j) entry pi,j is the probability of state transition xi→xj. If xi→xj is unreachable, assign pi,j=0. The matrixP satisfies(2)∑j=1npi,j=1,0≤pi,j≤1,1≤i,j≤n.Definition 9.
Absorbing state is the state where the security intention is violated. This state node only has in-going edges but does not have out-going edges.Definition 10.
Transient state is the nonabsorbing state, which has at least one out-going edge.Definition 11.
Absorbing Markov chain (AMC) [20] is a special Markov chain containing at least one absorbing state. For the AMC includingr absorbing states andt transient states, the standard form of the state transition matrix is(3)
P
=
Q
R
0
IwhereQ is a t×t matrix representing transition probabilities of the transient states, 0 is a r×t zero matrix,R is a t×r matrix representing the transition probabilities between transient states and absorbing states, andI is an r×r identity matrix. The total number of states is n=t+r.


## 3.1. Motivation

In the above section, we explained that the circles in the AG are the key issue in our study. It is possible to unfold any cyclic graph into an equivalent acyclic graph such that each node appears exactly once in any path. However, this procedure is not necessary if we apply a stochastic model to the cyclic nodes so that we can evaluate the same probabilities as on the unfolded graph but without actually unfolding it. The key idea is to model the complete AG as the AMC, which plays an important role in our approach. On the one hand, the Markov property of AMC is in line with the randomness of attack states transition. On the other hand, any network attacks have at least one ultimate state, which corresponds to the absorbing state in the AMC. Hence, we describe, analyze, and estimate the underlying rules of attack behaviors in the framework of AMC in this paper.


## 3.2. Attack Graph

As an effective method for modeling multistep attack behaviors, any real-world attack scenario can be abstracted as a logical AG such as Figure1.Figure 1
An example attack graph.Definition 1.
Atomic attack is a single step that cannot be broken anymore. It may be a host service scanning or an exploit of the vulnerability. Each atomic attack carries the attacker to a new attack stateS.Definition 2.
Attack graph is a tupleAG=(S,E,A,Δ), whereS is the set of state nodes,A is the set of atomic attack nodes,E is the set of directed edges, and Δ is the set of probabilities of state transitions.(1)
S=Si∣i=1,2,…,n is the set of all state nodes in the AG, in which G⊆S is the set of intention state nodes, and O=S-G is the set of residual state nodes.(2)
E⊆S×S, where the element inE is the inner product ofS. ∀ei,j∈E, ei,j is the edge connecting nodes Si and Sj, where Si is the former node of ei,j and Sj is the latter node of ei,j.(3)
An atomic attackai,j∈A allows an attacker to compromise the Sj from Si with a nonzero probability of success. The attacker can reach certain privilege state by exploiting the relevant vulnerability.(4)
Δ(ei,j)∈Δ denotes the attack likelihoods propagated through the edge ei,j. It measures the success probability associated with the atomic attack ai,j. If the state transition ei,j is unreachable, assign Δ(ei,j)=0.The logical attack graph is generated using a network model builder (e.g., MulVAL, TVA, and NETSPA) by taking the network topology, services running logs, and the firewall policy as input. In this paper, we adopt MulVAL to generate the logical AG. The MulVAL is an efficient polynomial-time builder [21]. Given an attack graph, the edge probability can be computed by diverse technologies (e.g., prior domain knowledge, alert sequence, CVSS metric, and data mining). For the specific surveys, the reader can refer to [1].Definition 3.
Attack intention is a certain ultimate state that attacker wants to achieve.Definition 4.
Attack path is the transition sequence of the attacker starting from an initial state to an intention state. The number of edges equals the length of the attack path.Definition 5.
Expected success probability of attack intention (EAIP) is the mathematical expected value of the probability that the attacker can reach his intention. ProbRank denotes the ranking of intentions according to EAIPs.Definition 6.
Expected attack path length (EAPL) is the mathematical expected value of the number of attack steps the attacker needs to take from his initial state to his intention state. LengRank denotes the ranking of state nodes according to their EAPLs.Remarks (1)
Assume that an attacker can exploit a total of two independent attack paths with length 1 and 4 to reach his intention with probability 1/6 and 1/3, respectively; thenEAIP=1/2,EAPL=(1/6)·1+(1/3)·4=3/2. In other words, the attacker will reach the intention node with a sum of probability of 1/2. Meanwhile, the mean number of steps of reaching the intention is 3. (2)
The path in ideal attack scenario does not consider the repeated appearing nodes, so there is no circle in the acyclic scenario graph. The EAPL and EAIP equal the arithmetic mean of statistics. (3)
In a real-world attack scenario, the number of possible paths is uncertain due to the cyclic path. Hence, the calculation of EAPL is difficult. To the best of our knowledge, so far little researches have been devoted to this issue.


## 3.3. Absorbing Markov Chain

Definition 7.
Markov chain (MC) [20] is a discrete sequence satisfying the following condition: MC contains a finite number of random states, and each state is only related to the predecessor state. Formally(1)pxi+1∣xi,xi-1,…,x1=pxi+1∣xi.Definition 8.
State transition matrixP [20] is an n×n adjacency matrix of MC; the (i,j) entry pi,j is the probability of state transition xi→xj. If xi→xj is unreachable, assign pi,j=0. The matrixP satisfies(2)∑j=1npi,j=1,0≤pi,j≤1,1≤i,j≤n.Definition 9.
Absorbing state is the state where the security intention is violated. This state node only has in-going edges but does not have out-going edges.Definition 10.
Transient state is the nonabsorbing state, which has at least one out-going edge.Definition 11.
Absorbing Markov chain (AMC) [20] is a special Markov chain containing at least one absorbing state. For the AMC includingr absorbing states andt transient states, the standard form of the state transition matrix is(3)
P
=
Q
R
0
IwhereQ is a t×t matrix representing transition probabilities of the transient states, 0 is a r×t zero matrix,R is a t×r matrix representing the transition probabilities between transient states and absorbing states, andI is an r×r identity matrix. The total number of states is n=t+r.


## 4. Model of AMC-Based AG

In this section, we first present a normalized algorithm for state transition probabilities in the AG and then construct the state transition matrixP of AMC. On this basis, we prove that the complete AC can be converted to the AMC.The pseudocode describing the normalization approach for edge probabilities in AG is presented in Algorithm1. The variablesi andj label theith row andjth column of the matrixP, respectively, where 1≤i,j≤n. The variablek labels thekth out-going edge of the node Si. The set Eouti is the set of total out-going edges of the node Si.Algorithm 1:Pseudocode for state transition probability normalization algorithm.
INPUT: A G = ( S , A , E , Δ ) OUTPUT: The matrix Pof AMC BEGIN ( 1 ) Initialize i,j=1, k=0, Eouti=⌀ ( 2 ) FORi=1ton​ ( 3 )  FORj=1ton​ ( 4 )   Select Sj∈S ( 5 )    IfΔ(ei,j)≠0​ ( 6 )    k=k+1 ( 7 )    ei,jk=ei,j ( 8 )    Add ei,jk to Eouti ( 9 )    elsepi,j=0 ( 10 )  FORt=1 to k​ ( 11 )    pi,jt=Δ(ei,jt)Δ(ei,j1)+…+Δ(ei,jk) ( 12 )    k=0 ( 13 ) Return P ENDWe initialize the variables firstly as depicted in line(1), and then each row vector of matrixP is generated orderly. For theith row vector ofP, as shown in lines (3)–(11), it is generated according to the node Si. More specifically, we first select all the out-going edges ei,jk of Si and add them into the set Eouti, then we calculate the normalized probability of state transition Si→Sjt in the AMC, and assign the (i,jt) entry ofP as Δ(ei,jt)/Δ(ei,j1)+…+Δ(ei,jk), 1≤t≤k. The residual entries in theith row vector are assigned with 0. We perform the above recursive process until the matrixP is fully constructed.According to the number of layers of the recursive algorithm, the time complexity isO(n2). Our algorithm needs to store n×n matrixP and 1×k vector Eouti; thus the space complexity is also O(n2). Therefore, the proposed Algorithm 1 is reachable in polynomial time.A complete attack graph contains at least one absorbing state node. The absorbing state is the attack intention node where the security goal is violated. It is possible to go to an absorbing state starting from any transient state in a finite number of steps in a complete AC. Once the attacker reaches the intention node, then the system is considered to be in a breached state and the attacker realizes his goal. Therefore, the attacker will continue to remain in this state until preventive measures are taken by the security team to remove the attacker’s presence from the system. Hence, the absorbing state corresponds to the attack intention, and any complete AC contains at least one absorbing state.A complete AG satisfies the following two conditions and is therefore an absorbing Markov chain: (i) The sum of probabilities of all out-going edges from the nodeSi is equal to 1. (ii) The AG contains at least one absorbing state node. The above conditions hold as follows.Using Algorithm1, for any node Si, we can obtain Δ(ei,j1)/Δ(ei,j1)+…+Δ(ei,jk)+Δ(ei,j2)/Δ(ei,j1)+…+Δ(ei,jk)+…+Δ(ei,jk)/Δ(ei,j1)+…+Δ(ei,jk)=1, which indicates that Definition 8 holds. Consequently, condition (i) holds. Since any complete AC contains at least one absorbing state, we can derive that condition (ii) holds. Accordingly, we can get that the proposed proposition holds by (1) and (2).The following is the state transition matrix of AMC associated with Figure1 calculated by Algorithm 1.(4)
P
=
0
Δ
e
1,2
Δ
e
1,2
+
Δ
e
1,3
Δ
e
1,3
Δ
e
1,2
+
Δ
e
1,3
0
Δ
e
2,1
Δ
e
2,1
+
Δ
e
2,4
0
0
Δ
e
2,4
Δ
e
2,1
+
Δ
e
2,4
0
0
1
0
0
0
0
1


## 5. New Insights into Evaluations of Attack Intention and Path

In the previous section, we model the AG as the AMC and construct the state transition matrix of AG-based AMC. In this section, some lemmas and theorems for state transition are deduced based on this model. In addition, we present new insight into evaluations to quantify EAIP and EAPL.


### 5.1. Evaluation of EAIP

Lemma 12.
LetP be the transition matrix of AMC meeting Definition 11. The entry pi,j denotes the probability of Si→Sj and pi,jm denotes the probability of Si→Sj after launchingm steps of atomic attack. Pm is themth power of matrixP. Then one has(5)Pm=Qm∑k=0m-1Qk·R0I.Proof.
Using mathematical induction, we have the following:(1)
Whenm=2, (5) holds as follows:(6)P2=QR0I·QR0I=Q·QQ·R+R·I0I·I=Q2Q+Q0·R0I=Q2∑k=01Qk·R0I.(2)
Assume (5) holds if m=h-1; thus Ph-1=Qh-1∑k=0h-2Qk·R0I, and then we can derive(7)Ph=Ph-1·P=Qh-1∑k=0h-2Qk·R0I·QR0I=Qh-1·QQh-1·R+∑k=0h-2Qk·R0I2=Qh∑k=0h-1Qk·R0I.
Therefore, the assumption follows. From(1) and (2), we can obtain that Lemma 12 holds.Lemma 13.
The attacker will reach an ultimate absorbing state from any initial transient state if the number of attack actions is not limited. In other words, the transition probabilities between transient states are 0. Mathematically,(8)limm→∞Pm=0∑k=0m-1Qk·R0I.Proof.
By (3) and (5), if the above formula holds, then we only need to prove limm→∞Qm=0. Theijth element Qi,jm of the matrix Qm gives the probability that the Markov chain, starting in the state Si, will be in the state Sj afterm steps. Then we need to prove limm→∞Qi,jm=0. It gives us an idea about the convergence of the AMC. Suppose the probability of reaching an absorbing state is nonzero; let it beu, where 0<u≤1. Then, initially, the probability that the process will not be absorbed is (1-u). Afterm steps, this probability is equal to (1-u)m. Note that as m→∞, we can derive (1-u)m→∞. Thus, for every transient state Si, the probability that the attacker remains in the state Si is 0. Hence, Lemma 13 holds.Lemma 14.
Given at×t fundamental matrixN, the (i,j) entry Ni,j denotes the expected number of visits to the transient node Sj from the initial transient node Si before absorption. Then we can derive N=(1-Q)-1.Proof.
( 1 ) If we want to compute the expected number of steps until the chain enters a recurrent class, assuming starting at state Si, we only need to sum Ni,j over all transient states Sj. Thus, the sum of number of visits the chain is in the state Sj, given that the chain, starting in the state Si, throughm steps of atomic attack is N=I+Q1+Q2+Q3⋯=∑m=0∞Qm.
( 2 ) As ∑k=0m-1Qk=I+Q+…+Qm-1=(I-Q)-1·(I-Qm), by (5) and (8), we can derive limm→∞Qm=0; it implies that all the eigenvalues ofQ have absolute values strictly less than 1. Hence, I-Q is an invertible matrix. Thus, limm→∞(I-Qm)=I. Furthermore, we can obtain ∑m=0∞Qm=limm→∞∑k=0m-1Qk=(I-Q)-1.
According to(1) and (2), Lemma 14 holds.Theorem 15.
Given at×r matrixB, the (i,j) entry Bi,j denotes the EAIP of the attacker absorbing in Sj, given that the chain started in Si, where 1≤i≤t, 1≤j≤r. Then one can derive B=N·R.Proof.
By Lemmas13 and 14, we can obtain limm→∞Pm=0N·R0I. Theith row of N·R gives the probabilities of ending up in each of the absorbing states, given that the chain started in theith transient states. Hence, we can derive B=N·R, and the theorem holds.To simplify the presentation, we use the attack graph in Figure1 as an example. We manually assign Δ(e1,2)=3/4,Δ(e1,3)=3/4,Δ(e2,1)=1/2,Δ(e2,4)=1/4, and then we can obtain the corresponding state transition matrixP using Algorithm 1. Additionally, combined with (3), we can constructQ andR and further calculate the matrixB as follows:(9)
P
=
S
1
S
2
S
3
S
4
S
1
1
2
S
2
1
2
S
3
S
4
0
1
2
1
2
0
2
3
0
0
1
3
0
0
1
0
0
0
0
1
,
Q
=
S
1
S
2
S
1
S
2
0
1
2
2
3
0
,
R
=
S
3
S
4
S
1
S
2
1
2
0
0
1
3
,
B
=
I
-
Q
-
1
·
R
=
S
3
S
4
S
1
S
2
3
4
1
4
1
2
1
2
.From the first row ofB, if the attacker started at S1, the EAIPs of S3 and S4 are 3/4 and 1/4 respectively. Since the EAIP of S3 is higher, the most likely attack intention is S3 and the rank of intentions is ProbRank=S3>S4. By the second row ofB, if the initial attack state is S2, it is observed that the reachable probabilities of S3 and S4 are equal to 1/2. Moreover, for the above two examples, we can see that the attacker will finally reach the absorbing state nodes with the definite probability 1 regardless of its initial state.


### 5.2. Evaluation of EAPL

Theorem 16.
Given at×1 matrixT, where the entry Ti denotes the EAPL the attacker needs to take from the initial state node Si to the intention state, 1≤i≤t, letC be a t×1 unit vector, and then one has T=N·C.Proof.
According to Lemma14, for attacker starting from the initial node Si, the visits to S1,S2,…,St before absorption are Ni,1,Ni,2,…,Ni,t, respectively. As a result, the EAPL of Si is Ti=Ni,1+Ni,2+…+Ni,t (equals to the sum of visits to the appearing nodes in the path). Hence, we can derive T=Ti=Ni,1+Ni,2+…+Ni,t=N·C and that Theorem 16 holds.Going on with the example in Section5.1, we can derive that(10)T=N·C=3234132·11=S1S29452.Obviously, EAPLs ofS1 andS2 are 9/4 and 5/2, respectively. Assume that the time-cost for each step attack is equal; then the penetration starting from S1 is quicker than that from S2. Therefore, the crucial degree ofS1 is higher, and the mitigation priorities of the nodes are LengRank=S1>S2.


### 5.3. Algorithm Complexity Analysis

For the above-mentioned two algorithms, the space and time complexity are as follows:(1)
The algorithms need to maintainn×n matrixP, t×t matrixQ, t×t matrixN, t×r matrixB, t×1 matrixC, and t×1 matrixT. Since n=r+t, the space complexity is O(n2).(2)
The operations of the algorithm include matrix inversion, matrix addition, and matrix multiplication. Among them, the time complexity of matrix multiplication is the highest. When twon×n matrices are multiplied, there are 2n3 fundamental operations, so the time complexity is O(n3).To sum up, the proposed algorithms achieve polynomial complexity.


## 5.1. Evaluation of EAIP

Lemma 12.
LetP be the transition matrix of AMC meeting Definition 11. The entry pi,j denotes the probability of Si→Sj and pi,jm denotes the probability of Si→Sj after launchingm steps of atomic attack. Pm is themth power of matrixP. Then one has(5)Pm=Qm∑k=0m-1Qk·R0I.Proof.
Using mathematical induction, we have the following:(1)
Whenm=2, (5) holds as follows:(6)P2=QR0I·QR0I=Q·QQ·R+R·I0I·I=Q2Q+Q0·R0I=Q2∑k=01Qk·R0I.(2)
Assume (5) holds if m=h-1; thus Ph-1=Qh-1∑k=0h-2Qk·R0I, and then we can derive(7)Ph=Ph-1·P=Qh-1∑k=0h-2Qk·R0I·QR0I=Qh-1·QQh-1·R+∑k=0h-2Qk·R0I2=Qh∑k=0h-1Qk·R0I.
Therefore, the assumption follows. From(1) and (2), we can obtain that Lemma 12 holds.Lemma 13.
The attacker will reach an ultimate absorbing state from any initial transient state if the number of attack actions is not limited. In other words, the transition probabilities between transient states are 0. Mathematically,(8)limm→∞Pm=0∑k=0m-1Qk·R0I.Proof.
By (3) and (5), if the above formula holds, then we only need to prove limm→∞Qm=0. Theijth element Qi,jm of the matrix Qm gives the probability that the Markov chain, starting in the state Si, will be in the state Sj afterm steps. Then we need to prove limm→∞Qi,jm=0. It gives us an idea about the convergence of the AMC. Suppose the probability of reaching an absorbing state is nonzero; let it beu, where 0<u≤1. Then, initially, the probability that the process will not be absorbed is (1-u). Afterm steps, this probability is equal to (1-u)m. Note that as m→∞, we can derive (1-u)m→∞. Thus, for every transient state Si, the probability that the attacker remains in the state Si is 0. Hence, Lemma 13 holds.Lemma 14.
Given at×t fundamental matrixN, the (i,j) entry Ni,j denotes the expected number of visits to the transient node Sj from the initial transient node Si before absorption. Then we can derive N=(1-Q)-1.Proof.
( 1 ) If we want to compute the expected number of steps until the chain enters a recurrent class, assuming starting at state Si, we only need to sum Ni,j over all transient states Sj. Thus, the sum of number of visits the chain is in the state Sj, given that the chain, starting in the state Si, throughm steps of atomic attack is N=I+Q1+Q2+Q3⋯=∑m=0∞Qm.
( 2 ) As ∑k=0m-1Qk=I+Q+…+Qm-1=(I-Q)-1·(I-Qm), by (5) and (8), we can derive limm→∞Qm=0; it implies that all the eigenvalues ofQ have absolute values strictly less than 1. Hence, I-Q is an invertible matrix. Thus, limm→∞(I-Qm)=I. Furthermore, we can obtain ∑m=0∞Qm=limm→∞∑k=0m-1Qk=(I-Q)-1.
According to(1) and (2), Lemma 14 holds.Theorem 15.
Given at×r matrixB, the (i,j) entry Bi,j denotes the EAIP of the attacker absorbing in Sj, given that the chain started in Si, where 1≤i≤t, 1≤j≤r. Then one can derive B=N·R.Proof.
By Lemmas13 and 14, we can obtain limm→∞Pm=0N·R0I. Theith row of N·R gives the probabilities of ending up in each of the absorbing states, given that the chain started in theith transient states. Hence, we can derive B=N·R, and the theorem holds.To simplify the presentation, we use the attack graph in Figure1 as an example. We manually assign Δ(e1,2)=3/4,Δ(e1,3)=3/4,Δ(e2,1)=1/2,Δ(e2,4)=1/4, and then we can obtain the corresponding state transition matrixP using Algorithm 1. Additionally, combined with (3), we can constructQ andR and further calculate the matrixB as follows:(9)
P
=
S
1
S
2
S
3
S
4
S
1
1
2
S
2
1
2
S
3
S
4
0
1
2
1
2
0
2
3
0
0
1
3
0
0
1
0
0
0
0
1
,
Q
=
S
1
S
2
S
1
S
2
0
1
2
2
3
0
,
R
=
S
3
S
4
S
1
S
2
1
2
0
0
1
3
,
B
=
I
-
Q
-
1
·
R
=
S
3
S
4
S
1
S
2
3
4
1
4
1
2
1
2
.From the first row ofB, if the attacker started at S1, the EAIPs of S3 and S4 are 3/4 and 1/4 respectively. Since the EAIP of S3 is higher, the most likely attack intention is S3 and the rank of intentions is ProbRank=S3>S4. By the second row ofB, if the initial attack state is S2, it is observed that the reachable probabilities of S3 and S4 are equal to 1/2. Moreover, for the above two examples, we can see that the attacker will finally reach the absorbing state nodes with the definite probability 1 regardless of its initial state.


## 5.2. Evaluation of EAPL

Theorem 16.
Given at×1 matrixT, where the entry Ti denotes the EAPL the attacker needs to take from the initial state node Si to the intention state, 1≤i≤t, letC be a t×1 unit vector, and then one has T=N·C.Proof.
According to Lemma14, for attacker starting from the initial node Si, the visits to S1,S2,…,St before absorption are Ni,1,Ni,2,…,Ni,t, respectively. As a result, the EAPL of Si is Ti=Ni,1+Ni,2+…+Ni,t (equals to the sum of visits to the appearing nodes in the path). Hence, we can derive T=Ti=Ni,1+Ni,2+…+Ni,t=N·C and that Theorem 16 holds.Going on with the example in Section5.1, we can derive that(10)T=N·C=3234132·11=S1S29452.Obviously, EAPLs ofS1 andS2 are 9/4 and 5/2, respectively. Assume that the time-cost for each step attack is equal; then the penetration starting from S1 is quicker than that from S2. Therefore, the crucial degree ofS1 is higher, and the mitigation priorities of the nodes are LengRank=S1>S2.


## 5.3. Algorithm Complexity Analysis

For the above-mentioned two algorithms, the space and time complexity are as follows:(1)
The algorithms need to maintainn×n matrixP, t×t matrixQ, t×t matrixN, t×r matrixB, t×1 matrixC, and t×1 matrixT. Since n=r+t, the space complexity is O(n2).(2)
The operations of the algorithm include matrix inversion, matrix addition, and matrix multiplication. Among them, the time complexity of matrix multiplication is the highest. When twon×n matrices are multiplied, there are 2n3 fundamental operations, so the time complexity is O(n3).To sum up, the proposed algorithms achieve polynomial complexity.


## 6. Experiments and Analyses

The Defcon’s Capture the Flag (CTF) contest is the largest open computer security hacking game in the world. The game is adversarial, with multiple potentially competing intentions. As demonstrated in [22], since all players are skilled in attack and defense, the attacking process is of great significance for intrusion analysis. The CTF23 dataset [23] released recently, in 2015, contains a large number of attack scenarios. The classical DARPA2000 dataset [24] by the MIT Lincoln laboratory is the standard test set for DDoS attack scenarios.In this section, deep performances are presented based on the above two datasets by using our metrics.


### 6.1. CTF 23

Defcon is the largest Internet security community in the world. Defcon provides a “Capture the Flag” (CTF) contest, which is a contest of computer security attack and defense skills, as shown in Figure2. CTF attracts several expert intruders with a legal opportunity to deliver their skills in a public forum. Each team has to defend its own flag, while trying to corrupt as many of the other teams’ flags as possible. A flag is a data file on the team’s server.Figure 2
Defcon’s Capture the Flag contest network.During the game, intruders seek to replace the flag on someone else’s server with their own flag, while defenders try to preserve their flags on their own server. Defcon has recently published the archive of CTF23, which includes all the traffic generation during the game. The size of CTF23 is more than hundreds of GB. There are many attackers starting from different initial states with different attack intentions in attack scenarios.Firstly, we use TCPReplay tool [25] to replay the CTF23 dataset and detect the alert data by Snort. By extracting the alert sequences using the analyzer ArcSight [26], we reconstruct more than 80 different attack scenarios. Among them, the minimum attack scenario only has 3 nodes, and the maximum attack scenario has no more than 20 nodes. Then we select a familiar attack scenario depicted in Figure 3 as our test scenario. Although the attack process is simple, it helps to analyze the impact of single attack step over the whole network.Figure 3
A simple attack scenarios extracted from CTF23.The set of transient states isO=S1,S2 and the set of the intention states is G=S3,S4. Assume that the attacker’s initial state isS1, and his intention isS4; one possible attack path is S1→S2→S4. The description of this path is as follows: The intruder (IP: 10.31.10.8) breaks into the server with IP address 10.31.1.2 using remote code execution vulnerability and gets its user privilege. After launching a brute-force attack to log in the MySQL server, the attacker can obtain the root privilege finally.To simplify the discussion, we give some enumerations and summarize the relationships between attack path and edge probabilities. Suppose that the success probabilities of “remote code execution” and “Rothenburg-based attack” are the same and equal toV1, the success probabilities of “SQL Injection” and “brute-force” are equal to V2, where V1,V2∈(0,1]. We first construct the state transition matrixP using Algorithm 1. Afterwards, the EAIP matrixB and EAPL matrixT can be calculated using Algorithms 2 and 3, respectively, as follows:(11)P=0V1V1+V2V2V1+V20V1V1+V200V2V1+V200100001,B=S1S2V1+V22V1+V2V12V1+V2V12V1+V2V1+V22V1+V2,T=S1S21+V1V21+V1V2.Algorithm 2:Pseudocode for EAIP evaluation algorithm.
INPUT: AG=(S,E,A,Δ) OUTPUT: Matrix B, ProbRank BEGIN ( 1 ) Use Algorithm1 to construct the matrix P. ( 2 ) Construct t×t matrix Q, t×r matrix R from matrix P according to Definition 11 ( 3 ) Calculate t×r matrix B=(I-Q)-1⋅R ( 4 ) FOR i = 1 to r​ ( 5 ) Rank Bi,1,Bi,2,…,Bi,r in descending order and record as ProbRank ​ ( 6 ) Return B and ProbRank ENDAlgorithm 3:Pseudocode for EAPL evaluation algorithm.
INPUT: A G = ( S , A , E , Δ ) OUTPUT: Matrix T, LengRank BEGIN ( 1 ) Use Algorithm1 to construct the matrix P ( 2 ) Construct t×t matrix Q, t×rmatrix R from P by Definition 11 ( 3 ) Construct t×1 matrix C=[1,1,…,1]T ( 4 ) Calculate t×1 matrix T=(I-Q)-1⋅C ( 5 ) FOR i = 1 to t​ ( 6 ) Rank T1,T2,…,Tt in in descending order and record as LengRank ​ ( 7 ) Return T and LengRank END


#### 6.1.1. Evaluation of EAIP

From the first row vector of matrixB, we can obtain that if the initial states is S1, the EAIPs of S3 and S4 are B1,1=V1+V2/2V1+V2 and B1,2=V1/2V1+V2, respectively. Some enumerations of EAIP calculation are organized in Table 2. The corresponding 3D figure ofV1,V2, and EAIP is illustrated in Figure 4. The EAIP ofS3 is higher than 0.5, and the EAIP ofS4 is lower than 0.5. Hence, the attacker is more likely to compromise the nodeS3. We can identify that the possible attack intention isS3. Meantime, the intentions rank is ProbRank=S3>S4. It means that the first suggested vulnerability to patch is SQL Injection Vulnerability on the server 10.5.7.2. Moreover, we can observe that the value of EAIP(S3)-EAIP(S4) increases as the parameter V2/V1 increases.Table 2
Enumerations of EAIPs in Figure3.
V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) 0.2 0.2 0.67 0.33 0.4 0.2 0.6 0.4 0.2 0.4 0.75 0.25 0.4 0.4 0.67 0.33 0.2 0.6 0.8 0.2 0.4 0.6 0.71 0.29 0.2 0.8 0.83 0.17 0.4 0.8 0.75 0.25 0.2 1 0.86 0.14 0.4 1 0.78 0.22 … … … … … … … …  V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) V 1 V 2 EAIP(S 3 ) EAIP(S 4 )  0.6 0.2 0.57 0.43 0.8 0.2 0.56 0.44 0.6 0.4 0.63 0.37 0.8 0.4 0.6 0.4 0.6 0.6 0.67 0.33 0.8 0.6 0.64 0.36 0.6 0.8 0.7 0.3 0.8 0.8 0.67 0.33 0.6 1 0.73 0.27 0.8 1 0.69 0.31 … … … … … … … …Figure 4
Distribution of EAIPs in Figure3.Affected by the attacker’s own characteristics (e.g., knowledge level, professional skills, and attack experience), a different attacker has a different success probability on the vulnerability. In practical application, the probability can be estimated by the attacker’s historical security events. Afterwards, the EAIPs of different intentions can be calculated using Algorithm1. The security engineer can take precautions for the preferred attack intention nodes.


#### 6.1.2. Evaluation of EAPL

From the matrixT, we observe that the EAPLs ofS1 andS2 are both 1+V1/V2. Therefore, the security rank of the transient nodes is LengRank=S1=S2.Some enumerations of EAPL are listed in Table3. The 3D figure of EAPL is illustrated in Figure 5. There is a relatively big difference of EAPL with differentV1 andV2. For example, from Table 3, when V1=0.8,V2=0.2, EAPL=5. On the contrary, when V1=0.2,V2=0.8, EAPL=1.25. Therefore, the probabilities ofV1 andV2 have significant impact on the number of steps the attacker needs to reach his intention. Meanwhile, from the formula of 1+V1/V2, the value of EAPL increases as V1/V2 increases. And the minimum EAPL=1 when V1=0. In particular, we can obtain EAPL=2 when V1=V2, indicating that the attacker should perform an average of two atomic attacks to achieve his intention.Table 3
Enumerations of EAPLs in Figure3.
V 1 V 2 EAPL V 1 V 2 EAPL 0.2 0.2 2 0.4 0.2 3 0.2 0.4 1.5 0.4 0.4 2 0.2 0.6 1.33 0.4 0.6 1.67 0.2 0.8 1.25 0.4 0.8 1.5 0.2 1 1.2 0.4 1 1.4 … … … … … …  V 1 V 2 EAPL V 1 V 2 EAPL  0.6 0.2 4 0.8 0.2 5 0.6 0.4 2.5 0.8 0.4 3 0.6 0.6 2 0.8 0.6 2.33 0.6 0.8 1.75 0.8 0.8 2 0.6 1 1.6 0.8 1 1.8 … … … … … …Figure 5
Distribution of EAPLs in Figure3.One can make use of EAPL to quantify the average number of atomic attacks for the attacker to achieve his intention. During the application, by analyzing the ongoing attack events, the security manager can locate the current state of the attacker. Through calculating the EAIPs of the attacker’s different intentions, one can also identify the attacker’s preferred target. This information is valuable for a security engineer to prioritize which intention node needs to be patched first and how it will affect the strength of the network against attacks.


### 6.2. DARPA 2000

The DARPA 2000 is a classical dataset for DDoS attack analysis, which is a commonly acknowledged. Similarly, we first use the TCPReplay tool to replay DARPA2000 dataset. Then with the automatic AG generation tool, we constructed the attack scenario graph of LLDOS1.0 in Figure6. For the edge probabilities, we borrow the results in [7], where(12)e2,5=0.15,e2,3=0.28,e3,5=0.1,e1,2=0.29,e2,2=0.2e2,4=0.28,e4,2=0.18,e4,3=0.42,e4,5=0.15,e5,5=1e1,4=0.33,e4,4=0.18.Figure 6
LLDOS1.0 attack scenario.Firstly, we use Algorithm1 to generate the state transition matrixP of AMC and then perform Algorithms 2 and 3 to calculate the matricesB andT as follows:(13)
P
=
47
S
1
S
2
47
S
3
87
S
4
53
S
5
47
S
1
S
2
S
3
S
4
S
5
0
0.47
0
0.53
0
0
0.22
0.31
0.31
0.16
0
0
0.87
0
0.13
0
0.19
0.45
0.19
0.17
0
0
0
0
1
,
B
=
S
1
S
2
S
3
S
4
1
1
1
1
,
T
=
S
1
S
2
S
3
S
4
8.198
7.200
7.692
7.197
.In this above scenario, the transient state set isO=S1,S2,S3,S4 and the absorbing state set is G=S5.According to the matrixB, the attacker will definitively reach the intention nodeS5 with the probability 1 regardless of initial state. By the matrixT, we can derive that, for different initial state nodesS1,S2,S3, andS4, the calculated EAPLs toS5 are 8.198, 7.200, 7.692, and 7.197, respectively. Hence, the security rank of the middle nodes in the attack path is LengRank=S1>S3>S2>S4.The security metrics under ideal and realistic scenarios in Figure6 are presented in Table 4. Some conclusions can be summarized as follows:(i)
For the ideal scenario, each node appears exactly once in any attack path, and the attacker never has to backtrack during the network penetration, Therefore, there is no circles in ideal path, and the number of total paths is 8. Among them, the shortest paths areS1→S2→S5 and S1→S4→S5 with length 2. The mode of path lengths is 3, and the median of path lengths is 3. The mean path length is 3. The ideal success probability ofS5 is 0.14, which is the cumulative probabilities of all the paths under the “monotonicity” assumption, which indicates that each step of the attack launched in the path is indeed successful.(ii)
For the realistic scenario, even a failed action of state transition is still handled as an occurrence of the atomic attack. Since the number of atomic attacks is not limited in actual practice, the occurrence probability ofS5 is 1, which is bigger than that of 0.14 in the ideal attack scenario. Moreover, the maximum EAPL is 8.2 when the attacker’s initial state is S1, and the minimum EAPL is 7.197 when the attacker’s initial state is S4. The maximum 8.2 indicates that the attacker needs to launch an average of 8.2 atomic attacks to breach his intention. However, in the ideal attack scenario, the result is 3 since the repeated nodes appearing in the path are excluded.Table 4
Structural measurements of LLDOS1.0 attack scenario in Figure6.
Types Measurement Value Ideal attack scenario Shortest path length 2 Median of path lengths 3 Mean path length 3 Number of paths 8 Mode of path lengths 3 Success probability of intention 0.14  Realistic attack scenario EAIP of intentionS5 1 Maximum EAPL 8.198 Minimum EAPL 7.197


### 6.3. Comparisons and Discussions

The detailed comparisons of security metrics among ours and other related methods are summarized in Table5. The security parameters under the ideal and realistic attack scenarios are fully analyzed. As explained in paragraph 3 of Section 1, the metrics under the ideal attack scenario is limited by the “monotonicity” assumption of attackers. Therefore, new insights into EAIP and EAPL in the cyclic graph under realistic attack scenario are provided for the first time in this paper. The major merits are as follows:(i)
For the ideal attack scenario, the common metrics involve the most likely attack path [17–19], success probability of intention [10, 16, 18, 19], and the number of attack paths [16–19], which are investigated in the acyclic graph. Furthermore, [18, 19] further analyzed the mean, median, and mode of path lengths. All these metrics do not take into account the circles and instead assume that each node appears exactly once in any attack path.(ii)
For the realistic attack scenario, two new insights into security metrics are given by using AMC to handle the circles in the cyclic graph. First, we investigate the EAIPs of different intentions, which helps to identify the most possible attack target and determine the priorities of critical destination hosts. Second, by locating the current state of the attacker, we can calculate EAPL. The measurement of EAPL enables the administrator to comprehend a reliability number of attack steps that the attacker needs to complete his goal and make the appropriate protection decisions.Table 5
Comparisons of security metrics among our method and others.
Types Ref. [10] Ref. [16] Ref. [17] Ref. [18] Ref. [19] Ours Most likely attack path   ✓ ✓ ✓ ✓ Cumulative success probability of intention ✓ ✓  ✓ ✓ ✓ Number of attack paths  ✓ ✓ ✓ ✓ ✓ Mean of path lengths    ✓ ✓ ✓ Median of path lengths    ✓ ✓ ✓ Mode of path lengths    ✓ ✓ ✓ EAIP of intention      ✓ EAPL of breaching intention      ✓To conclude, our new insights provide more accurate and reliable quantification into the security metrics of multistep attacks.


## 6.1. CTF 23

Defcon is the largest Internet security community in the world. Defcon provides a “Capture the Flag” (CTF) contest, which is a contest of computer security attack and defense skills, as shown in Figure2. CTF attracts several expert intruders with a legal opportunity to deliver their skills in a public forum. Each team has to defend its own flag, while trying to corrupt as many of the other teams’ flags as possible. A flag is a data file on the team’s server.Figure 2
Defcon’s Capture the Flag contest network.During the game, intruders seek to replace the flag on someone else’s server with their own flag, while defenders try to preserve their flags on their own server. Defcon has recently published the archive of CTF23, which includes all the traffic generation during the game. The size of CTF23 is more than hundreds of GB. There are many attackers starting from different initial states with different attack intentions in attack scenarios.Firstly, we use TCPReplay tool [25] to replay the CTF23 dataset and detect the alert data by Snort. By extracting the alert sequences using the analyzer ArcSight [26], we reconstruct more than 80 different attack scenarios. Among them, the minimum attack scenario only has 3 nodes, and the maximum attack scenario has no more than 20 nodes. Then we select a familiar attack scenario depicted in Figure 3 as our test scenario. Although the attack process is simple, it helps to analyze the impact of single attack step over the whole network.Figure 3
A simple attack scenarios extracted from CTF23.The set of transient states isO=S1,S2 and the set of the intention states is G=S3,S4. Assume that the attacker’s initial state isS1, and his intention isS4; one possible attack path is S1→S2→S4. The description of this path is as follows: The intruder (IP: 10.31.10.8) breaks into the server with IP address 10.31.1.2 using remote code execution vulnerability and gets its user privilege. After launching a brute-force attack to log in the MySQL server, the attacker can obtain the root privilege finally.To simplify the discussion, we give some enumerations and summarize the relationships between attack path and edge probabilities. Suppose that the success probabilities of “remote code execution” and “Rothenburg-based attack” are the same and equal toV1, the success probabilities of “SQL Injection” and “brute-force” are equal to V2, where V1,V2∈(0,1]. We first construct the state transition matrixP using Algorithm 1. Afterwards, the EAIP matrixB and EAPL matrixT can be calculated using Algorithms 2 and 3, respectively, as follows:(11)P=0V1V1+V2V2V1+V20V1V1+V200V2V1+V200100001,B=S1S2V1+V22V1+V2V12V1+V2V12V1+V2V1+V22V1+V2,T=S1S21+V1V21+V1V2.Algorithm 2:Pseudocode for EAIP evaluation algorithm.
INPUT: AG=(S,E,A,Δ) OUTPUT: Matrix B, ProbRank BEGIN ( 1 ) Use Algorithm1 to construct the matrix P. ( 2 ) Construct t×t matrix Q, t×r matrix R from matrix P according to Definition 11 ( 3 ) Calculate t×r matrix B=(I-Q)-1⋅R ( 4 ) FOR i = 1 to r​ ( 5 ) Rank Bi,1,Bi,2,…,Bi,r in descending order and record as ProbRank ​ ( 6 ) Return B and ProbRank ENDAlgorithm 3:Pseudocode for EAPL evaluation algorithm.
INPUT: A G = ( S , A , E , Δ ) OUTPUT: Matrix T, LengRank BEGIN ( 1 ) Use Algorithm1 to construct the matrix P ( 2 ) Construct t×t matrix Q, t×rmatrix R from P by Definition 11 ( 3 ) Construct t×1 matrix C=[1,1,…,1]T ( 4 ) Calculate t×1 matrix T=(I-Q)-1⋅C ( 5 ) FOR i = 1 to t​ ( 6 ) Rank T1,T2,…,Tt in in descending order and record as LengRank ​ ( 7 ) Return T and LengRank END


### 6.1.1. Evaluation of EAIP

From the first row vector of matrixB, we can obtain that if the initial states is S1, the EAIPs of S3 and S4 are B1,1=V1+V2/2V1+V2 and B1,2=V1/2V1+V2, respectively. Some enumerations of EAIP calculation are organized in Table 2. The corresponding 3D figure ofV1,V2, and EAIP is illustrated in Figure 4. The EAIP ofS3 is higher than 0.5, and the EAIP ofS4 is lower than 0.5. Hence, the attacker is more likely to compromise the nodeS3. We can identify that the possible attack intention isS3. Meantime, the intentions rank is ProbRank=S3>S4. It means that the first suggested vulnerability to patch is SQL Injection Vulnerability on the server 10.5.7.2. Moreover, we can observe that the value of EAIP(S3)-EAIP(S4) increases as the parameter V2/V1 increases.Table 2
Enumerations of EAIPs in Figure3.
V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) 0.2 0.2 0.67 0.33 0.4 0.2 0.6 0.4 0.2 0.4 0.75 0.25 0.4 0.4 0.67 0.33 0.2 0.6 0.8 0.2 0.4 0.6 0.71 0.29 0.2 0.8 0.83 0.17 0.4 0.8 0.75 0.25 0.2 1 0.86 0.14 0.4 1 0.78 0.22 … … … … … … … …  V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) V 1 V 2 EAIP(S 3 ) EAIP(S 4 )  0.6 0.2 0.57 0.43 0.8 0.2 0.56 0.44 0.6 0.4 0.63 0.37 0.8 0.4 0.6 0.4 0.6 0.6 0.67 0.33 0.8 0.6 0.64 0.36 0.6 0.8 0.7 0.3 0.8 0.8 0.67 0.33 0.6 1 0.73 0.27 0.8 1 0.69 0.31 … … … … … … … …Figure 4
Distribution of EAIPs in Figure3.Affected by the attacker’s own characteristics (e.g., knowledge level, professional skills, and attack experience), a different attacker has a different success probability on the vulnerability. In practical application, the probability can be estimated by the attacker’s historical security events. Afterwards, the EAIPs of different intentions can be calculated using Algorithm1. The security engineer can take precautions for the preferred attack intention nodes.


### 6.1.2. Evaluation of EAPL

From the matrixT, we observe that the EAPLs ofS1 andS2 are both 1+V1/V2. Therefore, the security rank of the transient nodes is LengRank=S1=S2.Some enumerations of EAPL are listed in Table3. The 3D figure of EAPL is illustrated in Figure 5. There is a relatively big difference of EAPL with differentV1 andV2. For example, from Table 3, when V1=0.8,V2=0.2, EAPL=5. On the contrary, when V1=0.2,V2=0.8, EAPL=1.25. Therefore, the probabilities ofV1 andV2 have significant impact on the number of steps the attacker needs to reach his intention. Meanwhile, from the formula of 1+V1/V2, the value of EAPL increases as V1/V2 increases. And the minimum EAPL=1 when V1=0. In particular, we can obtain EAPL=2 when V1=V2, indicating that the attacker should perform an average of two atomic attacks to achieve his intention.Table 3
Enumerations of EAPLs in Figure3.
V 1 V 2 EAPL V 1 V 2 EAPL 0.2 0.2 2 0.4 0.2 3 0.2 0.4 1.5 0.4 0.4 2 0.2 0.6 1.33 0.4 0.6 1.67 0.2 0.8 1.25 0.4 0.8 1.5 0.2 1 1.2 0.4 1 1.4 … … … … … …  V 1 V 2 EAPL V 1 V 2 EAPL  0.6 0.2 4 0.8 0.2 5 0.6 0.4 2.5 0.8 0.4 3 0.6 0.6 2 0.8 0.6 2.33 0.6 0.8 1.75 0.8 0.8 2 0.6 1 1.6 0.8 1 1.8 … … … … … …Figure 5
Distribution of EAPLs in Figure3.One can make use of EAPL to quantify the average number of atomic attacks for the attacker to achieve his intention. During the application, by analyzing the ongoing attack events, the security manager can locate the current state of the attacker. Through calculating the EAIPs of the attacker’s different intentions, one can also identify the attacker’s preferred target. This information is valuable for a security engineer to prioritize which intention node needs to be patched first and how it will affect the strength of the network against attacks.


## 6.1.1. Evaluation of EAIP

From the first row vector of matrixB, we can obtain that if the initial states is S1, the EAIPs of S3 and S4 are B1,1=V1+V2/2V1+V2 and B1,2=V1/2V1+V2, respectively. Some enumerations of EAIP calculation are organized in Table 2. The corresponding 3D figure ofV1,V2, and EAIP is illustrated in Figure 4. The EAIP ofS3 is higher than 0.5, and the EAIP ofS4 is lower than 0.5. Hence, the attacker is more likely to compromise the nodeS3. We can identify that the possible attack intention isS3. Meantime, the intentions rank is ProbRank=S3>S4. It means that the first suggested vulnerability to patch is SQL Injection Vulnerability on the server 10.5.7.2. Moreover, we can observe that the value of EAIP(S3)-EAIP(S4) increases as the parameter V2/V1 increases.Table 2
Enumerations of EAIPs in Figure3.
V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) 0.2 0.2 0.67 0.33 0.4 0.2 0.6 0.4 0.2 0.4 0.75 0.25 0.4 0.4 0.67 0.33 0.2 0.6 0.8 0.2 0.4 0.6 0.71 0.29 0.2 0.8 0.83 0.17 0.4 0.8 0.75 0.25 0.2 1 0.86 0.14 0.4 1 0.78 0.22 … … … … … … … …  V 1 V 2 EAIP(S 3 ) EAIP(S 4 ) V 1 V 2 EAIP(S 3 ) EAIP(S 4 )  0.6 0.2 0.57 0.43 0.8 0.2 0.56 0.44 0.6 0.4 0.63 0.37 0.8 0.4 0.6 0.4 0.6 0.6 0.67 0.33 0.8 0.6 0.64 0.36 0.6 0.8 0.7 0.3 0.8 0.8 0.67 0.33 0.6 1 0.73 0.27 0.8 1 0.69 0.31 … … … … … … … …Figure 4
Distribution of EAIPs in Figure3.Affected by the attacker’s own characteristics (e.g., knowledge level, professional skills, and attack experience), a different attacker has a different success probability on the vulnerability. In practical application, the probability can be estimated by the attacker’s historical security events. Afterwards, the EAIPs of different intentions can be calculated using Algorithm1. The security engineer can take precautions for the preferred attack intention nodes.


## 6.1.2. Evaluation of EAPL

From the matrixT, we observe that the EAPLs ofS1 andS2 are both 1+V1/V2. Therefore, the security rank of the transient nodes is LengRank=S1=S2.Some enumerations of EAPL are listed in Table3. The 3D figure of EAPL is illustrated in Figure 5. There is a relatively big difference of EAPL with differentV1 andV2. For example, from Table 3, when V1=0.8,V2=0.2, EAPL=5. On the contrary, when V1=0.2,V2=0.8, EAPL=1.25. Therefore, the probabilities ofV1 andV2 have significant impact on the number of steps the attacker needs to reach his intention. Meanwhile, from the formula of 1+V1/V2, the value of EAPL increases as V1/V2 increases. And the minimum EAPL=1 when V1=0. In particular, we can obtain EAPL=2 when V1=V2, indicating that the attacker should perform an average of two atomic attacks to achieve his intention.Table 3
Enumerations of EAPLs in Figure3.
V 1 V 2 EAPL V 1 V 2 EAPL 0.2 0.2 2 0.4 0.2 3 0.2 0.4 1.5 0.4 0.4 2 0.2 0.6 1.33 0.4 0.6 1.67 0.2 0.8 1.25 0.4 0.8 1.5 0.2 1 1.2 0.4 1 1.4 … … … … … …  V 1 V 2 EAPL V 1 V 2 EAPL  0.6 0.2 4 0.8 0.2 5 0.6 0.4 2.5 0.8 0.4 3 0.6 0.6 2 0.8 0.6 2.33 0.6 0.8 1.75 0.8 0.8 2 0.6 1 1.6 0.8 1 1.8 … … … … … …Figure 5
Distribution of EAPLs in Figure3.One can make use of EAPL to quantify the average number of atomic attacks for the attacker to achieve his intention. During the application, by analyzing the ongoing attack events, the security manager can locate the current state of the attacker. Through calculating the EAIPs of the attacker’s different intentions, one can also identify the attacker’s preferred target. This information is valuable for a security engineer to prioritize which intention node needs to be patched first and how it will affect the strength of the network against attacks.


## 6.2. DARPA 2000

The DARPA 2000 is a classical dataset for DDoS attack analysis, which is a commonly acknowledged. Similarly, we first use the TCPReplay tool to replay DARPA2000 dataset. Then with the automatic AG generation tool, we constructed the attack scenario graph of LLDOS1.0 in Figure6. For the edge probabilities, we borrow the results in [7], where(12)e2,5=0.15,e2,3=0.28,e3,5=0.1,e1,2=0.29,e2,2=0.2e2,4=0.28,e4,2=0.18,e4,3=0.42,e4,5=0.15,e5,5=1e1,4=0.33,e4,4=0.18.Figure 6
LLDOS1.0 attack scenario.Firstly, we use Algorithm1 to generate the state transition matrixP of AMC and then perform Algorithms 2 and 3 to calculate the matricesB andT as follows:(13)
P
=
47
S
1
S
2
47
S
3
87
S
4
53
S
5
47
S
1
S
2
S
3
S
4
S
5
0
0.47
0
0.53
0
0
0.22
0.31
0.31
0.16
0
0
0.87
0
0.13
0
0.19
0.45
0.19
0.17
0
0
0
0
1
,
B
=
S
1
S
2
S
3
S
4
1
1
1
1
,
T
=
S
1
S
2
S
3
S
4
8.198
7.200
7.692
7.197
.In this above scenario, the transient state set isO=S1,S2,S3,S4 and the absorbing state set is G=S5.According to the matrixB, the attacker will definitively reach the intention nodeS5 with the probability 1 regardless of initial state. By the matrixT, we can derive that, for different initial state nodesS1,S2,S3, andS4, the calculated EAPLs toS5 are 8.198, 7.200, 7.692, and 7.197, respectively. Hence, the security rank of the middle nodes in the attack path is LengRank=S1>S3>S2>S4.The security metrics under ideal and realistic scenarios in Figure6 are presented in Table 4. Some conclusions can be summarized as follows:(i)
For the ideal scenario, each node appears exactly once in any attack path, and the attacker never has to backtrack during the network penetration, Therefore, there is no circles in ideal path, and the number of total paths is 8. Among them, the shortest paths areS1→S2→S5 and S1→S4→S5 with length 2. The mode of path lengths is 3, and the median of path lengths is 3. The mean path length is 3. The ideal success probability ofS5 is 0.14, which is the cumulative probabilities of all the paths under the “monotonicity” assumption, which indicates that each step of the attack launched in the path is indeed successful.(ii)
For the realistic scenario, even a failed action of state transition is still handled as an occurrence of the atomic attack. Since the number of atomic attacks is not limited in actual practice, the occurrence probability ofS5 is 1, which is bigger than that of 0.14 in the ideal attack scenario. Moreover, the maximum EAPL is 8.2 when the attacker’s initial state is S1, and the minimum EAPL is 7.197 when the attacker’s initial state is S4. The maximum 8.2 indicates that the attacker needs to launch an average of 8.2 atomic attacks to breach his intention. However, in the ideal attack scenario, the result is 3 since the repeated nodes appearing in the path are excluded.Table 4
Structural measurements of LLDOS1.0 attack scenario in Figure6.
Types Measurement Value Ideal attack scenario Shortest path length 2 Median of path lengths 3 Mean path length 3 Number of paths 8 Mode of path lengths 3 Success probability of intention 0.14  Realistic attack scenario EAIP of intentionS5 1 Maximum EAPL 8.198 Minimum EAPL 7.197


## 6.3. Comparisons and Discussions

The detailed comparisons of security metrics among ours and other related methods are summarized in Table5. The security parameters under the ideal and realistic attack scenarios are fully analyzed. As explained in paragraph 3 of Section 1, the metrics under the ideal attack scenario is limited by the “monotonicity” assumption of attackers. Therefore, new insights into EAIP and EAPL in the cyclic graph under realistic attack scenario are provided for the first time in this paper. The major merits are as follows:(i)
For the ideal attack scenario, the common metrics involve the most likely attack path [17–19], success probability of intention [10, 16, 18, 19], and the number of attack paths [16–19], which are investigated in the acyclic graph. Furthermore, [18, 19] further analyzed the mean, median, and mode of path lengths. All these metrics do not take into account the circles and instead assume that each node appears exactly once in any attack path.(ii)
For the realistic attack scenario, two new insights into security metrics are given by using AMC to handle the circles in the cyclic graph. First, we investigate the EAIPs of different intentions, which helps to identify the most possible attack target and determine the priorities of critical destination hosts. Second, by locating the current state of the attacker, we can calculate EAPL. The measurement of EAPL enables the administrator to comprehend a reliability number of attack steps that the attacker needs to complete his goal and make the appropriate protection decisions.Table 5
Comparisons of security metrics among our method and others.
Types Ref. [10] Ref. [16] Ref. [17] Ref. [18] Ref. [19] Ours Most likely attack path   ✓ ✓ ✓ ✓ Cumulative success probability of intention ✓ ✓  ✓ ✓ ✓ Number of attack paths  ✓ ✓ ✓ ✓ ✓ Mean of path lengths    ✓ ✓ ✓ Median of path lengths    ✓ ✓ ✓ Mode of path lengths    ✓ ✓ ✓ EAIP of intention      ✓ EAPL of breaching intention      ✓To conclude, our new insights provide more accurate and reliable quantification into the security metrics of multistep attacks.


## 7. Conclusion and Future Work

Quantifying security with metrics is important since we want to have a scoring system to evaluate the strength of the security. Although many investigations have been made, they are more or less subjected to the attacker’s “monotonicity” assumption. To overcome the limitations, we employ a mathematical model AMC to handle the circles in AG and present the realistic metrics for calculating EAIP and EAPL. In addition, we aggregate existing approaches and give a suite of evaluation methods for both ideal and realistic attack scenario towards multistep attacks. Experiments verify the validity and accuracy of the proposed model and algorithms.Large-scale networks are mostly generated by integrating multiple small-scale local networks. Due to the scalability of security attacks, our metrics can be extended to the large-scale network systems. Trying to capture the large dataset of the enterprise to test the scalability of the proposed methodology is the future work. Meanwhile, the emphasis is on measuring the state transition probability based on the observed alerts from IDS, firewall, system logs, etc. so that we can improve the flexibility and applicability in a further step.



---

*Source: 4278632-2018-07-10.xml*