On one Saddle Point Search Algorithm for Continuous Linear Games as Applied to Information Security Problems

The paper introduces a game formulation of the problem of two players: the defender determines the security levels of objects, and the attacker determines the objects for attack. Each of them distributes his resources between the objects. The assessment of a possible damage to the defender serves as an indicator of quality. The problem of a continuous zero-sum game under constraints on the resources of the players is formulated so that each player must solve his own linear programming problem with a fixed solution of the other player. The purpose of this research was to develop an algorithm for finding a saddle point. The algorithm is approximate and based on reducing a continuous problem to discrete or matrix games of high dimension, since the optimal solutions are located at the vertices or on the faces of the simplices which determine the sets of players' admissible solutions, and the number of vertices or faces of the simplices is finite. In the proposed algorithm, the optimization problems of the players are sequentially solved with the accumulated averaged solution of the other player, in fact, the ideas of the Brown --- Robinson method are used. An example of solving the problem is also given. The paper studies the dependences of the number of algorithm steps on the relative error of the quality indicator and on the dimension of the problem, i.e., the number of protected objects, for a given relative error. The initial data are generated using pseudo-random number generators

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: https://doi.org/10.1109/TIFS.2009.2019154

[2] 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 MGTU im. N.E. Baumana [Science and Education: Scientific Publication], 2015, no. 9, pp. 160--187 (in Russ.). Available at: http://engineering-science.ru/doc/812283.html

[3] Zhang H., Jiang Lv., Huang Sh., et al. Attack-defense differential game model for network defense strategy selection. IEEE Access, 2019, vol. 7, pp. 50618--50629. DOI: https://doi.org/10.1109/ACCESS.2018.2880214

[4] Wu H., Wang W. A game theory based collaborative security detection method for internet of things systems. IEEE Trans. Inf. Forensics Security, 2018, vol. 13, no. 6, pp. 1432--1445. DOI: https://doi.org/10.1109/TIFS.2018.2790382

[5] Yang L., Li P., Zhang Y., et al. Effective repair strategy against advanced persistent threat: a differential game approach. IEEE Trans. Inf. Forensics Security, 2019, vol. 14, no. 7, pp. 1713--1728. DOI: https://doi.org/10.1109/TIFS.2018.2885251

[6] Sun Z., Liu Y., Wang J., et al. Non-cooperative game of throughput and hash length for adaptive merkle tree in mobile wireless networks. IEEE Trans. Veh. Technol., 2019, vol. 68, no. 5, pp. 4625--4650. DOI: https://doi.org/10.1109/TVT.2019.2899647

[7] Moura J., Hutchison D. Game theory for multi-access edge computing: survey, use cases, and future trends. IEEE Commun. Surveys Tuts., 2019, vol. 21, no. 1, pp. 260--288. DOI: https://doi.org/10.1109/COMST.2018.2863030

[8] Liu Z., Luong N., Wang W., et al. A survey on blockchain: a game theoretical perspective. IEEE Access, 2019, vol. 7, pp. 47615--47643. DOI: https://doi.org/10.1109/ACCESS.2019.2909924

[9] 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, 2019, no. 2, pp. 2--12 (in Russ.). DOI: https://doi.org/10.21681/2311-3456-2019-2-2-12

[10] Klyucharev P.G. On statistical testing of block ciphers. Matematika i matematicheskoe modelirovanie [Mathematics and Mathematical Modeling], 2018, no. 5, pp. 35--57 (in Russ.). DOI: https://doi.org/10.24108/mathm.0518.0000132

[11] Klyucharev P.G. Deterministic methods of Ramanujan graph construction for use in cryptographic algorithms based on generalized cellular automata. Prikladnaya diskretnaya matematika [Applied Discrete Mathematics], 2018, no. 42, pp. 76--93 (in Russ.).DOI: https://doi.org/10.17223/20710410/42/6

[12] Bykov A.Yu., Grishunin M.V., Krygin I.A. Saddle point search algorithm for the problem of site protection level assignment based on search of simplices’ faces on hyperplanes of equal dimension. Herald of the Bauman Moscow State Technical University. Series Instrument Engineering, 2019, no. 2, pp. 22--39.DOI: https://doi.org/10.18698/0236-3933-2019-2-22-39

[13] Gol’shteyn E.G. Generalized saddle version of the level method. Comput. Math. and Math. Phys., 2001, vol. 41, no. 8, pp. 1083--1091.

[14] Ber K., Gol’shteyn E.G., Sokolov N.A. Method for definition of function saddle point with polygon domain. Ekonomika i matem. Metody [Economics and Mathematical Methods], 2001, vol. 37, no. 3, pp. 97--105 (in Russ.).

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