Алгоритми синтезу оптимальної системи захисту інформації

A mathematical model of the dependence of the mean losses on safety violation in information/telecommunication systems with open architecture in the case of using non-absolutely reliable protection mechanisms was developed. The mathematical programming problem that emerges during synthesis of econom...

Full description

Saved in:

Bibliographic Details
Date:	2018
Main Authors:	Bonia, Yu. Yu., Novikov, О. М.
Format:	Article
Language:	Ukrainian
Published:	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018
Online Access:	https://journal.iasa.kpi.ua/article/view/127643
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	System research and information technologies
Download file:

Institution

System research and information technologies

_version_	1866302191413755904
author	Bonia, Yu. Yu. Novikov, О. М.
author_facet	Bonia, Yu. Yu. Novikov, О. М.
author_sort	Bonia, Yu. Yu.
baseUrl_str	http://journal.iasa.kpi.ua/oai
collection	OJS
datestamp_date	2018-04-11T11:11:15Z
description	A mathematical model of the dependence of the mean losses on safety violation in information/telecommunication systems with open architecture in the case of using non-absolutely reliable protection mechanisms was developed. The mathematical programming problem that emerges during synthesis of economically efficient protection system was defined. An algorithm for the integer separable programming problem solution was developed with the use of locally stochastic algorithms, and its efficiency and capacity for work were investigated. The use of this algorithm as a component of particularized computer aided desighn systems allows one to accelerate the synthesis of information protection systems with minimal total cost of protection mechanisms in information/telecommunication systems with open architecture.
first_indexed	2025-07-17T10:23:37Z
format	Article
fulltext	© Ю.Ю. Боня, О.М. Новіков, 2007 68 ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 TIДC ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ ТА МЕРЕЖІ УДК 681.3.06 АЛГОРИТМИ СИНТЕЗУ ОПТИМАЛЬНОЇ СИСТЕМИ ЗАХИСТУ ІНФОРМАЦІЇ Ю.Ю. БОНЯ, О.М. НОВІКОВ Розроблено математичну модель залежності середніх втрат при пору- шенні безпеки в інформаційно-телекомунікаційних системах з відкритою архітектурою для випадку використання не абсолютно надійних засобів захис- ту. Сформульовано задачу математичного програмування, яка виникає при синтезі економічно ефективної системи захисту. Розроблено алгоритм розв’язання задачі цілочисельного сепарабельного програмування з викори- станням локально-стохастичних алгоритмів. Проведено дослідження його пра- цездатності та ефективності. Використання розробленого алгоритму в якості складової спеціалізованих систем автоматизованого проектування дозволяє прискорити синтез систем захисту інформації з мінімальною вартістю за- собів захисту в інформаційно-телекомунікаційних системах з відкритою архітектурою. ВСТУП Проблема розробки формалізованих методик синтезу систем захисту інфор- мації (СЗІ) в інформаційно-телекомунікаційних системах (ІТС) з відкритою архітектурою є актуальною з ряду причин. Розповсюджуються технології систем з відкритою архітектурою, бракує методик аналізу ризиків, пов’язаних з успішною реалізацією загроз інформації. Такі методики стають все важливішими. Слабка формалізація відомих методик аналізу ризиків та синтезу СЗІ, оптимальних за певними критеріями, не дозволяє широко за- стосовувати автоматизовані системи проектування СЗІ. Подолати ці пере- шкоди допоможе розробка адекватної математичної моделі оцінки ризиків і супутні алгоритми та методики. Використання логіко-ймовірнісного математичного апарату, що засто- совувався при дослідженні безпеки структурно складних систем, дозволяє описувати порушення безпеки і в ІТС з відкритою архітектурою [1]. Якщо йдеться про розробку автоматизованої системи проектування СЗІ, то поряд з моделлю ризику, що виникає при реалізації загроз, слід також розглядати конкретну постановку задачі оптимізації. Відомі декілька постановок таких задач, які відрізняються видом обмежень та критеріїв оптимізації. Найваж- ливішими з них є мінімізація ймовірності порушення безпеки при накладан- ні обмежень на вартість засобів захисту та мінімізація вартості системи при Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 69 накладанні обмежень на величину ймовірності порушення чи величину ри- зику. Залежно від виду критеріїв та обмежень відповідна задача може бути використана для синтезу СЗІ в ІТС як державних структур, так і комерцій- них. Для останніх може бути характерним обмеження на бюджет витрат на СЗІ і мінімізація цих витрат. Для перших обмежуючим фактором є немож- ливість визначити втрати від реалізації загроз, оскільки їх матеріальний ви- раз не завжди можливий, а відомою є тільки ймовірність цих подій. У роботі [2] було запропоновано задачу математичного програмування, яка виникає при синтезі СЗІ із мінімальною вартістю в ІТС із відкритою ар- хітектурою за умови обмеження на величину залишкового ризику. Узагаль- нимо згадану задачу, ввівши до розгляду коефіцієнт ефективності 10 ≤≤ ijα i -го механізму захисту на j -му рівні стеку протоколів, та зробимо відпові- дні зміни у виразах для величини ризику. Враховуючи ту особливість відкритих систем, що реалізація засобу за- хисту на нижчому рівні стеку гарантує захист на всіх вищих рівнях, ймовір- ність порушення безпеки на рівнях стеку Wiii s ⊂},...,,{ 21 у результаті дії однієї загрози дорівнює ,)1()1( ),,min( 1},,{\},,{ ,, 1 11 1 ∏∏∏ =∈∈ −−= s sk k sk ks ii k k iiWi i iii iii qppP … …… … де },,2,1{ NW …= , N — кількість рівнів стеку протоколів; ip — ймовір- ність спричинення збитків на i -му рівні через реалізацію загрози; iq — ймовірність виключити негативну дію загрози на i -му рівні. Для стеку з N рівнями середні втрати від однієї загрози можуть бути отримані у вигляді ∑∑ ∑ == <<< ⊂ = s k i N s iii Wiii iii k s s s QPQ 11 ,,, ,,, 21 21 21 … … … , де коефіцієнт iQ — втрати від реалізації загрози на i -му рівні. Після спро- щень та підстановок вираз Q можна записати ∑ ∏ ∑∏ = = += − = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ +−−= N j j k N jk kkjkk j k kj QRQMRRQ 1 1 1 1 1 )1()1( α , (1) де зроблені позначення ii pR = та iii qM =α . Тут iR — ймовірність реалі- зації загрози на i -му рівні; sii αα = — коефіцієнт ефективності засобу за- хисту на i -му рівні стеку для деякої s -ї загрози, а бульова змінна iM ви- значає, чи реалізується механізм захисту на i -му рівні стеку. Через адитивність ризику перехід до випадку, коли розглядається L не- залежних загроз, проводимо шляхом додавання у співвідношенні (1) до змінних індексу i номера загрози та підсумування за цим індексом. Остаточний вигляд нової задачі математичного програмування буде та- ким: Ю.Ю. Боня, О.М. Новіков ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 70 ( ) { }⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ → ≤ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ +−− ∈= = = = = += − = ∑∑ ∑∑ ∏ ∑∏ ,min ,1)1( 1,01 1 max 1 1 1 1 1 1 ijM L i N j ijij L i N j j k N jk ikikijikik j k ikij CM RQRQMRR α (2) де ijR — ймовірність реалізації i -ї загрози на j -му рівні стеку; ijQ — ве- личина збитків при реалізації i -ї загрози на j -му рівні стеку; maxR — верх- ня границя втрат від порушення безпеки при реалізації L загроз; ijC — вар- тість реалізації i -го механізму захисту на j -му рівні стеку. ЕКВІВАЛЕНТНА ЗАДАЧА СЕПАРАБЕЛЬНОГО ПРОГРАМУВАННЯ У загальному випадку задачу (2) можна звести до еквівалентної задачі сепа- рабельного програмування. Для початку будемо кодувати комбінації меха- нізмів, які нейтралізують одну й ту саму i -ту загрозу у вигляді цілого числа ∑ = − −∈= N j N ij j i Mx 1 1 }12,,0{2 … . Тоді вирази для вартості системи і середніх втрат від порушення безпе- ки можна записати у вигляді ∑ = L i ii xF1 )( та ∑ = L i ii xG1 )( відповідно. Функ- ції iF , та iG задаються таблично та залежать від цілочисельної змінної ix неявним чином. Для їх обчислення необхідно декодувати значення змінної ix та підставити отримані бульові значення у відповідні вирази задачі (2) для фіксованого i . ( ) ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ −= ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ +−−= −== ∑ ∏ ∑∏ ∑ = = += − = = .12,,0 ,1)1()( ,12,,0,)( 1 1 1 1 1 1 N i N j j k N jk ikikijikik j k ikijii N i N j ijijii x QRQMRRxG xCMxF … … α Задача у цьому випадку має вигляд ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ≤∑∑ ==−∈ max 11}12,,0{ )()(min RxGxF L i ii L i ii x N i … (3) та може розв’язуватися за допомогою методу послідовного аналізу варіантів (ПАВ) [3] або з використанням методу вектора спаду для задачі сепарабель- ного програмування [4]. Слід відзначити, що також легко розглянути випадки, коли деякі ком- бінації змінних ijM для фіксованого i є забороненими (наприклад, коли Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 71 засіб не може бути реалізованим на певних рівнях стеку протоколів). У цьо- му випадку з усіх можливих N2 значень ix деякі потрібно відкинути, а ре- шту занумерувати наново. Отримана задача запишеться як ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ −<=≤′′ ∑∑ ==∈ 12},,,0{,)()(min max 11 N iii L i ii L i iiXx llXRxGxF ii … , де функції iF ′ та iG ′ задаються наново для всіх значень ii lx ,,0 …= , що за- лишилися. Окрім розглянутого вище загального випадку, коли ми не робимо ні- яких припущень щодо значень коефіцієнтів міцності засобів захисту та мо- жливих їх комбінацій, реалізованих на різних рівнях, існують ситуації, коли задача (2) стає лінійною. ЛІНЕАРИЗАЦІЯ ЗАДАЧІ Розглянемо ситуацію, коли для нейтралізації загрози обирається реалізація засобу захисту на єдиному рівні, або ми взагалі відмовляємося від його ви- користання. Для випадку абсолютно надійних засобів захисту тільки серед таких конфігурацій СЗІ слід шукати оптимальну, а всі ті, в яких реалізація засобу відбувається на двох і більше рівнях, мають більшу вартість при тому самому значенні ризику. У цьому випадку задача (2) насправді буде ліній- ною [2]. Із введенням неодиничних коефіцієнтів ефективності засобів захис- ту їх дублювання на різних рівнях стеку протоколів вже буде виправданим, і для приведення задачі (2) до лінійного вигляду необхідно примусово накла- сти обмеження на структуру СЗІ, тоді для i -ї загрози справджується ∑ = ≤n j ijM1 1 , Nn ≤≤1 , а разом з тим і ∏ ∑= = −=− n j n j ijijijij MM 1 11)1( αα , бо всі перехресні добутки зникають. Отже, у цьому випадку обмеження на значення середніх втрат буде лінійним. ≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ +−∑∑ ∑∑∏ = = +== − = L i N j N jk ikikij j k ikik j k ikij QRQMRR 1 1 11 1 1 )1( α max 1 1 1 1 1 )1( RQRQRR L i N j N jk ikikij j k ikij − ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ +−≥∑∑ ∑∏ = = += − = . Після накладання додаткового обмеження на структуру розв’язку і то- тожних перетворень вихідну задачу теж можна записати у лінійному вигля- ді. ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ −≥ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − =≤→ ∑∑∑∑ ∑ ∏ ∑∑∑ = == = = − = =∈= = .)1( ,,1,1,min max 1 11 1 1 1 1}1,0{1 1 RQRRQRM LiMCM L i N j ijij L i N j N jk j k ikikikijij N j ijM L i N j ijij ij α (4) Ю.Ю. Боня, О.М. Новіков ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 72 При покладанні всіх 1=ijα (тобто у випадку абсолютно надійних засо- бів захисту) задача (4) зводиться до задачі лінійного бульового програму- вання (ЛБП) з роботи [2]. Задачу (4) можна розв’язувати за допомогою точних методів бульового лінійного програмування (методу Балаша з вдосконаленням Джеофріона [5], методу ПАВ [3], Р-методу [6, 7] та ін.) і методів локальної оптимізації (ме- тоду вектора спаду, локально-стохастичних алгоритмів, методу керованого випадкового пошуку [6, 8]). Якщо задача (4) не розв’язується прямо, а відбувається перехід до екві- валентної задачі сепарабельного програмування, то функції iF , та iG з (3) виражаються наступним чином: ⎩ ⎨ ⎧ = −= = + ,,0 ,1,,0, )( 1, Nx NxC xF i ixi ii i … ( ) ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = −=−− = ∑ ∏∑∑ = =+= + = ,, ,1,,0,1 )( 1 11 1, 1 NxQR NxRQRQR xG i N j ijij i x k ik N xk ikikxi N j ijij ii i i i …α де значення змінної 1,,0 −= Nxi … відповідають використанню i -го засобу захисту на N,,1… -му рівнях стеку, а значення Nxi = — відмові від вико- ристання. РОЗВ’ЯЗАННЯ ЗАДАЧІ СЕПАРАБЕЛЬНОГО ПРОГРАМУВАННЯ ЗА ДОПОМОГОЮ ЛОКАЛЬНО-СТОХАСТИЧНИХ АЛГОРИТМІВ У роботі [2] для розв’язання задачі (3) запропоновано використати метод вектора спаду, що належить до класу методів локальної оптимізації. Окрім оригінального методу вектора спаду також існує ряд інших локально- стохастичних методів [8], тому пропонується використати їх ідеї для пода- льшого вдосконалення алгоритму розв’язання задачі. Важливу роль при ро- боті локально-стохастичних алгоритмів грає процедура генерування випад- кової перестановки, яка наводиться нижче. Алгоритм генерування випадкової перестановки αΠ 1. Формуємо початкову послідовність індексів ),,( 00 10 njjJ …= і зада- ємо деяке значення цілочисельного параметра α . 2. Покладаємо nk = . 3. За допомогою генератора псевдовипадкових чисел, рівномірно роз- поділених на інтервалі )1,0( , отримуємо випадкове число ξ і обчислюємо ]1)1[( +−= ki αξ . 4. Міняємо місцями i -й і k -й елементи послідовності knJ − , отримую- чи послідовність 1+−knJ . Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 73 5. Замінюємо k на 1−k і при 1>k переходимо до п.3, а при 1=k повертаємо випадкову перестановку 1−= nJJ . Якщо розглядати метод вектора спаду з радіусом околу 1=r , то всім змінним можна надати деякий пріоритет, який буде відображати їх «перспе- ктивність» з точки зору руху в напрямку збільшення (для задачі вигляду (3)). Евристичне правило для обчислення таких пріоритетних коефіцієнтів для j -ї змінної можна записати так: ))()1(())1()(( 0000 jjjjjjjjj xGxGxFxFv −++−= . Для випадку Nx j = 0 подальший рух є неможливим, тому ця змінна не враховується при обчисленні пріоритетних коефіцієнтів. Випадок =+ )1( 0 jj xG )( 0 jj xG= є нетиповим, бо зазвичай механізм, реалізований на більш висо- кому рівні стеку, забезпечує менший рівень захисту. Процедура αΠ має на меті зробити перебір напрямків зміни координат випадковим, не змінюючи суттєво порядок, що визначається за допомогою пріоритетних коефіцієнтів для відповідних змінних. Із збільшенням параме- тра α отримана перестановка J наближається до 0J , а при 1=α пріоритет не враховується взагалі і перестановка стає випадковою. Із врахуванням особливостей задачі алгоритм циклічного координатного підйому можна описати таким чином. Алгоритм циклічного координатного підйому 1. У якості початкового наближення 0x обираємо або нульовий вектор, або інший припустимий розв’язок задачі. Покладаємо 0=R і фіксуємо де- яке значення параметра α . 2. Обчислюємо за формулою −++−= )1(())1()(( 000 jjjjjjj xGxFxFv ))( 0 jj xG− пріоритетні коефіцієнти Ljv j ,,1, …= і будуємо адаптаційну послідовність ),,( 00 10 LjjJ …= таку, що 00 1 Ljj vv ≥≥… . Виключаємо з 0J всі індекси, які відповідають Nxi =0 (максимальному значенню змінної). Нехай кількість індексів після цієї процедури скоротилася з L до K . 3. За допомогою процедури αΠ генеруємо випадкову перестановку LKjjJ K ≤= ),,,( 1 … елементів послідовності 0J . 4. Виходимо з точки 0x та послідовно у порядку Kjj ,,1 … визначаємо координати припустимої точки з околу радіусу 1=r , що поліпшує значення цільової функції. 5. Покладаємо 1=h та 0xx = . 6. Якщо max)1()( RxGxGR hhhh jjjj ≤++− , то покладаємо −= RR )1()( ++− hhhh jjjj xGxG , 1+= hh jj xx . Ю.Ю. Боня, О.М. Новіков ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 74 7. Якщо Kh < , то замінюємо h на 1+h і переходимо до п.6. 8. Якщо 0xx ≠ , то покладаємо xx =0 і переходимо до п.2. Інакше по- кладаємо xx =∗ . 9. Повертаємо точку локального мінімуму ∗x цільової функції віднос- но околу радіусу 1=r . У роботі [8] також запропоновано алгоритм бікоординатного підйому, що є локально-стохастичним алгоритмом пошуку мінімуму в околі з радіу- сом 2=r . Для задачі, що розглядається, алгоритм бікоординатного підйому можна викласти у такому вигляді. Алгоритм бікоординатного підйому 1. За допомогою алгоритму циклічного координатного підйому знахо- димо точку x мінімуму цільової функції відносно околу одиничного радіу- су. Обчислюємо значення ∑ = = L i ii xGR 0 )( . 2. Розглянемо дві множини U та V , які визначаються таким чином: }\|{ NxiU i <= , }0\|{ >= ixiV . Позначимо \|\| UNU = і \|\| VNV = . 3. Формуємо множину Z , яка складається з трійок },,{ iii qfz , де )()( 1+−= iiii zzzzi xFxFf , ''+=iq для Uzi ∈ і )()( 1 iiii zzzzi xFxFf −= − , ''−=iq для Vzi ∈ . Впорядковуємо елементи множини Z за зростанням if . 4. Покладаємо xx = . 5. Покладаємо }''\|{min −== jqjl , }''\|{max +== jqjk . 6. Якщо lk < , то x є точкою мінімуму цільової функції відносно околу радіуса два, і робота припиняється. 7. Маємо lk > . Якщо lk zz = , то переходимо до п.9. 8. Якщо виконується −−+−++ )1()()1( llkkkk zzzzzz xGxGxGR max)( RxG ll zz <− , то покладаємо 1+= kk zz xx , 1−= ll zz xx і переходимо до п.2. Інакше — до наступного пункту. 9. Якщо ∅≠<+== },''\|{ kjqjW jU , то покладаємо jk UWj∈ = max і пере- ходимо до п.11. Інакше — до п.10. 10. Якщо ∅≠>−== },''\|{ ljqjW jV , то покладаємо jl VWj∈ = min , =k }''\|{max +== jqj і переходимо до п.11. Інакше — до п.12. 11. Якщо lk < , то переходимо до п.12. Інакше — до п.7. 12. Якщо xx = , то точка x є шуканою точкою локального мінімуму відносно околу радіуса два. Інакше за допомогою алгоритму циклічного ко- ординатного підйому, виходячи з точки x як початкової, знаходимо локаль- но-оптимальний розв’язок x′ . Якщо xx =′ , то x є шуканою точкою локаль- ного мінімуму відносно околу радіуса два. Інакше переходимо до п.2, покладаючи xx ′= . Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 75 ЗАСТОСУВАННЯ Р-МЕТОДУ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ БУЛЬОВОГО ПРОГРАМУВАННЯ Викладемо алгоритм розвязання задачі ЛБП (4), що виникає у процесі син- тезу оптимальної СЗІ, з використанням Р-методу. Зробимо позначення: ∏∑∑∑ − == +−+ = = + −−=−= 1 1 )1(,1 1 1 max1 )1(, j k ik N jk ikikijjNiL L i N j ijijL RQRaQRRb α , Ls sNkNs ab sks ,1, інакше,0 )1(,1 ,1 = ⎩ ⎨ ⎧ <<− == , ijjNiijjNi MxCc == +−+− )1()1( , . Тоді вихідна задача (4) може бути записана так: },,1),,,(,\|)({min 1}1,0{ LNjxxxbAxcxxJ LNx j …… ==≤= ∈ , де A — матриця ))1(( LNL ×+ ; xcb ,, — вектори розмірності LN , і розв’язана із використанням Р-методу [6, 7]. Цей метод відноситься до кла- су комбінаторних і полягає в тому, що всі значення вектора x неявно пере- бираються у порядку збільшення з точки зору лексикографічного впорядку- вання. При цьому безперспективні часткові розв’язки не добудовуються, що значно скорочує час пошуку. Для доведення несумісності підсистеми )1( +l -го порядку для частко- вого l -розв’язку ),,( 1 lxx … використовуються як вихідні нерівності задачі (4), так і одна штучна, в якій ми відображаємо наше знання про верхню гра- ницю значення цільової функції, відому на даний момент. До того моменту, коли ми не знайшли перший припустимий розв’язок, можна покласти ∞=∗J . Якщо ж ми знаходимо деякий повний припустимий розв’язок ),,( 1 LNxx ′′ … , то необхідно одразу покласти δ−′= ∑ = ∗ LN j jj xcJ 1 , де 0>δ , і для всіх припустимих векторів yx ≠ виконується δ≥− )()( yJxJ . Для об- числень із скінченною точністю величина δ завжди відома. Так, для цілих jc маємо ),,(НСД 1 LNcc …=δ . Для раціональних коефіцієнтів неважко отримати аналогічний вираз. У разі, якщо ми покладемо 0=δ , в результаті роботи алгоритму буде знайдено лексикографічно максимальний вектор з множини оптимальних розв’язків. Оскільки вектори перебираються у по- рядку їх лексикографічного зростання, то на це буде витрачатися додатко- вий час, що є небажаним. Особливості задачі дозволяють зробити певні спрощення. Так, у за- гальному випадку в алгоритмі використовуються дві множини jZ та jW , які заповнюються перед початком його роботи. Якби знаки та значення кое- фіцієнтів матриці A не були відомі наперед, то ми б мусили обчислювати та зберігати всі )2(2 +× LLN елементів множин jZ та jW . Насправді ж ми Ю.Ю. Боня, О.М. Новіков ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 76 знаємо, що в перших L нерівностях всі коефіцієнти є бульовими, а частина матриці A , яка відповідає за ці нерівності, має ту особливість, що в кожно- му її стовпці є лише одна одиниця, а в кожному рядку — рівно N одиниць. Для )1( +L -ї нерівності відомо: всі її коефіцієнти є від’ємними. Також відо- мо, що штучна )2( +L -га нерівність, яка використовується для відсіву за значенням цільової функції, має всі додатні коефіцієнти. Тому в нашому випадку для кожного },,1{ LNj …= множин jZ та jW можна записати ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ == ∑ = + LN jk kLjjj azzZ ,1\| , ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ==== ∑∑ = + = LN jk kjL LN jk ikijijj cwLiawwW ,1та,,,1,\| … . Як бачимо, для зберігання елементів множини jZ достатньо LN комі- рок, а для зберігання елементів множини jW — LN2 комірок (при цьому враховано, що ijw для Li ,,1…= повністю визначається N цілочисельними індексами, тому з усіх LN2 комірок половина завжди буде містити цілі чис- ла). Серед інших особливостей, за якими запропонований алгоритм відріз- няється від оригінального Р-методу, є умова, при виконанні якої ми робимо висновок про несумісність підсистеми )1( +l -го порядку для часткового l -розв’язку ),,( 1 lxx … . Відмінність полягає в тому, що деякі коефіцієнти множин jZ та jW відомі наперед, тому не зберігаються, і відповідні умови мають бути записані в явному вигляді. Нехай I — множина індексів, що складається з номерів тих обмежень, які можуть бути використані для доведення несумісності підсистеми )1( +l -го порядку для часткового l -розв’язку ),,( 1 lxx … . Якщо для підсис- теми l -го порядку ця множина невідома, то можна покласти =I )2,,1( += L… . В іншому ж випадку, коли переходимо від підсистеми l -го порядку до підсистеми )1( +l -го порядку (очевидно, що ми були вимушені зробити такий перехід через те, що спроби довести несумісність попере- дньої системи були невдалими), то з множини I можна вилучити деякі ін- декси. Оскільки при виконанні однієї з нерівностей 01 ,11 >−∑ = ++ l j jjLL xab , 1,11 ++= ∗ >−∑ lL l j jj wxcJ , (5) Lpwxab lp l j jpjp ,,1,1,1 …=>− +=∑ , для певного значення ILp ∈+= 2,,1… відповідна p -та нерівність задачі (в якості )2( +L -ї нерівності використовуємо штучне обмеження на значення цільової функції) ніколи не буде порушуватися при збільшенні l та довіль- Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 77 ному доповненні часткового l -розв’язку, то ми вилучаємо індекс p з мно- жини I . Таким чином, навіть якщо несумісність підсистеми )1( +l -го по- рядку не буде доведена, то при формуванні підсистеми )2( +l -го порядку до неї можна не включати нерівності з номерами, що були видалені з множи- ни I . Разом з тим нерівності з (5), які порушуються, можуть бути викорис- тані для доведення несумісності підсистеми )1( +l -го порядку для частково- го l -розв’язку ),,( 1 lxx … . Твердження 1. Якщо існує таке p , для якого порушується одна з не- рівностей (5) і справджується відповідна нерівність Lpxa l j jjp ,,1,1 1 , …=>∑ = , 1,, 1 1 , +=<− + = ∑ Lpzxab l l j jjpp , 2, 1 +=> ∗ = ∑ LpJxc l j jj , то підсистема )1( +l -го порядку для часткового l -розв’язку ),,( 1 lxx … є несумісною. Для збільшення швидкості роботи оригінального Р-методу його автори запропонували використовувати евристичне правило для впорядкування змінних. У нашому випадку воно має такий вигляд. 1. Для всіх LNjx j ,,1, …= знаходимо оцінку j L jL j c b a v ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ −= + + 1 1 ,1 . 2. Змінні впорядковуємо у порядку зростання оцінок jv , LNj ,,1…= . Алгоритм Р-методу 1. Покладаємо ∞=== ∗Jxxt LN ),0,,0(),,(,1 1 …… . 2. Якщо виконується ∑∑ = = ≤ L i N j ijij QRR 1 1 max , то переходимо до п.3. Інакше задача не має розв’язку, і робота алгоритму припиняється. 3. Змінюючи значення індексу l від t до 1−LN та перевіряючи умови теореми 1, знаходимо мінімальне l ′ , за якого підсистема )1( +′l -го порядку для часткового l ′ -розв’язку ),,( 1 lxx ′… є несумісною, і переходимо до п.4. Якщо ж такого l ′ не існує, то покладаємо 0=lx , 1,, −= LNtl … і переходи- мо до п.5. 4. Якщо всі компоненти часткового l ′ -розв’язку, що розглядається, дорівнюють 1, то припиняємо роботу алгоритму. При цьому останній припустимий розв’язок і буде оптимальним. Інакше будуємо новий Ю.Ю. Боня, О.М. Новіков ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 78 l ′′ -розв’язок за правилами: покладаємо }0},,1{\|{max =′∈=′′ jxljjl … та 1=′′lx , а для випадку ll ′′>′ ще і lljx j ′+′′== ,,1,0 … і переходимо до п.2. 5. Обчислюємо ∑ − = −= 1 1 LN j jijii xabD 1,,1 +=∀ Li … , −= ∗ + JDL 2 ∑ − = − 1 1 LN j jj xc . Якщо 0≥iD для всіх 2,,1 += Li … , то, покладаючи 0=LNx , отримуємо припустимий розв’язок ),,( 1 LNxx … початкової задачі і перехо- димо до п.7. 6. Покладаємо 1=LNx . Якщо 0, ≥− LNii aD 1,,1 +=∀ Li … та 02 ≥−+ LNL cD , то отримуємо припустимий розв’язок задачі і переходимо до п.7. Інакше покладаємо 1−=′ LNl і переходимо до п.4. 7. Після отримання першого припустимого розв’язку ),,( 1 LNxx ′′ … починається відсів розв’язків за значенням цільової функції. З цією ме- тою покладаємо δ−= ∑ = ∗ LN j jj xcJ 1 , де δ визначено раніше, та 1−=′ LNl і переходимо до п.4. ДОСЛІДЖЕННЯ РОЗРОБЛЕНИХ АЛГОРИТМІВ ТА ЇХ ПОРІВНЯЛЬНА ХАРАКТЕРИСТИКА Викладені вище локально-стохастичні алгоритми розв’язання задачі дискретного сепарабельного програмування (3) і Р-метод розв’язання задачі ЛБП (4) були запрограмовані мовою C# і їх ефективність досліджувалася на модельних прикладах з максимальною кількістю загроз 20=L та кількістю рівнів стеку протоколів 4=N . При розв’язанні задач ЛБП також робилося порівняння з ефективністю роботи алгоритмів Балаша з модифікаціями Джеофріона та методом вектора спаду, що були реалізовані мовою FОRTAN в бібліотеці чисельного аналізу НДОЦ МДУ [9] (відповідно до процедур MNR3R та MLC6R). Для точних методів Балаша та Р-методу ефективність виявилася недо- статньою, і задачі з кількістю бульових змінних 80=LN і 64=LN не були розв’язані у відведений час. Натомість наближені методи показали високу ефективність і достатню для практичних застосувань точність. Динаміку зміни вартості чергової припустимої конфігурації СЗІ у про- цесі роботи Р-методу можна прослідкувати на рис. 1. Часові характеристики згаданих алгоритмів наведені у таблиці. Час роботи методу вектора спаду при розв’язанні задачі ЛБП і алгоритму бікоординатного підйому при розв’язанні задачі сепарабельного програмування є поліноміальним (рис. 2). При розв’язанні одних і тих самих задач (або задач, записаних у еквіва- лентному вигляді) за допомогою різних алгоритмів були отримані такі ре- зультати. Оскільки задачі великої розмірності за допомогою точних методів розв’язувалися дуже повільно, то для порівняння використовувалася задача Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 79 розмірністю 60=LN (15 загроз). Метод Балаша, Р-метод знайшли точний розв’язок за порівняно малий час порядку 50 с. За допомогою наближених методів отримувався або той же глобальний мінімум (як для більшості задач ЛБП, що розв’язувалися за допомогою методу вектора спаду), або деякі ло- кальні мінімуми. Використана реалізація методу вектора спаду завжди починає пошук з нульового вектора, тому порівняння результатів його роботи для різних по- чаткових значень не проводилося. Для тих задач ЛБП, в яких метод вектора спаду не знайшов глобального мінімуму, значення критерію в точці локаль- ного мінімуму відрізнялося від оптимального на величину не більше 2,5%. Часові характеристики алгоритмів Час роботи алгоритмів Кількість загроз L MNR3R, с MLC6R, мс Р-метод, с Бікоординатний підйом, мс 10 0,0313 0,195 0,08 0,4995 11 0,1458 0,255 0,31 0,5715 12 0,3327 0,336 0,78 0,7309 13 0,5195 0,405 3,20 0,7985 14 1,526 0,508 11,53 0,9440 15 32,33 0,621 49,25 1,1275 16 – – 131 – 17 – – 465 – 18 – – 1879 – 19 – – 6215 – 20 – 1,305 – 2,0333 8500 9000 9500 10000 10500 11000 11500 12000 12500 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Номер припустимого розв'язку Зн ач ен ня к ри те рі ю J Рис. 1. Зміна значення критерію якості у процесі роботи Р-методу Ю.Ю. Боня, О.М. Новіков ISSN 1681–6048 System Research & Information Technologies, 2007, № 3 80 Алгоритм бікоординатного підйому починав пошук з випадкового век- тора, тому в більшості випадків він отримував різні локальні мінімуми. Че- рез високу швидкість алгоритму його можна запускати повторно. Конкретна кількість запусків з різних початкових точок може залежати від часу, який виділяється на розв’язання задачі. Значення відносних відхилень критерію від оптимального значення наведено на рис. 3. 0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2 2,2 10 11 12 13 14 15 16 17 18 19 20 Кількість загроз, штук Ч ас р оз в' яз ан ня з ад ач і, м с Задача бульового програмування Задача сепарабельного програмування Рис. 2. Залежність часу роботи наближених методів від розмірності задачі <3 3–6 6–9 9–12 12–15 15–18 18–21 21–24 24–27 27–30 30–33 33–36 >36 Відхилення локального мінімуму від глобального, % В ід со то к зн ач ен ь із за да ни м ін те рв ал ом в ід хи ле нь Рис. 3. Значення критерію в точках локальних мінімумів Алгоритми синтезу оптимальної системи захисту інформації Системні дослідження та інформаційні технології, 2007, № 3 81 ВИСНОВКИ Розроблено алгоритми синтезу СЗІ з мінімальною вартістю засобів захисту в ІТС з відкритою архітектурою. Розглянуто задачі математичного програму- вання, які виникають в процесі синтезу оптимальних СЗІ при врахуванні додаткових особливостей. Запропоновано алгоритм розв’язання задачі ціло- чисельного сепарабельного програмування з використанням локально- стохастичних алгоритмів. При порівнянні його з точним P-методом та мето- дом вектора спаду для розв’язання задачі ЛБП він показав кращі або рівні показники і може бути використаний як складова системи автоматизованого проектування СЗІ, оптимальної за економічним критерієм. Недостатня точ- ність розв’язання задачі сепарабельного програмування в порівнянні з зада- чею ЛБП нівелюється тим фактом, що в ній значно легше описати заборону певних комбінацій засобів захисту на різних рівнях стеку, як це часто буває на практиці. Всі розроблені алгоритми підтвердили свою працездатність і ефективність. Вони можуть бути використані при проектуванні реальних систем СЗІ, що задовольняють вимогам використання технології систем з відкритою архітектурою та для яких реально виконати чисельну оцінку ймовірнісних характеристик загроз безпеки і втрат від реалізації цих загроз. ЛІТЕРАТУРА 1. Новиков A., Тимошенко A. Построение логико-вероятностной модели защи- щенной компьютерной системы // Правове, нормативне та метрологічне за- безпечення системи захисту інформації в Україні. — 2001. — Вип. 3. — С. 101–105. 2. Боня Ю.Ю., Новиков А.Н. Синтез систем защиты информации с минимальной стоимостью механизмов защиты информации // Проблемы управления и информатики. — 2006. — №3. — С. 147–156. 3. Зайченко Ю.П. Исследование операций: Учебник. 6-е изд. — Киев: Слово, 2003. — 688 с. 4. Боня Ю.Ю., Новиков О.М. Синтез оптимальної системи захисту інформації на основі методу вектора спаду // Наук. вісті НТУУ «КПІ». — 2006. — № 4. — С. 107–112. 5. Geoffrion Arthur M. Integer Programming by Implicit Enumeration and Balas’ Method // SIAM Review. — 1967. — 9, № 2. — Р. 178–190. 6. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. — Киев: Наук. думка, 1985. — 384 c. 7. Артеменко В.І., Сергієнко І.В. Про метод розв’язування задач линійного про- грамування з бульовими змінними // Доп. АН УРСР. — 1980. — № 4. — Серія А. — С. 68–71. 8. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. — Киев: Наук. думка, 1980. — 276 c. 9. Систематический каталог библиотеки численного анализа НИВЦ МГУ. — http://srcc.msu.su/num anal/lib na/cat/cat0.htm. Надійшла 08.02.2007
id	journaliasakpiua-article-127643
institution	System research and information technologies
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T10:23:37Z
publishDate	2018
publisher	The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
record_format	ojs
resource_txt_mv	journaliasakpiua/50/691840b184e2d30995af34234cc0d850.pdf
spelling	journaliasakpiua-article-1276432018-04-11T11:11:15Z Algorithms for synthesis of optimal information protection system Алгоритмы синтеза оптимальной системы защиты информации Алгоритми синтезу оптимальної системи захисту інформації Bonia, Yu. Yu. Novikov, О. М. A mathematical model of the dependence of the mean losses on safety violation in information/telecommunication systems with open architecture in the case of using non-absolutely reliable protection mechanisms was developed. The mathematical programming problem that emerges during synthesis of economically efficient protection system was defined. An algorithm for the integer separable programming problem solution was developed with the use of locally stochastic algorithms, and its efficiency and capacity for work were investigated. The use of this algorithm as a component of particularized computer aided desighn systems allows one to accelerate the synthesis of information protection systems with minimal total cost of protection mechanisms in information/telecommunication systems with open architecture. Разработана математическая модель зависимости средних потерь при нарушении безопасности в информационно-телекоммуникационных системах с открытой архитектурой для случая использования не абсолютно надежных средств защиты. Сформулирована задача математического программирования, которая возникает при синтезе экономически эффективной системы защиты. Разработан алгоритм решения задачи целочисленного сепарабельного программирования с применением локально-стохастических алгоритмов. Проведено исследование его работоспособности и эффективности. Использование разработанного алгоритма в качестве составляющей специализированных систем автоматизированного проектирования позволяет ускорить синтез систем защиты информации с минимальной стоимостью средств защиты в информационно-телекоммуникационных системах с открытой архитектурой. Розроблено математичну модель залежності середніх втрат при порушенні безпеки в інформаційно-телекомунікаційних системах з відкритою архітектурою для випадку використання не абсолютно надійних засобів захисту. Сформульовано задачу математичного програмування, яка виникає при синтезі економічно ефективної системи захисту. Розроблено алгоритм розв’язання задачі цілочисельного сепарабельного програмування з використанням локально-стохастичних алгоритмів. Проведено дослідження його працездатності та ефективності. Використання розробленого алгоритму в якості складової спеціалізованих систем автоматизованого проектування дозволяє прискорити синтез систем захисту інформації з мінімальною вартістю засобів захисту в інформаційно-телекомунікаційних системах з відкритою архітектурою. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-04-02 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/127643 System research and information technologies; No. 3 (2007); 68-81 Системные исследования и информационные технологии; № 3 (2007); 68-81 Системні дослідження та інформаційні технології; № 3 (2007); 68-81 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/127643/122396 Copyright (c) 2021 System research and information technologies
spellingShingle	Bonia, Yu. Yu. Novikov, О. М. Алгоритми синтезу оптимальної системи захисту інформації
title	Алгоритми синтезу оптимальної системи захисту інформації
title_alt	Algorithms for synthesis of optimal information protection system Алгоритмы синтеза оптимальной системы защиты информации
title_full	Алгоритми синтезу оптимальної системи захисту інформації
title_fullStr	Алгоритми синтезу оптимальної системи захисту інформації
title_full_unstemmed	Алгоритми синтезу оптимальної системи захисту інформації
title_short	Алгоритми синтезу оптимальної системи захисту інформації
title_sort	алгоритми синтезу оптимальної системи захисту інформації
url	https://journal.iasa.kpi.ua/article/view/127643
work_keys_str_mv	AT boniayuyu algorithmsforsynthesisofoptimalinformationprotectionsystem AT novikovom algorithmsforsynthesisofoptimalinformationprotectionsystem AT boniayuyu algoritmysintezaoptimalʹnojsistemyzaŝityinformacii AT novikovom algoritmysintezaoptimalʹnojsistemyzaŝityinformacii AT boniayuyu algoritmisintezuoptimalʹnoísistemizahistuínformacíí AT novikovom algoritmisintezuoptimalʹnoísistemizahistuínformacíí

Алгоритми синтезу оптимальної системи захисту інформації

Institution

Similar Items