Algorithms of searching for admissible solutions to construct the matrix of the game in the problem of choice of protection objects under the restrictions on resources

Authors: Koshman A.A.
Published in issue: #4(33)/2019
DOI: 10.18698/2541-8009-2019-4-471
Category: Informatics, Computer Engineering and Control | Chapter: Methods and Systems of Information Protection, Information Security
Keywords: information protection, game theory, Boolean programming, game matrix, optimal strategy, object of protection, resource restriction, incomplete enumeration, decision tree
Published: 07.05.2019

The task of selecting the objects of protection under the restrictions on resources was considered. A task is a zero-sum game, where each player solves his own Boolean programming problem under the fixed solution of another player. Two algorithms for finding feasible solutions for the defender and the attacker with the maximum number of points in the game formulation of the problem are described. These algorithms can be used to build a game matrix. Algorithms are based on incomplete enumeration of solutions, starting with single and zero solutions. The performance of the algorithms was tested, it was proved that they allow to get the same result. An example of solving the problem is given.

References

[1] Chen L., Leneutre J. A game theoretical framework on intrusion detection in heterogeneous networks. IEEE Trans. Inf. Forensics Security, 2009, vol. 4, no. 2, pp. 165–178. DOI: 10.1109/TIFS.2009.2019154 URL: https://ieeexplore.ieee.org/document/4815406

[2] Bykov A.Yu., Altukhov N.O., Sosenko A.S. Problem of information security product choice in automated systems based on antagonistic play model. Inzhenernyy vestnik [Engineering Bulletin], 2014, no. 4. URL: http://engbul.bmstu.ru/doc/708106.html (in Russ.).

[3] 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: nauchnoe izdanie [Science and Education: Scientific Publication], 2015, no. 9. URL: https://technomagelpub.elpub.ru/jour/article/view/186 (in Russ.).

[4] Bykov A.Yu., Panfilov F.A., Khovrina A.V. The algorithm to select security classes for objects in distributed information systems and place data in the objects through reducing the optimization problem to the theory of games with non-conflicting interests. Nauka i obrazovanie: nauchnoe izdanie [Science and Education: Scientific Publication], 2016, no. 1. URL: http://engineering-science.ru/en/doc/830972.html (in Russ.).

[5] Bykov A.Yu., Krygin I.A., Mullin A.R. Algorithms of the protection system between assets of a mobile device on the basis of zero-sum game and equal security principle. Vestn. Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2018, no. 2, pp. 48–68. DOI: 10.18698/0236-3933-2018-2-48-68 URL: http://vestnikprib.ru/catalog/icec/sysan/1096.html (in Russ.).

[6] Basarab M.A. Teoriya optimizatsii i issledovanie operatsiy [Optimization theory and operation research]. Moscow, Bauman MSTU Publ., 2012 (in Russ.).

[7] Basarab M.A., Vel’ts S.V. Metody optimizatsii i issledovanie operatsiy v oblasti informatsionnoy bezopasnosti [Optimization methods and operation research in field of information security]. Moscow, Bauman MSTU Publ., 2015 (in Russ.).