Models of describing the dynamics of blocking nodes of computer networks by viruses based on the use of percolation KINE.pdf Впервые кинетика развития вирусной эпидемии в адресном пространстве компьютерных сетей и блокировка их узлов были проанализированы с помощью принятых в биологии простых феноменологических SI и SIR моделей [1-3]. Под моделью SI распространения вирусов подразумевают, что любой из компьютеров, входящих в атакуемую сеть, может находиться в одном из двух состояний: уязвимом (S) и инфицированном (I). Согласно этой модели имеется сеть, состоящая из постоянного числа (N) компьютеров, причем N = S +1, а на каждом инфицированном узле может существовать только одна копия червя, которая случайным образом выбирает в доступном адресном пространстве потенциальную жертву с некоторой постоянной средней скоростью атак в единицу времени. В модели SIR сетевые узлы существуют в трех состояниях: уязвимом (S), зараженном (I) и невосприимчивом (R). Отметим, что узлы оказываются неуязвимыми только после излечения от инфекции, а N - общее число узлов сети - равно S + I + R. Вводя постоянную среднюю скорость иммунизации и атак в единицу времени, для описания динамики развития эпидемий можно получить системы дифференциальных кинетических уравнений [Ibid.], описывающих процесс распространения эпидемии вирусов. Кроме того, среди ранних публикаций можно упомянуть оригинальную работу [4], в которой для моделирования распространения вирусов применили гидродинамическую модель, и этот процесс рассматривался как протекание жидкости. Дальнейшее развитие кинетические модели SI и SIR получили в работах [5-7]. В [5] было рассмотрено два типа процессов в компьютерной сети: один определяется серверными инфицированными узлами сети, имеющими высокий темп интенсивности вредоносных атак, а другой - инфицированными узлами клиента, имеющими низкий темп интенсивности вредоносных атак. Инфекционные узлы сервера передают вирусы узлам клиента в компьютерной сети, которые, однако, могут излечиваться с течением времени, но при этом снова становится восприимчивыми к заражению, но с меньшей вероятностью. В работе [6] рассматривается кинетическая модель описания вирусных эпидемий в компьютерных сетях на основе представлений об эпидемиологическом пороге, времени ожидания заражения, факторе репликации (коэффициент размножения), вероятности заражения и иммунизации, времени неприкосновенности узла и т.д. В работе [7] были усовершенствованы математические модели распространения компьютерных вирусов в гетерогенной компьютерной сети, учитывающие ее топологические и архитектурные особенности. Обобщенная структура компьютерной сети рассматривалась на основе модели PSIDR: N = S(t) + I(t) + D(t) + R(t), где N - общее количество объектов 22 Модели описания динамики блокировки узлов вычислительных сетей вирусами в системе, S(t) - количество уязвимых объектов, I(t) - количество зараженных объектов, R(t) -количество вылеченных объектов, обладающих иммунитетом, D(t) -количество объектов, в которых обнаружен вирус. Учет топологических и архитектурных особенностей сетей осуществлялся за счет умножения некоторых членов кинетических дифференциальных уравнений на эмпирические поправочные коэффициенты. В частности, для топологии сети «звезда» член, учитывающий убыль (заражение) уязвимых объектов, умножался на коэффициент, равный 0,6. Общие вопросы развития эпидемий вирусов в компьютерных сетях были рассмотрены в работах [8, 9]. В частности, в [8] указывается на необходимость разработки стратегий защиты, неуязвимых к изменениям в топологии сети и не требующих знания механизмов развития эпидемии. Например, создание механизмов регулирования числа соединений между узлами в единицу времени и их ограничение при возникновении атак или разработка методов превентивной вакцинации. В статье [9] обсуждаются вопросы разработки контрмер, препятствующих распространению вирусов. Авторы работы утверждают, что выпуск обновлений для программного обеспечения после обнаружения уязвимостей не дает надежной гарантии по безопасности. Для повышения уровня защиты они предлагают идею, согласно которой в компьютерной сети необходимо выделить подсеть, где будет целенаправленно распространяться антивирус, задачей которого станет борьба с вирусами. В работе [10] проводится анализ четырех моделей распространения вирусов: классическая модель SI, независимая каскадная модель, динамическая модель распространения и модель, учитывающая топологию сетей. Сравнение результатов моделирования показало, что наиболее перспективными с точки зрения разработки механизмов защиты являются модели, основанные на описании графа сети. В работе [11] рассматривается модель развития вирусной эпидемии не с произвольным порядком распространения вирусов, а с учетом погрешности результатов атак вследствие воздействия вирусов на уже зараженные узлы сети. Для этого авторы представляют сеть в виде направленного вероятностного графа без петель, узлы которого описываются переменными, задающими вероятности их состояния (зараженный, иммунизированный, восприимчивый), а дуги задают взаимодействие между переменными графической модели. Вирусное распространение определяется характеристиками сети и похоже на действие клеточного автомата. В публикации [12] рассматривается модель описания развития вирусных эпидемий на основе стохастических моделей интерактивных цепей Маркова, в которых состояние узлов сети на каждом следующем шаге развития эпидемии зависит от его состояния и состояния соседей на предыдущем шаге, а сама сеть представляется в виде ненаправленного графа. Для анализа и моделирования эпидемий вирусов в компьютерных сетях можно использовать методы сопоставления. В работе [13] описано две модели: одна на основе авторегрессионного анализа, а другая на основе Фурье-анализа. Результаты анализа показывают приемлемую корреляцию между временем распространением вирусов. Авторегрессионный и Фурье-анализ представляют возможность предсказания усиления и ослабления тенденций в распространении определенного типа вируса при помощи накопленного опыта по другим эпидемиям. При описании топологии блокирования узлов сетей при распространении вирусов в настоящее время преобладает подход, согласно которому развитие эпидемии представляется в виде процесса, напоминающего по своей структуре дерево Кэйли со случайным числом связей [14]. Можно обратить внимание на работу [15], в которой рассматривается задача определения вероятности заражения узлов в зависимости от удаленности узла от источника инфекции в сетях с различным масштабом и числом узлов. Топологическими параметрами здесь являлись масштаб и число узлов, однако разнообразие структур сетей в данных работах не исследовалось. Очевидно, что если блокированных узлов будет не очень много, то между двумя произвольно выбранными неблизлежащими узлами будет сохраняться хотя бы один «отрытый» путь (путь, состоящий из неблокированных узлов). Доля блокированных узлов, при которой сеть в целом потеряет работоспособность, будем называть порогом перколяции, ниже его значения сеть является работоспособной, несмотря на то что в ней есть некоторые узлы или их группы (кластеры), блокированные 23 С.А. Лесько, Д.О. Жуков, Л.А. Истратов вирусами. Выше порога перколяции вся сеть целиком выключается и теряет работоспособность по передаче данных. Следует отметить, что имеется много работ, в которых описаны исследования перколяционных свойств сетевых структур [16-22]. Однако никто не изучал взаимосвязи структурных свойств сетей и динамики их блокирования. Исследование процессов образования кластеров блокированных узлов и перколяции данных в сетях, имеющих различную (в том числе и случайную) топологию, представляет большой научный и практический интерес для разработки топологии вычислительных сетей, имеющих высокую отказоустойчивость, и создания новых методов и методологии защиты компьютерных сетей. 1. Перколяционные свойства сетевых структур В теории перколяции (теория вероятностей на графах) изучают решение задачи узлов и задачи связей для сетей с различной - как регулярной (2Б-структуры - треугольная, шестиугольная, деревья Кейли и т.д.; 3D - гексагональная, кубическая и т.д.), так и случайной - структурой. При решении задачи связей определяют долю связей, которую нужно разорвать, чтобы сеть распалась минимум на две несвязанные части. В задаче узлов определяют долю блокированных узлов, при которой сеть распадется на несвязанные между собой кластеры, внутри которых сохраняются связи (или, наоборот, долю проводящих узлов, когда проводимость возникает). Доля блокированных узлов (в задаче узлов) или разорванных связей (в задаче связей), при которой исчезает проводимость между двумя произвольно выбранными узлами сети, называется порогом перколяции (протекания). Определение долей блокированных узлов или связей эквивалентно нахождению вероятности случайно выбранного узла (или связи) быть в блокированном (разорванном) состоянии. Поэтому величина порога перколяции определяет вероятность передачи информации через всю сеть в целом, если блокирована (исключена) некоторая часть ее узлов (или связей), т.е. задана средняя вероятность блокирования узла (разрыва связи). В работах [23, 24] было проведено численное моделирование зависимости порогов перколяции случайных сетей от среднего числа связей в расчете на один узел (плотность) сети. Полученные в этих работах результаты для задачи блокирования узлов при небольших плотностях сетей показывают, что для случайных структур зависимость их натурального логарифма lnP(x) от обратной величины плотности сети (1/х) может быть описана уравнением 4 02 ln P ( x) = --2,26 (1) x с величиной коэффициента корреляции числовых данных и уравнения линейной зависимости, равным 0,97. Данная зависимость может быть использована для вычисления по величинам плотности сетей их порогов перколяции. Далее, используя динамические модели, можно определить время достижения и выхода сети из работоспособного состояния в целом. Рассмотрим две разработанные нами модели блокировки узлов сетей с течением времени и достижения величины порога блокирования (перколяции). 2. Кинетика распространения в компьютерных сетях эволюционирующих вирусов при условии устаревания и запаздывания действия защиты и достижение порога перколяции Рассмотрим сеть, в которой происходит процесс распространения вирусов, начинающийся раньше, чем появятся эффективные способы организационного и технического противодействия (антивирусная защита имеет время запаздывания). Долю узлов сети, находящихся в момент времени t в зараженном состоянии обозначим какyi(t), в защищенном (иммунизированном) состоянии - y2(t), в нейтральном состоянии (не инфицирован, не 24 Модели описания динамики блокировки узлов вычислительных сетей вирусами защищен и может быть заражен) - уз(і). Общее число узлов сети примем равным L. В начальный момент времени (t = 0) имеется некоторое количество (y\\(t = 0)) зараженных узлов, которые могут рассылать копии вирусов по узлам сети, случайно выбирая их в адресном пространстве. Кроме того, имеется некоторое число узлов сети (y2(t = 0)), которые занимаются борьбой с вирусами (излечивают зараженные и иммунизируют свободные узлы), рассылая копии антивирусов (полезные вирусы) по узлам сети, случайным образом выбирая их в адресном пространстве, и y3(t = 0) - в нейтральном состоянии (не инфицирован, не защищен и может быть заражен). Антивирусы могут устаревать, вследствие чего ранее иммунизированные узлы могут быть вновь инфицированы. Введем следующие времена: ті - запаздывания действия антивируса; Т2 - устаревания антивируса, т.е. узел становится уязвимым для новых видов вирусов спустя некоторое время после иммунизации. Поскольку распространение вирусов и антивирусов является независимым, то для их распространения следует выбрать механизм случайной рассылки. Описанный процесс стохастической кинетики распространения эволюционирующих вирусов в компьютерной сети можно описать диаграммой, представленной на рис. 1, и системой кинетических уравнений J ) - аУ\\ (t) Уз (t) ЪУі (t) У2 (t ті), (2) СУ2 (t-Ч) Уз (t) + ЪУі (t) У2 (t-T1)- кУ2 (t) , (3) - -аУі (t) Уз (t) - СУ2 (t - T1) Уз (t) + кУ2 (t -^2 ) . (4) dy2 (t) _ dt Фз (t) dt Рис. 1. Диаграмма, описывающая рассматриваемую модель процесса распространения вирусов в компьютерной сети Fig. 1. Diagram describing the considered model of the process of spreading viruses in a computer network Производные по времени определяют скорости изменения долей соответствующих узлов; a, b, c и к - некоторые коэффициенты, характеризующие соответствующие переходы на рис. 1 (эти коэффициенты являются интегральными параметрами, зависящими, например, от числа копий рассылаемых вирусов и антивирусов, вероятности встречи и т.д.). Перемножение различных функций, например y1(t)y3(t), характеризует вероятность соответствующих встреч. Для пояснения модели рассмотрим более подробно одно из кинетических уравнений, например (3). dy2 (t) ( Член уравнения описывает скорость изменения доли узлов, находящихся в защищенном (имdt мунизированном) состоянии, cy2 (t ) Уз (t) определяет прирост за счет иммунизации уязвимых уз лов, Ъуі (t) y2 (t -%i) -прирост за счет излечивания зараженных узлов, ky2 (t -^) - убыль за счет устаревания антивируса (иммунизированный узел может сначала переходить в незащищенное состояние, а затем заражаться вирусом). Аналогичным образом определяется смысловое значение членов кинетических уравнений (2) и (4). 25 С.А. Лесько, Д.О. Жуков, Л.А. Истратов Рассмотрим взаимосвязь между долями зараженных, иммунизированных и уязвимых узлов (yi(t), yi(t) и уз(0) при распространении эволюционирующих вирусов в сетях передачи данных и достижением порога перколяции (критической доли зараженных или блокированных узлов). Для обсуждения выберем в качестве примера компьютерную сеть, имеющую случайную структуру, в которой на один узел в среднем может приходиться от 2,5 до 4,0 связей. В соответствии с проведенными по уравнению (1) расчетами, общая доля зараженных узлов, при которой сеть потеряет работоспособность, в целом должна составлять от 0,52 (при 2,5 связей на узел порог перколяции равен 0,52) до 0,64 (при 4,0 связей на узел порог перколяции 0,64). На рис. 2 представлены результаты решения системы уравнений (2)-(4) с взятыми в качестве примера следующими значениями коэффициентов: a = 0,003; b = 0,0015; c = 0,0001 и k = 0,1, общим числом узлов сети равным 1 000, временами запаздывания и устаревания ті = 38 и Т2 = 12 условных единиц, начальными значениями y3(t = 0) = 1 000, y2(t = 0) = 1, yi(t = 0) =10. В данном случае доля зараженных узлов в стационарном состоянии будет достигать 0,64 (см. рис. 2, кривая 1). Для того чтобы сеть в целом оставалась работоспособной, необходимо, чтобы среднее число связей на один ее узел составляло более 4, что технологически является нереализуемым в реальной сети с точки зрения стоимостных затрат. Если реализовывать топологии, в которых среднее число связей на один узел будет составлять около 2,5-3,0, то порог перколяции (или возможная доля блокированных узлов) будет иметь величину 0,5. Используя данное значение порога перколяции можно решить обратную кинетическую задачу и определить необходимые для обеспечения заданного порога перколяции величины коэффициентов a, b, c, k и времен запаздывания и устаревания Т1 и т2. В свою очередь, на основании вычисленных параметров модели может быть задана необходимая надежность, определяемая вероятностями переходов. Рис. 2. Кинетика взаимных переходов между узлами компьютерной сети и порог перколяции при распространении эпидемий эволюционирующих вирусов при коэффициентах переходов: a = 0,003; b = 0,0015; c = 0,0001; k = 0,1 Fig. 2. Kinetics of mutual transitions between computer network nodes and the percolation threshold for the spread of epidemics of evolving viruses with transition coefficients: a = 0,003; b = 0,0015; c = 0,0001; k = 0,1 Доля узлов, находящихся при стационарном состоянии в защищенном (иммунизированном) состоянии (см. рис. 2, кривая 2) будет равна 0,32, доля узлов, находящихся при стационарном состоянии в нейтральном состоянии (не инфицирован, не защищен и может быть заражен) - 0,04 (см. рис. 2, кривая 3). 3. Стохастическая модель блокировки узлов сети и время достижения порога перколяции Предположим, что в некоторый момент времени t доля блокированных (вследствии перегрузок или заражения вирусами) узлов сети передачи данных составляет некоторую величину Хі, которую будем называть состоянием сети. 26 Модели описания динамики блокировки узлов вычислительных сетей вирусами Состояние, наблюдаемое в момент времени t, можно обозначить, как Xi (xi е X). Кроме того, введем интервал времени то, за который возможно изменение состояния Xi. В данном случае любое значение текущего времени t = hxo , где h - номер шага перехода между состояниями (процесс перехода между состояниями становится квазинепрерывным с бесконечно малым временным интервалом то), h = 0, 1, 2, 3, ..., N. Текущее состояние Xi на шаге h после перехода на шаг h + 1 может увеличиваться на некоторую величину s или уменьшаться на величину Ъ и соответственно оказаться равным Xi + s или Xi - Ъ. Величины s и Ъ принадлежат области определения xi и являются параметрами моделируемых процессов. Кроме того, на Xi + s и Xi - Ъ необходимо наложить ограничения: Xi + s < Ki (Ki - верхняя граница множества X) и Xi - Ъ ^ K2 (K2 - нижняя граница множества X). В самом простом случае s и Ъ являются некоторыми постоянными величинами для любого шага h. Введем понятие вероятности нахождения системы в том или ином состояния. Пусть после некоторого числа шагов h про описываемую систему можно сказать, что: P(x - е, h) - вероятность того, что она находится в состоянии (x - s); P(x, h) - вероятность того, что она находится в состоянии x; P(x + £,, h) - вероятность того, что она находится в состоянии (x + £,). После каждого шага состояние Xi (далее индекс i для краткости можно опустить) может изменяться на величину s или Ъ. Вероятность P(x, h + 1) того, что на следующем, (h + 1)-м, шаге система (или процесс) окажется в состоянии x, будет равна (см. рис. 3) P(x, h + 1) = P(x - s, h) + P(x + £,, h) - P(x, h). (5) Рис. 3. Схема возможных переходов между состояниями системы (или процесса) на (h + 1)-м шаге Fig. 3. Diagram of possible transitions between system states (or process) at h + 1 step Поясним уравнение (5) и представленную на рис. 3 схему. Вероятность перехода в состояние x на шаге h P(x, h + 1) определяется суммой вероятностей переходов в это состояние из состояний (x - s) - P(x - £, h), и (x + d) - P(x + £ h), в которых находилась система на шаге h, за вычетом вероятности перехода (P(x, h)) системы из состояния x (в котором она находилась на шаге h) в любое другое состояние на (h + 1)-м шаге. Будем считать, что сами переходы осуществляются с вероятностью, равной 1. Учитывая, что t = hTo, где t - время процесса, h - номер шага, то - длительность одного шага, перейдем от h к t. Разложим уравнение (5) в ряд Тейлора в близи точки x. Далее, перейдя от вероятности к плотности вероятности (р( x, t) dP ( x, t) ) и учитывая не более чем вторые производные, получим: dx ( x, t) d 2р( x, t) d р( x, t) --- = a - b-^--, (6) dt dx2 dx s где a = 2t b s-Ъ T d p( x, t) Член уравнения вида определяет общее изменение состояния системы или процесса с dt течением времени. Член уравнения вида d 2р( x, t) dt2 описывает процесс, при котором состояния сами 27 С.А. Лесько, Д.О. Жуков, Л.А. Истратов становятся источниками других состояний (поэтому он был исключен). Отметим также, что член d р( х, t) уравнения описывает упорядоченный переход либо в состояние, когда оно увеличивается dt (s >£,), либо когда оно уменьшается (s £), например x0 = 0,05, в = 0,015 и £ = 0,007. На рис. 4 представлена зависимость от времени вероятности 28 Модели описания динамики блокировки узлов вычислительных сетей вирусами Qi(l, t) того, что к моменту времени t окажется достигнутым порог перколяции. Кривая 1 построена для значения порога перколяции сети li = 0,30, кривая 2 для І2 = 0,40, кривая 3 для Із = 0,50, кривая 4 для І4 = 0,60. Полученные результаты можно связать с результатами рассмотрения перколяционной модели. Пересечение горизонтальной линии на рис. 4, с кривыми линиями, описывающими поведение вероятностей, позволяет определить время достижения порога перколяции при заданных параметрах моделирования, а, следовательно, и потерю работоспособности сети. Для кривой 1 оно составит порядка 28,0 условных единиц; для кривой 2 - 40,5; кривой 3 - 52,5 и для кривой 4 - 65,0 условных единиц. Заключение 1. В сетях передачи данных могут происходить блокирование узлов, образование их кластеров и достижение количественной доли, при которой вся сеть целиком теряет работоспособность (достижение порога перколяции), несмотря на то что значительная часть узлов все еще находится в рабочем состоянии. При среднем числе связей на один узел сети передачи данных в диапазоне значений от 2,5 до 3,5 доля неблокированных узлов, при которой сеть еще сохраняет общую работоспособность, должна иметь значения от 0,52 до 0,37. Используя данные значения порогов перколяции, можно решить динамическую задачу и определить необходимые для обеспечения заданного порога перколяции (надежность) величины коэффициентов в моделях, описывающих динамику блокирования узлов. 2. Модель распространения эволюционирующих вирусов в компьютерной сети может быть описана в графическом виде с помощью диаграммы возможных переходов между состояниями узлов, это позволяет получить систему кинетических дифференциальных уравнений, описывающих указанные процессы. В рамках модели любой узел сети может находиться в одном из трех состояний: в защищенном (иммунизированном), и узел сам может рассылать антивирусы (излечивает зараженные и иммунизирует свободные узлы); в зараженном (может рассылать копии вирусов по узлам сети); в нейтральном состоянии (может быть заражен). Анализ полученных решений показывает возможность существования в рамках модели различных режимов распространения вирусов; при некоторых наборах величин коэффициентов уравнений наблюдается осциллирующий характер вирусных эпидемий. 3. Разработанная на базе кинетических дифференциальных уравнений модель может быть модифицирована и расширена на основе создания более сложных графических диаграмм изменения состояний и переходов между ними. В частности, это позволяет дополнить систему кинетических уравнений членом, учитывающим общий рост числа пользователей и устройств в компьютерных сетях с течением времени, описываемый функцией любого вида. 4. При описании процесса блокирования узлов в вычислительных сетях можно рассматривать совокупность случайных переходов между состояниями всей сети в целом (изменение числа блокированных и разблокированных узлов). Такая формализация позволяет вывести дифференциальное уравнение второго порядка (типа уравнения Колмогорова), описывающее стохастическую динамику изменения состояний как отдельных узлов, так сети в целом. Полученное дифференциальное уравнение позволяет сформулировать и решить краевую задачу изменения загруженности и блокировки сети. Взаимосвязь стохастической и перколяционной моделей позволяет оценить время достижения порога перколяции и потери работоспособности сети в целом. 5. Практические рекомендации для защиты любых сетей от угроз вирусных атак заключаются в том, что в случае использования однотипного оборудования и программного обеспечения для создания сетей передачи данных, имеющих среднее число связей в расчете на один узел сети от 2,5 до 3,5, его доля должна находится в пределе от 0,48 (если блокируется 48% используемого оборудования, то все еще выполняется условие перколяции, так как доля неблокированных узлов равна 0,52) до 0,63 (превышать 48-63%).

Скачать электронную версию публикации