# It Is Time To Steer: A Scalable Framework for Analysis-driven Attack Graph
Generation

Alessandro Palma<EMAIL_ADDRESS>
Sapienza University of Rome  Marco Angelini<EMAIL_ADDRESS>
Link Campus University, Rome, Italy
Sapienza University of Rome, Rome, Italy

###### Abstract

In modern computer networks where sophisticated cyber attacks occur daily, a
timely cyber risk assessment becomes paramount. Attack Graph (AG) represents
the best-suited solution to model and analyze multi-step attacks on computer
networks, although they suffer from poor scalability due to their
combinatorial complexity.

This paper introduces an analysis-driven framework for AG generation. It
enables real-time attack path analysis before the completion of the AG
generation with a quantifiable statistical significance. We further accelerate
the AG generation by steering it with the analysis query and supporting a
novel workflow in which the analyst can query the system anytime. To show the
capabilities of the proposed framework, we perform an extensive quantitative
validation and we present a realistic case study on networks of unprecedented
size. It demonstrates the advantages of our approach in terms of scalability
and fitting to common attack path analyses.

###### Index Terms:

Attack Graph, Attack Path Analysis, Progressive Computation, Statistical
Significance, Computational Steering.

##  1 Introduction

In today’s digital world, where attackers are evolving smarter and the number
of different vulnerabilities is growing, cyber-attacks are becoming more
complex to mitigate and with a higher impact on organizations’ infrastructure
[1]. In this scenario, it is crucial for any organization to promptly assess
the potential cyber risks their networks are exposed to. This involves
identifying the vulnerabilities in the network’s systems and quantifying the
risk of their potential exploitation, which generally refers to the impact of
one or more exploits and their likelihood to happen [2, 3, 4].

Given the growing complexity of attacks, as multi-step attacks [5] (i.e.,
sequential exploits of different vulnerabilities among network hosts), it is
essential to model the threats in a network. Among the possible threat models
[6, 7], Attack Graph (AG) [8, 9] is a graph-based representation of the
potential attack paths in a network, used to analyze its cyber risk. For
example, an analyst may be interested in determining the most critical hosts
based on the number of paths traversing them. These kinds of analyses are
named _attack path analyses_ as they involve features of the attack paths
[10].

Although AGs are very expressive attack models for attack path analysis, the
first problem they show is the poorly scalable computation of the attack
paths, even for networks of moderate size as AGs may grow exponentially in the
size of network hosts and vulnerabilities [9]. Currently, providing scalable
approaches for attack path analysis is still an open problem, and this hinders
the possibility of promptly providing security strategies to harden the
network. Different works addressed the problem of scalability of AG generation
[11, 12, 13] and attack path analysis [14, 15, 16].

A second emerging problem is that they postulate a classic analysis workflow
in which the generation process step comes first and the analysis comes next,
aggravating the poor scalability of the generation process as it slows down or
completely stops the analysis phase in realistic scenarios.

A final problem concerns the alignment between the current network situation
and the related AG model: while the classic workflow permits the attack path
analysis on the complete set of attack steps, it also implies that any change
in the network needs a re-computation of the whole attack paths set to reflect
such changes, exacerbating the scalability problem. These problems make it
challenging to use AGs for today’s dynamic and large-scale networks.

To overcome them and provide affordable analysis, we contribute a novel
workflow for AG generation and attack path analysis. It leverages the concept
of _statistical significance_ [17] to express the degree of trustfulness of a
partial AG, where not all the attack steps are computed. According to the
foundational aspects of progressive data analysis [18, 19], it progressively
supports attack path analysis during the AG generation, allowing preventive
analyses with quantitative quality-controlled statistically significant
results. To improve the accuracy of analysis performed on partial AGs, we
design a _steering approach_ which automatically accelerates the AG generation
based on the requested attack path analysis. Given a path analysis query from
an analyst, it models the queried attack path features, extracts from them the
features of each single attack step, and uses them to prioritize the
generation of attack paths that answer the analysis query. We evaluate the
speed-up of this process through a comprehensive scalability analysis
performed on hundreds of experiments, varying both the network size and
vulnerability inventories. Finally, we present a realistic case study that
shows the capabilities of the approach in networks whose size cannot be
managed by state-of-the-art solutions.

Summarizing, this paper contributes: i) a novel framework for AG generation
and attack path analysis, based on progressive data analysis; ii) a way to
express statistical significance over partial AGs; iii) a novel approach to
steer the AG generation based on attack path analysis queries; iv) a
comprehensive validation through experimental evaluations for both
statistically significant AG generation and the steering mechanism; v) a
realistic case study demonstrating the possibility of managing large networks
and conducting common attack path analyses.

##  2 Preliminaries

In this section, we present the fundamental notions of attack graphs and
attack path analysis. In particular, we define their components and introduce
the risk model used for the attack path analysis.

###  2.1 Attack Graph Model Definition

An Attack Graph (AG) is a graph-based representation of the possible paths an
attacker can exploit to intrude and compromise an ICT network or, more
generally, an ICT system. To generate it, two inputs are necessary [20, 21,
22]: (i) the network _reachability graph_ (or network reachability matrix),
and (ii) the network _vulnerability inventory_. A network reachability graph
is a directed graph $R=(H,E)$ where nodes are associated with network hosts
$h_{1},\cdots,h_{n}\in H$ and edges represent reachability conditions between
hosts (taking into account firewall and routing rules). Thus, an edge
$e(h_{1},h_{2})\in E$ indicates that host $h_{1}$ can communicate with host
$h_{2}$ through a direct link.

A vulnerability inventory reports the list of network hosts with an associated
set of vulnerabilities, typically obtained by combining the vulnerability
knowledge bases, as the National Vulnerability Database (NVD) [23] by NIST
[24], with vulnerability scanners (e.g., Nessus [25]).

With these inputs, AG modeling consists of the representation of all the
dependencies between hosts and vulnerabilities that can be exploited by an
attacker. Thus, the first step to model AGs is defining the semantics of
attack nodes and edges to represent the structure of the attack steps. In this
paper, we leverage the Topology Vulnerability Analysis (TVA) attack graph
model [26], where the nodes are _security conditions_ and represent the
attacker access privileges in a specific host, while the edges are _exploit
dependencies_ and represent the possible movement of the attacker in case of
successful vulnerability exploit. More formally:

######  Definition 1 (Attack Graph)

An Attack Graph $G=(V,E)$ is a directed multi-graph in which $V$ is the set of
security condition nodes and $E$ is the set of labeled edges where an edge
$e=(v_{1},v_{2},u)\in E$ indicates that the attacker can move from condition
$v_{1}$ to condition $v_{2}$ by successfully exploiting vulnerability $u$.

An example of an AG is reported in Appendix B. Once the AG model is defined,
the next step is the _Attack Graph Generation_ , which is the computation of
the attack paths to analyze the cyber risks of the potential attacks. Attack
paths represent sequences of compromised devices and vulnerabilities exploited
during the attack, and are used to compute scores or metrics like the
likelihood of success of an attack, its impact, or the difficulty of execution
[12, 14, 27].

######  Definition 2 (Attack Path)

An Attack Path $AP=\langle v_{1},u_{1,2},v_{2},u_{2,3},\cdots v_{n}\rangle$ is
the ordered sequence of attacker states $v_{1},\cdots,v_{n}$, interleaved by
the sequence of vulnerabilities $u_{1,2},\cdots,u_{n-1,n}$ which exploit
allows an attacker to move between consecutive states.

When generation ends, the resulting attack paths are used to estimate the
risks of the different multi-step attacks, each one corresponding to a
different path in the AG. The attack path risks may be used either to evaluate
the overall exposure of the network (e.g., by aggregating the risks of the
different paths to have a comprehensive risk evaluation) or to perform
analyses according to specific requirements (e.g., analyzing which are the
attacks that may cause more damages to the network).

Figure 1: Classic attack graph generation and analysis process and the
progressive one. Dashed lines indicate periods in which the analysis is
stalled. PAG=Partial Attack Graph, SPAG=statistically Significant Partial
Attack Graph generation, PAP=Partial Attack Path analysis

###  2.2 Risk Model Definition

To evaluate the cyber risks of an attack path, we leverage the risk
methodology designed by Gonzalez-Granadillo et al. [2]. They consider CVSS
standard metrics [28] to estimate the likelihood and impact of an attack path
$AP$, and calculate the risk according to its standard definition, that is the
dot product of likelihood and impact [29].

$risk(AP)=likelihood(AP)\cdot impact(AP)$ (1)

In particular, the likelihood is calculated using the CVSS-3.1 exploitability
metrics, which are Attack Vector (AV), Attack Complexity (AC), Privilege
Required (PR), and User Interaction (UI). The impact is determined by the last
node in the path, as it represents the attacker’s final goal, and it considers
the CVSS-3.1 impact metrics, that are Confidentiality (C), Integrity (I), and
Availability (A). Likelihood, impact, and risk are all in the range [0,1].
More details about the risk model are available in Appendix C.

According to the defined risk model, the risks of the different attack paths
inform the analysis process and consequent decisions on the mitigation
strategies. For this reason, we evaluate AG expressiveness through the
distribution of the likelihood and impact of its paths.

######  Definition 3 (Vulnerability and Attack Path Features)

Let $AP$ be an attack path and let $u_{1,2},\cdots\in U_{AP}$ the sequence of
its vulnerabilities. We refer to _vulnerability features_ as the CVSS metrics
of a single vulnerability $u_{i,i+1}\in U_{AP}$. Contrary, we refer to _attack
path features_ as the risk metrics for the attack path $AP$ (for the defined
risk model they are likelihood and impact).

With this definition, we refer to _attack path analysis_ as the answer to
queries on attack path features. More formally:

######  Definition 4 (Attack Path Query)

An attack path Query $Q$ is a query that specifies a range of values for one
or more attack path features, potentially in conjunction or disjunction, to
express a human analyst or an automatic process information need.

For example, the query $Q=\\{impact~{}\geq~{}0.9\wedge likelihood<0.5\\}$
represents the need to look at not probable ($<0.5$) but very dangerous ($\geq
0.9$) potential attacks.

Since generating an AG (i.e., enumerating all its paths) and analyzing attack
paths is computationally expensive, we introduce a scalable framework in which
the analysis can be performed before the completion of AG generation, and the
generation can be steered by the analysis queries.

##  3 Overview of Our Approach

According to the classic process of attack path analysis, first defined by
Phillips and Swiler [30] and currently used [8, 31, 32], it is composed of two
principal milestones. Fig. 1-(a) depicts this classic workflow. We can
recognize the first milestone that is the AG generation and the second one is
the analysis of all its attack paths. The foundation of this framework is the
representation of all the possible attack steps to provide a comprehensive
view of the potential attacker’s movements on the network. Once the AG is
generated, the subsequent step is the analysis of its paths, to study the
attacks that can be put in place by an adversary. The problem of enumerating
the attack paths is combinatorial in the number of edges, determining one of
the main sources of their poor scalability. As a consequence, in the case of
medium-large networks, the attack path analysis may never be performed because
of this complexity.

In this paper, we propose a new framework for AG generation and analysis that
leverages the fundamental concepts of _progressive data analysis_ [18, 19],
that we report in Fig. 1-(b). The main idea behind progressive data analysis
is to produce partial results during execution with increasing accuracy to
generate intermediary outputs while the data is still being processed,
potentially targeting interactive times. In the scenario of AG generation and
analysis, the framework we propose considers the computation of _early
partial_ results that would give a coarse-grained approximation of the
complete AG.

At a certain instant $t_{significant}$ (driven by the amount of processed
data), the partial AG becomes _statistically significant_ (SPAG), in the sense
that it is a good statistical approximation of the complete AG. Statistical
significance must take into account the AG components that may vary in
different networks or even that may change over time. For this reason, it must
be evaluated on different attacker conditions (privileges on hosts) and
vulnerability distribution. From this moment on, attack path analysis
generates _mature partial_ results, which reflect the final outcome within an
acceptable margin of error, quantifiable through statistical indicators. This
is the first advancement of the proposed framework, that can produce
meaningful results to start exploring the attack paths at interactive time and
continuously, allowing first observations and exploration without incurring
the cost and waiting time of the full generation.

As the progressive AG generation continues to run, there will be a certain
instant $t_{stable}$ when the statistical significance reaches a threshold
that guarantees _definitive partial_ results. In these cases, the attack path
analysis produces results that will no longer change substantially from the
exact and, as such, supporting tasks like confirmatory analysis. This final
part of the workflow runs until the complete AG is generated and/or attack
paths are analyzed. At the same time, the approach hints at the possibility of
leaving out this part, saving computational resources due to the diminishing
return of the generation.

This way of generating AGs allows the analysis of attack paths with
preliminary data informed by quantifiable statistical indicators. However,
given the exponential size of AGs with respect to the network and
vulnerability inventory [9], it may still require a long time to reach the
stability of definitive partial results. For this reason, the proposed
framework contributes a _steering mechanism_ to accelerate the convergence of
the AG generation to the final outcome of any analysis executed during the
generation [33]. This mechanism consists of informing the next step of
generation with the current attack path analysis. For example, if the analysis
query asks for the attack paths with the highest risk, then the steering
mechanism prioritizes the generation of those paths that have high-risk
values. It corresponds to the red blocks on the bottom of Fig. 1-(b).

To automatically steer the generation with the analysis query we cannot
directly query the AG generator, as it is not driven by attack path features.
We leverage Machine Learning (ML) models to learn the vulnerability features
from the structure of the attack paths and consequently prioritize the
generation by selecting the vulnerability according to the learned features.
For this reason, the first phase of AG generation must be agnostic to the
attack path analysis (white blocks in Fig. 1-b) because it is used for
collecting the initial balanced small set of attack paths that will be used to
train the ML model and label attack paths as answers to the query or not.
Consequently, the ML model is trained with the collected labeled attack paths
to predict the vulnerability features that are representative only of attack
paths that answer the query positively. Having obtained the intervals of
vulnerability features that correspond to attack paths answering the query,
they are used as input to the AG generator to prioritize the next generation
of attack paths.

This steering mechanism allows a faster convergence of the partial AG to the
portion of the complete AG that answers the attack path analysis query. In the
next two sections, we describe the details of the statistically significant AG
generation and the steering mechanism, along with the evaluation activities
executed to demonstrate their validity.

##  4 StatAG: Statistically Significant Attack Graph Generation

In this section, we describe how to achieve a progressively convergent
statistically significant AG generation. It enables a new way of managing AGs
with the main advantage of allowing the exploration and analysis of attack
paths in partial AGs, without waiting for the complete generation, potentially
very long due to its combinatorial complexity [8, 9]. The core idea of this
approach, named _Statistically Significant Attack Graph Generation_ (StatAG),
is considering partial AGs being aware of statistical significance that
becomes gradually higher until it reaches its maximum value corresponding to
the complete AG (i.e., the exact result). Fig. 2 reports the workflow of
StatAG.

Figure 2: Workflow for the statistically significant attack graph generation
(StatAG).

The main activity during AG generation is the enumeration of its attack paths.
While existing approaches [11, 34, 35] leverage common algorithms for graph
traversal, i.e., BFS or DFS [36], we generate attack paths using random walks
[37] over the reachability graph. A random walk of length $k$ is a stochastic
process with random variables $X_{1},\cdots,X_{k}$ such that, given a graph
$G=(V,E)$, $X_{i+1}$ is a vertex $v\in V$ chosen uniformly at random from the
neighbors of $X_{i}$. The rationale for choosing random walks to visit the
graph is due to their capabilities of generating unbiased samples [38],
contrary to the classic traversal algorithms, which depend on the chosen
starting node. As a consequence, random walks facilitate a quicker convergence
of the path feature distributions of the partial AG to the complete AG [38] as
we have experimentally proven in Appendix A.

Following the sampling process, the next step involves constructing the
corresponding attack path. Let us remember that the modeled AG is a multi-
graph, therefore multiple edges (i.e., vulnerabilities) may exist between two
nodes, although only one of the multi-edges can be part of an attack path,
according to its definition (see Definition 2). When this happens, the
construction of the attack path involves randomly selecting one vulnerability
uniformly at random, so that the total number of attack paths aligns with the
number of sampled walks.

The collection of attack paths constructed from the sampled walks defines what
we name the partial AG.

######  Definition 5 (Partial Attack Graph)

Let $G=(V,E)$ be a complete Attack Graph, then a Partial Attack Graph
$PAG_{i}=(V_{i},E_{i})$ is an attack graph composed of a subset of nodes
$V_{i}\subset V$ and edges $E_{i}\subset E$ retrieved after $i$ iterations of
random walk sampling.

At this point, the approach iterates toward the generation of other partial
AGs that are progressively added to reconstruct the complete AG, eventually.
At the end of each iteration, we evaluate the statistical significance of the
partial AG that quantifies the degree of its approximation to the complete AG.
If it is acceptable, then the partial AG can be used for the initial
exploration of the AG, along with indicators communicating its degree of
uncertainty. To measure the statistical significance we need to define the
_null hypothesis_ $H_{0}$, which is the claim that no relationship exists
between two sets of data being analyzed [39]. In the context of the proposed
approach, the two sets of data are the attack path features of the partial AG
and the complete AG, and the statistical significance refers to the
probability of rejecting the null hypothesis. To evaluate this probability, we
need to measure the probability $p$ of obtaining test results at least as
extreme as the observed results (namely _p-value_) and the probability
$\alpha$ of rejecting the null hypothesis (namely _significance level_ [40]).
According to these definitions, the partial AG is statistically significant
when the $p\leq\alpha$ [41], with the value of $\alpha$ commonly set to 0.05
[39, 42].

We evaluate the null hypothesis through the Kolmogorov-Smirnov (KS) test [43],
which is a statistical test to compare two data distributions and quantify the
distance between them. In particular, we are interested in evaluating the
distance between the attack path feature distributions of the complete and
partial AGs. Let $\mathcal{D}_{AG}(x)$ and $\mathcal{D}_{PAG}(x)$ be the
distribution of the attack path feature $x$ according to the complete and
partial AG, respectively. Then, the KS distance between the two distributions
is:

$KS(x)=sup_{x}\mid\mathcal{D}_{AG}(x)-\mathcal{D}_{PAG}(x)\mid,$ (2)

where $sup_{x}$ is the supremum function [44], which corresponds to the least
upper bound of the distances between the two distributions of $x$. Using the
KS distance as defined in Equation 2, we can finally define the statistical
significance of partial AGs.

######  Definition 6 (Statistical Significance for partial AG)

Let $AG$ be the complete attack graph and let $PAG_{i}$ be the partial attack
graph generated at the $i^{th}$ iteration.
Let $H_{0}$: $KS(x)>T$ be the null hypothesis where $KS(x)$ is the KS distance
between the distributions of the attack path feature $x$ for the complete and
partial attack graph, and $T$ a predefined distance threshold.
Then, $PAG_{i}$ is _statistically significant_ for the attack path feature $x$
if the $p\leq\alpha$, with $p$ the p-value of the $KS(x)$ and $\alpha$ the
significance level.

Let us note that this definition is appropriate only for a posteriori
evaluation of the statistical significance because it requires the complete
attack graph $AG$. To enable the estimation of the statistical significance in
a real-time application, we need a way to provide its indication during the
progressive execution of the approach. For this purpose, we introduce the
concept of _Attack Path Feature stability_ (or simply stability) to quantify
the variability of the partial results of an attack path feature gathered
during the different iterations. To measure the stability of an attack path
feature $x$, we consider the KS distance between the cumulative distribution
of $x$ until the $i^{th}$ iteration and the one at iteration $i+1$. It
indicates how much the new samples of iteration $i+1$ vary the already sampled
distribution, with the rationale that a higher KS distance corresponds to more
unstable results given the higher variability of the distribution.

######  Definition 7 (Attack Path Feature Stability)

Let $PAG_{i}$ be the partial attack graph of the $i^{th}$ iteration of the
approach and let $\mathcal{D}_{PAG_{i}}(x)$ be the cumulative distribution of
the attack path feature $x$ in $PAG_{i}$. Then, the stability $\Delta$ of $x$
over $PAG_{i}$ is:

$\Delta_{PAG_{i}}(x)=1-\mid\mathcal{D}_{PAG_{i-1}}(x)-\mathcal{D}_{PAG_{i}}(x)\mid$
(3)

Given that the KS distances are defined in the range [0,1], we subtract 1 from
the difference of the distances to express the rationale that a higher
stability value corresponds to a more significant partial AG.

In the rest of this section, we validate the theoretical formulation of
statistical significance and its correlation with the attack path feature
stability.

###  4.1 StatAG Validation

To validate StatAG we first present the experimental setting, and then we
analyze the convergence of vulnerability features, attack path features, and
stability distributions.

####  4.1.1 Experimental Setting

We validate StatAG with an experimental setup designed for approaching the
different factors that affect the AG scalability [15, 32]. It consists of
synthetic networks and vulnerability inventories, in which we vary the number
of hosts, vulnerabilities, network topology, and composition of
vulnerabilities per host. Looking at the former, we considered configurations
with up to 20 hosts and 50 vulnerabilities per host, which is the biggest
configuration possible to compute all the paths (complete AG, used as ground
truth) in a reasonable amount of time (in the order of hundreds of hours)
[14]. We then tested $3$ network topologies, including mesh [45], random [46],
and power law [47]. We considered $5$ levels of heterogeneity of
vulnerabilities, varying from 0% (i.e., all vulnerabilities among the hosts
are the same) to 100% (i.e., all vulnerabilities among the hosts are
different) to increase the variability of vulnerability features. Thus, for
each network, we evaluated 15 different configurations, which we varied in 100
statistical variations, for a total of 1500 experiments.

We use Python and the scikit-learn machine learning library [48, 49] for the
implementation and we run the experiments on a Linux server with Intel(R)
Xeon(R) Gold 6248 CPU 2.50GHz and 256 GB memory. All the materials, as well as
the source code of all components including the code used for the experimental
evaluation, are publicly
available111https://github.com/Ale96Pa/attack_graph_progressive.

####  4.1.2 Results

We validate StatAG by studying the convergence of the partial AGs to the
complete AG. For the sake of simplicity, in the rest of this section, we refer
to the complete AG as _ground truth_ (GT) to indicate that it corresponds to
all the paths generated at the end of the classic generation process.

Figure 3: KS distance trend of partial AGs from the GT for the vulnerability
features distribution.

The first validation step concerns the convergence of the vulnerability
feature distributions of the partial AGs to the GT. Fig. 3 reports the median
KS distances during the entire execution of the approach. The convergence
speed of the vulnerability feature distributions depends on the distance
threshold $T$ (see Definition 6). For example, considering a good
approximation as $T=0.1$ (corresponding to just 10% approximation of the GT),
9 of 10 features are statistically significant after only 100 iterations,
except for the availability feature that has a KS distance of 0.2 after 100
iterations. In particular, we can notice 3 different trends in all the plots
in Fig. 3. The first one coincides with early partial results, where the KS
distance from the GT is too high to perform analysis with a reasonable
approximation but good for initial exploration. This trend lasts about the
first 100 iterations. After 100 iterations, corresponding to 9% of the
complete execution, the trend is flat until 1700 iterations on average,
corresponding to 77% of the complete execution. This is the interval where
mature partial results appear, that provide a 10% approximation of the GT for
most vulnerability features, with the worst performance reached by the
availability with a 20% approximation. Finally, in the last 23% of the
execution, the KS distance becomes very close to 0, corresponding to the
definitive partial results. The duration of mature partial results, in
contrast to early and definitive ones, can be attributed to the overall
limited variability in vulnerability features according to the CVSS metrics,
as documented by NIST [24]. As a consequence, the vulnerability variability is
covered very quickly in just 9% of the total number of iterations.

The convergence trend of the vulnerability features to the GT shows the
capability of the progressive approach to represent 90% of the vulnerability
inventory after a few iterations. It is a good result for the analysis of the
vulnerability inventory, but we need further investigation that concerns the
attack path analysis. To this aim, the next validation step concerns the
convergence trend of the attack path features of the partial AGs to the GT
ones. Fig. 4 reports the distribution trend of the KS distances between the
partial AGs and the GT for the attack path features, i.e., likelihood and
impact.

Figure 4: KS distance trend of partial AGs from the GT for the attack path
features distribution.

The trends in Fig. 4 show a gradual convergence for both likelihood and impact
with the largest distance equal to 0.2 in the first 100 iterations, where the
variability of the data is also higher (i.e., the box size of the boxplots).
The KS distance distribution becomes less variable and with lower median
values after about 100 iterations (9% of the execution) and until 1500
iterations (68% of the execution). It is the case of mature partial results,
that approximate the attack path features distribution from 15% to 5% (i.e.,
KS distances from 0.15 to 0.05). After 1500 iterations and until the end, we
can recognize mature partial results with a KS distance very close to 0. In
summary, attack path features can be queried after a few iterations with a 20%
approximation, gradually decreasing reaching a 5% approximation after 1500
iterations, with a trend similar to vulnerability features (see Fig. 3).

In the final validation step, we furnish evidence demonstrating that the
attack path feature stability (Equation 3) accurately reflects the trend in
statistical significance so that it can be used as a real-time indicator of
the convergence to the GT. To this aim, Fig. 5 reports the trend of the
stability for the performed experiments, where the trend of the median values
is represented with full-color hue, while the alpha blended areas identify the
variations between the upper and lower quartile values to report the
statistical variability.

Figure 5: Attack path stability trend of the attack path features during the
different iterations of the approach.

The stability trend is definitely coherent with the KS distance trend of Fig.
4: during the first 100 iterations (9% of the execution), the stability
indicates early partial results as well as the KS distance with the GT, with
stability values lower than 0.85. Between iterations 100 and 1000 (46% of the
execution), the stability reports an intermittent trend between 0.85 and 0.95,
indicating the mature partial results, where the AG is assisting its
statistical significance. The same trend corresponds to the KS distance from
the GT. Finally, we can identify the definitive partial results in the last
54% of iterations, where the stability is very close to 1 and,
correspondingly, the KS distance with the GT is very close to 0. In
conclusion, the analysis of the stability indicates that it is a good
predictor of the statistical significance of the partial AGs, with the great
advantage of being a metric that can be computed in real-time for each
iteration of the process.

The StatAG validation showed the ability of the approach to generate the
attack paths progressively, with three thresholds of significance (early,
mature, and definitive) that inform about the convergence of the partial AG to
the GT. This progressive approach represents an innovation in the Attack Graph
community, where traditional solutions typically focus on the complete
generation of AGs. However, when it comes to analyzing the complete AG for
attack path analysis, this approach still requires enumerating all paths. To
expedite convergence towards the subset of the complete AG that addresses a
particular attack path query, the next section introduces a steering mechanism
designed to guide both the generation and analysis processes.

##  5 SteerAG: Steered Attack Graph Generation and Analysis

StatAG allows us to consider an approximation of the complete AG before the
actual completion of its generation at every iteration of the process. This
only partially addresses the original problem of the poor scalability of AG:
while the convergence rate is the same as the random walk sampling, and
different quality of results can be used for different analyses (e.g.,
exploration, confirmation), this may still require a long time for an analysis
query to get the exact result. While for certain analyses this would not be
needed, being sufficient working with a suitable approximation, for others
this characteristic would not be ideal. For this reason, we contribute a
further improvement of the framework, central in its capability to merge
analysis and generation, and let the second be guided by the first, consisting
of accelerating the attack path analysis for dynamic and real-time
environments through the design of a steering mechanism, reported in Fig. 6.
We name this approach _Steered Attack Graph Generation and Analysis_
(SteerAG).

Figure 6: Workflow for the steered attack graph generation and analysis
(SteerAG).

According to the general framework (see Fig. 1), the steering process is
activated with the presence of attack paths generated using StatAG and an
attack path query for the analysis, issued by a human user or an automatic
process.

The first step of the steering approach is the _path features training_ ,
which consists of two activities. First, we label the attack paths coming from
the StatAG as “relevant” when their attack path features correspond to the
query requirements and “not relevant” otherwise. As this operation is linear
in the number of attack paths generated up to the issuing of an analysis query
in the worst case, it does not represent a costly operation. When a sufficient
number of attack paths are labeled, with this number depending on the ML model
used (i.e., ten to fifty for decision trees, around 100 for neural networks)
the second activity is the actual training of a binary ML-based classification
model, where the attack paths are classified according to their assigned label
but the classification is based on the vulnerability features of the paths and
not on characteristics of the whole path. In this way, we aim to discover the
latent relations existing between all the relevant attack paths and their
vulnerability characteristics based on the ones available. Being capable of
extracting this relation allows for steering the AG generator by the
discovered intervals of vulnerability features.

In our proposal, we use the decision tree classifier [50] as the ML model for
its properties that fit well the steering approach. Indeed, decision trees (i)
can be trained quickly and therefore are suitable for progressive data
analysis [33], (ii) produce sufficiently powerful classification models from
relatively small inputs, allowing its use early on during the progression
[50], and (iii) their structure can be easily translated into steering rules
which represent the features of the relevant data [51].

Once the decision tree has been trained on the vulnerability features, the
goal of the _vulnerability features extraction_ phase is to retrieve the rules
to steer the next StatAG generation from the structure of the trained decision
tree. We name them _steering rules_ and must consider the values of the
vulnerability features that generated only the “relevant” paths class. To do
so, we consider that the decision tree is built by using the vulnerability
features as split points and a leaf of the tree identifies whether the
vulnerability features from the root to the leaf generate “relevant” paths or
not. This makes it possible to compute the inverse mapping from the “relevant”
leaves to the root, keeping track of the vulnerability features values that
they and only they have in common. We can build the set of steering rules
considering that each path from the root to a “relevant” leaf node represents
a _conjunction_ of decision rules that must be satisfied in order for the
decision tree to classify it as relevant. Consequently, the logical
_disjunction_ of all such decision rules generates the set of steering rules.
Depending on the depth of the decision tree, we could have many steering
rules, where their union creates latent relations between relevant attack
paths and vulnerability features.

In the next step of the approach, we use the steering rules to consider only
the vulnerabilities that match them before sampling the graph again with
random walks as the StatAG generator mandates. In this way, the newly
generated attack paths have a high probability of matching the “relevant”
class for the attack path query given in input, thus accelerating the
progression of the AG generation towards attack paths answering the query.

Let us note that while the system is running, it continues to use the latest
retrieved steering rules until there is a slowdown in the precision of the
generation process, indicating that the relevant attack paths have been
exhausted. To check that this effectively means having reached the exact
answer to the query, another training is launched to adjust the steering with
new rules that take into account the cumulative collection of attack paths,
effectively repeating the described process until it converges to the exact
result (i.e., a new training does not return any additional attack paths). At
each iteration of SteerAG, preliminary attack path analysis can be performed
to answer the query, until all paths are generated. The process is even faster
in converging, guaranteeing an analysis results identical in quality to the
one conducted on the fully generated AG.

In the rest of this section, we validate SteerAG, highlighting its
performances by comparing it to the case in which it is not used.

###  5.1 SteerAG Validation

For the validation of SteerAG, we use the setting configurations used for
StatAG and described in Section 4.1.1, with the addition of another
experimental parameter that is a set of 100 attack path queries obtained with
different combinations of attack path features in the query and varying their
ranges from 0 to 1 with steps of 0.1. This resulted in a total number of
15,000 experiments.

The main evaluation metrics for the steering approach are the _recall_ and the
_precision_. The former, measured as $\frac{relevant\\_paths}{all\\_paths}$,
informs about the convergence rate of the partial AG to the GT, while the
latter, evaluated as $\frac{relevant\\_paths}{retrieved\\_paths}$, informs
about the ability of the decision tree model to correctly retrieve the attack
paths that are relevant for the query at every iteration.

(a) Recall.

(b) Precision.

Figure 7: Comparison of (a) recall and (b) precision trends for StatAG
(without steering) and SteerAG (with steering). The median values trend for
each curve is reported with full-color hue, while the alpha blended areas
identify the variations between the upper and lower quartile values.

Fig. 7 reports the recall and precision of the performed experiments. The
median values trend for each curve is reported with full-color hue, while the
alpha blended areas identify the variations between the upper and lower
quartile values. In this way, the statistical variability is reported for all
curves.

From the recall trend (Fig. 7a) we can observe the very good performance of
SteerAG that reaches values very close to 1 after just 250 iterations, with
the activation of the steering mechanism starting at 100 iterations on
average. In particular, we can recognize two thresholds during SteerAG:
between iteration 100 and 150 we observe early partial results (recall lower
than 0.5), useful for exploration; from iteration 200 until iteration 250 (11%
of the execution) the results are mature, supporting early decision making;
finally, from iteration 250 on we observe definitive partial results, with a
median recall of more than 0.95 indicating that 95% of the relevant paths are
retrieved.

It is interesting to note that without the presence of the steering approach,
the convergence to the GT (more precisely, to the portion of the GT relevant
to the query) is very slow: at the definitive partial results threshold
(iteration 250), random sampling has achieved a recall value of 0.2. Comparing
the two trends, we can conclude that the steering approach accelerates the
convergence to the GT saving around 90% iterations, providing a great
advantage for the timely analysis of the attack paths. These performances are
achieved consistently in all the experiments tested.

While the recall describes the ability of SteerAG to rapidly converge to the
GT, the precision is used as a real-time indicator of the quality of each
partial result. Fig. 7b shows the median precision trend during the execution
of the framework.

We can observe that the precision values are consistently high after the
activation of the steering mechanism at iteration 100, presenting median
values that reach peaks of 0.85. Similarly to the recall trend, precision
presents a rapid growth in the early iterations, in particular during the
generation of early partial results; this shows that the analyst can expect a
fast transition from early to mature partial results, due to the high
precision values. At iteration 500 (23% of the execution) it slows down. After
700 iterations (at 55% of the execution), there is another peak of precision
up to 0.2, and this can also be observed in the recall trend in Fig. 7a. It is
due to the retraining of the decision tree to adjust the steering rules after
the detection of the precision breakdown. The fact that the precision has
lower median values in the second steering activation than in the first one
can be explained by a lower residual probability of finding the few relevant
attack paths left (less than 2% at that stage).

In contrast, StatAG without the steering mechanism has a constant trend of low
precision values because, as expected, the probability of uniformly randomly
picking relevant attack paths to the issued query is much lower.

Overall, the validation of recall and precision demonstrate how the SteerAG
accelerates the AG generation and analysis. While it gives the statistical
variability of the trends, it does not allow us to investigate deeply how the
characteristics of the attack path queries affect the approach performance. In
particular, we are interested in evaluating the effect that the stringency of
a query has on the performances, to avoid cases in which a stringent query,
set to retrieve a low number of attack paths very specific, is indefinitely
running due to slow convergence. To validate this, we define three ranges of
queries: queries with _low_ range when the values of the attack path features
are in a range of at most 0.2, _medium_ range when it is between 0.3 and 0.5,
and _high_ range when it is over 0.5. The rationale is that low queries
require very specific characteristics of vulnerabilities with narrow
intervals, and so are more specific. Large queries retrieve a large number of
attack paths, defining not stringent vulnerability values in large intervals.
Medium queries are in the middle. We report different analyses in Fig. 8.

(a) Recall trend.

(b) Convergence rate.

(c) Missing iterations from the one with recall 1.

Figure 8: Analysis of the steering mechanism in relation to the range of the
attack path query.

Fig. 8a shows the recall trend of the different experiments for each query
range. It highlights three clearly different trends that for the low, medium,
and high ranges are respectively the fastest, medium, and slowest convergence
to the GT. To quantify the speed of the convergence to the GT, in Fig. 8b we
plot the recall values at the point of the maximum convergence of the recall
curves. In practice, it corresponds to the peak of the recall curve before its
stability. If the maximum convergence rate is low ($<0.2$) for high recall
values ($>0.8$), then it means that the approach converges slowly to the GT.
It is the case of 100% of the experiments with high query ranges, 54% of the
experiments with medium ranges, and 25% of the ones with low query ranges. In
contrast, for 46% of the experiments with medium ranges and 75% of the ones
with low ranges, the convergence rate is high ($>0.3$) when the recall is
higher than 0.8, indicating a very quick convergence to the GT. In particular,
25% of the experiments with low ranges reach the maximum convergence rate
(between 0.2 and 0.3) when the recall is around 0.8, indicating a slower
convergence with respect to the other low-range experiments.

Finally, in Fig. 8c we study the number of iterations remaining from the point
of maximum convergence until all relevant paths are retrieved (i.e., when the
recall is 1). We observe two main portions: the left one indicates the
experiments that are closer to the recall value 1 and it is composed of all
the experiments with low range and 70% of the ones with medium range. The
right one indicates the cases that require more iterations to reach recall 1
and includes all the experiments with the high range and 30% of the ones with
the medium range.

The results for low and medium query ranges confirm the capability of SteerAG
to retrieve fast attack paths even for stringent queries correctly. The
results for the high-range queries seem counter-intuitive to be not as good as
the others. In fact, this is not true, as an investigation of the trend shows
that it depends only on the very high quantity of attack paths to retrieve,
related to the capacity to process attack paths at each iteration (i.e., the
sampling size for each iteration) than to a difficulty of the approach in
retrieving correct attack paths. Looking at the precision values, they are
consistently high throughout the whole process, and it is worth noting that
the maximum convergence rate is always reached with high recall values
($>0.8$), even for high-range queries.

Overall, we do not observe an effect of the stringency of the query on the
performance, with the only parameter to set as the sampling size in order to
speed up the high-range queries.

##  6 Case Study Evaluation

In this section, we illustrate a case study to show the capabilities of the
approach to be applied in a real setting. We first show how the approach can
be used in real-time with a network bigger than the ones typically analyzed by
state-of-the-art solutions allowing higher scalability. Next, we provide a
systematization of attack path analyses retrieved from the literature and show
how the approach is capable of supporting them.

###  6.1 Application to large networks

The first application we prove deals with the scalability of the networks. In
Table I we report the works of the literature that address the generation and
analysis of attack paths, highlighting their scalability in terms of the
network parameters. In particular, we consider the maximum number of hosts,
vulnerability per host, and whether they generate all paths or not. In this
last case, the approaches define heuristics to prioritize the paths under
analysis and avoid the full generation (more details in Section 7).

TABLE I: Scalability parameters of existing works on attack path computation.
ND=Not Defined

|  | num.
---
hosts
| num. vulns
---
per host
| all
---
paths
Ghosh et al. (2012) [52] | 5 | 2 | $\checkmark$
Wang et al. (2016) [53] | 7 | 2 | ✓
Tian et al. (2017) [54] | 4 | ND | ✓
George et al. (2018) [55] | 50 | ND | $\times$
Li et al. (2019) [56] | 18 | 7 | ✓
Yichao et al. (2019) [15] | 50 | 5 | $\times$
Li et al. (2020) [16] | 15 | 12 | ✓
Sun et al. (2022) [14] | 8 | 4 | $\times$

From Table I we can observe that the largest experimental settings include
either many hosts (50) and few vulnerabilities (5), or a medium number of
hosts (15) and vulnerabilities (12 vulnerabilities per host). For the
validation of our approach, we already considered networks bigger than those
(see Section 4.1.1), but here we want to report an even bigger case study with
100 hosts and 100 vulnerabilities per host, all different from each other to
prove our approach provides a big improvement over the state-of-the-art.
Concerning the attack path query and for the sake of example, we consider the
most common risk analysis that requires attack paths with the highest risk,
therefore with both likelihood and impact between 0.9 and 1, as the most risky
situations. We prove later the support of a wide range of analysis queries.
Let us note that the generation of the complete AG is intractable for such a
size with the classic full generation, but we show that the progressive
generation allows having partial results even in this case, through the real-
time indicators that are the stability (for StatAG) and precision (for
SteerAG) controllable in real-time by an analyst or an automatic process.

Figure 9: Attack Path features stability trend during the execution of StatAG.

From the stability trend of Fig. 9 it is evident that until iteration 100 the
results are early partial, with very low and fluctuant stability indicating a
still high approximation of the complete AG. The analyst can no matter what
start exploring in this phase, even by iteration 1, and eventually query the
system for her information needs. Contrary, from iteration 100 s/he starts
observing high stability values both for likelihood and impact, thus can
hypothesize that it is the time of significant partial results, and support
tasks like hypotheses formulation. In a real scenario, it is reasonable to
observe a constant trend of the stability values before considering the
results statistically significant. From the observation of Fig. 9, a
reasonable time to consider mature partial results is at iteration 300, where
both likelihood and impact show a regular median stability of 0.85,
progressively increasing. This phase supports hypothesis testing, comparative
or confirmatory analyses, and early decision-making. From this time, the
attack path analysis can start with the consideration that it approximates at
least 85% of the complete AG.

Figure 10: Precision trend during the execution of SteerAG.

In the meanwhile, the analyst observes the precision trend of Fig. 10. S/he
notices a rapid growth at iteration 100, indicating that the SteerAG has been
activated. This observation is in line with the stability trend (Fig. 9), thus
indicating the starting point of mature partial results. The precision has an
average value of 0.8 until around iteration 8300. During this long period, the
analyst can perform attack path analysis, considering that new paths are
incoming to answer the query and, therefore, s/he should progressively monitor
the new results. When the precision is stable for a longer period (i.e.,
around iteration 2000), s/he can consider that most of the attack paths are
included in the query and, from this moment on, assumes that the analysis is
composed of definitive partial results (i.e., other incoming paths do not
significantly change the attack path feature distributions. Finally, when the
precision breaks down around iteration 8300, the results are very close to the
exact ones. Let us note, that this observation agrees with the stability trend
(Fig. 9), indicating from iteration 1000, a stability very close to 1, until
the end of the execution. From this iteration on, the analyst can produce the
final outcomes of the analysis and proceed with her work.

To give an idea of the advantages provided by the proposed framework, we
identify two potential targets: a human analyst and an automatic analysis
process. The former takes advantage of the progressive generation to perform
early decision-making in interactive times. In fact, each iteration has an
average duration between 0.5 and 5 seconds, and after a few minutes ($\approx
5$) from the beginning of execution, s/he can start performing analysis with
mature partial results. The latter has the advantage of progressive results
feeding, without the need for interactive response time but instead based on
results accuracy thresholds: the attack path analysis reaches definitive
results after a few hours ($\approx 12$) making it computable in contrast to
classic approaches that do not support it.

###  6.2 Coverage of Attack Path Analyses

To conclude the presentation of the case study, we analyze how the proposed
approach can analyze a selected set of queries with the configuration settings
used for the validation (Section 4.1.1). The attack path queries are extracted
from state-of-the-art works addressing the systematization of attack path
analysis [57, 58], and they are the following:
Q1: Evaluate the risk on the shortest attack paths [59];
Q2: Retrieve the attack paths with maximum impact (i.e., impact = 1) [60];
Q3: Retrieve the attack paths with maximum likelihood (i.e., likelihood = 1)
[61]
Q4: Retrieve the attack paths with maximum risk (i.e., likelihood $\cdot$
impact = 1) [4];
Q5: Retrieve the attack paths corresponding to _black swan_ attacks, i.e.,
those ones with very high impacts (impact $>$ 0.9), but very unlikely to
happen (likelihood $<$ 0.3) [62];
Q6: Retrieve the attack paths corresponding to _gray swan_ attacks, i.e.,
those ones with very low impacts (impact $<$ 0.3), but highly probable
(likelihood $>$ 0.9) [63];
Q7: Prioritize the attack paths by risk [8]. Let us note that this query
corresponds to an ensemble of queries, retrieving first the paths with risk 1,
then between 0.9 and 1, and so on. To avoid the complete enumeration of the
paths, we stop the approach once we retrieve the paths with risk values higher
than 0.5.

Fig. 11 reports the recall median trend for the analysis of these queries,
where each experiment is repeated 100 times.

Figure 11: Recall trend for the attack path analyses of the query
systematization.

The recall trends in Fig. 11 show that most of the queries (specifically,
Q1-Q5 and Q7) converge very rapidly to the GT, indicating the concrete support
that the approach can provide during attack path analysis. Among them, Q2, Q3,
and Q4 ask for precise values of attack path features, while Q1, Q5, and Q7
ask for more complex queries, requiring more than one traversal in the same
AG. In particular query Q6 for gray swan attacks has the worst performance
requiring 3500 median iterations to retrieve all the paths. The reason for its
worse performance may be the need to perform more traversals to answer the
query, which includes many paths. Let us remark that it still provides
approximate answers but with a slower convergence rate.

This case study showed the capabilities of the approach to perform attack path
analysis with networks’ size that existing solutions cannot address and
according to state-of-the-art attack path analysis.

##  7 Related Work

Several works leverage Attack Graphs (AGs) for analyzing cyber risks of
computer networks [8, 9, 64], which underline their expressiveness and high
computational complexity. Our framework intersects two main areas of the
related work: AG generation and attack path analysis.

###  7.1 Attack Graph Generation

To address the scalability issue of AGs, the research focuses on the design of
approaches to generate AGs.

One possible solution consists of leveraging distributed and parallel
computing. The distributed approaches, as Kaynar et al. [11] and Sabur et al.
[65], partition the network based on its services and vulnerabilities and
assign the different partitions among distributed agents. In this way, each
agent computes the attack paths on a smaller portion of the graph which is
finally combined with the other paths to complete the generation. The
approaches based on parallel computing [16, 56] instead adapt the graph search
algorithms (i.e., BFS and DFS), that are designed for serial computation, to
parallel algorithms that allow running the AG generation in multi-core
environments. Our approach is agnostic to potential distribution or
parallelization, as it acts on the workflow of analysis and generation.

Another possibility is using Artificial Intelligence (AI). For example, Li et
al. [66] leverage Deep Learning and node2vec [67] to train a neural network
with data from system logs and use it to predict dependencies between network
hosts and label the sequence of events as potential attack paths. Besides,
Ychao et al. [15] model the path discovery problem as a planning problem on
graphs. They translate vulnerability information to formalism actions and use
state-of-the-art planners to discover attack paths.

While Distributed and AI-based solutions provide a good improvement in the
scalability of AG generation, they still require waiting until the generation
is completed to perform the first analyses. In dynamic scenarios where network
components change rapidly (and so do attack graphs), it is not reasonable to
wait for the re-computation of the attack paths each time the environment
changes.

###  7.2 Attack Path Analysis

To make AGs actionable for cyber risk analysis, different works addressed the
scalability problem from the attack path analysis perspective. The central
idea behind these works is the design of heuristics that prioritize the
analysis of certain attack paths according to specific security requirements.

Some of them prioritize the attack path analysis considering the graph
topological structure: it is the case of Sun et al. [14], who use nodes’ in-
degree and out-degree, and Gonda et al. [68, 34], who map AGs to planning
graphs and leverages the nodes’ centrality. Other works define priorities
according to security metrics, as Liu et al. [69] who map potential exploits
to the easiest reachable attack target, and then prioritize the analysis based
on their probability. Similarly, Wang et al. [53] prioritize attack paths on
the degree of matching between attack nodes and a set of predefined security
conditions, while Feng et al. [12] associate a cost value to each attack node
and prioritizes the attack paths based on the costs. These works take specific
assumptions to assign priorities, and therefore they are fine only for
scenarios that conform to such assumptions. Moreover, most of them are usually
static assumptions, which do not necessarily follow the network exposure.

Few works addressed the problem of considering attack path analysis to
prioritize the generation. One of them is proposed by Yuan et al. [27] and
Salayma et al. [70]. They model the AG through a graph database and perform
attack path analysis by suitably writing queries to the database. While these
solutions allow the expression of complex and highly customizable queries,
they have the drawback that depend on the graph database, which may slow down
the performance during the analysis [71]. Nadeem et al. [72] use alerts coming
from Intrusion Detection Systems (IDS) to drive the attack path analysis. They
translate alert events to episode sequences that are then used to build the AG
and execute the analysis driven by alerts. Similarly, Hassan et al. [73]
perform rule matching on system logs to identify the events that match attack
behaviors described in security knowledge bases. While these alert-based
approaches are context-aware, they may not represent the entire environment,
such as network components with no alerts detected.

##  8 Limitations and Opportunities

This paper proposed a new framework to generate and analyze AGs based on
progressive data analysis. To the best of the authors’ knowledge, it is the
first contribution to advancing the classic sequential AG-based process.
In this section, we elicit some limitations as well as opportunities for the
proposed work.

First, we point out that our approach and its validation are applied to
_topological_ attack graphs [12, 20, 74], where nodes represent the attacker
states on the network and edges the lateral movements of vulnerability
exploits. However, there exist _logical_ AGs [22, 75, 31], that model the
attacker states according to the dependency relations expressed as logical
axioms and formal rules. We believe that our approach can be easily adjusted
to perform attack path analysis over logical AGs, for example, adapting the
attack path construction with model-checking [76]. We consider this extension
as future work.

Additionally, we considered the likelihood and impact as attack path features
since they are the main ones used in the existing literature on cyber risk
management. Nonetheless, there exist different risk models that use different
metrics, especially in domains such as cloud computing [77] and automotive
[78]. These metrics may present a non-linear relation to the vulnerability
features, thus making the decision tree training more challenging. To this
aim, we suggest exploring other ML models, in particular Graph Neural Networks
[79], that are challenging to adapt to our approach due to the large amount of
needed resources for training, the long training time not compatible with
interactive analysis, and their black-box nature that make it difficult to
retrieve the steering rules.

Finally, another point worth discussing is the possible bias introduced by
SteerAG. In fact, the steering rules tend to bias the distribution of
vulnerability and attack path features towards the query requirements, as we
expected since it actually accelerates the convergence to the complete AG.
However, it would be interesting to study a way to keep the two distributions
distinct, allowing both to answer correctly the analysis query and at the same
time extract from its answer the part to add to statAG to keep its statistical
significance and minimize introduced bias.

Other considerations related to the proposed approach examine the
opportunities it opens for further research. One involves the improvement of
the decision tree predictions after the precision breakdown. Currently, we
just re-train the decision tree with the newly incoming paths, so as to update
the steering rules. However, more advanced approaches can be studied to detect
the precision breakdown and efficiently re-train the ML model. A solution that
we want to explore for this aim is Network Representation Learning [80].

An additional opportunity is to study the smart combination of analysis
queries to create strategies for the generation of the AG, prioritizing the
analyst goal by gaining a higher versatility than classic sampling methods
like stratified sampling. These combinations can be initially executed even
without the security operator’s intervention, obtaining a highly dynamic way
of prioritizing the AG to generate.

Finally, while the proposed framework can be included in an automatic
pipeline, where a process issues analysis queries, it opens the research for
the design of human-in-the-loop systems to support security experts during the
real-time risk analysis of attack paths, possibly with some form of active
learning [81, 82] where human interactions help accelerate the AG generation
and analysis.

##  9 Conclusion

This paper presented a new framework for AG-based systems addressing the
problem of their scalability by leveraging progressive data analysis. We
designed two approaches to progressively generate statistically significant
partial AGs (StatAG) and accelerate the generation based on the attack path
query (SteerAG). Additionally, it can better adapt to network changes (e.g.,
new connections or vulnerabilities in the network) without the need for
recomputing the entire AG, a benefit that classic AG generation approaches
lack. We provided extensive experimental validation and showed a case study
demonstrating the capability of the framework to (i) analyze networks whose
size cannot be managed with existing solutions, and (ii) efficiently support
common attack path analyses. The approach is orthogonal to the existing ones
and can be used in their combination without loss of generality.

In future works, we intend to i) Investigate the application of StatAG and
SteerAG to the class of logical AGs, ii) extend it to more heterogeneous risk
models, iii) apply advanced learning solutions, such as network representation
learning, and iv) develop an interactive system to validate the approach in
real scenarios with security experts.

## References

  * [1] S. Dambra, L. Bilge, and D. Balzarotti, “Sok: Cyber insurance–technical challenges and a system security roadmap,” in _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 1367–1383.
  * [2] G. Gonzalez-Granadillo, S. Dubus, A. Motzek, J. Garcia-Alfaro, E. Alvarez, M. Merialdo, S. Papillon, and H. Debar, “Dynamic risk management response system to handle cyber threats,” _Future Generation Computer Systems_ , vol. 83, pp. 535–552, Jun. 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167739X17311433
  * [3] J. Zengy, X. Wang, J. Liu, Y. Chen, Z. Liang, T.-S. Chua, and Z. L. Chua, “Shadewatcher: Recommendation-guided cyber threat analysis using system audit records,” in _2022 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2022, pp. 489–506.
  * [4] D. W. Woods and R. Böhme, “Sok: Quantifying cyber risk,” in _2021 IEEE Symposium on Security and Privacy (SP)_ , 2021, pp. 211–228.
  * [5] J. Navarro, A. Deruyver, and P. Parrend, “A systematic survey on multi-step attack detection,” _Computers & Security_, vol. 76, pp. 214–249, 2018.
  * [6] R. Khan, K. McLaughlin, D. Laverty, and S. Sezer, “Stride-based threat modeling for cyber-physical systems,” in _2017 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT-Europe)_. IEEE, 2017, pp. 1–6.
  * [7] T. UcedaVelez and M. M. Morana, _Risk Centric Threat Modeling: process for attack simulation and threat analysis_. John Wiley & Sons, 2015.
  * [8] K. Zenitani, “Attack graph analysis: An explanatory guide,” _Computers & Security_, vol. 126, p. 103081, Mar. 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0167404822004734
  * [9] K. Kaynar, “A taxonomy for attack graph generation and usage in network security,” _Journal of Information Security and Applications_ , vol. 29, pp. 27–56, Aug. 2016. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2214212616300011
  * [10] H. S. Lallie, K. Debattista, and J. Bal, “A review of attack graph and attack tree visual syntax in cyber security,” _Computer Science Review_ , vol. 35, p. 100219, 2020.
  * [11] K. Kaynar and F. Sivrikaya, “Distributed Attack Graph Generation,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 13, no. 5, pp. 519–532, Sep. 2016, conference Name: IEEE Transactions on Dependable and Secure Computing.
  * [12] Y. Feng, L. Wang, J. Zhang, Z. Cai, and Y. Gan, “Generation Method of Network Attack Graph Based On Greedy Heuristic Algorithm,” _International Journal of Hybrid Information Technology_ , vol. 10, no. 6, pp. 23–32, Jun. 2017. [Online]. Available: http://gvpress.com/journals/IJHIT/vol10_no6/3.pdf
  * [13] A. Palma and S. Bonomi, “A workflow for distributed and resilient attack graph generation,” in _2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks-Supplemental Volume (DSN-S)_. IEEE, 2023, pp. 185–187.
  * [14] W. Sun, Q. Li, P. Wang, and J. Hou, “Heuristic Network Security Risk Assessment Based on Attack Graph,” in _Cloud Computing_ , ser. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, M. R. Khosravi, Q. He, and H. Dai, Eds. Cham: Springer International Publishing, 2022, pp. 181–194.
  * [15] Z. Yichao, Z. Tianyang, G. Xiaoyue, and W. Qingxian, “An Improved Attack Path Discovery Algorithm Through Compact Graph Planning,” _IEEE Access_ , vol. 7, pp. 59 346–59 356, 2019. [Online]. Available: https://ieeexplore.ieee.org/document/8708196/
  * [16] M. Li, P. J. Hawrylak, and J. Hale, “Implementing an Attack Graph Generator in CUDA,” in _2020 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)_ , May 2020, pp. 730–738.
  * [17] H. Aliee, F. Khosravi, and J. Teich, “Efficient treatment of uncertainty in system reliability analysis using importance measures,” in _2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_ , 2019, pp. 76–87.
  * [18] J.-D. Fekete and R. Primet, “Progressive analytics: A computation paradigm for exploratory data analysis,” _arXiv preprint arXiv:1607.05162_ , 2016.
  * [19] M. Angelini, G. Santucci, H. Schumann, and H.-J. Schulz, “A review and characterization of progressive visual analytics,” in _Informatics_ , vol. 5. MDPI, 2018, p. 31.
  * [20] K. Ingols, R. Lippmann, and K. Piwowarski, “Practical Attack Graph Generation for Network Defense,” in _2006 22nd Annual Computer Security Applications Conference (ACSAC’06)_ , Dec. 2006, pp. 121–130, iSSN: 1063-9527.
  * [21] S. Jajodia, S. Noel, and B. O’Berry, “Topological Analysis of Network Attack Vulnerability,” Jan. 2005, vol. 5, pp. 247–266.
  * [22] X. Ou, S. Govindavajhala, A. W. Appel _et al._ , “Mulval: A logic-based network security analyzer.” in _USENIX security symposium_ , vol. 8. Baltimore, MD, 2005, pp. 113–128.
  * [23] NIST, “NVD: National Vulnerability Database.” [Online]. Available: https://nvd.nist.gov/
  * [24] ——, “NIST: National Institute of Standards and Technology.” [Online]. Available: https://www.nist.gov/
  * [25] T. N. Security, “Nessus,” Tenable Network Security, tool, 11 2022. [Online]. Available: www.tenable.com/products/nessus
  * [26] S. Jajodia and S. Noel, “Topological vulnerability analysis,” in _Cyber situational awareness: Issues and research_. Springer, 2009, pp. 139–154.
  * [27] B. Yuan, Z. Pan, F. Shi, and Z. Li, “An Attack Path Generation Methods Based on Graph Database,” in _2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC)_ , vol. 1, Jun. 2020, pp. 1905–1910.
  * [28] CVSS Special Interest Group (SIG), “CVSS: Common Vulnerability Scoring System.” [Online]. Available: https://www.first.org/cvss/
  * [29] ISO Central Secretary, “Iso/iec 27001:2022-information security, cybersecurity and privacy protection - guidance on managing information security risks,” International Organization for Standardization, Geneva, CH, Standard ISO/IEC 27005:2022, 2022.
  * [30] C. 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.
  * [31] D. Tayouri, N. Baum, A. Shabtai, and R. Puzis, “A survey of mulval extensions and their attack scenarios coverage,” _IEEE Access_ , 2023.
  * [32] J. Zeng, S. Wu, Y. Chen, R. Zeng, and C. Wu, “Survey of attack graph analysis methods from the perspective of data and knowledge processing,” _Security and Communication Networks_ , vol. 2019, pp. 1–16, 2019.
  * [33] M. Hogräfer, M. Angelini, G. Santucci, and H.-J. Schulz, “Steering-by-example for Progressive Visual Analytics,” _ACM Transactions on Intelligent Systems and Technology_ , vol. 13, no. 6, pp. 96:1–96:26, 2022. [Online]. Available: https://doi.org/10.1145/3531229
  * [34] T. Gonda, T. Pascal, R. Puzis, G. Shani, and B. Shapira, “Analysis of attack graph representations for ranking vulnerability fixes.” in _GCAI_ , 2018, pp. 215–228.
  * [35] W. Bai, A. Cheng, C. Wang, and Z. Pan, “A fast user actual privilege reasoning framework based on privilege dependency graph reduction,” _IET Information Security_ , vol. 17, no. 3, pp. 505–517, 2023.
  * [36] C. Y. Lee, “An algorithm for path connections and its applications,” _IRE transactions on electronic computers_ , no. 3, pp. 346–365, 1961.
  * [37] K. Pearson, “The problem of the random walk,” _Nature_ , vol. 72, no. 1865, pp. 294–294, 1905.
  * [38] R.-H. Li, J. X. Yu, L. Qin, R. Mao, and T. Jin, “On random walk based graph sampling,” in _2015 IEEE 31st international conference on data engineering_. IEEE, 2015, pp. 927–938.
  * [39] N. L. Sproull, _Handbook of research methods: A guide for practitioners and students in the social sciences_. Scarecrow press, 2002.
  * [40] J. L. Devore _et al._ , _Probability and Statistics for Engineering and the Sciences_. Duxbury Press Belmont, 1995, vol. 5.
  * [41] T. Pyzdek and P. A. Keller, _Quality engineering handbook_. CRC Press, 2003.
  * [42] N. J. Salkind, _Encyclopedia of measurement and statistics_. SAGE publications, 2006.
  * [43] F. J. Massey Jr, “The kolmogorov-smirnov test for goodness of fit,” _Journal of the American statistical Association_ , vol. 46, no. 253, pp. 68–78, 1951.
  * [44] W. Rudin, _Principles of mathematical analysis_ , 1953.
  * [45] E. W. Zegura, K. L. Calvert, and M. J. Donahoo, “A quantitative comparison of graph-based models for internet topology,” _IEEE/ACM Transactions on networking_ , vol. 5, no. 6, pp. 770–783, 1997.
  * [46] P. ERDdS and A. R&wi, “On random graphs i,” _Publ. math. debrecen_ , vol. 6, no. 290-297, p. 18, 1959.
  * [47] C. R. Palmer and J. G. Steffan, “Generating network topologies that obey power laws,” in _Globecom’00-IEEE. Global Telecommunications Conference. Conference Record (Cat. No. 00CH37137)_ , vol. 1. IEEE, 2000, pp. 434–438.
  * [48] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Édouard Duchesnay, “Scikit-learn: Machine learning in python,” _Journal of Machine Learning Research_ , vol. 12, no. 85, pp. 2825–2830, 2011. [Online]. Available: http://jmlr.org/papers/v12/pedregosa11a.html
  * [49] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright _et al._ , “Scipy 1.0: fundamental algorithms for scientific computing in python,” _Nature methods_ , vol. 17, no. 3, pp. 261–272, 2020.
  * [50] S. B. Kotsiantis, “Decision trees: a recent overview,” _Artificial Intelligence Review_ , vol. 39, pp. 261–283, 2013.
  * [51] K. Dimitriadou, O. Papaemmanouil, and Y. Diao, “Explore-by-example: An automatic query steering framework for interactive data exploration,” in _Proceedings of the 2014 ACM SIGMOD international conference on Management of data_ , 2014, pp. 517–528.
  * [52] N. Ghosh and S. K. Ghosh, “A planner-based approach to generate and analyze minimal attack graph,” _Applied Intelligence_ , vol. 36, no. 2, pp. 369–390, Mar. 2012. [Online]. Available: https://doi.org/10.1007/s10489-010-0266-8
  * [53] S. Wang, G. Tang, G. Kou, and Y. Chao, “An attack graph generation method based on heuristic searching strategy,” in _2016 2nd IEEE International Conference on Computer and Communications (ICCC)_ , Oct. 2016, pp. 1180–1185.
  * [54] J.-w. Tian, X. Li, Z. Tian, and W.-h. Qi, “Network attack path reconstruction based on similarity computation,” in _2017 13th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD)_. Guilin: IEEE, Jul. 2017, pp. 2457–2461. [Online]. Available: https://ieeexplore.ieee.org/document/8393160/
  * [55] G. George and S. M. Thampi, “A Graph-Based Security Framework for Securing Industrial IoT Networks From Vulnerability Exploitations,” _IEEE Access_ , vol. 6, pp. 43 586–43 601, 2018, conference Name: IEEE Access.
  * [56] M. Li, P. Hawrylak, and J. Hale, “Concurrency Strategies for Attack Graph Generation,” in _2019 2nd International Conference on Data Intelligence and Security (ICDIS)_ , Jun. 2019, pp. 174–179.
  * [57] D. J. Landoll, _Information Security Policies, Procedures, and Standards: A Practitioner’s Reference_. CRC Press, 2017.
  * [58] O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. Wing, “Automated generation and analysis of attack graphs,” in _Proceedings 2002 IEEE Symposium on Security and Privacy_ , 2002, pp. 273–284.
  * [59] S. Noel and S. Jajodia, “Metrics suite for network attack graph analytics,” in _Proceedings of the 9th Annual Cyber and Information Security Research Conference_ , 2014, pp. 5–8.
  * [60] I. Kotenko and E. Doynikova, “Security Assessment of Computer Networks Based on Attack Graphs and Security Events,” in _Information and Communication Technology_ , Linawati, M. S. Mahendra, E. J. Neuhold, A. M. Tjoa, and I. You, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, vol. 8407, pp. 462–471, series Title: Lecture Notes in Computer Science. [Online]. Available: http://link.springer.com/10.1007/978-3-642-55032-4_47
  * [61] G. Kavallieratos and S. Katsikas, “Attack Path Analysis for Cyber Physical Systems,” in _Computer Security_ , ser. Lecture Notes in Computer Science, S. Katsikas, F. Cuppens, N. Cuppens, C. Lambrinoudakis, C. Kalloniatis, J. Mylopoulos, A. Antón, S. Gritzalis, W. Meng, and S. Furnell, Eds. Cham: Springer International Publishing, 2020, pp. 19–33.
  * [62] T. Aven, “On the meaning of a black swan in a risk context,” _Safety science_ , vol. 57, pp. 44–51, 2013.
  * [63] N. Khakzad, F. Khan, and P. Amyotte, “Major accidents (gray swans) likelihood modeling using accident precursors and approximate reasoning,” _Risk analysis_ , vol. 35, no. 7, pp. 1336–1347, 2015.
  * [64] A. Ramos, M. Lazar, R. Holanda Filho, and J. J. Rodrigues, “Model-based quantitative network security metrics: A survey,” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 4, pp. 2704–2734, 2017.
  * [65] A. Sabur, A. Chowdhary, D. Huang, and A. Alshamrani, “Toward scalable graph-based security analysis for cloud networks,” _Computer Networks_ , vol. 206, p. 108795, Apr. 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S1389128622000251
  * [66] T. Li, Y. Jiang, C. Lin, M. Obaidat, Y. Shen, and J. Ma, “DeepAG: Attack Graph Construction and Threats Prediction with Bi-directional Deep Learning,” _IEEE Transactions on Dependable and Secure Computing_ , pp. 1–1, 2022, conference Name: IEEE Transactions on Dependable and Secure Computing.
  * [67] A. Grover and J. Leskovec, “node2vec: Scalable Feature Learning for Networks,” in _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , ser. KDD ’16. New York, NY, USA: Association for Computing Machinery, 2016, pp. 855–864. [Online]. Available: https://dl.acm.org/doi/10.1145/2939672.2939754
  * [68] T. Gonda, G. Shani, R. Puzis, and B. Shapira, “Ranking vulnerability fixes using planning graph analysis,” in _IWAISe: First International Workshop on Artificial Intelligence in Security_ , vol. 41, 2017.
  * [69] X. Liu, C. Fang, D. Xiao, and H. Xu, “A Goal-Oriented Approach for Modeling and Analyzing Attack Graph,” in _2010 International Conference on Information Science and Applications_ , Apr. 2010, pp. 1–8, iSSN: 2162-9048.
  * [70] M. Salayma and E. C. Lupu, “Threat Modelling in Internet of Things (IoT) Environment Using Dynamic Attack Graphs,” Oct. 2023, arXiv:2310.01689 [cs]. [Online]. Available: http://arxiv.org/abs/2310.01689
  * [71] J. Guia, V. G. Soares, and J. Bernardino, “Graph databases: Neo4j analysis.” in _ICEIS (1)_ , 2017, pp. 351–356.
  * [72] A. Nadeem, S. Verwer, S. Moskal, and S. J. Yang, “Alert-Driven Attack Graph Generation Using S-PDFA,” _IEEE Transactions on Dependable and Secure Computing_ , vol. 19, no. 2, pp. 731–746, Mar. 2022, conference Name: IEEE Transactions on Dependable and Secure Computing.
  * [73] W. U. Hassan, A. Bates, and D. Marino, “Tactical provenance analysis for endpoint detection and response systems,” in _2020 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2020, pp. 1172–1189.
  * [74] M. S. Barik, A. Sengupta, and C. Mazumdar, “Attack Graph Generation and Analysis Techniques,” _Defence Science Journal_ , vol. 66, no. 6, p. 559, Oct. 2016. [Online]. Available: http://publications.drdo.gov.in/ojs/index.php/dsj/article/view/10795
  * [75] M. J. Froh and G. Henderson, _MulVAL extensions II_. Defence R&D Canada-Ottawa, 2009.
  * [76] E. M. Clarke, “Model checking,” in _Foundations of Software Technology and Theoretical Computer Science: 17th Conference Kharagpur, India, December 18–20, 1997 Proceedings 17_. Springer, 1997, pp. 54–56.
  * [77] E. Pauley, R. Sheatsley, B. Hoak, Q. Burke, Y. Beugin, and P. McDaniel, “Measuring and mitigating the risk of ip reuse on public clouds,” in _2022 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2022, pp. 558–575.
  * [78] G. Macher, E. Armengaud, E. Brenner, and C. Kreiner, “A review of threat analysis and risk assessment methods in the automotive context,” in _Computer Safety, Reliability, and Security: 35th International Conference, SAFECOMP 2016, Trondheim, Norway, September 21-23, 2016, Proceedings 35_. Springer, 2016, pp. 130–141.
  * [79] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 32, no. 1, pp. 4–24, 2021.
  * [80] D. Zhang, J. Yin, X. Zhu, and C. Zhang, “Network representation learning: A survey,” _IEEE transactions on Big Data_ , vol. 6, no. 1, pp. 3–28, 2018.
  * [81] B. Settles, “Active learning literature survey,” 2009. [Online]. Available: http://digital.library.wisc.edu/1793/60660
  * [82] M. Angelini, S. Bonomi, S. Lenti, G. Santucci, and S. Taggi, “Mad: A visual analytics solution for multi-step cyber attacks detection,” _Journal of Computer Languages_ , vol. 52, pp. 10–24, 2019.

##  Appendix A Attack Path Sampling Analysis

(a) BFS.

(b) DFS.

(c) Random Walk.

Figure 12: KS distance trend of partial AGs from the GT for the attack path
features distribution when sampling using (a) BFS, (b) DFS, and (c) Random
Walks algorithms.

In this appendix, we report the analysis that shows the better performance of
random walk sampling than BFS and DFS ones. We use the experimental setting
defined in Section 4.1.1 and report in Fig. 12 the comparison of the
convergence trend of the KS distance of partial AGs from the complete AG
(i.e., the ground truth GT) for the three sampling algorithms.

Considering the different trends, we can observe that the BFS sampling (Fig.
12a) has the worst performance for two main reasons. First, the results of the
experiments have higher variability if compared with DFS 12b and random walk
12c, indicating less controlled KS distances from the GT. Second, the median
values have a higher constant trend of 0.2 that increases further for the
impact. In contrast, random walk sampling has better performance, with low
data variability right from the first iterations and with monotonically
decreasing convergence. Finally, DFS sampling has lower variability than BFS,
but the median values are at 0.2, while random walks represent well the
complete AG with a median KS distance closer to 0.

This analysis is in line with our expectation, because both BFS and DFS
sampling are biased to the starting node, and as a consequence, they tend to
visit the same edges and, therefore, the same vulnerabilities. Contrary,
random walks enable visiting the graph in an unbiased manner, thus increasing
the unique vulnerability visited and this results in a faster convergence to
the attack path features of the complete AG. For this reason, we included
random walk sampling in our approach.

##  Appendix B An example of Attack Graph

In this appendix, we provide an example of an attack graph, modeled according
to the AG model described in section 2.

(a) Simple network configuration. (b) Attack Graph for the simple network
configuration.

Figure 13: Example of (a) network configuration and (b) its resulting attack
graph model.

For the sake of explanation, let us consider the simple network reported in
Fig. 13a [74], in which the Demilitarized Zone (DMZ) is safeguarded by two
firewalls, namely Firewall-1 and Firewall-2. It has a Web Server (H1) and a
Login Server (H2). Firewall-1 shields the DMZ from external threats
originating from the attacker located on Host H0, and it allows only http and
ssh traffic. Firewall-2 safeguards the DMZ from internal threats and permits
access to the Database server solely from the Web server. The vulnerability
inventory is reported in Table II, while the resulting attack graph is in Fig.
13b.

TABLE II: Vulnerability inventory for the illustrative example.

Software | Host | Vulnerability
---|---|---
Apache Web Server | H1 | V1 (CVE-2006-3747)
OpenSSH | H2 | V2 (CVE-2002-0640)
MySQL | H3 | V3 (CVE-2009-2446)
Linux Kernel | H3 | V4 (CVE-2004-0495)
Linux Kernel | H3 | V5 (CVE-2023-3269)

Host H1 is running a vulnerable version of Apache web server, which has a
vulnerability (CVE-2006-3747) that allows a remote attacker to exploit and
gain user privilege on the Web Server. The ssh service on H2 has a
vulnerability (CVE-2002-0640), which allows remote attackers to gain user
privilege. Database server H3 is a Linux box running MySQL database which has
a remotely exploitable vulnerability (CVE-2009-2446), enabling the attacker to
gain user privilege. The Linux kernel in host H3 also has a vulnerability
(CVE-2004-0495) that allows local users to gain root privilege.

Let us note that vulnerabilities V4 and V5 affect the same service, resulting
in multi-edges in the attack graph.

##  Appendix C Risk Model details

This appendix provides additional details of the risk model introduced in
Section 2. It considers CVSS standard metrics to estimate the likelihood and
impact of an attack path. In particular, the likelihood is calculated
according to the following formulas:

$\displaystyle exploitability(u)=RoundUp(AV\cdot AC\cdot PR\cdot UI)$ (4)
$\displaystyle likelihood(AP)=norm(\sum_{u\in
U_{AP}}\frac{1}{exploitability(u)})$ (5)

Equation 4 determines the exploitability of a vulnerability $u$ by multiplying
the CVSS-3.1 exploitability metrics, that are :

  * •

Attack Vector (AV): measure the context by which vulnerability exploitation is
possible, thus a larger value corresponds to a more remote attacker;

  * •

Attack Complexity (AC): measures the conditions beyond the attacker’s control
that must exist to exploit a vulnerability;

  * •

Privilege Required (PR): measures the level of privileges an attacker must
possess before successfully exploiting a vulnerability;

  * •

User Interaction (UI): measures the requirement for a human attacker to
successfully compromise a vulnerable component.

Given that an attack path $AP$ is composed of multiple vulnerabilities, then
its likelihood is calculated as the normalized sum of the inverse of
exploitability, as reported in Equation 5. This choice is due to the CVSS
exploitability metrics, defined in the range [0,1], which have the rationale
that the easier the exploitation of the vulnerability, the closer they are to
one. Thus the likelihood is measured as the inverse of their product, summed
for all the vulnerabilities in the path, normalized to be in the range [0,1].

The impact of an attack is determined by the last node in the path, as it
represents the attacker’s final goal. In particular, let $u_{n}$ be the last
vulnerability of an attack path $AP$ which allows it to finally reach the
attacker target. Then,

$\displaystyle impact(AP)=1-[(1-C_{n})\cdot(1-I_{n})\cdot(1-A_{n})]$ (6)
$\displaystyle risk(AP)=likelihood(AP)\cdot impact(AP)$ (7)

where the CVSS-3.1 impact metrics are used, that are:

  * •

Confidentiality (C): measures the impact on information access and disclosure.

  * •

Integrity (I): measures the impact on trustworthiness and veracity of
information;

  * •

Availability (A): measures the impact on accessibility of information
resources.

Contrary to exploitability metrics, the CVSS impact metrics have the rationale
that the more damages caused by successful exploitation, the closer they are
to 1. For this reason, the impact is calculated by subtracting the value of
the metrics from 1. Finally, equation 7 expresses the risk of an attack path
$AP$ as the dot product of its likelihood and impact [29].