2.7 Основные положения классической схемы размещения и её применение в социальных информационных сетях

Под атакой будем понимать попытку заражения компьютера пользователя СИС вредоносным программным обеспечением.

Пусть на N групп СИС производится n независимых атак, в каждой из которых с равными вероятностями осуществляется выбор одной из N социальных групп, занумерованных числами 1, 2, …, N. Обозначим количество успешно реализованных атак в i-ой социальной группе, i = 1, 2, …, N. Случайные величины имеют полиномиальное распределение: если целые неотрицательные таковы, что , то

. (2.7.1)

Другими словами ситуацию, в которой возникает полиномиальное распределение, можно описать в терминах равновероятной схемы размещения. Если n атак независимо одна от другой производятся на N социальных групп так, что каждая атака с равными вероятностями попадает в одну из N групп, занумерованных числами 1, 2, …, N, то число успешно реализованных атак имеют полиномиальное распределение (2.7.1) [98].

В такой схеме атак на группы СИС, приводящей к полиномиальному распределению, значения количества зараженных компьютеров пользователей СИС могут быть получены при условии последовательных независимых атак. Если отказаться от возможности проведения атак таким путем, то любой набор целочисленных неотрицательных случайных величин , для которых , можно рассматривать как схему проведения n атак на N групп СИС и интерпретировать как число зараженных компьютеров пользователей СИС в i-ой социальной группе, i = 1, 2, …, N [17,120].

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

. (2.7.2)

где — независимые одинаково распределенные целочисленные случайные величины.

Обобщенная схема размещения задается параметрами n и N и распределением случайных величин , которое с помощью соотношения (2.7.2) определяет совместное распределение случайных величин (число зараженных АС в соответствующей социальной группе). Обозначим

. (2.7.3)

Для случайных величин, определяющих число зараженных компьютеров пользователей СИС в соответствующей социальной группе СИС, с полиномиальным распределением (2.7.1) соотношение (2.7.2) выполняется, если имеет распределение Пуассона с произвольным параметром :

. (2.7.4)

Поэтому распределение числа зараженных компьютеров , удовлетворяющее соотношению (2.7.2) при некотором распределении (2.7.3), можно рассматривать как обобщение полиномиального распределения [83,84].

За равновероятной схемой размещения, приводящей к полиномиальному распределению (2.7.1), закрепилось название классическая схема размещения. Использование естественных терминов, связанных с классической схемой размещения, оказалось удобным для наглядного описания ряда комбинаторных задач, в которых возникает полиномиальное распределение [120]. Многие результаты, относящиеся к классической схеме размещения, могут быть получены с использованием связи (2.7.2) полиномиального распределения с распределением Пуассона (2.7.4). Введение обобщенных схем размещения не только расширяет область применения удобного языка для описания комбинаторных объектов, но и сохраняет возможность применения опирающихся на соотношение (2.7.2) методов, разработанных для анализа классической схемы размещения [17,98].

Обозначим число социальных групп, содержащих ровно r зараженных компонент СИС, в обобщенной схеме размещения с распределениями (2.7.2) и (2.7.3). Покажем, как представление (2.7.2) можно использовать для изучения этих случайных величин.

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

.

Введем также обозначения

, .

Следующая лемма выражает распределение через вероятности, связанные с суммами независимых одинаково распределенных величин.

Лемма 1: Справедливо равенство

. (2.7.5)

Доказательство: Пусть — событие, состоящее в том, что ровно в k социальных группах, определённых случайными величинами заразилось r компонент СИС. В силу равенства (2.7.2)

.

Равенство (2.7.5) получается с помощью очевидных преобразований числителя: событие может произойти при различных выборах случайных величин, принимающих значение r, поэтому

В обобщенной схеме размещения возможен достаточно простой подход и к изучению членов вариационного ряда , построенного для случайных величин расположением их значений в неубывающем порядке [120].

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

,

где А — подмножество натуральных чисел, .

В частности, если А состоит из одного значения r, то , где — случайная величина, определенная перед леммой 1. Обозначим .

Следующая лемма сводит изучение распределений членов вариационного ряда к изучению вероятностей, связанных с суммами независимых слагаемых [120].

Лемма 2. Для любого натурального m

,(3.7.6)

,(3.7.7)

где - множество целых неотрицательных чисел, не превосходящих r, - его дополнение в множестве целых неотрицательных чисел, .

Доказательство. Докажем соотношения (3.7.7) при m=1. Для максимального члена вариационного ряда в силу (2.7.2) и независимости справедливы следующие равенства:

.

Используя случайные величины , окончательно получаем, что

. (2.7.8)

Соотношения (3.7.6) и (3.7.7) при других значениях m доказываются аналогично.

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

Лемма 3. Справедливо равенство

,

где - целые неотрицательные числа и различны.

Леммы 1, 2 и 3 выражают распределения случайных величин и членов вариационного ряда в обобщенной схеме размещения через вероятности, связанные с суммами независимых случайных величин [120].

Приведем несколько примеров сведения комбинаторных задач к обобщенной схеме размещения [98].

Пример 1. В случайном отображении

,

принимающем с равными вероятностями значения из множества , случайные величины независимы и для целых положительных , не превосходящих n,

. (2.7.9)

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

. (2.7.10)

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

,

в котором независимы и одинаково распределены по закону Пуассона.

Пример 2. При m атаках на N групп СИС, с помощью случайного выбора без возвращения производится n атак на каждую группу СИС. Обозначим число успешно реализованных атак на i-ую группу СИС, i = 1, 2, …, N. Легко видеть, что для целых неотрицательных таких, что ,

.

Если в обобщенной схеме размещения случайные величины имеют биномиальное распределение

,

то

,

и распределение случайных величин в этой схеме совпадает с условным распределением независимых случайных величин при условии . Таким образом, можно рассматривать как успешную реализацию атак в обобщенной схеме размещения, в которой случайные величины имеют биномиальное распределение с параметрами (m, р) [120].

Пример 3. Рассмотрим все различные разбиения числа общего числа атак n на N групп СИС, не меньших . Число таких разбиений равно . Зададим на множестве этих разбиений равномерное распределение, приписав каждому разбиению , , вероятность . Тогда число n можно записать в виде

,

где слагаемые являются случайными величинами, причем, если , , то

.

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

.

Действительно, как легко проверить,

,

поскольку для геометрически распределенных слагаемых

.

Пример 4. Рассмотрим множество , состоящее из N групп СИС; социальные группы занумерованы числами 1, 2, …, N, а пользователи СИС, входящие в эти группы, n занумерованы числами 1, 2, …, n. Число различных групп в равно [120]. Число групп, в которых содержится пользователей, k = 1, 2, …, N, равно

,

где множитель есть число разбиений n атак на N упорядоченных групп, а — число групп, которые появляются в связи с заражения компьютеров пользователей СИС в k-й группе разбиения. Отсюда следует, что

, (2.7.11)

где суммирование проводится по целым неотрицательным таким, что [32].

Зададим на равномерное распределение. Обозначим число зараженных компьютеров пользователей в k-ой группе СИС из , k = 1, 2, …, N. Для случайных величин

, (2.7.12)

где — целые неотрицательные числа и .

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

, (2.7.13)

где параметр х лежит в интервале и функция задается рядом

.

Используя (2.7.11), легко получаем, что

,

поэтому при любом х, , для целых неотрицательных таких, что ,

. (2.7.14)

Правые части равенств (2.7.12) и (2.7.14) одинаковы, и совместное распределение совпадает с совместным распределением при условии [120].

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

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

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