Построение матрицы достижимости и контрдостижимости — КиберПедия 

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...

Построение матрицы достижимости и контрдостижимости



Граф может быть моделью организации, в которой люди представлены вершинами, а дуги интерпретируют каналы связи. При рассмотрении такой модели можно поставить вопрос, может ли информация от одного лица хi быть передана другому лицу хj, т. е. существует ли путь, идущий от вершины хi к вершине хj. Если такой путь существует, то говорят, что вершина хj достижима из вершины хi. Можно интересоваться достижимостью вершины хj из вершины хi только на таких путях, длины которых не превосходят заданной величины или длина которых меньше наибольшего числа вершин в графе и т. д.

Достижимость в графе описывается матрицей достижимости R=[rij], i, j=1, 2, ... n, где n – число вершин графа, а каждый элемент определяется следующим образом:

rij=1, если вершина хj достижима из хi,

rij=0, в противном случае.

Множество вершин R(xi) графа G, достижимых из заданной вершины xi, состоит из таких элементов xj, для которых (i, j)-й элемент в матрице достижимостей равен 1. Очевидно, что все диагональные элементы в матрице R равны 1, поскольку каждая вершина достижима из себя самой путeм длины 0. Поскольку прямое отображение 1-го порядка Г+1(xi) является множеством таких вершин xj, которые достижимы из xi с использованием путей длины 1, то множество Г++1(xi)) = Г+2(xi) состоит из вершин, достижимых из xi с использованием путей длины 2. Аналогично Г+p(xi) является множеством вершин, которые достижимы из xi с помощью путей длины p.

Так как любая вершина графа, которая достижима из xi, должна быть достижима с использованием пути (или путей) длины 0 или 1, или 2, ..., или p, то множество вершин, достижимых для вершины xi, можно представить в виде

.

Множество достижимых вершин R(xi) представляет собой прямое транзитивное замыкание вершины xi, т. е. R (xi) = T+(xi). Следовательно, для построения матрицы достижимости находим достижимые множества R (xi) для всех вершин . Полагая, rij=1, если и rij=0 в противном случае.

Матрица достижимости имеет вид, как показано на рис.1,в. Матрицу достижимости можно построить по матрице смежности ( рис.1,б), формируя множество маршрутов из вершин с которой связана вершина xi непосредственно. Т.е в матрице достижимости в каждой строке xi ставится 1 напротив того узла xj, с которым узел xi связан неважно как или непосредственно или через другие узлы.

Матрица контрдостижимости (рис.1г). Q = [ qij], i, j =1, 2, ... n, где n – число вершин графа, определяется следующим образом:

qij=1, если из вершины xj можно достичь вершину xi ,

qij=0, в противном случае.

Контрдостижимым множеством Q (xi) является множество таких вершин, что из любой вершины этого множества можно достичь вершину xi . Аналогично построению достижимого множества R (xi) можно записать выражение для Q (xi):



.

Другими словами – в матрице контрдостижимости в каждом столбце xj ставится 1 напротив того узла xi, с которым узел xj связан неважно как или непосредственно или через другие узлы.

 

 

Рисунок 1Б. – Граф сети (1а) и описывающие его матрицы

1б – матрица смежности; 1в – матрица достижимости; 1г – матрица контрдостижимости.

 

 

Построения графа атак на основе графа сети и матрицы достижимости (рис.1в)

 

1. По условию задачи источник атак воздействует на сеть из узла S – узла №1. Определим методом Дейкстры кратчайшие маршруты до узлов достижимости сети – целей атак из узла S. Для этого построим таблицу 1, где столбцы – номера узлов графа сети, строки – номер шага алгоритма Дейкстры. Согласно алгоритма при определении кратчайших маршрутов до целей:

– на первом шаге всем узлам графа присваивается «вес» ¥ (бесконечно большое расстояние), а узлу источнику атак S вес равный 0.

– на втором шаге указываются узлы которые поменяли свой вес с «¥» до веса смежной с узлом S дуги исходящей из узла S;

– на третьем шаге и далее рассматриваются только узлы графа сети, изменившие свой вес на предыдущем шаге;

– действия продолжаются от узла S до посещения всех узлов согласно матрицы достижимости.

– веса узлов графа сети на последнем шаге и есть минимальное расстояние до цели атаки от узла S.

– сам кратчайший путь определяется действиями в обратном направлении: указывается конечный узел цели, далее на маршруте указывается узел при рассмотрении которого конечный узел поменял свой вес и т.д. на маршруте кратчайшего пути указываются все узлы до узла S включительно.

Покажем действия согласно 2.1 для рассматриваемого примера в таблице 1



Таблица 1

№ шага S
¥ ¥ ¥ ¥ ¥ ¥
¥ ¥ ¥ ¥
­– ¥ ­– ¥ ¥
¥ ¥ ¥

Примечание: В отличие от других алгоритмов определения кратчайших маршрутов (Форда-Беллмана, Флойда-Уоршола) в алгоритме Дейкстры вес узла графа на очередном шаге рассматривается один раз. В таблице 1 факт окончания просмотра узла показан «–».

Все кратчайшие маршруты до целей атак из узла S определяются: S 2 4

S 5

(стрелки показывают ход рассуждений при определении маршрута по таблице 1).

Минимальная протяженность обеих маршрутов до узлов 4 и 5 составила 7 условных единиц.

 

2. Аналогично определим методом Дейкстры совокупные максимальные вероятности реализации угроз достижимых узлов графа сети от источника атак S (Таблица 2), т.е. решаем задачу на максимум.

Таблица 2

№ шага S
0,3 0,7
­– 0,18

 

Маршруты воздействия угроз аналогичные маршрутам в п.2.1 S – 2 – 4

S – 5

Максимальная вероятности реализации угроз до узлов составила: до узла 2 – 0,3, до узла 4 – 0,18, до узла 5– 0,7.

 

3. Аналогично определим методом Дейкстры совокупную минимальную стоимость СЗИ узлов графа сети до целей атак из узла S (Таблица 3), т.е. решаем задачу опять на минимум. В этом случае мы принимаем условие – чем меньше стоимость СЗИ на узлах графа сети, тем больше вероятность у злоумышленников достичь своей цели за счет организованных атак на узлы сети.

Таблица 2

№ шага S
¥ ¥ ¥ ¥ ¥ ¥
¥ ¥ ¥ ¥
­– ¥ ­– ¥ ¥
¥ ¥ ¥

 

Маршруты воздействия угроз аналогичные маршрутам в п.2.1 S – 2 – 4

S – 5

Минимальная совокупная стоимость СЗИ на маршрутах атаки составила: до узла 2 – 7, до узла 4 – 12, до узла 5 – 9 условных единиц.

 

4. Граф атак от узла S до узлов достижимости графа сети примет вид (рис. 2Б):

 

               
   
     
 
   
 
     
 

 


Рисунок 2Б. Граф атаки согласно графа представленного на рисунке 1а

 

Анализ графа атак (вывод по лабораторной работе №2):

При условии реализации угроз на сеть, исходящих от узла №1 (S) сети наибольшей уязвимостью обладает узел №5 графа сети, непосредственно связанный с источником угрозы и имеющий большую уязвимость (0,7). Наименьшей уязвимостью обладает узел №4 графа сети (0,18), имея при этом качественную систему защиты (10). Узлы 3,6,7 графа сети при реализации угрозы от источника S не пострадают т.к. находятся вне зоны достижимости.

 

 


Дополнительная информация из теории графов:

 

Пример построения матрицы смежности и матрицы инцидентности.

Матрица смежности всегда квадратная (по числу узлов). В матрице инциденций количество столбцов соответствует числу ребер. Для ориентированных ветвей (дуг) в матрице инциденций узел из которого дуга выходит помечается «-1», а узел куда дуга входит «1». Для более информативной матрицы инциденций можно вместо 1 (-1) ставить весовые характеристики ребер указанные на графе (2,3…).






Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...





© cyberpedia.su 2017 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав

0.011 с.