2.6 Математическая модель распространения вредоносного программного обеспечения в социальных информационных сетях на основе теории цепей Маркова

Рассмотрим СИС, состоящую из N компьютеров. Каждый компьютер может находиться в одном из двух состояний – незараженный или зараженный.

Сеть можно представить в виде графа, узлами которого являются компьютеры, а дугами – каналы связи между ними, по которым может распространяться вредоносное программное обеспечение (ВПО) [35]. Вес связи w_ij означает вероятность перехода ВПО по каналу связи между компьютерами i и j за единицу времени [98].

Общее состояние СИС является совокупностью состояний всех компьютеров сети, которое можно описать вектором из N элементов, где значение i-го элемента соответствует состоянию i-го компьютера: I (infected), если компьютер заражен, и S (suspected), если компьютер не заражен [35].

Состояние СИС в следующий момент времени зависит только от текущего состояния СИС, и не зависит от предыдущих. Поэтому процесс распространения ВПО в СИС можно представить как цепь Маркова.

Переходные вероятности вычисляются по формуле:

. (2.6.1)

СИС перейдет из состояния sⁱ в состояние s^j при условии, если каждый компьютер в СИС перейдет из состояния s_kⁱ в состояние s_k^j, где k – номер компьютера в СИС. Вероятность этого события описывается следующей формулой:

(2.6.2)

Для определения вероятности перехода k-го компьютера из состояния s_kⁱ в состояние s_k^j необходимо рассмотреть четыре варианта для различных состояний компьютера на предыдущем и следующем шаге: переход из состояния S в состояние I, из S в S, I в S, и I в I [133].

S→I. Вероятность заражения незараженного k-го компьютера при исходном состоянии СИС sⁱ равна P_зар (k,sⁱ).

S→S. Поскольку событие перехода компьютера в зараженное состояние и событие, при котором незараженный компьютер останется незараженным, образуют полную группу событий, то вероятность того, что компьютер останется незараженным будет равна 1-P_зар (k,sⁱ).

I→S. Так как модель не учитывает излечения компьютера от ВПО, то переход из состояние 1 в состояние 0 невозможен, т.е. имеет нулевую вероятность.

I→I. Так как модель не учитывает излечения компьютера от ВПО, то вероятность перехода из состояния 1 в состояние 1 равна единице.

В результате получается следующая формула:

(2.6.3)

Узел k перейдет из незараженного состояния в зараженное за единицу времени в случае, если ВПО к нему поступит хотя бы с одного другого узла (рис. 2.9).

W1k W2k … WNk

Рис. 2.9. Схема заражения узла

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

(2.6.4)

Вероятность передачи ВПО от узла m узлу k при состоянии m-го компьютера s_mⁱ можно вычислить следующим образом:

- если компьютер m заражен, вероятность равна w_mk,

- если компьютер m не заражен, то вероятность передачи ВПО с него равна нулю.

(2.6.5)

Математическое ожидание среднего числа зараженных компьютеров на шаге n можно вычислить следующим образом [47].

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

.

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

.

Если рассматривать в виде марковской цепи не процесс распространения ВПО по всей СИС, а строить отдельную марковскую цепь для каждого узла, можно значительно сократить объем вычислений [133].

В каждый момент времени каждый компьютер с определенной вероятностью может быть незараженным (S), либо зараженным (I). Вектор состояния в данном случае состоит из двух элементов (в более общем может состоять из большего количества элементов) – вероятности того, что компьютер не заражен и вероятности того, что компьютер заражен: , где k – номер компьютера, t – номер шага [120].

Матрица переходных вероятностей для данного узла будет иметь следующий вид:

. (2.6.6)

Поскольку данная модель не учитывает возможность излечения, то переход из состояния I в состояние S невозможен, а из состояния I возможно попасть только обратно в состояние I, то

Так как сумма элементов строки матрицы переходов всегда равна единице, то .

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

, (2.6.7)

где P_зар(k) - это вероятность заражения k-го узла, которая, как было показано выше, вычисляется по формуле

. (2.6.8)

Передача ВПО от узла m узлу k произойдет при одновременном наступлении следующих событий:

- если компьютер m заражен на предыдущем шаге, вероятность этого события равна ;

- если вирус пройдет по связи m-k, вероятность этого события равна w_mk.

Следовательно, вероятность передачи ВПО от узла m узлу k равна произведению вероятности зараженности компьютера m на предыдущем шаге, умноженной на вероятность перехода ВПО по связи m-k:

. (2.6.9)

В результате подстановки получаем следующую матрицу переходов для отдельного узла:

. (2.6.10)

Как можно заметить, матрица переходов зависит от состояния узлов СИС на предыдущем шаге, следовательно, цепь Маркова для каждого узла является неоднородной [133].

Для использования модели на основе цепи Маркова необходимо задать начальное распределение - вектор вероятностей нахождения СИС в том или ином состоянии в начальный момент времени. Выбирается единственное начальное состояние сети , для которого вероятность принимается равной единице, для остальных - нулю: , где [83,84].

Исходя из теории марковских цепей, распределение на шаге t будет равно .

Начальное распределение задается для каждого узла сети: , где j - номер узла. Удобнее всего выбрать в СИС зараженные компьютеры, для которых вероятность нахождения в зараженном состоянии равна 1, т.е. , а для остальных - наоборот .

Далее для каждого шага t производятся следующие действия:

- для каждого j-го узла по формуле (2.6.10) строится матрица переходов;

- вектор начального на предыдущем шаге умножается на полученную матрицу переходов, в результате получается вектор распределения для первого шага: ;

- имея множество векторов распределения на шаге t равно , а следовательно, зная вероятность нахождения каждого узла в зараженном состоянии в момент времени t , можно вычислить математическое ожидание количества зараженных компьютеров на этом шаге:

.

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

поток атак

Рис. 2.10.Узел СИС

Для этого узла составим схему изменения состояний его элементов. Введём обозначения:

p_з – вероятность заражения;

– пуассоновский поток атак на элементы узла;

- вероятность перехода из незараженного состояния в зараженное.

Тогда схема переходов состояний элементов СИС будет выглядеть следующим образом (рис.2.11).

р_к

р_а

Рис. 2.11. Схема изменения состояний элементов узла СИС

На основе схемы изменения состояний элементов узла СИС построим вероятностную схему связей в виде стохастической матрицы (рис. 2.12):

	S00	S01	S10	S11	S20	S21	S30	S31	S40	S41	S50	S51
S00	1−pa	0	0	0	0	0	0	0	0	0	0	0
S01	0	1−pa	0	0	0	0	0	0	0	0	0	0
S10	pa	0	1−pa −pк	0	0	0	0	0	0	0	0	0
S11	0	pa	pк	1−pa	0	0	0	0	0	0	0	0
S20	0	0	pa	0	1−pa−pк	0	0	0	0	0	0	0
S21	0	0	0	pa	pк	1−pa	0	0	0	0	0	0
S30	0	0	0	0	pa	0	1−pa−pк	0	0	0	0	0
S31	0	0	0	0	0	pa	pк	1−pa	0	0	0	0
S40	0	0	0	0	0	0	pa	0	1−pa−pк	0	0	0
S41	0	0	0	0	0	0	0	pa	pк	1−pa	0	0
S50	0	0	0	0	0	0	0	0	pa	0	1−pк	0
S51	0	0	0	0	0	0	0	0	0	pa	pк	10

Рис. 2.12. Матрица переходов из незараженного состояния в зараженное