Розділ 4. Застосування теорії графів в інформаційній безпеці

Постановка задачі: спроектувати захищену компютерну мережу, яка містить 14 компютерів. Відстані між компютерами вказані на графі. Необхідно визначити зв`язки цієї мережі. Зокрема:

- Виконати правильну нумерацію графу.

- Побудувати мінімальне дерево-остов.

- Визначити кількість шляхів від компютера 1 до компютера 14 та описати їх.

- Визначити та вказати найкоротші шляхи.

Темпи виробництва, його масштаби та спеціалізація окремих галузей, багатопрофільні звязки обумовлюють необхідність розробки ефективних методів планування та управління, які б давали можливість оцінити змінний стан системи та передбачити її майбутнє, щоб оптимізувати відповідний процес і керувати його перебігом. Системи обєктів дослідження разом зі звязками між ними називаються мережею. Графічне зображення множини досліджуваних обєктів і звязків між ними називається графом.

Граф доцільно зображати у вигляді діаграми. На діаграмі обєкти зображаються пронумерованими точками або кружками, які називаються вершинами, звязки між обєктами -відрізками ліній, які зєднують відповідні обєкти. Якщо звязок між двома обєктами А та В однобічний (від А до В є звязок, а зворотний звязок відсутній), то це зображається орієнтованим відрізком, стрілка якого відповідає напрямку звязку. Такий однобічний орієнтований відрізок називається дугою, а графічне зображення неорієнтованих попарних звязків між обєктами -ребрами (ситуація, коли обєкт А може бути повязаний з обєктом В і навпаки). Граф, вершини якого мають лише однобічний звязки, називається орієнтованим, або орграфом. Маємо такий граф компютерної мережі з вказаними відстанями між вершинами (комп`ютерами ). Виконаємо правильну нумерацію графа [12].

Рис. 4.1. Нумерація графа

Виконавши правильну нумерацію графа мережі, можна ефективно реалізувати алгоритм пошуку найкоротшого шляху між заданими вершинами. Реалізацію алгоритму приведено до побудови послідовності шляхів з однієї дуги, двох дуг, трьох дуг і т. д., які зєднують вершини певного рангу з кінцевою вершиною. При цьому перегляд вершин виконується в послідовності зменшення їх номерів. На кожному етапі алгоритму відбувається перехід від вершини більш високого рангу до вершини меншого рангу за умови, що із множини всіх шляхів, які починаються в одній і тій же вершині, необхідно залишити для наступного кроку реалізації алгоритму лише найкоротший шлях від цієї вершини до завершальної. За правильної нумерації вершин такий упорядкований перехід у послідовності зменшення рангів відбувається автоматично, навіть за умови, коли нумерацію рангів вершин опущено.

Нумерацію виконаємо у довільному порядку, але від 1-ї вершини наступною по порядку буде та вершина, шлях до якої найкоротший і позначимо цю вершину 2, а всі інші нумеруємо довільно.

Рис. 4.2. Довільна нумерація вершин

При побудові графу планування захищеної мережі необхідно дотримуватися певних правил, щоб у подальшому можна було досліджувати його.

1. Граф планування захищеної мережі не повинен мати "глухих кутів", тобто подій, з яких не виходить жодної роботи, окрім завершальної події. Поява "глухих кутів" подій свідчить про не досить ретельно виконаний аналіз взаємозвязків.

2. На графові не може бути "хвостових" подій (окрім вихідної події), тобто подій, яким не передує жодна робота. Такою "хвостовою"подією є подія яка не може відбутися, отже, не можуть відбутися і наступні події.

3. Граф не може мати замкнутих контурів і петель, тобто шляхів, які зєднують певні події з ними ж. Поява замкнутих контурів вимагає перегляду складу робіт та їх взаємозвязків, після змістовного аналізу яких завжди зявляється можливість уникнути замкнутих контурів і петель.

4. На графові планування захищеної мережі повинна бути лише одна вихідна та лише одна завершальна подія [13].

Під час проектування залізниць,компютерних мереж, ліній електропередач та інших ліній комунікації виникають проблеми побудови мережі з мінімальними витратами. Теоретично таке завдання успішно вирішується через побудову мінімального остовного дерева. Це завдання має низку методів рішення.

Інтерфейс програми має бути таким. Спочатку користувач вводить порядок графа, щоб програма могла сформувати таблицю введення даних (матриця терезів) з певним кількістю рядків і шпальт. Далі програма створює якийсь масивa [14] [14] (передбачається, що кількість вершин графа менше, або рівне 14). Цей масив ініціалізується: кожному a[i] [j] присвоюється 100 (передбачається, що максимальна довжина ребра менше 100). Потім дані з таблиці введення копіюються в масив. У осередку таблиці щось міститься у масив щось копіюється. Потім робиться цикл, який переривається тільки тоді, коли всі елементи масиву стануть знову рівні 100. Як працює цикл? Спочатку перебуває мінімальний елемент масиву (в галузі вище головною діагоналі матриці введення). Він запамятовується (змінна buf) і його присвоюється 100. Відповідно до алгоритму Прима, якщо ребро підходить мінімальний елемент викреслюється, а цикл починається з початку. Підходяще ребро чи ні? Складається масив з n елементів. Кожен елемент дорівнює 1 чи 0. Коли вершина входить у дерево, в елемент масиву з її номером записується 1 (спочатку всі елементи масиву, крім першого рівні 0). Щоб визначити підходяще ребро чи ні, треба подивитися, чи містяться одиниці в масиві (номери елементів рівні номерам вершин ребра). Якщо номерам вершин ребра відповідають обидві одиниця, отже, ребро не підходить. Якщо це основна умова не виконується - ребро підходить. Алгоритм перестає працювати, коли всі вершини включені у новий граф.

Окремо можна назвати процедуру малювання графа. Програма створює двомірний масив координат вершин графа (>krug [2] [14]). Вершини розташовуються на окружності на рівній відстані друг від друга. Такий спосіб дуже зручний, бо не треба тривожитися, що ребра будуть нашаровуватися одне на інше.

Визначимо кількість можливих шляхів від компютера 1 до компютера 14 та опишемо їх.

Розглянувши всі можливі шляхи та знайшовши їх довжини бачимо що в нашому графі захищеної мережі є лише два найкоротших шляхи 1,2,6,9,8,12,14 та 1,3,6,9,8,12,14 довжина яких складає 19 одиниць.

Пошук найкоротшого шляху між заданими вершинами (компютерами) дає можливість визначити найкоротший шлях та найменшу відстань від довільної вершини графу, що в свою чергу дозволяє побудувати захищену компютерну мережу з мінімальними витратами.