## 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\). \(\mathbb{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 1 in Appendix B. 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 [PERSON]'s shortest path method. The step-by-step process of the algorithm is visually presented in the flow chart shown in Figure 1.  
```
Initialization. Set \(t_{S}:=0\), \(u_{i}:=+\infty\) for \(\forall i\in\mathbb{O}\mathbb{R}\) and \(\mathbb{F}:=\{\mathit{node}\ \mathcal{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 \(\mathbb{P}\mathrm{Pred}(j)\), are in the set \(\mathbb{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}:=max_{k\in\mathbb{P}\mathrm{Pred}\ (j)}\Big{(}t_{k}+\tau_{kj}+\tau_{j} \Big{)}.\] (4) Modify the set \(\mathbb{F}\) as follows: \(\mathbb{F}:=\mathbb{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 \(\mathbb{F}\). Define the temporal time \(u_{i}\) of node \(i\) as follows: \[u_{i}:=\min_{k\in[\mathbb{P}\mathrm{Pred}\ (i)]\cap\mathbb{F}]}(t_{k}+\tau_{ki}+ \tau_{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 \(\mathbb{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}:=\min_{k\in[\mathbb{O}\mathbb{F}\cap\mathbb{P}\mathrm{Pred}\ (p)\setminus\mathbb{F}]}\Big{(}u_{k}+\tau_{p}+\tau_{p}\Big{)}.\] (6) Considering that either of the two cases can occur in the graph under consideration, define \(\min\big{(}u_{i},u_{p}\big{)}\) and select the OR node, \(i\) or \(p\), that has the smaller value of the temporal time, \(\min\big{(}u_{i},u_{p}\big{)}\), 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.