Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397

Issue N3 2021 year

DOI: 10.17587/prin.12.150-156
A Model of Secure Functioning of Computer Systems
A. V. Galatenko, agalatenko@hse.ru, HSE University, Moscow, 101000, Russian Federation, V. A. Kuzovikhina, pletnyova_va@mail.ru, New school, Moscow, 119192, Russian Federation
Corresponding author: Kuzovikhina Vesta A., Teacher, New school, Moscow, 119192, Russian Federation, E-mail: pletnyova_va@mail.ru
Received on December 29, 2020
Accepted on January 15, 2021

We propose an automata model of computer system security. A system is represented by a finite automaton with states partitioned into two subsets: "secure" and "insecure". System functioning is secure if the number of consecutive insecure states is not greater than some nonnegative integer k. This definition allows one to formally reflect responsiveness to security breaches. The number of all input sequences that preserve security for the given value of k is referred to as a k-secure language. We prove that if a language is k-secure for some natural and automaton V, then it is also k-secure for any 0 < k < k and some automaton V = V (k). Reduction of the value of k is performed at the cost of amplification of the number of states. On the other hand, for any non-negative integer k there exists a k-secure language that is not k"-secure for any natural k" > k. The problem of reconstruction of a k-secure language using a conditional experiment is split into two subcases. If the cardinality of an input alphabet is bound by some constant, then the order of Shannon function of experiment complexity is the same for al k; otherwise there emerges a lower bound of the order nk.

Keywords: formal security model, finite automata, regular languages, multiple conditional experiments
pp. 150–156
For citation:
Galatenko A. V., Kuzovikhina V. A. A Model of Secure Functioning of Computer Systems, Programmnaya Ingeneria, 2021, vol. 12, no. 3, pp. 150—156.
This work was supported by the Russian Foundation for Basic Research, project no. 18-07-01055.