автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Вычисление показателей живучести информационных сетей на модели нестационарной гиперсети

На правах рукописи

ЮРГЕНСОН Анастасия Николаевна

ВЫЧИСЛЕНИЕ ПОКАЗАТЕЛЕЙ ЖИВУЧЕСТИ ИНФОРМАЦИОННЫХ СЕТЕЙ НА МОДЕЛИ НЕСТАЦИОНАРНОЙ ГИПЕРСЕТИ

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 2006

Работа выполнена в Новосибирском Государственном Университете.

Научный руководитель: доктор физико-математических наук,

профессор Попков Владимир Константинович Научный консультант: кандидат технических наук

Соколова Ольга Дмитриевна

Официальные оппоненты: доктор технических наук

Родионов Алексей Сергеевич

кандидат физико-математических наук Залюбовский Вячеслав Валерьевич

Ведущая организация: Вычислительный Центр РАН

(г. Москва)

Защита состоится 19 декабря 2006 г. в 10 часов на заседании диссертационного совета Д 003.061.02 при Институте Вычислительной Математики и Математической Геофизики СО РАН по адресу: 630090, Новосибирск, просп. Ак. Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки Института Вычислительной Математики и Математической Геофизики СО РАН.

Автореферат разослан 17 ноября 2006 г. П

Ученый секретарь / !\ и

диссертационного совета / //¡/[

д. ф.-м. н. / /у / / С.Б.Сорокин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Задачи анализа живучести сетей возникают в связи с исследованием устойчивой работоспособности сетей передачи данных при отказе их элементов, вызванных техногенными сбоями или целенаправленными разрушениями. Решение таких задач позволяет выявить узкие места сети, прогнозировать возможный ущерб до разрушений, и в дальнейшем укрепить или модернизировать сети, сводя к минимуму возможные потери.

Одним из универсальных параметров живучести, чувствительным к изменению состояния сети, является изменение величины информационного потока в сети (трафика). В связи с этим задача моделирования разрушающих информационных воздействий (РИВ) на сеть и выявление характерных, соответствующих данному воздействию, изменений потока в сети, становится одной из актуальных проблем информационной безопасности.

Цель работы заключается в моделировании работы сети на нестационарной гиперсети при разрушающих информационных воздействиях, распространяющихся во времени. Величина максимального потока исследуется как характеристика живучести сети. В качестве РИВ рассматривается последовательное уменьшение пропускной способности каналов первичной сети.

Для этого в диссертационной работе решаются следующие задачи:

• создание теоретической базы для работы с понятием максимального потока и минимального разреза с гиперсетях;

• создание методов и алгоритмов поиска величины максимального потока в стационарных и нестационарных гиперсетях;

• моделирование процесса распространения РИВ в нестационарной гиперсети;

• проведение численных экспериментов.

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

Научная новизна работы состоит в следующем:

• Изложенные теоретические результаты показывают, что при работе с гиперсетями нужна особая методика и особые алгоритмы, отличные от общеизвестных, опирающихся на теорию Форда-Фалкерсона.

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

• Разработаны оригинальная методика моделирования РИВ на нестационарных гиперсетях и алгоритмы поиска оптимальных маршрутов распространения атак в гиперсетях.

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

Основные положения, выносимые на защиту:

1. Теоретические результаты (доказательство теорем) для величин максимального потока и минимального разреза в гиперсетях.

2. Приближенные алгоритмы поиска максимального потока в гиперсетях.

3. Метод поиска простой цепи с наибольшей пропускной способностью в нестационарной гиперсети.

4. Методика моделирования РИВ, распространяющихся во вре-. ; . мени, на модели нестационарной гиперсети. Алгоритмы по.., ■ иска оптимальных маршрутов распространения атак "с возвращением ресурса" и "без возвращения ресурса" в нестационарной гиперсети.

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

Апробация работы. Основные научные результаты диссертации докладывались и обсуждались на семинаре "Моделирование инфо-коммуникационных систем" под руководством д.ф.-м.н. В.К. Попкова, на 1-й международной азиатской школе-семинаре "Проблемы оптимизации сложных систем" (Новосибирск,19 - 26 июня 2005 г.,), на международной научно-практической конференции "Связь - 2004", (г.Бишкек, Киргизия, август 2004 г.), на конференции "Математика и безопасность информационных технологий" (Москва, МГУ, 28 - 29 октября 2004 г.), на международной конференции "Проблемы функционирования информационных сетей" (Новосибирск, 31 июля - 3 августа 2006 г.), на международной конференции "Вычислительные технологии в науке, технике и образовании" (Павлодар, Казахстан, сентябрь 2006 г.).

Кроме того, были сделаны доклады на конференциях молодых ученых ИВМиМГ (апрель 2004, апрель 2005, апрель 2006 г.).

Основные научные результаты диссертации опубликованы в 12 работах, список которых приведен в конце автореферата.

Структура и объем работы.

Диссертация состоит из введения, трех глав, заключения и списка литературы. Диссертация изложена на 97 страницах, включает библиографический список из 80 наименований работ, 44 рисунка, 2 таблицы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ '

Во введении обоснована актуальность темы диссертации, сформулирована цель диссертации и приведено краткое изложение полученных результатов.

В первой главе описываются многослойные модели информационных сетей, в том числе и модель гиперсети, позволяющая учитывать вторичную сеть, построенную на базе каналов первичной сети. •

Определение: Гиперсеть НБ — (X, V, Я; Р, .Р, IV) включает следующие объекты (рисунок 1): X = (жх,..., хп) - множество вершин-, V = (их, •.., Уд) - множество ветвей; К — (г1> • • • > 7*т) ~~ множество ребер-,

отображение Р определяет граф первичной сети РЗ = (X, У); отображение Ж определяет орграф вторичной сети ШБ = (X, Я); Р : Я -> ~ отображение сопоставляет каждому ребру г € Я множество .Р(г) его ветвей, образующих простой маршрут в гра-

каждой ветви Vj 6 V сопоставлена пропускная способность ветви а^ > 0;

каждому ребру Гк £ Я сопоставлена пропускная способность ребра > 0, такая что для всех ветвей £ Р(г^) верно <5^ < о.^

Далее в первой главе перечисляются методы исследования живучести сети и основные показатели живучести многослойных и однослойных сетей.

Рис. 1: Гиперсеть

фе РБ = (Х,У)\

Вторая глава посвящена теоретическим результатам для задачи поиска величины максимального потока между двумя выделенными вершинами в гиперсети.

Определение: (в—¿) поток в гиперсети НБ — (X, V, Я; Р, Р, IV) есть функция / : Я —> М+ со следующими ограничениями:

Угк е Я /Ы<4 (1)

£ /ы= £ /М (3)

Где 7г+ С Я множество ребер, входящих в вершину а^, а С Д множество ребер, исходящих из вершины ^.Условие (3) показывает, что поток, входящий в любую вершину (исключая вершины б- и £) равен исходящему потоку из оной.

Задача о поиске максимального потока: Найти величину ¡р максимального (д — ¿) потока, где

(р = тах Цгк)

Пусть НБ = (.Х", V, И; Р, Р, У/) - гиперсеть. Обозначим минимальный (в—Ь) разрез сетей РБ и МТБ соответственно МтСЫ(РБ) и МтСиЬ(\¥Б) (величину соответствующего минимального разреза \МтСЫ{РБ)\ и \МтСЫ(\¥Б)\).

Определение: Минимальным (в — £) разрезом гиперсети IIБ будем называть величину ,

\МтСЫ(НБ)\ = тт{\МтСЫ(РБ)\, \МтСиг{\УБ)\)

В диссертационной работе показано, что теорема Форда-Фалкер-сона о равенстве величин максимального потока и минимального разреза в графах, не верна в гиперсетях. В частности отмечено, что величина максимального потока не превосходит величины минимального разреза гиперсети. Для некоторых видов гиперсетей

молено найти нижние оценки величины максимального (s — t) потока.

Пусть HS = (X, V, R; Р, F, W) - гиперсеть, s и t - выделенные вершины, ц> - максимальный (s — t) поток.

Теорема 1 Пусть HS' = (А', V', R'\Р', F, W') гиперсеть: WS' С WS, в которой каждое ребро используется для передани максимального потока;

PS' С PS, Vj е PS' о 3rk G WS' : vj € F(rk).

Если в гиперсети HS' для каждой ветви Vj G F(rk) верно ¿jt = Qj, к = 1,..., |Д|, тогда существует MinCut(PS') минимальный разрез первичной сети PS', все ветви которого насыщены (то есть неравенство (2) превращается в равенство для ветвей минимального разреза), при этом \MinCut{HS')\ = \MinCut(PS')\

Теорема 2 Пусть HS' - сужение гиперсети HS, определенное в Теореме 1. Пропускные способности всех ребер и ветвей в IIS' равны С. Тогда для величины максимального (s — t) потока в гиперсети IIS' верно следующее:

где п - число вершин в гиперсети.

Также в работе приведено доказательство МР-полноты целочисленной задачи поиска максимального потока в гиперсети.

Далее описаны приближенные алгоритмы для решения задачи поиска максимального потока в гиперсети. Было предложено несколько подходов:

• модификация алгоритма Форда-Фалкерсона,

• построение и-цепей,

• построение простых цепей. .

• комбинация трех первых методов.

Для модифицированного алгоритма Форда-Фалкерсона доказаны 2 теоремы, дающие нижние оценки величины потока в гиперсетях специального вида.

Под дополняющим путем будем понимать (s — t) путь во вторичной сети WS не нулевой пропускной способности.

Теорема 3 Пусть HS = (X, V, R; Р, F, W) - гиперсетъ, в которой пропускные способности всех ребер и ветвей равны. Пусть максимальный поток величины <р образован к дополняющими путями (к > 2), причем каждый дополняющий путь не проходит по одной и той otee ветви несколько раз. Тогда поток <pff, найденный модифицированным алгоритмом, удовлетворяет неравенству

VFF > £¥>■

Теорема 4 Пусть HS - гиперсетъ, в которой пропускные способности всех ребер и ветвей равны. Если ни один дополняющий (s — t) путь в гиперсети не имеет общую ветвь с другими дополняющими путями, то найденный модифицированным алгоритмом поток <pff удовлетворяет следующему неравенству

<р

-г < <PFF < V,

п — 1

где ¡р - максимальный поток, п - число вершин в гиперсети

Из теоремы 3 следует, что модифицированный алгоритм Форда-Фалкерсона, основанный на стратегии "посылать как можно больший поток по найденному дополняющему пути", не всегда приводит к максимальному потоку.

Из теоремы 4 следует, что при построении потока необходимо учитывать топологию первичную сеть PS. Для этого использованы понятия v— цепи и простой цепи, введенные В.К. Попковым.

Определение: Маршрут (гго, ri, xj,..., r^a?*) в гиперсети HS называется v-цепью, если каждая ветвь используется не более одного раза.

Определение: Маршрут (жо, rj, xi,..., r^, Xfc) в гиперсети HS называется простой цепью, если каждая вершина встречается не более одного раза.

Основная идея алгоритмов: Построить и-цепи (или простые цепи) и использовать их .в качестве дополняющих (а — ¿) путей при построении потока.

Основная идея комбинированного алгоритма: Построить простые цепи, гьцепи и использовать их в качестве дополняющих (в — £) путей при построении (в — £) потока. Затем в гиперсети с остаточными пропускными способностями ветвей и ребер построить добавочный поток модифицированным алгоритмом Форда-Фалкерсона.

Далее в работе описана программная реализация алгоритмов и приведены результаты численных экспериментов.

Таблица 1: Сравнение результатов работы алгоритм о в

Л» Мод. «-цепи Простые Комбинирован-

Ф-Ф цепи ный алгоритм

1 1,97 5,74 3,44 5,84

2 1,04 4,23 3,09 5,16

3 1,36 2,94 2,6 4,04

4 1,96 4,5 3,1 4,8

5 64,5 162,9 168,9 171

6 59,5 171,3 218,6 . 219,4

7 32,2 76,35 112,3 112,3

8 52,4 138,3 180,9 180,9

В таблице 1 приведено сравнение величин (з — Ь) потоков, найденных: модифицированным алгоритмом Форда-Фалкерсона, алгоритмом с поиском «-цепей, алгоритмом с поиском простых цепей, комбинированным алгоритмом. В качестве, тестовых примеров были сгенерированы случайные гиперсети с параметрами \Х\ = 20, \У\ = 30, |Д| = 100 для первых 4-х гиперсетей, |Я| = 500 для остальных. На каждом тестовом примере был вычислен максимальный поток для пяти случайных пар вершин, затем найдено среднее арифметическое значений потоков.

На рис. 2 приведены значения вычисленного потока для 20 случайных пар вершин з и 4 (тестовая гиперсеть сгенерирована случайно с параметрами: |Х| = 50, = 70, |Я| = 10000). Результат работы модифицированного алгоритма Форда-Фалкрсона

1 2 3 4.5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

| — г"К -»-у.дели -1-просты»цепи » комбинир. алг. |

Рис. 2: Сравнение результатов работы алгоритмов: Ф-Ф, г>-цепей, простых цепей и комбинированный алгоритм

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

Итак, в ходе численных экспериментов установлено, что для разных пар вершин лучший поток могут находить разные алгоритмы, но в среднем комбинированный алгоритм получает наибольший поток.

В конце главы в разделе Поиск простой (я — цепи с максимальной пропускной способностью в нестационарной гиперсети рассматривается задача поиска простых цепей в нестационарных гиперсетях.

Определение: Н3(т) — (X, V, Я; Р, Р, У/) нестационарная гиперсеть со следующими параметрами (т 6 [0,Г]): каждой вершине Х{ € X сопоставлена емкость вершины (буфер)

А > 0;

каждой ветви Vj 6 V сопоставлена функция пропускной способности ветви а-з(т) >0;

каждому ребру r^ S R сопоставлена функция пропускной способности ребра 5k{r) > 0 и тг > 0 - задержка передачи потока по ребру.

Постановка задачи: Найти в гиперсети HS простую (s — t) цепь р, такую что

min(ar( V^ ту)) —> max Vr6p z—'

Vr'6p\r

Vr€p

Под обозначением р\г будем понимать часть цепи р до ребра г. Поставленная задача является NP-полной

В диссертационной работе для решения задачи был использован метод ветвей и границ: в качестве допустимых решений рассматривались последовательности вершин {s,Х2, ■ ■ ■, жг}, каждому допустимому решению соответствовало множество простых цепей р — {s,r\,X2, • ■ • ,rn_i,a:j).

Приведены численные эксперименты для сравнения разных схем ветвления: базовый алгоритм (обычный метод ветвей и границ), Sort - базовый алгоритм ветвей и границ с сортировкой ребер по убыванию на этапе ветвления, Алгоритмы 1 и 2, для которых в операции ветвления участвует а) только к лучших цепей и ребер, Ь) к случайных цепей и ребер, где к - заданное число.

В таблице 2 приведены результаты работы алгоритмов на трех гиперсетях случайных гиперсетях с параметрами |Х| = 20, |V| = 100, |i2| = 500. Задержка передачи потока по ребру - случайное целое число из интервала [1,10]. Вершины sut выбирались случайно. Т = 20, к = 5.

Обозначения в таблице: max q - максимальная пропускная способность простой цепи, найденная алгоритмом, |П| - количество допустимых решений, построенных в процессе работы алгоритма (если количество допустимых решений превышало 1400, то алгоритм прекращал работу).

В примере 1 все алгоритмы нашли точное решение, но алгоритм 2 и сортировка завершают работу в несколько раз быстрее (по количеству построенных допустимых решений). Во втором

Таблица 2: Результаты численных экспериментов

Пример 1 Пример 2 Пример 3

Название |Oi| max q\ |fb| max <?2 |Пз| max 5з

Базовый 499 54.0 47 77.0 1401 2.0

Алгоритм1а 493 54.0 47 77.0 1401 2.0

Алгоритм1Ь 494 54.0 47 77.0 1401 2.0

Sort 74 54.0 26 74.0 44 100.0

Алгоритм2а 52 54.0 18 74.0 29 100.0

Алгоритм2Ь-1 39 54.0 25 50.0 588 100.0

Алгоритм2Ь-2 66 54.0 33 74.0 25 100.0

Алгоритм2Ь-3 133 54.0 47 77.0 33 100.0

примере те же алгоритмы дают лучший результат по быстроте, но найденный ими рекорд отличается от точного (точный рекорд нашли базовый и алгоритм 1). В третьем тестовом примере работа Алгоритма1 и базового алгоритма были остановлены, т.к. было достигнуто критическое значение |Г2| = 1400, но полученный рекорд намного хуже, чем рекорд, найденный Алгоритмом 2. Так как в алгоритме 2Ь присутствует выборка объектов с некоторой вероятностью, то для сравнения приведены три результата, найденные алгоритмом.

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

Третья глава посвящена моделированию разрушающих информационных воздействий, распространяющихся во времени, на модели нестационарной гиперсети.

Определение: (s—t) поток в нестационарной гиперсети HS(t) — (X, V, R; P,F, W) есть функция / : Rx [0,-Т] R+ со следующими ограничениями: .

Vr > 0, Vrfc € R fk(r)<Sk(r), Vvj е V £ /к(г)<сф)

rk€F-Hvj)._.

V* е х \ {м} | £ Мт) - £ /р(т)

<Р

В диссертационной работе сделан обзор нескольких методов сведения нестационарной гиперсети к стационарной. Выбран следующий метод сведения:

Пусть Т € Ъ. В каждый отрезок времени [р,р +1], р — О,... , Т будем считать гиперсеть стационарной с параметрами:

гр+1 грЧ-1

Щ е V а^ : — I ссз{т)с1т-, Угк Е К 5к / 5к{т)йт Лр ¿р

Итак, в каждый момент времени т = 1,... ,Т поток есть сумма трех потоков:

1. Поток (й — ¿), который считается по описанному в первом разделе модифицированному алгоритму Ф-Ф;

2. Поток из всех вершин (кроме в) в Ь (открытие буферов);

3. Поток из з во все вершины (кроме (заполнение буферов).

Моделирование атак на сеть осуществляется путем изменения пропускной способности первичной сети нестационарной гиперсети. Пусть э и í выделенные вершины гиперсети, у>(г) - максимальный (а — 4) поток в момент времени т. Под атакой будем понимать следующее: пусть "заражена" некоторая вершина х; в каждый момент времени атака переходит в любую смежную с х вершину по соответствующей, соединяющей их ветви первичной сети РБ; у этой ветви атака забирает часть пропускной способности (возможно всю).

Рассмотрено два крайних случая атак:

1. Атака, возвращающая на следующем шаге времени ресурс, забранный атакой у ветви (далее будем называть такую атаку "с возвращением ресурса");

2. Атака, не возвращающая на следующем шаге времени ресурс, забранный атакой у ветви (далее будем называть такую атаку "без возвращения ресурса").

Таким образом, под распространением атаки будем понимать маршрут в первичной сети, в котором каждое ребро подвергалось "атаке" (т.е. теряло часть пропускной способности) в соответствующий момент времени.

Постановка задачи: Найти оптимальный маршрут распространения атаки на первичную сеть PS, такой что

ip(r) —> min

т6[0,Т]

То есть минимизируется суммарный по всем моментам времени максимальный (s — t) ноток.

Для атаки "с возвращением ресурса" были построены точный и приближенный (если известна не вся информация о работе и структуре сети) алгоритмы, решающие поставленную задачу.

Для атаки "без возвращения ресурса" был построен приближенный алгоритмы (так как задача NP-полна), решающие поставленную задачу.

Суммарный поток Усредненный поток

1 2 Э 4 5 6 7 О 910 13 14 «И» Я 24 М И 30 |_нет 'одУ -4-опт > случ1 ^ СЛуч~2-j

Рис. 3: Результаты численных экспериментов

На рис. 3 приведены результаты численных экспериментов для атаки "с возвращением ресурса": простой линией показан максимальный поток в нормально функционирующей сети, линия с кружочками - максимальный поток при приближенной атаке, линия с крестом - оптимальная атака; остальные линии - случайно распространяющиеся атаки того же типа. Эксперимент проводился на случайной гиперсети: \Х\ = 300, |У| = 400, |Я| = 50000, Т = 30.

На оси абсцисс отмечены моменты времени, на оси ординат - величина потока. Левый график соответствует суммарному потоку (моменту времени т соответствует сумма потоков за все предыдущие моменты времени). Правый график соответствует усредненному потоку (моменту времени т соответствует сумма потоков за 10 предыдущих моментов времени).

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

Аналогичные результаты приведены для атаки 'без возвращения ресурса".

Далее в работе описана задача поиска оптимального минимального разреза.

В конце главы рассматривается задача моделирования РИВ на мобильные сети на модели нестационарной гиперсети.

Постановка задачи: Найти максимальный поток между выделенными вершинами s и t за период времени [0,Т], где в следующий момент времени в качестве вершин sut могут рассматриваться либо те же вершины, либо смежные с s u t вершины.

Для поиска приближенного значения максимального потока использовался алгоритм поиска потока по кратчайшим ребрам, с наибольшей пропускной способностью. Каждый дополняющий (5 — t) путь состоит из одного ребра из s в t.

Теорема 5 Пусть H S гиперсеть, sut выделенные вершины, - максимальный (s — t) поток:

где (р<1 - поток, образованный ребрами длины меньше I, - поток по ребру г^, длина которого 1епдШ(г^ > I. Если существует ребро гр+1 из в в t длины I, не участвующее в образовании максимального потока, но позволяющее пропустить поток /р+ъ та~ кой что

р

U+1 > mm{fi\length(ri) = I},

тогда поток ¡ра1, найденный алгоритмом, удовлетворяет следующему неравенству

Ч> > ¥>0,1 > Ч>-- 1)

В диссертационной работе приведены результаты численных экспериментов для величины максимального потока в гиперсети с различной топологией первичной сети. На первичную сеть Р5 воздействовали атаки двух типов.

В заключении представлены основные результаты, полученные в работе, и выводы.

• Получены теоретические результаты для величин максимального потока и минимального разреза. Показано, что теорема Форда-Фалкерсона о равенстве величин максимального потока и минимального разреза в графах, не верна в гиперсетях. Для некоторых видов гиперсетей получены соотношения между величинами максимального потока и минимального разреза.

• Доказана МР-полнота задачи поиска максимального потока в гиперсети.

• Предложены приближенные алгоритмы для решения задачи поиска максимального потока в гиперсети. Алгоритмы основаны на модификации алгоритма Форда-Фалкерсона, построении и-цепей, построении простых цепей и комбинации этих алгоритмов. Алгоритмы программно реализованы. На основе результатов численных экспериментов сделан вывод, что комбинированный алгоритм в среднем находит лучший поток.

• , • Для модифицированного алгоритма Форда-Фалкерсона по-

• лучены нижние оценки для величины потока, найденного алгоритмом, для гиперсетей специального вида.

• Построен алгоритм поиска простых цепей с наибольшей пропускной способностью в нестационарных гиперсетях на основе метода ветвей и границ.

• Разработана методика моделирования РИВ, распространяющихся во времени на модели нестационарной гиперсети. Построены алгоритмы поиска "оптимальных" атак "с возвращением ресурса" и "без возвращения ресурса".

Список литературы

[1] Величко В.В., Юргенсон А.Н. "Модели структурной надежности в мобильных сетях передачи данных"// ISSN 001357771 "Электросвязь" №3 С. 36-37, 2006 г.

[2] Соколова О. Д., Юргенсон А. Н. "О сведении одной проблемы мониторинга информационной сети к задаче в гиперсетях" // Вычислительные технологии, т.9. (Новосибирск) и Вестник КазНУ им. Аль-Фараби (Казахстан), Совместный выпуск, часть 3, 2004 г., - С. 47-52.

[3] Попков В.К., Соколова О.Д., Юргенсон А.Н. "О некоторых задачах анализа устойчивости работы информационных сетей" // Материалы конференции "Математика и безопасность информационных технологий" (Москва, МГУ, 28-29 октября 2004 года) - С. 326-331.

[4] В.К. Попков, А.Н. Юргенсон "Применение модели гиперсети к исследованию временных характеристик сетей свя-зи"//Материалы конференции МНПК "Связь - 2Ö04", Бишкек, Киргизия, С. 264-267

[5] Соколова О.Д., Юрошев A.B., Юргенсон А.Н. "Включение элементов принятия решений для задач проектирования информационных сетей"//Труды международной конференции "Вычислительные технологии в науке, технике и образовании". 2 том. - Павлодар: ТОО НПФ "Эко", 2006, С. 209-214

[6] Попков В.К., Соколова О .Д., Юргенсон А.Н. "Максимальный ' поток и минимальный разрез в гиперсетях"// Материалы 9-й

межд. конф. ПФИС-2006, Новосибирск - С. 242 - 246.

[7] Блукке В.П., Величко В.В., Попков В.К., Юргенсон А.Н. "Проблемы живучести сетей мобильной связи"// Новосибирск, 2005.-113 С.-(Препринт/РАН. Сиб. Отделение. ИВ-МиМГ; 1162)

[8] А.Н. Юргенсон "Моделирование информационных атак с помощью гиперсетей"// Материалы конференции молодых ученых ИВМиМГ (апрель 2004) - С. 257 - 266

[9] Юргенсон А.Н. "Поиск простой (s-t) цепи с максимальной пропускной способностью в нестационарной гиперсети"// Материалы конф. мол. ученых ИВМиМГ (апрель 2005) - С. 264274

[10] Величко В.В., Юргенсон А.Н. "Задача анализа структурной надежности мобильных сетей связи"// Труды ИВМиМГ серия Информатика 2005 - С. 58-65.

[11] Попков В.К., Соколова О.Д., Юргенсон А.Н., Юрошев A.B. "О некоторых подходах к решению задач анализа работы сетей передачи данных"// Труды ИВМиМГ серия Информатика 2005 - С. 111-116.

[12] Величко В.В., Попков В.К., Соколова О.Д.. Юргенсон А.Н. "Об одной задачи устойчивости мобильных сетей передачи данных"// Материалы международной научной конференции по проблемам безопасности и противодействия терроризму. Интеллектуальный центр МГУ. 2-3 ноября 2005г. - М: МЦН-МО, 2006. С. 300-304

Подписано в печать 9.11.2006г. Формат 60 х 841/16. Уч.-изд. л. 1 Тираж 100 экз. Заказ №532

Лицензия ЛР № 021285 от 6 мая 1998 г. Редакционно-издательский центр НГУ 630090, Новосибирск-90, ул. Пирогова, 2

Введение

Глава 1. Моделирование и задачи анализа живучести информационных сетей

1.1. О моделировании систем сетевой структуры гиперсетями

1.1.1. О многослойных моделях информационных сетей.

1.1 2. Математические модели многослойных сетей

1.1.3. Модель гиперсети.

1.2. Известные методы исследования живучести сетей связи

1.2.1. Понятия "устойчивости" и "живучести".

1.2.2. Методы анализа живучести.

1.2.3. Классификация основных структурных показателей живучести многослойных сетей.

Глава 2. Задачи поиска максимальных (в — Ь) потоков в гиперсетях

2.1. Максимальный поток и минимальный разрез в гиперсетях

2.1.1. Основные определения.

2.1.2. Соотношение максимального потока и минимального разреза в гиперсетях.

2.1.3. О сложности задачи поиска целочисленного максимального (в — ¿) потока в гиперсети

2.1.4. Выводы.

2.2. Алгоритмы поиска максимального (5 — ¿) потока в гиперсети

2.2.1. Алгоритм Форда - Фалкерсона (Ф-Ф).

2.2.2. Построение ^-цепей.

2.2.3. Построение простых цепей.

2.2.4. Численные результаты.

2.2.5. Выводы.

2.3. Поиск простой (в — ¿) цепи с максимальной пропускной способностью в нестационарной гиперсети

2.3.1. Постановка задачи

2.3.2. Классический метод ветвей и границ.

2.3.3. Метод ветвей и границ с частичным ветвлением.

2.3.4. Результаты численных экспериментов

2.3.5. Выводы.

Глава 3. Применение задачи поиска максимального (в — Ь) потока в нестационарной гиперсети для моделирования РИВ

3.1. О моделировании систем сетевой структуры нестационарными гиперсетями.

3.1.1. Методы сведения нестационарных сетей к стационарным моделям

3.2. Моделирование РИВ на сеть на модели нестационарной гиперсети

3.2.1. Моделирование РИВ распространяющихся во времени

3.2.2. Поиск оптимальной стратегии атаки.

3.2.3. Атака "с возвращением ресурса".

3.2.4. Атака "без возвращения ресурса".

3.2.5. Поиск минимального разреза для оптимальной атаки "без возвращения ресурса".

3.2.6. Выводы.

3.3. Максимальный поток в нестационарной гиперсети с мобильными абонентами.

3.3.1. Моделирование процесса атак на мобильные терминалы

3.3.2. Результаты численных экспериментов

3.3.3 Выводы.

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

Сложные механизмы взаимодействия между разными уровнями информационной сети и нетривиальность возникающих задач требует многослойной математической модели, способной описать протоколы и процессы, происходящие в реальных сетях. Действительно, сложность и высокая стоимость современных телекоммуникационных систем не позволяют основывать проектирование и формирование их архитектуры, выбор основных конструктивных параметров и оценку характеристик лишь на инженерной интуиции [60].

В процессе проектирования сетей также необходимо учитывать ряд параметров живучести и надежности. Это позволит выявить узкие места сети, прогнозировать возможный ущерб до разрушений и в дальнейшем укрепить или модернизировать сети, сводя к минимуму возможные потери, выбрать оптимальные параметры и строить рациональные стратегии управления

Стоит отметить, что современные информационные сети связи предполагают включение в свою структуру эффективных систем мониторинга, отслеживающих параметры состояния сети для обеспечения контроля и безопасности. Также мониторинг предполагает выявление различных неполадок или угроз вирусных атак. Существенная доля атак нацелена на максимальное потребление предоставляемых ресурсов с целью значительного ухудшения или прекращения предоставления услуг пользователям. Например, DDoS-атаки (Distributed Denial Of Service Attack) направлены на значительное увеличение трафика к атакуемому объекту (обычно атакуемыми ресурсами являются: ширина канала, процессорное время серверов и роутеров, конкретные реализации протоколов) [15].

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

Одним из универсальных параметров, чувствительным к изменению состояния сети, является отслеживание изменений величины информационного потока в сети (трафика). В связи с этим задача моделирования разрушающих информационных воздействий (РИВ) на сеть и выявление характерных, соответствующих данному воздействию, изменений потока в сети является одной из актуальных проблем информационной безопасности.

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

Цель работы заключается в моделировании работы сети с помощью нестационарной гиперсети при разрушающих информационных воздействиях, распространяющихся во времени. Величина максимального потока рассматривается как характеристика живучести сети. В качестве РИВ рассматривается последовательное уменьшение пропускной способности каналов первичной сети. Для этого в диссертационной работе решаются следующие задачи:

• создание теоретической базы для работы с понятием максимального потока и минимального разреза в гиперсетях;

• создание методов и алгоритмов поиска величины максимального потока в стационарных и нестационарных гиперсетях;

• моделирование процесса распространения РИВ в нестационарной гиперсети;

• проведение численных экспериментов. Структура работы

Материал диссертации состоит из трех глав и организован следующим образом:

В Главе 1 описываются многослойные модели информационных сетей. В частности, описана модель гиперсети, позволяющая учитывать вторичную сеть, построенную на базе каналов первичной сети. Гиперсеть [62] более адекватно чем граф описывает сложность и иерархичность современных сетей.

Далее рассматриваются методы исследования живучести сети. Перечисляются основные показатели живучести многослойных и однослойных сетей

Глава 2 посвящена теоретическим результатам для задачи поиска величины максимального потока между двумя выделенными вершинами в гиперсети. Введено понятие минимального разреза. Показано, что теорема Форда-Фалкерсона о равенстве величин максимального потока и минимального разреза в графах не верна в гиперсетях. Для некоторых видов гиперсетей получены соотношения между величинами максимального потока и минимального разреза в гиперсетях. Также дано доказательство МР-полноты задачи поиска максимального потока в гиперсети.

Далее описаны приближенные алгоритмы для решения задачи поиска максимального потока в гиперсети. Было предложено несколько подходов:

• модификация алгоритма Форда-Фалкерсона,

• построение ?/-цепей,

• построение простых цепей.

• комбинация трех первых методов.

Для модифицированного алгоритма Форда-Фалкерсона доказаны 2 теоремы, дающие нижние оценки величины потока в гиперсетях специального вида. Также показано, что стратегия "посылать как можно больший поток по найденному дополняющему пути" не всегда приводит к максимальному потоку.

Далее в работе описана программная реализация алгоритмов и приведены результаты численных экспериментов для сравнения результатов работы алгоритмов. Отмечено, что комбинированный алгоритм в среднем позволяет найти лучший поток, чем остальные приближенные алгоритмы.

В конце главы рассмотрена задача поиска простых цепей в нестационарных гиперсетях. Для ее решения использован метод ветвей и границ. Приведены результаты численных экспериментов для сравнения разных алгоритмов ветвления.

Глава 3 посвящена моделированию разрушающих информационных воздействий (РИВ), распространяющихся во времени, на модели нестационарной гиперсети. Сделан обзор нескольких методов сведения нестационарной гиперсети к стационарной. Для оценки живучести и поиска нижних границ параметров живучести рассмотрена задача построения "оптимальных" атак, минимизирующих максимальный поток за некоторый период времени. Алгоритм построения оптимальных атак был описан для двух крайних случаев: для атаки "с возвращением ресурса" и "без возвращения ресурса" Приведены результаты численных экспериментов для сравнения разрушающих воздействий атак построенных оптимально и случайно.

В конце главы рассмотрена задача моделирования РИВ на мобильные сети на модели нестационарной гиперсети. Приведены численные результаты для гиперсетей с различной топологией первичной сети.

Основные положения, выносимые на защиту

• Теоретические результаты (доказательство теорем) для величин максимального потока и минимального разреза в гиперсетях.

• Приближенные алгоритмы поиска максимального (б — ¿) потока в гиперсетях.

• Метод поиска простых цепей в нестационарной гиперсети.

• Методика моделирования РИВ, распространяющихся во времени, на модели гиперсети. Алгоритмы поиска оптимального маршрута распространения атак "с возвращением ресурса" и "без возвращения ресурса" в гиперсети.

• Методика моделирования РИВ, распространяющихся во времени, для мобильных сетей.

Научная новизна работы состоит в следующем:

• Изложенные теоретические результаты показывают, что при работе с гиперсетями нужна особая методика и особые алгоритмы, отличные от общеизвестных, опирающихся на теорию Форда-Фалкерсона.

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

• Разработаны оригинальная методика моделирования РИВ на нестационарных гиперсетях и алгоритмы поиска оптимальных маршрутов распространения атак в гиперсетях.

Апробация работы

Результаты работы докладывались на следующих конференциях:

• Конференции молодых ученых ИВМиМГ (2004-2006 гг.)

• Международная научно-практическая конференция "Связь - 2004", (Бишкек, Киргизия, август 2004г.)

• Конференция "Математика и безопасность информационных технологий" (Москва, МГУ, 28-29 октября 2004 года)

• Международная конференция "Проблемы функционирования информационных сетей" (Новосибирск, 31 июля - 3 августа 2006 г.)

• Международная конференция "Вычислительные технологии в науке, технике и образовании" (Павлодар, Казахстан, сентябрь 2006г.)

Основные результаты были опубликованы в журналах [43, 75], материалах конференций [42, 65, 64, 66, 68, 79] и трудах ИВМиМГ СО РАН [36, 42, 67].

Структура и объем диссертации

Диссертационная работа состоит из введения, трех глав, заключения. Она содержит 97 страниц машинописного текста, 2 таблицы. В библиографию включено 80 наименований.

3.2.6. Выводы

Сделан обзор нескольких методов сведения нестационарной гиперсети к стационарной. Наиболее оптимальным методом сведения для гипересетй большой размерности в данном случае оказался метод предполагающий, что в каждый момент времени гиперсеть стационарна (Метод 1).

Для оценки живучести и поиска нижних границ параметров живучести рассматривалась задача построения "оптимальных" атак (т.е. уменьшающие максимальный поток до минимума за некоторый период времени). Алгоритм построения оптимальных атак был описан для атак "с возвращением ресурса" и "без возвращения ресурса". Рассмотрена задача поиска оптимального минимального разреза.

Приведены результаты численных экспериментов для сравнения разрушающих воздействий атак построенных оптимально и случайно.

3.3. Максимальный поток в нестационарной гиперсети с мобильными абонентами

Как ранее уже упоминалось, нестационарная гиперстеь описывается характеристиками, изменяющими свое значение во времени (например, пропускная способность ветвей или ребер, задержка). Рассмотрим еще один случай нестационарного поведения, когда изменяются выделенные вершины зиЬ. В качестве примера такой сети, можно привести беспроводные локальные сети (Wireless Local Area Network) или мобильные сети, где терминалы (абоненты) переходят из зоны действия одной базовой станции к другой.

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

Проблема усложняется еще тем, что базовые станции могут быть выведены из строя различными способами. Например: физическое уничтожение, включение широкополосной помехи, вывод некоторых каналов из строя узкополосной радио помехой. Кроме того, современные сети мобильной связи могут быть атакованы разрушающими информационными воздействиями (РИВ).

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

Вершин гиперсети х € X будут выступать в качестве базовых станций; множество ветвей V ~ линии связи, соединяющие базовые станции; множество ребер R - виртуальные каналы, по которым производится передача информации между терминалами.

Процедура перехода: В каждый момент времени базовая станция может передать терминал соседней базовой станции (в случае перехода терминала в зону действия другой станции).

Постановка задачи: Найти максимальный поток за период времени [О, Т] между выделенными вершинами s и £, при условии, что выделенные вершины могут изменяться.

Особенность задачи, в отличие от обычным систем передачи информации, состоит в том, что базовые станции выделяют для передачи информации (сеанса связи) какой-то канал (ребро). То есть для поиска максимального (s — ¿)потока нужно использовать ребра с начальной вершиной s и с конечной вершиной t, а не (s — t) маршруты как в предыдущих разделах. В WLAN для поиска подходящего ребра (для передачи информации), чаще всего используется маршрутизация: по кратчайшему пути с подходящей пропускной способностью. Поэтому для поиска приближенного значения максимального потока будет использоваться алгоритм: поток по кратчайшим ребрам, с наибольшей пропускной способностью.

Теорема 3.1. Пусть H S гиперсеть, sut выделенные вершины, ip - максимальный (s - t) поток: где 1р<1 - поток образованный ребрами длины < I, /, - поток по ребру гг, длина которого 1епдИг(гг) > I. Если существует ребро гр+\ из в в £ длины I, неучаствующее в образовании максимального потока, но позволяющее пропустить поток /р+1, такой что

Тогда поток <ра1, найденный алгоритмом, удовлетворяет следующему неравенству у>уа1>4>- /р+1(тт {1,р} - 1)

Доказательство. Левая часть неравенства очевидна (т.к. - максимальный поток).

Величина потока, найденная алгоритмом, может быть меньше чем ср, т.к. алгоритм посылает поток по кратчайшим ребрам с наибольшей пропускной способностью и не может отследить случаи, когда ребро хотя и р fp+i > шт{/г|length(rt) = /} удовлетворяет требованиям, но ухудшает значение максимального потока. Пусть алгоритм использовал ребро гр+\ для построения потока. Найдем насколько уменьшились значения потоков по ребрам которые были присоединены позже чем rp+i.

Если ребро rp+1 инцидентно ветви одного или нескольких из ребер г* (к = 1 ,.,р) (Рис. 3.10), то новые значения потока по ребрам гf'k > fk — fp+1- Ребро rp+1 может "испортить" I ветвей (т.к. длина ребра гр+\ равна /), поэтому ребро гр+\ может "испортить" не более min {1,р} потоков

Д. Тогда, поток найденный алгоритмом р р

Vai = 4><i + fp+1 + ^fl><P<i + fp+1 + Yj h ~ fp+1 min (3"4)

1 i=i

Т.е. ip > ipai > V - /p+i(min {l,p} — 1) что и требовалось доказать. поток по Гр+1

3.3.1. Моделирование процесса атак на мобильные терминалы

Разрушающие воздействия (атаки), приводящие к полной или частичной утрате сетью связи своих функций, можно разделить на два класса: случайные и направленные. Различия в причинах нарушения связи обусловливают существенные отличия в их проявлении, характере и масштабности нарушений связи, их продолжительности, путях и способах их устранения. Случайная атака приводит к нарушению лишь отдельных связей, подразумевает незнание атакующим структуры и потоков в сети. Направленная атака предполагает наличие информации о функционировании сети, и на основе этих данных происходит направленное действие на узкие места.

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

Как было сказано выше, случайная атака предполагает отсутствие информации о структуре и функционировании сети. Рассмотрим два варианта такой атаки:

1. В гиперсети Нв есть несколько зараженных терминалов. В некоторый момент времени такой терминал посылает заявку базовой станции на передачу потока "ложной" информации. Базовая станция выделяет маршрут для передачи этого потока. Во всех ветвях первичной сети, по которым прошел маршрут, пропускная способность уменьшается на величину потока. Если заявка зараженного терминала велика, то поток может передаваться в течении нескольких тактов работы сети (зараженные терминалы и их корреспонденты могут перемещаться из зоны действия одной базовой станции в другую). Если поток передан, то занятая им пропускная способность освобождается.

2. В каждый момент времени атакующий забирает ресурс у случайной ветви (например, шум на частоте некоторой базовой станции). Забранный ресурс не освобождается в последующие такты работы.

Алгоритм направленной атаки:

1. на основе мониторинга сети на предыдущих тактах работы выявляются узкие места сети (в нашем случае находится ветвь первичной сети, по которой идет наибольший поток)

2. Посылается дополнительный поток некоторой величины по найденной ветви. Занятая им пропускная способность не освобождается в последующие такты работы.

3.3.2. Результаты численных экспериментов

В качестве примера работы модели мобильной сети рассмотрена нестационарная гиперсеть с числом базовых станций - 20. В качестве первичной сети рассматривались графы различной топологии: дерево, цикл, цикл с хордами, решетка. Вторичная сеть - случайный граф. На графиках показаны

No - Максимальный (s — £)поток в сети без атак (простая линия); attack 1 - Максимальный (s — t)поток в сети при случайной атаке, образованной множеством "зараженных" абонентов. В каждый момент времени ложный поток могут отправить не более 10 терминалов (линия с кругами). attack2 - Максимальный (s — ¿)поток в сети при направленной атаке (линия с крестами). attack3 - Максимальный (s—t)поток в сети при случайной атаке, забирающий некоторый ресурс у случайной ветви (линия с квадратами).

В скобках для каждой атаки указана величина забираемого у сети ресурса. На рис. 3.11-3.18 показаны поведение максимального потока, в гиперсетях с различными типами первичных сетей и неподвижными (стационарными) вершинами s и ¿.

На рис. 3.15 подробно показана ошибка алгоритма. Действительно, если первичная сеть - цикл с тремя хордами (рис. 3.15), то наибольший (10-20) поток дают три пути {10,9,8,., 1,20}, {10,11,., 20}, {10,20}. Но если атака ухудшила пропускную способность нескольких ветвей первичной сети, то возникнет случай, когда у пути {10,9,8,7,14,15,16,17,3,2,1,20} будет большая пропускная способность и алгоритм выберет именно этот путь и путь {10,20}. Хотя возможно суммарная пропускная способность отвергнутых путей больше, чем у выбранных.

На рис. 3.19 показано изменение максимального потока в гиперсети при нестационарных абонентах. Резкое понижение величины потока в центре

Максимальный поток г

-1.

13579 14 19 24 29 34 39 44 49 54 5963 68 73 78 83 88 93 98 t

No attack 1 (10) -4- attack 2 (10) -■- attack 3 (10) )

Рис. 3.11. Изменение макс.потока (первичная сеть - дерево) Максимальный поток

13579 14 19 24 29 34 39 44 49 54 5963 68 73 78 83 88 93 98 Wo attack 1 (10) -+- attack 2(10) -»- attack 3 (10) |

Рис. 3.12. Изменение макс потока (первичная сеть - цикл) графика при атаках обусловлено изначальным (простая линия на графике) подобным поведением величины максимального потока (например, узкое место).

Как видно из графиков, тактика атаки, основанная на информации о функционировании сети на предыдущих тактах работы, резко понижает качество обслуживания только в том случае, если абоненты работают по — Ыо -*- айаск 1 (10) -+- айаск 2 (10) -»- айаск 3 (10) |

Рис. 3.13. Изменение макс.потока (первичная сеть - цикл с двумя хордами)

Максимальный поток

Рис. 3.14. Изменение макс.потока (первичная сеть - цикл с тремя хордами)

Усредненный поток

8 000

3 000

4 000

7 000 6 000 5000

13 5 7 9 13 1 7 21 2529 33 37 41 45 49 53 57 61 65 69 73 7781 85 89 No -»-attack 1 (10) -ьattack2(10) -»-attack3(10) | некоторому расписанию. 3.3.3. Выводы

Мобильная сеть может моделироваться нестационарной гиперсетью, где подвижность абонентов моделируется потоком с изменяющимися во времени истоком и стоком. Рассмотрены возможные варианты воздействия на сеть с изменением пропускной способности ветвей.

Среди разрушающих воздействий (атак), приводящие к полной или

Максимальный поток

2 3 4 5 6 7 8 910 1 2 1 4 1 6 1 8 20 22 24 26 28 30

No attack 2 (10) -н attack 3 (10) J

Рис. 3.15. Погрешность алгоритма (первичная сеть - цикл с тремя хордами)

Максимальный поток

Максимальный поток

750

700

650

600

550 стттт—■-1

I ' AtUJL

1 >W"!'4i

It И I I \J . t I

I 11 I I H ( NI > j I I И I

1111 i 4 mi i i »i t i ill LUi I » I i I » II

I I I » I i I

II III II I I I I i > I I I I I I I I 1tf>M11 т> r r mi

- „ - - L . «I. . 1. J

13579 131721 2529 3337 41 4549 5357 61 6569 73 7781 8589 i1 4"1

123456789 12 15 18 21 24 2729 32 35 3840 43 4648

-No

-attack 2 (10)

-+- attack 3 (10) J

Рис. 3.16. Изменение макс.потока (первичная сеть - решетка)

Суммарный поток

Усредненный поток г

1 3 5 7 9 12151821 2427303336 394245485154 5760636669 — attack 1 (20) -+- attack 2 (20) -—attack 3(20) |

12 45 7 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60

No

Рис. 3.17. Изменение макс.потока (первичная сеть - цикл с хордами, вершины 5 и < перемещаются по расписанию)

Суммарный поток Усредненный поток

No —-attack 1 (20) -+-attack2(20) -»-attack3(20) 1

Рис. 3.18. Изменение макс.потока (первичная сеть - решетка, вершины s и i перемещаются по расписанию) — Но -*- attack 1 (40) -4- attack 2 (40) |

Рис. 3.19. Изменение макс потока (первичная сеть - цикл, вершины s и t перемещаются хаотично) частичной утрате сетью связи своих функций, рассматрены два класса: случайные и направленные. Для моделирования атаки в гиперсети введен дополнительный поток, который уменьшал полезную пропускную способность в линиях связи. Рассмотрено влияние атаки на качество обслуживания в сети, т.е. влияние атаки на величину максимального потока.

Из результатов численных экспериментов установлено, что тактика атаки, основанная на информации о функционировании сети на предыдущих тактах работы, резко понижает качество обслуживания только в том случае, если абоненты работают по некоторому расписанию.

Заключение

В диссертационной работе обоснована и решена задача моделирования РИВ, распространяющихся во времени на модели гиперсети.

Основными результатами работы являются:

• Получены теоретические результаты для величин максимального потока и минимального разреза. Показано, что теорема Форда-Фалкер-сона о равенстве величин максимального потока и минимального разреза в графах, не верна в гиперсетях. Для некоторых видов гиперсетей получены соотношения между величинами максимального потока и минимального разреза.

• Доказана ^-полнота задачи поиска максимального потока в гиперсети.

• Предложены приближенные алгоритмы для решения задачи поиска максимального потока в гиперсети. Алгоритмы основаны на модификации алгоритма Форда-Фалкерсона, построении г>-цепей, построении простых цепей и комбинации этих алгоритмов. Алгоритмы программно реализованы. На основе результатов численных экспериментов сделан вывод, что комбинированный алгоритм в среднем находит лучший поток.

• Для модифицированного алгоритма Форда-Фалкерсона получены нижние оценки для величины потока, найденного алгоритмом, для гиперсетей специального вида.

• Построен алгоритм поиска простых цепей с наибольшей пропускной способностью в нестационарных гиперсетях на основе метода ветвей и границ.

• Разработана методика моделирования РИВ, распространяющихся во времени на модели нестационарной гиперсети. Построены алгоритмы поиска "оптимальных" атак "с возвращением ресурса" и "без возвращения ресурса".

1. Arakawa S., Katow J.,Murata M. "Design method of logical topologies with quality of reliability in WDM networks"//Photonic Network Communications,5:2, pp 107-121, 2003

2. Barefoot C.A, "Vulnerability in graphs a comparative survey"// Journal of Combinatorial Mathematics and Combinatorial Computation 1987 Vol.1, p. 13-22

3. Carlier J., Yu Li, Lutton J. "Reliability evaluation of large telecommuncation networks"//Discrete Applied Mathematics 76 (1997), pp. 61-80.

4. Chang J-M., Yang J-S., Wang Y-L., Cheng Y. "Panconnectivity, fault-tolerant Hamiltonicity and hamiltonian-connectivity in alternating group graphs" // Networks 2004. Vol. 44 N 4. P. 302-310.

5. Cher Y., Tan J , Hsu L., "Kao S. Super-connectivity and super-edge-connectivity for some inter connection networks" // Appl. Math, and Comput. 2003.N.2-3. P.245-254.

6. Fleischer Lisa K , Skutella Martin "Quickest Flows Over Time" http.//www andrew.cmu.edu/user/lkf/papers/FS-journal.pdf

7. Glockner G.D., Nemhauser G.L. "A Dynamic network flow problem with uncertain arc capacities, formlation and problem structure" // "Operation Research", Vol.48, № 2, March-April 2000, pp. 233-242

8. Ho Y., Frinke D., Tobin D. "Planning, Petri-Nets and Intrusion Detection"// 21st Proc. National Information Systems Security Conference http.//csrc nist gov/nissc/1998/proceedings/paperF5.pdf

9. Kirlangic A. "On the Weak-integrity of Graphs" // Journal of Mathematical Modelling and Algorithms 2003. Vol. 2. N 2. P. 81-95.

10. Kirlangic A "The edge-integrity of some graphs" // Journal of Combinatorial Mathematics and Combinatorial Computation. 2001. Vol. 37. P. 139-148.

11. Kuzmanovic Aleksandar, Knightly Edward W. "Low-Rate TCP-Targeted Denial of Service Attacks"// Proceedings of ACM. SIGCOMM '03, Karlsruhe, Germany http //www.acm.org/sigcomm/sigcomm2003/papers/p75-kuzmanovic.pdf

12. Lammel R., Verhoef C. "Semi-automatic Grammar Recovery"// Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands. 2000.

13. Lengauer T., Wanke E. "Efficient solution of connectivity problem on hierarchically defined graphs"// SIAM J.Comput., Vol 17., №6, 1988, pp. 1063-1080

14. Liu Mingyan , Baras John S. "Performance Analysis Using A Hierarchical Loss Network Model"// in Proc. IEEE GLOBECOM, vol. 3, 2000, pp. 1793-1797

15. Ludovic M "A Genetic Algorithm as an Alternative Tool for Security Audit Trails Analysis"// http://www.rennes supelec.fr/ren/rd/ssir/publis/raid98me.pdf

16. Murali Kodialam T. V. Lakshman "Detecting Network Intrusions via Sampling: A Game Theoretic Approach"// IEEE 2003 http://www.comsoc.org/confs/ieee-infocom/2003/papers/4602.PDF

17. Petingi L., Urquhart M. "Algorithms for the Computation of Communication Network Vulnerability Indexes"// Serie "Reports t'ecnicos". 1996.

18. Peyravian M. "Providing different levels of network availability in high-speed networks"// Global Telecommunications Conference, 1994. GLOBECOM '94. 'Communications: The Global Bridge'., IEEE,Vol.2 pp. 941-945, 1994

19. Philips Cynthia A. "The network inhibition problem"// Proceedings of the twenty-fifth annual ACM symposium on Theory of computing 1993. P. 776-785

20. Shan Zheng, Chen Peng, Xu Ying, Xu Ke "A network state based intrusion detection model"//International Conference on Computer Networks and Mobile Computing, 2001, pp 481-486

21. Shener 0., Haines J., Jha S., Lippmann R., Wing J. "Automated generation and analyses of attack graphs"// Proc. Of IEEE Symp. On Sec. And Priv. 2002 . p. 273-284

22. Stepashkin M.V. Kotenko I.V. "Analyzing Vulnerabilities and Measuring Security Level at Design and Exploitation Stages of Computer Network Life Cycle"// MMM-ACNS 2005, LNCS 3685, Springer-Verlag Berlin Heidelberg, 2005. pp 311-324Л

23. Swiler L.P., PhilpsC, Gaylor T. "A Graph-Based Network Vulnerability Analysis System"// Sandra report SSAAAAAND97-3010/1. US-705. Sandia National Laboratories, USA, 1998

24. Westmark Vickie R. "A Definition for Information System Survivability"// Proceeding of the 37th Hawaii International Conference on System Sciences 2004 (IEEE) http://csdl2 computer.org/comp/proceedings/hicss/2004/2056/09/205690303a.pdf

25. Yin J-H , Li J-S , Chen G-L., Zhong С On the fault-tolerant diamert and wide diametr of w-connected graphs" // Networks. 2005. Vol. 48. N 2. P. 88-94.

26. Zang S , Peng S "Relationship between scattering number and other vulnerability parameters" // International Journal of Computer Mathematics. 2004. Vol. 81 N 3. P. 291-298.

27. Zhang S , Wang Z. "Scattering number in graphs" // Networks 2001. Vol. 37 N 2 P 102-108

28. Баранов А.П., Борисенко Н.П., Зегжда П.Д., Корт С.С., Ростовцев А.Г. "Математические основы информационной безопасности". Орел: ВИПС, 1997. 354 с

29. Березко М.П., Вишневский В.М., Левнер Е.В., Федотов Е.В. "Математические модели исследования алгоритмов маршрутизации в сетях передачи данных"// "Информационные процессы", Том 1, N° 2, 2001, стр. 103-125.

30. Береснев В JI, Дементьев В Т. "Исследование операций" Учебное пособие, НГУ, 1979, 92 с.

31. Блукке В.П, Величко В.В., Попков В К., Юргенсон А.Н. "Проблемы анализа живучести мобильной связи"// Новосибирск, 2005 (Препринт / СО РАН, ИВМиМГ; 1162)

32. Васенин В.А. "Информационная безопасность и компьютерный терроризм"// Научные и методологические проблемы информационной безопасности (сборник статей) М.: МЦНМО, 2005. с.67-84

33. Вишневский В.М. "Теоретические основы проектирования компьютерных сетей". М.: Техносфера, 2003, 512 с.

34. Вишневский В.М., Ляхов А.И., Даскалова Хр. "Вероятностные методы исследования широкополосных беспроводных сетей"// Ргос. Int. Workshop "Distributed Computer and Communication Networks"(DCCN-2005). Sofia, Bulgaria, April 23-29, pp. 9-18, 2005

35. Величко В.В , Юргенсон А.Н. "Задача анализа структурной надежности мобильных сетей связи"// Труды ИВМиМГ серия Информатика 2005 С. 58-65.

36. Величко В В., Юргенсон А.Н. "Модели структурной надежности в мобильных Сетях передачи данных"// ISSN 0013-57771 "Электросвязь"№3, С. 36-37 , 2006 г

37. Гольдштейн B.C. "Сетевой мониторинг: проблемы и решения"//М: "Вестник связи", №4, 2002

38. Грушо А А , Тимнонина Е.Е 'Теоретические основы защиты информации". М.: Яхтсмен, 1996. - 304 с.

39. Гэри М., Джонсон Д. "Вычислительные машины и трудно решаемые задачи" -М.: Мир, 1982 416 с.

40. Кристофидес Н. "Теория графов. Алгоритмический подход" М.: Мир 1978, - 432 с

41. Дудник Б Я , Овчаренко В.Ф., Орлов В.К. и др. "Надёжность и живучесть системы связи" М. Радио и связь, 1984г.

42. Майнагашев С.М., Попков В.К. "Задача о максимальном потоке в нестационарных сетях связи"// Сб. трудов. Ситемное моделирование -13, Новосибирск, ВЦ СО АН СССР, 1988, с 64-69

43. Малашенко Ю.Е. "Математические модели анализа потоковых сетевых систем" -ВЦ РАН, Москва 1993, 170 с.

44. Малашенко Ю.Е , Новикова Н.М. "Многокритериальный и максиминный анализ многопродуктовых сетей" ВЦ РАН, Москва 1988, 66 с.

45. Малышко В.В., Харари Ф. "Задача о минимальном блокирующем потоке в сети"// Кибернетика Jf«2, 1986, с. 44-48

46. Назарова И.А. "Лексикографическая задача анализа уязвимости многопродуктовой сети"// Теория и системы управления. 2003 №5 с. 123-134

47. Назарова И.А. "Методы упорядоченного перебора, использующий вектор оценочных функций". М. ВЦ РАН, 1995

48. Назарова И.А. "Модели и методы анализа многопродуктовых сетей" ВЦ РАН, Москва, 2004, 111 с.

49. Назарова И А "Модели и методы решения задачи анализа уязвимости сетей"// ВЦ РАН, Москва 2006, Сообщения по прикладной математике, 44 с.

50. Нильсон H "Искусственный интеллект" М. Мир 1979

51. Олифер В.Г., Олифер Н.А. "Компьютерные сети. Принципы, технологии, протоколы" СПб: Питер, 2001. - 627 с

52. Сатовский Б JL "MPLS технология маршрутизации для нового поколения сетей общего пользования"// "Сети и системы связи", N°3, 2001, http.//www ccc.ru/magazine/depot/0103/read.html70303.htm

53. Соколов И.А., Антонов C.B., Шоргин С.Я. "Моделирование современных телекоммуникационных систем" http://elics.iitp.ru/file/t2c2 doc

54. Попков В.К. "Математические модели живучести сетей связи" Новосибирск 1990г.

55. Попков В К. "Математические модели связности"- Новосибирск, ИВМ и МГ СО-РАН, 2001г.

56. Попков B.K "Применение теории нестационарных гиперсетей в задачах обнаружения атак в IP сетях"// Материалы XXX юбилейной международной конференции IT+SE'2003

57. B.K. Попков, О.Д. Соколова, А.Н. Юргенсон "К вопросу о моделировании информационных атак с помощью гиперсетей" //Материалы конференции МНПК "Связь 2004", Бишкек, Киргизия, стр 258-263

58. Попков В.К., Соколова О.Д., Юргенсон А.Н. "Максимальный поток и минимальный разрез в гиперсетях"// Материалы 9-й международной конференции ПФИС-2006, Новосибирск с. 242 - 246.

59. Попков В К , Соколова О.Д., Юргенсон А.Н. "О некоторых задачах анализа устойчивости работы информационных сетей" // Материалы конференции "Математика и безопасность информационных технологий" (Москва, МГУ, 28-29 октября 2004 года) С. 326-331.

60. Попков В.К., Соколова О.Д., Юргенсон А.Н., Юрошев A.B. "О некоторых подходах к решению задач анализа работы сетей передачи данных"// Труды ИВМиМГ серия Информатика 2005 с 111-116.

61. В.К. Попков, А.Н. Юргенсон "Применение модели гиперсети к исследованию временных характеристик сетей связи"// Материалы конференции МНПК "Связь -2004", Бишкек, Киргизия, с. 264-267;

62. Пронь С.П. "Обзор подходов к оптимальному проектированию сетей связи с учетом живучести" Йошкор - Ола, 1984г.

63. Родионов А С "Имитационное моделирование распространения вируса типа "почтовый червь"// XXX Межд. конф. "Информационные технологии в науке, образовании, телекоммуникации и бизнесе", Украина, Гурзуф, 2003г., с. 212-214

64. Родионов A.C. "Проблемы создания систем имитационного моделирования инфо-телекоммуникационных сетей"// МНПК Связь-2004. Материалы 8-й межд.конф "Проблемы функционирования информационных сетей", т.2. с. 268-272

65. Rodionov A.S., Choo Н., Youn H.Y. "Process Simulation Using Randomized Markov Chain and Truncated Marginal Distribution"// Supercomputing.-2002,M.-P 69-85

66. Свами M. Тхуласираман К. "Графы, сети, алгоритмы" М.: "Мир" 1984г.

67. Сердюк В. "Вы атакованы защищайтесь!" http.//www. bytemag ru/Article.asp?ID=2030

68. Соколова О. Д, Юргенсон А. Н. "О сведении одной проблемы мониторинга информационной сети к задаче в гиперсетях" // Вычислительные технологии, т.9. (Новосибирск) и Вестник КазНУ им. Аль-Фараби (Казахстан), Совместный выпуск, часть 3, 2004 г., С. 47-52.

69. Тютин В А. "Проблемы создания средств проектирования телекоммуникационных сетей с технологией передачи ATM"// Электронный журнал "ИССЛЕДОВАНО В POCCHH"http.//zhurnal.ape relarn.ru/articles/2001/137.pdf

70. Форд JI., Фалкерсон Д. "Потоки в сетях"- М.: Мир 1966, 276 с.

71. Юргенсон А Н. "Моделирование информационных атак с помощью гиперсетей"// Материалы конференции молодых ученых ИВМиМГ (апрель 2004) С. 257-266

72. Юргенсон А.Н. "Поиск простой (s-t) цепи с максимальной пропускной способностью в нестационарной гиперсети" // Материалы конференции молодых ученых ИВМиМГ (апрель 2005) С. 264-274

73. Якимов М.А. "Об одном подходе к решению NP-полных задач теории графов"// Труды ИВМиМГ, Информатика 4, Новосибирск, 2002, с. 158-164.