Сетевой червь

Размещено на http://www.allbest.ru/

Введение

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

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

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

В дипломной работе исследуется SEIR - модель. Цель дипломной работы: анализ минимизации задачи затрат для SEIR модели во время действия эпидемии. Исследование основано на принципе максимума Понтрягина в форме Лагранжа.

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

Работа состоит из введения, четырех глав и заключения.

В главе 1 обзор основных моделей: SI, SIR, SEIQR, SEIR. Были описаны возможные задачи для исследования в этих моделях и приведены основные

результаты, полученные для них.

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

В главе 3 излагается задача оптимального управления в форме Понтрягина с фиксированным временем и свободным правым концом. Была сформулирована теорема о необходимых условиях оптимальности для изучаемой задачи и приведена схема решения подобных задач. Был применен принцип максимума Понтрягина к SEIR модели. Доказана теорема о том, что на заключительном интервале времени оптимальное управление равно нулю.

В главе 4 изучается оптимизационная задача для SEIR модели с одномерным управлением. С помощью пакета Mathematica вычисляются допустимые экстремали.



Глава 1. Обзор основных моделей эпидемии в компьютерных сетях

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

У эпидемии сетевых червей существует несколько стадий [1].

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

2) Стадия «взрывного роста» популяции червей. На этой стадии активность червя становится заметной, но не является максимальной. Наступает когда достигается ”критическая масса” (в работе [2] эта масса достигается, когда заражено 5% уязвимых узлов).

3) Насыщение узлов сети червями. После завершения второй стадии большая часть узлов сети уже заражено. Черви взаимодействуют чаще с зараженными узлами, поэтому увеличение зараженных узлов не возможно.

4) Затухание эпидемии. Начало противодействия эпидемии. Появляется возможность удалить червя или препятствовать его проникновению на узел.

5) Полное затухание. В результате противодействия у червя не остается возможности для распространения.

6) Возобновление эпидемии.

Рассмотрим основные модели, описывающие распространение эпидемии сетевых червей.

Простейшая модель эпидемии SI (Susceptible-Infected) [2]

Предполагается, что в данной модели сеть не защищена, то есть, не установлена антивирусная программа, а, следовательно, эпидемия не может угаснуть. Компьютер может находиться только в двух состояниях: уязвимом (Susceptible) и инфицированном (Infected). Тогда общее число узлов постоянно и равно N:

число незараженных компьютеров,

число инфицированных компьютеров.

Пусть

и ,

т.е. i - доля зараженных компьютеров, s - доля незараженных. Тогда динамика системы описывается следующим уравнением [2]:

где в - частота заражения, то есть скорость размножения червя.

Уравнение (1) имеет аналитическое решение:

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

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



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

Модель эпидемии SIR (Susceptible-Infected-Removed) [1],[3],[4]

В этой модели узел может находиться в трех состояниях: здоровом, уязвимом для червя (S), инфицированном (I) и невосприимчивом (R), то есть, учитывается возможность избавления системы от заражённых узлов. В SIR модели предполагается, что во время действия эпидемии некоторое количество заражённых субъектов либо избавляется от вредоносной программы, например, после установки антивирусного программного обеспечения, либо перестаёт функционировать. После ликвидации вируса узел становится невосприимчивым к нему.

Структура компьютерной системы на основе SIR - модели может быть представлена выражением:

,

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

Обозначим доли уязвимых, инфицированных и вылеченных узлов через s, i и r:

Систему (2) часто называют системой Кермака-Маккендрика.

В работе [3] для этой модели определяется понятие порогового условия для развития эпидемии. Введем функцию инфективности - средняя инфективность узла, зараженного единиц времени назад, по отношению к здоровым узлам сети. Пусть вероятность заразиться при контакте с инфицированным узлом, среднее число контактов в единицу времени, промежуток времени, когда узел является заразным. Тогда

Количество новых инфицированных в момент времени t узлов равно

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

Теорема 1 (пороговая теорема).

Пусть процесс распространения вируса по сети описывается моделью (3). Тогда вспышка эпидемии возникает тогда и только тогда, когда основное репродуктивное число больше единицы. В противном случае, появление вируса в сети не приводит к эпидемии. [3]

В [4] был получен аналог основного репродуктивного числа. На участке возрастания i(t) ее производная по времени должна быть больше 0. Поскольку количество здоровых узлов непрерывно уменьшается за счет перехода узлов из здорового состояния в инфицированное, следовательно, для наступления эпидемии необходимо выполнение следующего условия:

В [4] показано, что наступление эпидемии возможно, когда . Следовательно, при эпидемия не наступит.

Модель эпидемии SEIQR (Susceptible-Exposed-Infected-Quarantine-Removed)[5]

Согласно данной модели объекты делятся на пять групп:

- здоровые (S)

- инфицированные, распространяющие инфекцию (I)

- инфицированные, не распространяющие инфекцию, то есть находящиеся в инкубационном периоде(E)

- вылеченные, обладающие иммунитетом (R)

- находящиеся в карантине(Q)

Структура компьютерной системы, основанной на SEIQR - модели, задается выражением:

Динамика системы описывается следующими уравнениями:

В [5] показано, что введение дополнительных типов объекта управления и возможность введения узлов сети в карантин повышает точность конечного результата при условии, что имеется обновляемое антивирусное программное обеспечение.



где в - коэффициент заражения, д - коэффициент карантирования, k,г - коэффициенты лечения, б - коэффициент перехода из латентного состояния E в инфицированное I (т.е. среднее время пребывания в латентном состоянии).

Модель эпидемии SEIR [6]-[9]

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

Используем эту модель для описания процесса распространения компьютерного вируса на фиксированном интервале времени [0, T].

Объекты сети могут находиться в четырех состояниях:

- здоровые (S)

- инфицированные, распространяющие инфекцию (I)

- инфицированные, не распространяющие инфекцию, то есть находящиеся в инкубационном периоде(E)

- вылеченные, обладающие иммунитетом (R).

Введем следующие переменные для описания модели:

N - общее количество компьютеров в сети,

S(t) - количество здоровых, но уязвимых узлов в момент времени t,

E(t) - количество узлов, находящихся в инкубационном периоде в момент времени t,

I(t) - количество зараженных узлов в момент времени t, которые распространяю инфекцию,

в - коэффициент заражения,

б - коэффициент перехода вируса из латентного состояния,

- коэффициенты лечения.

Тогда динамика модели описывается следующими дифференциальными уравнениями:

Так , то .

В [6] для модели SEIR показано, что не все восприимчивые объекты заражаются в течение действия эпидемии.

В [7] SEIR модель изучалась в предположении, что интенсивность заражения зависит от возраста инфекции. Авторы показали, что несколько стандартных теорем математической эпидемиологии могут быть применимы для SEIR - модели и рассчитали основное репродуктивное число , при котором положение равновесия устойчиво. Найдены условия, при которых заболевание присутствует всегда.

В [8] изучается SEIR модель развития эпидемии в предположении, что особи могут рождаться и погибать. Найдено положение равновесия рассматриваемой системы, определены условия, при которых равновесия асимптотически устойчиво. Рассмотрено применение модели к трансмиссивным заболеваниям (vector borne diseases), т.е. заболеваниям, которые передаются кровососущими насекомыми.

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

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

Глава 2. Постановка задачи оптимального управления. Существование решения

Зададим фиксированный интервал времени [0, T], на котором происходит процесс распространение вируса. В качестве функционала затрат рассмотрим следующий интеграл:

который включает в себя:

затраты на один инфицированный и заразный узел (I).

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

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

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

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

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

Функции управления ограничены: , .

Теорема 2. Множество решений задачи (5) - (6) ограничено.

Доказательство: Утверждение теоремы вытекает из следующих Лемм [10]:

Лемма1. для любого t.

Лемма2. и для любого t.

Лемма3. для любого t.

В силу приведенных Лемм, Так как по нашему предположению

, то , ,



для всех t. Теорема 3. В задаче (5) - (6) оптимальное решение существует.

Доказательство: Для доказательства существования решения применим теорему Филиппова [11] - [12]. Для этого проверим выполнение следующих условий:

1) Множество допустимых управлений выпукло и компактно.

2) Множество допустимых скоростей выпукло.

3) Допустимые решения системы (6) ограничены.

Множество управлений - это прямоугольник. Прямоугольник - компактное, выпуклое множество. Следовательно, выполнение условия 1 очевидно.

Условие 2 выполнено в силу того, что рассматриваемая задача является линейной по управлению.

Условие 3 доказывается в Теореме 2.

Следовательно, теорему Филиппова можно применить, и решение существует.

Глава 3. Задача оптимального управления. Необходимые условия оптимальности

Нужно минимизировать следующий функционал:

на траекториях системы:

,



при условиях на управление:

И заданном условии в момент :

Задача (7) - (10) называется задачей оптимального управления с заданным временем и незакрепленным правым концом [13]. Здесь вектор функция фазовая переменная, управление. Уравнение (8) называется дифференциальной связью, а соотношение (9) - ограничением на управление, соотношение (10) - краевое условие.

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

Пару ( будем называть управляемым процессом в задаче оптимального управления (7) - (10), если функция управления кусочно-непрерывная, удовлетворяющая условию (9), а фазовая траектория кусочно-непрерывно дифференцируема и удовлетворяет уравнению дифференциальной связи (8) везде, кроме точек разрыва управления . Будем считать управляемый процесс допустимым, если, помимо того, выполнено краевое условие.

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



,

выполняется неравенство .

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

Тогда выполнено условие оптимальности по :

где единственное решение дифференциального уравнения

с краевым условием

).

Множитель Лагранжа функционала оказывается равным единице, а условие трансверсальности в несущественно. [13]

Схема решения задачи[13]

Пусть векторная кусочно-дифференцируемая функция, которая называется сопряженной функцией.

1) Выписываем необходимые условия оптимальности процесса (:

• Сопряженные уравнения (уравнение Эйлера):



• Условие трансверсальности - краевое условие для :

• Оптимальность по :

2) Ищем допустимые управляемые процессы, для которых выполняются условия оптимальности.

3) Находим решение или доказываем, что его нет.

Замечание 1. Отметим, что в необходимые условия оптимальности не входит переменная .

Применим принцип максимума Понтрягина к нашей задаче

По условию теоремы о необходимом условии экстремума

1) Выпишем уравнения Эйлера:

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



Глава 4. Оптимизационная задача с одномерным управлением. Численное моделирование экстремалей

Рассмотрим задачу (5) - (6) при условии, что параметр фиксирован и равен некоторому положительному числу. Таким образом, управлением является только параметр k.

Для задачи (18) - (19) верны теоремы 2 и 3. Необходимые условия оптимальности принимают вид:

Заметим, что и в этом случае Теорема 5 выполняется, т.е. в конечный момент времени управление .

Особые управления

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

Пусть для всех . Тогда все существующие производные функции также равны нулю: .

Используем это для определения управления:

Мы видим, что во второй производной появилось управление, т.е. мы можем из последнего равенства выразить :

Для задачи (18) - (19) допустимые экстремали, построенные с помощью пакета Mathematica, особые участки не содержали. Сложность выражения (25) не позволило получить простые условия существования особых управлений.

Оптимальная траектория будет состоять из участков, являющихся решениями одной из трех систем:

1)

2)

3)

4)

Построение допустимых экстремалей с использованием пакета Mathematica

Будем рассматривать распространение сетевой эпидемии на отрезке времени [0, T]. 1. Начнем решать задачу оптимального управления с правого конца, т.е. положим . Необходимо задать граничные условия. Из условий трансверсальности следует, что а значения фазовых переменных на правом конце зададим произвольно .

2. Теорема 5 утверждает, что на заключительном интервале времени управление равно нулю, поэтому начинаем решать задачу с .

3. Построим фазовые и сопряженные переменные.

4. По фазовым и сопряженным переменных вычисляем функцию переключения .

5. Определяем ближайшую к T точку, в которой функция переключения равна нулю, и обозначим ее . Момент - момент переключения управления я с нуля на .

6. Далее решаем систему, подставляя управление равное . Для решения системы с управлением используем значения фазовых и сопряженных переменных в момент , полученные на предыдущем этапе.

7. Снова определим ближайший к момент переключения , в котором обращается в ноль.

8. Действуем аналогично, пока не найдем решение на всем отрезке [0,T]. Если выполняются начальные условия для фазовых переменных, то решение удовлетворяет необходимым условиям оптимальности. Если для фазовых переменных не выполняются начальные условия, то необходимо изменить граничные условия для функций , , на начальном этапе вычислений.

Пример 1. Рассмотрим развитие эпидемии компьютерного вируса на отрезке времени [0, 10]. Так как известны значения сопряженных переменных в момент времени T, то начнем решать систему уравнений принципа максимума Понтрягина в обратном времени, начиная с T. Введем начальные условия:

T = 10, в = 5, , = 1, = 0.7, = 3, N = 50, б = , , , , , , , г = 0.1, k = 0.

Определим ближайший к T=10 момент переключения, в котором функция переключения равна нулю, и обозначим его .

В этот момент времени значение управления меняется с нуля на . Далее решаем систему на отрезке времени [0, ] с управлением равным . В качестве краевых условий берем значения фазовых переменных в точке переключения в первой системе:

,

,

,

,

Начальные условия фазовых переменных выполнены, получили решение, удовлетворяющее необходимым условиям оптимальности.

Целевой функционал в данном случае равен 340.0261724012998.

Пример 2. Рассмотрим развитие эпидемии компьютерного вируса на отрезке времени [0, 10]. По аналогии с первым примером начнем решать систему уравнений принципа максимума Понтрягина, начиная с T. Введем начальные условия:

T = 10, в = 5, , = 1, = 0.7, = 3, N = 50, б = , , , , , , , г = 0.1, k = 0.

Определим ближайший к T=10 момент переключения, в котором функция переключения равна нулю, и обозначим его

В этот момент времени значение управления меняется с нуля на . Далее решаем систему на отрезке времени [0, ] с управлением равным . В качестве краевых условий берем значения фазовых переменных в точке переключения в первой системе:

,

,

,

,

Вычисляем для при . Определяем функцию переключения . Снова определим ближайший к момент переключения 0.03456759821780173 в котором обращается в ноль.

Таким образом, управление совершает еще одно переключение с на . Теперь рассматриваем эпидемию на отрезке [0,0.03456759821780173]. В качестве краевых условий берем значения фазовых переменных в точке переключения во второй системе:

,

,

,

,

.

Начальные условия фазовых переменных выполнены, получили решение, удовлетворяющее необходимым условиям оптимальности.

Целевой функционал в данном случае равен

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



Заключение

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



Список использованной литературы

1. Качалин А.И. Моделирование процесса распространения сетевых червей для оптимизации защиты корпоративной сети//Искусственный интеллект.2006.С.84 - 86.

2. Захарченко А. "Черводинамика: причины и следствия". SIR модель и её варианты.URL: http://citforum.ru/security/virus/ch_dinamic/ (дата обращения 19.05.2015).

3. Братусь А.С. Новожилов А.С. Платонов А.П. Динамические системы и модели биологии М.: Физматлит, 2010.

4. Котенко И. В., Воронцов В. В. Аналитические модели распространения сетевых червей //Труды СПИИРАН. Вып. 4. -- СПб.: Наука, 2007. С. 208-224.

5. Давыдов В.В. Сравнительный анализ моделей распространения компьютерных вирусов в автоматизированных системах управления технологическим процессом//Вестник НТУ "ХПИ". 2012. № 38.С. 147-151.

6. Масленников Б.И. Сравнительный анализ методов имитационного моделирования//Интернет-журнал «Науковедение».2014.вып.1.С.1-9.

7. Gergely Rцst, Jianhong Wu. SEIR epidemiological model with varying infectivity and infinite delay// Math Biosci Eng.2008. 389-402.

8. Nita H. Shah, Jyoti Gupta. SEIR Model and Simulation for Vector Borne Diseases.//Applied Mathematics.2013.4.13-17.

9. Helmut Maurer, Maria Do Ros_ario De Pinho. Optimal Control of Epidemiological SEIR models with L1-Objectives and Control-State Constraints. Submitted, 21 pages. 2014. <hal-01101291>.URL: https://hal.inria.fr/hal-01101291.

10. Yongqing Yuan. The Collision Regions Between Two Epidemic Models: SIR vs. SEIR// Annandale-on-Hudson.New York.2012.23-24.

11. Knowles G. An Introduction to Applied Optimal Control.1982, Academic Press, N.Y., p.180

12. Cesari L. Optimization theory and Applications.1983, Springer,N.Y.p.554

13. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Теория. Примеры. Задачи. М.: Наука. Главная редакция физико-математической литературы.1984.

Размещено на Allbest.ru