Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Оптимізація розподілу ресурсів між об’єктами системи захисту інформації ускладнюється тим, що протистояння відбувається в умовах невизначеності, коли дії суперника невідомі. Одним з підходів до вирішення цієї проблеми є динамічне управління ресурсами, при якому захист оперативно реагує на дії суперн...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2014 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85556 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки / М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 86-98. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859764305481695232 |
|---|---|
| author | Демчишин, М.В. Левченко, Є.Г. Рабчун, Д.І. |
| author_facet | Демчишин, М.В. Левченко, Є.Г. Рабчун, Д.І. |
| citation_txt | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки / М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 86-98. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| container_title | Системні дослідження та інформаційні технології |
| description | Оптимізація розподілу ресурсів між об’єктами системи захисту інформації ускладнюється тим, що протистояння відбувається в умовах невизначеності, коли дії суперника невідомі. Одним з підходів до вирішення цієї проблеми є динамічне управління ресурсами, при якому захист оперативно реагує на дії суперника, змінюючи свою стратегію після кожного його кроку. Невизначеність викликає певні труднощі в організації захисту, що в деяких випадках взагалі унеможливлюють процес динамічного управління. Інший підхід ґрунтується на забезпеченні гарантованого результату, коли розподіл ресурсів захисту не є оптимальним для всіх стратегій суперника, проте дає упевненість, що втрати інформації не будуть перевищувати визначену величину при будь-яких його діях. Реалізацією цього підходу є сідлова точка матричної гри, котра відображає стан спокою динамічного протистояння двох сторін. У системі, котра містить два об’єкти, проаналізовано умови існування сідлової точки у залежності від вразливості об’єктів, розподілу ресурсів між ними, співвідношення між ресурсами сторін протистояння.
Оптимизация распределения ресурсов между объектами системы защиты информации усложняется тем, что противостояние происходит в условиях неопределенности, когда действия соперника неизвестны. Одним из подходов к решению этой проблемы является динамическое управление ресурсами, при котором защита оперативно реагирует на действия соперника, меняя свою стратегию после каждого его шага. Неопределенность вызывает определенные трудности в организации защиты, что в некоторых случаях вообще делает процесс динамического управления невозможным. Другой подход основывается в обеспечении гарантированного результата, когда распределение ресурсов защиты не является оптимальным для всех стратегий соперника, однако дает уверенность, что потери информации при любых его действиях не будут превышать определенную величину. Реализацией данного подхода является седловая точка матричной игры, которая отражает состояние покоя динамического противостояния двух сторон. В системе, содержащей два объекта, проанализированы условия существования седловых точек в зависимости от уязвимости объектов, распределения ресурсов между ними, соотношение между ресурсами противоборствующих сторон.
An optimization of resources allocation between information security objects is complicated due to the fact that the opposition occurs in uncertainty conditions when the opponent actions are unknown. First approach to solve this problem is the dynamic resources management in which protection reacts to the opponent’s actions effectively by changing the strategy after every opponent’s step. In some cases, the uncertainty causes difficulties in implementing the protection that makes the process of dynamic management impossible. Another approach is based on providing a guaranteed outcome when the allocation of protection resources is not optimal for all strategies of the opponent, but guarantees that, for any of its actions, the information loss will not exceed the defined value. The implementation of this approach is the matrix game saddle point, which reflects the dormancy state of the dynamic confrontation between two sides. The saddle point existence conditions are analyzed in a system of two objects depending on its vulnerability, resources allocation between them, and the conflicting sides resources ratio.
|
| first_indexed | 2025-12-02T04:50:47Z |
| format | Article |
| fulltext |
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун, 2014
86 ISSN 1681–6048 System Research & Information Technologies, 2014, № 3
УДК 004.681
ГРАФОАНАЛІТИЧНИЙ МЕТОД ПОШУКУ СІДЛОВОЇ ТОЧКИ
В ІГРОВИХ ЗАДАЧАХ ІНФОРМАЦІЙНОЇ БЕЗПЕКИ
М.В. ДЕМЧИШИН, Є.Г. ЛЕВЧЕНКО, Д.І. РАБЧУН
Оптимізація розподілу ресурсів між об’єктами системи захисту інформації
ускладнюється тим, що протистояння відбувається в умовах невизначеності,
коли дії суперника невідомі. Одним з підходів до вирішення цієї проблеми є ди-
намічне управління ресурсами, при якому захист оперативно реагує на дії су-
перника, змінюючи свою стратегію після кожного його кроку. Невизначеність
викликає певні труднощі в організації захисту, що в деяких випадках взагалі
унеможливлюють процес динамічного управління. Інший підхід ґрунтується
на забезпеченні гарантованого результату, коли розподіл ресурсів захисту не
є оптимальним для всіх стратегій суперника, проте дає упевненість, що втрати
інформації не будуть перевищувати визначену величину при будь-яких
його діях. Реалізацією цього підходу є сідлова точка матричної гри, котра ві-
дображає стан спокою динамічного протистояння двох сторін. У системі,
котра містить два об’єкти, проаналізовано умови існування сідлової точки
у залежності від вразливості об’єктів, розподілу ресурсів між ними, співвід-
ношення між ресурсами сторін протистояння.
ВСТУП
Протистояння в інформаційній сфері відбувається в умовах невизначеності.
Це приводить до того, що рішення про необхідну кількість ресурсів та їх
розподіл між об’єктами доводиться приймати, не маючи відомостей щодо
аналогічних рішень суперника. У зв’язку з цим виникає потреба у розробці
такої стратегії, яка б забезпечувала виконання певних умов оптимальності за
будь-яких дій протилежної сторони. Користуючись термінологією теорії
ігор, необхідно знайти рішення гри з сідловою точкою. Ця точка характерна
тим, що нижнє значення гри (мінімально можливе для захисту втрати інфо-
рмації) дорівнює її верхньому значенню (максимально досяжній кількості
здобутої нападом інформації). Така ситуація є рівноважною: жодна одна зі
сторін не зацікавлена в її порушенні.
Пошук сідлової точки в наших умовах ускладнюється тим, що задача
не може бути зведена до матричної гри із скінченим числом стратегій: кіль-
кість ресурсів, котрі виділяє кожна зі сторін, може приймати будь-які зна-
чення, звичайно, в певному розумному інтервалі. Наближений аналітичний
розв’язок можна отримати, якщо розглянути дискретні набори розподілів
ресурсів нападу та захисту, і послідовно уточнювати результати, зменшую-
чи інтервал дискретизації. Знаходження сідлової точки визначає відповідні
розподіли ресурсів, які вважаємо оптимальними.
Аналітичний підхід до розв’язку задачі, в якій задіяно велику кількість
параметрів і функціональних залежностей, не завжди дає можливість про-
аналізувати закономірності у великому масиві результатів. У [1] здійснено
спробу геометричного тлумачення розв’язання задачі оптимального розпо-
Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Системні дослідження та інформаційні технології, 2014, № 3 87
ділу ресурсів нападу. Такий підхід дає можливість пояснити зміну стратегії,
а саме: перехід від розподілу ресурсів між об’єктами до їх зосередження на
одному з них. Проте графічне зображення розв’язку в тривимірному прос-
торі можливе лише для системи з двох об’єктів, що в загальному випадку
обмежує застосування наведеної методики.
Мета роботи — розробка методу оптимізації розподілу ресурсів у сис-
темі з довільною кількістю об’єктів, який включає геометричну інтерпрета-
цію пошуку сідлової точки.
МЕТОДИКА РОЗРАХУНКІВ І РЕЗУЛЬТАТИ
Розглянемо у якості прикладу систему з чотирьох об’єктів (рис.1,а) та вико-
ристаємо математичну модель [2], в якій цільова функція визначає частку
втраченої інформації в системі:
,),(),(),(),(
11
l
k
kkkk
l
k
k yxfyxqpgyxiyxi (1)
де x та y — ресурси нападу і, відповідно, захисту, ,
1
l
k k Xx
;
1
l
k k Yy k — номер об’єкта; kg — відносна вартість інформації на
k-му об’єкті (через kg також позначається сам об’єкт); kp — імовірність
нападу на k-й об’єкт; ),( yxqk — імовірність виділення нападом ресурсів x
на k-ий об’єкт при заданому значенні ;y ),( yxfk — імовірність вилучення
інформації з k-го об’єкту, яку розглядаємо як динамічну вразливість об’єкта.
Найважливішою характеристикою системи інформаційної безпеки є вра-
зливість її об’єктів. У подальшому зосередимось на розгляді впливу цієї ха-
рактеристики і покладемо 1kp (напад відбувся) та 1const),( yxqk
(імовірності виділення нападом різної кількості ресурсів однакові).
Тоді цільова функція (1) матиме вигляд
1g 2g
X
Y
1x 2x
1y 2y
б
1g 2g 3g 4g
1x 2x 3x 4x
1y 2y 3y 4y
а
X
Y
Рис. 1. Схеми інформаційного протистояння: а — в системі з чотирьох об’єктів;
б — в системі з двох об’єктів
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун
ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 88
.),(),(
1
l
k
kk yxfgyxi (2)
Величини в правій частині (2) — відносні: ),(,, yxfyx k віднесені до
вартості інформації на об’єкті, kg — до вартості інформації системи.
У відповідності до моделі [2] вважаємо, що вразливість залежить від
співвідношення ресурсів нападу і захисту, тобто від відношення yx / на
конкретному об’єкті. Функції ),( yxfk мають задовольняти умовам: при
0y
x ,0),( yxfk при y
x 1),( yxfk . Цим умовам відповіда-
ють дробово-степеневі та показникові функції [2]. Враховуючи, що ці зале-
жності повинні мати близькі форми, обмежимось розглядом дробово-
степеневих функцій:
k
n
n
k
cyx
yx
yxf
k
k
)/(
)/(
),( . (3)
У наступних розрахунках використаємо такі функції :),( yxfk
4/
/
),(1
yx
yx
yxf ,
32)/(
)/(
),(
3
3
2
yx
yx
yxf , (4) (5)
8)/(
)/(
),(
2
2
3
yx
yx
yxf ,
16)/(
)/(
),(
3
3
4
yx
yx
yxf . (6) (7)
Параметри у виразах (4)–(7) вибрані довільно — з метою максимально
виразного представлення результатів. Форми наведених залежностей зобра-
жено на рис. 2 а, в (номери кривих відповідають виду залежностей (4)–(7)).
Пошук сідлової точки ведеться ітераційним методом, шляхом почерго-
вого розв’язання задач оптимізації розподілу власних ресурсів кожної зі
сторін. Розподіл ресурсів суперника після попереднього кроку вважається
відомим (антагоністична позиційна гра з повною інформацією) [3]. На пер-
шому кроці приймемо, що протилежна сторона поділила свої ресурси про-
порційно розподілу інформації на об’єктах. У проведених розрахунках при-
йнято рівномірний розподіл інформації по об’єктах: 321 ggg
,25,04 g .1
4
1
k
kg Вважаємо, що сторона з ресурсами
4
1k
kyY захи-
щає інформацію, а сторона з ресурсами
4
1k
kxX прагне її вилучити.
Перший крок робить сторона .X Розподіл ресурсів Y на цьому кроці від-
повідно до розподілу }{ kg вважаємо рівномірним: 4321 yyyy .
Оптимальний розподіл ресурсів можна знайти шляхом перебору варіан-
тів між усіма об’єктами. Проте з метою графічного зображення процесу оп-
тимізації поділимо всю систему на пари об’єктів та розділимо процес опти-
мізації на два етапи. Перший етап направлено на пошук оптимальних
Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Системні дослідження та інформаційні технології, 2014, № 3 89
розподілів для кожної пари об’єктів, другий — для усієї системи, що вклю-
чає, в нашому випадку, дві пари об’єктів.
Результати розрахунків на першому етапі у всьому інтервалі зміни мож-
ливих значень 3,0...0X при незмінному і рівномірному розподілі ресурсів
Y між об’єктами ( 2,0Y , 05,0ky ) показано на рис. 2 б, г. Напівжирною
кривою зображено лінію найкрутішого підйому, тобто найбільш ефективно-
го розподілу ресурсів при різних значеннях .X Одержані результати дають
змогу проаналізувати динаміку розподілу ресурсів між об’єктами при зрос-
танні загальної кількості ресурсів нападу. Спочатку всі ресурси доцільно
вкладати в 1x , 3x , тобто в об’єкт 1g для першої пари та 3g для другої пари
(відрізки AB на рис. 2, б, г). Потім більш ефективною стає стратегія розподі-
лу ресурсів між двома об’єктами (відрізки BC). У точці C всі ресурси слід
вкласти в один об’єкт — 2g на рис. 2, б та 4g на рис. 2, г. Для другої пари
об’єктів точка C переходить у відрізок CD. При подальшому збільшенні X
більш ефективним знову стає розподіл ресурсів, причому для першої пари
об’єктів значення 1x та 2x зростають монотонно (відрізок CF на рис. 2,б),
а в другій парі спочатку спостерігається перерозподіл ресурсів між
)(2,1 xi
0,2
0,15
0,1
0,05
0 0,05 0,1 0,15 0,2 0,25 0,3
21 , xx
a
6
7
4
5
0 0,05 0,1 0,15 0,2 0,25 0,3
43 , xx
в
)(4,3 xi
0,25
0,2
0,15
0,1
0,05
г
0,2
0
)(4,3 xi
0,5
0,4
0,3
0,2
0,1
0
4x 3x
0,3 0,1
0,1 0,2 А
B
C
D
E
F
B
C
F
)(2,1 xi
0,4
0,3
0,2
0,1
0
2x
1x
0,3 0,1
0,1
0,2
А
0
0,2
б
Рис. 2. Характеристики пар об’єктів 1g , 2g (а, б) та 3g , 4g (в, г): а, в — форми
функцій вразливості об’єктів; б, г — оптимальний розподіл ресурсів між об’єктами
(напівжирні лінії)
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун
ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 90
об’єктами — зростання 3x відбувається при зменшенні 4x (відрізок DE на
рис. 2, г), а далі обидві величини зростають монотонно (відрізок EF).
Наведені результати являють собою частинні розв’язки поставленої за-
дачі та входять як складові ),( 211 xxi , ),( 432 xxi в цільову функцію
),,,( 4321 xxxxi , котра є сепарабельною:
),(),(),,,( 43
)2(
21
)1(
4321 xxixxixxxxi
168324 3
4
3
4
42
3
2
3
32
2
2
2
2
1
1
1
x
x
g
x
x
g
x
x
g
x
x
g . (8)
Графічно функцію (8) можна представити у вигляді просторової фігури
),( 21 XXi , де 211 xxX , 432 xxX , XXX 21 (рис. 3, б). Ребрами
цієї фігури є функції ),( 1
)1( Xi )( 2
)2( Xi з рис. 2, б, г (рис. 3, а).
Лінія найкрутішого підйому на рис. 3, б разом із відповідними лініями
на рис. 2, б, г дозволяє визначити множину значень цільової функції (8), кот-
рі відображають оптимальний розподіл ресурсів між чотирма об’єктами для
всіх можливих значень .X Для цього в площині 210XX (рис. 3, б) слід про-
вести пряму XXX 21 та через неї побудувати вертикальну площину,
паралельну осі ),( 21 XXi . Перетин площини з лінією найшвидшого підйому
дає точку оптимізації, а її проекція на площину 210XX — точку А на прямій
,21 XXX яка і визначає оптимальний розподіл ресурсів ,0
1X .0
2X Ви-
ходячи зі значень ,0
1X ,0
2X аналогічним методом знаходимо оптимальний
розподіл ресурсів ,1x 2x (рис. 2, б) та ,3x 4x (рис. 2, г).
Далі розглядаємо хід протилежної сторони: вважаючи відомим розпо-
діл }{ kx , знаходимо оптимальний розподіл }.{ ky Для цього, виходячи із
заданого значення ,Y будуємо просторові фігури ),,( 21 yyi ),,( 43 yyi знахо-
димо лінії найшвидшого спуску та оптимальний розподіл ресурсів захисту
)(),( 2
)2(
1
)1( XiXi
0,4
0,3
0,2
0,1
0 0,1 0,2 0,3 0,4 0,5 0,6
21 , XX
a б
0,5
0
),( 21 XXi
1
0,8
0,6
0,4
0,2
0
2X
0,4 0,2
А
0,6 0
2X 0
1X
Рис. 3. Оптимальний розподіл ресурсів X для пар об’єктів
Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Системні дослідження та інформаційні технології, 2014, № 3 91
між об’єктами. Почергові кроки, в яких напад розподіляє свої ресурси з ме-
тою максимізації вилученої інформації ),,,,( 4321 xxxxi а захист розподіляє
свої ресурси з метою мінімізації ),,,,( 4321 yyyyi приводять до ситуації, ко-
ли ці значення зрівнюються — суперникам невигідно змінювати власні
стратегії, що і є сідловою точкою.
Як приклад, зобразимо графічну інтерпретацію пошуку сідлової точки
в системі з двох об’єктів (рис. 1, б). Враховуючи, що умови існування сідло-
вої точки суттєво залежать від форми функцій вразливості, розглянемо два
варіанти. У першому випадку вразливості об’єктів виражаються дробово-
лінійними функціями, в другому — дробово-нелінійними. Оберемо дробово-
лінійні функції у вигляді:
2/
/
),()1(
1
yx
yx
yxf ;
4/
/
),()1(
2
yx
yx
yxf , (9)
а дробово-нелінійні:
32)/(
)/(
),(
2
2
)2(
1
yx
yx
yxf ;
192)/(
)/(
),(
3
3
)2(
2
yx
yx
yxf . (10)
Цільова функція для першої пари вразливостей має вигляд:
4/
/
2/
/
),(
22
22
2
11
11
1
)1(
yx
yx
g
yx
yx
gyxi , (11)
для другої:
192)/(
)/(
32)/(
)/(
),(
3
22
3
22
2
11
2
11)2(
yx
yx
yx
yx
yxi . (12)
Розподіл інформації між об’єктами вважаємо рівномірним:
.5,021 gg Перший крок робить напад. Розподіл ресурсів захисту на
цьому кроці встановимо пропорційно розподілу інформації на об’єктах,
тобто також рівномірним. Для першої системи маємо: 2,0X , 05,0Y ,
;4 YXZ для другої — ,3,0X ,05,0Y .6 YXZ Вибір розрахун-
кових параметрів обумовлений, як і у попередньому випадку, прагненням
найбільш виразного представлення результатів і не обмежує загальність за-
стосування методики.
Графічне зображення кроків ),( 21 xxi та ),( 21 yyi має вигляд просторо-
вих фігур (рис. 4), одержаних із використанням пакету Optimization Toolbox
програмного комплексу Matlab. Кожен крок являє собою розв’язок задачі
умовної оптимізації: знаходження максимуму або мінімуму цільової функції
за обмежень, котрі накладаються на ресурси нападу і, відповідно, захисту.
На першому кроці перетин просторової фігури ),( 21 xxi з вертикальною
площиною, що проходить через обмежувальну пряму ,2,0X дає лінію пе-
рерізу (вона позначається напівжирною лінією на рис. 4, а). Ця лінія визна-
чає множину усіх можливих значень ),,( 21 xxi котра відповідає різним роз-
поділам },{ 21 xx при заданому обмеженні .X На наступному кроці
аналогічну процедуру здійснюємо відносно просторової фігури ),( 21 yyi і об-
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун
ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 92
межувальної прямої 05,0Y (рис. 4, б). Точки оптимізації на кожному кро-
ці позначаються квадратиками.
Просторові фігури ),( 21 xxi та ),( 21 yyi являють собою множину
розв’язків цільової функції в межах загальних ресурсів нападу X та захисту
Y за умови незмінності обсягу ресурсів протилежної сторони: на першому
кроці XY ,const — var, на другому YX ,const — var. У цьому випад-
ку має місце умовна оптимізація: умову накладено на обсяги ресурсів X та
,Y тобто пошук оптимального розв’язку відбувається серед числових зна-
чень діагонального перерізу (рис. 4 — діагональна напівжирна лінія), що
собою і являє накладення вищезгаданої умови.
Обмежувальні напівжирні лінії, які одержано в результаті перерізу про-
сторової фігури координатними площинами, зображають функції вразливо-
сті, на котрих побудована фігура: на рис. 4,а при 02 x це )( 1
)1(
1 xf (9), роз-
рахована при 025,0
21
Y
y , при 01 x це )( 2
)1(
2 xf та .025,02 y На
рис. 4, в це функції )( 1
)2(
1 xf та )( 2
)2(
2 xf (10). На рис. 4,б , г маємо відпові-
дні функції )(yf з (9), (10) при знайдених значеннях 21, xx .
Залежності ),( 21 xxi та ),( 21 yyi дають змогу знайти оптимальні зна-
чення цільових функцій кожної зі сторін і відповідні розподіли своїх ресур-
сів при заданих величинах ресурсів протилежної сторони. Динамічне проти-
),( 21 xxi
0,6
0,4
0,2
0
a
2x 1x
0,1 0,1
0
0,2
0,2
в
2x 1x 0
0,3
0,1
0,2
0,1 0,2
б г
),( 21 yyi
0,8
0,6
0,4
0,2
2y 1y 0,05
0
0,04
0,02
),( 21 yyi
0,9
0,8
0,7
0,6
0,5
2y 1y
0,02
0,05
0
0
0,04
0
Рис. 4. Графічне зображення розв’язку задач максимізації вилучення (а, в) і мінімі-
зації втрат (б,г) інформації в системі з двох об’єктів у випадку дробово-лінійних
(а,б) та дробово-нелінійних (в,г) функцій вразливості
Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Системні дослідження та інформаційні технології, 2014, № 3 93
стояння, яке призводить до сідлової точки (якщо вона існує), можна спосте-
рігати в системі координат, де враховано зміну ресурсів обох сторін. З цією
метою на рис. 5 зображено функції ),,( 21 zzi де 111 yxz , 222 yxz . Про-
аналізуємо умови появи сідлової точки.
Лінія AB на рис. 5,а відображає ситуацію, за якої усі ресурси захисту
зосереджено на другому об’єкті ( 021 yy ), а ресурси нападу поступово
перерозподіляють, збільшуючи частку ресурсів 1x на першому об’єкті.
У початковій області значення i стрибком зростає до максимального, оскі-
льки при 01 y з першого об’єкта вилучається вся інформація при будь-
якому 01 x . Частка інформації, яка вилучається з другого об’єкта при зро-
станні відношення 21 xx , поступово зменшується через те, що збільшення
величини 1x відбувається за рахунок зменшення 2x . В результаті лінія AB
демонструє зменшення загальної величини 21 iii .
Лінію AD одержано при 01 x — всі ресурси нападу направлено на
другий об’єкт і вилучення інформації відбувається тільки з другого об’єкта.
Зростання відношення 21 yy вздовж лінії AD відбувається за рахунок збіль-
шення кількості ресурсів 1y на першому об’єкті за одночасного зменшення
2y на другому. В результаті величина i зростає.
Лінія DC відповідає ситуації, коли переважну кількість ресурсів захис-
ту зосереджено на першому об’єкті: 2021 yy . Другий об’єкт практично
не захищений, і з нього вилучається майже вся інформація. При збільшенні
1x зростає 1i , а за ним сумарне значення ,i причому ці величини переви-
щують відповідні значення на кривій ,AB одержані за тих самих співвідно-
шень .21 xx Це пояснюється тим, що на лінії AB зростання 1x не дає ко-
рисного ефекту, оскільки при 01 y з першого об’єкту вилучається вся
інформація при будь-якому значенні 1x . Ефект, як зазначалось, зворотній —
за рахунок зменшення 2x і, відповідно, зменшення 2i .
а б
A
B
C
D
),( 21 zzi
0,6
0,4
0,2
20
1
0
1
20
2
1
y
y
(мінімізація)
2
1
x
x
(максимізація)
),( 21 zzi
0,6
0,4
0,2
20
1
0
1
20
2
1
y
y
(мінімізація) 2
1
x
x
(максимізація)
Рис. 5. Поява сідлової точки при зміні розподілу ресурсів і використанні різних
типів функцій вразливості: а — дробово-лінійних (9) при 2,0X , ,05,0Y ,4Z
б — дробово-нелінійних (10) при 25,0X , 05,0Y , 5Z
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун
ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 94
Для лінії BC маємо велике відношення 21 xx )20( 21 xx , тобто пе-
реважну кількість ресурсів нападу зосереджено на першому об’єкті. При
збільшенні ресурсів захисту 1y на цьому об’єкті величина 1i зменшується,
в той час, як 2i змінюється несуттєво через низьке значення 2x . Під час на-
ближення до точки C значення 2y стає настільки малим, що різко зростає
2i , а з ним величина i . В результаті маємо просторову фігуру, в якій дві
протилежні границі AB та CD мають опуклість направлену вгору, а дві
інші — AD та BC — опуклість, направлену донизу. Така форма границі
й забезпечує появу сідлової точки.
Зазначимо, що наведені особливості фігури ),( 21 zzi спостерігаються
у випадку, коли вразливості об’єктів ),( yxf описуються дробово-лінійними
функціями. Якщо хоча б одна з функцій є дробово-нелінійною, то за певних
Z напрямок окремих опуклостей може зміститися, і сідлова точка не мати-
ме місця. У цьому випадку пошук сідлової точки зводиться до нескінченно-
го циклічного процесу почергового розв’язання задач максимізації та міні-
мізації. На рис. 6, а показано цей процес у системі з двох об’єктів,
вразливості котрих описуються дробово-нелінійними функціями (11), (12),
але на відміну від рис. 5, при .7Z Кружечками зображено граничні точки
циклу. На рис. 6, б представлено просторове зображення цього процесу.
Проаналізуємо зміну станів протягом декількох кроків, починаючи
з точки 1 (вона визначається початковим розподілом ресурсів і відповідає
значенню )63,0)z,z( 21 i . Перший крок, який робить захист, зображає пере-
хід з точки 1 у точку 2 вздовж лінії ,const21 xx 21 yy — var. Мінімальне
значення 62,0i за такого руху досягається на границі області — в точці 2,
де 2021 yy (майже усі ресурси захисту зосереджено на першому об’єкті).
Наступний крок, котрий робить напад, направлено на максимізацію значен-
ня i та зображається рухом вздовж лінії 2021 yy з точки 2 в точку 3, що
знаходиться на перетині граничних ліній і відповідає значенню 8,0i .
20
а б
),( 21 zzi
0,8
0,6
0,4
20
0
1
2
1
y
y
(мінімізація) 2
1
x
x
(максимізація)
1
),( 21 zzi
1
0,8
0,4
0,2
0
2 4 6 8 10 12 14 16
Кроки
3
2
1
Рис. 6. Циклічний процес пошуку сідлової точки (а) і його просторове зобра-
ження (б): ламана 1 — )z,z( 21оптi , 2 — )z,z( 21опт1i , 3 — )z,z( 21опт2i
Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Системні дослідження та інформаційні технології, 2014, № 3 95
У подальшому рух відбувається вздовж лінії ,2021 xx і через декілька
кроків ми переходимо на ще одну граничну лінію 021 yy та зрештою по-
вертаємось у початкову точку. Той факт, що у своєму русі робоча точка пе-
ріодично виходить на границі області, свідчить про те, що процес не є збіж-
ним, оскільки сідлова точка відсутня (сідлові точки розглядаємо лише
в чистих стратегіях).
На форму просторової фігури і наявність сідлової точки впливає: форма
функцій вразливості ),,( yxfk яка визначається параметрами cn, та спів-
відношенням ресурсів нападу і захисту ,YXZ яке обмежує можливі зна-
чення yx в функціях вразливості, а також розподіл інформації 21 gg між
об’єктами.
Найбільший вплив на інтервал Z серед інших чинників мають враз-
ливості об’єктів, а саме ступінь нелінійності функцій ),( yxf , яка, в основ-
ному, визначається параметром n . При дробово-лінійних функціях )1( n ,
а також при 1n сідлова точка існує при всіх значеннях .Z Вплив обох па-
раметрів — n та c — показано на рис. 7, а, де зображено інтервали існу-
вання сідлової точки в системі з двох однакових об’єктів ( 21 gg ,
nnn 21 ) за різних n для двох значень c . Величини Z на рис. 7, а пока-
зані до значень ,20Z величини n — до .3n При 1n інтервал Z стає
обмеженим, при 1n з’являється нижня межа, котра при 32c та зростан-
ні n монотонно рухається в бік збільшення ,Z а потім (при 5,1n ) нижня
межа починає опускатись і виникає верхня межа, яка рухається в бік малих
,Z поступово звужуючи інтервал Z й переміщуючи його в бік менших .Z
При 192c форма лінії, яка зображає верхню межу, практично не змі-
нюється, проте сама лінія зміщується в бік більших .n Поведінка нижньої
межі виражена більш яскраво: в інтервалі значень n від 1 до 1,35 спостері-
гається різке зростання, а при 35,1n — поступовий спад. Ширина інтер-
валу Z існування сідлової точки поступово спадає зі збільшенням ,n
а самі інтервали зміщуються в бік більших значень .n
Z
20
15
10
5
0 1 1,5 2 2,5 3
n
192c
32c
192c
32c
n c
Z
20
15
10
5
1
2
3
0,5
1,5
2,5 50
100
150
200
a б
Рис. 7. Інтервали існування сідлових точок при 21 gg та: а — при різних n та
двох значеннях с; б — при різних n та різних c
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун
ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 96
Значення ,Z необхідні для існування сідлової точки, в залежності від
обох параметрів n та c при їх неперервній зміні, показано у вигляді прос-
торової фігури на рис. 7, б. Інтервали Z знаходяться між нижньою і верх-
ньою поверхнями. Напівжирними лініями виділено верхні межі зображених
на рис. 7, а, залежностей )(nZ для двох значень 32c та .192c Попередні
результати отримані для випадку, коли інформацію розподілено між
об’єктами порівну: .21 gg
На рис. 8 показано інтервали існування сідлових точок у залежності від
відношення 21 gg для системи з дробово-нелінійними функціями вразливості.
При певному співвідношенні 21 gg інтервал Z існування сідлової точки
досягає максимуму (на рис. 8 цей інтервал має місце при 7241,021 gg
і становить 995,1752,4747,6)( max Z ). Зазначимо, що просторова фі-
гура (рис. 5, б) відповідає точці А на рис. 8 з 121 gg , 5Z , котра знахо-
диться в області існування сідлових точок, а фігура, зображена на рис. 6,б —
точці В з 7Z поза межами цієї області.
Ще один важливий показник — значення )(Zi в інтервалі існування сі-
длової точки. Ці величини показано у вигляді просторової фігури ),( Zni на
рис. 9, б. Поверхня ),( Zni має досить складну форму, вигнуту в обох на-
прямках.
Швидкість досягнення сідлової точки в процесі почергової оптимізації
залежить від того, наскільки близько знаходиться початкова точка від сідло-
вої. Проаналізуємо вплив початкових умов на кількість кроків, необхідних
для досягнення сідлової точки в системі, сформованій дробово-нелінійними
функціями ),( yxf (6), (7) (рис. 2, в). Результати рис. 10, а, б одержані за
початкових умов ,025,0221 Yyy результати рис. 10, б, г — при
.0275,0,0225,0 21 yy Кількість кроків при цьому зросла з чотирьох до
дванадцяти.
Z
7
6
5
4
3
0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2
21 gg
А
В
Рис. 8. Область існування сідлових точок
у випадку дробово-нелінійних функцій
),( yxf
n
Z
),( ZnI
0,6
0,4
0,2
0
1
2
3
0,5
1,5
2,5 0
5
10
20
15
Рис. 9. Значення ),( Zni в області існу-
вання сідлової точки при 32c
Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки
Системні дослідження та інформаційні технології, 2014, № 3 97
Порівняння математичної моделі [2] з іншими моделями показує [4], що
використана нами модель дає якісно, а при певному виборі параметрів —
кількісно співпадаючі результати з моделлю Гордона–Лоеба [5], котра
знайшла своє емпіричне підтвердження [6], проте має менший діапазон за-
стосування, зокрема не призначена для оптимізації розподілу ресурсів між
об’єктами. Це дає можливість сподіватись, що наведена методика буде ко-
рисною під час проектування оптимальних систем захисту інформації.
ВИСНОВКИ
Існування сідлової точки залежить від параметрів n та c функцій вразливо-
сті об’єктів, розподілу інформації 21 ggG по об’єктах, співвідношення
YXZ ресурсів нападу і захисту. При 1n сідлова точка існує за будь-
яких значень інших параметрів. При 1n інтервал Z існування сідлової
точки залежить від n , c та .G На параметри G та Z ми можемо впливати,
розподіляючи інформацію між об’єктами і виділяючи певну кількість ресур-
сів на захист. Визначення параметрів n та c вимагає встановлення форми
функціональних залежностей ),,( yxfk котрі виражають динамічні вразли-
1x
),( 21 zzi
0,8
0,7
0,6
0,5
0,3
0,2
0,1
0
2 4 6 8 10 12
Кроки б
),( 21 zzi
0,4
0,3
0,2
0,1
0
a
1 1,5 2 2,5 3 3,5 4
Кроки
г)
в г
),( 21 zzi
0,8
0,6
0,4
0,2
20
1
0
1
20
2
1
y
y
(мінімізація) 2
1
x
x
(максимізація)
),( 21 zzi
0,8
0,6
0,4
0,2
20
1
0
1
2
1
y
y
(мінімізація)
2
1
x
x
(максимізація)
0
20
Рис. 10. Пошук сідлової точки (а, б) і його графічне зображення (в, г) за різних по-
чаткових умов: 025,021 yy (а, в), ,0225,01 y 0275,02 y (б, г)
М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун
ISSN 1681–6048 System Research & Information Technologies, 2014, № 3 98
вості об’єктів. Ці залежності мають найбільший вплив на інформаційну без-
пеку системи. Визначення їх форми і ступеня відповідності реальним систе-
мам є важливим завданням математичного моделювання процесу проти-
стояння двох сторін в інформаційній сфері.
ЛІТЕРАТУРА
1. Демчишин М.В. Геометрична інтерпретація оптимізації розподілу ресурсів між
об’єктами захисту інформації, Захист інформації. — 2011. — № 2(51). —
С. 21–28.
2. Левченко Є.Г., Рабчун А.О. Оптимізаційні задачі менеджменту інформаційної
безпеки // Сучасний захист інформації. — 2010. — № 1. — С. 16–23.
3. Шикин Е.В., Шикина Г.Е. Исследование операций. — М.: Проспект. — 2006. —
280 с.
4. Левченко Є.Г., Демчишин М.В., Рабчун А.О. Математичні моделі економічного
менеджменту інформаційної безпеки // Системні дослідження та
інформаційні технології. — 2011. — № 4. — С. 88–96.
5. Gordon L.A., Loeb M.P. The Economics of Information Security Investment // ACM
Transactions on Information and System Security. — 2002. — 5, № 4. —
P. 438–457.
6. Liu W., Tanaka H., Matsuura K. Empirical-Analysis Methodology for Information-
Security Investment and Its Application to a Reliable Survey of Japanese
Firms // Information Processing of Japan Digital Courier, Sep. 2007. — 3. —
P. 585–599.
Надійшла 29.10.2012
|
| id | nasplib_isofts_kiev_ua-123456789-85556 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1681–6048 |
| language | Ukrainian |
| last_indexed | 2025-12-02T04:50:47Z |
| publishDate | 2014 |
| publisher | Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| record_format | dspace |
| spelling | Демчишин, М.В. Левченко, Є.Г. Рабчун, Д.І. 2015-08-07T12:26:40Z 2015-08-07T12:26:40Z 2014 Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки / М.В. Демчишин, Є.Г. Левченко, Д.І. Рабчун // Системні дослідження та інформаційні технології. — 2014. — № 3. — С. 86-98. — Бібліогр.: 6 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/85556 004.681 Оптимізація розподілу ресурсів між об’єктами системи захисту інформації ускладнюється тим, що протистояння відбувається в умовах невизначеності, коли дії суперника невідомі. Одним з підходів до вирішення цієї проблеми є динамічне управління ресурсами, при якому захист оперативно реагує на дії суперника, змінюючи свою стратегію після кожного його кроку. Невизначеність викликає певні труднощі в організації захисту, що в деяких випадках взагалі унеможливлюють процес динамічного управління. Інший підхід ґрунтується на забезпеченні гарантованого результату, коли розподіл ресурсів захисту не є оптимальним для всіх стратегій суперника, проте дає упевненість, що втрати інформації не будуть перевищувати визначену величину при будь-яких його діях. Реалізацією цього підходу є сідлова точка матричної гри, котра відображає стан спокою динамічного протистояння двох сторін. У системі, котра містить два об’єкти, проаналізовано умови існування сідлової точки у залежності від вразливості об’єктів, розподілу ресурсів між ними, співвідношення між ресурсами сторін протистояння. Оптимизация распределения ресурсов между объектами системы защиты информации усложняется тем, что противостояние происходит в условиях неопределенности, когда действия соперника неизвестны. Одним из подходов к решению этой проблемы является динамическое управление ресурсами, при котором защита оперативно реагирует на действия соперника, меняя свою стратегию после каждого его шага. Неопределенность вызывает определенные трудности в организации защиты, что в некоторых случаях вообще делает процесс динамического управления невозможным. Другой подход основывается в обеспечении гарантированного результата, когда распределение ресурсов защиты не является оптимальным для всех стратегий соперника, однако дает уверенность, что потери информации при любых его действиях не будут превышать определенную величину. Реализацией данного подхода является седловая точка матричной игры, которая отражает состояние покоя динамического противостояния двух сторон. В системе, содержащей два объекта, проанализированы условия существования седловых точек в зависимости от уязвимости объектов, распределения ресурсов между ними, соотношение между ресурсами противоборствующих сторон. An optimization of resources allocation between information security objects is complicated due to the fact that the opposition occurs in uncertainty conditions when the opponent actions are unknown. First approach to solve this problem is the dynamic resources management in which protection reacts to the opponent’s actions effectively by changing the strategy after every opponent’s step. In some cases, the uncertainty causes difficulties in implementing the protection that makes the process of dynamic management impossible. Another approach is based on providing a guaranteed outcome when the allocation of protection resources is not optimal for all strategies of the opponent, but guarantees that, for any of its actions, the information loss will not exceed the defined value. The implementation of this approach is the matrix game saddle point, which reflects the dormancy state of the dynamic confrontation between two sides. The saddle point existence conditions are analyzed in a system of two objects depending on its vulnerability, resources allocation between them, and the conflicting sides resources ratio. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Методи аналізу та управління системами в умовах ризику і невизначеності Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки Графоаналитический метод поиска седловой точки в игровых задачах информационной безопасности A semigraphical method for saddle point calculation in information security playing problems Article published earlier |
| spellingShingle | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки Демчишин, М.В. Левченко, Є.Г. Рабчун, Д.І. Методи аналізу та управління системами в умовах ризику і невизначеності |
| title | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки |
| title_alt | Графоаналитический метод поиска седловой точки в игровых задачах информационной безопасности A semigraphical method for saddle point calculation in information security playing problems |
| title_full | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки |
| title_fullStr | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки |
| title_full_unstemmed | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки |
| title_short | Графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки |
| title_sort | графоаналітичний метод пошуку сідлової точки в ігрових задачах інформаційної безпеки |
| topic | Методи аналізу та управління системами в умовах ризику і невизначеності |
| topic_facet | Методи аналізу та управління системами в умовах ризику і невизначеності |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85556 |
| work_keys_str_mv | AT demčišinmv grafoanalítičniimetodpošukusídlovoítočkivígrovihzadačahínformacíinoíbezpeki AT levčenkoêg grafoanalítičniimetodpošukusídlovoítočkivígrovihzadačahínformacíinoíbezpeki AT rabčundí grafoanalítičniimetodpošukusídlovoítočkivígrovihzadačahínformacíinoíbezpeki AT demčišinmv grafoanalitičeskiimetodpoiskasedlovoitočkivigrovyhzadačahinformacionnoibezopasnosti AT levčenkoêg grafoanalitičeskiimetodpoiskasedlovoitočkivigrovyhzadačahinformacionnoibezopasnosti AT rabčundí grafoanalitičeskiimetodpoiskasedlovoitočkivigrovyhzadačahinformacionnoibezopasnosti AT demčišinmv asemigraphicalmethodforsaddlepointcalculationininformationsecurityplayingproblems AT levčenkoêg asemigraphicalmethodforsaddlepointcalculationininformationsecurityplayingproblems AT rabčundí asemigraphicalmethodforsaddlepointcalculationininformationsecurityplayingproblems |