Постановка оптимизационной задачи для модели PSIDR (Progressive Susceptible-Infected-Detected-Removed). Правило решения задачи оптимизации со свободным правым концом и фиксированным временем. Принцип максимума Понтрягина. Численное моделирование решений.
Аннотация к работе
В современном мире, проблема распространения сетевых червей, то есть вредоносной программы, которая способна сама осуществлять поиск новых узлов для распространения вирусной угрозы с помощью коммуникационных сетей, стала чрезвычайно актуальна. Данный вид вредоносной программы наносит колоссальный ущерб в финансовом плане, а так же служит фундаментом для кражи конфиденциальной и частной информации.[1] Меры защиты, существующие в современном мире, не всегда быстро и оперативно справляются с эпидемиями вредоносного программного обеспечения, поэтому все большую актуальность приобретает задача по созданию эффективной системы обнаружения и защиты, способная остановить эпидемию на начальной стадии. Одним из подходов для анализа распространения эпидемии вирусов в сети, является аналитическое моделирование, которое позволяет получить решение в общем виде и возможность быстро смоделировать сценарий конкретной эпидемии. В дипломной работе исследуется модель эпидемии компьютерных вирусов PSIDR.Произвольный компьютер системы может находиться в двух состояниях: уязвимом (Susceptible), либо в зараженном (Infected). Обозначим N-общее число компьютеров в сети, S(t)-количество компьютеров в уязвимом состоянии, I(t)-количество компьютеров в зараженном состоянии в момент времени t: Введем переменную ?-скорость распространения вируса: ?= где - скорость, с которой червь сканирует систему, - размер адресного пространства сети. Усложнением модели SI является следующая модель: 1.2 Модель эпидемии вируса SIR (Susceptible-Infected-Removed model) В данной модели узлы сети могут находится в нескольких состояниях: здоровые, но подверженные заражению (S - susceptible), инфицированные (I-infective),невосприимчивые к заражению ((R - recovered/removed). Рассмотрим модель SIR в предположении, что новые компьютеры в сети не появляются и компьютеры из сети не удаляются.Будем рассматривать ? как параметр управления. Рассмотрим задачу минимизации затрат во время эпидемии. В качестве целевой функции рассмотрим следующий функционал: I(t) ?(t)) dt где: - плата за компьютеры, которые подверглись заражению Предположим что возможности установки нового антивируса, ограничены, то есть, будем рассматривать ?, удовлетворяющее ограничению: 0??(t)? Рассмотрим решение в виде: D(t)= (t) подставим в уравнение: (t) = ?I(t) (t) , = ?I(t), = d? , отсюда следует, что D(t)= d? так как D(0)=0, =0, то есть: D(t)= d? таким образом D(t)>0, так как подынтегральная функция положительна.Задачу (7) - (10) будем называть задачей оптимального управления в форме Понтрягина с фиксированным временем и свободным правым концом. :R ? ? > R-функции n r 1 переменных, : > - функция n переменных, ?: R ? ? > R-вектор-функция n r 1 переменных, Вектор-функция x(.) называется фазовой переменной, u(.)-управлением. Уравнение (8), называемое дифференциальной связью, должно выполняться во всех точках непрерывности управления u(.) на интервале (, ).Пусть (оптимальный процесс в задаче оптимального управления, функции , и их частные производные по непрерывны в множестве , где окрестность множества а функция (условие гладкости).1.Составить уравнения для сопряженных переменных p(t): 2.Выписать краевые условия для сопряженных переменных(условие трансверсальности)Для решения задачи (3)-(6) применим принцип максимума Понтрягина: 1)Выпишем сопряженные уравнения: = (?I(t) ?(t))-?I(t) Из условия (5) следует, что оптимальное управление имеет следующую структуру ?= t?( (12) ? принимает значение если принимает отрицательные значения. ? принимает значение 0, если принимает положительные значения. ? принимает значение, если равно 0 на некотором интервале времени.Если существует ненулевой интервал (, ) такой, что функция переключения G(t)=0 для всех t ? (, ), то соответствующая экстремаль (S,I, ) называется особым, а управление - особым управлением. Из условия (11) особое управление не определяется. Что бы найти его, будем дифференцировать функцию переключения G(t) до тех пор, пока не появится управление. Известно, что управление при этом может появиться только у четной производной функции G(t): (t)=0 следовательно = 0(12) Управление появилось в (14).2.В силу леммы 5 на заключительном интервале, управление равно 0. 3.Вычисляем фазовые и сопряженные переменные. 7.Опять вычисляем ближайший момент к , в котором функция G(t) обращается в ноль. Построим решения данной системы: Рис. Видим что больше переключений нет, таким образом мы поулчили решение на всем отрезке: Рис. Ищем точку пересечения: Дальше вычисляем значения фазовых и сопряженных переменных в точке переключения: Решаем систему дифференциальных уравнений с управлением и вычисленными значениями фазовых и с поряженных переменных: Строим решения новой системы: Рис.В дипломной работе изучена задача оптимизации для PSIDR модели с одномерным управлением.
План
Оглавление
Введение
Глава 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 описывается алгоритм построения численного решения.
Вывод
В дипломной работе изучена задача оптимизации для 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.Jose Roberto Castilho Piqueira, Betyna Fernandez Navarro and Luiz Henrique Alves Monteiro.Epidemiological Models Applied to Viruses in Computer Networks. Journal of Computer Science 1 2005, (1): 31-34