Об одном алгоритме поиска седловой точки для непрерывных линейных игр применительно к задачам защиты информации

Приведена игровая постановка задачи двух игроков: защитник определяет уровни защищенности объектов, а нападающий --- объекты для атаки, каждый распределяет свои ресурсы между объектами. Показателем качества является оценка возможного ущерба защитника. Задача --- непрерывная игра с нулевой суммой при ограничениях на ресурсы игроков --- сформулирована так, что каждый игрок должен решить свою задачу линейного программирования при фиксированном решении другого игрока. Разработан алгоритм поиска седловой точки, являющийся приближенным и базирующийся на сведении непрерывной задачи к дискретной или матричной игре большой размерности, так как оптимальные решения находятся в вершинах или на гранях симплексов, определяющих множества допустимых решений игроков, а число вершин или граней симплексов конечно. В предложенном алгоритме последовательно решаются оптимизационные задачи игроков при накопленном усредненном решении другого игрока, по сути, использованы идеи метода Брауна --- Робинсона. Приведен пример решения задачи. Исследованы зависимости числа шагов алгоритма от относительной погрешности показателя качества и от размерности задачи (числа защищаемых объектов) при заданной относительной погрешности. Исходные данные сформированы с помощью генераторов псевдослучайных чисел

Литература

[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] Быков А.Ю., Шматова Е.С. Алгоритмы распределения ресурсов для защиты информации между объектами информационной системы на основе игровой модели и принципа равной защищенности объектов. Наука и образование: научное издание МГТУ им. Н.Э. Баумана, 2015, № 9, с. 160--187. URL: 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] Быков А.Ю., Гришунин М.В., Крыгин И.А. Игровая задача выбора защищаемых объектов и исследование алгоритма поиска седловой точки на основе модификации метода Брауна --- Робинсона. Вопросы кибербезопасности, 2019, № 2, с. 2--12. DOI: https://doi.org/10.21681/2311-3456-2019-2-2-12

[10] Ключарёв П.Г. О статистическом тестировании блочных шифров. Математика и математическое моделирование, 2018, № 5, с. 35--57. DOI: https://doi.org/10.24108/mathm.0518.0000132

[11] Ключарёв П.Г. Детерминированные методы построения графов Рамануджана, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах. Прикладная дискретная математика, 2018, № 42, с. 76--93. 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] Гольштейн Е.Г. Обобщенный седловой вариант метода уровней. Журнал вычисл. матем. и матем. физики, 2001, т. 41, № 8, с. 1139--1147.

[14] Бэр К., Гольштейн Е.Г., Соколов Н.А. Метод отыскания седловой точки функции, область определения которой содержится в многограннике. Экономика и матем. методы, 2001, т. 37, № 3, с. 97--105.

[15] Стрекаловский А.С., Орлов А.В. Биматричные игры и билинейное программирование. М., ФИЗМАТЛИТ, 2007.