Алгоритмы решения дискретно-непрерывной игры применительно к задачам информационной безопасности на основе комбинации приближенного и точного методов

Аннотация

Приведена модель дискретно-непрерывной игры с нулевой суммой двух игроков, защитника и нападающего, применительно к задаче выбора защитником средств защиты, а нападающим --- вариантов проведения атак. Для выбора комбинаций средств защиты и проведения атак защитник решает задачу булевого программирования, а нападающий --- задачу линейного программирования. Показано, как свести такую задачу к матричной игре. Для поиска седловой точки в смешанных стратегиях можно использовать точный алгоритм, основанный на решении прямой и двойственной задач линейного программирования, но в таком виде задача может иметь большую размерность и недопустимое время решения. Для уменьшения размерности задачи предложено на предварительном этапе использовать приближенный алгоритм на основе метода Брауна --- Робинсона, но без явного построения матрицы игры, что позволило существенно уменьшить размерность задач, решаемых с помощью точного алгоритма. По сокращенной матрице игры, полученной приближенным алгоритмом, предложено искать седловую точку в чистых или смешанных стратегиях, а также MinMax и MaxMin, если использовать принцип гарантированного результата при принятии решений. Приведены пример решения задачи и результаты тестирования алгоритмов на исходных данных, полученных с помощью генератора псевдослучайных чисел

Просьба ссылаться на эту статью следующим образом:

Быков А.Ю., Сысоев В.В. Алгоритмы решения дискретно-непрерывной игры применительно к задачам информационной безопасности на основе комбинации приближенного и точного методов. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2024, № 2 (147), с. 102--124. EDN: QYMMDE

Литература

[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] Басараб М.А., Троицкий И.И., Онуфриева Е.В. Исследование функционирования SIEM-систем с помощью различных корреляторов для бинарных последовательностей вида (1, --1) при условии, что случайные величины принимают свои значения с одинаковыми вероятностями. Сб. тр. XI Междунар. науч.-техн. конф. "Безопасные информационные технологии". М., Изд-во МГТУ им. Н.Э. Баумана, 2021, с. 32--36.

[14] Ключарёв П.Г. Клеточные автоматы и их обобщения в задачах криптографии. Часть 1. Вопросы кибербезопасности, 2021, № 6, с. 90--101.

[15] Ключарёв П.Г. Клеточные автоматы и их обобщения в задачах криптографии. Часть 2. Вопросы кибербезопасности, 2022, № 1, с. 37--48.

[16] Зеленецкий А.С., Ключарев П.Г. Алгоритм поиска аффинных аннигиляторов булевой функции. Математика и математическое моделирование, 2021, № 1, с. 13--26. DOI: http://doi.org/10.24108/mathm.0121.0000255

[17] Быков А.Ю., Гришунин М.В., Крыгин И.А. Игровая задача выбора защищаемых объектов и исследование алгоритма поиска седловой точки на основе модификации метода Брауна --- Робинсона. Вопросы кибербезопасности, 2019, № 2, с. 2--12.

[18] Быков А.Ю., Крыгин И.А., Гришунин М.В. и др. Об одном алгоритме поиска седловой точки для непрерывных линейных игр применительно к задачам защиты информации. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2020, № 4 (133), с. 58--74. 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] Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М., ФИЗМАТЛИТ, 2007.