SCIENCE & EDUCATION

Article file: SE-BMSTU...o107.pdf (1763.56Kb)

1 Bauman Moscow State Technical University, Moscow, Russia

Modern methods to solve the practical problems related to the information security system design in multipurpose distributed systems often use optimization models. The paper formulates a problem statement of bilinear Boolean programming with the quality score that determines the level of the system security to select classes of protected objects in distributed systems and allocate databases in these objects. Restrictions specify the maximum cost of protection and the recommended amount of data stored in the object. To solve this problem, using the algorithms of discrete programming is possible, but the accurate algorithms, generally, are exponentially time-consuming.
To find a solution the paper proposes to interpret this problem as a problem of two players with non-conflicting interests. The first player is responsible for the assignment of security classes for the system objects, and the second player is responsible for the distribution of databases between the objects. To find solutions the use of a Nash equilibrium criterion is offered. To find the equilibrium solution is developed an algorithm and are proved its convergence, and the fact that it really allows us to obtain the Nash equilibrium position. Using the problem-solving approach related to reducing the original optimization problem to a two-player game with non-conflicting interests allowed a decreasing dimension of the original problem, because at each step of the algorithm is solved the problem of discrete optimization of a smaller dimension than the original problem of Boolean programming.
The paper presents results of solving the problem, as well as research results on the time complexity of represented algorithms. It conducts a comparative analysis of the two approaches: an approach based on solving a discrete optimization problem and an approach based on reducing the problem to a two-player game with non-conflicting interests. An approach based on reducing the initial problem to a game, allowed us to decrease solution time significantly, by 2-3 orders, while, in general, the reached value was the same as in the original problem of Boolean programming.

1. Germeier Yu.B. Igry s neprotivopolozhnymi interesami [ Games with nonconflicting interests ]. Moscow, Nauka Publ., 1976. 327 p. (in Russian).
2. Rastogi V., Yan Chen, Xuxian Jiang. Catch Me If You Can: Evaluating Android Anti-Malware Against Transformation Attacks. IEEE Transactions on Information Forensics and Security , 2014, vol. 9, iss. 1, pp. 99-108. DOI:10.1109/TIFS.2013.2290431
3. Dunning L.A., Kresman R. Privacy Preserving Data Sharing With Anonymous ID Assignment. IEEE Transactions on Information Forensics and Security , 2013, vol. 8, iss. 2, pp. 402-413 . DOI: 10.1109/TIFS.2012.2235831
4. Sung, Y.E., Xin Sun, Rao S.G., Xie G.G., Maltz D.A. Towards Systematic Design of Enterprise Networks. IEEE/ACM Transactions on Networking , 2011, vol. 19, iss. 3, pp. 695-708. DOI: 10.1109/TNET.2010.2089640
5. Bregni S., Giacomazzi P., Poli A. Cost-Performance Optimization of SSL-Based Secure Distributed Infrastructures. IEEE Latin America Transactions , 2011, vol. 9, iss. 4, pp. 550-556. DOI: 10.1109/TLA.2011.5993742
6. Quansheng Guan, Yu F.R., Shengming Jiang, Leung V.C.M. Joint Topology Control and Authentication Design in Mobile Ad Hoc Networks With Cooperative Communications. IEEE Transactions on Vehicular Technology , 2012, vol. 61, iss. 6, pp. 2674-2685. DOI: 10.1109/TVT.2012.2196061
7. Zhiyong Shan, Xin Wang. Growing Grapes in Your Computer to Defend Against Malware. IEEE Transactions on Information Forensics and Security , 2014, vol. 9, iss. 2, pp. 196-207. DOI: 10.1109/TIFS.2013.2291066
8. Bykov A.Yu., Altukhov N.O., Sosenko A.S. The problem of choosing software / hardware means in automated information systems based on the model of an antagonistic game. Inzhenernyi vestnik MGTU im. N.E. Baumana = Engineering Herald of the Bauman MSTU, 2014, no. 4, pp. 525-542. Available at: http://engbul.bmstu.ru/doc/708106.html, accessed 12.01.2016. (in Russian).
9. Bykov A.Yu., Shmatova E.S. The Algorithms of Resource Distribution for Information Security Between Objects of an Information System Based on the Game Model and Principle of Equal Security of Objects. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2015, no. 9, pp. 160-187. DOI:10.7463/0915.0812283( in Russian ).
10. Strekalovskii A.S., Orlov A.V. Bimatrichnye igry i bilineinoe programmirovanie [ Bimatrix games and bilinear programming ]. Moscow, Fizmatlit Publ., 2007. 224 p. (in Russian).
11. Aleeva S.R., Yakubovich Y.O. Equilibrium programming and its application for a search of Nash equilibrium. Vestnik Chelyabinskogo gosudarstvennogo universiteta = Herald of Chelyabinsk State University , 2013, no. 28 (319), pp. 6-20. (in Russian).
12. Guidance document. The automated control system. Protection against unauthorized access to information. Automated systems classification and requirements for protection of information . Sbornik rukovodyashchikh dokumentov po zashchite informatsii ot NSD [ Collection of guidelines to protect information from unauthorized access ]. Moscow , Publ . of FSTEC of Russia, 1998, pp . 23-52. ( in Russian ).
13. Ovchinnikov A.I., Zhuravlev A.M., Medvedev N.V., Bykov A.Yu. Mathematical Model of Optimal Selection of Aids of Protection Against Threats for Safety of Enterprise Computer Network. Vestnik MGTU im. N.E. Baumana . Ser. Priborostroenie = Herald of the Bauman Moscow State Technical University. Ser . Instrument Engineering , 2007, no . 3 , pp . 115-121. ( in Russian ).
14. Ovchinnikov A.I., Medvedev N.V., Bykov A.Yu. Application of Recession Vector Method to Solving Problem on Search of Variants of Protection against Security Threats of Enterprise Computer Network. Vestnik MGTU im. N.E. Baumana . Ser. Priborostroenie = Herald of the Bauman Moscow State Technical University. Ser . Instrument Engineering , 2008 , no. 2 , pp . 73-82. ( in Russian ).
15. Bykov A.Yu., Panfilov F.A., Shmyrev D.V. A Problem on Choosing Protection in Automated Systems Taking into Account the Classes of Immunity against Unauthorized Data Access. Inzhenernyy zhurnal: nauka i innovatsii = Engineering Journal: Science and Innovation , 2012, no. 1. DOI: 10.18698/2308-6033-2012-1-85 (in Russian).
16. Bykov A.Yu., Gurov A.V. A Problem on Choosing Protection against Attacks in Automated Systems with Fuzzy Parameters of Goal Function. Inzhenernyy zhurnal: nauka i innovatsii = Engineering Journal: Science and Innovation , 2012, no. 1. DOI: 10.18698/2308-6033-2012-1-86 (in Russian).
17. Klyucharev P.G. Computational Complexity of Some Problems on Generalized Cellular Automations. Bezopasnost Informatsionnykh Tekhnology, 2012, no. 1, pp. 30-32. (in Russian).
18. Klyucharev P.G. NP-hard of step backward problem in generalized cellular automaton. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2012, no. 1. Available at: http://technomag.bmstu.ru/doc/312834.html, accessed 12.01.2016. (in Russian).
19. Klyucharev P.G. On period of generalized cellular automation. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2012, no. 2. Available at: http://technomag.bmstu.ru/doc/340943.html, accessed 12.01.2016. (in Russian).
20. Klyucharev P.G. Performance and effectiveness of hardware realization of stream ciphers based on generalized cellular automata. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2013, no. 10, pp. 299-314. DOI: 1013.0624722 (in Russian).
21. Klyucharev P.G. The FPGA realization of the general cellular automata based cryptographic hash functions: Performance and effectiveness. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2014, no. 1, pp. 214-223. DOI:10.7463/0114.0675812 (in Russian).
22. Klyucharev P.G. On Collision Resistance of Generalized Cellular Automata. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2014, no. 9, pp. 2314-223. DOI:10.7463/0914.0727086 (in Russian).