On discrete automaton models of attacks in computer networks

D. E. Gorbatenko ; S. E. Kochemazov ; A. A. Semenov

Prikladnaya Diskretnaya Matematika. Supplement, no. 9 (2016), pp. 80-83.

Résumé

We propose a new model for describing the development of attacks in computer networks. The basis of the model is a synchronous discrete automaton defined by the network graph, where vertices are hosts. We consider transitions between the states of this automaton, that take place in discrete time moments. At each time moment, we associate with the graph vertices Boolean vectors referred to as host states. At each consecutive time moment, the host states are synchronously computed according to some fixed pre-defined rules. In more detail, let $G=(V,A)$ be a graph interpreting the computer network. Let $Q=\{q_1,\dots,q_l\}$ be the set of possible host vulnerabilities. The process of development of an attack in the network is the process of exploiting the available vulnerabilities by an adversary. At the next time moment, new available vulnerabilities can appear as a result of such exploitation. Therefore, we can consider the network as discrete automaton, that functions in time moments $t\in\{0,1,\dots\}$. We refer to the moment $t=0$ as initial moment. For each $t$, let us associate with each host $v\in V$ a Boolean vector $\alpha^v(t)=\left(\alpha_1^v,\dots,\alpha_l^v,\alpha^v_{l+1},\dots,\alpha^v_r(t)\right)$, $r\geq l$, called the state of the host $v$ at time moment $t$. The first $l$ coordinates of this vector form the so-called vector of vulnerabilities: we assume that $\alpha_j^v=1$ iff host $v$ has the vulnerability $q_j$, $j\in\{1,\dots,l\}$. This vector of vulnerabilities is fixed and does not change. The coordinates of $\alpha^v(t)$ with indices $l+1,\dots,r$ contain the information that can change for time. In particular, the corresponding vector values reflect some access permissions the considered host has on other hosts. The coordinates $l+1,\dots,r$ of $\alpha^v(t)$ form the vector of possibilities of host $v$ at moment $t$. If we assume that we know the states of all hosts at initial time moment, we can consider the transitions of the network to the consecutive states by changing the vectors of possibilities of the hosts according to pre-defined rules. As such rules, we used the pairs of the kind (pre-condition, post-condition), by means of which in the widely known work by M. Danforth the elementary attacks are defined. In the context of the proposed model, we analyzed several types of attacks in computer networks. To obtain superuser permissions on a desired host, we considered combinatorial problems of finding best distributions of adversary hosts in the attacked networks. In this process, it is possible to take into account various additional constraints. Also, we considered the combinatorial problem referred to in the work by M. Danforth as the problem of distributing patches. All considered problems were reduced to Boolean satisfiability problem and solved using state-of-the-art SAT solvers. In our experiments, we considered random graphs with several hundred vertices.

Détail

Keywords: discrete automaton, attack graph, Boolean satisfiability, SAT.

Bibliographie

[1] Devyanin P. N., Modeli bezopasnosti kompyuternykh sistem, Ucheb. posobie dlya vuzov, Izdatelskii tsentr “Akademiya”, M., 2005

[2] Jha S., Sheyner O., Wing J., “Two formal analysis of attack graphs”, Proc. 15th IEEE Workshop on Computer Security Foundations (CSFW'02), 2002, 49–63 | DOI

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

[4] Kolegov D. N., Problemy sinteza i analiza grafov atak, , 2009 http://www.securitylab.ru/contest/299868.php

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

[6] Kauffman S., “Metabolic stability and epigenesis in randomly constructed genetic nets”, J. Theoretical Biology, 22 (1969), 437–467 | DOI

[7] Kochemazov S., Semenov A., “Using synchronous Boolean networks to model several phenomena of collective behavior”, PLoS ONE, 9:12 (2014), e115156, 28 pp. | DOI

[8] Barabasi A-L., Albert R., “Emergence of scaling in random networks”, Science, 286 (1999), 509–512 | DOI | MR | Zbl