Марковские цепи и их применение при моделировании динамики реализации угроз безопасности информации в информационных системах
Моделирование динамики процессов в предметной области ТЗИ, в том числе динамики реализации угроз, - это разработка моделей, в которых непосредственно учитывается фактор времени. Для такого моделирования сегодня имеется достаточно много методов.
Однако наибольшее применение нашли методы теории марковских [35, 57] и полумарковских процессов [35, 83-85], построенные на их основе методы теории массового обслуживания [83, 86-88] и ее составной части - теории потоков [89, 90], а также аппарат теории сетей Петри-Маркова [91,35] и его расширений.
Следует подчеркнуть, что каждая угроза безопасности информации в ИС реализуется по-своему и поэтому для каждой угрозы приходится разрабатывать свою математическую модель. Из-за этого, во-первых, сегодня отсутствует приемлемый по полноте набор таких моделей, во-вторых, постоянное расширение спектра угроз приводит к необходимости разработки все новых моделей. А это не только затруднительно, но и приводит к значительным сложностям их практического применения, так как обусловливает необходимость, наряду с созданием приемлемых описательных моделей, разрабатывать программные средства моделирования процессов их реализации, поскольку без автоматизации расчетов количественно оценить возможности реализации угроз крайне сложно. В данном разделе рассматриваются наиболее часто применяемые методы для моделирования динамики реализации угроз безопасности информации, основанные на аппарате марковских и полумарковских процессов.
Марковские процессы являются частным видом случайных процессов и впервые были весьма глубоко исследованы в трудах отечественных ученых А.А. Маркова и А.Н. Колмогорова. Достаточно полно теория марковских процессов изложена в [57], именно на основе этого труда В.И. Тихонова и М.А. Миронова далее приводятся основные положения этой теории.
В соответствии с [57] случайный процесс £(t) называют марковским, если для любых п моментов времени tl<t2<... < tn из отрезка [О,Г] условная функция распределения последнего значения %(t„) при фиксированных
значениях (f ),(f (/,)....(f (/„_t) зависит только от £, (tn_l), то есть при заданных
значениях справедливо соотношение:
Р{£ ((,)< С,,/4(0 = £М = ,7 f (U = Ц = Р{${іп)< = 4,м}, (5-D
где .Р{»} - вероятность события, указанного в фигурных скобках.
Как и другие случайные процессы, в которых множество состояний и область определения времени реализации процесса могут быть как непрерывными, так и дискретными различают марковские процессы с дискретным множеством состояний и с дискретным временем (дискретные процессы с дискретным временем, получившие название марковских цепей), марковские процессы с дискретным множеством состояний и с непрерывным временем (дискретные процессы с непрерывным временем) и марковские процессы с непрерывным множеством состояний и с непрерывным временем (непрерывные процессы с непрерывным временем). Последние пока не нашли применения при моделировании процессов в предметной области защиты информации и далее не рассматриваются.
Для марковских цепей количество фазовых состояний {<9^} ,к = \,К, моделируемой системы конечно, то есть составляет величину К, и система в дискретные моменты времени tx < t: <... случайным образом меняет свое
фазовое состояние Ѳ0 —» Ѳх —» Ѳ2 при этом полное описание поведения
системы за п шагов задается совместными вероятностями:
Р{Ѳ0АЛ,-А)=Щ =\А = \А=\-А =90 (5.2)
при разных п и Ѳп
Если ввести условную вероятность перехода системы из состояния в состояние на /л -м шаге:
то поведение марковской цепи описывается соотношением:
ЩДД,.Д) = Щ>)- и^іѳмм, (5.4)
М=1
где Р(Ѳ0) - вероятность нахождения системы в начальном состоянии Ѳ0 в момент времени t0.
Для простой цепи Маркова вероятность фазового состояния в момент времени tn зависит лишь от того, в каком состоянии система находилась в непосредственно предшествующий момент времени /п-1, поэтому марковские цепи, как и все марковские процессы, для которых выполняется это свойство, называют процессами без последействия. Для таких процессов
к {ѳпі%А,-А^ = *М,іѳп^
Р(ѳ0 АА,-А,) = т) П Ам / ѳц_х). (5.5)
М= 1
Вырожденным является случай, когда вероятность нахождения системы в фазовом состоянии Ѳп в момент времени !п не зависит от того, в каком состоянии она находилась в предшествующий момент времени Іп ,, при этом:
жп (Ѳ„/Ѳ0,Ѳ1,-,Ѳ„-1) = Р „ М (5.6)
Если обозначить безусловную вероятность того, что на п -м шаге система перейдет в к-е состояние как р{Ѳп=9к) = рк{п) и вероятность перехода из j -го состояния на р -м шаге в к -е состояние на п -м шаге как р{Ѳп=9кІѲм = &]) = лік(/л,п) при (j,k) = lK,0<p<n,n = l,N, то для определения вероятностей перехода марковской цепи из состояния j в состояние к имеет место уравнение Маркова, а для расчета безусловной вероятности нахождения системы в состоянии Ѳп = 9к следующее соотношение:
РМ) = %Р, (Р) пи-(рЛ і,к = \,К; 0 <р<т<п. (5.8)
Если ввести квадратные матрицы x(fi,n) = KJk(p,n), элементами которой являются вероятности перехода и матрицу-строку РТ(п) = {рк{п)\, то в матричной форме уравнения (5.7) и (5.8) записываются следующим образом[57]:
п) = я(/и, пі)-я(пі, п), (5.9)
Рг(п) = Рт(р)-ж(р,п) ши Р(п)-лт(р,п)-Р(р). (5.10)
Различают однородные и неоднородные цепи Маркова. Однородная цепь Маркова характеризуется тем, что вероятности перехода лік (р, п) зависят только от разности аргументов, то есть:
к1к(р.,п) = кл(п-р) ^ (5.11)
при этом уравнение Маркова имеет вид:
xjk(n-р) = ^Гія]І(т-р)-7uih(n-m),j,k = 1,А',0< p<m<n. (5-12)
/=1
Если условие (5.11) не выполняется, то цепь Маркова является неоднородной.
Если для однородной цепи обозначить одношаговые вероятности перехода через л]к = Лд(1), то поведение цепи описывается системой алгебраических уравнений, решением которой является вероятность того, что моделируемая система попадет в состояние к :
Рь=ТРо-жа-к = 1-К- (5ЛЗ)
Если обозначить матрицу вероятностей единичных переходов, то уравнение (5.12) можно записать в матричной форме:
Рт(т + р) = Рт{р)-ят. (5.15)
Для цепи Маркова с конечным числом состояний при выполнении условия я]к(п)> О, начиная с некоторого числа п, существуют предельные (финальные) вероятности, которые не зависят от начального распределения
Такие марковские цепи называют эргодическими, при этом финальные вероятности являются решением системы линейных уравнений (5.14), удовлетворяющих дополнительному требованию:
£Л=1,Й>0. (5.17)
k= 1
Финальные вероятности образуют стационарное распределение {рк).
Цепь Маркова называют стационарной, начиная с г0, если вероятности начального состояния jri”) совпадают с соответствующими финальными вероятностями {рк} .
Цепь Маркова для наглядности часто представляют в виде ориентированного графа, вершины которого определяются состояниями цепи, а каждой дуге, идущей из состояния і9; в состояние Зк, ставится в соответствие
число лjk, если л jk> 0. Пример такого графа приведен на рисунке 5.1.
Рассмотрим пример использования аппарата марковских цепей для моделирования процессов реализации угроз безопасности информации в ИС.
Стационарный случайный процесс называется эргодическим, если любая его вероятностная характеристика, полученная усреднением по множеству возможнвіх реализаций, с вероятностью, сколь угодно близкой к единице, равна временному среднему, полученному усреднением за достаточно большой промежуток времени одной единственной реализации случайного процесса, то есть выполняется равенство:
тх =М [х(?)] = J л; • p{x)dx = lim — J x{t)dt , где x(t') - случайный процесс, mx=M[x(t)] – его математическое ожидание, а [-Г.Г] - временной отрезок, на котором осуществляется усреднение по одной из реализация случайного процесса.
Пример 5.1: модель процесса инфицирования компьютера вредоносной программой, заражающей исполняемые файлы.
Пример ориентированного графа для однородной марковской цепи
Пусть вредоносная программа внедрена в компьютер (записана в одном из каталогов файловой системы), которая должна осуществить поиск исполняемых файлов, например, с расширением *.ехе, а затем инфицировать их. Программа осуществляет последовательно поиск каждого такого файла и инфицирует его, после чего переходит к поиску и инфицированию другого файла и т.д. Пусть вероятность внедрения вредоносной программы составляет величину р0, вероятность поиска - ли вероятность инфицирования - ліп{.
Ориентированный граф такой марковской цепи приведен, при этом для упрощения графа процедуры поиска и инфицирования файлов объединены в единую процедуру.
Граф марковской цепи, моделирующей инфицирование компьютера вредоносной программой
Рассмотрим простой случай, когда число состояний равно 4 (г = 4). Тогда переходные вероятности определяются следующим образом
*11 _ ^'*12 — */М ' *m/>* 13 = 1 _ *find ' *»/' *24 = *34 = *find ' *inf > й ВерОЯТНОСТИ
того, что в системе через два шага будет инфицирован только один файл, то есть система перейдет или в состояние 5, или по маршруту 1 —> 3 —> 4 в состояние 4, определяется из соотношения:
Рг = Ра (яfind • *inf XI - жАш) • *i„f ) (5.18)
Тогда вероятность того, что за к шагов вредоносная программа сумеет
f* -J- 1
инфицировать ровно z,z<——, исполняемых файлов, определяется из соотношения:
Рк = РоСЦпгы-лшУ(1-лМІ -7rirf)*-z , (5.19)
то есть распределение вероятности представляет собой распределение Бернулли, при этом среднее количество инфицированных файлов за к шагов составит величину к ■ 7tfind ■ .
Несмотря на глубокую проработанность, аппарат марковских цепей нашел лишь весьма ограниченное применение при моделировании процессов в предметной области ТЗИ (если не учитывать их использование в виде процессов Д.Кендалла в аппарате полумарковских процессов, см. раздел 5.7). В основном он применяется в случаях, когда оказывается достаточным представление процесса в виде мгновенных вероятностных переходов из состояния в состояние или с жестко фиксированной длительностью каждого перехода, одинаковой для всех переходов, при этом состав возможных состояний определяется заранее. Значительно более широкое применение нашел аппарат дискретных марковских процессов с непрерывным временем.
