Графы атак. Достижимость в графах

достижимости

нарушителя для достижения угроз (целей)
Топологический анализ защищенности сетей предполагает построение

графа атак на основе результатов сканирования сети, модели нарушителя и данных о конфигурации сети

В основном графы атак рассматриваются при анализе защищенности сетей.

enumeration graph –вершинам соответствуют тройки (s,d,a), где s – источник

атаки, d – цель атаки, a – элементарная атака

– элементарные атаки, приводящие к таким результатам
exploit dependency graph –

вершины соответствуют результатам атак, дуги отображают условия, необходимые для выполнения атаки и следствие атаки

может быть моделью организации, в которой люди представлены вершинами, а

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

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

рассчитываться между объектами сети, или между объектами сети и источниками

угроз. При расчете матрицы достижимости учитываются следующие особенности:
- динамическая маршрутизация : объект считается достижимым, если он достижим хотя бы по одному маршруту;
- возможность наличия нескольких оконечных точек для объекта (источника угроз) : угроза считается достижимой, если она достижима хотя бы на одной оконечной точке;
- при расчете матрицы учитываются возможности преобразования адресов источника и получателя (источника угроз и узла сети).

Граф атак может строиться в одном из следующих режимов:
- из одного объекта-источника атаки;
- конечного набора объектов-источников атаки

b: array [1..p,1..n] of real;
  c: array [1..m,1..n] of real;
 

s: Real;
  i, j, k: Integer;
begin
  ...
  for i:=1 to m do
    for j:=1 to n do begin
      s:=0; for k:=1 to p do
s:=s+e[i,k]*b[k,j];
      c[i,j]:=s;
    end;
  ...
end.

// b: array [1..p,1..n] of integer;
  c: array [1..m,1..m] of

integer;
  s: integer;
  i, j, k: Integer;
begin
  ...
  for i:=1 to m do
    for j:=1 to n do begin
      s:=0; for k:=1 to p do
s:=s+e[i,k]*e[k,j];
      c[i,j]:=s;
    end;
  ...
end.

которых в k-ом столбце стоит 0, копируем в новую матрицу.
3.

Строки с номером i, у которых в k-ом столбце стоит 1, объединяем с помощью операции ИЛИ с k-ой строкой, результат записываем в ту же новую матрицу.

E0. Следуя указаниям шага 2, скопируем строки матрицы Е0, в

первом столбце которой стоят 0:

В первом столбце единиц нет. Переходим к рассмотрению второго столбца и вычислению матрицы E2. Рассчитываем значения в строке 1-ой и 3-ей, выполняя дизъюнкцию k-ой строки (второй) со строками, у которых на k-ом месте стоит 1

у которых в 3-ем столбце 0: вторую и третью Рассчитываем

значения в строке 1-ой и 4-ой, выполняя дизъюнкцию k-ой строки (третьей) со строками, у которых на k-ом месте стоит 1. Получаем матрицу E3:

Вычисляем матрицу E4. Рассматриваем 4-ый столбец матрицы E3. Копируем строки, у которых в 4-ом столбце 0: вторую. Рассчитываем значения в строке 1-ой, 3-ей и 4-ой, выполняя дизъюнкцию k-ой строки (четвертой) со строками, у которых на k-ом месте стоит 1. Полученная матрица является матрицей достижимости – E*

1 to n
for i = 1 to n

for j = 1 to n
W[i,j] = min(W[i,j], W[i,k] + W[k,j])

Для нахождения матрицы достижимости оператор min заменяется дизъюнкцией, сложение заменяется конъюнкцией

for k = 1 to n
for i = 1 to n
for j = 1 to n
W[i,j] = W[i,j] or (W[i,k] and W[k,j])

№1.
источник угроз
вероятности реализации угроз
расстояние между узлами сети
стоимость СЗИ

узла графа сети

матрица достижимости:

целей атак из узла S
S-2-4 длина 7
S-5 длина 7
Аналогично

определим методом Дийкстры совокупные максимальные вероятности реализации угроз

S-2 вероятность 0,3
S-2-4 вероятность 0,18
S-5 вероятность 0,7

S-2 стоимость 7
S-2-4 стоимость 12
S-5 стоимость 9

Аналогично определим методом Дейкстры совокупную минимальную стоимость СЗИ узлов графа сети

АТАК

графа атак.
3. Какие виды графов атак вы знаете?
4. Определение матрицы

достижимости.
5. Определение матрицы контрдостижимости.
6. Опишите матричный способ нахождения матрицы достижимости.
7. Опишите алгоритм Флойда-Уоршелла.