Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2016, Issue 9, Pages 80–83
DOI: https://doi.org/10.17223/2226308X/9/31
(Mi pdma270)
 

This article is cited in 1 scientific paper (total in 1 paper)

Mathematical Foundations of Computer Security

On discrete automaton models of attacks in computer networks

D. E. Gorbatenkoa, S. E. Kochemazovb, A. A. Semenovb

a Institute of Mathematics, Economics and Informatics of Irkutsk State University, Irkutsk
b Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk
Full-text PDF (565 kB) Citations (1)
References:
Abstract: 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.
Keywords: discrete automaton, attack graph, Boolean satisfiability, SAT.
Funding agency Grant number
Russian Foundation for Basic Research 14-07-00403а
15-07-07891а
Document Type: Article
UDC: 519.7
Language: Russian
Citation: D. E. Gorbatenko, S. E. Kochemazov, A. A. Semenov, “On discrete automaton models of attacks in computer networks”, Prikl. Diskr. Mat. Suppl., 2016, no. 9, 80–83
Citation in format AMSBIB
\Bibitem{GorKocSem16}
\by D.~E.~Gorbatenko, S.~E.~Kochemazov, A.~A.~Semenov
\paper On discrete automaton models of attacks in computer networks
\jour Prikl. Diskr. Mat. Suppl.
\yr 2016
\issue 9
\pages 80--83
\mathnet{http://mi.mathnet.ru/pdma270}
\crossref{https://doi.org/10.17223/2226308X/9/31}
Linking options:
  • https://www.mathnet.ru/eng/pdma270
  • https://www.mathnet.ru/eng/pdma/y2016/i9/p80
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024