Последовательный анализ трафика вычислительной сети тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Журавлев Денис Николаевич

ПОСЛЕДОВАТЕЛЬНЫЙ АНАЛИЗ ТРАФИКА ВЫЧИСЛИТЕЛЬНОЙ СЕТИ

01.01.09 — дискретная математика и математическая кибернетика

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

Петрозаводск 2004

Работа выполнена в Институте прикладных математических исследований Карельского научного центра РАН.

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

Официальные оппоненты: доктор физико-математических наук, профессор Е. В. Морозов, кандидат физико-математических наук, доцент С. Л. Сергеев.

Ведущая организация: Петрозаводский государственный университет.

Защита состоится 28 декабря 2004 г. в 14 часов 15 мин. на заседании диссертационного совета К 002.142.01 в Институте прикладных математических исследований Карельского научного центра РАН по адресу: 185610, Петрозаводск, ул. Пушкинская,

С диссертацией можно ознакомиться в библиотеке Карельского научного центра РАН.

11.

г.

Ученый секретарь диссертационного совета К 002.142.01

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

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

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

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

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

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

Цель исследования. Целью диссертации является разработка и исследование методов вероятностной диагностики, предназна-

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

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

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

Основные положения диссертации, выносимые на защиту. На защиту выносятся следующие положения:

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

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

тегиях для случая явного задания функции распределения шаблона атаки.

3. Задача динамического распределения нестраничной памяти сведена к задаче оптимальной остановки. Решение данной задачи найдено в классе однопороговых правил остановки.

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

Связь работы с крупными научными программами, темами. Основные результаты, представленные в данной диссертации, были получены в ходе выполнения проекта "Применение теоретико-игровых методов в задачах поиска, распределения и защиты информационных ресурсов в компьютерных сетях" в рамках программы № 4 фундаментальных исследований Отделения математических наук РАН "Математические и алгоритмические проблемы информационных систем нового поколения".

Апробация результатов диссертации. Результаты работы были представлены в докладах на VII Международной конференции по электронным публикациям "EL-Pub2002" (Новосибирск, 2002 г.), International Workshop "Networking games and resource allocation" (Петрозаводск, 2002 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), Семинаре "Неделя Финской Информатики" (Петрозаводск, 2003 г.), VI Международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004 г.).

Публикация результатов. Основные результаты диссертации опубликованы автором в семи работах, из них одна статья в журнале "Программирование", две статьи в сборниках трудов

Института прикладных математических исследований Карельского научного центра РАН, тезисы четырех докладов на международных, всероссийских и региональных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Общий объем диссертации составляет 119 страниц. Список литературы содержит 99 наименований.

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

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

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

где а, к > 0.

Для определения момента изменения показателя Парето функции распределения ON и OFF периодов, применяется метод последовательного анализа (метод кумулятивных сумм). Этот

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

если х > к\ если х < к,

F0(x)

метод представляет собой многократно применяемый последовательный анализ Вальда А, а именно — последовательный критерий отношения вероятностей для двух простых гипотез Но (нет разладки) и /:'\ (есть разладка). Пусть в —случайная величина, принимающая значения 0,1,..., а наблюдения ■ ■ таковы, что при условии в = п величины

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

_ /1 — (х)" > если х -

[0, если х < к,

где к > 0, а > 0.

Независимые, одинаково распределенные случайные величины

?П!£п+1>•••

также имеют Парето функцию распределения

=/МгЛ еслих>*; [О, если х < к,

где к > 0, £ > 0 и а ф /3.

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

Р\{Хп)

Sn — 5„_i

Ро(яп)'

которая в последовательном критерии отношения вероятностей сравнивается на каждом шаге с двумя порогами: е и /х, где ц > е > 0. Если на шаге п значение 5„ > ц, то принимается гипотеза #ь если 5„ < е, то принимается Щ, а если е < 5П < ц, то выполняется п + 1 наблюдение. То есть обнаружение осуществляется посредством правила остановки, имеющего следующий вид:

т = щ£ {п > 1: 5П > ц).

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

1. среднее время задержки определения разладки

Хорошее правило остановки определяется таким уровнем при котором среднее время до ложной тревоги М^т не было меньше некоторого значения R > 0, выбираемого экспертом, а время задержки М0т было минимальным.

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

Теорема 2.2.1. Если ¡3 < а и выполнено условие

Mqt = М {т\9 = 0};

2. среднее время до ложной тревоги

МооТ = М {т\в = оо}.

то

т

Теорема 2.2.2. Если а < /3 и выполнено условие 'сЛ / /3

яю

(Г^-Н (¥)А

<1,

Мот =

Теорема 2.3.1. Если ¡3 < а и выполнено условие

то

Мп

0 — / ч Теорема 2.3.2. Если а < ¡3 и выполнено условие

то

(I)' + .

<1,

МооГ =

1

Полученный результат позволяет использовать метод кумулятивных сумм для определения аномалий типа "отказ в обслуживании". Главным недостатком аномального подхода является большое количество ложных тревог. Выбор конкретного значения параметра Я позволяет ограничивать среднее количество

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

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

Решения данной задачи можно найти как решение следующей игры. Пусть имеются два игрока 1 и 2, которые хотят угадать значение 5 реализации случайной величины. При этом известно, что данная случайная величина принимает значения на интервале [0,1] и имеет функцию распределения 00). Если игрок 1 высказал предположение х, а игрок 2 предположение у, то

1. если х < в < у, то игрок 2 выигрывает Ь,

2. если 5 < х < у, то игрок 1 выигрывает а,

3. если у < в < х, то игрок 1 выигрывает Ь,

4. если в <у <х, то игрок 2 выигрывает а,

5. для всех остальных случаев игроки имеют нулевой выигрыш.

Тогда выигрыш игрока 1 при условии, что игроки сделали предположения равен

Для описанной выше игры получен следующий результат.

Теорема 3.2.1. В симметричной антагонистической игре с функцией выигрыша Н(х, у) существует решение в смешанных стратегиях вида (v(x),u(y))l где

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

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

запроса на память. Проведем нормировку и будем рассматривать величины (заявки)

(2)

где г = 1,..., М.

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

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

выборов N игроков, рассмотрим следующую игру. Пусть

конечные совокупности независимых одинаково распределенных случайных величин с равномерной функцией распределения на интервале [0,1]. Каждый игрок г, где г е М, г < N. наблюдает за траекторией процесса и в любой момент может прекратить наблюдение, то есть согласиться с предложенной величиной. Случайный момент времени который будем предполагать моментом остановки, является стратегией игрока.

Обозначим через

функцию выигрыша 1-го игрока в случае остановки на шаге Будем рассматривать следующие варианты функции <р:

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

Оптимальные стратегии т,* будем искать среди однопорого-вых стратегий вида

1. =

1, если ц>[х\) > а; п(а) = тп, если ip(x\) < а,...,<р(х[,...,zjj > а; М, если у(х[) < а,...,<р{х\,...,х1т) < а,

где х}- — наблюдение случайной величины

То есть для заданной функции необходимо определить порог а*, такой, что, если впервые выполнено условие (р(х\,...,х}) > а*, то следует остановиться на этом шаге, иначе необходимо получить следующее наблюдение и рассматривать функцию 1р(х[,..., !).

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

Так, например, для совокупности случайных величин

где а е [0,1).

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

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

значение -Ь, а белому а, где а, Ъ € N. Обозначим данное состояние урны как (т,р). Пусть из урны осуществляется равновероятный выбор без возвращения.

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

Данная игра является обобщением известного случая игры,

Введем обозначение

V(m,p) = max(A(m,p),N(m,p)),

где

А(т,р) = + V(m,p - 1)) + J^-(-b + V(m - 1,р)) (4)

т + р т

и

= 7^V(m>p ~ + ~ (5)

т + р т + р

Тогда А(т,р) — это математическое ожидание всего выигрыша игрока при условиях: урна первоначально находилась в состоянии (т,р), игрок соглашается с первым шаром и его дальнейшие действия определяются оптимальной стратегией (если урна находится в состоянии (т',р), то оптимальная стратегия игрока: соглашаться с шаром, если и отказываться от

шара в противном случае).

N(m,p) определяется аналогично при условии, что игрок не соглашается с первым шаром.

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

В случае, когда значение одного черного шара равно сумме значений белых шаров с обратным знаком, верна следу-

ющая теорема.

Теорема 4.3.1. Если Ь = ап, а,п € N и ар> Ьт, то

Теорема 4.3.5. Если а,Ь & N для урны (т,р) и игрок действует согласно оптимальной стратегии, то последний шар с которым согласится игрок, будет белым.

Теорема 4.4.1. Если Ь = ап, а,п б N и ар > Ьт, то

У{т,р) = д

+ {ар ~Ьт)-д, (6)

(?)

У(т + 1,р + п) > У(т,р).

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи

1. Журавлев Д. Н. Определение моментов изменения степенного параметра распределения Парето методом кумулятивных сумм // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2002, выт. 3, с. 28-41.

2. Мазалов В. В., Журавлев Д. Н. О методе кумулятивных сумм в задаче обнаружения изменения трафика компьютерных сетей // Программирование, 2002, № 6, с. 156-162.

3. Журавлев Д. Н. Оптимальная политика выбора для урно-вой схемы с двумя типами шаров // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2004, вып. 5, с. 19-32.

Тезисы докладов

4. Zhuravlev D. Disorder time determination for the Pareto distribution fonction using the method of cumulative sums // Applied stochastic models and information processes, 2002, 2, pp. 159-160.

5. Мазалов В. В., Журавлев Д. Н. Применение метода кумулятивный сумм для определения аномалий HTTP транзакций, http://www.ict.nsc.ru/ws/elpub2002/4511.

6. Журавлев Д. Н. Применение теоретико-игровых методов для определения структуры сетевого трафика // Обозрение прикладной и промышленной математики, 2003, т. 10, выып. 2, с. 469-470.

7. Журавлев Д. Н. Оптимальная политика одобрения в ур-новой модели // Обозрение прикладной и промышленной математики, 2004, т. И, вып. 3, с. 635-636.

Изд. лиц. № 00041 от 30.08.99. Подписано в печать 21.09.04. Формат 60х84'/16. Бумага офсетная. Гарнитура «Times». Печать офсетная. Уч.-изд. л. 1,0. Усл. печ. л. 1,0. Тираж 100 экз. Изд. № 76. Заказ № 458

Карельский научный центр РАН 185003, Петрозаводск, пр. А. Невского, 50 Редакционно-издательский отдел

»24505

Введение.

Глава I. Принципы моделирования вычислительной сети.

§ 1. Основные сложности построения математической модели вычислительной сети.

§ 2. Теорема об ON/OFF процессе.

Глава II. О методе кумулятивных сумм в задаче обнаружения изменения свойств трафика.

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

§ 2. Определение аналитического вида Мог для распределения Парето.

§ 3. Определение аналитического вида МооТ для распределения Парето.

§ 4. Имитационное моделирование процедуры поиска разладки.

§ 5. Применение метода кумулятивных сумм для обнаружения компьютерных атак.

Глава III. Теоретико-игровые методы в задачах исследования трафика.

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

§ 2. Определение момента прекращения поиска сигнатуры

§ 3. Определения оптимального поведения для повышения уровня загрузки телекоммуникационного оборудования

Глава IV. Задача оптимального выбора для памяти телекоммуникационного оборудования.

§ 1. Использование урновых моделей при проектировании ATM коммутатора.

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

§ 3. Оптимальная политика выбора в урновой модели с двумя типами шаров.

§ 4. Парадокс сравнения урн.

В настоящее время существует два основных подхода для моделирования трафика вычислительной сети. При первом подходе фиксируется время и измеряются текущие характеристики сети. Далее, исходя из полученных данных, строится и исследуется математическая модель [36, 81].

Основными недостатками данного подхода являются:

1. привязанность модели ко времени;

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

3. большой размер сети делает сложным получение статистически значимого результата (в смысле "репрезентативности выборки").

Второй подход известен как принцип экономии (principle of parsimony) [50, 56]. Его основная идея состоит в нахождении таких характеристик, которые остаются инвариантными для различных сетей. Поиск подобных характеристик привел к достаточно неожиданным результатам. Прежде всего, было обнаружено большое количество параметров с бесконечной дисперсией (Noah effect) [47, 80, 93, 94]. К таким параметрам относятся: время работы процессора, размеры файлов, времена между приходами пакетов имели функцию распределения с тяжелым хвостом.

Вторая инвариантная характеристика была впервые обнаружена в 1993 году группой ученых (Leland W., Taqqu М., Willinger W. и Wilson D.), которые исследовали Ethernet-трафик в сети Bellcore и обнаружили, что он обладает самоподобием [66]. Под самоподобием подразумевается повторяемость распределения нагрузки во времени при различных масштабах. Это означает, что, если мы нарисуем график зависимости плотности информационного потока от времени, взяв за единицу измерения секунду, минуту, час и так далее, то каждый раз получим практически одинаковые диаграммы.

После того, как данный феномен был доказан, большое количество исследователей занялись проблемой самоподобия сетевого трафика. Например, сразу после введения в использование World Wide Web (WWW) появились публикации на тему самоподобия трафика и в этой системе [41, 47, 79]. Удалось определить, что возможная причина такого странного эффекта заключается в особенностях распределения файлов по серверам, их размерах, а также в типичном поведении пользователей [47, 67, 78, 95, 97]. Еще одна причина была обнаружена в ходе недавних исследований, проведенных под руководством Фенга В. и Тиннакорнсрисуфа П. В данном исследовании был поставлен под сомнение протокол TCP: то есть заведомо не проявляющий признаков самоподобия трафик, пройдя через стек протоколов TCP/IP, модулируется последним и превращается в самый настоящий "сетевой фрактал". Особенно сильно этот эффект заметен в высокоскоростных сетях [18].

Также было замечено, что агрегированный самоподобный процесс обладает свойством долговременной зависимости (Joseph Effect или long-range dependence) [47, 54, 83]. То есть, будущее процесса определяется его прошлым, причем с убывающей степенью влияния по мере того, как прошлое удалено от настоящего. Таким образом, процесс с долговременной зависимостью как бы медленно "забывает" свое относительно давнее прошлое по мере продвижения в будущее.

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

1. суперпозиция ON/OFF процессов [54];

2. суперпозиция M/G/oo процессов, где времена обслуживания имеют функцию распределения с тяжелым хвостом [42].

В данной работе используется ON/OFF процесс: идеализированный источник пакетов переключается между ON состоянием, в котором происходит передача данных с постоянной интенсивностью, и OFF состоянием молчания. Длины ON и OFF периодов независимы; ON периоды одинаково распределены с функцией распределения, имеющей тяжелый хвост, то же справедливо для OFF периодов. На практике, как правило, если известно, что распределение имеет тяжелый хвост, то работают с Парето функцией распределения с дополнительным ограничением на показатель а < 2 [47, 78].

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

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

Следующий тип задач, рассмотренный в данной работе, — это задачи оптимизации работы телекоммуникационного оборудования. В данной работе решаются две задачи, данного типа:

1. задача динамического распределения нестраничной памяти;

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

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

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

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

Во второй главе для определения момента изменения показателя Парето функции распределения ON и OFF периодов применяется метод последовательного анализа (метод кумулятивных сумм). В отличие от классических методов математической статистики, в которых число производимых наблюдений заранее фиксируется, методы последовательного анализа характеризуются тем, что момент прекращения наблюдения (момент остановки) является случайным и определяется наблюдателем в зависимости от значений наблюдаемых данных [20, 34]. Качество правила остановки метода кумулятивных сумм оценивается следующими характеристиками: среднее время задержки определения разладки Мог и среднее время до ложной тревоги Моот. Как правило, получить Мот и МооТ в аналитическом виде удается лишь в специальных случаях [20]. В параграфах II.2, II.3 удалось получить аналитический вид данных характеристик.

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

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

Основные результаты диссертации:

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

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

3. Задача динамического распределения нестраничной памяти сведена к задаче оптимальной остановки. Решение данной задачи найдено в классе однопороговых правил остановки.

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

Основные результаты диссертации опубликованы автором в 7 работах [7, 8, 9, 10, 17, 16, 99], из них 1 статья в журнале "Программирование" [17], 2 статьи в сборниках трудов Института прикладных математических исследований Карельского научного центра РАН [7, 10], 4 тезиса докладов на международных, всероссийских и региональных конференциях [8, 9, 16, 99]. Результаты также докладывались на VII Международной конференции по электронным публикациям "EL-Pub2002" (Новосибирск, 2002 г.), International Workshop "Networking games and resource allocation" (Петрозаводск, 2002 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), Семинаре "Неделя Финской Информатики" (Петрозаводск, 2003 г.), VI Международной конференции "Вероятностные методы в дискретной математике" (Петрозаводск, 2004 г.).

Основные результаты, представленные в данной диссертации, были получены в ходе выполнения проекта "Применение теоретико-игровых методов в задачах поиска, распределения и защиты информационных ресурсов в компьютерных сетях" в рамках программы № 4 фундаментальных исследований Отделения математических наук РАН "Математические и алгоритмические проблемы информационных систем нового поколения".

В диссертации принята двойная нумерация параграфов и тройная нумерация теорем, лемм, формул и замечаний. Это значит, что параграф III.4 является четвертым по порядку в главе III, а теорема 1.2.3 является третьей по порядку в параграфе 1.2. и

1. Айвазян С. А. Сравнение оптимальных свойств критериев Неймана-Пирсона и Вальда // Теория вероятностей и ее применение, 1959, 4, вып. 1, с. 86-93.

2. Березовский Б. А., Гнедин А. В. Задача наилучшего выбора. -М.: Наука, 1984.

3. Боровков А. А. О субэкспоненциальных распределениях и асимптотике распределения максимума последовательных сумм // Сибирский математический журнал,2002, 43, № 6, с. 1235-1263.

4. Блэк Ю. Сети ЭВМ: протоколы, стандарты, интерфейсы. -М.: Мир, 1990.

5. Вальд А. Последовательный анализ. -М.: Физматгиз, 1960.

6. Ганьжа Д. Коммутаторы ATM // LAN, № 4, 1997.

7. Журавлев Д. Н. Определение моментов изменения степенного параметра распределения Парето методом кумулятивных сумм // Тр. Института прикл. матем. ис-след. Карельского НЦ РАН, 2002, вып. 3, с. 28-41.

8. Журавлев Д. Н. Применение теоретико-игровых методов для определения структуры сетевого трафика // Обозрение прикладной и промышленной математики,2003, т. 10, вып. 2, № 2, с. 469-470.

9. Журавлев Д. Н. Оптимальная политика одобрения в ур-новой модели // Обозрение прикладной и промышленной математики, 2004, т. 11, вып. 3, с. 635-636.

10. Журавлев Д. Н. Оптимальная политика выбора для ур-новой схемы с двумя типами шаров // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2004, вып. 5, с. 19-32.

11. Золотов С. Протоколы Internet. -СПб.: BHV, 1998.

12. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения -М.: Наука, 1976.

13. Леман Э. Проверка статистических гипотез. -М.: Наука, 1979.

14. Лукацкий А. В Безопасность сети банка глазами специалистов // Аналитический банковский журнал, 1999, 1-2, с. 104-106.

15. Моменты остановки и управляемые случайные блуждания / Мазалов В. В., Винниченко С. В. -Новосибирск: Наука, 1992.

16. Мазалов В. В., Журавлев Д. Н. Применение метода кумулятивных сумм для определения аномалий HTTP транзакций, http://www.ict.nsc.ru/ws/elpub2002/4511.

17. Мазалов В. В., Журавлев Д. Н. О методе кумулятивных сумм в задаче обнаружения изменения трафика компьютерных сетей // Программирование, 2002, № 6, с. 156162.

18. Митилино С. Фрактальная катастрофа TCP/IP // Компьютерное Обозрение, 2001, № 9.

19. Моттль В. В., Мучник И. Б. Скрытые марковские модели в структурном анализе сигналов. -М.: Физматлит, 1999.

20. Никифоров И. В. Последовательное обнаружение изменения свойств временных рядов. -М.: Наука, 1983.

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

22. Теория игр: Учеб. пособие для ун-тов / Петросян Л. А., Зенкевич Н. А., Семина Е. А. -М.: Высш. шк., Книжный дом "Университет", 1998.

23. Прудников А. П., Брычков Ю. А., Маричев О. И. Интегралы и ряды. Элементарные функции. -М.: Наука, 1981.

24. Соколов А. В. Математические модели и алгоритмы оптимального управления динамическими структурами данных / ПетрГУ. Петрозаводск, 2002.

25. Спицер Ф. Принципы случайного блуждания. -М.: Мир, 1969.

26. Феллер В. Введение в теорию вероятностей и ее приложения. -М.: Мир, 1984. Т. 1.

27. Феллер В. Введение в теорию вероятностей и ее приложения. -М.: Мир, 1967. Т. 2.

28. Ширяев А. Н. Обнаружение спонтанно возникающих эффектов // Докл. АН СССР, 1961, 138, № 4, с. 799-801.

29. Ширяев А. Н. Задача скорейшего обнаружения нарушения стационарного режима // Докл. АН СССР, 1961, 138, № 5, с. 1039-1042.

30. Ширяев А. Н. Об оптимальных методах в задачах скорейшего обнаружения // Теория вероятностей и ее применение, 1963, 8, вып. 1, с. 26-51.ш

31. Ширяев А. Н. К обнаружению разладки производственного процесса // Теория вероятностей и ее применение, 1963, 8, вып. 3, с. 264-281.

32. Ширяев А. Н. К обнаружению разладки производственного процесса // Теория вероятностей и ее применение, 1963, 8, вып. 4, с. 431-443.

33. Ширяев А. Н. Некоторые точные формулы в задаче о "разладке" // Теория вероятностей и ее применение, 1965, 10, вып. 2, с. 380-385.

34. Ширяев А. Н. Статистический последовательный анализ. -М.: Наука, 1976.

35. Allman М., Paxson V. On estimating end-to-end network path properties // Proceedings of ACM SIGCOMM '99, 1999.

36. Almeida J., Almeida V., Yates D. Measuring the behavior of a World Wide Web server // Proceedings of the Seventh IFIP Conference on HPN, 1997.

37. Amoroso E. Intrusion Detection. An introduction to Internet surveillance, correlation, trace back, traps and response. Intrusion. Net Books, 1999.

38. Anderson J. P. Computer Security Threat Monitoring and Surveillance, James P. Anderson Co., Fort Washington, 1980.

39. Bagshaw M., Johnson R. A. Sequential procedures for detecting parameter changes in a time-series model // Amber. Statist. Assoc., 1977, 72, № 359, pp. 593-597.

40. Belkovskii D. V., Garnaev A. Y. A competitive prediction number game under unsymmetrical conditions // Game Theory and Application, 2004, 10, pp. 22-30.

41. Barford P. R. Modeling, measurement and performance of world wide web transactions, Dissertation, 2001.

42. Borst S., Zwart B. Fluid queues with heavy-tailed M/G/oo input // SPOR Report Eindhoven University of Technology, 2, 2001.

43. Boyce W. .M. Stopping rules for selling bonds // Bell J. Econ. Mgmt. Sci., 1, 1970, pp. 27-53.

44. Boyce W. M. On a simple optimal stopping problem // Discrete Math., 5, 1973, pp. 297-312.

45. Campbell I. A. A note an optimal-fit method for dynamic allocation of storage // The Computer Journal, 14, № 1, 1971, pp. 7-9.

46. Chen R. W., Zane A., Odlyzko A. M., Shepp L. A. An optimal acceptance policy for an urn scheme // SI AM J. Discrete Math., 11, № 2, 1998, pp. 183-195.

47. Crovella M., Bestavros A. Self-similarity in world wide web traffic: evidence and possible causes // IEEE/ACM Transactions on networking, 1997, 5, № 6, pp. 835-847.

48. Crovella M., Taqqy M. Estimating the heavy tail index from scaling properties // Methodology and Computing in Applied Probability, 1999, 1, № 1, pp. 55-79.

49. Denning D. E. Views for multilevel database security / / IEEE Trans. Software Eng., 1987, 13, № 2, pp. 129-140.

50. Erramilli A., Narayan 0., Willinger W. Experimental queuing analysis with long-range dependent packet traffic // IEEE/ACM Transactions on Networking, 1996, 4, pp. 209223.

51. Goel A. L., Wu S. M. Determination ARL and a contour nomogram for CUSUM charts to control normal mean // Technometrics, 1971, 13, № 2, pp. 221-230.

52. Goldie C. M., Kluppelberg C. Subexponential distributions http:// citeseer.ist.psu.edu/goldie97subexponential.html

53. Goldsmith P. L., Whitfield H. Average run lengths in cumulative chart quality control schemes // Technometrics, 1961, 3, № 1, pp. 11-80.

54. Heath D., Resnick S., Samorodnitsky G. Heavy tails and long range dependence in on/off processes and associated fluid models // Mathematics of Operations Research, 1998, № 23, pp. 145-165.

55. Ilgun K., Kemmerer R. A., Porras P. A. // IEEE Trans. Software Eng., 1995, 21, № 3.

56. Jefferys W. H., Berger J. O. Ockham's razor and Bayesian analysis // American Scientist, 1992, 80, pp. 64-72.

57. Johnson N. L., Kotz S. Urn model and their application, New York, Wiley, 1978.

58. Johnson R. A. The effect of serial correlation on the performance of cusum tests // Technometrics, 1975, 17, №1, pp. 73-80.

59. Kemp K. W. Formal expressions which can be used for the determination of operating characteristic and average sample number of a simple sequential test //J. Roy. Statist. Soc. B., 1967, 29, № 2, pp. 248-262.

60. Kemperman J. The general one-dimensional random walk // S-Gravenhage, 1950, pp. 111.

61. Kiefer J., Weiss L. Some properties of generalized sequential probability ratio test // Ann. Math. Statist., 1957, 28, № 1, pp. 57-74.

62. Kleinrock L., Yemini Y. An optimal adaptive scheme for multiple access brodcast communicatios

63. C'78, 1, 1978, pp. 7.2.1-7.2.5.

64. Kuzmanovic A., Knightly E. Low-rate TCP-targeted denial of service attack, 2003, http: / / www.acm.org/sigcomm/sigcomm2003/ papers / p75-kuzmanovic.pdf.

65. Leland W. E, Taqqu M. S, Willinger W., Wilson D. V. On the self-similar nature of ethernet traffic // IEEE/AMC transactions of networking, 1994, 2, № 1, pp. 1-15.

66. Liebovitch L. S., Fischbarg J., Koniarek J. P. Ion channel kinetics: a model based on fractal scaling rather than markov processes // Mathematical Biosciences, 1987, 84, pp. 37-68.

67. Lorden G. On exceeds over the boundary // Ann. Math. Statist., 1970, 41, № 2, pp. 520-527.

68. Lorden G. Procedures for reacting to a change in distribution // Ann. Math. Statist., 1971, 42, № 6, pp. 18971908.

69. Lorden G., Eisenberg I. Detection of failure rate increases // Technometrics, 1973, 15, № 1, pp. 167-175.

70. Lou X. C., Willsky A. S.,Verghese G. C. Failure detection with uncertain systems // Proceedings American Control Conference, 1983.

71. Mahajan R., Floyd S., Wetherall D. Controlling high-bandwidth flows at the congested router // Proceedings of IEEE ICNP '01, Riverside, 2001.

72. Mazalov V. V. Method of cumulative sums and problems of optimal control by technological processes // Software Engineering and Knowledge Engineering, 1997, 7, № 2, pp. 216-229.

73. Nadler J., Robbins N. B. Some characteristics of Page's twosided procedure for detecting a change in a location parameter // Ann. Math. Statist., 1971, 42, №2, pp. 538551.

74. Page E. S. Continuous inspection schemes // Biometrika, 1954, 41, № 1, pp. 100-115.

75. Page E. S. An improvement to Wald's approximation for some properties of sequential tests //J. Roy. Statist. Soc. B, 1954, 16, № 1, pp. 136-139.

76. Page E. S. Controlling the standard deviation by cusum and warning lines // Technometrics, 1963, 5, № 3, pp. 307-315.

77. Park K., Kim G., Crovella M. On the relationship between file sizes, transport protocols, and self-similar network traffic // Proceedings ot the Fourth International Conference on Network Protocols, 1996, pp. 171-180.

78. Paxson V., Floyd S. Why we don't know how to simulate the Internet // Proceedings of the 1997 Winter Simulation Conference, 1997.

79. Paxson V., Floyd S. Wide-area traffic: The failure of poisson modeling // IEEE/ACM Transactions on Networking, 1995, 3, № 3, pp. 226-244.

80. Paxson V. End-to-end Internet packet dynamics // Proceedings of ACM SIGMOMM'97, 1997.

81. Pollak M., Siegmund D. Approximations to the expected sample size of certain sequential tests // Ann. Statist., 1975, 3, № 6, pp. 1267-1282.

82. Racheva-Iotova B., Samorodnitsky G. Long range dependence in heavy tailed stochastic processes, http://www.orie.cornell.edu/abstracts/trl301-abstract

83. Reynolds M. R. Approximations to the average run length in cumulative sum control charts // Technometrics, 1975, 17, № 1, pp. 65-71.

84. Roberts S. W. Control charts tests based on geometric moving average // Technometrics, 1959, 1, № 3, pp. 239250.

85. Rohadgi V. K. On lattice path with diagonal steps // Canad. Math. Bull., 1967, 4, № 3, pp. 470-472.

86. Sakaguchi M. Three-player game of "Keep-or-Exchange" // Game Th. Appl., 2004, 10.

87. Samorodnitsky G. Long range dependence, heavy tails and rare lecture notes. MaPhySto, Centre for Mathematical Physics and Stochastics, Aarhus, 2002.

88. Shepp L. A. Explicit Solutions to Some Problems of Optimal Stopping // Ann. Math. Statist., 1969, 40, pp. 993-1010.

89. Siegmund D. Error probability and average sample number of the sequential probability ratio test // J. Roy. Statist. Soc. B., 1975, 37, № 3, pp. 394-401.

90. Taylor H. M. A stopped brownian motion formula // Ann. Probab, 1975, 3, № 2, pp. 234-246.

91. Wang H., Zhang D., Shin K. Detecting syn flooding attacks // Proceedings of IEEE INFOCOM '2002, 2002.

92. Willinger W, Taqqu M., Leland W, Wilson D. Self-similarity in high-speed packet traffic: analysis and modeling of ethernet traffic measurements // Statistical Science, 1995, 10, pp. 67-85.

93. Willinger W., Paxson V., Taqqu M. Self-similarity and heavy tails: structural modeling of network traffic. / A practical guide to heavy tails: statistical techniques and application, 1996, pp. 17-53.

94. Willinger W., Taqqu M., Sherman R., Wilson V. Self-similarity through high-variability: statistical analysis of ethernet LAN traffic at the source level // IEEE/ACM Transactions on the Networking, 1997, 5, № 1, pp. 71-86.

95. Willinger W., Paxson V. Where Mathematics meets the Internet // Notices of the American Mathematical Society, 1998, 45, pp. 961-970.

96. Willinger W., Paxson V. Discussion of "Heavy Tail Modeling and Teletraffic Data" by SR Resnick // Ann. of Stat., 1997, 25, № 5, pp. 1805-1869.

97. Zeng G., Zhu H., Chlamtar I A novel queuing model for 802.11 wireless LANs // WNCG'03, 2003.

98. Zhuravlev D. Disorder time determination for the Pareto distribution function using the method of cumulative sums // Applied stochastic models and information processes, 2002, 2, pp. 159-160.