Geodesic
An effective algorithm for building a~set of the shortest attacks within the context of one model of attack development in computer networks
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 90-95.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: attacks in computer networks, attack graphs, discrete dynamical systems. 
@article{PDMA_2018_11_a27,
     author = {D. E. Gorbatenko and A. A. Semenov},
     title = {An effective algorithm for building a~set of the shortest attacks within the context of one model of attack development in computer networks},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {90--95},
     publisher = {mathdoc},
     number = {11},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2018_11_a27/}
}
TY  - JOUR
AU  - D. E. Gorbatenko
AU  - A. A. Semenov
TI  - An effective algorithm for building a~set of the shortest attacks within the context of one model of attack development in computer networks
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2018
SP  - 90
EP  - 95
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2018_11_a27/
LA  - ru
ID  - PDMA_2018_11_a27
ER  - 
%0 Journal Article
%A D. E. Gorbatenko
%A A. A. Semenov
%T An effective algorithm for building a~set of the shortest attacks within the context of one model of attack development in computer networks
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2018
%P 90-95
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2018_11_a27/
%G ru
%F PDMA_2018_11_a27
D. E. Gorbatenko; A. A. Semenov. An effective algorithm for building a~set of the shortest attacks within the context of one model of attack development in computer networks. Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 90-95. http://geodesic.mathdoc.fr/item/PDMA_2018_11_a27/

[1] Sheyner O., Haines J.W., Jha S., et al., “Automated generation and analysis of attack Graphs”, Proc. 2002 IEEE Symp. Security and Privacy, 2002, 273–284 | DOI

[2] Amman P., Wijesekera D., Kaushik S., “Scalable, graph-based network vulnerability analysis”, CCS 2002, Proc. 9th ACM Conf. Computer and Communications Security, 2002, 217–224

[3] Ou X., Wayne B., Miles M., “A scalable approach to attack graph generation”, Proc. 13th ACM Conf. Computer and Communications Security, 2006, 336–345

[4] Ou X., Govindavajhala S., Appel A., “MulVAL: A logic-based network security analyzer”, SSYM'05, Proc. 14th Conf. USENIX Security Symp., v. 14, 2005, 113–128

[5] Ingols K., Lippmann R., Piwowarski K., “Practical attack graph generation for network defense”, ACSAC'06, Proc. 22nd Ann. Computer Security Appl. Conf., 2006, 121–130

[6] Danforth M., Models for Threat Assessment in Networks, PhD Thesis, University of California-Davis, 2006

[7] Devyanin P. N., Modeli bezopasnosti kompyuternykh sistem, Academia, M., 2005

[8] Gorbatenko D. E., Kochemazov S. E., Semënov A. A., “O diskretno-avtomatnykh modelyakh atak v kompyuternykh setyakh”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 80–83