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

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

Оглавление

Введение

Глава 1. Некоторые модели распространения вирусов

1.1 SI модель

1.2 Модель эпидемии вируса SIR (Susceptible-Infected-Removed model)

1.3 Модель эпидемии SAIR (Susceptible-Antidotal-Infected-Removed)

1.4 Модель PSIDR(Progressive Susceptible-Infected-Detected-Removed)

Глава 2. Постановка оптимизационной задачи для модели PSIDR

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

3.1 Постановка задачи оптимального управления

3.2 Необходимые условия оптимальности в задаче со свободным правым концом

3.3 Правило решения задачи оптимизации со свободным правым концом и фиксированным временем

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

3.5 Особые экстремали

Глава 4. Численное моделирование решений

Заключение

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



Введение

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

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

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

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

В дипломной работе исследуется модель эпидемии компьютерных вирусов PSIDR. Целью дипломной работы является анализ модели и определение оптимального управления. Исследование основано на принципе максимума Понтрягина. В дипломной работе доказано существование решения оптимизационной задачи для модели PSIDR. Найдена структура оптимального управления. С использованием пакета “Wolfram Mathematica 10” получены траектории, претендующие на оптимальность. Работа состоит из введения и четырех глав. В главе 1 приведен обзор некоторых эпидемиологических моделей. В главе 2- сформулирована задача, проанализированы допустимые траектории, доказано существование оптимального решения. В главе 3 сформулированы необходимые условия оптимальности и получена структура оптимального управления. В главе 4 описывается алгоритм построения численного решения.



Глава 1. Некоторые модели распространения вирусов

1.1 SI модель

SI модель- это простейшая модель распространения вируса. В ней предполагается, что узлы сети не защищены от атак вируса, то есть на них не установлено антивирусное программное обеспечение. Отсюда следует, что в данной модели эпидемия не может остановиться. Произвольный компьютер системы может находиться в двух состояниях: уязвимом (Susceptible), либо в зараженном (Infected).

Рассмотрим модель с постоянным числом компьютеров в сети. Обозначим N- общее число компьютеров в сети, S(t)- количество компьютеров в уязвимом состоянии, I(t)- количество компьютеров в зараженном состоянии в момент времени t:

Введем переменную в- скорость распространения вируса:

в=

где - скорость, с которой червь сканирует систему, - размер адресного пространства сети.

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

(1-i)i (1)

где: i(t)=

Известно аналитическое решение уравнения (1):

i(t)=

где - доля инфицированных узлов в начале эпидемии,

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

Заметим, что , то есть I(t)N

Усложнением модели SI является следующая модель:

1.2 Модель эпидемии вируса SIR (Susceptible-Infected-Removed model)

В данной модели узлы сети могут находится в нескольких состояниях: здоровые, но подверженные заражению (S - susceptible), инфицированные (I -infective),невосприимчивые к заражению ((R - recovered/removed). Характер эпидемии зависит только от количества зараженных узлов.

Рассмотрим модель SIR в предположении, что новые компьютеры в сети не появляются и компьютеры из сети не удаляются.

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

S(t)+I(t)+R(t)=N

Изменение характеристик в данной модели полностью описывается уравнениями



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

1.3 Модель эпидемии SAIR (Susceptible-Antidotal-Infected-Removed)

Все компьютеры в модели делятся на 4 вида:

S- незараженные компьютеры, восприимчивые к вирусам

A- незараженные компьютеры, с установленной антивирусной программой

I- зараженные компьютеры

R- вылеченные компьютеры

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

где коэффициенты имеют следующий смысл:

N - частота добавления новых компьютеров

- частота гибели компьютеров не из-за вируса

- частота заражения уязвимых компьютеров

- частота заражения компьютеров, с установленной антивирусной программой

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

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

- частота лечения выведенных из строя компьютеров с участием оператора

- интенсивность обращения восприимчивых к тем ,кто устанавливает антивирус

Если предположить, что новые компьютеры не добавляются, а старые выходят из строя только из-за вируса, то есть, значения N и м равны нулю, то система принимает вид:

1.4 Модель PSIDR(Progressive Susceptible-Infected-Detected-Removed)

В данной модели эпидемию компьютерных сетей можно разделить на две фазы:

1)Вирус заражает один из компьютеров, после чего распространяется в системе свободно.

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

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

В данной модели I-зараженные (разносчики), S-подверженные заражению, R- вылеченные и невосприимчивые, D-обнаруженные зараженные объекты.

Изменение характеристик в нашей модели полностью описывают уравнениями:

где в - скорость заражения; ?? - скорость лечения; µ -скорость обнаружения. В [6] показывают, что антивирусная программа должна быть обновлена как можно раньше, так как задержка обновления антивирусной программы приводит к большему распространению эпидемии в системе.



Глава 2. Постановка оптимизационной задачи для модели PSIDR

Рассмотрим модель PSIDR. Будем рассматривать м как параметр управления. Рассмотрим задачу минимизации затрат во время эпидемии. В качестве целевой функции рассмотрим следующий функционал:

I(t) + м(t)) dt

где: - плата за компьютеры, которые подверглись заражению

- плата за обновление антивируса

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

0?м(t)?

Таким образом, мы имеем задачу оптимального управления:

I(t) + м(t)) dt> min (3)

(4)

Заданы начальные условия:

I(0)=, S(0)= , D(0)=, (5)

Ограничения на управление:

0?м(t)? (6)

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

Лемма 1. S(t)?0, ? t?[0,T].

Доказательство:

= -вS(t)I(t)-м(t)S(t)

=-S(t)(вI(t)+м(t))

отсюда следует, что

S(t)=

S(0)==>0, а так как экспонента всегда положительна, то

S(t)>0 для ? t

Лемма 2. I(t)?0 ? t?[0,T].

Доказательство:

= -вS(t)I(t)-м(t)I(t)

=-I(t)(вS(t)+м(t))

отсюда следует, что

I(t)=

I(0)==>0, а так как экспонента всегда положительна, то

I(t)>0 для ? t

Лемма 3. D(t)?0 ? t?[0,T].

Доказательство:

=м(t)I(t)-??(t)D(t)

Решим это уравнение методом вариации постоянной.

Рассмотрим решение в виде:

D(t)= (t)

подставим в уравнение:

(t)= мI(t)(t),

= мI(t),

=dф+,

отсюда следует, что

D(t)= +dф

так как D(0)=0, =0, то есть:

D(t)=dф

таким образом D(t)>0, так как подынтегральная функция положительна.

Лемма 4. R(t)?0 ? t?[0,T].

Доказательство:

Так как

?0 ? t?[0,T]

то R(t)- возрастающая функция, в силу начальных условий R(0)=0, имеем R(t)?0 ? t?[0,T].

Доказательство Теоремы 1.

Так как в силу леммы (1)-(4): S(t),I(t),D(t),R(t)?0 и S(t)+I(t)+D(t)+R(t)=N ? t?[0,T], то каждая из функций не превосходит N для всех t, то есть множество решений задачи (3)-(6) ограничено.

Теорема 2. Оптимальное решение существует.

Доказательство:

Применим теорему Филиппова о существовании решения[8],[9]. Необходимо проверить следующие условия:

1)Ограниченность множества допустимых решений

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

3)Выпуклость по управлению множества допустимых скоростей

Условие 1 доказано в Теореме 1.

Условие 2 очевидно выполнено.

Условие 3 выполнено, так как функция в правой части система линейна по управлению.

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

Замечание 1.

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



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

3.1 Постановка задачи оптимального управления

Требуется минимизировать функционал.

(7)

при условиях:

(8)

(9)

(10)

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

Здесь:

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

:R ЧЧ> R- функции n+r+1 переменных,

:> - функция n переменных,

ц: R ЧЧ> R- вектор-функция n+r+1 переменных,

Вектор-функция x(.) называется фазовой переменной, u(.)-управлением. Уравнение (8), называемое дифференциальной связью, должно выполняться во всех точках непрерывности управления u(.) на интервале (, ).

Соотношение (9) -называется ограничением на управление, соотношение (10) - начальное условие для фазовых переменных.

Пара (x(.), u(.)), называется управляемым процессом в задаче оптимального управления, если x- кусочно-непрерывная дифференцируемая функция, u(.)кусочно-непрерывная функция управления, выполняется дифференциальная связь (8).

Управляемый процесс является допустимым, если, кроме того выполняются соотношения (9) и (10).

Допустимый управляемый процесс =((.),(.)) называют локально оптимальным, если существует ?? >0 такое, что для всякого допустимого управляемого процесса о=(x(.), u(.)) для которого < ??, выполняется неравенство?

3.2 Необходимые условия оптимальности в задаче со свободным правым концом

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

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

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

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

)

3.3 Правило решения задачи оптимизации со свободным правым концом и фиксированным временем

1.Составить уравнения для сопряженных переменных p(t):

2.Выписать краевые условия для сопряженных переменных(условие трансверсальности)

)

3.Выписать необходимое условие оптимальности процесса по управлению

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

5.Найти решение или доказать, что его нет.

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

Для решения задачи (3)-(6) применим принцип максимума Понтрягина:

1)Выпишем сопряженные уравнения:



=(вI(t)+м(t))-вI(t)

=вS(t)+(-вS(t)+м(t))+C1

2)Выпишем условие трансверсальности:

(T)=0, i=1,2

3)Впишем условие оптимальности по управлению:

м(t)+м(t)S(t)+м(t)I(t) >, или

(11)

Обозначим:

G(t)=)

Функцию G(t) будем называть функцией переключения.

Из условия (5) следует, что оптимальное управление имеет следующую структуру

м=t?((12)

м принимает значение если принимает отрицательные значения.

м принимает значение 0, если принимает положительные значения.

м принимает значение, если равно 0 на некотором интервале времени. В этом случае управление называется особым.

3.5 Особые экстремали

Если существует ненулевой интервал (,) такой, что функция переключения G(t)=0 для всех t ? (,), то соответствующая экстремаль (S,I,) называется особым, а управление - особым управлением. Из условия (11) особое управление не определяется. Что бы найти его, будем дифференцировать функцию переключения G(t) до тех пор, пока не появится управление. Известно, что управление при этом может появиться только у четной производной функции G(t):

(t)=0 следовательно = 0(12)

(t)=0 следовательно вIS + вIS + = 0(13)

(t)=0 следовательно + в + I - = 0(14)

Управление появилось в (14). Определяем его:

м_особое = I(t)(вI(t)S(t) - S(t) - в)

Для задачи (3)-(6) нам не удалось показать, что особые решения обязательно реализуются. Для их численного определения необходимы продвинутые методы. Для рассмотренных в работе параметров особые траектории не обнаружены.

Лемма 5. Существует такой интервал времени (?,Т), что м(t) = 0, для ? t?(?,Т).

Доказательство:

Проанализируем поведение функции переключения при t, близких к T.

G(T)=>0. Так как G(t)- непрерывная функция, то при t, близких к T, G(t) сохраняет знак, то есть, G(t)> 0. В силу (6) м(t)=0 при t, ,близких к T. Лемма Доказана.

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

1) м = 0

-в(t)S(t)I(t)

в(t)S(t)I(t)

=(t)в(t)I(t)-в(t)I(t)

(t)=(t)в(t)S(t)- в(t)S(t)+

2) м=

)

в(t)S(t)I(t))

=(в(t)I(t)+ (t))-в(t)I(t)

=в(t)S(t)+(-в(t)S(t)+ (t))+C1

3) м =

)

в(t)S(t)I(t))

=(в(t)I(t)+ (t))-в(t)I(t)

=в(t)S(t)+(-в(t)S(t)+ (t))+C1

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



Глава 4. Численное моделирование решений

Рассмотрим задачу (3)-(6):

I(t) + м(t)) dt> min (3)

(4)

I(0)=, S(0)= , D(0)=, (5)

0?м(t)? (6)

1.Задаем систему для S(t),I(t), и начинаем решать с правого конца при t = T. Нужно задать условие на правом конце. В силу условий трансверсальности , а ограничения для фазовых переменных S(T),I(T) мы задаем произвольным образом.

2.В силу леммы 5 на заключительном интервале, управление равно 0. 3.Вычисляем фазовые и сопряженные переменные.

4. Зная их вычисляем функцию переключения G(t).

5.Определяем ближайший слева к T момент переключения , в котором G(t)=0. В этот момент управление переключается с нуля на либо на . Попробуем найти траекторию, которая не содержит особых управлений.

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

7.Опять вычисляем ближайший момент к , в котором функция G(t) обращается в ноль.

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

Пример 1. Рассмотрим задачу распространения сетевой эпидемии. Начнем решать задачу оптимального управления с правого конца.

Построим решения данной системы:



Рис. 1. График функции S

Рис. 2. График функции I



Рис. 3. График функции p1

Рис. 4. График функции p2

Вычисляем фазовые и сопряженные переменные, строим функцию переключения G.



Рис. 5. График функции переключения

Видим, что произошло переключение управления. Вычислим момент, в котором функция переключения равна нулю.

Обозначим: T1= момент переключения управления с 0 на .

Вычислим фазовые и сопряженные переменные в момент T1:

Подставляем полученные значения в систему, с

Построим решение новой системы:



Рис. 6. График функции s

Рис. 7. График функции i



Рис. 8. График функции p1

Рис. 9. График функции p2

Снова строим функцию переключения:

Рис. 10. График функции переключения

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

Рис. 11. График функции s

Рис. 12. График функции i

Найдем целевой функционал:

Целевой функционал равен

Пример 2. Рассмотрим задачу с другими начальными условиями

Построим решения данной системы:

Рис. 13. График функции s



Рис. 14. График функции i

Рис. 15. График функции p1

Рис. 16. График функции p2

Найдем ближайший слева к T момент переключения , в котором G(t)=0

Рис. 17. График функции переключения



Ищем точку пересечения:

Дальше вычисляем значения фазовых и сопряженных переменных в точке переключения:

Решаем систему дифференциальных уравнений с управлением и вычисленными значениями фазовых и с поряженных переменных:



Строим решения новой системы:

Рис. 18. График функции s



Рис. 19. График функции i

Рис. 20. График функции p1

Рис. 21. График функции p2

Найдем ближайший слева к T1 момент переключения , в котором G(t)=0

Рис. 22. График функции переключения

Видим, что произошло переключение управления с 0 на

Находим точку, в котором G(t)=0 :

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

Далее решаем еще одну систему с переключением с на 0



Строим решения:

Рис. 23. График функции s



Рис. 24. График функции i

Строим функцию переключения и проверяем, будут ли еще переключения:



Рис. 25. График функции переключения

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



Рис. 26. График функции i

Рис. 27. График функции s



Вычислим целевой функционал:

I(t) + м(t)) dt при =1

+*0.5

Целевой функционал равен

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

Таблица 1. Зависимость показателей от параметров задачи

в	c1	T	i[0]	s[0]	м	целевой функционал	момент переключения
0.01	1	25	0.0140911	51.8201	0.05	37.9559	24.800000013511557`
0.01	1	25	0.00102266	69.1112	0.05	26.2966	24.800000013511557`
0.01	1	25	0.00102266	69.1112	0.05	28.217	24.900037412311557`
0.01	1	5	7.93355	19.6589	0.02	57.8266	4.9023849182211447`
0.02	1	10	2.22345	19.7917	0.01	17.199	9.9091384819288819
0.02	1	10	0.00414475	38.5996	0.01	7.80016	9.8012933919394810
0.02	1	10	0.0668592	33.5785	0.01	25.6398	9.8048183762818199



Заключение

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



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

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

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

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

4.J. Leveille. Epidemic Spreading In Technological Networks. Technical Report HPL-2002-287, HP Laboratories Bristol, 2002.

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

6.Груздева Л.М. Применение системы имитационного моделирования AnyLogic при обучении студентов направления «Информационная безопасность» // Современные научные исследования и инновации. 2014. № 10 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2014/10/39768 (дата обращения: 12.05.2015).

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

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

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

10.Josй Roberto Castilho Piqueira, Betyna Fernбndez Navarro and Luiz Henrique Alves Monteiro.Epidemiological Models Applied to Viruses in Computer Networks. Journal of Computer Science 1 2005, (1): 31-34

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

...