Вычисление показателей живучести информационных сетей на модели нестационарной гиперсети тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Юргенсон, Анастасия Николаевна

• Юргенсон, Анастасия Николаевна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Юргенсон, Анастасия Николаевна

Введение

Глава 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 перемещаются хаотично) частичной утрате сетью связи своих функций, рассматрены два класса: случайные и направленные. Для моделирования атаки в гиперсети введен дополнительный поток, который уменьшал полезную пропускную способность в линиях связи. Рассмотрено влияние атаки на качество обслуживания в сети, т.е. влияние атаки на величину максимального потока.

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

Заключение

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Юргенсон, Анастасия Николаевна, 2006 год

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.