Сети Петри и их применение при оценке возможностей реализации угроз безопасности информации
Дальнейшим развитием теории конечных автоматов стал переход к методам анализа и синтеза дискретных параллельных систем, среди которых выделились методы, основанные на использовании аппарата сетей специального вида, предложенных Карлом Петри [73] и названных в честь него сетями Петри.
Характерными примерами таких не описываемых в рамках классической теории автоматов параллельных систем, в которых отдельные компоненты функционируют, в основном, независимо, взаимодействуя друг с другом время от времени, являются многопроцессорные вычислительные системы, мультипрограммные операционные системы, асинхронные электронные схемы и т.п.
Следует подчеркнуть, что реальные системы функционируют во времени, то есть события происходят в некоторые моменты времени и длятся некоторое время. В дискретных системах события явно привязаны к определенным моментам и интервалам времени, но в ряде таких систем события могут происходить внутри больших интервалов времени, при этом часто выходом может служить отказ от введения времени и тактированных последовательностей изменения состояний моделируемой системы с заменой их причинно-следственными связями между событиями. Модели такого типа получили название асинхронных. Замена временных связей причинно- следственными дает возможность более наглядно описать структурные особенности функционирования систем [74].
Процесс взаимодействия в больших асинхронных системах, как правило, имеет сложную динамическую структуру. Для упрощения их описания в моделях указываются не непосредственные связи между событиями, а те ситуации (определенные сочетания условий), при которых данное событие может реализоваться.
В связи с этим дискретные системы представляются как структуры, образованные из элементов двух типов - событий и условий.
В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов (обычно переходы обозначаются буквой t) и множеством мест или позиций (обозначается буквой р).
Позиции и переходы связаны отношением непосредственной зависимости (непосредственной причинно-следственной связи), которая изображается с помощью направленных дуг. Позиции, из которых ведут дуги на переход, называются входными позициями данного перехода, а позиции, к которым ведут дуги из данного перехода, называются выходными для данного перехода
Выполнение условия отображается разметкой соответствующей позиции с помощью помещения в нее маркеров (фишек), при этом количество маркеров в позиции указывает на емкость условия. В процессе функционирования сети Петри происходит смена разметок позиций как результат срабатывания ее переходов. Сеть останавливается, если ни один из ее переходов не может сработать.
Г рафическим представлением сети Петри служит двудольный ориентированный граф с двумя типами вершин, при этом вершины-позиции изображаются кружочками, а вершины-переходы - барьерами (планками). В сети Петри допускается существование кратных дуг, в этом случаем графическим ее представлением является мультиграф (рисунок 4.13).
Формально сеть Петри определяется набором С = {P,T,F,M}, где Р - непустое множество позиций сети, Т - непустое множество переходов сети, F - отношение инцидентности, то есть отображение переходов в комплекты позиций и наоборот FcPxruTxP, М0 - функция начальной разметки сети.
Пример графа сети Петри.
Обозначение позиций и переходов соответствует принятым для описания сетей Петри-Маркова.
Функционирование сети Петри описывается формально с помощью множества последовательностей срабатываний переходов и множества достижимых в сети разметок. Переход может сработать при некоторой разметке М, если каждое входное место перехода t имеет разметку с количеством маркеров (фишек), не меньшим, чем кратность дуги, соединяющей позицию р и переход t. Формально это записывается следующим образом:
переход (, е Т в маркированной сети Петри с маркировкой fieM разрешен, если для всех р,^Р выполняется условие /и(р,) S w(pj,I(tj)), где w - количество дуг (с учетом кратности), входящих в переход о из позиции pt.
При этом переход запускается удалением всех разрешающих фишек из его входных позиций (то есть разметка каждой его входной позиции р. уменьшается на величину кратности дуги, соединяющей позицию р. и переход Г) и последующим помещением в каждую из его выходных позиций
по одной фишке для каждой дуги. Сеть Петри считается ординарной, если кратность всех ее дуг не превышает единицы.
Разметка М достижима из разметки М, если существует последовательность разметок М ,МѴМ2,...,М' ислово г =t]t2...tk в алфавите Г такие, что имеет место отношения [ } непосредственного следования
Множество всех последовательностей срабатываний сети Петри называют свободным языком сети Петри, при этом рассматриваются все разметки сети, достижимые из начальной разметки М0 и составляющие множество R(C,M0)- Язык сети Петри используется при ее анализе в интересах выявления характеристик моделируемой системы.
В ходе такого анализа часто важным для практики оказывается выявление наличия таких свойств сети как ограниченность и безопасность, достижимость и живость (активность переходов). Достаточно полно характеристика этих свойств приведена в [74].
Аппарат сетей Петри быстро привлек внимание специалистов, занимающихся вопросами моделирования систем. Однако скоро стало понятно, что классические сети Петри имеют определенные ограничения, не позволяющие адекватно моделировать многие системы. В результате появились многочисленные модификации этого аппарата и разнообразные подклассы сетей Петри. Краткая характеристика некоторых из них приведена в таблице 4.8.
Аппарат сетей Петри нашел применение и при решении вопросов технической защиты информации в ИС. Сегодня уже сформировалось несколько направлений использования этого аппарата в данной области, к которым относятся следующие.
1. Анализ программных кодов на предмет выявления в них уязвимостей, которые могут быть использованы для реализации угроз безопасности информации. В частности, уже в первых работах [74, 75] по практическому применению сетей Петри было предложено их использование при моделировании процессов анализа кодов в интересах выявления недопустимых конструкций кода, тупиков, непредусмотренных циклов, приводящих к зависанию программы и т.д., а в [76] изложен один из подходов к применению сетей Петри для решения задач анализа структурной динамики параллельных программ. Вместе с тем разработка методов анализа программного обеспечения с использованием сетей Петри в интересах оценки возможностей реализации угроз безопасности информации в ИС находятся в самой начальной стадии.
2. Моделирование процессов обнаружения сетевых атак на ИС. Так, в [77] предложено использовать для реализации алгоритма обнаружения сетевых атак формализм раскрашенных сетей Петри. В такой модели раскрашенная сеть Петри описывает сценарий атаки, при этом каждая сигнатура вторжения соответствует экземпляру сети Петри, которая может иметь более одного начального состояния, что обеспечивает частичную упорядоченность, и единственное конечное состояние. Сигнатура считается распознанной при достижении конечного состояния сети. С переходом могут быть связаны условные выражения, определяющие логические условия его срабатывания. С сетью Петри связано множество переменных.
Каждый маркер поддерживает собственную копию переменных в связи с тем, что каждый маркер может связать различные переменные в процессе распознавания (в терминах раскрашенной сети Петри каждый маркер является цветным; при этом цвет может рассматриваться как кортеж, состоящий из п строк, если сигнатура имеет п переменных).
Хотя использование данного метода позволяет обнаруживать широкий спектр сетевых атак, он требует значительных вычислений (время распознавания экспоненциально по отношению к размеру раскрашенных сетей Петри), и пока не может использоваться в системах обнаружения атак реального времени.
3. Моделирование межсетевых протоколов передачи сообщений в компьютерных сетях, в том числе в интересах обеспечения безопасности передаваемых по сети пакетов. Так, в [80] описано использование аппарата сетей Петри для выявления ошибок в протоколах, наличия тупиков, анализа выполнимости процедур проверки пакетов с неверными номерами, наличие недопустимых циклов обработки пакетов и т.д.
4. Моделирование процессов защиты информации с применением разнообразных мер и средств ТЗИ. Так, в [81] сети Петри использовались для имитационного моделирования и исследования эффективности ложных информационных систем, используемых для отвлечения нарушителя на ложный информационных ресурс. Такие модели могут создаваться также в интересах исследования программных способов разграничения доступа к процедурам, функциям, модулям программ, файлам, каталогам и директориям, полям и записям в базах данных, к программно-аппаратным элементам ИС.
Вместе с тем, аппарат сетей Петри в основном применяется при имитационном моделировании ряда процессов, связанных с реализацией угроз безопасности информации, с возможностью применения некоторых мер защиты, с получением с использованием имитационных моделей статистических данных, необходимых для оценки эффективности средств защиты и др.
Краткая характеристика некоторых подклассов сетей Петри
|
Подкласс сети Петри |
Определение сети |
Достоинства сети |
Недостатки сети |
|
Ординарная сеть Петри |
Ординарной называют сеть Петри, у которой кратность любой позиции равна 0 или 1, то есть выполняется условие: М.р,Мі,))*\ иніР,’(Ю,)) £ 1 и для нее количество фишек в любой позиции не превышает 1. Если в сети Петри никакая позиция не может быть одновременно входом и выходом моделируемого процесса, то такую сеть называют сетью без петель или нерефлексивной сетью. Если ординарная сеть является нерефлексивной, то ее называют простой сетью Петри. |
Позволяет достаточно просто моделировать многие процессы |
Не позволяет моделировать процессы со сложными условиями, пересекающимися ветвями, стохастические процессы и учитывать фактор времени |
|
Автоматная сеть Петри |
Простая сеть Петри, в которой каждый переход имеет одно входное и ровно одно выходное место и через него может переместиться только одна фишка, то есть выполняется условие V/ е I/(О) 1 и н{6Н0) = 1 • Автоматная сеть безопасна тогда и только тогда, когда ее начальная разметка содержит ровно одну фишку |
Автоматная сеть допускает моделирование так называемого конвейерного параллелизма, когда несколько фишек независимо перемещаются по сети, а также отображать конфликтные ситуации, когда позиция является входной или выходной для нескольких переходов |
Не позволяет моделировать процессы со сложными условиями, стохастические процессы и учитывать фактор времени |
|
Сеть Петри «Синхронизиров анный граф» |
Простая сеть Петри, в которой в каждую позицию входит только одна дуга и из каждой позиции выходит только одна дуга, то есть выполняется условие: и<р,./(;,)) = ! uv.{p,.(H,t )) = \ |
Позволяет описывать несложные параллельные процессы |
Не позволяет моделировать конфликтные ситуации, стохастические процессы и учитывать фактор времени |
|
Свободные сети Петри (сеть Петри со свободным выбором) |
Сеть Петри, в которой любая дуга, ведущая от позиции к переходу, или начинается позицией, из которой не выходит ни одной другой дуги, или заканчивается переходом, в которые не ведет никакая дуга. Класс свободных сетей является подклассом ординарных сетей и строго включает в себя классы автоматных сетей и синхрографов |
Позволяет исследовать на безопасность многие несложные процессы, учитывать: наличие ловушек - позиций, которые одновременно являются входными и выходными для перехода (если ловушка размечена, то есть содержит хотя бы одну фишку, то при функционировании сети она всегда остается размеченной, так как любая фишка, попавшая в ловушку, не может исчезнуть из нее); наличие тупиков -позиций, помещая в каждую из которых фишку, соответствующий переход должен забирать по крайней мере одну фишку из нее (если тупик пуст, то соответствующий переход мертв). В сильно связных сетях позиция может быть одновременно и ловушкой, и тупиком |
Те же, что и для ординарных сетей |
|
Сеть Петри «мар кированны й граф» |
Это сеть Петри, в которой каждая позиция является входом для точно одного перехода и выходом точно оного перехода. Двойственна автоматной сети Петри, так как в автоматной сети переходы имеют один вход и один выход, в маркированном графе позиции имеют один вход и один выход |
Те же, что и в автоматных сетях Петри |
Те же, что и в автоматных сетях Петри |
|
Подкласс сети Петри |
Определение сети |
Достоинства сети |
Недостатки сети |
|
Ингибиторная сеть Петри |
Это сеть Петри, дополненная специальной функцией инцидентности /*): РхГ —> {0,1}, которая вводит ингибиторные дуги («сдерживающие дуги» [74]). Она обеспечивает возможность проверки на нулевую разметку, что не позволяют делать обычные сети. Ингибиторная дуга обозначается не стрелкой на конце, а кружком. Переход / может сработать, если каждая его входная позиция р, соединенная с / обычной дугой с кратностью «</>,/) , содержит не менее мі р.І) фишек, а каждая входная позиция, соединенная с переходом f ингибиторной дугой (ее кратность всегда равна 1), имеет нулевую разметку, что формально записывается следующим образом: |
Значительно расширяет возможности моделирования процессов, так как позволяет проверять позиции на нулевую разметку, управлять срабатываем переходов путем ввода условий их срабатывания |
Не позволяет учитывать фактор времени |
|
Сеть Петри с приоритетами |
Это сеть Петри, дополненная частично упорядоченным множеством приоритетов PR , каждый из которых связан с определенным переходом pr{l)e. PR .Переход f может сработать, если для любого другого перехода (\ который может сработать по стандартному условию, выполняется соотношение рг[1) ^ pr{t) |
Позволяет моделировать функционирование дискретных систем, в которых необходим неодновременный запуск нескольких устройств со строго определенной последовательностью. Равносильна по возможностям моделирования ингибиторным сетям |
То же |
|
Временная сеть |
Это сеть Петри, в которой переходы обладают весом, определяющим продолжительность их срабатывания (задержку). Равносильна сети с приоритетом и ингибиторной сети. Разновидностью временных сетей являются стохастические сети, в которых задержки в срабатывании переходов являются случайными |
Позволяет моделировать функционирование систем с учетом временного фактора |
Большая громоздкость учета в модели временного фактора, сложность учета временных параметров парциальных процессов, составляющих моделируемый процесс. Невозможность учета времени срабатывания логических стохастических переходов |
|
Раскрашенная (цветная) сеть Петри |
Это сеть Петри [74], фишкам которой приписывают дополнительные атрибуты, которые названы цветами. Условия срабатывания переходов и правила изменения разметки сети задаются специальными таблицами, учитывающими цвета фишек. В каждой такой таблице столбцы, связанные с входными позициями перехода, содержат сочетания конкретных цветных фишек, при которых переход может сработать. Столбцы, связанные с выходными позициями, указывают цвета фишек, которые добавляются в выходные позиции для каждого входного сочетания цветных фишек |
Раскрашенная сеть равномощна ингибиторным сетям и сетям с приоритетом |
Те же, что и для ингибиторных сетей |
|
Подкласс сети Петри |
Определение сети |
Достоинства сети |
Недостатки сети |
|
Самомодифицир уемая сеть Петри |
В соответствии с [74] в сетях данного класса каждой дуге (/>,/) и (/,/>) приписана модифицируемая кратность. В качестве кратности может выступать не только число, как в определении сетей Петри, но и символ (например, q ) некоторой позиции данной сети, в этом случае кратность дуги переменна и равна текущей разметке M{q) позиции q . Поскольку разметка позиции q динамически меняется при работе сети, число фишек, перемещаемых одним и тем же переходом, динамически меняется при разных срабатываниях этого перехода |
Введение модифицируемой кратности позволяет достаточно просто моделировать ингибиторные сети и сети с приоритетами |
Те же, что и для ингибиторных сетей |
|
Иерархическая сеть Петри |
Эта сеть, наряду с неделимыми (атомарными) компонентами, содержит составные компоненты, сами представляющие собой системы. |
Является существенным обобщением сетей Петри. Позволяет моделировать процессы в иер архичес ких стру ктур ах |
В практике моделирования процессов реализации угроз в ИС не применялась |
|
WF-сети |
WF-сети - это подкласс сетей Петри, называемый также сетями потоков работ. Сеть Петри называется сетью потоков работ (WF- сетью), если выполняются следующие условия: существует только одна исходная позиция, такая что отсутствуют входящие переходы, инцидентные этой позиции; существует только одна конечная позиция, такая что отсутствуют выходящие переходы, инцидентные этой позиции; каждый узел данной сети расположен на пути от указанных исходной и конечной позиций [78] |
WF-сети позволяют проверять графы потоков работ на наличие структурных конфликтов, таких как наличие тупиков, что имеет место, если: конечная позиция достижима при любой последовательности переходов от исходной позиции; WF-сеть не содержит лишних позиций (которые никогда не будут выполнены); при достижении конечной позиции не должно оставаться фишек в промежуточных позициях |
То же |
|
Е-сеть |
Е-сети (от англ. Evaluation - «вычисления», «оценка») - «оценочные сети», относящиеся к подклассу сетей Петри [79]. В Е- сетях: • имеются несколько типов вершин-позиций: простые позиции, позиции-очереди, разрешающие позиции; - фишки могут снабжаться набором признаков (атрибутов); - с каждым переходом может бытъ связана ненулевая задержка и функция преобразования атрибутов фишек; - введены дополнительные виды вершин-переходов; - в любую позицию может входить не более одной дуги и выходить также не более одной |
Применяются для оценки производительности систем, моделирования динамики выполнения процессов |
Не позволяет в должной мере исследовать динамику процесса, поскольку временные его характеристики вводятся как исходные данные, а не вычисляются по результатам срабатывания сети |
