## 1 Introduction
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,\pi_{V},\tau_{E})\); \(s\) and \(f\) are two selected nodes, the start and target, respectively, \(s,f\in V\). The set of nodes \(V=s\cup\texttt{AND}\cup\texttt{OR}\cup f\), and \(E\) is the set of arcs. \(\pi_{V}\) and \(\tau_{E}\) are known sets of times represented as the weights on the nodes in \(V\) and arcs in \(E\), respectively. In particular, \(\pi_{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, \(\tau_{kj},(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.