Open AccessArticle

Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes

Eugene Levner

^1,* and

Dmitry Tsadikovich

Faculty of Sciences, Holon Institute of Technology, 58102 Holon, Israel

Department of Management, Bar Ilan University, 5290002 Ramat Gan, Israel

Author to whom correspondence should be addressed.

Algorithms 2024, 17(11), 504; https://doi.org/10.3390/a17110504

Submission received: 11 September 2024 / Revised: 28 October 2024 / Accepted: 31 October 2024 / Published: 4 November 2024

(This article belongs to the Section Algorithms for Multidisciplinary Applications)

Download

Browse Figures

Figure 1
The flow chart of the proposed algorithm. "> Figure 2
(a) Example 1 adapted from [<a href="#B41-algorithms-17-00504" class="html-bibr">41</a>]. (b) Extracted minimum-length attack path. "> Figure 3
(a) Acyclic attack graph equipped with the node times. (b) Extracted minimum-length attack path for Example 2. "> Figure 4
(a) Attack graph with cycles. (b) Extracted minimum-length attack path. "> Figure 5
(a) The unweighted attack graph with cycles. (b) Extracted minimum-length attack path. "> Figure 6
Attack graph with cycles without an attack path. "> Figure 7
The extended attack graph with the start node (adapted from [<a href="#B20-algorithms-17-00504" class="html-bibr">20</a>]). "> Figure 8
Extracted minimum-length attack path for the attack graph in <a href="#algorithms-17-00504-f007" class="html-fig">Figure 7</a>. "> Figure 9
A scheme of defenders’ response to a malicious attack. ">

Review Reports Versions Notes

Abstract

This paper studies the security issues for cyber–physical systems, aimed at countering potential malicious cyber-attacks. The main focus is on solving the problem of extracting the most vulnerable attack path in a known attack graph, where an attack path is a sequence of steps that an attacker can take to compromise the underlying network. Determining an attacker’s possible attack path is critical to cyber defenders as it helps identify threats, harden the network, and thwart attacker’s intentions. We formulate this problem as a path-finding optimization problem with logical constraints represented by AND and OR nodes. We propose a new Dijkstra-type algorithm that combines elements from Dijkstra’s shortest path algorithm and the critical path method. Although the path extraction problem is generally NP-hard, for the studied special case, the proposed algorithm determines the optimal attack path in polynomial time,

O (n m)

, where

n

is the number of nodes and

m

is the number of edges in the attack graph. To our knowledge this is the first exact polynomial algorithm that can solve the path extraction problem for different attack graphs, both cycle-containing and cycle-free. Computational experiments with real and synthetic data have shown that the proposed algorithm consistently and quickly finds optimal solutions to the problem.

Keywords:

cybersecurity; cyber-attack; cyclic attack graph; attack path; AND/OR graph; attack time assessment; attack path extraction; polynomial algorithm

1. Introduction

Today, complex cyber–physical systems (CPSs) depend highly on and suffer from deliberate hostile cyber-attacks. As the number of Internet users grows at an unprecedented rate, roughly doubling annually, the number of cybercrimes steadily increases yearly [1,2,3]. There is a daily and ongoing need for risk management of existing CPSs, including vulnerability analysis of hardware and software assets constantly threatened by hostile attacks. Vulnerability analysis and the development of efficient algorithms aimed at estimating/mitigating the consequences of hostile attacks on cyber–physical systems are the most crucial research areas to ensure CPS’s cybersecurity.

These algorithms provide a rigorous, scientifically sound engineering approach to analyzing and preventing adversarial attacks. The development and analysis of one such algorithm is the subject of this research.

Graphs are a powerful and widely used tool in all aspects of cyber-attack investigation. The first comprehensive analysis of an adversarial cyber-attack based on a graph model was performed in 1998 by Phillips and Swiler [4]. However, their approach required exponential computational time to generate the desired graph. Later, Ammann et al. [5] introduced a very productive concept of an exploit dependency, which allowed attack graphs to be generated much more efficiently.

To investigate the vulnerability of the cyber network, researchers in [4] introduced and used a specific type of directed graph called an attack graph (AG) to describe and analyze malicious attacks and network insecurities visually.

Analysis and research of attack graphs can help cyber-defense professionals identify vulnerabilities in a network that an attacker could exploit, thereby helping to strengthen the network’s defenses. Typically, each node in an attack graph corresponds to a malicious event caused by attackers, and the edges correspond to the causal relationships between events. Such a graph represents a merged set of attack paths, each representing a sequence of steps an attacker can take to compromise the relevant network.

A significant difference between attack graph analysis and other adversarial risk analysis methods is that AGs are constructed primarily from the attacker’s point of view so that the defender can better understand the attacker’s intentions and better organize the defense. Since different studies use different terms and various definitions related to cyber-attacks and related graph models, we provide the reader with the terms used in this paper in Table A1 in Appendix A.

Given the extensive research conducted in the graph-based cybersecurity domain, this paper focuses on and references the most influential pioneering studies (see, for example, [6,7,8,9,10,11], among many others). Interested readers are encouraged to consult the comprehensive surveys for a more detailed discussion of various problem formulations, models, and corresponding vulnerability analysis methods [12,13,14,15,16,17].

In this paper, we focus on two relatively close attack graph formalisms that have been the most well-studied in the literature during the past decades for modeling computer networks from a cybersecurity perspective: exploit-dependency graphs (EDGs) [5,6,7,8,9,10,11] and AND/OR graphs (AOGs) [18,19,20,21,22,23,24,25]. The widespread popularity of EDG and AOG attack models is due to their broad applicability, relatively moderate complexity, and scalability in graph generation.

We next recall the corresponding definitions. The first popular formal model, called the exploit dependency graph, is a directed graph consisting of two types of nodes: exploit and condition nodes. Typically, an exploit node corresponds to a known vulnerability in the network under consideration; and a condition node represents a condition or prerequisite that must be fulfilled or achieved for a successful exploit. Edges represent logical or technological connections between nodes. Other interpretations of nodes and edges are widely known in the literature. For instance, nodes in EDG can represent privileges, vulnerabilities, and host machines, among others (see [12,13,14,15,16,17]). However, the analysis and comparison of these interpretations are beyond the scope of this work.

Each exploit node in EDG can be interpreted as describing an AND combination of its preconditions, and a condition node corresponds to an OR combination of its preceding exploit nodes. In simple terms, each exploit node is of type AND, and each condition node is an OR node in this formal model. The edges in the EDG lead from condition nodes to exploit nodes or from exploit nodes to condition nodes. Thus, the exploit-dependency graph can be viewed as a bipartite AND/OR graph.

To address a combinatorial explosion in the number of nodes, a monotonicity assumption is introduced in [5], which states that if a network component is compromised by an attacker once, it will remain compromised then and forever after. Due to this assumption, the graph model stores exactly one node for each exploit and each security condition, resulting in an attack graph of polynomial size in the number of vulnerabilities and security conditions. This study adheres to the monotonicity assumption. A more detailed investigation of the complexity of EDG generation is beyond the scope of this study.

The second popular formal model, called the AND-OR graph (AOG) [18,19,20,21,22,23,24,25], is a directed graph consisting of two types of nodes: AND and OR nodes. The nodes generally represent different components of the CPS, such as host computers, sensors, routers, and controllers. In this type of graph, the nodes may also optionally represent conditions of an attack graph. If all immediately preceding nodes (subtasks) before the parent node must be accessed to achieve the attacker’s goal, then such a parent node is called an AND node; in this paper, such a node will be displayed as a circle. If executing/accessing any immediately preceding node is sufficient to successfully achieve the goal of the parent node, then such a parent node is called an OR node and is represented as a diamond. The nodes are connected by edges representing possible attacker paths from node to node.

The node set

V

in the AOG is defined as follows:

V = s \cup A N D \cup O R

, where the terms have the following meanings:

$s$ : the start node in the graph, which has no predecessors;
$A N D$ : the set of AND nodes with a conjunctive relationship between their predecessors. That is, all predecessors of an AND node must be accessed before this parent node can be accessed;
$O R$ : the set of OR nodes, where at least one predecessor of such node must be accessed so the parent node can be accessed;
A particular node, either of AND or OR type, is specified as a target of an intruder.

The set of the edges is denoted by

E

The AOG models are beneficial in vulnerability analysis as they are suitable for semantically treating intricate logical interdependencies between CPS components. The EDGs defined above can be easily transformed into the AOGs, which are not necessarily bipartite, making them more general than the EDGs. In the following, we will focus on the cybersecurity of general non-bipartite AOGs. Specifically, our primary attention will be paid to the attack graphs containing directed cycles of positive length.

Now, we highlight the role and importance of attack paths in attack graphs. Discovering (extracting) an attack path is one of the well-known and powerful tools for assessing the actual vulnerability and constitutes the primary focus of the current research. An attack path (AP) is a sequence of steps attackers can take to infiltrate computer systems and reach their target(s). It is a connected acyclic subgraph of the attack graph that typically takes the form of a chain composed of the linked exploits (AND nodes) and conditions (OR nodes). However, in this work, we also explore more general structures of attack paths: we will examine cases where the attack path can take the form of multiple chains, a tree, or other types of acyclic subgraphs in an AND/OR attack graph.

Typically, the AP aims to detect either the most vulnerable nodes in the underlying attack graph [17,18,19,20,21,22,23] or the fastest/cheapest/most effective path to reach a target node in the attack graph [3,15,26]. In this study, similar to [15,26], we investigate the attack graph from a temporal perspective, considering the total time required for the intruder to achieve their objective. Note that our graph-based approach is distinct from studies of the Markov chains, probabilistic models, and propositional logic models widely used in the literature for vulnerability analysis and complements them; however, due to limited space, these popular methods are beyond the scope of this work. For completeness, we note that the path problem extraction is generally known to be NP-hard [17,27]. However, in some special cases (particularly the one studied in this paper), the problem can be solved in polynomial time.

Description of the Attack Path Extraction Problem. The main goal of attack path detection is to identify attack paths in CPS as efficiently as possible. Since the attacker’s goal may vary depending on different problem environments and different system modifications, attack path detection may include different objective functions, such as extracting the path with the minimum length, the path with the maximum damage inflicted, the minimum resource expenditure required to achieve the ultimate goal, and the maximum loss incurred affecting a specific asset. An attacker can be a person, group, or computer program intending to compromise an asset’s confidentiality, integrity, availability, or any other security characteristic. We assume that an attacker (or their group) has sufficient capabilities and resources to simultaneously carry out an attack and compromise multiple vulnerable assets.

Early simplified graph models of attack path discovery treated the underlying attack graphs without weights—see, for example, the models in [5,15], where multiple attack paths were found in an unweighted AG. These models will be extended in this paper. Specifically, in contrast to the unweighted graph models [5,15], we will equip nodes and arcs with timing parameters of the attacker’s hacking/compromising actions and look for the attack path that moves fastest to the target in a given AND/OR attack graph.

Consider an AND/OR attack graph

< G, s, f >

where

G = (V, E, π_{V}, τ_{E})

;

s

and

f

are two selected nodes, the start and target, respectively,

s, f \in V

. The set of nodes

V = s \cup A N D \cup O R \cup f,

and

E

is the set of arcs.

π_{V}

and

τ_{E}

are known sets of times represented as the weights on the nodes in

V

and arcs in

E

, respectively. In particular,

π_{j}

j \in V

, indicates the known time required to carry out a specific action on the node

j

. It can include but is not limited to the known or estimated time for finding and exploiting a vulnerability and escalating privileges after gaining access. In turn,

τ_{k j}

(k, j) \in E

, represents the known transition time required to move from one step of an attacker to another.

t_{j}

\forall j \in V

, denotes non-negative decision variables representing the completion time of the attacker’s compromising activity at node

j

j \in V

The attack path extraction problem is formulated as follows: find a subgraph of a given attack graph such that the completion times of the attacker’s actions to compromise nodes obey inequalities (1)–(3) below, and the completion time at the target node

f

is minimal.

Formally, according to the definition of AND/OR nodes, the completion times at the nodes of the attack path satisfy the following conditions:

t_{j} \geq t_{S}, \forall j \in V

(1)

t_{j} \geq {m a x}_{k \in P r e d (j)} (t_{k} + τ_{k j} + π_{j}), \forall j \in A N D

(2)

t_{j} \geq {m i n}_{k \in P r e d (j)} (t_{k} + τ_{k j} + π_{j}), \forall j \in O R,

(3)

where

P r e d (j)

is the set of nodes immediately preceding node

j

The model in (1)–(3) is applicable for describing and solving path extraction problems on unweighted graphs. In this case, it is sufficient to set in (1)–(3)

π_{j} = 0, f o r a l l n o d e s j \in V

and

τ_{k j} = 1, a n d f o r a l l e d g e s (k, j) \in E

; then, obviously, the objective function will represent the total number of edges in the extracted path. This problem turns into the standard critical path problem (PERT-CPM) if the set

O R

is empty and into the shortest path problem if the set

A N D

is empty [28,29].

The main contributions of this paper are as follows:

(i) We present and explore a new flexible and efficient approach to assessing hostile attack paths and extracting the fastest and, hence, most dangerous vulnerable paths of adversarial attacks in computer networks;

(ii) The attack-path extraction problem is formulated as an optimization problem on AND/OR attack graphs, where the timing characteristics of adversarial actions are injected into the nodes and edges of the graph;

(iii) A new exact polynomial-time path extraction algorithm is developed, which complements previous approximation and heuristic graph algorithms;

(iv) From the defender’s perspective, extraction of the attack path will reveal the most vulnerable places in the cyber network, thus facilitating efficient network hardening;

(v) The proposed algorithm is proven to successfully handle directed cycles of positive length, solving the cyclic graph problem in

O (n m)

time, where

n

is the number of nodes and

m

is the number of edges in the underlying attack graph. The algorithm’s complexity is verified on synthetic and real network examples.

The remainder of this paper is organized as follows. Section 2 briefly overviews the earlier related algorithms and their complexity. Section 3 describes a new fast algorithm and highlights its advantages compared to known related solution algorithms. Section 4 and Section 5 contain illustrative numerical examples and a case study, respectively. Section 6 briefly describes the importance of extracting attack paths for developing countermeasures and cyber-defense. Section 7 concludes the paper.

2. Literature Review

We begin this section with an overview of algorithmic research for the problem of attack graph generation, which was briefly discussed in the Introduction. Attack graph generation occurs in a cyber–physical system when cyber defenders want to identify all possible attack paths that attackers can use to gain unauthorized/unwanted access to the system [5,15,19,24]. Among the most established and influential methods of attack graph generation, we would like to point out the breadth-first search (BFS) method in [5,6,11], the MulVAL analyzer [30], and the topological vulnerability analyzer (TVA) [7]. The interested reader is referred to the review papers [12,13,14,15,16,17] for a much more complete and detailed overview of the relevant methods of attack graph generation.

This paper addresses a different problem: extracting the most vulnerable attack path in a given attack graph. Unlike attack graph generation, the attack path extraction problem we study has a simpler structure and smaller size; hence, it is computationally simpler. Today, many combinatorial path-finding algorithms are known for extracting attack paths on acyclic attack graphs with AND/OR nodes. In such paths, the role of OR nodes is simple and natural—they are used to model the precedence relations between a pair of nodes (which can represent events, actions, a pair of hosts, etc.). However, such a simple presentation—using only OR nodes—is not suitable and is insufficient for solving real problems arising in cybersecurity. Indeed, in an actual attack situation, any complete and practical description of an attacker’s malicious activity must consider and include the fact that usually all important nodes (CPS components) must be protected from attacks, and their predecessors must be protected as well.

Thus, before gaining access to a node in the attack path, an attacker is forced to attack/hack all of its multiple predecessors—which is modeled by an AND node in the graph. As a result, the path extraction model naturally includes two types of nodes, OR and AND. In the cybersecurity literature [20,21,22,23,24], these conditions represented by an AND and OR nodes are called conjunctive and disjunctive, respectively. Classical path-finding algorithms are useless in this case—for example, Dijkstra’s and Bellman–Ford’s shortest path algorithms are known to focus on processing only one predecessor of any node in the path, and as such, they only process graphs with OR-nodes; similarly, a breadth-first search does not work with weighted graphs and is not suitable for processing nodes with logical AND/OR conditions.

The attack path extraction algorithms on AND/OR graphs available in the literature can be divided into two groups: (a) for attack graphs without cycles, and (b) for attack graphs containing cycles. The first group refers to relatively simple combinatorial problems that can be solved efficiently, in polynomial time, using modified known graph algorithms such as BFS and decision trees (see, e.g., [5,9,11,12,13,14,15,16,17,19,31,32,33]).

The models and algorithms of the second group are more difficult and a significant extension of the graph models without cycles. A cycle (also called a loop) in an AG does not mean an attacker moves along this cycle infinitely. It can be a natural result of merging multiple overlapping attack paths or extending an existing AG model over time. In practice, cycles often occur in attack graphs [10,31]. Interest in studying and developing corresponding algorithms on cyclic attack graphs has increased in recent decades.

Nevertheless, as far as we know, today, in the literature, there are only heuristic and approximation methods for solving the path extraction problem on cyclic AND/OR graphs. The first systematic studies of attack graphs with a cyclic topology known to us were conducted by Noel et al. [34] and Wang et al. [10]. These algorithms are based on a modified breadth-first search in the attack graph in combination with the heuristic cycle elimination rules. To eliminate the cycle, ref. [34] proposes removing an exploit (i.e., some AND node) from the cycle, and, accordingly, ref. [10] offers to disable a condition node (i.e., an OR node) in the cycle. The works [10,34] propose promising directions for further development of these methods.

Another interesting practical algorithm successfully extracting paths in the cyclic attack graphs was developed by Homer [20,21]. It was based on unfolding cyclic graphs into acyclic by duplication of nodes. This unfolding algorithm worked well on small and medium-sized graphs, but for large-sized instances, it could cause a size explosion and be impractical since it generated an exponential number of additional nodes.

In sum, the cited algorithms do not guarantee the optimal (minimum time or minimum cost) solution, and their complexity assessments remain incomplete and problematic. We agree with the remark in [24] that “research in this field still seems immature”.

In this context, one of the main goals of this paper is to bridge the gap between the research on attack graph algorithms serving to improve the cybersecurity of CPS, on the one hand, and efficient algorithms on AND/OR graphs, which have been studied in the established fields of operations research and artificial intelligence for more than five decades, where AND/OR graph models have many real-world applications. For example, De Mello and Sanderson [35], Wang and Liu [36], Santos et al. [37,38], and Sotskov [39], among many others, have studied applications to planning and scheduling of various processes with alternative operations. However, in most of these works, the authors studied cycle-free AND/OR graphs and proposed various practical but non-polynomial search algorithms.

In contrast to these studies, in 1990, Dinic [40] proposed an elegant Dijkstra-type polynomial-time algorithm for finding shortest paths in directed bipartite AND/OR graphs with positive operation times. Several years later, Chauvet et al. [41] revisited and improved Dinic’s paper; namely, they extended the algorithm of [40] to handle general (non-bipartite) AND/OR graphs and also fixed the poor language of the original paper [40]. However, the algorithms in [40,41] were not ideally structured and not cybersecurity oriented: in particular, the times on nodes were ignored; positive-length cycles were cunningly hidden between lines; and, most importantly, the short analysis of the algorithm complexity in both [40,41] was imprecise and incorrect. In this paper, we study a path-finding algorithm similar to [40,41] and propose a new fast algorithm specifically tailored for cybersecurity path-finding on cyclic AND/OR attack graphs, which overcomes the algorithmic shortcomings mentioned above in a practically important special case.

To put the landscape of previous work into a broader perspective, we conclude this section with a brief comparison of the proposed graph approach with a relatively new class of methods based on so-called knowledge graphs. A knowledge graph (KG) is a network of arbitrary real-world entities and their relationships; entities are considered nodes, while edges define relationships, and edges and nodes have numerical labels [42]. Over the past few decades, KGs have seen a surge in applications in modeling, management, and control of various CPSs in industry, economics, and communications [42,43,44].

A prominent example of applying KG methods in cybersecurity is CyGraph. This graph-based situational awareness system focuses on visual analysis of cyber-attacks on CPSs and their knowledge management. Using an original knowledge graph model, this intelligent system integrates data, events, and relationships and can, among other things, predict likely attack paths before a cyber-attack occurs and detect critical vulnerabilities in the network [45,46].

Other typical examples of KG applications in the cyber-security domain are given in [47,48], where knowledge graphs are used to represent the network topology, asset data, and vulnerability information, to guide attack path extraction. In these works, KG-based algorithms are developed to extract vulnerable attack paths, and they are applied for automated counterattack defense in electric power systems. The interested reader is referred to the excellent recent reviews [42,43,44] for more detailed information, comprehensive analysis, and the current state of the art.

A thorough review and comparison of the existing KG-based methods available in the literature allows us to state that the knowledge-based graphs and AND/OR graphs are two different and independent categories of graphs that produce complementary models and solution methods. The specificity and advantage of known KG-based methods compared to the proposed graph method are that KGs focus on the rich semantics of multivariate entities and knowledge extraction in solving problems [42,43,44]. Accordingly, KGs reveal a wider range of attack paths and more informative cyber-attack scenarios, including information on the predicted consequences of attacks.

At the same time, the obvious main features and advantages of the proposed AND/OR graph-based algorithm are that (i) it exactly solves the path extraction problem in a strongly polynomial time; (ii) it can effectively solve the studied problem for both cycle-free and cycle-containing attack graphs; and (iii) it successfully works with disjunctive and conjunctive logical relations between nodes, which extends and generalizes the known path-finding problems.

In conclusion, while a more detailed comparison of the two graph categories is beyond the scope of this paper, we believe that integrating knowledge graphs and AND/OR graphs is a promising direction for future research.

In the next section, we propose a polynomial-time algorithm to optimally solve the attack path extraction problem on AND/OR graphs.

3. The Algorithm for Extracting Attack Paths

Compared with previously known path-finding algorithms on AND/OR graphs, the proposed Algorithm 1 for extracting the minimum-length path described in this section has the following differences and advantages:

(i) A new mathematical model for attack path extraction is proposed, in which the durations of the attacker’s malicious actions (hack time/damage) on each node and each edge of the graph are included and accurately studied;

(ii) A new fast, combinatorial Dijkstra-type path-finding algorithm is developed, which takes into account the durations of the attacker’s actions on the edges and nodes of the graph;

(iii) The new algorithm can quickly and efficiently extract optimal attack paths in attack graphs with directed cycles, representing a significant algorithmic gain in cybersecurity from both practical and theoretical points of view, as it helps speed up the computation of attack paths and develop appropriate countermeasures.

The proposed algorithm consists of the following initialization step and three iteratively repeated steps. At the initial step, the algorithm assigns time 0 to the start node S.

F

denotes the set of the nodes for which the algorithm determines step by step the requested completion times

t_{j}

, which are here called permanent labels; the temporal completion times also called temporal labels at a node are denoted

u_{i}

. The full list of notations is presented in Table A2 in Appendix B.

Algorithm 1. Minimum path extraction
Initialization. Set $t_{S} : = 0$ , $u_{i} ≔ + \infty$ for $\forall i \in O R$ and $F : = {n o d e S}$ . Step 1. [Calculate the shortest times for AND-nodes] Choose an arbitrary yet-unvisited AND node $j$ such that all its immediate predecessors, denoted $P r e d (j)$ , are in the set $F .$ If there is no such AND-node in the attack graph, go to Step 2; otherwise, set the permanent completion time of node $j$ as follows:
${t_{j} ≔ m a x}_{k \in P r e d (j)} (t_{k} + τ_{k j} + π_{j}) .$	(4)
Modify the set $F$ as follows: $F : = F \cup j$ , and return to Step 1. Step 2. [Calculate the temporal of OR nodes. To do this, use two alternative ways, denoted Step 2.1 and Step 2.2 below] Step 2.1 Choose an arbitrary unvisited OR-node $i$ such that some of its immediate predecessors (either of type AND or of type OR) are in the set $F$ . Define the temporal time $u_{i}$ of node $i$ as follows:
${u_{i} ≔ m i n}_{k \in [P r e d (i) ⋂ F]} (t_{k} + τ_{k i} + π_{i}) .$	(5)
Step 2.2. Choose an arbitrary unvisited OR-node $p$ such that at least one of its immediate predecessors, denoted $k$ , is of type OR, does not belong to the set $F,$ and has already obtained a finite temporal time value $u_{k}$ at some earlier step of the algorithm. Define the temporal time $u_{p}$ of node $p$ as follows:
${u_{p} ≔ m i n}_{k \in [O R ⋂ P r e d (p) \ F]} (u_{k} + τ_{k p} + π_{p}) .$	(6)
Considering that either of the two cases can occur in the graph under consideration, define $m i n (u_{i}, u_{p})$ and select the OR node, $i$ or $p$ , that has the smaller value of the temporal time, $m i n (u_{i}, u_{p})$ , in (5–6). If none of the OR-nodes in the graph under study satisfies (5) or (6) at this step, then the problem has no solution. Repeat Step 2 for unvisited OR nodes as long as some nodes can change their temporal times according to (5–6). Then go to Step 3. Step 3. [Calculate the permanent earliest time of an OR-node and revise $F$ ]. Choose an OR node $d$ that has the minimum temporal time among all OR nodes defined in Step 2 as follows:
$u_{d} : = {m i n}_{(i, p \in O R \ F)} ({m i n u}_{i}$ ; $m i n u_{p}$ ).	(7)
Set $t_{d} : = u_{d}; F : = F \cup d$ . If, at this step, multiple OR nodes have the same minimum temporary time label $u_{d}$ , assign each of them a permanent time label $t_{d}$ and add them all to the set $F$ . Go to Step 1. Repeat Steps 1–3 cyclically until either (a) all the nodes of the given attack graph will be in the set $F$ , or (b) a permanent time label for the target node will be determined, or (c) neither (5) nor (6) in Steps 2 is satisfied, in which case the problem is unsolvable.

Note a peculiarity of the algorithm presented above: unlike the critical path method, it can handle directed cycles of positive length in the underlying attack graph; this property is ensured by the presence of OR nodes, and in this respect, the proposed algorithm resembles Dijkstra’s shortest path method.

The step-by-step process of the algorithm is visually presented in the flow chart shown in Figure 1.

Next, in the following Claim 1, we estimate the worst-case complexity of the proposed algorithm.

Claim 1.

The complexity of the suggested algorithm is

O (n m),

where

n

is the number of nodes and

m

is the number of edges in the underlying attack graph.

The proof is given in Appendix C.

4. Numerical Examples and Their Analysis

The purpose of this section is to illustrate the implementation of the proposed algorithm on various attack graphs and to investigate its characteristics. The analysis of the obtained results accompanies the solution of numerical examples. We start with a simple cycle-free AND/OR attack graph, where only the edges are weighted with their times (durations) (see Example 1). Then, in Example 2, we add weights to the nodes while keeping the attack graph acyclic, and in Example 3, we add cycles to the weighted graph. The implementation of the algorithm on the unweighted cycle graph is presented in Example 4. Example 5 shows the case when the attack graph with a cycle does not contain a solvable attack path.

Note that the times on nodes and arcs, i.e.,

π_{j}

and

τ_{k j}

, respectively, in all examples are expressed in minutes. These times were obtained from the CVSS (Common Vulnerability Scoring System [49]) and expert assessments, which were then converted into minutes.

Example 1.

This example of the AND/OR attack graph under consideration is adapted from [41] and is shown in Figure 2a. The corresponding graph includes five main nodes, numbered from 2 to 6, with these numbers shown in bold italics inside the nodes. The edges are equipped with known times (durations) marked in blue.

The node Start is an auxiliary node. Among the nodes in Figure 2a, three AND nodes are exploits (shown as ovals) and two OR nodes are conditions (shown as diamonds). The attacker starts from the Start node, and his/her goal is to gain access to the target node 3 in the shortest time.

The proposed algorithm provides the solution presented in Table 1. The rows in Table 1 correspond to the cyclically repeated Steps 1–3 of the algorithm; the columns correspond to the nodes. In the cells of Table 1, we place temporal or permanent time values for the nodes produced by the algorithm.

The algorithm solves this example step by step as follows. It starts with the initialization step, in which it assigns a permanent time

t_{S} = 0

to the Start node and temporal times (“temporal labels”)

u_{i} = \infty

to all OR nodes; then, the Start node is added to the set

F

, which stores all nodes with permanent (i.e., minimal) completion times. Next, in Step 1, the algorithm searches for and scans AND nodes for which all predecessors are in the set

F

. Since node 2 in this example has only one predecessor, the node Start, which is already in

F

, a permanent label for node 2 is calculated according to (4), and this node is added to

F

(see the row labeled (1) in the third line of Table 1). The given time parameters are used as follows. According to (4), the permanent time label

t_{2}

for node 2 is calculated as follows:

t_{2} ≔ t_{s} + τ_{s 2} + π_{2} = 2

, where

t_{s} = 0;

τ_{s 2} = 2

; and

π_{2} = 0

. At this step, we consider that node 2 has only one predecessor. Note that two other AND nodes, 3 and 4, do not yet have all their predecessors in

F

, so they cannot receive a permanent label at this step, and therefore the algorithm goes to Step 2.

In Step 2, the temporal time labels

u_{i}

for the OR nodes are calculated according to (5) and (6) (see row (2) of Table 1). For instance, the temporal time for node 6 is calculated as follows:

u_{6} ≔ t_{2} + τ_{26} + π_{6} = 3

, where

t_{2} = 2

τ_{26} = 1

, and

π_{6} = 0

Then, in Step 3, among all temporal labels of the OR nodes, node 6 with the smallest temporal label is chosen and granted a permanent time label

t_{6}

, as shown in row (3) in Table 1. This node is added to set

F .

Since the permanent time label for the target node 3, has not been found yet, the algorithm goes again to Step 1 (row (1) in the last line of Table 1). During the execution of Step 1, the permanent label for the AND node 3 can be defined because all its predecessors, i.e., nodes 2 and 6, are already in the set

F

. The algorithm terminates when the minimal time for the target node 3 is found.

As can be seen in Table 1, the overall minimum attack time to compromise the target node 3 is 6 min. The corresponding attack path is shown in Figure 2b with a thick dashed line. This attack path is optimal, in the sense that it has the minimum length among the attack paths in the attack graph under consideration. A configuration of the resulting attack path, the subgraph in Figure 2b, is neither a chain nor a tree but a “flower graph”. Recall that in this study, we assume that the attacker (which could be a group of people or a set of programs) can perform multiple malicious actions simultaneously. In the considered Example 1 in Figure 2b, this means that after the attacker has gained access to node 2, they have enough resources to simultaneously perform his/her transition actions on edges from 2 to 3 and from 2 to 6.

Next, we will consider more general (and more realistic) formulations of the problem, in which the durations of the attacker’s compromising activities on nodes are added to the model, which can significantly affect the duration and configuration of the attack path.

In Example 2, we consider the path extraction problem on the attack graph with both node and edge times.

Example 2.

Consider the attack graph shown in Figure 3a. It is an acyclic AND/OR graph with weighted edges and nodes: nodes are equipped with known times (durations) marked in red, and all edge times are marked in blue.

Here, the problem is to find the attack path of the smallest duration from the Start to node 3. All steps of the algorithm in solving the problem are shown in Table 2, and the extracted minimum-length attack path is shown in Figure 3b with a thick dashed line.

Table 2 shows that the minimum attack time to compromise target node 3 is 15 min. The extracted attack path presented in Figure 3b, shown with a thick dashed line, notably differs from the one found in Figure 2b, when the attack times on nodes were neglected. Although the attack path in Figure 3b includes more nodes to be compromised before the target node is reached compared to the one presented in Figure 2b, it is shorter in terms of the overall attack time when the times on nodes are considered: the alternative attack path AP = {start → 2 → 6 → 3} will result in an overall attack time of 18 min.

Example 3.

Consider the attack graph shown in Figure 4a. It is a cycled graph with weighted edges and nodes. Nodes are equipped with known times marked in red, and all edge times are marked in blue. The intruder’s goal is to access node 7.

The proposed algorithm provides the solution presented in Table 3. The attack path is shown in Figure 4b.

Unlike the attack graphs presented in Figure 2a and Figure 3b, the attack graph in Figure 4a contains a cycle, which makes the path-finding problem more difficult. As we can see in Table 3, the proposed algorithm successfully detects and eliminates the cycle and quickly solves the problem, providing an optimal cycle-free attack path, shown in Figure 4b.

For completeness, we consider an unweighted attack graph similar to that presented in Figure 4a, that is, we set

π_{j} = 0, \forall j \in V

and

τ_{k j} = 1, \forall (k, j) \in E

. This graph is presented in Figure 5a.

Example 4.

The AND/OR attack shown in Figure 5a is an unweighted attack graph with cycles. The intruder’s goal is to access node 7.

The solution for the attack graph in Figure 5a is presented in Table 4 and shown in Figure 5b.

Figure 5b shows that the solution presented in Table 4 leads to two equivalent attack paths with the same shortest length of 3 min. The first extracted path is AP₁ = {start → 6 → 3 → 7} (see the purple path in Figure 5b) and the second one is AP₂ = {start → 5 → 2 → 7} (see the red path in Figure 5b). The obtained paths differ from the path found in the weighted attack graph, shown in Figure 4b. The paths presented in Figure 5b are shorter in length and include fewer nodes that the intruder must compromise before the target will be accessed.

The attack graphs presented in Examples 3 and 4 (see Figure 4a and Figure 5a, respectively) include cycles that the proposed algorithm successfully processed and eliminated.

Remark 1.

Unlike the cycle eliminating algorithms [10,34], in which the cycle is detected by the decision-maker, the proposed algorithm detects and eliminates the cycle without human intervention.

Remark 2.

In some practical cases, the problem with cycles may not be solved by the proposed algorithm, in which case the algorithm terminates without accessing the target.

A numerical example of such a case is presented in Example 5.

Example 5.

The AND/OR attack graph shown in Figure 6 is equipped with the times on nodes and arcs and has cycles. The intruder’s goal is to access node 7.

The execution of the algorithm is presented in Table 5.

As one can see in Table 5, the algorithm cannot set the permanent time label to an unvisited OR node (target) 7 (see the last row in Table 5), and therefore, must stop before the target is reached. This means that the solution does not exist and, thus, this problem is unsolvable, that is, the target node 7 is impossible to access.

5. A Case Study

In this section, we study a more realistic example of an attack graph of larger size with actual data and an attack on a network with AND/OR nodes. The example is adapted from [20] and shown in Figure 7.

The attacker’s target in Figure 7 is node G. As we argued in the Introduction, the AND nodes correspond to exploits, representing the specific actions or steps an attacker must take to exploit a vulnerability within the system. The OR nodes are associated with privileges, representing the conditions that must be satisfied or acquired during the attack. These privileges involve gaining certain access rights or control over a part of the system. The description of the conditions is given in Table 6. The description of the AND nodes is presented in Table 7. Note that the meaning of vulnerabilities and the CVE codes in columns #2–#3 in Table 7 are borrowed from [49].

The attack graph from [20] is modified as follows: the edges and nodes are equipped with weights representing the expected action durations of the attacker (in minutes); they are obtained from the Common Vulnerability Scoring System [49] and expert assessments.

Table 8 below shows the operations of the algorithm executed step by step.

The shortest extracted attack path is shown in a thick dashed line in Figure 8 and is as follows: AP* = {start → 1 → 2 → {A∪B} → 3 → C →7 → D→ 11 → G}. Its duration is 295 min (see Table 8). A randomly generated path AP’ = {start → 2 → B → 5 → F → 12 → G} is shorter in the number of steps and longer in time.

This case study shows the main advantage of the proposed algorithm. Namely, unlike the cycle-unfolding method [20], where a node in a cycle is replaced by multiple additional nodes in the attack graph, which leads to the explosive growth in the attack graph size, the proposed algorithm does not increase the size of the original problem and effectively copes with the cycles.

The role of attack path extraction in cyber-defense is discussed in Section 6.

6. Cyber-Defense and Countermeasures Against Attack Paths

This paper provides theoretical and computational results that prove that attack paths are a valuable working tool for studying possible cyber threats related to intruders’ penetration into CPSs. Extracting the shortest attack path, as achieved in this work, allows defenders to detect the most vulnerable assets and analyze different types of prepared countermeasures in case of an attack, to thwart the attackers’ intention.

Countermeasures against cyber-attacks include corrective actions, procedures, special devices, and methods aimed at reducing threats, neutralizing vulnerabilities, and eliminating or preventing damage to the CPSs caused by an adversary’s malicious actions. These countermeasures are generally divided into three main categories. The first category is preventive measures, which are designed to stop an attack before an intruder can exploit a vulnerability. Early identification of the shortest attack path allows defenders to better understand which critical components of the system should be defended first or which devices should be regularly patched and updated.

The second category is detection measures, which include various actions related to identifying and reporting threats as they occur. For example, machine learning and big data techniques can detect unusual patterns by scanning the network. Knowing the most likely attack paths allows defenders to understand which network segments to focus on and where to place detection systems, such as intrusion detection systems. The third category is corrective actions. In addition to preventive and detective measures, which are usually performed proactively, corrective actions are taken after an attack is detected to mitigate its impact or recover from the damage caused. Attack path analysis may help isolate affected systems or segments, to prevent an attacker from moving further along the attack path.

The fast and easy-to-use path extraction algorithm proposed in this paper may serve as an assistant tool with other countermeasures. The schematic representation of a defender’s actions using different types of countermeasures in response to malicious actions along an attack path is shown in Figure 9.

7. Conclusions

This study focused on developing an efficient method for extracting a minimum-time attack path in given attack graphs. Determining the possible attack path of an intruder is critically important for cyber-defense as it helps identify threats and thwart attacker intentions. The corresponding solution methods developed to date for path extraction in cyclic AND/OR attack graphs are heuristic, require human intervention, and provide only an approximate solution.

In this paper, we have proposed a novel algorithm that, compared to previously known path-finding algorithms on AND/OR graphs, introduces and processes the attacker’s actions on both nodes and edges of the attack graphs and determines the optimal attack path in polynomial time, O(nm), where n is the number of nodes and m is the number of edges in the attack graph. These factors represent significant algorithmic advantages in cybersecurity from both practical and theoretical points of view, as they help speed up the computation of attack paths. To the best of our knowledge, this is the first polynomial algorithm that can exactly solve the path extraction problem for AND/OR attack graphs, both containing and not containing cycles. Computational experiments on real and synthetic data show that the proposed algorithm consistently and quickly finds optimal solutions to the problem.

In future research, it would be desirable and practice-minded to further develop the proposed AND/OR graph-based approach to improve network security, by combining two different concepts, attack paths and defense trees, to achieve this goal; this will lead to a more complex two-layer attack/defense graph that includes both attack and defense actions, thereby improving the cybersecurity model. Another practical and promising direction for future research is to integrate two categories of graphs, knowledge graphs and AND/OR graphs, thereby leveraging the advantages of each graph type and expanding the range and information content of the extracted knowledge about attack paths, vulnerabilities, and attack countermeasures.

Author Contributions

Conceptualization, E.L. and D.T.; methodology, E.L.; validation, E.L. and D.T; writing—original draft preparation, E.L. and D.T. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

Data is contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

Appendix A

Table A1. The list of key terms used in this paper.

Term	Meaning of the Term
attack, or cyber-attack	any unwanted, deliberate attempt to steal, disclose, alter, disable, or destroy programs, data, applications, or other assets through unauthorized access to a CFS, computer network, system, or digital device.
attack graphs (AG)	visual models of network insecurities that show in graphical form possible paths of where and how an attacker has completed a successful breach and compromised a computer network, system, or host computer. Two AG formalisms are best studied for modeling CPS from a cybersecurity perspective: exploit-dependency graphs and AND/OR attack graphs.
attack path	a visual representation of an attacker’s specific journey to access sensitive data or leverage system access to exploit vulnerabilities. An attack path is an acyclic subgraph of a given attack graph in which all nodes satisfy conditions (iii–iv) of the definition of an attack path given in Section 1.
attack path extraction	a systematic review of the components, connections, and interactions within a given cyber–physical system to infer/map potential sequences of actions that an attacker might exploit. By reproducing these pathways, defenders can assess the potential impact and risk of multiple attack scenarios and ultimately prioritize their risk mitigation efforts more effectively.
attacker (or intruder)	person or group committing malicious acts with intent to destroy, alter, steal data, gain unauthorized access, or make unauthorized use of an asset.
accessible (reachable) node	a node for which there exists an attack path from the start node to the target.
AND/OR graph (AOG)	a directed graph consisting of two types of nodes: AND and OR nodes. The nodes in AOG generally represent different components of the CPS, such as host computers, sensors, routers, and controllers. In this type of graph, the nodes may also optionally represent conditions of an attack graph.
AND/OR nodes	AND nodes have conjunctive, whereas OR nodes have disjunctive relationships with their predecessors. More specifically, if all predecessors must be accessed before the considered node is attacked, such a node is called an AND node. If executing/accessing any predecessor is sufficient to achieve the considered node, then such a node is called an OR node.
condition	a specific prerequisite must be fulfilled or achieved for a successful exploit.
cyber–physical system (CPS)	a network of interconnected physical and computer components to securely, flexibly, and effectively manage integrated computing, networking, and physical processes.
cybersecurity	the state of the network being free from danger or threat.
cyber-defense	the action of defending from or resisting attack.
data exfiltration	a type of security breach that includes unauthorized copying, transfer, or retrieval of data from either a server or an individual’s computer without proper authorization with malicious intent.
defender	an application or an individual that monitors in real-time for malware, viruses, and other security threats.
exploit	a piece of software/data or a set of commands that use a vulnerability to cause unintended or unanticipated behavior in a CPS’s software or hardware. Exploits allow attackers to gain remote access to a target network and penetrate deeper into the network.
exploit-dependency graph (EDG)	a directed attack graph composed of two types of nodes: exploit nodes and condition nodes. An exploit node corresponds to an exploit in the considered network; a condition node denotes that a specific host is reachable by an intruder, this host has a vulnerability, and an attacker compromises the host. Edges run from condition nodes to exploit nodes or from exploit nodes to condition nodes, i.e., the exploit-dependency graph is bipartite.
hardening a system	see network hardening.
hostile attack	a form of a cyber warfare that has a goal of espionage, where information or data are stolen via the Internet, or of sabotage, such as compromising a node. The attacks usually come in the form of a computer virus or through a coordinated attack by a network of hostile computer systems.
intruder	see attacker.
leverages access to exploit vulnerability	to effectively use system access to exploit vulnerabilities.
leverage attack paths	to use different paths to access sensitive information and exploit a vulnerable configuration or resource.
malware	intentionally designed malicious software to cause disruption or damage, steal data, damage or destroy computers and computer systems; the types of malware include viruses, worms, trojans, spyware, and ransomware.
monotonicity	an assumption that if a network component is compromised by an attacker once, it will remain compromised then and forever after. The monotonicity allows for a significant reduction in the AG size.
network hardening	implementing cyber-security actions and measures to strengthen a network’s defenses and protect sensitive data. It includes vulnerability assessments, securing open ports, and predicting an attacker’s likely paths.
parent node, child	a node v that has an edge leading to it from an immediately preceding node w is called the parent node (or successor), while w is a predecessor or child of v.
privilege	a permission/right to perform a computer operation or access a database.
vulnerability	an instance of one or more weaknesses in a computer system that an attacker can exploit to carry out a successful malicious attack, causing a negative impact on confidentiality, integrity, or availability of the system. It can happen due to user flaws or errors, and attackers will exploit any of them.
vulnerability analysis	methodology that is systematically carried out to identify, classify, prioritize, and mitigate vulnerabilities and security risks
weaponization (in cybersecurity)	creating or modifying malware to exploit specific vulnerabilities; weaponization enhances the effectiveness of cyber-attacks, making them more sophisticated and harder to detect.

Appendix B

Table A2. Notations used in this paper.

Notation	Description
$i$	Index of an OR node in the attack graph
$j$	Index of an AND node in the attack graph
$s, f$	Starting and target nodes
$V$	Set of nodes
$E$	Set of edges
$O R$ $(A N D)$	The set of all OR nodes (respectively, all AND nodes) in the graph
$P r e d (i) / P r e d (j)$	The predecessor set of node $i / n o d e j$
$u_{i}$	A temporal earliest completion time on the node $i$
$t_{i}$	A permanent earliest completion time on the node $i$ (decision variable)
$t_{j}$	A permanent earliest completion time on the node $j$ (decision variable)
$F$	The set of nodes for which the permanent times are defined; any of these nodes is called visited
$τ_{k j}$	Time (duration) of the attacker’s compromise action in edge $(k, j)$ from node $k$ to node $j$
$π_{j}$	Duration of the attacker’s compromise action in node $j$

Appendix C. The Proof of Claim 1

Proof.

Initialization Step: The initialization procedure requires linear time

O (n)

Step 1: During one run of this step, the occurrence times

t_{j}

, for all AND nodes that have predecessors in set

F

, must be calculated. According to (4), the calculation of

t_{j}

for one node

j

will be proportional to the cardinality of the set

P r e d (j) .

Since each AND node is connected to any of its predecessors by exactly one arc, the calculation of all occurrence times

t_{j}

of all AND nodes that have predecessors in set

F

will be at most

O (|E|) = O (m)

. Then, accounting for the number of runs of Step 1 after Step 3 during the execution of the entire algorithm, which cannot exceed the total number of OR nodes, the total complexity of this step is then

O (n m)

Step 2: In the worst case, the total complexity of this step is also

O (n m)

. The proof follows the same lines as for Step 1, so we omit it here.

Step 3: During each run of Step 3, the operation (7) seeks to use the minimum time, which can be achieved in

O (n)

time. Given that the number of runs of this step cannot exceed the total number of OR nodes, the total complexity of this step is

O (n^{2})

in the worst case.

From the above estimation of the Initialization Step and Steps 1–3, it follows that the total complexity of the entire algorithm is

O (n m)

. □

References

Almansoori, A.; Al-Emran, M.; Shaalan, K. Exploring the Frontiers of Cybersecurity Behavior: A Systematic Review of Studies and Theories. Appl. Sci. 2023, 13, 5700. [Google Scholar] [CrossRef]
Taherdoost, H. Insights into Cybercrime Detection and Response: A Review of Time Factor. Information 2024, 15, 273. [Google Scholar] [CrossRef]
Wang, W.; Sun, D.; Jiang, F.; Chen, X.; Zhu, C. Research and Challenges of Reinforcement Learning in Cyber Defense Decision-Making for Intranet Security. Algorithms 2022, 15, 134. [Google Scholar] [CrossRef]
Phillips, C.; Swiler, L.P. A Graph-Based System for Network-Vulnerability Analysis. In Proceedings of the 1998 Workshop on New Security Paradigms, Charlottesville, VA, USA, 22–25 September 1998; pp. 71–79. [Google Scholar]
Ammann, P.; Wijesekera, D.; Kaushik, S. Scalable, Graph-Based Network Vulnerability Analysis. In Proceedings of the ACM Conference on Computer and Communications Security, Washington, DC, USA, 18–22 November 2002; pp. 217–224. [Google Scholar] [CrossRef]
Sheyner, O.; Haines, J.; Jha, S.; Lippmann, R.; Wing, J.M. Automated Generation and Analysis of Attack Graphs. In Proceedings of the IEEE Symposium on Security and Privacy, Berkeley, CA, USA, 12–15 May 2002; IEEE: Piscataway, NJ, USA, 2002; pp. 273–284. [Google Scholar] [CrossRef]
Jajodia, S.; Noel, S.; O’berry, B. Topological Analysis of Network Attack Vulnerability. In Managing Cyber Threats: Issues, Approaches, and Challenges; Springer: Berlin/Heidelberg, Germany, 2005; pp. 247–266. [Google Scholar]
Noel, S.; Jajodia, S. 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), Washington, DC, USA, 29 October 2004; pp. 109–118. [Google Scholar] [CrossRef]
Noel, S.; Robertson, E.; Jajodia, S. Correlating Intrusion Events and Building Attack Scenarios through Attack Graph Distances. In Proceedings of the Annual Computer Security Applications Conference (ACSAC), Tucson, AZ, USA, 6–10 December 2004; IEEE: Piscataway, NJ, USA, 2004; pp. 350–359. [Google Scholar] [CrossRef]
Wang, L.; Noel, S.; Jajodia, S. Minimum-Cost Network Hardening Using Attack Graphs. Comput. Commun. 2006, 29, 3812–3824. [Google Scholar] [CrossRef]
Ingols, K.; Lippmann, R.; Piwowarski, K. Practical Attack Graph Generation for Network Defense. In Proceedings of the Annual Computer Security Applications Conference (ACSAC), Miami Beach, FL, USA, 11–15 December 2006; IEEE: Piscataway, NJ, USA, 2006; pp. 121–130. [Google Scholar] [CrossRef]
Lippmann, R.P.; Ingols, K.W. An Annotated Review of Past Papers on Attack Graphs; No. PR-IA-1; Citeseer: Princeton, NJ, USA, 2005. [Google Scholar]
Kaynar, K. A Taxonomy for Attack Graph Generation and Usage in Network Security. J. Inf. Secur. Appl. 2016, 29, 27–56. [Google Scholar] [CrossRef]
Lallie, H.S.; Debattista, K.; Bal, J. A Review of Attack Graph and Attack Tree Visual Syntax in Cyber Security. Comput. Sci. Rev. 2020, 35, 100219. [Google Scholar] [CrossRef]
Zenitani, K. Attack Graph Analysis: An Explanatory Guide. Comput. Secur. 2023, 126, 103081. [Google Scholar] [CrossRef]
Wachter, J. Graph Models for Cybersecurity—A Survey. arXiv 2023, arXiv:2311.10050. [Google Scholar]
Zeng, J.; Wu, S.; Chen, Y.; Zeng, R.; Wu, C. Survey of Attack Graph Analysis Methods from the Perspective of Data and Knowledge Processing. Secur. Commun. Netw. 2019, 2019, 2031063. [Google Scholar] [CrossRef]
Ou, X.; Boyer, W.F.; McQueen, M.A. A Scalable Approach to Attack Graph Generation. In Proceedings of the ACM Conference on Computer and Communications Security, Alexandria, VA, USA, 30 October–3 November 2006; pp. 336–345. [Google Scholar] [CrossRef]
Wang, L.; Islam, T.; Long, T.; Singhal, A.; Jajodia, S. An Attack Graph-Based Probabilistic Security Metric. In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Springer: Berlin/Heidelberg, Germany, 2008; Volume 5094, LNCS; pp. 283–296. [Google Scholar] [CrossRef]
Homer, J. A Comprehensive Approach To Enterprise Network Security Management; Kansas State University: Manhattan, KS, USA, 2009. [Google Scholar]
Homer, J.; Zhang, S.; Ou, X.; Schmidt, D.; Du, Y.; Rajagopalan, S.R.; Singhal, A. Aggregating Vulnerability Metrics in Enterprise Networks Using Attack Graphs. J. Comput. Secur. 2013, 21, 561–597. [Google Scholar] [CrossRef]
Matthews, I. Machine Learning and Probabilistic Methods for Network Security Assessment. Newcastle University. 2022. Available online: https://theses.ncl.ac.uk/jspui/handle/10443/5677 (accessed on 21 August 2024).
Barrère, M.; Hankin, C. Analysing Mission-Critical Cyber-Physical Systems with AND/OR Graphs and MaxSAT. ACM Trans. Cyber-Phys. Syst. 2021, 5, 1–29. [Google Scholar] [CrossRef]
Zenitani, K. A Scalable Algorithm for Network Reachability Analysis with Cyclic Attack Graphs. J. Comput. Secur. 2023, 31, 29–55. [Google Scholar] [CrossRef]
Sadeghian, A. Detecting the Most Vulnerable Nodes in the AND-OR Graph Using MITRE ATT&CK; Laval University Library: Québec, QC, Canada, 2024. [Google Scholar]
Ingoldsby, T.R. Attack Tree Threat Risk Analysis; Amenaza Technol. Ltd.: Calgary, AB, Canada, 2013; p. 36. [Google Scholar]
Desmedt, Y.; Wang, Y. Analyzing Vulnerabilities of Critical Infrastructures Using Flows and Critical Vertices in and/or Graphs. Int. J. Found. Comput. Sci. 2004, 15, 107–125. [Google Scholar] [CrossRef]
Adelson-Velsky, G.M.; Levner, E. Project Scheduling in AND-OR Graphs: A Generalization of Dijkstra’s Algorithm. Math. Oper. Res. 2002, 27, 504–517. [Google Scholar] [CrossRef]
Adelson-Velsky, G.M.; Gelbukh, A.; Levner, E. On Fast Pathfinding Algorithms in AND-OR Graphs. Math. Probl. Eng. 2002, 8, 283–293. [Google Scholar] [CrossRef]
Ou, X.; Govindavajhala, S.; Appel, A.W. MulVAL: A Logic-Based Network Security Analyzer. In Proceedings of the USENIX Security Symposium, Baltimore, MD, USA, 31 July–5 August 2005; Volume 8, pp. 113–128. [Google Scholar]
Zhang, J.; Wang, W.; Zio, E. Study on the Application of Graph Theory Algorithms and Attack Graphs in Cybersecurity Assessment. In Proceedings of the 2023 7th International Conference on System Reliability and Safety (ICSRS), Bologna, Italy, 22–24 November 2023; IEEE: Piscataway, NJ, USA, 2023; pp. 558–564. [Google Scholar] [CrossRef]
Mishra, S.; Alotaibi, W.B.; Alshehri, M.; Saxena, S. Cyber-Attacks Visualisation and Prediction in Complex Multi-Stage Network. Int. J. Comput. Appl. Technol. 2022, 68, 345–356. [Google Scholar] [CrossRef]
Arat, F.; Akleylek, S. Attack Path Detection for IIoT Enabled Cyber Physical Systems: Revisited. Comput. Secur. 2023, 128, 103174. [Google Scholar] [CrossRef]
Noel, S.; Jajodia, S.; O’Berry, B.; Jacobs, M. Efficient Minimum-Cost Network Hardening via Exploit Dependency Graphs. In Proceedings of the Annual Computer Security Applications Conference (ACSAC), Las Vegas, NV, USA, 8–12 December 2003; IEEE: Piscataway, NJ, USA, 2003; pp. 86–95. [Google Scholar] [CrossRef]
De Mello, L.S.H.; Sanderson, A.C. AND/OR Graph Representation of Assembly Plans. IEEE Trans. Robot. Autom. 1990, 6, 188–199. [Google Scholar] [CrossRef]
Wang, T.; Liu, D.X. Scheduling AND/OR Precedence Constraints Jobs to Minimize the Makespan by Mapping from CPM to AND/OR Network. In Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Hong Kong, China, 17–19 August 2005; IEEE: Piscataway, NJ, USA, 2005; pp. 169–172. [Google Scholar] [CrossRef]
dos Santos Souza, U.; Protti, F. Tractability, Hardness, and Kernelization Lower Bound for and/or Graph Solution. Discret. Appl. Math. 2017, 232, 125–133. [Google Scholar] [CrossRef]
Souza, U.D.S.; Protti, F.; Dantas Da Silva, M. Revisiting the Complexity of and/or Graph Solution. J. Comput. Syst. Sci. 2013, 79, 1156–1163. [Google Scholar] [CrossRef]
Sotskov, Y.N. Assembly and Production Line Designing, Balancing and Scheduling with Inaccurate Data: A Survey and Perspectives. Algorithms 2023, 16, 100. [Google Scholar] [CrossRef]
Dinic, E.A. The Fastest Algorithm for the PERT Problem with AND-and OR-Nodes (the New-Product-New-Technology Problem). In Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, Waterloo, ON, Canada, 28–30 May 1990; pp. 185–187. [Google Scholar]
Chauvet, F.; Levner, E.; Proth, J.-M. On PERT Networks with Alternatives; INRIA: Le Chesnay-Rocquencourt, France, 1998. [Google Scholar]
Zhang, K.; Liu, J. Review on the Application of Knowledge Graph in Cyber Security Assessment. In IOP Conference Series: Materials Science and Engineering; IOP Publishing: Bristol, UK, 2020; Volume 768, p. 52103. [Google Scholar] [CrossRef]
Xue, B.; Zou, L. Knowledge Graph Quality Management: A Comprehensive Survey. IEEE Trans. Knowl. Data Eng. 2023, 35, 4969–4988. [Google Scholar] [CrossRef]
Liu, K.; Wang, F.; Ding, Z.; Liang, S.; Yu, Z.; Zhou, Y. Recent Progress of Using Knowledge Graph for Cybersecurity. Electronics 2022, 11, 2287. [Google Scholar] [CrossRef]
Noel, S.; Harley, E.; Tam, K.H.; Limiero, M.; Share, M. CyGraph: Graph-Based Analytics and Visualization for Cybersecurity. In Handbook of Statistics; Elsevier: Amsterdam, The Netherlands, 2016; Volume 35, pp. 117–167. [Google Scholar] [CrossRef]
Noel, S.; Purdy, S.; O’Rourke, A.; Overly, E.; Chen, B.; DiFonzo, C.; Chen, J.; Sakellis, G.; Hegde, M.; Sapra, M.; et al. Graph Analytics and Visualization for Cyber Situational Understanding. J. Def. Model. Simul. 2023, 20, 81–95. [Google Scholar] [CrossRef]
Wang, W.; Han, L.; Ge, G.; Yang, Z. An Algorithm of Optimal Penetration Path Generation under Unknown Attacks of Electric Power WEB System Based on Knowledge Graph. In Proceedings of the 2021 2nd International Conference on Computer Communication and Network Security (CCNS), Xining, China, 30 July–1 August 2021; IEEE: Piscataway, NJ, USA, 2021; pp. 141–144. [Google Scholar] [CrossRef]
Liu, R.; Fu, R.; Xu, K.; Shi, X.; Ren, X. A Review of Knowledge Graph-Based Reasoning Technology in the Operation of Power Systems. Appl. Sci. 2023, 13, 4357. [Google Scholar] [CrossRef]
Byers, R.; Turner, C.T.B. National Vulnerability Database; NIST (National Institute of Standards and Technology): Gaithersburg, MD, USA, 2020. [Google Scholar]

Figure 1. The flow chart of the proposed algorithm.

Figure 2. (a) Example 1 adapted from [41]. (b) Extracted minimum-length attack path.

Figure 3. (a) Acyclic attack graph equipped with the node times. (b) Extracted minimum-length attack path for Example 2.

Figure 4. (a) Attack graph with cycles. (b) Extracted minimum-length attack path.

Figure 5. (a) The unweighted attack graph with cycles. (b) Extracted minimum-length attack path.

Figure 6. Attack graph with cycles without an attack path.

Figure 7. The extended attack graph with the start node (adapted from [20]).

Figure 8. Extracted minimum-length attack path for the attack graph in Figure 7.

Figure 9. A scheme of defenders’ response to a malicious attack.

Table 1. Solution to Example 1.

	Start	2	3	4	5	6
Step	Start	2	3	4	5	6
Initial	$t_{S} = 0$				$u_{5} = \infty$	$u_{6} = \infty$
(1)		$t_{2} = 2$
(2)					$u_{5} = 4$	$u_{6} = 3$
(3)						$t_{6} = 3$
(1)			$t_{3} = 6$

Table 2. Solution to Example 2.

	Start	2	3	4	5	6
Step	Start	2	3	4	5	6
Initial	$t_{S} = 0$				$u_{5} = \infty$	$u_{6} = \infty$
(1)		$t_{2} = 12$
(2)					$u_{5} = 4.5$	$u_{6} = 14$
(3)					$t_{5} = 4.5$
(1)				$t_{4} = 6$
(2)						$u_{6} = 9$
(3)						$t_{6} = 9$
(1)			$t_{3} = 15$

Table 3. Solution to Example 3.

	Start	2	3	4	5	6
Step	Start	2	3	4	5	6
Initial	$t_{S} = 0$			$u_{5} = \infty$	$u_{6} = \infty$	$u_{7} = \infty$
(1)
(2)				$u_{5} = 9.5$	$u_{6} = 3$	$u_{7} = \infty$
(3)					$t_{6} = 3$
(1)			$t_{3} = 7$
(2)				$u_{5} = 8.5$		$u_{7} = 18$
(3)				$t_{5} = 8.5$
(1)		$t_{2} = 10$
(2)						$u_{7} = 12.5$
(3)						$t_{7} = 12.5$

Table 4. Solution to Example 4.

	Start	2	3	5	6	7
Step	Start	2	3	5	6	7
Initial	$t_{S} = 0$			$u_{5} = \infty$	$u_{6} = \infty$	$u_{7} = \infty$
(1)
(2)				$u_{5} = 1$	$u_{6} = 1$	$u_{7} = \infty$
(3)				$t_{5} = 1$	$t_{6} = 1$
(1)		$t_{2} = 2$	$t_{3} = 2$
(2)						$u_{7} = 3$
(3)						$t_{7} = 3$

Table 5. Solution to Example 5.

	Start	2	3	5	6	7
Step	Start	2	3	5	6	7
Initial	$t_{S} = 0$			$u_{5} = \infty$	$u_{6} = \infty$	$u_{7} = \infty$
(1)
(2)				$u_{5} = 9.5$	$u_{6} = 3$	$u_{7} = \infty$
(3)					$t_{6} = 3$
(1)			$t_{3} = 7$
(2)				$u_{5} = 8.5$		$u_{7} = \infty$
(3)				$t_{5} = 8.5$
(1)
(2)						$u_{7} = \infty$

Table 6. The list of OR nodes used in the attack graph presented in Figure 7.

Node ID (#1)	Node Description (#2)	Compromising Time (in Minutes) (#3)
A	Initial access obtained (e.g., phishing, exploiting an external service)	30
B	Privilege escalation	15
C	Gained Remote Code Execution (RCE) privileges	60
D	Gaining access to restricted or high-privilege resources	15
E	Execution of unauthorized or harmful operations	20
F	Gaining administrative privileges	1
G	Stealing sensitive data	30

Table 7. The list of exploits used in the attack graph presented in Figure 7.

Node ID (#1)	Vulnerability (#2)	CVE Reference (#3)	Compromising Time (in Minutes) (#4)
1	Microsoft’s Windows Print Spooler service vulnerability	CVE-2021-34527	10
2	Windows Netlogon Service vulnerability	CVE-2020-1472	20
3	Remote desktop services’ vulnerability	CVE-2019-0708	30
5	Microsoft’s Windows certificate vulnerability	CVE-2020-0601	50
6	Unix mail transfer vulnerability	CVE-2018-6789	20
7	Microsoft’s Windows SMB protocol vulnerability	CVE-2017-0144	10
8	Enterprise network infrastructure vulnerability	CVE-2021-22986	45
9	HTTP Protocol vulnerability	CVE-2021-31166	60
10	Windows name resolution server vulnerability	CVE-2020-1350	10
11	Web application vulnerability	CVE-2017-5638	5
12	Microsoft .NET Framework vulnerability	CVE-2017-8759	60
13	Microsoft Office Memory Corruption Vulnerability	CVE-2017-11882	6

Table 8. Solution to the numerical example in Figure 7.

	Start	1	2	3	5	6	7	8	9	10	11	12	A	B	C	D	E	F	G
Step	Start	1	2	3	5	6	7	8	9	10	11	12	A	B	C	D	E	F	G
Initial	$t_{s} = 0$												$u_{A} = \infty$	$u_{B} = \infty$	$u_{C} = \infty$	$u_{D} = \infty$	$u_{E} = \infty$	$u_{F} = \infty$	$u_{G} = \infty$
(1)		$t_{1} = 10$	$t_{2} = 20$
(2)													$u_{A} = 45$	$u_{B} = 60$	$u_{C} = \infty$	$u_{D} = \infty$	$u_{E} = \infty$	$u_{F} = \infty$	$u_{G} = \infty$
(3)													$t_{A} = 45$
(1)
(2)														$u_{B} = 60$	$u_{C} = \infty$	$u_{D} = \infty$	$u_{E} = \infty$	$u_{F} = \infty$	$u_{G} = \infty$
(3)														$t_{B} = 60$
(1)				$t_{3} = 100$	$t_{5} = 111$
(2)															$u_{C} = 180$	$u_{D} = \infty$	$u_{E} = \infty$	$u_{F} = 202$	$u_{G} = \infty$
(3)															$t_{C} = 180$
(1)						$t_{6} = 240$	$t_{7} = 220$	$t_{8} = 229$
(2)																$u_{D} = 250$	$u_{E} = 271$	$u_{F} = 202$	$u_{G} = \infty$
(3)																		$t_{F} = 202$
(1)												$t_{12} = 312$
(2)																$u_{D} = 250$	$u_{E} = 271$		$u_{G} = 542$
(3)																$t_{D} = 250$
(1)									$t_{9} = 390$		$t_{11} = 260$
(2)																	$u_{E} = 271$		$u_{G} = 295$
(3)																	$t_{E} = 271$
(1)										$t_{10} = 293$
(2)																			$u_{G} = 295$
(3)																			$t_{G} = 295$

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Levner, E.; Tsadikovich, D. Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes. Algorithms 2024, 17, 504. https://doi.org/10.3390/a17110504

AMA Style

Levner E, Tsadikovich D. Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes. Algorithms. 2024; 17(11):504. https://doi.org/10.3390/a17110504

Chicago/Turabian Style

Levner, Eugene, and Dmitry Tsadikovich. 2024. "Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes" Algorithms 17, no. 11: 504. https://doi.org/10.3390/a17110504

APA Style

Levner, E., & Tsadikovich, D. (2024). Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes. Algorithms, 17(11), 504. https://doi.org/10.3390/a17110504

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Fast Algorithm for Cyber-Attack Estimation and Attack Path Extraction Using Attack Graphs with AND/OR Nodes

Abstract

1. Introduction

2. Literature Review

3. The Algorithm for Extracting Attack Paths

4. Numerical Examples and Their Analysis

5. A Case Study

6. Cyber-Defense and Countermeasures Against Attack Paths

7. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

Appendix A

Appendix B

Appendix C. The Proof of Claim 1

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI