An effective algorithm for building a set of the shortest attacks within the context of one model of attack development in computer networks

In the paper, we present an algorithm to extract a set of shortest attacks within the context of one particular model of attack development in a computer network. This model does not make it possible to construct attack graphs with the asymptotically greatest number of vertices. However, the graphs constructed within the model do not contain loops, thus making it possible to correctly define the length of attack. The model represents the development of attacks as a discrete dynamical process. Similar to the most models of attack development, it possesses the monotonicity property. The consequence of this is a simple structure of a State Transition Graph (STG) of Discrete Dynamical System describing a development of attacks in the considered model. We propose an algorithm, which can extract from a particular STG an attack graph and a subgraph representing all the shortest attacks in a considered computer network. The algorithm for extracting the set of the shortest attacks under standard assumptions (when the number of vulnerabilities and atomic attacks are constants that do not depend on a network size) has the complexity of $\mathrm O(n^2)$ where $n$ is the number of hosts in a network.