Традиционные сети Петри-Маркова и особенности их применения при моделировании динамики реализации угроз безопасности информации в информационных системах
Впервые аппарат сетей Петри-Маркова как симбиоз сетей Петри и марковских и полумарковских процессов предложен в работах ученых Тульского Государственного университета Игнатьева В.М., Ларкина Е.В, Сабо Ю.И. применительно к решению задач надежности.
Под сетью Петри-Маркова (СПМ) понимается множество у/ = {Н,М], при этом 5 - сеть Петри, которая представляет собой двудольный граф вида [91]:
а = {a,z,ia(z),oz(A)}, (6.1)
где А - множество позиций СПМ, моделирующих состояния рассматриваемого процесса (соответственно традиционно позиции сети обозначаются цифрой и буквой а);
Z - множество переходов СПМ, моделирующих условия перехода из состояния в состояние (соответственно традиционно переход сети обозначаются цифрой и буквой г);
/^(Z) - входная функция переходов (выходная функция позиций), отображающая множество А в множество Z ;
Oz (Д) - выходная функция переходов (входная функция позиций, отображающая множество Z в множество А, а М представляет собой случайный процесс, определяющий логиковероятностные свойства модели и описываемый четверкой
М = |Q,n,f(f),*pJ, (6.2)
при этом 0={?і(г))?2(2)ѵ?дг)} - вектор вероятностей запуска моделируемого процесса из каждого перехода сети;
П /(a)j(z)j - матрица переходных вероятностей, определяющая вероятности перемещения процесса из позиции і(а) в переход j(z). Далее принимается, что первый индекс в переходных вероятностях соответствует позиции, а второй - переходу, и матрица записывается следующим образом
П=[<Ь вд=[/ MJM (')]-[/, со] - матрица плотностей распределения времени перемещения процесса из позиции /(а) в переход j(z);
W = ^j(z),i(a)]°[^ji] – матрица логических условии, элементы которой равны 0 или 1 при выполнении задаваемых различными способами условий (например, в виде логических функций, высказываний и др.),
_WUAOjW)]> еслнаад е04(гЛг));
^(,W(e) {°,если ameOA(zJW), при этом - это элемент множества Z , то есть переход с номером y(z), а /(я) - это номер элемента множества А , то есть позиции, в которую процесс перемещается из перехода с номером j(z).
Матрицы вероятностей и плотностей распределения в некоторых случаях могут заменяться полумарковской матрицей
h(0 = [я)(„),Лг) X ] = \_\a).J{2) ] (6.4)
В этом случае полумарковские и логические свойства модели описываются тройкой
M = {Q,h(0,^}. (6.5)
Последовательность перемещений по СПМ реализуется в виде полушагов.
Полушагом называют перемещение по СПМ из позиции г(я) в сопряженный с нею переход j(z) или из перехода y'(z) в сопряженную с ним позицию £(я). Совокупность полушагов в СПМ таким образом представляется в виде упорядоченных множеств аа: ={i{a), j(z)} и о:а = {]{/),к(а)\. Два последовательных полушага образуют шаг.
СПМ, как и сети Петри, удобно представлять в виде ориентированных взвешенных графов. Пример такого ориентированного графа приведен.
Пример графа сети Петри-Маркова
На рисунке позиции обозначены кружочками, переходы - жирной чертой, а возможность выполнения полушага отмечается стрелкой, при этом над стрелкой, указывающей перемещение из позиции в переход, могут указываться плотность распределения времени и вероятность выполнения полушага из позиции в переход.
Перемещение процесса из перехода в позицию считается мгновенным и происходит с единичной вероятностью. С использованием понятия полушага вводятся понятия входных и выходных позиций и переходов. Выходной (входной) позицией а.^ перехода z.^ называется позиция, в которую (из
которой) можно попасть из (в) zj{^ за один полушаг.
Входные и выходные позиции перехода zобразуют множества: /
(Zj(z)) {акІ’акІ’-"акг}’r ^j(z) i (Zj(z) ) ’ Яп2 ’ } ’ Г ^^Дг)’
где - количество позиций, из которых имеются дуги в переход z
ДО’ - количество позиций, в которые входят дуги из перехода zj(_t. Входной функцией позиций IZ(A) называется функция, отображающая множество позиций А в подмножества переходов = из
которых есть вход в позиции из множества А (входных переходов).
Выходной функцией позиций Oz(A) называется функция,
отображающая множество А в подмножества выходных переходов OzW) = {Oz(ait(a))’ —’Oz(aK(a))}, в которые есть вход из позиций, составляющих множество А (выходных переходов).
Входной функцией переходов (Z) называется функция, отображающая множество переходов Z в подмножества позиций IA(Z) = {/ .(z;i,;i )....,/4(zJ(z))|, из которых есть вход в переходы из множества
Z (входные позиции).
Выходной функцией переходов 0A(Z) называется функция, отображающая множество Z в подмножества позиций OJZ) = {0A(zJi;)).....0A(zJ(z))j (выходных позиций).
СПМ считается ординарной, если в множествах Iz(a.^ и 02(сіщ
переход zj{z), а в множествах IA{zj{_^ и 0A^z.^ - позиция а^а) могут
встретиться не более одного раза.
Переходы СПМ разделяют на примитивные и непримитивные. Примитивным переходом СПМ называется переход z , для входной и
ВЫХОДНОЙ функций которого ВЫПОЛНЯЮТСЯ условия ^[^(Zy(z))] = ^[^.4(Zy(.-))] = l, где К[..] - мощность соответствующего множества.
Все остальные типы переходов - непримитивные. Непримитивные переходы образуют подмножество Zzji е Z (для них вводится специальная индексация j'(zn), например, \(zn)<2(zn)< ...< j(zn)< ...< J{zn)). Примеры непримитивных переходов показаны.
Примеры непримитивных переходов СПМ
Непримитивный переход z.( ,, для выходной функции которого выполняется
условие К
^ 1 (~Д-и) )
“Д-)
= 0, называется конечным переходом. Очевидно, что конечные переходы образуют непустое множество ZE Ф0, иначе процесс перемещений по СПМ был бы бесконечным.
Стартовым переходом называется переход, из которого начинается последовательность перемещений по СПМ, при этом конечный переход не может быть стартовым, а любой непримитивный переход, не являющийся конечным, может быть стартовым.
Переходы, в зависимости от их текущего состояния, разделяются на закрытые и открытые. Переход z.^ называется закрытым, если из него не разрешен полушаг ни в одну из позиций подмножества Ол ® j.
Переход z^_( называется частично открытым, если в подмножестве Oa(zjm) существуют элементы, полушаг в которые разрешен. В этом случае полушаги из указанного перехода в его выходные позиции могут быть разделены на разрешенные и запрещенные.
Переход z^(_( называется открытым, если в подмножестве 0A^z.y^j отсутствуют элементы, полушаг в которые не разрешен.
Логическим условием разрешения полушага называется условие, при выполнении которого переход открывается для выполнения полушага у Полушаг из позиции в переход z^z) (необязательно примитивный) является случайным событием и определяется вероятностью при этом справедливо равенство J ( - ) (6.6) Л-М(--І
Независимо от вероятностей полушаг из позиции ав переход z^ производится в течение случайного времени, определяемого плотностью распределения , для которой (поскольку указанное время является положительно определенной случайной величиной) справедливы ограничения:
оо Лам.-)(0 = о при t < 0 и J f(a)J(z) (t)dt = 1 (6.7) о
Для расширения возможности интерпретации состояний моделируемого процесса могут использоваться так называемые псевдопозиции, введение которых в модели процессов диктуется необходимостью разделения переходов в моделях.
Перемещение процесса из псевдопозиции в переход считается мгновенным, то есть = S(t), где S(t) - дельта-функция (функция Дирака) [92], 5{t) Г0 при t Ф 0; [со при t = О/J 8(t}dt = 1.
Для обозначения перемещения процесса по СПМ используются, как и в сетях Петри, фишки (метки, маркеры), при этом позиции и непримитивные переходы в зависимости от их состояния разделяются на помеченные и непомеченные. Множество помеченных компонентов СПМ формирует ее разметку.
Разметкой СПМ Ѳ(П) называется выделение в ее структуре позиций и непримитивных переходов путем помещения в них фишек. Как позиция, так и непримитивный переход называются помеченными, если они содержат хотя бы одну фишку. Помеченная позиция сіі(а) обозначается а^а ^, а помеченный переход - г](тв), при этом ® (П) = \ai(a.e)T“’ai(a,e)T--’aHa.e)’Z\(:n.e)T-’Zn:n.e)’ZJ(:n,e)\ ■ (6-8)
Разметка может быть начальной (0-разметка) и текущей (и-разметка). 0-разметка Ѳ(0)(3) формируется при старте процесса, а и-разметка Ѳ^(н) - после п полушагов процесса.
Для управления срабатыванием переходов могут применяться также J-переходы (введены в Е-сетях, см. раздел 4.5), которые выполняются только тогда, когда в выходной позиции отсутствует фишка и имеются фишки во входящих позициях, в том числе в позиции, инцидентной входящей управляющей дуге.
Изложенная краткая характеристика классического аппарата сетей Петри-Маркова дает лишь общее представление о нем, но позволяет сделать важные выводы
Во-первых, классическая сеть Петри-Маркова остается автоматной сетью, то есть срабатывание переходов в ней определяется наличием в позициях, инцидентных переходу, фишек и, в случае наличия управляющих дуг (например, ингибиторных), - фишек в позициях, инцидентных таким дугам. Это обусловливает то, что в таких сетях крайне сложно, а чаще практически невозможно моделировать динамику выполнения целого ряда логических условий, таких как условия «И-НЕ», «ИЛИ-HE», исключающее «ИЛИ» («XOR»), «И-ИЛИ» и др., которые часто встречаются в моделях реализации угроз безопасности информации в ПС. При этом сложность состоит не в определении логических правил (что достаточно просто записывается в соответствии с математической логикой), а в определении соотношений для времен срабатывания таких переходов. В частности, в [91 ] показано, каким образом можно рассчитать время ожидания завершения второй процедуры в составе моделируемого процесса после завершения первой, если процесс завершается после завершения второй процедуры. Однако для других условий формулы для расчета временных характеристик отсутствуют.
Во-вторых, весьма сложно моделировать циклические процедуры с заранее установленными правилами их завершения и дальнейшего продолжения выполнения процесса.
С учетом изложенного моделирующие возможности классического аппарата сетей Петри-Маркова применительно к решению задач аналитического моделирования процессов реализации угроз безопасности информации в ПС оказываются ограниченными.
Для расширения моделирующих возможностей СПМ в [35] предложено использовать:
- окрашивание позиций, маркеров и переходов СПМ (применение цветных СПМ);
- логические запреты на выполнение переходов с использованием ингибиторых (сдерживающих) дуг (по аналогии с классическими сетями Петри) или специальных ограничений на срабатывание переходов;
- формирование так называемых иерархических сетей, в которые вложены другие, возможно, также иерархические, сети;
- приоритеты срабатывания переходов, при этом, если несколько переходов являются разрешенными, то срабатывает тот из них, который имеет наивысший приоритет;
- изменяемую структуру, в которой кратность ребер не является постоянной, при этом в самомодифицируемых сетях кратность ребра может задаваться либо натуральным числом, либо определяться количеством фишек, находящихся во входных позициях некоторого перехода;
- временные сети, в которых переходам ставятся в соответствие их времена срабатывания, либо позициям ставятся в соответствие времена нахождения фишек в позициях (по сути, временные сети предшествовали сетям Петри-Маркова).
В теории сетей Петри ингибиторные («сдерживающие») дуги применяются для обнаружения «нулевого» условия или введения запрета на выполнение перехода.
Следует отметить, что применение «цветных» СПМ позволяет разрабатывать модели процессов, в которых окрашенным переходам поставлены в соответствие определенные операторы, выполняемые в зависимости от цветов маркера, перехода и инцидентных переходу позиций, что заметно расширяет моделирующие возможности данного аппарата. Применение же запретов, ингибиторных дуг и специальных ограничений приводит к необходимости поиска путей определения аналитических соотношений для расчета времени срабатывания переходов сети с такими условиями, что на практике оказывается не всегда возможным.
Далее рассматриваются иные модификации аппарата СПМ, расширяющие его моделирующие возможности.
