Algorithms for Solving a Discrete-Continuous Game Based on Combination of the Approximate and Exact Methods in the Context of Information Protection Tasks

Abstract

The paper presents a model of a discrete-continuous zero-sum game between two players, i.e. defender and attacker, in relation to the problem of selecting protection means by the defender, and attack options by the attacker. The defender solves a Boolean programming problem to select the defense combinations, and the attacker solves a linear programming problem to find the attack combinations. It is shown how to reduce such problems to a matrix game. To find a saddle point in the mixed strategies, the exact algorithm could be introduced on the basis of solutions to the direct and dual linear programming problems. However, the problem in this form could have large dimension and unacceptable solution time. To reduce the problem dimension, the paper proposes to use at the preliminary stage an approximate algorithm based on the Brown --- Robinson method, but without explicitly constructing the game matrix making it possible to significantly reduce dimension of the problems solved by the exact algorithm. Based on the game reduced matrix obtained by the approximate algorithm, it is proposed to search for a saddle point in the pure or mixed strategies, as well as the minimax and maximin, if the principle of guaranteed results in decision-making is used. An example of solving the problem is provided, as well as results of testing the algorithms on initial data obtained using a pseudorandom number generator

Please cite this article in English as:

Bykov A.Yu., Sysoev V.V. Algorithms for solving a discrete-continuous game based on combination of the approximate and exact methods in the context of information protection tasks. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering, 2024, no. 2 (147), pp. 102--124 (in Russ.). EDN: QYMMDE

References

[1] Min H., Li C.Y. Construction of information security risk assessment model based on static game. ISCIPT, 2021, pp. 647--650. DOI: https://doi.ieeecomputersociety.org/10.1109/ISCIPT53667.2021.00137

[2] Jain A., Tripathi K., Jatain A., et al. A game theory based attacker defender model for IDS in cloud security. INDIACom, 2022, pp. 190--194. DOI: https://doi.org/10.23919/INDIACom54597.2022.9763191

[3] Zhang H., Zhang X., Sun P., et al. Traceability method of network attack based on evolutionary game. NaNA, 2022, pp. 232--236. DOI: https://doi.ieeecomputersociety.org/10.1109/NaNA56854.2022.00046

[4] Sinha A. AI and security: a game perspective. COMSNETS, 2022. DOI: http://doi.org/10.1109/COMSNETS53615.2022.9668430

[5] Guo Y., Zou K., Yang M., et al. Tripartite evolutionary game of multiparty collaborative supervision of personal information security in app: empirical evidence from China. IEEE Access, 2022, vol. 10, pp. 85429--85441. DOI: https://doi.org/10.1109/ACCESS.2022.3198705

[6] Zhang X. Access control mechanism based on game theory in the internet of things environment. IEEE ICCC, 2022. DOI: https://doi.org/10.1109/ICCC56324.2022.10065968

[7] Bian Y., Lin H., Song Y. Game model of attack and defense for underwater wireless sensor networks. IEEE ITAIC, 2022. DOI: http://doi.org/10.1109/ITAIC54216.2022.9836681

[8] Miaji M., Miaji Y. exploiting game theory strategy and artificial intelligent to analyze social networks: a comprehensive survey. SMAP, 2022. DOI: http://doi.org/10.1109/SMAP56125.2022.9941773

[9] Zhang Y., Liu F., Chen H. Optimal strategy selection for attack graph games using deep reinforcement learning. 2022 IEEE HPCC/DSS/SmartCity/DependSys, 2022. DOI: https://doi.org/10.1109/HPCC-DSS-SmartCity-DependSys57074.2022.00135

[10] Xing W., Zhao X., Basar T., et al. Security investment in cyber-physical systems: stochastic games with asymmetric information and resource-constrained players. IEEE Trans. Automat. Contr., 2022, vol. 67, no. 10, pp. 5384--5391. DOI: http://doi.org/10.1109/TAC.2021.3116093

[11] Qurashi J.M., Ikram M.J., Jambi K., et al. Autonomous vehicles: security challenges and game theory-based countermeasures. ICAISC, 2023. DOI: http://doi.org/10.1109/ICAISC56366.2023.10085301

[12] Yao Y.D., Li X., Cui Y.P., et al. Game theory and coverage optimization based multihop routing protocol for network lifetime in wireless sensor networks. IEEE Sens. J., 2022, vol. 22, no. 13, pp. 13739--13752. DOI: http://doi.org/10.1109/JSEN.2022.3178441

[13] Basarab M.A., Troitskii I.I., Onufrieva E.V. [The investigation of the operation of SIEM-systems using various correlators for binary sequences (1, --1) under condition, that random values take values with same probability]. Sb. tr. XI Mezhdunar. nauch.-tekh. konf. "Bezopasnye informatsionnye tekhnologii" [Secure Information Technologies. Proc. 11th Int. Sc.-Tech. Conf.]. Moscow, BMSTU Publ., 2021, pp. 32--36 (in Russ.).

[14] Klyucharev P.G. Cellular automata and their generalizations in cryptography. Part 1. Voprosy kiberbezopasnosti [Cybersecurity Issues], 2021, no. 6, pp. 90--101 (in Russ.).

[15] Klyucharev P.G. Cellular automata and their generalizations in cryptography. Part 2. Voprosy kiberbezopasnosti [Cybersecurity Issues], 2022, no. 1, pp. 37--48 (in Russ.).

[16] Zelenetskiy A.S., Klyucharev P.G. Affine annihilator finding algorithm for Boolean function. Matematika i matematicheskoe modelirovanie [Mathematics and Mathematical Modeling], 2021, no. 1, pp. 13--26 (in Russ.). DOI: http://doi.org/10.24108/mathm.0121.0000255

[17] Bykov A.Yu., Grishunin M.V., Krygin I.A. The game problem of selection of assets to protect and research of saddle point search algorithm based on Brown --- Robinson method modification. Voprosy kiberbezopasnosti [Cybersecurity Issues], 2019, no. 2, pp. 2--12 (in Russ.).

[18] Bykov A.Yu., Krygin I.A., Grishunin M.V., et al. On one saddle point search algorithm for continuous linear games as applied to information security problems. Herald of the Bauman Moscow State Technical University, Series Natural Sciences, 2020, no. 4 (133), pp. 58--74 (in Russ.). DOI: http://doi.org/10.18698/0236-3933-2020-4-58-74

[19] Bykov A.Yu., Grishunin M.V., Fedorov E.G., et al. Algorithm for determining saddle point in game theory problem of choosing software for information security on computer network servers. CEUR Workshop Proceedings. Moscow, 2021, с. 22--32.

[20] Strekalovskiy A.S., Orlov A.V. Bimatrichnye igry i bilineynoe programmirovanie [Bimatrix games and bilinear programming]. Moscow, FIZMATLIT Publ., 2007.