А.А. Абраамян

Российско-Армянский (Славянский) университет, Армения

Управление информационной безопасностью с использованием игр безопасности Штакельберга

Аннотация

В данной работе рассматривается моделирование управления информационной безопасностью с применением игр Штакельберга. Результаты исследований подтверждают целесообразность использования игр безопасности Штакельберга в указанном моделировании.

Abstract

In this paper the application of Stackelberg games in modeling of information security management is described. Results of current research are stating the applicability of Stackelberg Games in information security modeling.

Ключевые слова: информационная безопасность, игры Штакельберга

Введение

Теория игр хорошо подходит для моделирования проблем безопасности при разных ситуационных атаках. В последнее время проводились исследования, осованные на играх безопасности Штакельберга, которые применимы ко многим задачам распределения ресурсов безопасности и проблем планирования [1]. Они применимы не только для моделирования физической безопасности, но и для проблем информационной безопасности, где также фигурируют лидеры и ведомые. В данном случае в роли лидера выступает специалист по информационной безопасности, а в роли ведомого - хакер. Развитие технологий информационной безопасности заставляет хакеров вкладывать дополнительные ресурсы для разработки новых инструментов и технологий своих вредоносных действий. Существует множество типов атак и, соответственно, множество типов мер безопасности для защиты против них. Следовательно, существует множество разработанных стратегий и для хакеров, и для специалистов, обеспечивающих безопасность информации.

Задача состоит в нахождении оптимальной стратегии защитника с использованием принципов игр безопасности Штакельберга. Это, в свою очередь, приводит к проблеме нахождения сильного равновесия Штакельберга, что является решением данной задачи.

В статье приводится подробное описание игр безопасности Штакельберга и байесовских игр безопасности Штакельберга в аспекте их использования в сфере информационной безопасности.

Игры Штакельберга

Игра Штакельберга это игра двух лиц (лидера и ведомого), где лидер осуществляет смешанную стратегию первым, а ведомый после наблюдения реагирует конкретной (строгой) стратегией, максимизируя свой выигриш.

В общей форме игры Штакельберга [2], смешанную стратегию лидера можно представить ввиде N-мерного вектора L . Ожидаемые выигрыши лидера и ведомого - линейные комбинации вектора L с весовыми коэффицентами, зависищями от выбора ведомого. По заданной стратегии лидера L, ведомый максимизирует ожидаемый выигрыш выбирая одну из чистых стратегий из набора F. Для каждой чистой стратегии f, выбранной ведомым, выигрыш лидера будет µ_f^TL+µ_f,0, а выигрыш ведомого ν_f^TL+ν_f,0 , где µ_f и ν_f векторы из Rⁿ, а µ_f,0, ν_f,0 принадлежат R. Обозначим через U и V матрицы выигрышей лидера и ведомого соответственно. Таким образом:

U= , V= .

Байесовские Игры Штакельберга

Байесовксое расширение игр Штакельберга дает возможность учитывать множественные типы ведомых [2]. Каждый тип имеет собственную матрицу выигрышей. Это расширение дает возможность моделирования для разных типов злоумышленников во многих аспектах.

Формально, байесовкая игра Штакельберга это игра Штакельберга между лидером и ведомым, чей тип случайно выбран из множества типов ведомых {1, 2, …, I}. Каждому типу 1≤i≤I сопоставлена вероятность появления pⁱ,а также матрицы выигрышей Uⁱ и Vⁱ для лидера и ведомого соответсвенно. Лидер применяет свою смешанную стратегию зная распределение всех возможных типов ведомых, но не зная конкретно тип ведомого который принимает участие в игре. Ведомый знает свой собственный тип i и действует оптимальным образом согласно матрице выигрышей Vⁱ.

Ожидаемые выигрыши можно определить при помощи смешанной стратегии лидера L и вектора конкретных стратегий ведомого f=(f¹, f², …,f^I) , где fⁱ – конкретная стратегия ведомого типа i. Таким образом, для ведомого типа i, ожидаемый выигрыш:

νⁱ(L,fⁱ)= .

Ожидаемый выигрыш лидера:

u(L,F)= ,

где )= ожидаемый выигрыш лидера против ведомого типа i.

Равновесие Штакельберга

Рассматривается сильное равновесие Штакельберга, как определено в [2]. В байесковских играх Штакельберга определяется конкретная стратегия каждого типа ведомого при данной смешанной стратегии лидера L. Определим вектор функций g=(g¹,…, g^I), где gⁱ сопоставляет смешанную стратегию лидера с конкретной стратегией ведомого типа i. Пусть g(L) вектор действий ведомого по данной L согласно g, т.е. g(L)=(g¹(L),…, g^I(L)). Это позволяет формально определить сильное равновесие Штакельберга.

Определение. Для данной байесковской игры Штакельберга с матрицами выигрышей (U¹,V¹),…,(U^I, V^I) и распределением типов p, пара стратегий (L, g) является сильным равновесием Штакельберга тогда и только тогда, когда:

1. Лидер действует наилучшим образом:

u(L,g(L))≥u(L´, g(L´)), L´

2. Ведомый действует наилучшим образом:

νⁱ(L, gⁱ(L))≥νⁱ(L, f), 1≤i≤I, 1≤f≤F

3. Ведомый выбирает наилучший ответ стратегии лидера:

uⁱ(L, gⁱ(L))≥uⁱ(L, f), 1≤i≤I.

Решение игр Штакельберга

Стратегия лидера, которая удовлетворяет сильному равновесию Штакельберга, является оптимальной, т.к. она максимизирует ожидаемый выигрыш лидера, допуская, что ведомый действовал наилучшим образом. В этом разделе будут рассмотрены некоторые базовые алгоритмы для нахождения оптимальной стратегии лидера в байесовских играх Штакельберга.

Как показано в [4], проблема определения оптимальной стратегии лидера L* эквивалентна нахождению смешанной стратегии лидера L и конкретной стратегии ведомого f=g(L), которые удавлетворяют трем условиям сильного равновесия Штакельберга. Математически стратегия лидера L* может быть определена в результате решения следующей задачи максимизации:

(L*, f*)= .

Данную задачу максимизации можно решить используя методы линейного программирования, как дано в [4]. Идея состоит в переборе всех конкретных стратегий ведомого f {1,…,F}^I. Для каждого f, оптимальная стратегия лидера L*(f) определяется решением задачи линейного программирования:

, где f лучший ответ ведомого.

Оптимальное решение одной из задач линейного программирования, в которой (ожидаемый выигрыш лидера) имеет наибольшое значение определяет оптимальную стратегию лидера L*.

Так как ведомые разных типов независимы друг от друга, то наибольшее число возможных комбинаций лучших ответов ведомого равно F^I, где I количество типов ведомых. Таким образом, приведенный выше метод состоит из F^I линейных программ, что, естественно, ведет к экспоненциальному росту времени расчетов при увеличении количества типов ведомых.

В общем случае, проблема нахождения оптимальной стратегии для лидера в байесовской игре Штакельберга является NP-полной [4]. Но, несмотря на это, некоторые недавние исследования привели к определенным практическим результатам. Например, метод DOBSS (Decomposed Optimal Bayesian Stackelberg Solver) является эффективным метдом решения байесовской игры Штакельберга как показано в [2]. Метод заключается в преобразовании множество задач линейного программирования в одну задачу целочисленного программирования:

Идея метода состоит в представлении чистой стратегии каждого типа ведомого в бинарный вектор В частности, , если ведомый типа i выбрал стратегию f, в противном случае. Очевидно, что , т.к. только один может быть равным 1. M – бесконечно большая константа. Переменная uⁱ – ожидаемый выигрыш лидера против ведомого типа i, который определяется как , когда ведомый выбирает стратегию f (т.е. ). - ожидаемый выигрыш ведомого типа i, т.е.

Применение байесковских игр Штакельберга в сфере информационной безопасности

Приведенный метод может быть использован для моделирования проблем информационной безопасности. В частности, в роли лидера может выступать служба информационной безопасности (или организация), а в роли ведомого хакер (или организованная преступная группировка). Лидер действует первым, применяя разные методы информационной безопасности для защиты информационного пространства своей организации. Ведомый имеет возможность исследовать текущее состояние информационной сети и делать ответный ход конкретной стратегией в зависимости от результатов исследований. Можно смоделировать множество типов ведомых, т.к. существует много разных видов атак на информационные системы. Служба информационной безопасности осведомлена о статистическом распределении известных атак.

Служба информационной безопасности организации считается лидером исходя из следующих соображений:

1. Во многих организациях политика информационной безопасности является общедоступным документом;

2. Потенциальные инструменты и меры безопасности являются стандартными и известными. Злоумышленники могут изучить систему безопасности, которая внедрена в данной организации в результате исследования состояния информационной системы. Более того, такая информация часто общедоступна через компании, которые разрабатывают системы безопасности или через, собственно, эту орагнизацию.

3. Каждая система безопасности имеет свои недостатки и уязвимые места, что дает возможность злоумышленникам выбрать наилучший способ атаки.

Заключение

В данной статье было рассмотрено применение игр безопасности Штакельберга в сфере информационной безопасности. Было приведено подробное описание модели. В некоторых работах [1] [2] данная модель использовалась для обеспечения физической безопасности разных обьектов. Форма приведенной модели позволяет применить ее для задач информационной безопасности, где в роли лидера выступает системный администратор или специалист по информационной безопасности, а в роли ведомого злоумышленник (хакер).

Литература

[1] M. Tambe, M. Jain, J. A. Pita, A. Jiang “Game Theory for Security: Key Algorithmic Principles, Deployed Systems, Lessons Learned”, in 50th Annual Allerton Conference on Communication, Control, and Computing, 2012

[2] P. Paruchuri, J. P. Pearce, J. Marecki, M. Tambe, F. Ordonez, and S. Kraus, “Playing Games with Security: An Efficient Exact Algorithm for Bayesian Stackelberg Games,” in Proc. of The 7th InternationalConference on Autonomous Agents and Multiagent Systems (AAMAS),2008.

[3] D. Korzhyk, Z. Yin, C. Kiekintveld, V.Conitzer, M.Tambe,“Stackelberg vs Nash in Security Games - An Extended investigation of interchangeability, equivalence and uniqueness”, in Journal of Artificial Intelligence Research 41,2011.

[4] V. Conitzer, T. Sandholm, “Computing the optimal strategy to commit to”, in EC,2006.

[5] M. Jain, E. Kardes, C. Kiekintveld, M. Tambe, F. Ordonez. “Security games with arbitrary schedules: A branch and price approach”, in AAAI, 2010.