# Security Metric Methods for Network Multistep Attacks Using AMC and Big Data Correlation Analysis

Authors: Hao Hu; Yuling Liu; Hongqi Zhang; Yuchen Zhang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Network security metrics allow quantitatively evaluating the overall resilience of networked systems against attacks. From this aim, security metrics are of great importance to the security-related decision-making process of enterprises. In this paper, we employ absorbing Markov chain (AMC) to estimate the network security combining with the technique of big data correlation analysis. Specifically, we construct the model of AMC using a large amount of alert data to describe the scenario of multistep attacks in the real world. In addition, we implement big data correlation analysis to generate the transition probability matrix from alert stream, which defines the probabilities of transferring from one attack action to another according to a given scenario before reaching one of some attack targets. Based on the probability reasoning, two metric algorithms are designed to estimate the attack scenario as well as the attackers, namely, the expected number of visits (ENV) and the expected success probability (ESP). The superiority is that the proposed model and algorithms assist the administrator in building new scenarios, prioritizing alerts, and ranking them.


---

## Body

## 1. Introduction

Network security metrics deal with how to provide quantifiable evidence to assist security practitioners in securing computer networks, which have received significant attention in recent years [1–3]. The underlying vulnerabilities associated with services leave loopholes, thus allowing cyber intruders to exploit services and threatening the security and privacy of data [4, 5]. Various security schemes, such as encryption, authentication, access control, firewalls, intrusion detection system (IDS), and data leak prevention systems (DLPSs), address these security issues. However, no individual scheme fits all cases. For example, the intrusion detection system for securing network system aims to provide a layer of defense against malicious uses of computing systems by sensing attacks and alerting users. Conventional intrusion detection systems can only produce isolated alert events. However, most cyberattacks are not single attack actions nowadays. They are multistage, multihost attacks, which are composed of a series of attack actions, leading to the fact that the cybersecurity faces huge threats and challenges. For example, the notorious Zeus botnet contains five steps including probe, overflow attack, target host infection, virus propagation, and user information stealing. Due to the complexity of state transition in multistep attacks, the security metric is of great significance for the manager to comprehend the attack properties.With the expansion of the scale of the network, the number of distributed nodes in the network keeps increasing thus resulting in massive, multisource, and heterogeneous security alert data. Big data analysis is of great benefit to organizations, business, companies, and many large scale and small-scale industries. In order to analyze complex data and to identify patterns, by correlating the logical relationship within the huge amount of alert events, the attack scenarios are extracted, multistep attacks are recognized, the possible attack paths are identified, potential attack targets are predicted, and critical threat host nodes are discovered from the alert flow. The alert correlation analysis focuses on discovering the relationships between massive raised alerts, thereby improving the performance of network protection.This paper considers as input the large number of alerts generated by several IDS sensors, processes them across an alert correlation method based on the absorbing Markov chain (AMC), and extract two security metric algorithms with high precision, such as building new scenarios, prioritizing alerts and scenarios, and ranking them.We regard the contributions of this paper to be threefold; namely, we have the following:(i)
The alert correlation algorithm is proposed to deal with the real-time alert flow. It integrates the alerts according to the correlation between their IP addresses ensuring no information loss in the process of alert preprocessing and mining each independent attack scenario.(ii)
The AMC-based model is developed for attack description that enables adaptive and precise attack recognition, analysis, and prediction, which require no prior knowledge and training data set, as well as time linear complexity, correlation, and prediction of multistep attacks with precise transition probabilities.(iii)
Two novel metric algorithms are designed by using the AMC model to extract various security properties of the attack scenarios and the attackers including the estimated probability required to reach different attack target alerts, the estimated number of each alert during an attack, critical alerts, and priority of alerts.The remainder of this paper is organized as follows: Section2 gives an overview of some related works. Section 3 presents the working framework and schematic of our approach. Section 4 develops the model of AMC-based security metrics and gives the details of the construction of AMC by fusing real-world alert data. Section 5 shows how to unitize the AMC model to design the approaches of extracting relevant security properties. Section 6 gives the experiments, analyses, and comparisons as well as discussions. Finally, we conclude this paper in Section 7.


## 2. Related Works

The issue of security metrics has long attracted much attention. Recently, Pendleton et al. [1] designed a security metrics framework. Behi et al. [6] provided a structure for quantitation of network security and prioritization of significant security metrics. A practical method of extracting attack properties of attacker in an enterprise network is the vulnerability attack graph (VAG). The VAG represents possible ways in which a potential attacker can break into the given network by exploiting a series of vulnerabilities on various network hosts and gaining certain privileges at each step. VAG-based security metrics provide quantifiable evidences to assist security practitioners in securing computer networks, which has been a popular method.The present works of VAG-based security, the future challenges, and open issues were overviewed in [3]. Noel et al. [7] described a suite of metrics based on the model of VAG, including metrics of victimization, size, containment, and topology of the network. The probability theory is often combined with the VAG; Sheyner et al. [8] explained that the invader tends to select the easiest path to achieve the attack target. A suite of VAG-based security metrics such as the normalized mean of path lengths, median of path lengths, mode of path lengths, and standard deviation of path lengths was further aggregated by Idika et al. [9]. Similarly, the method for measuring the number of paths was demonstrated by Ortalo et al. [10], and the shortest path metric was analyzed in Phillips et al. [11]. Additionally, the measurement of average path length was introduced by Li et al. [12]. The success probability for a multistep attack is actually an aggregate calculation over the probabilities for each individual step in the path. From the viewpoint of time and probability, Zhu et al. [13] provided several metrics, including mean time to vulnerability, local risk rate, mean risk rate, and overall risk value. One may refer to the specific literatures for detailed surveys. To improve the performance of current metrics, Sarraute et al. [14] designed a modified version of Floyd–Warshall and Dijkstra algorithm to compute the shortest attack path. Moreover, Obes et al. [15] explored the advantageous attack paths for the given network, which aims to minimize time for an attacker to reach the target states. A VAG for predicting the expected path length of compromising the security target was proposed by Kaluarachchi et al. [16], where the attack graph was developed based on the relationship of vulnerability exploits. Hu et al. [17] further unitized the common vulnerability scoring system to calculate the expected number of atomic attacks needed to compromise the attack target. While the above reports made a significant development in security metric using VAG, the major limitation is that the VAG represents all the possible ways an invader can breach a security policy according to the network architecture of the enterprise network, which is complex and large with the increase of the scale of the network.To improve the flexibility and richness of metrics, Ghasemigol et al. [18] introduced a comprehensive approach that can predict future attacks with more precision and dynamically adapt to changes in the environment. Abraham et al. [19] analyzed that the occurrence probability of path length can change over time with respect to the age of vulnerabilities. Ghanshyam et al. [20] proposed graph distance metrics for assessing temporal changes in attack surface of dynamic networks, which can be used to identify most critical hosts in the network as per their locations. Pendleton et al. [1] made a survey focusing on the state-of-the-art existing metrics in terms of their advantages/disadvantages and they designed a security metric framework to measure system-level security by aggregating vulnerabilities, defense power, attack/threat severity, and situations. Patapanchala et al. [21] computed the cumulative probability that an attacker could succeed in gaining a specific privilege or carrying out an attack in the network by aggregating vulnerability metrics. Compared with the above methods, Fredj [22] developed an alert correlation graph to calculate the expected path length with improved practicality. Although many beneficial results have been achieved, they only give the calculations of expected number of steps required for the attacker to reach the attack target but not analyze which target is more vulnerable especially for sophisticated attack scenarios with multiple targets.As stated above, although a large number of security metrics approaches were reported, majority of them focus on the path metrics under the ideal attack scenario using VAG with assumption that all exploits are of equal strength and do not take into account the relative difficulty in exploiting the vulnerabilities. We recognize that the ideal attack path is often not the actually exploited path by the attacker. Moreover, the real relationship of exploits can be extracted from the alert stream detected by distributed IDSs. Consequently, models limited to ideal attack scenarios based on the VAG are less promising, which need to be modified and properly treated.To address this issue, we identify the attacker’s target from the huge amount of alert data through correlation analysis techniques. In contrast to the VAG, the alert correlation graph established based on AMC is used to describe the attack process. The AMC includes a finite node set V that forms the alerts detected by the security sensors. Firstly, the massive alert data is fused and correlated by clustering the IP address-related alert events. Then the correlated cluster of alerts is obtained. Secondly, based on the Markov property of AMC, the one-step transition probability matrix of different attack types produced by the alerts in each cluster is extracted. Thirdly, two metric algorithms for estimating expected number of visits (ENV) to each alert node and expected success probability (ESP) of alert target node are designed based on the proposed model. Finally, we test the performance of our method on a small-scale network. Our method solves the subjective shortcoming of manual setting of transition probabilities so that we can get the objective and reliable measurements.


## 3. Framework of Security Metric

The AMC is a special Markov chain, which has been widely applied in the analysis of economics rules. The basic idea is to model the attack process as the AMC from the real alert stream of IDS, VDS, Firewall, and other security devices. AMC ensures intuitive representation of correlated alerts. In addition, we employ AMC to implement security metrics. The workflow and schematic framework of security metric are depicted in Figure1, which contains two steps as follows.Figure 1
The main steps of the security metric framework.(i)
Construction of AMC (Section4): The absorbing Markov chain model is used to define the probabilities to transit from one attack action/type to another according to a given scenario before reaching one of some attack targets. It includes a finite node setS that forms the alerts that could be generated by the IDS sensors. (ii)
Security metrics of attack scenarios and attackers based on AMC (Section5): Generally, an intruder performs several actions in a well-predefined order called attack scenario. We give some theorems with respect to analyses of attack behaviors using probability theory. Then we design two metric algorithms to calculate the ENV and ESP as well as to present the relevant nodes ranking.


## 4. Model of AMC

The Markov and absorption properties of the state transition in AMC are in line with the randomness and accessibility characteristics of multistep attacks, respectively. Therefore, AMC can be used to describe the cyberattacks. At present, the format of the multisource heterogeneous alert data generated by different detection devices is quite different, the quantity and the amount of the data is huge, and the alert information is redundant. First, we must integrate the security data of IDSs, firewalls, VDSs, and other network devices to understand the alert data and standardize the data format. In this way, we can get more precise and reduce security event. Then the underlying attack scenario behind the alert flow is discovered. Finally, the attack scenario is modeled as a process for actions that transforms a system from one state to another, until reaching some targets that we call attack targets.


### 4.1. Alert Correlation Analysis

A key problem in mining attack scenarios directly from massive alert events is as follows. Since there may be several independent attack activities hidden in these alert events, this may cause confusions of attack scenarios if we directly associate these multisource alerts. Therefore, we must first accurately mine each independent attack activity and then separately measure the security property of each attack scenario.From this aim, we propose an alert clustering method based on the correlation of IP address. We format the multisource alert data detected by the different sensors and give the formal definition of alert event as follows.Definition 1.
Alert event is as an 7-tupleai=(timestamp,pluginID,pluginSID,srcIP,srcPort,desIP, desPort), where thetimestamp is the time when the sensor detects malicious features.pluginID is the number of source sensors generating the alert event.pluginSID is the classification information of the alert event in the corresponding sensor.srcIP andsrcPort are the source IP address and source port of the sensor producing alerts, respectively.desIP anddesPort are the destination IP address and destination port, respectively.
The attack type of the alert is determined by thepluginID andpluginSID together in Definition 1. Therefore, we use the variable type to indicate the type attribute of the alert.In general, alert events triggered by the same attack activity are always related to each other in the address distribution. For example, in a multistep attack, the target node of the former attack step may be the source node of the latter attack step. Based on this consideration, we use the correlation property of IP address. In detail, the alert events of the same attack activities are integrated together to provide an accurate data source for the construction of the absorbing Markov chain.The procedure of alert clustering based on IP address correlation is shown in Algorithm1. The cluster A1 in Figure 2 is a collection of alert sequences with IP addresses that are relevant. It is a set of alerts with the same source IP addresses or destination IP addresses in the original alert flow. ClusterSet is the collection composed of various clustersAi.Algorithm 1:Pseudocode for alert clustering based on the correlation of IP addresses.
Input: Real-time alert flow Output : The clusters of alerts with IP address correlated (1) WhileA is not empty (2)  a t e m p = A ⋅ first and drop A ⋅ first. (3) If  A0is not existing yet (4)  creat  A0  and add  atemp  toA0. (5)  else for  each  Ai  :  clusterSet (6)  if a t e m p  ⋅  IP  is in Ai⋅ IPset (7) add atemp to Ai. (8)  go  to  step (1). (9)  creat  An  and  add  atemp  to  An. (10)  EndFigure 2
Alerts clustering based on the correlation of IP addresses.The class clusters generated by the Algorithm1 are data sources for security metrics. Compared with the existing alert clustering method, the advantage of ours is that we do not adopt the concept of “similarity distance” with a strong subjectivity [22] but integrate the alerts according to the correlation analysis between their addresses, thus reflecting the address relevance of the attack. Meanwhile, there is no information loss in the process of alert preprocessing, which provides favorable conditions for accurately mining the hidden attack scenarios under the massive alerts.


### 4.2. Construction of AMC

The attack patterns of the attackers are hidden in the clusters generated by Algorithm1. This section investigates how to mine the hidden attack scenario based on these clusters. Since absorbing Markov chain can effectively model the randomness of development of discrete events, we use it to describe the attack process. We first overview some of the terminologies associated with AMC so that the reader can understand easily.Definition 2.
A Markov chain [23] is a collection of discrete random sequences denoted as S=s1,s2,…,sn, which contains a finite number of states. The sequence is a Markov chain if the following condition is satisfied. The formula indicates that the probability to go from a state to another only depends on the current state but is not related to the previous states.(1)psi+1∣si,si-1,…,s1=psi+1∣si.Definition 3.
An absorbing state is the destination state of the attacker, where the security is breached. The absorbing state nodea only has in-going edges but does not have out-going edges. Formally, a∈S∣∃ua∈E∧!∃aw∈E.Definition 4.
A transient state is the intermediate state of the attacker. The transient state nodeb has at least one out-going edge. Formally, {b∈S∣∃bw∈E}.Definition 5.
An absorbing Markov chain [23] is a special Markov chain containing at least one absorbing state. The associated state transition matrixP has the following canonical form.(2)
P
=
Q
R
0
I
,
0
≤
p
i
,
j
≤
1
,
∑
j
=
1
n
p
i
,
j
=
1
,
∀
1
≤
i
≤
nwhereQ is a nonzero (n-r)×(n-r) matrix denoting the transition probabilities between transient states.0 is r×(n-r) zero matrix.R is (n-r)×r matrix denoting the probabilities of transitions from the absorbing states to transient states.I is an r×r identity matrix denoting the transition probabilities between absorbing states. Besides,r is the number of absorbing states, n-r is the number of transient states, andn is the number of total states. The AMC requires that the sum of all transition probabilities of a given state must be equal to 1.We first present our design motivation using the example scenario in Figure3. The aim of alert correlation is to extract the one-step transition probability matrix of attack steps hidden in the alert flow. The identification of the node corresponds to the alert ID, which also represents a kind ofattack type caused by alert. The node reflects the attack step taken by the attacker. The weight of the edge corresponds to the frequency of repetition of the transition from an alert to another. Given an edge (i,j), the probability p(i,j) is the likelihood that the alertj will be raised given that the current raised alert isi. The transition probability between states represents the conditional probability that the attacker moves from the current attack type to the next attack type.Figure 3
The absorbing Markov chain representation of the attack scenario by alert correlation.Since our abstraction of attack scenario is developed based on the Markov property, which indicates that the next attack step is only related to the current attack step, therefore, the next step the attacker takes under the current attack step is independent of the attack path occurring before. This is also consistent with the reality. When the attacker reaches a valid state, he begins to consider what to do next based on the current state. In other words, only the current state will affect the attacker’s decision and the history states will not affect it.The AMC in Figure3 can also be expressed using a transition probability matrix as follows. The element in the matrix indicates the transition probability from the corresponding row’s attack type to the corresponding column’s attack type. We use AMC to describe the attack process. The element pij in the matrix represents the conditional probability p(j∣i) from the present attack typei to the future attack typej. The semantics of transition probability in the perspective of alert correlation is the probability of attacker from the current attack stepito the next attack stepj. (3)
P
=
A
t
t
a
c
k
T
y
p
e
1
.
2
2
.
7
3
.
6
4
.
5
5
.
5
1
2
3
4
5
0.2
0.7
0
0
0.1
0
0
0.6
0.4
0
0
0
0
0.5
0.5
0
0
0
1
0
0
0
0
0
1We analyze each class cluster of alerts produced by Algorithm1 and mine the hidden the corresponding one-step transition probability matrix using Algorithm 2.Algorithm 2:Pseudocode for mining the transition probability matrix from alerts.
Input : Class cluster with IP address correlation Output : One - step transition probability matrix of cluster (1)  For  each  ai:A (2)  If k = = 0 (3)  i = a k ⋅ type andj=ak+1⋅ type. (4)  add i and j to the set of alert types V. (5)  creat P according to V. (6)  p k j++ (7)  else (8)  i = a k ⋅ type andj=ak+1⋅ type. (9)  If a k + 1 ⋅ type is not included in V (10)  add a k + 1 ⋅ type to V. (11)  add row and column of a k + 1 ⋅ type to P. (12)  p i j++ (13)  else (14)  p i j++ (15)  End (16)  For  i=0,1,⋯,size (17)  where size is the number of P ’s row or column (18)  For j = 0,1 , ⋯ , s i z e (19)  p i j = p i j / s u m. (20)  where sum is the summation of row i (21)  End (22)  EndIn the process of traversing each alert in the class cluster by Algorithm2, if a new attack type is detected, a new row and column are added for the attack type in the transition probability matrixP, as shown in lines (9)-(12). This ensures that all types of attack are included inP shown in lines (1)-(15) The concept of proximity is used when mining associations between attack types. If the alert ai and alert ai+1 appear in turn, the appearance of attack type ai+1·type is only related to ai·type according to the Markov property. Then we add 1 to the count of ai·type to ai+1·type, which is the pij++ in line (6) of Algorithm 2. For instance, if we consider the weight of edge <AttackType_1,AttackType_2> is 2 this means that the intruder has caused the generation of the alert withAttack Type_1 and then another withAttack Type_2 two times.We normalize the transition probability matrix obtained after abstraction to meet the requirements of the Markov chain model. According to Definition1, the sum of all transition probabilities of a given state must be equal to 1. It is reflected that the sum of every row of the matrixP must be equal to 1. Thus, we convert the frequency of transitions between attack types into transition probabilities in lines (16)-(21). In other words, we assign the weight of the edge based on the number of frequencies of the transition from an alert to another. For each row ofP, we divide each element of the row by the sum of the rows to obtain the corresponding probability distribution in line (19). Since each cluster is independent, therefore Algorithm 2 is able to use real-time parallel processing technology to deal with each class cluster as well as the collection of transition probability matrix. This is particularly important in the current big data and cloud-computing environment.


## 4.1. Alert Correlation Analysis

A key problem in mining attack scenarios directly from massive alert events is as follows. Since there may be several independent attack activities hidden in these alert events, this may cause confusions of attack scenarios if we directly associate these multisource alerts. Therefore, we must first accurately mine each independent attack activity and then separately measure the security property of each attack scenario.From this aim, we propose an alert clustering method based on the correlation of IP address. We format the multisource alert data detected by the different sensors and give the formal definition of alert event as follows.Definition 1.
Alert event is as an 7-tupleai=(timestamp,pluginID,pluginSID,srcIP,srcPort,desIP, desPort), where thetimestamp is the time when the sensor detects malicious features.pluginID is the number of source sensors generating the alert event.pluginSID is the classification information of the alert event in the corresponding sensor.srcIP andsrcPort are the source IP address and source port of the sensor producing alerts, respectively.desIP anddesPort are the destination IP address and destination port, respectively.
The attack type of the alert is determined by thepluginID andpluginSID together in Definition 1. Therefore, we use the variable type to indicate the type attribute of the alert.In general, alert events triggered by the same attack activity are always related to each other in the address distribution. For example, in a multistep attack, the target node of the former attack step may be the source node of the latter attack step. Based on this consideration, we use the correlation property of IP address. In detail, the alert events of the same attack activities are integrated together to provide an accurate data source for the construction of the absorbing Markov chain.The procedure of alert clustering based on IP address correlation is shown in Algorithm1. The cluster A1 in Figure 2 is a collection of alert sequences with IP addresses that are relevant. It is a set of alerts with the same source IP addresses or destination IP addresses in the original alert flow. ClusterSet is the collection composed of various clustersAi.Algorithm 1:Pseudocode for alert clustering based on the correlation of IP addresses.
Input: Real-time alert flow Output : The clusters of alerts with IP address correlated (1) WhileA is not empty (2)  a t e m p = A ⋅ first and drop A ⋅ first. (3) If  A0is not existing yet (4)  creat  A0  and add  atemp  toA0. (5)  else for  each  Ai  :  clusterSet (6)  if a t e m p  ⋅  IP  is in Ai⋅ IPset (7) add atemp to Ai. (8)  go  to  step (1). (9)  creat  An  and  add  atemp  to  An. (10)  EndFigure 2
Alerts clustering based on the correlation of IP addresses.The class clusters generated by the Algorithm1 are data sources for security metrics. Compared with the existing alert clustering method, the advantage of ours is that we do not adopt the concept of “similarity distance” with a strong subjectivity [22] but integrate the alerts according to the correlation analysis between their addresses, thus reflecting the address relevance of the attack. Meanwhile, there is no information loss in the process of alert preprocessing, which provides favorable conditions for accurately mining the hidden attack scenarios under the massive alerts.


## 4.2. Construction of AMC

The attack patterns of the attackers are hidden in the clusters generated by Algorithm1. This section investigates how to mine the hidden attack scenario based on these clusters. Since absorbing Markov chain can effectively model the randomness of development of discrete events, we use it to describe the attack process. We first overview some of the terminologies associated with AMC so that the reader can understand easily.Definition 2.
A Markov chain [23] is a collection of discrete random sequences denoted as S=s1,s2,…,sn, which contains a finite number of states. The sequence is a Markov chain if the following condition is satisfied. The formula indicates that the probability to go from a state to another only depends on the current state but is not related to the previous states.(1)psi+1∣si,si-1,…,s1=psi+1∣si.Definition 3.
An absorbing state is the destination state of the attacker, where the security is breached. The absorbing state nodea only has in-going edges but does not have out-going edges. Formally, a∈S∣∃ua∈E∧!∃aw∈E.Definition 4.
A transient state is the intermediate state of the attacker. The transient state nodeb has at least one out-going edge. Formally, {b∈S∣∃bw∈E}.Definition 5.
An absorbing Markov chain [23] is a special Markov chain containing at least one absorbing state. The associated state transition matrixP has the following canonical form.(2)
P
=
Q
R
0
I
,
0
≤
p
i
,
j
≤
1
,
∑
j
=
1
n
p
i
,
j
=
1
,
∀
1
≤
i
≤
nwhereQ is a nonzero (n-r)×(n-r) matrix denoting the transition probabilities between transient states.0 is r×(n-r) zero matrix.R is (n-r)×r matrix denoting the probabilities of transitions from the absorbing states to transient states.I is an r×r identity matrix denoting the transition probabilities between absorbing states. Besides,r is the number of absorbing states, n-r is the number of transient states, andn is the number of total states. The AMC requires that the sum of all transition probabilities of a given state must be equal to 1.We first present our design motivation using the example scenario in Figure3. The aim of alert correlation is to extract the one-step transition probability matrix of attack steps hidden in the alert flow. The identification of the node corresponds to the alert ID, which also represents a kind ofattack type caused by alert. The node reflects the attack step taken by the attacker. The weight of the edge corresponds to the frequency of repetition of the transition from an alert to another. Given an edge (i,j), the probability p(i,j) is the likelihood that the alertj will be raised given that the current raised alert isi. The transition probability between states represents the conditional probability that the attacker moves from the current attack type to the next attack type.Figure 3
The absorbing Markov chain representation of the attack scenario by alert correlation.Since our abstraction of attack scenario is developed based on the Markov property, which indicates that the next attack step is only related to the current attack step, therefore, the next step the attacker takes under the current attack step is independent of the attack path occurring before. This is also consistent with the reality. When the attacker reaches a valid state, he begins to consider what to do next based on the current state. In other words, only the current state will affect the attacker’s decision and the history states will not affect it.The AMC in Figure3 can also be expressed using a transition probability matrix as follows. The element in the matrix indicates the transition probability from the corresponding row’s attack type to the corresponding column’s attack type. We use AMC to describe the attack process. The element pij in the matrix represents the conditional probability p(j∣i) from the present attack typei to the future attack typej. The semantics of transition probability in the perspective of alert correlation is the probability of attacker from the current attack stepito the next attack stepj. (3)
P
=
A
t
t
a
c
k
T
y
p
e
1
.
2
2
.
7
3
.
6
4
.
5
5
.
5
1
2
3
4
5
0.2
0.7
0
0
0.1
0
0
0.6
0.4
0
0
0
0
0.5
0.5
0
0
0
1
0
0
0
0
0
1We analyze each class cluster of alerts produced by Algorithm1 and mine the hidden the corresponding one-step transition probability matrix using Algorithm 2.Algorithm 2:Pseudocode for mining the transition probability matrix from alerts.
Input : Class cluster with IP address correlation Output : One - step transition probability matrix of cluster (1)  For  each  ai:A (2)  If k = = 0 (3)  i = a k ⋅ type andj=ak+1⋅ type. (4)  add i and j to the set of alert types V. (5)  creat P according to V. (6)  p k j++ (7)  else (8)  i = a k ⋅ type andj=ak+1⋅ type. (9)  If a k + 1 ⋅ type is not included in V (10)  add a k + 1 ⋅ type to V. (11)  add row and column of a k + 1 ⋅ type to P. (12)  p i j++ (13)  else (14)  p i j++ (15)  End (16)  For  i=0,1,⋯,size (17)  where size is the number of P ’s row or column (18)  For j = 0,1 , ⋯ , s i z e (19)  p i j = p i j / s u m. (20)  where sum is the summation of row i (21)  End (22)  EndIn the process of traversing each alert in the class cluster by Algorithm2, if a new attack type is detected, a new row and column are added for the attack type in the transition probability matrixP, as shown in lines (9)-(12). This ensures that all types of attack are included inP shown in lines (1)-(15) The concept of proximity is used when mining associations between attack types. If the alert ai and alert ai+1 appear in turn, the appearance of attack type ai+1·type is only related to ai·type according to the Markov property. Then we add 1 to the count of ai·type to ai+1·type, which is the pij++ in line (6) of Algorithm 2. For instance, if we consider the weight of edge <AttackType_1,AttackType_2> is 2 this means that the intruder has caused the generation of the alert withAttack Type_1 and then another withAttack Type_2 two times.We normalize the transition probability matrix obtained after abstraction to meet the requirements of the Markov chain model. According to Definition1, the sum of all transition probabilities of a given state must be equal to 1. It is reflected that the sum of every row of the matrixP must be equal to 1. Thus, we convert the frequency of transitions between attack types into transition probabilities in lines (16)-(21). In other words, we assign the weight of the edge based on the number of frequencies of the transition from an alert to another. For each row ofP, we divide each element of the row by the sum of the rows to obtain the corresponding probability distribution in line (19). Since each cluster is independent, therefore Algorithm 2 is able to use real-time parallel processing technology to deal with each class cluster as well as the collection of transition probability matrix. This is particularly important in the current big data and cloud-computing environment.


## 5. AMC-Based Security Metrics

In this section, some lemmas and theorems for extracting properties of attackers towards multistep attacks are given. In addition, two algorithms are designed to measure the security property from the attacker’s perspective.


### 5.1. Metric of ENV

Lemma6 gives the state transition matrix of AMC aftern transitions. Lemma 7 indicates that the ultimate probability between the transient states is 0 when t→∞. Based on the probability theory, we further explore the matrix of calculating the expected node visits number ENV for middle host of attack path. Then the metric algorithm of ENV is given. Finally, a calculating example is provided.Lemma 6.
Given a state transition matrixP of AMC satisfying Definition 5, let pi,jt be the probability from statei to statej throught steps of attack. We can obtain the state transition matrix P(t) aftert step attacks as follows.(4)Pt=Qt∑k=0t-1Qk·R0I.Proof.
Use the mathematical induction to analyze the following:(1)
Whent=2, the Lemma 6 holds as follows:(5)P2=QR0I·QR0I=Q·QQ·R+I·R0I·I=Q2Q+Q0·R0I=Q2∑t=01Qt·R0I.(2)
Suppose whent=u-1, Lemma 6 also holds and thus P(u-1)=Q(u-1)∑t=0u-2Q(t)·R0I, then we can obtain the following formula and thereby the supposition holds:(6)Pu=Pu-1·P=Qu-1∑k=0u-2Qk·R0I·QR0I=Qu-1·QQu-1·R+∑k=0u-2Qk·R0I2=Qu∑k=0u-1Qk·R0I.
To conclude, we can obtain that Lemma6 is met by (1) and (2).Lemma 7.
The attacker starts attacking from the source node and keeps on launching attacks until it reaches the ultimate destination node, and thereby the transition probabilities between transient states are 0. Mathematically,limt→∞⁡Q(t)=0.Proof.
Assume thatqij=v∈(0,1), qijt denotes the probability of i→j in exactlyt steps. Then we can obtain limt→∞qijt=limt→∞qii1·qi1i2·…·qit-1j=limt→∞v1·…·vt=0. Hence, the probability of the attacker remaining in the transient state is 0. Lemma 7 holds.Theorem 8.
Given(n-r)×(n-r) fundamental matrixN, in which nij gives the expected number of visits that the process is in the transient statej if it is started in the initial statei, then we have N=(1-Q)-1.Proof.
( 1 ) The total number of visits to state j fromi in differentt steps is (7)N=nij=∑t=0∞1-qijt×0+qijt×1=∑t=0∞Qt,t=0,1,2,⋯,∞
( 2 ) By Lemma 7, we have limt→∞Q(t)=0, and thus limt→∞(I-Q(t))=I. Meantime, due to ∑k=0t-1Q(k)=(I-Q)-1·(I-Q(t)), we have N=∑k=0∞Q(k)=(I-Q)-1.
To sum up, Theorem8 holds by (1) and (2).ENV gives the expected number of each alert of the current scenario depending on the initial alerts raised by the intruder. Based on the ENVs of total alerts, we can obtain the ranking of alerts to arrange the patching preference of related vulnerabilities. The specification of ENV metric is shown in Algorithm3.Algorithm 3:Pseudocode for calculating ENV.
Input: Real - time alert flow{a0,a1,a3,⋯} Output: Matrix N and threat ranking of middle alert nodes (1)  UseAlgorithm1to fuse original alert flow to generate different class clusters. (2)  Fork=1to h (3)  where h is the number of clusters (4)  Use Algorithm 2 to construct n×n transition probability matrix P of A k . (5)  Generate ( n - r ) × ( n - r ) matrix Q from P according to Definition2. (6)  Calculate ( n - r ) × ( n - r ) foundational matrix N = I - Q - 1 . (7)  For i = 1 to n - r (8)  Rank n i 1 , n i 2 ,L, n i n - r in value decreasing. (9)  Return matrix N and the node ranking. (10)  End (11)  EndWe first use Algorithm1 to separate different attack scenarios from the original alert stream and obtain the clusters of different scenarios, as shown in line (1). Then Algorithm 2 is employed to construct the AMC of each scenario. Afterwards, we use the result of Theorem 8 to calculate the ENVs of different nodes in each scenario, as shown in lines (2)-(6). Finally, the threat ranking of the hosts corresponding to the alert nodes is given in lines (7)-(9).To demonstrate Algorithm3 clearly, we use Figure 3 as an example. Suppose we have obtained the corresponding transition probability matrixP. Additionally, combined with Definition 2, we can construct matrixQ and further calculate the fundamental matrixN as follows.(8)P=0.20.7000.1000.60.400000.50.50001000001,Q=0.20.70000.6000,N=I-Q-1=1.2500.8750.525010.6001.In practical application, if the initial alert raised by the intruder isAttackType_1, from the first row vector ofN, we can obtain that the ENVs of AttackType_1, AttackType_2, and AttackType_3 are n11=1.25, n12=0.875, and n12=0.525, respectively. Herein, the priority of hosts related to the three alerts is AttackType_1>AttackType_2>AttackType_3, and the alert leading to AttackType_1 is more critical.


### 5.2. Metric of ESP

Theorem 9.
Given(n-r)×r matrixB, the (i,j) entry bij denotes the ESP of attacker reaching the attack target Attacktype_j if the attacker starts with the initial alert associated with attacktype_i, where 1≤i≤n-r, r≤j≤n. Then we can derive B=N·R.Proof.
b i j is equal to the sum of probabilities of transitions via different intermediate alert nodes sm in differentt steps, t=0,1,2,⋯,∞, m=1,2,⋯,n-r. Then, we can derive(9)B=bij=∑t=0∞qi1t·r1j+…+qimt·rmj+…+qin-rt·rn-rj=∑t=0∞Qt·R
By Theorem8, we can obtain ∑t=0∞Qt=N. Hence, we can derive B=N·R, and the theorem holds.Similar to the metric of ENV, we first get the clusters of different attack scenarios from the original alert stream. Then we extract the AMC from each cluster. Combining with the results of Theorem9, we get the threat ranking of destination alert nodes corresponding to the target hosts. The details are shown in Algorithm 4.Algorithm 4:Pseudocode for calculating ESP.
Input: Real - time alert flow{a0,a1,a3,⋯} Output: Matrix B and threat ranking of absorbing alert nodes (1)  UseAlgorithm1to fuse original alert flow to generate different class clusters. (2)  Fork=1 to h (3)  where h is the number of clusters (4)  Use Algorithm 2 to construct n×n transition probability matrix P of A k . (5)  Generate ( n - r ) × ( n - r ) matrix Q and ( n - r ) × r matrix R from P according to Definition2. (6)  Calculate ( n - r ) × r ) matrix B = I - Q - 1 × R . (7)  For i = 1 to n - r (8)  Rank b i 1 ,  b i 2 , ⋯ , b i r in value decreasing. (9)  Return matrix B and the node ranking. (10)  End (11)  EndGo on with the analysis of Figure3 in Section 5.1, and we employ Algorithm 4 to construct the matrix(10)B=1-Q-1·R=AttackType1230.64250.35750.61250.38750.70.30.50.5.Take the first row ofBas an example; the value b11 gives the estimated probability of reaching the attack target AttackType_4 if the invader has just raised the AttackType_1. Since b11>b12, the most likely attack target is AttackType_4 and we rank the targets as AttackType_4>AttackType_5, and alert leading to AttackType_4 is the critical node. Moreover, since 0.6125+0.3875=1, we can identify that the attacker will finally reach the absorbing state.


### 5.3. Algorithm Performance Analysis

The operations of the above algorithms include matrix inversion, matrix addition, and matrix multiplication. The computation complexity of matrix multiplication is the highest. Multiplication of twon×n matrices requires 2n3 basic operations and thereby the computation complexity is O(n3). Our algorithm needs to save several matricesP,Q,N,R. Therefore, the storage complexity is O(n2). Overall, the proposed algorithm is time linear.


## 5.1. Metric of ENV

Lemma6 gives the state transition matrix of AMC aftern transitions. Lemma 7 indicates that the ultimate probability between the transient states is 0 when t→∞. Based on the probability theory, we further explore the matrix of calculating the expected node visits number ENV for middle host of attack path. Then the metric algorithm of ENV is given. Finally, a calculating example is provided.Lemma 6.
Given a state transition matrixP of AMC satisfying Definition 5, let pi,jt be the probability from statei to statej throught steps of attack. We can obtain the state transition matrix P(t) aftert step attacks as follows.(4)Pt=Qt∑k=0t-1Qk·R0I.Proof.
Use the mathematical induction to analyze the following:(1)
Whent=2, the Lemma 6 holds as follows:(5)P2=QR0I·QR0I=Q·QQ·R+I·R0I·I=Q2Q+Q0·R0I=Q2∑t=01Qt·R0I.(2)
Suppose whent=u-1, Lemma 6 also holds and thus P(u-1)=Q(u-1)∑t=0u-2Q(t)·R0I, then we can obtain the following formula and thereby the supposition holds:(6)Pu=Pu-1·P=Qu-1∑k=0u-2Qk·R0I·QR0I=Qu-1·QQu-1·R+∑k=0u-2Qk·R0I2=Qu∑k=0u-1Qk·R0I.
To conclude, we can obtain that Lemma6 is met by (1) and (2).Lemma 7.
The attacker starts attacking from the source node and keeps on launching attacks until it reaches the ultimate destination node, and thereby the transition probabilities between transient states are 0. Mathematically,limt→∞⁡Q(t)=0.Proof.
Assume thatqij=v∈(0,1), qijt denotes the probability of i→j in exactlyt steps. Then we can obtain limt→∞qijt=limt→∞qii1·qi1i2·…·qit-1j=limt→∞v1·…·vt=0. Hence, the probability of the attacker remaining in the transient state is 0. Lemma 7 holds.Theorem 8.
Given(n-r)×(n-r) fundamental matrixN, in which nij gives the expected number of visits that the process is in the transient statej if it is started in the initial statei, then we have N=(1-Q)-1.Proof.
( 1 ) The total number of visits to state j fromi in differentt steps is (7)N=nij=∑t=0∞1-qijt×0+qijt×1=∑t=0∞Qt,t=0,1,2,⋯,∞
( 2 ) By Lemma 7, we have limt→∞Q(t)=0, and thus limt→∞(I-Q(t))=I. Meantime, due to ∑k=0t-1Q(k)=(I-Q)-1·(I-Q(t)), we have N=∑k=0∞Q(k)=(I-Q)-1.
To sum up, Theorem8 holds by (1) and (2).ENV gives the expected number of each alert of the current scenario depending on the initial alerts raised by the intruder. Based on the ENVs of total alerts, we can obtain the ranking of alerts to arrange the patching preference of related vulnerabilities. The specification of ENV metric is shown in Algorithm3.Algorithm 3:Pseudocode for calculating ENV.
Input: Real - time alert flow{a0,a1,a3,⋯} Output: Matrix N and threat ranking of middle alert nodes (1)  UseAlgorithm1to fuse original alert flow to generate different class clusters. (2)  Fork=1to h (3)  where h is the number of clusters (4)  Use Algorithm 2 to construct n×n transition probability matrix P of A k . (5)  Generate ( n - r ) × ( n - r ) matrix Q from P according to Definition2. (6)  Calculate ( n - r ) × ( n - r ) foundational matrix N = I - Q - 1 . (7)  For i = 1 to n - r (8)  Rank n i 1 , n i 2 ,L, n i n - r in value decreasing. (9)  Return matrix N and the node ranking. (10)  End (11)  EndWe first use Algorithm1 to separate different attack scenarios from the original alert stream and obtain the clusters of different scenarios, as shown in line (1). Then Algorithm 2 is employed to construct the AMC of each scenario. Afterwards, we use the result of Theorem 8 to calculate the ENVs of different nodes in each scenario, as shown in lines (2)-(6). Finally, the threat ranking of the hosts corresponding to the alert nodes is given in lines (7)-(9).To demonstrate Algorithm3 clearly, we use Figure 3 as an example. Suppose we have obtained the corresponding transition probability matrixP. Additionally, combined with Definition 2, we can construct matrixQ and further calculate the fundamental matrixN as follows.(8)P=0.20.7000.1000.60.400000.50.50001000001,Q=0.20.70000.6000,N=I-Q-1=1.2500.8750.525010.6001.In practical application, if the initial alert raised by the intruder isAttackType_1, from the first row vector ofN, we can obtain that the ENVs of AttackType_1, AttackType_2, and AttackType_3 are n11=1.25, n12=0.875, and n12=0.525, respectively. Herein, the priority of hosts related to the three alerts is AttackType_1>AttackType_2>AttackType_3, and the alert leading to AttackType_1 is more critical.


## 5.2. Metric of ESP

Theorem 9.
Given(n-r)×r matrixB, the (i,j) entry bij denotes the ESP of attacker reaching the attack target Attacktype_j if the attacker starts with the initial alert associated with attacktype_i, where 1≤i≤n-r, r≤j≤n. Then we can derive B=N·R.Proof.
b i j is equal to the sum of probabilities of transitions via different intermediate alert nodes sm in differentt steps, t=0,1,2,⋯,∞, m=1,2,⋯,n-r. Then, we can derive(9)B=bij=∑t=0∞qi1t·r1j+…+qimt·rmj+…+qin-rt·rn-rj=∑t=0∞Qt·R
By Theorem8, we can obtain ∑t=0∞Qt=N. Hence, we can derive B=N·R, and the theorem holds.Similar to the metric of ENV, we first get the clusters of different attack scenarios from the original alert stream. Then we extract the AMC from each cluster. Combining with the results of Theorem9, we get the threat ranking of destination alert nodes corresponding to the target hosts. The details are shown in Algorithm 4.Algorithm 4:Pseudocode for calculating ESP.
Input: Real - time alert flow{a0,a1,a3,⋯} Output: Matrix B and threat ranking of absorbing alert nodes (1)  UseAlgorithm1to fuse original alert flow to generate different class clusters. (2)  Fork=1 to h (3)  where h is the number of clusters (4)  Use Algorithm 2 to construct n×n transition probability matrix P of A k . (5)  Generate ( n - r ) × ( n - r ) matrix Q and ( n - r ) × r matrix R from P according to Definition2. (6)  Calculate ( n - r ) × r ) matrix B = I - Q - 1 × R . (7)  For i = 1 to n - r (8)  Rank b i 1 ,  b i 2 , ⋯ , b i r in value decreasing. (9)  Return matrix B and the node ranking. (10)  End (11)  EndGo on with the analysis of Figure3 in Section 5.1, and we employ Algorithm 4 to construct the matrix(10)B=1-Q-1·R=AttackType1230.64250.35750.61250.38750.70.30.50.5.Take the first row ofBas an example; the value b11 gives the estimated probability of reaching the attack target AttackType_4 if the invader has just raised the AttackType_1. Since b11>b12, the most likely attack target is AttackType_4 and we rank the targets as AttackType_4>AttackType_5, and alert leading to AttackType_4 is the critical node. Moreover, since 0.6125+0.3875=1, we can identify that the attacker will finally reach the absorbing state.


## 5.3. Algorithm Performance Analysis

The operations of the above algorithms include matrix inversion, matrix addition, and matrix multiplication. The computation complexity of matrix multiplication is the highest. Multiplication of twon×n matrices requires 2n3 basic operations and thereby the computation complexity is O(n3). Our algorithm needs to save several matricesP,Q,N,R. Therefore, the storage complexity is O(n2). Overall, the proposed algorithm is time linear.


## 6. Experiments and Discussions

In this section, we test the proposed model and algorithms on a small-scale experiment network. We first describe the experiment setup. Then the experiment results are demonstrated. Experiment analyses as well as some comparisons and discussions are given finally.


### 6.1. Experiment Environment

#### 6.1.1. Network Topology

Given a real network as depicted in Figure4 to perform our approaches, the network is composed of the firewalls, routers, Snort IDSs, a web server, a database server, a graphic workstation, and an external host for launching attack.Figure 4
Experiment network topology.


#### 6.1.2. Network Configuration

The firewall policies are organized in Table1. The network is divided into 2 subnets. The servers H1, H2 are deployed in the DMZ zone, and the workstation H3 and servers H4, H5 are deployed in the trusted zone. The remote host H0 is forbidden to access with servers in the trusted zone by firewalls and can only communicate with H1, H2 in the DMZ zone via HTTP protocol (port 80). Servers in the trusted zone can only communicate with the servers in the DMZ zone passively.Table 1
Firewall policy.
Source Destination Protocol Port Internet Webserver HTTP 80 Internet Database Server HTTP 80 Webserver Database Server PostgreSQL 3306 Webserver FTP Server NFS 21 Webserver Graphic Workstation SIP 5060 Webserver Authentication Server Kerberos UDP 88 Database Server FTP Server NFS 21 Database Server Graphic Workstation SIP 5060 Database Server Authentication Server SSL 443 Database Server Webserver TCP 3306 Authentication Server FTP Server NFS 21 Authentication Server Graphic Workstation SIP 5060After scanning the network using tool Nessus [24], we collect the vulnerabilities in the network. By querying the database of NVD, we obtain the detailed host configuration and vulnerability information as shown in Table 2.Table 2
Host configuration and vulnerability information.
Host # Configuration ofHost # Service CVE # No. Overview of CVE # H1 Web serverWindows server 2012 HTTP CVE2012-3328 v 1 Allowing remote attackers to inject arbitrary web script or HTML via vectors related to a hidden frame footer  H2 Database serverMSQL server 2000 PostgreSQL CVE2013-0676 v 2 Allowing remote authenticated users to obtain sensitive information via a SQL query  H3 Authentication serverWindows server 2012 Kerberos CVE2016-0049 v 3 Allowing remote attackers to bypass authentication by deploying a crafted Key Distribution Center (KDC) and then performing a sign-in action SSL CVE2012-6137 v 5 Allowing remote man-in-the-middle attackers to obtain sensitive information such as user credentials  H4 Graphic workstationRed hat Linux 7.2 Linux CVE 2013-4512 v 6 Allowing local users to cause a denial of service or possibly have other unspecified impact by leveraging root privileges for a write operation  H5 FTP serverWindows server 2012 HFS CVE2014-6287 v 4 Allowing remote attackers to execute arbitrary programs via a sequence in a search action


### 6.2. Experiment Analyses

In order to collect real-world attack alert data, the attacker carries out the UDP FLOOD attack and SYN FLOOD attack. We collect the alert data detected by the running IDS, the firewall, and syslog of servers for experiment analyses.


#### 6.2.1. Construction of AMC

After using Algorithm1 to fuse the original alerts, we get two class clusters A1 and A2. Taking cluster A1 of UDF FLOOD scenario as an example, we further use Algorithm 2 to mine the one-step transition probability matrix. The attack type represented by each row and column of the matrix is numbered according to the occurrence order of its corresponding alert event. The description of each attack type corresponding to the detected alert raised by the intruder is organized in Table 3. The Graphviz toolkit [25] is used to draw the absorbing Markov chain of the attack scenario extracted from A1 as shown in Figure 5. The yellow node denotes the remote attacker in the Internet. Two green nodes are the target states of the attacker. Other nodes represent the attack types of attack events derived from the alert analysis. According to the alerts raised by the intruder, we can obtain the attack steps that the intruder has taken.Table 3
The descriptions of alerts and their attack types in clusterA1.
Alert Number Attack Type a 1 ICMP PING  a 2 TELENT Bad login  a 3 RPC sadmind UDP PING  a 4 WEB-MISC adobe portable document format file download attempt  a 5 RSERVICES rsh root  a 6 DOS mstream handler to client  a 7 BAD-TRAFFIC loopback trafficFigure 5
The AMC model extracted from the real alert flow.


#### 6.2.2. Metric of ENV

In this section, we conduct Algorithm3 to calculate ENV for the realistic attack scenario. The state transition matrixP of Figure 5 is constructed firstly, and then we calculate the matrixN.(11)
P
=
0
0.35
0.65
0
0
0
0
0
0
0.15
0.18
0.25
0.20
0.22
0
0.06
0
0.17
0.31
0.02
0.44
0
0
0
0
0.79
0.21
0
0
0
0
0
0
0.33
0.67
0
0
0
0
0
1
0
0
0
0
0
0
0
1
,
N
=
1
0.39
0.71
0.19
0.47
0
1.01
0.15
0.21
0.46
0
0.06
1.01
0.18
0.47
0
0
0
1
0.79
0
0
0
0
1
.The different rows ofN indicate the ENVs of attacker starting from different initial states. The distribution of ENV is illustrated in Figure 6. The bigger value indicates the higher critical level of the vulnerability related to the node. For example, from the first row ofN, if the attacker has just raised the alert node a1, then the ENVs to middle nodes a2,a3,a4,a5 are 0.39, 0.71, 0.19, and 0.47, respectively. The corresponding threat ranking is a3>a2>a5>a4. Thus, the security manager can employ this priority to determine which alert relevant vulnerability needs to be patched first. Herein, the first vulnerability suggested to be patched is the CVE 2014-1878 leading to a3.Figure 6
ENV distribution of attacker arising with different middle alert nodes from different source alert nodes.


#### 6.2.3. Metric of ESP

We further use Algorithm3 to measure the ESP of different attack targets; the ESP matrix is calculated as B=0.290.710.400.600.230.770.470.530.330.67. For a given attack target, the larger bij is, the higher the probability will reach it. Suppose the manager observed that the intruder had just raised the alert a1, then from the first row ofB, we can obtain the fact that the ESPs of attacker raising a6 and a7 are 0.5035 and 0.4965, respectively. Therefore, the invader is more likely to breach the host H4 associated with a6.The distribution of ESP is illustrated in Figure7. The abscissa is the source alert of attacker and the ordinate is the ESP of achieving the target alert. When the source alerts (first observed alerts) are a1, a2, a3, a4, and a5, which indicates that regardless of the source alerts we can predict that the most likely target alert is a6 (Graphic workstation H4) since it can bring more loss to the network system by causing DOS stream.Figure 7
ESP distribution of attacker arising with different target alert nodes from different source alert nodes.


### 6.3. Comparisons and Discussions

In order to compare the metrics of the realistic scenario using alerts as input with that of the ideal scenario using vulnerability exploits as input, we further summarize the detailed qualitative analyses in Table4. Our major merits are shown in Table 4.Table 4
Comparisons of security metrics among our method and others.
Types Metrics [9] [10] [11] [14] [17] [18] [20] Ours VAG-based security metrics Shortest attack path length ✓  ✓ ✓  – ✓ Most possible attack path ✓ ✓ ✓ ✓  ✓ ✓ Cumulative probability of attack target ✓ ✓  ✓  ✓ ✓ Number of attack paths ✓ ✓ ✓    ✓  AMC-based security metrics ENV to the middle attack node     ✓   ✓ ESP of attack target node        ✓ Ranking of middle attack nodes        ✓ Ranking of attack targets     ✓   ✓The VAG-based security metrics utilize vulnerability attack graph to represent all the possible ways an intruder can compromise a security policy through vulnerability exploitation. The VGA can be constructed by using network connectivity information and known vulnerabilities within the architecture of the network. It reveals all the ways an attacker can leverage vulnerabilities in a given network to violate a security policy. Since all attack paths are included, the VAG describes a more general and loose scenario. We refer the metrics within the ideal attack scenario as the ideal metrics. Most existing studies focused on ideal scenario since it includes all possible scenarios for attackers. For instance, [8, 11, 14, 20] analyzed the shortest path length, which assumes that each atomic attack can succeed immediately. Meanwhile, the number of ideal paths was calculated in [9–11, 20], which is established based on the hypothesis that each node appears exactly once in the attack path. The most probable path is identified by calculating the cumulative success probability of each attack path in [9–11, 18, 20], where the cumulative probability is obtained by calculating the product of the probabilities of the substeps of attack. The ideal probability that an attacker could achieve the target is the sum of the cumulative probabilities of all ideal paths [9, 10, 14, 18, 20]. We take Figure 5 as an example; if the source alert isa1, the cumulative probabilities of reaching a6 and a7 are 0.19 and 0.38, respectively. It is interesting that the sum of 0.19 and 0.38 is 0.57 but not 1. In general, the attacker starts attacking from the source alert and keeps on launching permeation until he reaches the ultimate target node. Therefore, the cumulative probability is an ideal result without considering the failed actions of attack. Moreover, as the size and scale of the network increase, the number of nodes and edges in the VAG increases dramatically, thus making the metrics complicated and difficult to implement.Although the above ideal security metrics can only properly reflect the security strength of the network in a certain extent, we recognize that the ideal attack scenario may not be the real scenario launched by the attackers. From this aim, we collect the incoming alert flow to extract the alert correlation graph by using alert correlation analysis technique. Compared with the VAG, we model the real-world attack scenario as the absorbing Markov chain, thus improving the authenticity of measurement. Meanwhile, the scale of the generated graph is significantly reduced and it is beneficial to improve the efficiency and accuracy of metrics. For example, if the source alert isa1, the expected success probability ofa6 is 0.29, which is larger than the ideal success probability 0.19. This is due to the fact that we pick up the missed failed attack actions in ideal scenario. Since the ESP ofa7 is larger, we can identify that the target alert isa7. The ENV ofa2 is 0.39, which indicates that an average of 0.29 times of alerts with attack type “TELENT Bad login” will be aroused if the intruder has just aroused alerta1. The ENV ofa3 is the largest, so the vulnerability leading to alerta3 with attack type “RPC sadmind UDP PING” is the most critical and thus suggested to be patched first. Although [17] also gives a measurement of the average numbers of visits to the middle hosts of attack path, the estimate of transition probability is deduced based on the common vulnerability scoring system and therefore still depends on the expert experience. Moreover, existing researches focus on analyzing attackers with just one attack target. How to deal with the sophisticated scenarios including multiple attack targets has not been taken into consideration yet. In contrast to [17], the probabilities of state transitions are calculated from the real-time alert data set automatically in our method and do not require any prior knowledge. Besides, we can analyze the scenarios with multiple targets. Hence, our measurement results are more objective and practical.In summary, the AMC model extracting from the real-time alert data is more closely related to the actual scenario of attack, and therefore the metrics obtained are more accurate and effective. The proposed model and metric algorithms provide quantitative and efficient data support for network proactive defense and will assist in making appropriate security decisions in advance.


## 6.1. Experiment Environment

### 6.1.1. Network Topology

Given a real network as depicted in Figure4 to perform our approaches, the network is composed of the firewalls, routers, Snort IDSs, a web server, a database server, a graphic workstation, and an external host for launching attack.Figure 4
Experiment network topology.


### 6.1.2. Network Configuration

The firewall policies are organized in Table1. The network is divided into 2 subnets. The servers H1, H2 are deployed in the DMZ zone, and the workstation H3 and servers H4, H5 are deployed in the trusted zone. The remote host H0 is forbidden to access with servers in the trusted zone by firewalls and can only communicate with H1, H2 in the DMZ zone via HTTP protocol (port 80). Servers in the trusted zone can only communicate with the servers in the DMZ zone passively.Table 1
Firewall policy.
Source Destination Protocol Port Internet Webserver HTTP 80 Internet Database Server HTTP 80 Webserver Database Server PostgreSQL 3306 Webserver FTP Server NFS 21 Webserver Graphic Workstation SIP 5060 Webserver Authentication Server Kerberos UDP 88 Database Server FTP Server NFS 21 Database Server Graphic Workstation SIP 5060 Database Server Authentication Server SSL 443 Database Server Webserver TCP 3306 Authentication Server FTP Server NFS 21 Authentication Server Graphic Workstation SIP 5060After scanning the network using tool Nessus [24], we collect the vulnerabilities in the network. By querying the database of NVD, we obtain the detailed host configuration and vulnerability information as shown in Table 2.Table 2
Host configuration and vulnerability information.
Host # Configuration ofHost # Service CVE # No. Overview of CVE # H1 Web serverWindows server 2012 HTTP CVE2012-3328 v 1 Allowing remote attackers to inject arbitrary web script or HTML via vectors related to a hidden frame footer  H2 Database serverMSQL server 2000 PostgreSQL CVE2013-0676 v 2 Allowing remote authenticated users to obtain sensitive information via a SQL query  H3 Authentication serverWindows server 2012 Kerberos CVE2016-0049 v 3 Allowing remote attackers to bypass authentication by deploying a crafted Key Distribution Center (KDC) and then performing a sign-in action SSL CVE2012-6137 v 5 Allowing remote man-in-the-middle attackers to obtain sensitive information such as user credentials  H4 Graphic workstationRed hat Linux 7.2 Linux CVE 2013-4512 v 6 Allowing local users to cause a denial of service or possibly have other unspecified impact by leveraging root privileges for a write operation  H5 FTP serverWindows server 2012 HFS CVE2014-6287 v 4 Allowing remote attackers to execute arbitrary programs via a sequence in a search action


## 6.1.1. Network Topology

Given a real network as depicted in Figure4 to perform our approaches, the network is composed of the firewalls, routers, Snort IDSs, a web server, a database server, a graphic workstation, and an external host for launching attack.Figure 4
Experiment network topology.


## 6.1.2. Network Configuration

The firewall policies are organized in Table1. The network is divided into 2 subnets. The servers H1, H2 are deployed in the DMZ zone, and the workstation H3 and servers H4, H5 are deployed in the trusted zone. The remote host H0 is forbidden to access with servers in the trusted zone by firewalls and can only communicate with H1, H2 in the DMZ zone via HTTP protocol (port 80). Servers in the trusted zone can only communicate with the servers in the DMZ zone passively.Table 1
Firewall policy.
Source Destination Protocol Port Internet Webserver HTTP 80 Internet Database Server HTTP 80 Webserver Database Server PostgreSQL 3306 Webserver FTP Server NFS 21 Webserver Graphic Workstation SIP 5060 Webserver Authentication Server Kerberos UDP 88 Database Server FTP Server NFS 21 Database Server Graphic Workstation SIP 5060 Database Server Authentication Server SSL 443 Database Server Webserver TCP 3306 Authentication Server FTP Server NFS 21 Authentication Server Graphic Workstation SIP 5060After scanning the network using tool Nessus [24], we collect the vulnerabilities in the network. By querying the database of NVD, we obtain the detailed host configuration and vulnerability information as shown in Table 2.Table 2
Host configuration and vulnerability information.
Host # Configuration ofHost # Service CVE # No. Overview of CVE # H1 Web serverWindows server 2012 HTTP CVE2012-3328 v 1 Allowing remote attackers to inject arbitrary web script or HTML via vectors related to a hidden frame footer  H2 Database serverMSQL server 2000 PostgreSQL CVE2013-0676 v 2 Allowing remote authenticated users to obtain sensitive information via a SQL query  H3 Authentication serverWindows server 2012 Kerberos CVE2016-0049 v 3 Allowing remote attackers to bypass authentication by deploying a crafted Key Distribution Center (KDC) and then performing a sign-in action SSL CVE2012-6137 v 5 Allowing remote man-in-the-middle attackers to obtain sensitive information such as user credentials  H4 Graphic workstationRed hat Linux 7.2 Linux CVE 2013-4512 v 6 Allowing local users to cause a denial of service or possibly have other unspecified impact by leveraging root privileges for a write operation  H5 FTP serverWindows server 2012 HFS CVE2014-6287 v 4 Allowing remote attackers to execute arbitrary programs via a sequence in a search action


## 6.2. Experiment Analyses

In order to collect real-world attack alert data, the attacker carries out the UDP FLOOD attack and SYN FLOOD attack. We collect the alert data detected by the running IDS, the firewall, and syslog of servers for experiment analyses.


### 6.2.1. Construction of AMC

After using Algorithm1 to fuse the original alerts, we get two class clusters A1 and A2. Taking cluster A1 of UDF FLOOD scenario as an example, we further use Algorithm 2 to mine the one-step transition probability matrix. The attack type represented by each row and column of the matrix is numbered according to the occurrence order of its corresponding alert event. The description of each attack type corresponding to the detected alert raised by the intruder is organized in Table 3. The Graphviz toolkit [25] is used to draw the absorbing Markov chain of the attack scenario extracted from A1 as shown in Figure 5. The yellow node denotes the remote attacker in the Internet. Two green nodes are the target states of the attacker. Other nodes represent the attack types of attack events derived from the alert analysis. According to the alerts raised by the intruder, we can obtain the attack steps that the intruder has taken.Table 3
The descriptions of alerts and their attack types in clusterA1.
Alert Number Attack Type a 1 ICMP PING  a 2 TELENT Bad login  a 3 RPC sadmind UDP PING  a 4 WEB-MISC adobe portable document format file download attempt  a 5 RSERVICES rsh root  a 6 DOS mstream handler to client  a 7 BAD-TRAFFIC loopback trafficFigure 5
The AMC model extracted from the real alert flow.


### 6.2.2. Metric of ENV

In this section, we conduct Algorithm3 to calculate ENV for the realistic attack scenario. The state transition matrixP of Figure 5 is constructed firstly, and then we calculate the matrixN.(11)
P
=
0
0.35
0.65
0
0
0
0
0
0
0.15
0.18
0.25
0.20
0.22
0
0.06
0
0.17
0.31
0.02
0.44
0
0
0
0
0.79
0.21
0
0
0
0
0
0
0.33
0.67
0
0
0
0
0
1
0
0
0
0
0
0
0
1
,
N
=
1
0.39
0.71
0.19
0.47
0
1.01
0.15
0.21
0.46
0
0.06
1.01
0.18
0.47
0
0
0
1
0.79
0
0
0
0
1
.The different rows ofN indicate the ENVs of attacker starting from different initial states. The distribution of ENV is illustrated in Figure 6. The bigger value indicates the higher critical level of the vulnerability related to the node. For example, from the first row ofN, if the attacker has just raised the alert node a1, then the ENVs to middle nodes a2,a3,a4,a5 are 0.39, 0.71, 0.19, and 0.47, respectively. The corresponding threat ranking is a3>a2>a5>a4. Thus, the security manager can employ this priority to determine which alert relevant vulnerability needs to be patched first. Herein, the first vulnerability suggested to be patched is the CVE 2014-1878 leading to a3.Figure 6
ENV distribution of attacker arising with different middle alert nodes from different source alert nodes.


### 6.2.3. Metric of ESP

We further use Algorithm3 to measure the ESP of different attack targets; the ESP matrix is calculated as B=0.290.710.400.600.230.770.470.530.330.67. For a given attack target, the larger bij is, the higher the probability will reach it. Suppose the manager observed that the intruder had just raised the alert a1, then from the first row ofB, we can obtain the fact that the ESPs of attacker raising a6 and a7 are 0.5035 and 0.4965, respectively. Therefore, the invader is more likely to breach the host H4 associated with a6.The distribution of ESP is illustrated in Figure7. The abscissa is the source alert of attacker and the ordinate is the ESP of achieving the target alert. When the source alerts (first observed alerts) are a1, a2, a3, a4, and a5, which indicates that regardless of the source alerts we can predict that the most likely target alert is a6 (Graphic workstation H4) since it can bring more loss to the network system by causing DOS stream.Figure 7
ESP distribution of attacker arising with different target alert nodes from different source alert nodes.


## 6.2.1. Construction of AMC

After using Algorithm1 to fuse the original alerts, we get two class clusters A1 and A2. Taking cluster A1 of UDF FLOOD scenario as an example, we further use Algorithm 2 to mine the one-step transition probability matrix. The attack type represented by each row and column of the matrix is numbered according to the occurrence order of its corresponding alert event. The description of each attack type corresponding to the detected alert raised by the intruder is organized in Table 3. The Graphviz toolkit [25] is used to draw the absorbing Markov chain of the attack scenario extracted from A1 as shown in Figure 5. The yellow node denotes the remote attacker in the Internet. Two green nodes are the target states of the attacker. Other nodes represent the attack types of attack events derived from the alert analysis. According to the alerts raised by the intruder, we can obtain the attack steps that the intruder has taken.Table 3
The descriptions of alerts and their attack types in clusterA1.
Alert Number Attack Type a 1 ICMP PING  a 2 TELENT Bad login  a 3 RPC sadmind UDP PING  a 4 WEB-MISC adobe portable document format file download attempt  a 5 RSERVICES rsh root  a 6 DOS mstream handler to client  a 7 BAD-TRAFFIC loopback trafficFigure 5
The AMC model extracted from the real alert flow.


## 6.2.2. Metric of ENV

In this section, we conduct Algorithm3 to calculate ENV for the realistic attack scenario. The state transition matrixP of Figure 5 is constructed firstly, and then we calculate the matrixN.(11)
P
=
0
0.35
0.65
0
0
0
0
0
0
0.15
0.18
0.25
0.20
0.22
0
0.06
0
0.17
0.31
0.02
0.44
0
0
0
0
0.79
0.21
0
0
0
0
0
0
0.33
0.67
0
0
0
0
0
1
0
0
0
0
0
0
0
1
,
N
=
1
0.39
0.71
0.19
0.47
0
1.01
0.15
0.21
0.46
0
0.06
1.01
0.18
0.47
0
0
0
1
0.79
0
0
0
0
1
.The different rows ofN indicate the ENVs of attacker starting from different initial states. The distribution of ENV is illustrated in Figure 6. The bigger value indicates the higher critical level of the vulnerability related to the node. For example, from the first row ofN, if the attacker has just raised the alert node a1, then the ENVs to middle nodes a2,a3,a4,a5 are 0.39, 0.71, 0.19, and 0.47, respectively. The corresponding threat ranking is a3>a2>a5>a4. Thus, the security manager can employ this priority to determine which alert relevant vulnerability needs to be patched first. Herein, the first vulnerability suggested to be patched is the CVE 2014-1878 leading to a3.Figure 6
ENV distribution of attacker arising with different middle alert nodes from different source alert nodes.


## 6.2.3. Metric of ESP

We further use Algorithm3 to measure the ESP of different attack targets; the ESP matrix is calculated as B=0.290.710.400.600.230.770.470.530.330.67. For a given attack target, the larger bij is, the higher the probability will reach it. Suppose the manager observed that the intruder had just raised the alert a1, then from the first row ofB, we can obtain the fact that the ESPs of attacker raising a6 and a7 are 0.5035 and 0.4965, respectively. Therefore, the invader is more likely to breach the host H4 associated with a6.The distribution of ESP is illustrated in Figure7. The abscissa is the source alert of attacker and the ordinate is the ESP of achieving the target alert. When the source alerts (first observed alerts) are a1, a2, a3, a4, and a5, which indicates that regardless of the source alerts we can predict that the most likely target alert is a6 (Graphic workstation H4) since it can bring more loss to the network system by causing DOS stream.Figure 7
ESP distribution of attacker arising with different target alert nodes from different source alert nodes.


## 6.3. Comparisons and Discussions

In order to compare the metrics of the realistic scenario using alerts as input with that of the ideal scenario using vulnerability exploits as input, we further summarize the detailed qualitative analyses in Table4. Our major merits are shown in Table 4.Table 4
Comparisons of security metrics among our method and others.
Types Metrics [9] [10] [11] [14] [17] [18] [20] Ours VAG-based security metrics Shortest attack path length ✓  ✓ ✓  – ✓ Most possible attack path ✓ ✓ ✓ ✓  ✓ ✓ Cumulative probability of attack target ✓ ✓  ✓  ✓ ✓ Number of attack paths ✓ ✓ ✓    ✓  AMC-based security metrics ENV to the middle attack node     ✓   ✓ ESP of attack target node        ✓ Ranking of middle attack nodes        ✓ Ranking of attack targets     ✓   ✓The VAG-based security metrics utilize vulnerability attack graph to represent all the possible ways an intruder can compromise a security policy through vulnerability exploitation. The VGA can be constructed by using network connectivity information and known vulnerabilities within the architecture of the network. It reveals all the ways an attacker can leverage vulnerabilities in a given network to violate a security policy. Since all attack paths are included, the VAG describes a more general and loose scenario. We refer the metrics within the ideal attack scenario as the ideal metrics. Most existing studies focused on ideal scenario since it includes all possible scenarios for attackers. For instance, [8, 11, 14, 20] analyzed the shortest path length, which assumes that each atomic attack can succeed immediately. Meanwhile, the number of ideal paths was calculated in [9–11, 20], which is established based on the hypothesis that each node appears exactly once in the attack path. The most probable path is identified by calculating the cumulative success probability of each attack path in [9–11, 18, 20], where the cumulative probability is obtained by calculating the product of the probabilities of the substeps of attack. The ideal probability that an attacker could achieve the target is the sum of the cumulative probabilities of all ideal paths [9, 10, 14, 18, 20]. We take Figure 5 as an example; if the source alert isa1, the cumulative probabilities of reaching a6 and a7 are 0.19 and 0.38, respectively. It is interesting that the sum of 0.19 and 0.38 is 0.57 but not 1. In general, the attacker starts attacking from the source alert and keeps on launching permeation until he reaches the ultimate target node. Therefore, the cumulative probability is an ideal result without considering the failed actions of attack. Moreover, as the size and scale of the network increase, the number of nodes and edges in the VAG increases dramatically, thus making the metrics complicated and difficult to implement.Although the above ideal security metrics can only properly reflect the security strength of the network in a certain extent, we recognize that the ideal attack scenario may not be the real scenario launched by the attackers. From this aim, we collect the incoming alert flow to extract the alert correlation graph by using alert correlation analysis technique. Compared with the VAG, we model the real-world attack scenario as the absorbing Markov chain, thus improving the authenticity of measurement. Meanwhile, the scale of the generated graph is significantly reduced and it is beneficial to improve the efficiency and accuracy of metrics. For example, if the source alert isa1, the expected success probability ofa6 is 0.29, which is larger than the ideal success probability 0.19. This is due to the fact that we pick up the missed failed attack actions in ideal scenario. Since the ESP ofa7 is larger, we can identify that the target alert isa7. The ENV ofa2 is 0.39, which indicates that an average of 0.29 times of alerts with attack type “TELENT Bad login” will be aroused if the intruder has just aroused alerta1. The ENV ofa3 is the largest, so the vulnerability leading to alerta3 with attack type “RPC sadmind UDP PING” is the most critical and thus suggested to be patched first. Although [17] also gives a measurement of the average numbers of visits to the middle hosts of attack path, the estimate of transition probability is deduced based on the common vulnerability scoring system and therefore still depends on the expert experience. Moreover, existing researches focus on analyzing attackers with just one attack target. How to deal with the sophisticated scenarios including multiple attack targets has not been taken into consideration yet. In contrast to [17], the probabilities of state transitions are calculated from the real-time alert data set automatically in our method and do not require any prior knowledge. Besides, we can analyze the scenarios with multiple targets. Hence, our measurement results are more objective and practical.In summary, the AMC model extracting from the real-time alert data is more closely related to the actual scenario of attack, and therefore the metrics obtained are more accurate and effective. The proposed model and metric algorithms provide quantitative and efficient data support for network proactive defense and will assist in making appropriate security decisions in advance.


## 7. Conclusions and Future Works

Current enterprise networks typically have multiple entry points. This topology is intended to enhance a network’s accessibility and availability, but it leaves security vulnerabilities that sophisticated attackers can exploit using advanced techniques, such as multistep attacks. Quantifying security with metrics is important since we want to have a scoring system to estimate the strength of the security. From this aim, we present an absorbing Markov model for extracting several attack properties with higher precision based on correlation analysis of alert data. Using the model of absorbing Markov chain, we can extract various properties of the attack scenarios as well as the attackers, such as the estimated probability of reaching each attack target and the estimated occurrence number of each alert in the attack scenario. The experiments verify that our approaches are available, reliable, and comprehensive. For future work, we plan to extend the model by combining other predictive techniques to design a suit of more comprehensive, integrated approaches to the metrics of security.



---

*Source: 5787102-2018-08-02.xml*