ПРОГРАММИРОВАНИЕ, 2014, No 6, с. 54-61
БЕЗОПАСНОСТЬ И ЗАЩИТА
УДК 681.32
МЕТОД КУМУЛЯТИВНЫХ СУММ ДЛЯ ОБНАРУЖЕНИЯ ВТОРЖЕНИЙ И БОРЬБЫ С НИМИ *
© 2014 г. В.В. Мазалов, H.H. Никитина
1 Институт прикладных математических исследований Карельского научного центра РАН 185035 Петрозаводск, ул. Пушкинская, 11 E-mail: mazalov@krc.kareJia.ru, nikitina@krc.karelia.ru Поступила в редакцию 21.03.2013
В работе рассматривается задача обнаружения момента вторжения в вычислительную систему и последующего изменения протокола обслуживания входного потока задач. Для обнаружения момента вторжения используется метод кумулятивных сумм. Приводятся аналитические выражения характеристик метода для случая распределения Бернулли. Предлагается протокол обслуживания, позволяющий отделять от общего входного потока задачи, сгенерированные в результате вторжения.
1. ВВЕДЕНИЕ
Проведение DOS-атаки (от англ. Denial of Service) на вычислительную систему заключается в том, что к регулярному входному потоку задач, генерируемому обычными пользователями, добавляется искусственный поток задач. При отсутствии атак ресурсы системы, как правило, позволяют своевременно обслуживать все регулярные задачи. Но при наличии искусственных задач во входном потоке снижается эффективность обслуживания, т.к. помимо регулярных задач приходится обслуживать и искусственные, поступающие с высокой интенсивностью и/или требующие значительного количества ресурсов. Система не способна обрабатывать все поступающие задачи. В результате возрастает количество отказов в обслуживании, что и является целью атаки. Таким образом, возникает две задачи: зарегистрировать момент вторжения и изменить протокол обслуживания задач так, чтобы продолжать обслуживать регулярные задачи в присутствии искусственного потока.
Предположим, что каждая задача характеризуется численной величиной. Если предположить, что данная характеристика задачи — случайная величина х, то регулярный и искусственный потоки будут иметь разные параметры распределений. Можно сделать вывод о наличии атаки, если зафиксировано изменение распределения потока задач. Момент изменения называется моментом разладки.
В работе [1] впервые было предложено использовать метод кумулятивных сумм для обнаружения момента изменения характеристик случайного процесса. Одним из примеров применения метода кумулятивных сумм является обнаружение момента изменения среднего значения неотрицательных, независимых, одинаково распределенных случайных величин {хп}, п = 1,2,.... Предполагается, что до момента разладки с.в. подчиняются распределению ^(х, ао), а начиная с момента разладки в > 0 хп ~ ^(х,а), где а = а0.
Согласно методу, описанному в [1], строится последовательность кумулятивных сумм
* Работа поддержана Отделением математических наук РАН и Российским фондом фундаментальных исследований (13-01-91158, 13-01-00033).
Sn = (Sn-1 + q(xn))+,
где z+ = max(0, z) q(x) = log ffs 00); So = s > 0
Вывод о наличии разладки делается на шаге ть, когда значение кумулятивной суммы впервые превышает заданное пороговое значение Ь:
ть = inf{n > 0 : Sn > b}.
(2)
Процесс обнаружения момента разладки характеризуется двумя основными характеристиками: ARL (Average Run Length) — среднее количество наблюдений до сигнала об обнаружении разладки при условии, что по факту разладка не произойдет никогда (9 = те); AD (Average Delay) — среднее количество наблюдений до сигнала при условии, что по факту разладка про-
9=0
начальном условии So = s выражения для характеристик ARL и AD можно записать в следующем виде:
ARL = jTO(s) = ЕДт,|9 = те}, (3) AD = jo (s)= Es {ть|9 = 0}. (4)
В работе [1] показано, что функция jTO(s) < те является решением интегрального уравнения типа Фредгольма. В частности, можно показать, что для кумулятивных сумм, имеющих линейную форму Sn = (Sn-i + xn — а)+, где а — const, уравнение имеет вид
j(s) = 1 + Es{I(0 < Si < b)j(Si)}+
+ Ps{Si = 0}j (0),
s < b. (5)
Здесь Es — обозначение математического ожидания, Ps — вероятностная мера при начальном So = s
9=0
В работе [2] была показана оптимальность метода кумулятитвных сумм в минимаксном смысле, в ряде работ были получены приближенные и аналитические выражения характеристик ARL и AD: в частности, численное решение для случая нормального распределения [3], численные и аналитические решения для случая экспоненциального распределения [4, 6, 5], распределений с «тяжелыми хвостами» [7] и др.
В данной работе исследуется случай распределения Бернулли. Предполагается, что поступившая в систему задача характеризуется величиной 1 или 0 с вероятностью, соответствен-
но, ао или 1 — ао. Подобная характеристика может описывать множество ситуаций, возникающих на практике в вычислительной системе: например, вновь пришедшая задача с вероятно-ао
1 — ао
наличии вторжения интенсивность входного потока увеличивается, и вероятность постановки в очередь возрастает до а > а0.
В части 2 выводятся аналитические выражения для характеристик процесса обнаружения разладки ARL и АБ, полученные решением уравнения (5). В части 3 приводятся результаты моделирования входного потока заявок в вычислительной системе, в котором наблюдается разладка, и предлагается новый протокол обслуживания после момента обнаружения, при котором из смешанного входного потока выделяются регулярные задачи.
2. АНАЛИТИЧЕСКОЕ ВЫРАЖЕНИЕ ХАРАКТЕРИСТИК ПРОЦЕССА
Рассмотрим последовательность дискретных независимых одинаково распределенных с.в. хп, п = 1, 2,..., имеющих распределение Бернулли с
ао
( 0, х < 0, ^(х) = I 1 —ао, 0 < х < 1, [ 1, х > 1.
В предположении, что после разладки с.в. имеют распределение Бернулли с известным параметром а = ао, выражение для вычисления кумулятивных сумм принимает вид
Sn = S^i + ln
а
'(1 —а)
i-Xn
а
'(1 — ао)
i-Xn
+
Далее будем предполагать а > а0. При а < а0 полученные в работе решения остаются верными после замены а0 = 1 — а0, а' = 1 — а.
Для удобства последующих выкладок приведем ^(хп) к линейному виду:
q(xn) = ln
aXn (1 — а) aXn (1 — ао)
i-xn
i-Xn
, а , 1 — а \ , 1 — а _
ln--ln -- Xn + ln --= YXn + в.
а0 1 — а0 / 1 — а0
По свойствам логарифма и в предположении а > ао, выполняются неравенства 7 > 0 в < 0 и 7 + в > 0.
Запишем функциональное уравнение для АИТ, пользуясь (5). Заметим, что
{0, если х1 = 0 и 8+в < 0,
в+в > 0, если х1 = 0 и в+в > 0, 8+7+в > 0, если х1 = 1.
Второе слагаемое (5):
ЕД/(0 <51 < Ь); (51)} = ^ Р* (51 = Л); (51)
0<к<Ь
= Рв(51 = в+7+в)/(в+7+в < Ь);(в+7+в) + + Рв(51 = в+в)/(0 < в+в < Ь);(в+в) = = ао/(в+7+в < Ь); (в+7+в) +
+ (1-ао)/(0 < в+в < Ь);(в+в).
Третье слагаемое (5):
Рв(51 = 0) = (1 - ао)/(в <-в).
Получаем линейное функциональное уравнение
;(в) = 1 + ао/(в+7+в < Ь);(в+7+в) + + (1 - ао)/(0 < в + в < Ь); (в+в) +
+ (1-ао)/(в < -в);(0), в < Ь.
Пользуясь свойствами вероятности и определением функции ;(в), запишем его в форме:
Г1 + ао; (в+7+в) + (1- ао); (в + в)+, ; (в) = < 0 < в < Ь,
0, в > Ь.
(6)
Аналогичный вид имеет уравнение для нахож-
ао а
ао а
ния констант в уравнении целыми числами и решим полученное разностное уравнение, рассматривая только целые значения переменной. В за-
ао а
принимать различные формы. Рассмотрим возможные случаи.
1. Пусть [7 + в] = [-в]- Без потери общности, положим -в = 1, Ь* = г = [г] = 1.
В новых обозначениях уравнение (6) принимает вид
(1 + ао; (в + 1) + (1-ао); (в-1)+,
;(в) = [ 0 < в < ь*,
[0, в > Ь*.
(7)
Для 0 < в < Ь* запишем систему рекуррентных уравнений:
(; (0) =1 + ао; (1) + (1-ао);(0),
; (п) = 1 + ао; (п+1) + (1-ао); (п-1),
; (Ь* -1) = 1 + ао; (Ь*) + (1 -ао); (Ь* -2), ;(Ь*) = 0.
(8)
(а) Пусть ао = 0.5. Обозначив ;(0) =
запишем рекуррентное выражение для ; (п), 0 < п < Ь:
Г ;(0) = *, ;(1) = t - 2, ;(2) = * - 6,
; (п) = * - 2(1+2 +...+п) = *-п(п+1),
;(Ь) = * - ь*(ь*+1).
Поскольку ;(Ь*) = 0 * = Ь*(Ь* + 1), и решение системы (8) имеет вид
;(п) = Ь*(Ь* + 1) - п(п+1). (9) ао = 0.5
Утверждение 1: Решение системы (8) ао = 0. 5
; (п) =
(2ао - 1)(Ь*-п) + и-0**1 - Й-ОГ1
(2ао - 1)2 0 < п < Ь*. (10)
Доказательство: Пусть ;(0) = ; (1) = * - Заметим, что функция (10) может быть записана в виде
;(п) = ' о
4ао* - (1 -ао)(1/ао - 1)п
(2ао - 1)2
ао(2п - 4* + 1)+ п + * + 1 (2ао - 1)2
,
и
где
г =
(1 —Ц>)(( ^ )Ь* — 1) + Ь*(2ар — 1) (2а0 — 1)2 '
№
п = 0 п = 1
зывает, что формула (11) верна. Пусть формула верна для п = г — 2 и п = г — 1. Подставим эти значения в рекуррентное уравнение системы (8) для
3 (г),г > 1
_ з(г-1) - 1 - (1-а0)Лг-2) =
ао
1 /(2ао-1)(Ь*-г+1) + ^Г* -00 ^ (2ао-1)2
(2ао - 1)(Ь*- г+2) + (1-"°ьГ+1 -
-1 - (1-ао)-
(2ао-1)2 ао(2ао- 1)(6*-г) + -
__"о
ао \ (2ао-1)2
(2ао - 1)(Ь* - г) + - Й-Ц^
__у_«О_а0
(2ао-1)2
п тт , п п ( 0 <а0 < 0.5,
2. Пусть 7 + в < — в, т.е. < _ или
[ а > 1 — а0,
0.5 < а0 < 1. Без потери общности, положим 7 + в = 1, Ь* = ,г = т+в. Пусть т = [г] > 1. В новых обозначениях уравнение (6) принимает вид
{1 + а03 (8 + 1)+(1 — а0 )3 (8 — т)+, 0 < 8 < Ь*,
0,8 > Ь*.
(12)
Для 0 < 8 < Ь* запишем систему рекуррентных уравнений:
(3(0) =1+а03(1) + (1 — а0)3(0),
3(т) =1+а03 (т + 1) + (1 —а0)3(0), 3(т + 1)=1+а03 (т+2) + (1 —а0)3 (1),
3(Ь* — 1)=1+а03 (Ь*) + (1 — а0)3 (Ь*— т —1), 13(Ь*) =0.
(13)
Для решения системы применим метод производящих функций. Введем функцию ф(г)
(здесь 3п = 3 (п)):
,, \ • п . Зо-1 -(1-ао)Зо ,
Ф(г) = У Зп* — Зо +----—
ао
п = о
+ 31 -1-(1-ао)Зо 2 + + Зт -1-(1-ао)Зо т+1 + + * + • • • + * +
ао
ао
+ Зк-1-(1-ао)3к-т к+1 + = + * + • • • —
ао
.. оо .. т
-1 £ + ^ф(*) - ^Зо £ *к-
ао ао ао
к=1 к=1
о
1-ао т + 1 \ г • к -* Т > Зк *
ао
^ • к . • • .1 *
У,Зк * + Зо — Зо +---- +
г—' ао * — 1
+ ф(*)(---- *
ао ао
* 1 - ао т+1\ 1-ао . *т+1 - *
\ 1 - ао . * -
)--Зо--
у ао * — 1
Получаем следующий вид производящей функции:
Ф(г) =
30а0(г — 1) — 30(1 —а0)(гт+1 — г) + г (а0 — г + (1 — а0)гт+1)(г — 1) .
Представим правую часть выражения в виде простых дробей для последующего разложения производящей функции в ряд
(а0 — г + (1 —а0)гт+1)(г — 1) (1 — а0 )гт+1 — г + а0
30
(г — 1)(а0 — г + (1 —а0)гт+1) г
(г — 1)((1 — а
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.