## 2 Literature Review
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 [PERSON] [20; 21]. It was based on unfolding cyclic graphsinto 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, [PERSON] and [PERSON] [35], [PERSON] and [PERSON] [36], [PERSON] et al. [37; 38], and [PERSON] [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, [PERSON] [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, [PERSON] et al. [41] revisited and improved [PERSON]'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 [43; 44; 42]. 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].