CTMC: Рубежи защиты

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

Выберем состояния и договоримся о времени

В марковском процессе с непрерывным временем и дискретными состояниями система в каждый момент находится в одном из выбранных состояний. Состояний конечное число, а переход может произойти в любой момент, без привязки к шагу «раз в минуту» или «раз в сутки». Такую модель также называют непрерывной цепью Маркова, или Continuous-Time Markov Chain (CTMC).

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

Главное допущение — марковское свойство: при известном текущем состоянии для прогноза не требуется вся предыстория. Например, состояние «первоначальный доступ» должно содержать достаточно информации, чтобы дальнейшие переходы можно было описать без отдельного учёта всех действий нарушителя до входа.

Это требование к выбранной модели, а не свойство любой реальной атаки. Если вероятность обнаружения существенно зависит от уже проведённого внутри времени, одного состояния «внутри» может быть недостаточно: потребуется уточнить состояния или выбрать другой способ описания.

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

Зададим вероятности и начальное состояние

Пусть состояния обозначены . Вероятность находиться в состоянии в момент равна

В каждый момент система находится ровно в одном состоянии, поэтому

На одной истории нарушитель либо снаружи, либо внутри, либо уже заблокирован. Вероятности описывают неопределённость исхода, а при многократном повторении одинаковых условий — ожидаемые доли историй в этих состояниях. Они не означают, что один нарушитель «на 30 % находится внутри».

Сразу зададим начальное распределение . Здесь и далее — вектор-строка. Если точно известно, что система стартует из , то

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

Подпишем стрелки интенсивностями

Проведём стрелку , если такой непосредственный переход допустим. Подпись над ней — интенсивность перехода, то есть скорость соответствующего механизма. Если время измеряется в часах, размерность интенсивности — ч⁻¹.

Для малого интервала :

Остаток становится малым по сравнению с при уменьшении интервала. Формула относится именно к малому времени: значение интенсивности нельзя использовать как вероятность перехода за произвольный час. Вероятность не превосходит единицы, а интенсивность может быть больше единицы в выбранных единицах времени.

Отсутствие стрелки означает отсутствие непосредственного перехода. Достичь того же состояния через промежуточные вершины всё ещё может быть возможно.

Сколько ждать и куда переходить

Сложим интенсивности всех выходов из :

При время до выхода имеет экспоненциальное распределение:

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

Например, если из состояния «внутри» возможны получение привилегий с интенсивностью и блокировка с интенсивностью , то среднее ожидание любого из этих событий равно , а вероятность блокировки при выходе — . Величина характеризует механизм блокировки без конкурирующего выхода; это не средняя длительность состояния при наличии обоих переходов.

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

Составим уравнения по графу

Вероятность каждого состояния меняется за счёт входов и выходов. Для запишем входящие потоки со знаком «плюс», исходящие — со знаком «минус»:

Входящий поток содержит вероятность того состояния, откуда идёт стрелка, умноженную на интенсивность этой стрелки. Исходящие потоки содержат вероятность текущего состояния. Это правило составления уравнений Колмогорова для вероятностей состояний.

Посмотрим на небольшой пример. Сервис находится либо в рабочем состоянии , либо в состоянии отказа . Отказ происходит с интенсивностью , восстановление — с интенсивностью .

Для рабочего состояния получим приток после восстановления и отток при отказе. Для неработающего — наоборот:

Сложим правые части: потоки сократятся. Поэтому сохраняется и при корректных начальных условиях остаётся равным единице. Такую проверку удобно делать для любой составленной системы.

Соберём матрицу интенсивностей

Зафиксируем один порядок состояний для строк и столбцов. Вне диагонали запишем интенсивности переходов, а на диагонали — суммарную интенсивность выхода со знаком «минус»:

Получили матрицу интенсивностей, или генератор . Её строка отвечает на вопрос «откуда переходим», столбец — «куда». Вне диагонали значения неотрицательны, на диагонали неположительны, сумма каждой строки равна нулю.

Для примера с сервисом в порядке :

Теперь обе системы — общая и двухсостоянийная — записываются одной строкой:

Отрицательная диагональ не задаёт «отрицательную вероятность»: она учитывает потерю вероятности при выходе. При использовании вектора-столбца формула имела бы вид . Смешивать эти два соглашения нельзя.

Получим прогноз на заданное время

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

В начале — единичная матрица. Через время распределение состояний равно

Чтобы пройти интервал , можно сначала рассмотреть переходы за , затем — за и просуммировать по всем промежуточным состояниям. Это даёт соотношение Чепмена — Колмогорова:

На малом интервале . Подставив это разложение в последнее соотношение и перейдя к производной, получим прямые уравнения Колмогорова:

При выделении малого интервала в начале получается обратная форма . Для постоянной матрицы решение обеих форм выражается через матричную экспоненту:

Это экспонента всей матрицы, а не поэлементное вычисление . Если интенсивности меняются со временем, простая подстановка в эту формулу в общем случае неверна: требуется решать систему с переменной матрицей.

Не будем смешивать три разных объекта: — интенсивность, — вероятность направления следующего скачка, — вероятность оказаться в состоянии через заданное время. Последняя учитывает также промежуточные переходы и ожидания.

Найдём стационарное распределение

Распределение называется стационарным, если при старте из него вероятности больше не меняются. Подставим постоянное распределение в уравнение Колмогорова: его производная равна нулю, поэтому

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

Решим баланс для двух состояний

Пусть и . Для сервиса достаточно равенства потоков и нормировки:

Выразим и подставим в сумму. Получим

Увеличение скорости восстановления повышает стационарную долю рабочего времени. Это вывод для модели с повторяющимися отказами и восстановлениями, а не прогноз единственного инцидента к ближайшему сроку.

Когда решение единственно

Сначала посмотрим на структуру графа. Если из любого состояния можно по допустимым стрелкам добраться до любого другого, конечная цепь неприводима. Для неё существует единственное стационарное распределение, и при увеличении времени распределение состояний сходится к нему из любого начального состояния.

В этом случае ранг равен . Одно из зависимых уравнений можно заменить нормировкой и решить линейную систему. Условие неотрицательности служит дополнительной проверкой результата.

Если же на графе несколько замкнутых классов, из которых нет выхода, стационарных распределений несколько. В частности, каждое поглощающее состояние уже даёт стационарное распределение: вся вероятность сосредоточена в нём. Предельный результат может зависеть от старта и от вероятностей попадания в эти классы. Поэтому находить стационарные вероятности без предварительного просмотра графа недостаточно.

Применим аппарат к «Защитнику»

Общая теория допускает разные графы. В игре «Защитник» выбран один эпизод атаки с семью состояниями:

Здесь буква без аргумента обозначает состояние, а — введённую выше переходную матрицу.

Каждой стрелке соответствует один параметр:

Все интенсивности здесь измеряются в ч⁻¹. Граф показывает объединение допустимых переходов. В сценарии кражи отключён переход разрушения: . В сценарии разрушения отключена кража: . Начало эпизода также зависит от сценария: внешний нарушитель стартует из , внутренний — из , привилегированный — из .

По тому же правилу входов и выходов получим:

Например, вероятность состояния растёт после получения привилегий и уменьшается при любом из трёх выходов: блокировке, краже или разрушении. В матрице строка поэтому содержит , , в столбцах назначения и на диагонали. Для поглощающих , , строки нулевые.

Почему здесь важен горизонт, а не только стационарность

Из , и нет возврата: эпизод завершён. Модель не описывает новые независимые атаки после восстановления. При положительных базовых интенсивностях и предусмотренных мерах состояния , , , переходные, а стационарные распределения имеют вид

Для конкретного старта достижимы не все такие смеси. Например, в сценарии кражи из недостижимо . Нужную предельную смесь определяют вероятности поглощения, а не одно лишь уравнение .

В игре исследуется результат к заданному времени . Замедление проникновения может оставить эпизод незавершённым к этому сроку. Это полезный эффект на выбранном горизонте, но он не означает, что нарушитель никогда не доберётся внутрь. При сохранении единственного выхода с изменение меняет ожидание входа, а не вероятность когда-либо совершить этот переход.

Разделим исход, вероятность и длительность

Одна случайная история отвечает на вопрос «что случилось в этом эпизоде». Прогноз отвечает на вопрос «с какими вероятностями возможны состояния к сроку ». Один удачный исход ещё не доказывает качество набора защиты.

Для этой модели вероятность кражи к сроку равна : состояние поглощающее. Вероятность уже произошедшего разрушения равна

Восстановленный сервис уже покинул , но сам факт разрушения не исчез. Поэтому отдельно не даёт вероятность произошедшего инцидента.

Ожидаемый суммарный простой до срока определяется всей кривой вероятности , а не только её последним значением:

Интеграл измеряется в часах. В терминах отдельных историй мы усредняем время, проведённое в , учитывая только часть эпизода до . Ускорение восстановления сокращает это время, но не отменяет уже случившееся разрушение.

Свяжем меры защиты с переходами

В «Защитнике» выбор мер меняет интенсивности, сохраняя выбранный граф. Защита внешнего входа уменьшает , разграничение прав замедляет переход , мониторинг ускоряет блокировку и . Контроль критических операций замедляет и и усиливает блокировку у цели; подготовка восстановления увеличивает .

Начнём сравнение с вопроса: какую стрелку меняет мера и достижима ли она из нашего старта? Затем зафиксируем одинаковые начальное состояние и горизонт, чтобы различия результатов относились к защите. Стоимость и эффективность мер в игре условные; эта модель помогает исследовать механизм решения, а не выбирает продукты для реальной инфраструктуры.

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

Продолжим исследование

Эксперимент: свяжем граф, матрицу и прогноз

Цель — объяснить, как изменение переходов меняет вероятности и ожидаемые последствия.

Зафиксируем сценарий и горизонт. Изменим одну меру защиты и сравним интенсивности, кривые вероятностей и ожидаемые последствия. Отдельно посмотрим на вероятность ущерба и ожидаемый простой: улучшение одного показателя не обязано одинаково менять другой.

Игра: примем решение при ограниченном бюджете

Цель — выбрать сочетание мер и обосновать его действие через модель.

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

Реализация в Scilab: другой пример той же теории

В статье «Динамическая вероятностная модель взаимодействия САЗ ИС» рассмотрен другой граф — взаимодействие пяти программных компонентов активной защиты. Там можно проследить переход от системы уравнений к коду Scilab и поиску стационарных вероятностей. Это самостоятельный пример, а не продолжение графа «Защитника».

При сопоставлении формул учтём обозначения: в той статье используется вектор-столбец и матрица , здесь — вектор-строка и генератор . При одинаковом порядке состояний эти соглашения связаны транспонированием: .