A scalable algorithm for network reachability analysis with cyclic attack graphs

Abstract

Today, it is indispensable for us to know our IT infrastructure’s security level to make rational decisions to protect it from malicious attacks. However, the ever-growing scale and complexity of our infrastructures make it difficult. One available approach is attack-graph analysis, a model-based algorithm that generates a directed graph called an attack graph composed of possible attack actions and their AND/OR combinations. An attack graph allows us to identify the logical possibility of cyber-attacks. Unfortunately, attack graphs lack quantitative information, such as the likelihood of a successful attack – the reachability. Meanwhile, some advanced approaches, such as the Bayesian attack-graph, compute reachabilities with an attack graph. Still, those methods have problems in the scalability and the handling of cycles contained in attack graphs. This study proposes and examines another approach named reachability-graph analysis. A reachability graph is a directed graph obtained from an attack graph by which we can compute the reachabilities. It is extremely fast to generate, thus applicable to large-scale network analysis. Furthermore, this method allows cycles in attack graphs. Such a scalable algorithm has been awaited for over a decade; it generates probabilistic security metrics and is guaranteed applicable to any cyclic AND/OR graphs. We compare our approach’s computational efficiency with the Bayesian attack-graph. Also, we apply our approach to large-scale, cyclic attack graphs. Several theoretical properties with proofs and the computational complexity of our approach are examined too.

Keywords

Attack graph cyclic attack graph Bayesian attack graph network security metrics network reachability analysis

1. Introduction

Today, we can easily find various reports telling us the rise of cyber-attacks and the relevant damages to our society [6,9,34]. It is indispensable for us to know the security level of our IT infrastructure on which we depend. That knowledge is the basis for rational decision making to protect ourselves. However, the ever-growing scale and complexity of the IT infrastructures make it difficult to analyze its security. For example, it is not uncommon to see a computer network composed of thousands of machines, and that each node contains multiple vulnerabilities to be exploited. The number of logically possible combinations of the exploits is astronomical.

One available approach is attack-graph analysis [32]. Attack-graph analysis is a model-based algorithm that generates and analyzes a directed graph called an attack graph. We can obtain an attack graph from the network topology and its configuration, including the information about the distribution of vulnerabilities. The node in the graph represents an attack action, and a “path” between two nodes corresponds to a sequential attack action procedure. Attack graphs enable us to identify the potential of cyber-attacks.

Due to resource limitations, we need to prioritize cybersecurity investments in general. Unfortunately, attack graphs lack the quantitative information required for such prioritization. Our interest is in the likelihood of a successful attack – the reachability, which is quantitative. There are many studies approaching reachabilities in the broad sense. For example, Mehta et al. [22] proposed a method processing an attack graph as a kind of Markov chain, but an attack graph is an AND/OR graph, and AND combinations of events are not expressible as a Markov chain. Sawilla and Ou [35] propose a proxy metric considering AND combinations of events. However, the metric is not interpretable as a probability. Bayesian attack graphs [10,20,39] can calculate reachabilities as probabilities while handling AND/OR combinations of events. The remained problems are the scalability and the handling of cycles in attack graphs; Bayesian attack graphs are defined as acyclic graphs, although general attack graphs are cyclic. It is still challenging to analyze the security of a network with the realistic scale and cyclic network topology.

In this study, we propose yet another approach named reachability-graph analysis. A reachability graph is a directed graph obtained from an attack graph. It enables us to compute reachabilities as probabilities, not as proxy metrics. It is extremely fast to generate, thus applicable to large-scale network security analysis. Also, it applies to attack graphs with cycles that Bayesian attack graphs cannot handle. We examine its performance and characteristics, including configurable filter functions used to define reachabilities.

The major contributions of this study are as follows:

To the author’s best knowledge, the proposed algorithm is the first scalable one that calculates probabilities and applies to cyclic attack graphs with AND/OR nodes.

This study also articulates a class of extensible metrics provided with a suite of mathematical proofs. It enables further development of security metrics with the desirable properties above.

Section 2 refers to the relevant prior studies and quickly summarizes them. Section 3 defines the problem we solve in this study, with the definition of attack graphs. Section 4 explains two approaches: the Bayesian attack graph and the reachability graph. The latter is our proposed approach. In Section 5, we examine these approaches with two numerical experiments. The first experiment compares the computational efficiency of our approach with Bayesian attack graphs. The second experiment shows the performance of our approach applied to large-scale networks with cyclic topology. Then, after discussing the relevant theoretical topics, including the computational complexity and the extensibility of our approach, we make conclusions.

2. Background

Phillips and Swiler [32] proposed the first comprehensive framework of attack graph analysis, though their approach requires an exponential volume of computation to generate the graph [37]. Later on, Ammann et al. [3] introduced the concept of exploit dependency graph [27], which enables the attack-graph generation in polynomial time. Based on these foundational studies, the current major approaches are divided into two types of attack-graph definition: TVA (Topological Vulnerability Analysis) proposed by Jajodia and Noel [18] and Logical Attack Graph proposed by Ou et al. [28–30]. Both approaches leverage the concept of exploit dependency in common. We adopt the definition by Albanese et al. [2] as the basis of our approach in this study, which is in the school of TVA.

An attack graph describes the qualitative inference results about the potential attacks. In essence, an attack graph is a kind of AND/OR graph. It is a directed graph where each node in it denotes AND/OR bindings of its parents. Attack graphs lack any quantitative information such as successful attack likelihood or monetary loss. We need some additional approaches to make relevant risks comparable.

Idika and Bhargava [17] propose to use the combination of simple metrics such as the mean length of attack paths, the standard deviation of them, and the count of them. Though, their metrics are qualitative inherently. For example, can we determine if a network’s risk is twice as high when we see the doubled number of attack paths? The algorithm by Mehta et al. [22] computes the pseudo PageRank like Google’s. Each node’s rank metric in an attack graph denotes the expected probability of the coupled event occurrence. The critical limitation is that the metric cannot handle AND combinations of events. Sawilla and Ou [35] propose another metric named AssetRank. This metric considers the AND/OR combinations of events. On the other hand, the value of AssetRank is not a probability. Wang et al. [38] define a set of intuitive calculation rules for event occurrence probabilities. Their approach can handle both of AND/OR combinations of events. However, it assumes that every event on the graph is independent. The algorithm proposed by Homer et al. [13,14] overcomes all of these issues. The problem left is that the computational complexity explodes in the worst case.

To date, the Bayesian attack graph [10,20,39] seems to be the most sophisticated approach for attack-graph based security metrics calculation. A Bayesian attack graph is an attack graph represented as a Bayesian network [31] and can compute the occurrence probability of the non-independent events coupled with nodes.

A Bayesian network is a joint probability distribution expressed as a DAG (Directed Acyclic Graph) of stochastic variables. Belief propagation is a well-known inference algorithm proposed by Pearl [31]. It is an exact inference algorithm applicable to Bayesian networks with polytree structure. At the same time, it is also empirically known as an approximate inference algorithm applicable to arbitrary Bayesian networks [24]. The computational complexity of belief propagation is almost linear in many cases.

The key idea in the Bayesian attack graph is to leverage conditional probability distribution. In a Bayesian network, we can formulate a mapping from the AND/OR combination of events in an attack graph to the corresponding node with an appropriately defined conditional distribution.

Liu and Man [20] proposed the earliest attempt for the Bayesian attack graph. Each variable in their Bayesian attack graph corresponds to a host’s state, such as the host is compromised or not. Their approach does not care about the difference between AND/OR combinations of events. Frigault and Wang [10] proposed to leverage the flexibility of conditional probability distributions to represent the combination of events. Pen Xie et al. [39] examined the use of Noisy-OR and Noisy-AND to map attack graph nodes to Bayesian network nodes. Meanwhile, these prior studies only discussed the theoretical and limited cases of problems. The studies by Poolsappasit et al. [33] and Muñoz-Gonzalez et al. [23] are Bayesian attack graph applications to more realistic scenarios.

As is mentioned above, various researchers have discussed the Bayesian attack graph. However, there remain the following two issues.

The first and prominent issue is scalability. In realistic scenarios, we have to analyze a network composed of thousands of computers. Nevertheless, none of these Bayesian prior studies examined the analysis for such large-scale networks. The exact inference on a Bayesian network is an NP-hard problem [7]. Therefore, it is inevitable to depend on the approximate inference algorithms to process large-scale networks. Regretfully, those approximations are not sufficiently fast. Furthermore, it could be erroneous, and there is no guarantee for the algorithm to terminate in general.

The second issue is the treatment of cycles. By definition, a Bayesian network is a DAG. In contrast, an attack graph can contain cycles. Frigault and Wang [10] assume that the input attack graph is a DAG. Peng Xie et al. [39] never mentioned the cycles in an attack graph. Poolsappasit et al. [33] assume that it is ignorable. Muñoz-Gonzalez et al. [23] refer to the cycles cut algorithm in Wang et al. [38], while Wang’s approach requires multiple, transformed graph evaluations implicitly. In theory, we can regard the approach by Homer et al. [13,14] as a kind of Bayesian attack graph with graph conversion preprocess from cyclic to acyclic, and this conversion also accompanies costly computation alike.

As a whole, we can say that the Bayesian attack graph has considerable weaknesses in the application to practical cases, including large scale, cyclic attack-graphs. We solve these issues with another approach named reachability graph.

3. Problem settings

3.1. Attack graph

At first, let us define attack graphs. We follow the definition in [2].

Definition 1 (Attack graph).

Given a set of exploits E, a set of security conditions C where $E \cap C = \emptyset$ , a require relation $R_{r} \subseteq C \times E$ , and an imply relation $R_{i} \subseteq E \times C$ , an attack graph G is the directed graph $G = (E \cup C, R_{r} \cup R_{i})$ , where $E \cup C$ is the vertex set and $R_{r} \cup R_{i}$ is the edge set. For each attack graph $G = (E \cup C, R_{r} \cup R_{i})$ , initial conditions refer to the subset $C_{i} \subseteq C$ composed of every condition $c \in C$ satisfying $∄ e \in E such that (e, c) \in R_{i}$ , i.e., the set of all the leaves in the graph, whereas intermediate conditions refer to the subset $C ∖ C_{i}$ .

Usually, we use initial conditions as the representation of vulnerabilities of the hosts on a network. The exploits are the nodes representing the AND nodes in an attack graph. The intermediate conditions are the nodes corresponding to the OR nodes. See Fig. 1 shows an example.

Fig. 1.

A small example of an attack graph.

This attack graph implies that the occurrence of $c_{4}$ depends on the occurrence of $e_{1}$ or $e_{2}$ . Also, $e_{1}$ depends on $c_{1}$ and $c_{2}$ , and $e_{2}$ depends on $c_{2}$ and $c_{3}$ . The following formulae in propositional logic represent their relationship: $\begin{array}{l} c_{4} & = e_{1} \lor e_{2}, \\ e_{1} & = c_{1} \land c_{2}, \\ e_{2} & = c_{2} \land c_{3} . \end{array}$ With this graph, we can extract two “paths” for the security condition $c_{4}$ . That is, $c_{1} \land c_{2} \to e_{1} \to c_{4}$ and $c_{2} \land c_{3} \to e_{2} \to c_{4}$ .

We use an attack graph as an input to generate other graph structures discussed in Section 4. Various algorithms are proposed to generate an attack graph [16,19,36]. Most of the algorithms have the polynomial computational-complexity in the size of the network to be analyzed. Based on these prior studies, we assume that the attack graph in need is given.

3.2. Network reachability analysis

Our interest is in the probabilistic quantification of the risks implied by an attack graph. Suppose every node in an attack graph is a Bernoulli variable, i.e., each variable takes a value either True or False. If the node $c_{1}$ has an assigned probability of 0.9 for $c_{1} = True$ , then we interpret it as that the occurrence probability of event $c_{1}$ is 0.9. We call that probability reachability and denote the reachability to node x by “ $reachability (x)$ ”. With this reachability concept, the following definition clarifies the problem which we try to solve:

Definition 2 (Network reachability analysis).

Given an attack graph $G = (E \cup C, R_{r} \cup R_{i})$ , and initial reachabilities $I \subseteq C_{i} \times [0, 1]$ satisfying ${c | (c, r) \in I} = C_{i}$ and $\forall (c_{k}, r_{k}), (c_{k}^{'}, r_{k}^{'}) \in I, c_{k} = c_{k}^{'} ⟹ r_{k} = r_{k}^{'}$ . Let us define a problem in which we identify the “ $reachability (x)$ ” for every $x \in E \cup C$ . We call this problem a network reachability analysis.

This definition is incomplete in the sense that there is a freedom of choice for the “natural” assignment of reachabilities to nodes in an attack graph. We leverage this flexibility to examine several different approaches to the problem.

4. Approach

4.1. Bayesian attack graph

As preparation, we define several terms relevant to Bayesian network. In this subsection, we use capital variables such as $X_{1}, \dots, X_{n}$ to denote Bernoulli variables. Then, a Bayesian network is a joint distribution of $X_{1}, \dots, X_{n}$ defined as $\begin{array}{l} P (X_{1}, \dots, X_{n}) = \prod_{k} P (X_{k} | parents (X_{k})), \end{array}$ where (1) “ $parents (X_{k})$ ” denotes the subset of ${X_{1}, \dots, X_{n}}$ satisfying $\begin{array}{l} P (X_{k} | X_{1}, \dots, X_{k - 1}, X_{k + 1}, \dots, X_{n}) = P (X_{k} | parents (X_{k})), \end{array}$ and (2) the graph composed of $X_{1}, \dots, X_{n}$ and their dependencies is a DAG, i.e., the set of all ascendants of any $X_{k}$ does not contain $X_{k}$ . A leaf $X_{k}$ in the graph is supposed to have a prior distribution $P (X_{k})$ . On the other hand, every node $X_{k}$ with parents has a conditional probability distribution $P (X_{k} | parents (X_{k}))$ .

In this study, we focus on only two types of conditional distribution: Noisy-OR and Noisy-AND. Let us define the set $τ (X_{k}) = {X_{i} | X_{i} \in parents (X_{k}), X_{i} = True}$ . The Noisy-OR distribution function of $X_{k}$ is defined as follows: $\begin{array}{l} P (X_{k} | parents (X_{k})) = \{\begin{matrix} 1 - \prod_{μ \in {μ_{k, i} | X_{i} \in τ (X_{k})}} (1 - μ) & (τ (X_{k}) \neq \emptyset) \\ 0 & (otherwise), \end{matrix} \end{array}$ where each $μ_{k, i} \in [0, 1]$ is predefined for each pair composed of variable $X_{i} \in parents (X_{k})$ and $X_{k}$ . We denote this conditional distribution by “ $noisy‐OR (X_{k}, {μ_{k, 1}, μ_{k, 2}, \dots})$ ”. Similarly, The Noisy-AND distribution function of $X_{k}$ is defined as follows: $\begin{array}{l} P (X_{k} | parents (X_{k})) = \{\begin{matrix} \prod_{ν \in {ν_{k, i} | X_{i} \in τ (X_{k})}} ν & (τ (X_{k}) = parents (X_{k})) \\ 0 & (otherwise), \end{matrix} \end{array}$ where each $ν_{k, i} \in [0, 1]$ is predefined for each pair composed of variable $X_{i} \in parents (X_{k})$ and $X_{k}$ . We denote this conditional distribution by “ $noisy‐AND (X_{k}, {ν_{k, 1}, ν_{k, 2}, \dots})$ ”. Diez and Druzdzel [8] discuss the detail of these conditional distributions.

With the terms introduced above, we define a Bayesian attack graph as follows. Here, we simplify the definition in Poolsappasit et al. [33] and Muñoz-Gonzalez et al. [23].

Definition 3 (Bayesian attack graph).

Given an attack graph $G = (E \cup C, R_{r} \cup R_{i})$ where $E = {e_{1}, \dots, e_{m}}$ and $C = {c_{1}, \dots, c_{n}}$ , and initial reachabilities $I \subseteq C_{i} \times [0, 1]$ satisfying ${c_{k} | (c_{k}, r_{k}) \in I} = C_{i}$ and $\forall (c, r), (c^{'}, r^{'}) \in I, c = c^{'} ⟹ r = r^{'}$ . Let $E_{k}$ be the Bernoulli variable corresponding to node $e_{k}$ in E, and $C_{k}$ be the Bernoulli variable corresponding to node $c_{k}$ in C. Also, let $parents (E_{k}) = {C_{ℓ} | (c_{ℓ}, e_{k}) \in R_{r}}$ for each $E_{k}$ , and $parents (C_{k}) = {E_{ℓ} | (e_{ℓ}, c_{k}) \in R_{i}}$ for each $C_{k}$ . Then, we call the joint distribution defined as follows a Bayesian attack graph: $\begin{array}{l} P (C_{1}, \dots, C_{n}, E_{1}, \dots, E_{m}) = \prod_{X_{k} \in {C_{1}, \dots, C_{n}, E_{1}, \dots, E_{m}}} P (X_{k} | parents (X_{k})), \end{array}$ where $\begin{array}{l} P (X_{k} | parents (X_{k})) = \{\begin{matrix} P (X_{k}) = \{\begin{matrix} r_{k} & (X_{k} = 1) \\ 0 & (X_{k} = 0) \end{matrix} & (X_{k} \in C_{i}) \\ noisy‐OR (X_{k}, {μ_{k, 1}, \dots}) & (X_{k} \in C ∖ C_{i}) \\ noisy‐AND (X_{k}, {ν_{k, 1}, \dots}) & (X_{k} \in E) . \end{matrix} \end{array}$

We have to define the configuration parameters $μ_{k, i}$ and $ν_{k, i}$ for Noisy-OR/AND to obtain a Bayesian attack graph. We omit the discussion how to determine those parameters. As our focus is on the computation after those parameters are supplied, we assume those parameters are given appropriately. Additionally, the input attack graph G is supposed to be a DAG since a Bayesian network is a DAG.

In a Bayesian attack graph, the marginal probability assigned to each node corresponds to the reachability. Various inference algorithms, such as belief propagation, can compute those probabilities. In the definition above, we map AND nodes in an attack graph to the variables with Noisy-AND probability distribution. Similarly, OR nodes are mapped to the variables with Noisy-OR distribution. As Section 4.3.2 in [31] discusses, the computational complexity of each conditional distribution’s marginalization with Noisy-OR/AND scales linearly with the number of parent variables, while it is exponential in general. We use the loopy belief propagation algorithm with this efficient computation for the experiment in Section 5.1.

4.2. Reachability graph

A reachability graph, which we propose here, is a directed graph in another form derived from an attack graph. In a reachability graph, we use the following functions to compute the reachability assigned to each node in an attack graph:

Max-OR function: $max‐OR ({x_{1}, \dots, x_{n}}) = {max}_{k} reachability (x_{k})$ , defined for $\forall {x_{1}, \dots, x_{n}} \subseteq E$ .

Min-AND function: $min‐AND ({x_{1}, \dots, x_{n}}) = {min}_{k} reachability (x_{k})$ , defined for $\forall {x_{1}, \dots, x_{n}} \subseteq C$ .

An arbitrary filter function $f : [0, 1] \to [0, 1]$ , satisfying $\forall v_{1}, v_{2} \in [0, 1], v_{1} ⩽ v_{2} ⟹ f (v_{1}) ⩽ f (v_{2})$ , and $\forall v \in [0, 1], f (v) ⩽ v$ .

With the aid of these functions, we define the reachability graph as follows:

Definition 4 (Reachability graph).

Given an attack graph $G = (E \cup C, R_{r} \cup R_{i})$ where $E = {e_{1}, \dots, e_{m}}$ and $C = {c_{1}, \dots, c_{n}}$ , and initial reachabilities $I \subseteq C_{i} \times [0, 1]$ satisfying ${c | (c, r) \in I} = C_{i}$ and $\forall (c_{k}, r_{k}), (c_{k}^{'}, r_{k}^{'}) \in I, c_{k} = c_{k}^{'} ⟹ r_{k} = r_{k}^{'}$ . For each node $e \in E$ , let $parents (e) = {c_{k} | (c_{k}, e) \in R_{r}}$ . Similarly, let $parents (c) = {e_{k} | (e_{k}, c) \in R_{i}}$ for each node $c \in C ∖ C_{i}$ . With these definitions, we categorize every node $x \in E \cup C$ into the following three types and assign reachabilities respectively:

1. External node: a node $x \in C_{i}$ , with $reachability (x) = r_{k}$ where $(x, r_{k}) \in I$ .

2. Max-OR node: a node $x \in C ∖ C_{i}$ , with $reachability (x) = f_{[x]} (max‐OR (parents (x)))$ where $f_{[x]}$ is the arbitrary filter function defined for each $x \in C ∖ C_{i}$ .

3. Min-AND node: a node $x \in E$ , with $reachability (x) = f_{[x]} (min‐AND (parents (x)))$ where $f_{[x]}$ is the arbitrary filter function defined for each $x \in E$ .

We call the pair of G and its associated reachability defined above as a reachability graph. For convenience in the later discussion, we also define $children (x) = {e | (x, e) \in R_{i}} \cup {c | (x, c) \in R_{i}}$ .

The reachability graph introduced above is ill-defined. For example, in Fig. 2, where we assume that the filter function $f_{[x]}$ is defined as $f_{[x]} (x) = x$ , both the reachability graph A and B give the legitimate reachabilities for the attack graph G. The number in the node represents the reachability for the node.

Fig. 2.

An example of the reachability-graph undecidability.

Also, there is another problem. The initial reachabilities define the reachabilities only for external nodes. We need to compute the reachabilities for other nodes.

We define Algorithm 1 to compute the whole reachability graph uniquely:

Algorithm 1:

Reachability-graph analysis

The following claims hold for Algorithm 1:

Proposition 5.

Every temporal reachability increases monotonically during the process of the algorithm.

Lemma 6.

Suppose we have an input attack graph, and let $C_{i}$ be the set of initial conditions, and $f_{[x]}$ be the filter function defined for each node x in the attack graph. For every temporal and final reachability to $x_{n}$ , there exists a series of nodes $x_{0} \in C_{i}, {x_{1}, \dots, x_{n}} \subseteq E \cup C$ satisfying $\begin{array}{l} reachability (x_{n}) = f_{[x_{n}]} \circ f_{[x_{n - 1}]} \circ \dots \circ f_{[x_{1}]} \circ I (x_{0}) \end{array}$ and composing an acyclic path.

Theorem 7 (Termination of reachability graph analysis).

Given the input attack graph is finite, the procedure of reachability-graph analysis always terminates within finite steps.

Theorem 8 (Confluence of reachability graph analysis).

The resultant reachabilities identified by the reachability-graph analysis is determined uniquely irrespective of the choice of update node in line 10 of the algorithm.

Theorem 8 implies the affinity of this algorithm to parallelism. See Appendix for the proofs.

4.3. The interpretation of reachabilities

Given an attack graph and its associated initial reachabilities, both Bayesian attack graphs and reachability graphs determine the reachabilities to nodes in the graph. However, the interpretation of reachabilities is different. Let us see the detail by calculating the reachabilities for Fig. 3.

Fig. 3.

An input attack-graph for reachability calculation.

Firstly, let us see a simple, intuitive way of reachability assignment following [38].

Remind that an attack graph $G = (E \cup C, R_{r} \cup R_{i})$ contains two types of nodes, the exploits E and the conditions C. Let us define a function $p : (E \cup C) \to [0, 1]$ , which assign individual scores to each node in G. We define the probability P of the event implied by an exploit e or a condition c in G as follows (Be cautious in distinguishing the use of P and p, and that $P (e)$ means $P (E = True)$ .): $\begin{array}{l} P (e) & = p (e) \prod_{c \in parents (e)} P (c), and \\ P (c) & = \{\begin{matrix} p (c) & (parents (c) = \emptyset) \\ p (c) {1 - \prod_{e \in parents (c)} (1 - P (e))} & (parents (c) \neq \emptyset) . \end{matrix} \end{array}$

The definition above follows the approach by Wang et al. [38]. Let us apply this definition to the case in Fig. 3. Suppose that the initial event probability $P (c_{0}) = 1.0$ , and every individual score, such as $p (e_{1})$ and $p (c_{1})$ , equals to 0.8. Then, the probability $P (c_{2})$ is calculated as follows: $\begin{array}{l} P (c_{1}) & = p (c_{1}) P (e_{1}) = p (c_{1}) p (e_{1}) P (c_{0}) \\ = p (c_{1}) p (e_{1}) p (c_{0}) = 0.8 \cdot 0.8 \cdot 1.0 = 0.64, \\ P (e_{2}) & = p (e_{2}) P (c_{1}) = 0.8 \cdot 0.64 = 0.512, \\ P (e_{3}) & = p (e_{3}) P (c_{1}) = 0.8 \cdot 0.64 = 0.512, \\ P (c_{2}) & = p (c_{2}) {1 - (1 - P (e_{2})) (1 - P (e_{3}))} \\ ≃ 0.609. \end{array}$ The probability $P (c_{2})$ is also the $reachability (c_{2})$ determined in this approach. It seems intuitive and easily understandable.

In the Bayesian attack graph, the probability is different. While the approach above assumes that $e_{2}$ and $e_{3}$ are independent, the paths leading to them are identical until halfway through. Therefore, the two are never independent. The correct probability for $c_{2}$ considering their dependencies is as follows (Note that, in this calculation, the scores such as $p (c_{2})$ and $p (e_{2})$ play the role of the configuration parameters $μ, ν$ in Noisy-OR/AND.): $\begin{array}{l} P (c_{2}) & = \sum_{E_{3}, E_{2}, C_{1}, E_{1}, C_{0}} P (c_{2} | E_{2}, E_{3}) P (E_{2} | C_{1}) P (E_{3} | C_{1}) P (C_{1} | E_{1}) P (E_{1} | C_{0}) P (C_{0}) \\ ≃ 0.557. \end{array}$

Now, let us see how our approach, the reachability graph analysis, handles the reachability in yet another different way. Here, we use filter functions $f_{[x]} (v) = p (x) \cdot v$ . Then, the reachability to $c_{2}$ is calculated as follows (This calcuation omits the detailed process of the algorithm.): $\begin{array}{l} reachability (e_{1}) & = f_{[e_{1}]} (min‐AND ({c_{0}})) = 0.8 \cdot 1.0 = 0.8, \\ reachability (c_{1}) & = f_{[c_{1}]} (max‐OR ({e_{1}})) = 0.8 \cdot 0.8 = 0.64, \\ reachability (e_{2}) & = f_{[e_{2}]} (min‐AND ({c_{1}})) = 0.8 \cdot 0.64 = 0.512, \\ reachability (e_{3}) & = f_{[e_{3}]} (min‐AND ({c_{1}})) = 0.8 \cdot 0.64 = 0.512, \\ reachability (c_{2}) & = f_{[c_{1}]} (max‐OR ({e_{2}, e_{3}})) = 0.8 \cdot 0.512 \\ ≃ 0.410. \end{array}$

As we can see, the reachability graph has a different probability assignment.

The difference between these three cases comes from handling events convergence at node $c_{2}$ . Figure 4 and the Venn diagram in Fig. 5 explains this difference more intuitively.

Fig. 4.

Another attack graph for reachability calculation.

Fig. 5.

The overlapping volume of convergent events.

Figure 5 shows the volume of overlapped attacks in node $e_{2}$ in Fig. 4. By assumption, attackers start at node $c_{0}$ and penetrate deeper into the attack graph. To get through node $e_{2}$ , the attacker must achieve both of $c_{1}$ and $c_{2}$ . Then, let us assume that twelve attackers had achieved $c_{1}$ , and ten attackers had achieved $c_{2}$ . Under this circumstance, how many attackers can succeed to get to $e_{2}$ ? It depends on the case. When the two groups have no common part, no one can get to $e_{2}$ . On the other extreme, if the ten achievers are a subset of the twelve achievers, then the ten attackers will get to $e_{2}$ . Algorithm 1 always assumes this complete overlap at AND/OR nodes in the graph. In contrast, the approach by Wang et al. [38] assumes that this overlap is limited to the volume determined as the product of reachabilities at the precondition nodes. The Bayesian attack graph determines this overlap depends on the overlaps of paths up to the AND/OR node. This difference in the overlapping volume is the root cause of the reachabilities difference. At AND nodes, the small overlap means less reachability. At OR nodes, the small overlap means more reachability since it enlarges the volume of $c_{1} \cup c_{2}$ . These characteristics and Lemma 6 imply that, in reachability graph analysis, the accumulated difficulty of attacks in the most accessible path determines reachability. In our approach, the reachability “0.410” indicates that 41% of the attackers going sequentially along with its best course can accomplish the goal, while other approaches assume the parallel attempts by an attacker.

This difference in the reachability semantics also affects how we can decrease them. In practice, if we want to strengthen the system’s security, we have to focus on the weakest part of the system. However, in the usual approach like Bayesian attack graph, we can lower the reachabilities without focusing on that. In contrast, it is required in the reachability graph analysis since its reachabilities are determined by the path composed of the most advantageous sequence for the attacker. This point is a discreet but substantive virtue of our approach.

5. Experiment

5.1. Performance comparison

This subsection compares the computational efficiencies of the Bayesian attack graph and the reachability graph through a numerical experiment. Figure 6 shows the general structure of the networks to be analyzed in this experiment.

Fig. 6.

General structure of the experimental network.

The network comprises four layers – databases, servers, gateways, and clients – and the Internet connection. We assume that the attacker starts the penetration from the Internet. The network topology forms a combination of overlapped trees, i.e., non-polytree DAG. Also, we assume each node except the Internet has at least one vulnerability.

Following the structure above, we examine five classes of networks with the number of nodes defined in Table 1.

Table 1

Network size parameters for the experiment

Class name	nw1	nw2	nw3	nw4	nw5
# of databases	1	2	3	3	3
# of servers	2	3	4	4	4
# of gateways	3	3	4	4	5
# of clients	24	30	48	56	80
# of clients per gateway	8	10	12	14	16
# of vulnerabilities per client	2	3	3	4	4
# of total vulnerabilities	58	86	119	155	196
# of attack graph nodes	267	420	641	821	1,114
# of attack graph edges	382	588	921	1,257	1,740
# of nodes + edges	649	1,008	1,562	2,078	2,854

The number of total vulnerabilities is the total of unique vulnerabilities over the network under this consideration. Note that we assume that client nodes share some vulnerabilities since most client computers have the same configuration. More detail is given in the Appendix.

We apply the two approaches in Section 4 to randomly generated attack graphs explained above. The data set comprises five classes defined in Table 1, where each class is a set of fifty networks. Therefore, we examine 250 cases overall. For the Bayesian attack graphs, the configuration parameters μ and ν for Noisy-OR/AND are set to one. For the reachability graphs, we assign a filter function $f_{[x]} (v) = a_{x} \cdot v$ for each AND node x where $a_{x} \in [0, 1]$ is a constant defined for x. For OR nodes, we assign the filter function $ident (v) = v$ . More detailed information are available in the attached program for this article.

We compute the reachabilities to all the nodes in an attack graph by the two approaches. Both algorithms are implemented in Python 3.7 and are executed by cpython-3.7.3. The served hardware has an Intel Core i7-9750HQ 2.6 GHz processor (6 cores with HyperThreading) and 32GB memory. Figure 7 to Fig. 9 show the comparison results. In Fig. 7 and Fig. 8, the bars are the average times in seconds to calculate all the reachabilities, and the error bars represent the standard deviation.

Fig. 7.

Processing times of Bayesian attack graphs.

Fig. 8.

Processing times of reachability graphs.

Figure 9 shows the box plot with 4-quantiles in which the processing times are compared. Y-axis values show the ratios calculated by “the processing time in Bayesian attack graph” / “the processing time in reachability graph”. The circles are outliers with values either more than $Q 3 + 1.5 (Q 3 - Q 1)$ or less than $Q 1 - 1.5 (Q 3 - Q 1)$ where $Q 3$ and $Q 1$ denote the third and the first quantile, respectively.

Fig. 9.

Comparison of processing times.

It is easy to see that the reachability-graph analysis outperforms the Bayesian attack graph based approach. While the reachability graph analysis scales linearly in the size of the attack graph, the Bayesian attack graph based approach does not. Of course, their performance is not directly comparable since their semantics are different. Still, this clear advantage could make our approach an attractive alternative to the Bayesian attack graph.

5.2. Applicability to large-scale, cyclic networks

In this section, we apply the reachability-graph analysis to large-scale networks. Table 2 shows the size parameters of the networks.

Table 2
Network size parameters for the large-scale experiment

Class name nw6 nw7 nw8 nw9 nw10

# of databases 6 6 8 8 8

# of servers 8 12 16 16 16

# of gateways 12 16 24 32 64

# of clients 576 800 1,320 2,176 3,840

# of clients per gateways 48 50 55 136 240

# of vulnerabilities per client 8 12 16 20 24

# of total vulnerabilities 1,178 1,818 3,016 4,872 8,440

# of attack graph nodes 9,629 16,901 33,233 65,313 138, 769

# of attack graph edges 18,702 35,990 75,496 154,536 336, 264

# of nodes + edges 28,331 52,891 108,729 219,849 475, 033

Class name	nw6	nw7	nw8	nw9	nw10
# of databases	6	6	8	8	8
# of servers	8	12	16	16	16
# of gateways	12	16	24	32	64
# of clients	576	800	1,320	2,176	3,840
# of clients per gateways	48	50	55	136	240
# of vulnerabilities per client	8	12	16	20	24
# of total vulnerabilities	1,178	1,818	3,016	4,872	8,440
# of attack graph nodes	9,629	16,901	33,233	65,313	138, 769
# of attack graph edges	18,702	35,990	75,496	154,536	336, 264
# of nodes + edges	28,331	52,891	108,729	219,849	475, 033

Other experiment configurations are as same as the previous experiment, i.e., 50 cases per class. Figure 10 shows the result.

Fig. 10.

Processing times of large-scale reachability graphs.

The attack graphs in the largest case have more than 130,000 nodes and 330,000 edges. Bayesian attack graph based approach cannot handle this class of networks due to its computational cost. We can say that reachability-graph analysis has the potential to analyze practical scale problems.

In addition to the above experiment, let us see how much the cycles in an attack graph affect the performance. For the purpose, we replace some of the gateway nodes in nw10 with hub nodes and cut some connections between clients and the Internet. In brief, when a node connects to a hub node, the hub node also connects to the node. As a result, the topology in (A) is transformed into (B), as shown in Fig. 11. This modification increases the topological distance from the Internet to the clients and enforces cycles handling relevant to them.

We apply this transformation to the fifty networks in nw10 while varying the number of hubs from 0 to 56, in 8 increments. Figure 12 shows the distribution of the processing times with the reachability-graph analysis of those networks.

Fig. 11.

Replacement of a gateway with a hub.

As the number of hubs increases, the processing times are getting longer. Nevertheless, the performance degradation is limited. Even when most of the gateways are replaced with hubs, it does not exceed the doubled processing time in the baseline case where no hubs. This result is a natural consequence implied by Lemma 6. The lemma guarantees that the analysis process does not loop the graph repeatedly.

Fig. 12.

Processing times of cyclic reachability-graphs.

6. Discussions

6.1. Computational complexity

Belief propagation applied to polytree has the computational complexity of $O (N exp (w))$ where N denotes the number of nodes in the graph, and w is the maximum number of parent nodes subject to marginalization. The complexity of loopy belief propagation depends on the problem. While it works as same as belief propagation in the best case, the process never stops in the worst case. In the Bayesian attack graph, the width parameter w can be considerable since it corresponds to the number of clients connected to a server or a gateway. It seems the leading cause of the non-linear behavior seen in Fig. 7.

In contrast, reachability-graph analysis always terminates within finite steps. The worst-case computational complexity is $O (N^{2})$ , where N denotes the number of nodes in the graph. We can derive this estimation as follows. Lemma 6 assures that each temporal reachability will be updated at most N times since the value derives from a chain of filter functions that cannot be longer than N. Therefore, even in the worst-case, the update count of reachabilities will not exceed $N^{2}$ .

In most cases, the reachability at a node will be updated just several times. Due to the monotonicity guaranteed by Proposition 5, any update requires the propagation of increased reachability. On the other hand, as the “while” iteration in Algorithm 1 goes further, the propagated reachability weakly decreases since filter functions satisfy $f (v) ⩽ v$ . It means that the late-propagated reachabilities are getting less capable of updating.

Figure 13, showing the update counts per node in the acyclic cases in Section 5, backs up the estimation above. The update counts per node keep around 1.0. In short, we can expect that the computational complexity in simple acyclic attack graphs is nearly linear. However, this estimation focuses on the update counts per node, and it is different from the actual processing times per node. The latter result is shown in Fig. 14. The processing times get increase as the graphs get larger. Note that the size of “nw6” is about ten times larger than “nw5.” This result implies that the time complexity of the algorithm is not linear. It depends on various factors, including, but not limited to, the topological structure of the attack graph, the distribution of initial reachabilities, and the order of element extraction at line 10 in the algorithm. These properties contribute to the count of reachability calculations performed at line 12 and 14. Figure 15 shows the averaged counts of these calculations per node. We can see the increase in evaluation counts, which is the main cause of the non-linear change in the processing times.

Fig. 13.

Update counts per node in acyclic attack graphs.

Fig. 14.

Processing times per node in acyclic attack graphs.

Fig. 15.

Evaluation counts per node in acyclic attack graphs.

As Fig. 12 shows, cycles do not affect the discussion above so much. Figure 16 to Fig. 18 clarify the performance detail.

Fig. 16.

Processing timers per node in cyclic attack graphs.

Fig. 17.

Update counts per node in cyclic attack graphs.

Fig. 18.

Evaluation counts per node in cyclic attack graphs.

6.2. Variations in filter functions

In Section 5, we used the simple filter function $f_{[x]} (v) = a_{x} \cdot v$ where $a_{x} \in [0, 1]$ is a constant chosen for each x. This is not the only form of filter functions available for use. The necessary and sufficient requirements for any filter function f are (1) $\forall v \in [0, 1], f (v) ⩽ v$ , and (2) $\forall v_{1}, v_{2} \in [0, 1], v_{1} ⩽ v_{2} ⟹ f (v_{1}) ⩽ f (v_{2})$ . One of such legitimate functions is the sigmoid function with shift $\begin{array}{l} ς_{a} (v) = \frac{1}{1 + e^{- a (v - c_{1})}} - c_{2}, \end{array}$ where $0 ⩽ a, c_{1}, c_{2}$ . We can use this function to express attacks causing resource starvation because the sigmoid function’s output increases drastically when the input exceeds some threshold. This behavior resembles DoS attacks. In a similar way, attacks depriving finite resources can be handled with output capped functions like as follows: $h_{a} (v) = min {a, v}$ where $a \in [0, 1]$ . This function $h_{a} (v)$ limits the number of successful attacks at node v. It corresponds to a situation where many attackers are trying to seize a limited number of resources such as processors, network interfaces, and other physical devices.

In this study, we limit reachability within $[0, 1]$ . However, we can remove this limitation without losing the properties implied by Lemma 6, Theorem 7, and Theorem 8. This limitation is introduced to make reachabilities comparable with probabilities. When we use the most simple filter function, $f_{[x]} (v) = v$ , and also remove that limitation, the reachability is equivalent to the skill metric discussed in [4].

6.3. Monotonicity of reachability-graph analysis

Let both $v = (v_{1}, \dots, v_{n})$ and $w = (w_{1}, \dots, w_{n})$ be vectors in $R^{n}$ . If the two vectors v and w satisfy that $v_{i} ⩽ w_{i}$ for every $i \in {1, \dots, n}$ , then we say v is less than or equals to w and denote it by $v ⩽ w$ . Additionaly, let $F : R^{n} \to R^{m}$ be a function which satisfies $F (v) ⩽ F (w)$ whenever $v ⩽ w$ . Then, we say that F is monotonic.

We can regard the initial reachabilities in a reachability-graph analysis as a vector. Similarly, we can interpret the process of reachability-graph analysis as a function that maps an initial reachability vector to another reachability vector representing the whole reachabilities in a graph. Under this interpretation, the reachability-graph analysis function F satisfies $F (I_{1}) ⩽ F (I_{2})$ for any pair of initial reachabilities $I_{1} ⩽ I_{2}$ . That is, the reachability-graph analysis is monotonic about the initial reachabilities and the resultant reachabilities. This property derives immediately from Lemma 6 and the monotonicity of max-OR, min-AND, and the filter functions.

6.4. Other related works

In this subsection, we refer to recent studies not mentioned in Section 2. By comparing with them, we clarify why we stick to scalable, probability calculation algorithms applicable to attack graphs as cyclic AND/OR graphs.

Information security management is a kind of risk management, so it is natural to calculate risks during the process. In general, a risk is defined as the product of a probability and an impact. This explains the fundamental importance of probability calculation. For example, Chung et al. [5] propose a comprehensive framework for virtual network systems security management, in which attack probability calculation virtually equivalent to that of [38] is incorporated. The studies by GhasemiGol et al. [12] and Aksu et al. [1] also use the same calculation rules. As these prior studies indicate, probability calculation algorithms can provide a basis for other advanced studies. Our study proposes another type of probability, and it could be an alternative to the existing one to broaden our risk understandings.

Cyclic structures in an attack graph make security metrics calculation difficult. If we somehow unravel those cycles, the problem gets relatively easy. The algorithm by Wang et al. [38] contains such cycle elimination applied before probability calculation. Yousefi et al. [40] propose to unravel an attack graph to a set of attack paths; such a graph conversion enables further applications, for example, Q-learning over attack graphs [41]. However, cycle elimination might cause unintended biases since it implies the selection of specific attack paths. Also, cycle unraveling easily brings computational explosion. In one aspect, cyclic structures are the by-product of information compression to make an attack graph compact. Appropriate handling of cyclic structures is inherent and indispensable for practical attack graph analysis.

It is needless to say the importance of scalability. But, we have a trade-off between the expressiveness of problems and the scalability of applicable algorithms. HARM [11,15] is a well-established approach, highly scalable and applicable to cyclic attack graphs; with it, we can calculate probabilities too. The essence of HARM is on its hierarchical structure. That is, it restricts the form of attack graphs. As a consequence, AND/OR combinations of nodes cannot appear freely; those locations are limited in the peripheral portions of the whole graph. This constraint makes efficient, dynamic programming like algorithms work. At the same time, it cannot fully leverage the expressiveness of AND/OR combinations of nodes, especially in the network topological structure description. The mixture of AND/OR combinations is closely related to the rich expressiveness of Datalog used in MulVAL [28–30] and is the vital basis for practical attack templates. In short, HARM chooses the scalability at the cost of attack templates expressiveness. Conversely, our study puts more emphasis on expressiveness.

In comparison to the prior studies above, the work by Matthews et al. [21] strongly resembles our study at a glance; they proposed “Cyclic Bayesian Attack Graphs.” However, their description is very confusing. Firstly, the “Bayesian attack graph” defined in their work is not that of [10,20,23,39] but is equivalent to the one given partly in [38], i.e., not a Bayesian network. Secondly, they claim that their algorithm’s worst-case computational complexity is $O (n^{2})$ where n denotes the number of nodes in the attack graph; it is dubious since they also say that their algorithm is “detecting all attack paths.” The algorithm adopts depth-first search to enumerate attack paths while avoiding infinite recursion by checking if the searched node “has been visited already.” If the algorithm enumerates all the attack paths, then its worst-case computational complexity is exponential. If not, it means unintentionally omitted attack paths exist, i.e., it fails to handle cycles correctly. The consequence changes depending on how we interpret the phrase “visited already.” In any case, it is difficult to accept their claim literally.

Overall, our study is the first one satisfying all the following requirements together: (1) applies to cyclic AND/OR attack graphs, (2) calculates probabilities, and (3) scales well.

Finally, we would like to refer to the studies by Nguyen and Nicol [25,26]. Their studies are based on uncertain graphs; an uncertain graph is a probabilistic distribution of deterministic graphs. This framework defines a cyclic attack graph as a probabilistic distribution of acyclic attack graphs. When we want to calculate the reachability to a node in an attack graph, in theory, we enumerate every possible acyclic graph and check the path’s existence on each graph. Then, determine the reachability as the weighted sum according to each acyclic graph’s existence probability. The two studies elaborate on the Monte-Carlo sampling strategy for uncertain graphs. Though it seems not scalable so far, it is a very different, challenging approach. Their analysis suggests yet another frontier.

6.5. Limitations

The experiments shown in Section 5 are simplified miniatures of practical situations; each host is represented as a small-scaled attack graph (see Appendix for the detail). In practice, one host can hold hundreds or more vulnerabilities, and its attack graph gets larger too. Also, the topological structure of subject networks can be more complex. These in-situ conditions worsen the performance of our algorithm. Though our approach could outperform existing ones, it does not guarantee unconditional applicability to actual cases.

The loopy belief propagation compared with our algorithm is implemented solely in Python by the author. There could be far more efficient implementation. In that case, the performance ratio shown in Fig. 9 changes. However, any implementation cannot overcome the non-linear complexity of Bayesian network inference.

The reliability of the inference result depends on many factors. At least, the initial reachabilities and the filter functions should be determined carefully. The parameters used in the experiments are not validated in the field. The popular way to assign those parameters in the literature is CVSS based pseudo probability calculation, e.g., [4]. Note that it is a qualitative approach inherently. There is no guarantee that the doubled value of the pseudo probability means the doubled likelihood. One practical approach is regarding every calculation as a kind of What-If analysis. In that case, the reachability-graph analysis generates quantitative results based on the assumption.

7. Conclusions and future work

This study has examined network security analysis methods based on an attack graph. While a simple attack graph applies mainly to qualitative security analysis, advanced approaches enable quantitative security analysis based on an attack graph. The Bayesian attack graph based approach is the representative one. We pointed out several issues about that approach. With that approach, large-scale network analysis is impractical due to its computational load. Also, it cannot handle cyclic structure in an attack graph. In contrast, the proposed approach – reachability-graph analysis – scales well and can handle cycles in an attack graph. Our approach shows thousands of times faster results in the experiment compared to the Bayesian attack graph based approach. Besides, we have shown several other properties of this approach, including the termination and the confluence of analyses and the extensibility enabled by filter functions. It is also guaranteed to be monotonic to the increase in initial reachabilities. Collectively, the proposed approach is yet another tool to analyze network security in practical scenarios.

Security analysis is just a prerequisite for effective risk management. We need to determine the choice of security controls so that we can contain the security risk within an acceptable level. We will discuss this topic in our future works by leveraging the monotonicity of reachability-graph analysis.

Footnotes

Appendix

Here, let us see the proofs of the claims in Section 4.2. Before proceeding to the proofs, we define several terms.

We call a node other than external nodes in an attack graph $G = (E \cup C, R_{r} \cup R_{i})$ an internal node. In Algorithm 1, the temporal reachabilities of internal nodes are initialized to be zero. The algorithm updates each reachability of an internal node whenever the value is inconsistent with its parents’ reachabilities. When an internal node has such inconsistency, we say the node is unstable. On the other hand, if the node has consistent reachability, we say it is stable. We call a graph containing an unstable node an unstable graph – otherwise, a stable graph. The algorithm is a procedure to derive a stable graph from an initial unstable graph. In the following discussion, we call each iteration of the while loop in the algorithm a step.

Finally, let us clarify the composition detail of the experimental virtual networks in Section 5. Figure 19 illustrates the vulnerabilities in a node (host) and the relationship among them as an attack graph.

This partial attack graph contains seven vulnerabilities and is composed of two layers. The attacker penetrates this node through the “In” event. If he/she successfully compromises this node, then he/she approaches to the “Out” event. To accomplish the “Out” event, he/she needs to exploit one of first layer vulnerabilities $v_{1, 1}, v_{1, 2}, v_{1, 3}$ and another one of second layer vulnerabilities $v_{2, 1}, v_{2, 2}, v_{2, 3}$ . Otherwise, $v_{0}$ must be compromised. The left-most vulnerability $v_{0}$ represents an inherent vulnerability in each host, which is a simplified representation of a zero-day vulnerability. Each vulnerability has a non-zero reachability given by initial reachabilities. We compose an attack graph by binding small graphs like in Fig. 19; each small graph is composed of two layers with one zero-day vulnerability and other vulnerabilities.

The Python program for the experiment is available online: https://github.com/kengo-zenitani/2021-reachability-graph-analysis.

Acknowledgments

The author wishes to acknowledge Dr. Junichi Iijima, Professor in the Department of International Digital and Design Management, School of Management, Tokyo University of Science, and Dr. Keisuke Tanaka, Professor in the Department of Mathematical and Computing Science, School of Computing, Tokyo Institute of Technology, for reviewing and providing constructive advice on the drafts of this article.

References

M.U.

Aksu,

M.H.

Dilek,

E.I.

Tatli,

Bicakci,

H.I.

Dirik,

M.U.

Demirezen and

Aykir, A quantitative CVSS-based cyber security risk assessment methodology for IT systems, in: Proceedings – International Carnahan Conference on Security Technology 2017-Octob, 2017, pp. 1–8. ISBN 9781538615850. doi:10.1109/CCST.2017.8167819.

Albanese,

Jajodia and

Noel, Time-efficient and cost-effective network hardening using attack graphs, in: IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2012), IEEE, 2012, pp. 1–12, ISSN 1530-0889. ISBN 978-1-4673-1625-5. doi:10.1109/DSN.2012.6263942.

Ammann,

Wijesekera and

Kaushik, Scalable, graph-based network vulnerability analysis, in: Proceedings of the 9th ACM Conference on Computer and Communications Security – CCS’02, ACM Press, New York, New York, USA, 2002, p. 217. ISBN 1581136129. doi:10.1145/586110.586140.

Cheng,

Wang,

Jajodia and

Singhal, Aggregating CVSS base scores for semantics-rich network security metrics, in: 2012 IEEE 31st Symposium on Reliable Distributed Systems, IEEE, 2012, pp. 31–40, ISSN 10609857. ISBN 978-1-4673-2397-0. doi:10.1109/SRDS.2012.4.

C.J.

Chung,

Khatkar,

Xing,

Lee and

Huang, Network intrusion detection and countermeasure selection in virtual network systems, IEEE Transactions on Dependable and Secure Computing 10(4) (2013), 198–211. doi:10.1109/TDSC.2013.8.

Cisco, Cisco 2018 Annual Cybersecurity Report, Technical Report, 2018. ISSN 19853807. ISBN 9781107671812. doi:10.1002/ejoc.201200111.

Dagum and

Luby, Approximating probabilistic inference in Bayesian belief networks is NP-hard, Artificial Intelligence 60(1) (1993), 141–153. doi:10.1016/0004-3702(93)90036-B.

F.J.

Diez and

M.J.

Druzdzel, Canonical Probabilistic Models for Knowledge Engineering, Technical Report, UNED, Madrid, Spain, ISBN Technical Report CISIAD-06-01, 2006.

EYGM, EY Global Information Security Survey 2018-19, Technical Report, 2019.

10.

Frigault and

Wang, Measuring network security using Bayesian network-based attack graphs, in: 2008 32nd Annual IEEE International Computer Software and Applications Conference, IEEE, 2008, pp. 698–703, ISSN 07303157. ISBN 978-0-7695-3262-2. doi:10.1109/COMPSAC.2008.88.

11.

Ge,

J.B.

Hong,

Guttmann and

D.S.

Kim, A framework for automating security analysis of the Internet of things, Journal of Network and Computer Applications 83 (2017), 12–27. doi:10.1016/j.jnca.2017.01.033.

12.

Ghasemigol,

Ghaemi-Bafghi and

Takabi, A comprehensive approach for network attack forecasting, Computers and Security 58 (2016), 83–105. doi:10.1016/j.cose.2015.11.005.

13.

Homer,

Ou and

Schmidt, A sound and practical approach to quantifying security risk in enterprise networks, Kansas State University Technical Report, 1–15, 2009.

14.

Homer,

Zhang,

Ou,

Schmidt,

Du,

S.R.

Rajagopalan and

Singhal, Aggregating vulnerability metrics in enterprise networks using attack graphs, Journal of Computer Security 21(4) (2013), 561–597. doi:10.3233/JCS-130475.

15.

J.B.

Hong and

D.S.

Kim, Towards scalable security analysis using multi-layered security models, Journal of Network and Computer Applications 75 (2016), 156–168. doi:10.1016/j.jnca.2016.08.024.

16.

J.B.

Hong,

D.S.

Kim,

C.-J.

Chung and

Huang, A survey on the usability and practical applications of graphical security models, Computer Science Review 26 (2017), 1–16. doi:10.1016/j.cosrev.2017.09.001.

17.

Idika and

Bhargava, Extending attack graph-based security metrics and aggregating their application, IEEE Transactions on Dependable and Secure Computing 9(1) (2012), 75–85. doi:10.1109/TDSC.2010.61.

18.

Jajodia and

Noel, Topological Vulnerability Analysis, in: Cyber Situational Awareness, Elsevier, 2010, pp. 139–154. ISBN 9780128136522. doi:10.1007/978-1-4419-0140-8_7.

19.

R.P.

Lippmann and

K.W.

Ingols, An Annotated Review of Past Papers on Attack Graphs, Technical Report, 2005.

20.

Liu and

Man, Network vulnerability assessment using Bayesian networks, in: Data Mining, Intrusion Detection, Information Assurance, and Data Networks Security 2005,

B.V.

Dasarathy, ed., Vol. 5812, International Society for Optics and Photonics, 2005, p. 61. doi:10.1117/12.604240.

21.

Matthews,

Mace,

Soudjani and

Van Moorsel, Cyclic Bayesian attack graphs: A systematic computational approach, in: Proceedings – 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2020, 2020, pp. 129–136. ISBN 9781665403924. doi:10.1109/TrustCom50675.2020.00030.

22.

Mehta,

Bartzis,

Zhu,

Clarke and

Wing, Ranking attack graphs, in: International Workshop on Recent Advances in Intrusion Detection, 2006, pp. 127–144, ISSN 03029743. ISBN 354039723X. doi:10.1007/11856214_7.

23.

Muñoz-González,

Sgandurra,

Paudice and

E.C.

Lupu, Efficient attack graph analysis through approximate inference, ACM Transactions on Privacy and Security 20(3) (2017), 1–30. doi:10.1145/3105760.

24.

K.P.

Murphy,

Weiss and

M.I.

Jordan, Loopy belief propagation for approximate inference: An empirical study, in: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers Inc., 1999, pp. 467–475.

25.

H.H.

Nguyen and

D.M.

Nicol, Estimating loss due to cyber-attack in the presence of uncertainty, in: Proceedings – 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2020, 2020, pp. 361–369. doi:10.1109/TrustCom50675.2020.00057.

26.

H.H.

Nguyen,

Palani and

D.M.

Nicol, An approach to incorporating uncertainty in network security analysis, ACM International Conference Proceeding Series Part F1271 (2017), 74–84. doi:10.1145/3055305.3055308.

27.

Noel and

Jajodia, Managing attack graph complexity through visual hierarchical aggregation, in: Proceedings of the 2004 ACM Workshop on Visualization and Data Mining for Computer Security – VizSEC/DMSEC’04, ACM Press, New York, New York, USA, 2004, p. 109. ISBN 1581139748. doi:10.1145/1029208.1029225.

28.

Ou, A logic-programming approach to network security analysis, PhD thesis, Princeton University, USA, 2005.

29.

Ou,

W.F.

Boyer and

M.A.

McQueen, A scalable approach to attack graph generation, in: Proceedings of the 13th ACM Conference on Computer and Communications Security – CCS’06, ACM Press, New York, New York, USA, 2006, pp. 336–345, ISSN 15437221. ISBN 1595935185.

30.

Ou,

Govindavajhala and

A.W.

Appel, MulVAL: A logic-based network security analyzer, in: Proceedings of the 14th Conference on USENIX Security Symposium, Vol. 14, 2005.

31.

Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., 1988. ISBN 9780080514895.

32.

Phillips and

L.P.

Swiler, A graph-based system for network-vulnerability analysis, in: Proceedings of the 1998 Workshop on New Security Paradigms, 1998, pp. 71–79. ISBN 1-58113-168-2. doi:10.1145/310889.310919.

33.

Poolsappasit,

Dewri and

Ray, Dynamic security risk management using Bayesian attack graphs, IEEE Transactions on Dependable and Secure Computing 9(1) (2012), 61–74. doi:10.1109/TDSC.2011.34.

34.

PwC, Strengthening digital society against cyber shocks: Key findings from The Global State of Information Security^® Survey 2018, Technical Report, 2018. ISSN 2050-6406. ISBN 1474-1784 (Electronic)∖r1474-1776 (Linking). doi:10.1038/nrd3793.

35.

R.E.

Sawilla and

Ou, Identifying critical attack assets in dependency attack graphs, in: European Symposium on Research in Computer Security, Springer, 2008, pp. 18–34. doi:10.1007/978-3-540-88313-5_2.

36.

Singhal and

Ou, Security risk analysis of enterprise networks using probabilistic attack graphs, NIST, 2011.

37.

L.P.

Swiler,

Phillips,

Ellis and

Chakerian, Computer-attack graph generation tool, in: Proceedings – DARPA Information Survivability Conference and Exposition II, DISCEX, Vol. 2, 2001, pp. 307–321. ISBN 0769512127. doi:10.1109/DISCEX.2001.932182.

38.

Wang,

Islam,

Long,

Singhal and

Jajodia, An attack graph-based probabilistic security metric, in: IFIP Annual Conference on Data and Applications Security and Privacy, 2008, pp. 283–296. ISBN 978-3-540-70567-3. doi:10.1007/978-3-540-70567-3_22.

39.

Xie,

J.H.

Li,

Ou,

Liu and

Levy, Using Bayesian networks for cyber security analysis, in: 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), IEEE, 2010, pp. 211–220, ISSN 1530-0889. ISBN 978-1-4244-7500-1. doi:10.1109/DSN.2010.5544924.

40.

Yousefi,

Mtetwa,

Zhang and

Tianfield, A novel approach for analysis of attack graph, in: 2017 IEEE International Conference on Intelligence and Security Informatics: Security and Big Data, ISI 2017, 2017, pp. 7–12. ISBN 9781509067275. doi:10.1109/ISI.2017.8004866.

41.

Yousefi,

Mtetwa,

Zhang and

Tianfield, A reinforcement learning approach for attack graph analysis, in: Proceedings – 17th IEEE International Conference on Trust, Security and Privacy in Computing and Communications and 12th IEEE International Conference on Big Data Science and Engineering, Trustcom/BigDataSE 2018, 2018, pp. 212–217. ISBN 9781538643877. doi:10.1109/TrustCom/BigDataSE.2018.00041.