## 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, [PERSON]'s and [PERSON]'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 [PERSON] et al. [34] and [PERSON] 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.