Темы исследований студентов. Модели на графах

Темы исследований студентов. Модели на графах.

1 Графовые модели в безопасности

1.1 Графовые нейронные сети (GNN) для обнаружения угроз

• Графовые нейросети используются для поиска сложных аномалий в сетевом трафике.

• Обнаружение аномалий и вторжений (NIDS)

  • Разработка системы на базе GNN для выявления сложных сетевых атак, в т.ч. в зашифрованном трафике, с акцентом на снижение ложных срабатываний.

• Фазовые графы для кибербезопасности

  • Применение GNN к фазовым графам, построенным на временных рядах сетевой активности.
  • Позволяют выявлять аномалии в поведении сети без предварительного расчета сложных признаков.

• Объяснимые GNN для верификации безопасности

  • Использование объяснимого искусственного интеллекта (XAI) для интерпретации решений GNN.

1.2 Графы атак (Attack Graphs) и управление рисками

• Графы атак есть инструмент для моделирования и визуализации путей, которыми злоумышленник может проникнуть в систему.

• Динамическое моделирование кибератак

  • Исследование того, как действия злоумышленника могут менять саму структуру системы (например, в облачных средах), и разработка формализма для описания таких атак с помощью динамических графов.

• Интеграция с киберфизическими системами (CPS)

  • Разработка методов оценки рисков для CPS (энергосистемы, заводы) путем объединения графов атак с моделями операционных процессов.

• Метрики на основе графов атак

  • Разработка метрик безопасности.

1.3 Теория графов для моделирования и защиты сетей

• Применение фундаментальных концепций теории графов для повышения устойчивости сети.

• Адаптивная топология сети

  • Разработка модели сети, которая может динамически менять свою топологию в ответ на атаки, что особенно актуально для крупных инфраструктур.

• Защита от множественных атак

  • Создание эвристических алгоритмов для оптимального размещения защитных ресурсов в узлах сети при условии одновременных атак.

• Моделирование сетевой инфраструктуры

  • Построение графовой модели сложного объекта для анализа его устойчивости к кибератакам.

1.4 Безопасность в специализированных сетях: IoT, SDN и КИИ

• Обнаружение вторжений в IoT
  • Создание двухуровневой системы на основе GNN для выявления аномального поведения устройств в сетях IoT.
• Оптимизация размещения IoT-устройств
  • Анализ графа атак для поиска такого физического расположения устройств, которое минимизирует риски для всей сети.
• Обнаружение атак в промышленных сетях
  • Проектирование специализированных систем для защиты АСУ ТП.
• Программно-конфигурируемые сети (SDN)
  • Обнаружение DDoS-атак в SDN с помощью графовых методов.

1.5 Графовые модели для анализа вредоносного ПО

• Обнаружение на основе поведения
  • Построение графа вызовов API и анализ его центральности или аномалий для выявления вредоносной активности.
• Анализ путей заражения
  • Восстановление графа распространения вредоносного ПО по сети.

1.6 Графовые методы для анализа социальных сетей и дезинформации

• Выявление ботов
  • Классификация аккаунтов в соцсетях на основе графа их связей.
• Обнаружение дезинформации
  • Анализ графа распространения новости для выявления фейков по характерным паттернам.
• Анализ Darknet
  • Исследование графов скрытых сервисов (Tor, I2P) для выявления ключевых узлов и незаконных сообществ.

1.7 Формальная верификация и доказательство безопасности

• Верификация протоколов
  • Доказательство свойств безопасности криптографических протоколов с помощью графовых моделей.
• Моделирование мандатного доступа (MAC)
  • Применение конечных динамических систем на графах, где состояние системы описывается ориентациями графа, для анализа политик безопасности.

2 Графовые аналитические модели

2.1 Общая информация

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

2.2 Эпидемиологические модели на графах

• Классические компартментные модели (SIR, SIS, SEIR) переносятся на графовую структуру, где каждый узел находится в одном из состояний, а заражение происходит по рёбрам.
• Моделирование распространения червей, ботнетов, вредоносного ПО в корпоративных сетях.
• Оценка эффективности карантина и вакцинации узлов.

2.2.1 Математическая формализация

• Дискретная версия (разностные уравнения)

  • Для каждого узла \(i\) вероятность быть заражённым на шаге \(t+1\) зависит от состояний соседей. \(p_i(t+1) = 1 - \prod_{j \in N(i)} (1 - \beta \cdot p_j(t))\), где \(\beta\) — вероятность передачи инфекции по ребру, \(N(i)\) — соседи узла \(i.

• Непрерывная версия (система ОДУ, приближение среднего поля)

  • Для однородной сети со средней степенью \(\langle k \rangle\): \(\frac{ds}{dt} = -\beta \langle k \rangle s i\), \(\frac{di}{dt} = \beta \langle k \rangle s i - \gamma i\), \(\frac{dr}{dt} = \gamma i\).
  • На реальном графе вместо \(\langle k \rangle\) можно использовать спектральный радиус \(\lambda_1\) матрицы смежности: порог эпидемии \(\beta / \gamma > 1/\lambda_1\).

2.3 Модели распространения влияния

• Процесс активации узлов под влиянием уже активных соседей.
• Для анализа вирусного маркетинга, социальной инженерии, распространения дезинформации.
• Модели формализуются как задачи максимизации влияния (NP-трудные), решаемые жадными алгоритмами.
• Реализация: симуляции на графе, оптимизация выбора стартовых узлов.

2.3.1 Independent Cascade (IC)

• Каждое ребро \((u,v)\) имеет вероятность \(p_{uv}\).
• В момент, когда узел \(u\) становится активным, он с вероятностью \(p_{uv}\) пытается однократно активировать соседа \(v\).
• Процесс продолжается, пока есть новые активации.
• Математически это стохастический процесс на графе.
• Ожидаемое число активированных узлов вычисляется через Монте-Карло или аппроксимации.

2.3.2 Linear Threshold (LT)

• Каждый узел \(v\) имеет порог \(\theta_v \in [0,1]\).
• Узел активируется, если сумма весов активных соседей \(\sum_{u \in N_{active}(v)} w_{uv} \ge \theta_v\).
• Веса нормированы: \(\sum_{u \in N(v)} w_{uv} \le 1\).

2.4 Случайные графовые модели

• Генерация синтетических топологий, имитирующих реальные сети.
• Теоретический анализ устойчивости.
• Вычисление критических порогов перколяции, исследование влияния топологии на распространение угроз, тестирование алгоритмов защиты.
• Реализация: генерация графов.

2.4.1 Модель Эрдёша–Реньи

• Каждое ребро появляется независимо с вероятностью \(p\).
• Математические свойства: распределение степеней — биномиальное (приближается к пуассоновскому), порог связности \(p_c \approx \ln n / n\).

2.4.2 Модель Барабаши–Альберт

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

2.4.3 Модель Уоттса–Строгаца

• Начинается с регулярной решётки, рёбра переподключаются с вероятностью \(p\).
• Позволяет получить высокий коэффициент кластеризации при малом среднем расстоянии.

2.5 Марковские процессы на графах

• Динамика состояний узлов моделируется цепями Маркова, где переходные вероятности зависят от соседей.
• Реализация: решение уравнений Чепмена–Колмогорова, вычисление фундаментальной матрицы.

2.5.1 Случайное блуждание

• Стационарное распределение пропорционально степеням узлов.
• Применяется в алгоритме PageRank, для оценки важности узлов, моделирования перемещения злоумышленника по сети.

2.5.2 Цепи Маркова для состояний безопасности

• Узел может быть в состояниях: нормальный, заражённый, изолированный, восстановленный.
• Матрица переходов \(P\) строится на основе параметров атаки и защиты.
• Анализ вероятностей достижения компрометации, среднего времени до поглощения.

2.5.3 Скрытые марковские модели на графах

• Наблюдаемые события (трафик, логи) зависят от скрытых состояний узлов.
• Граф задаёт зависимости между скрытыми состояниями соседей (например, в распределённых атаках).

2.6 Графы атак и деревья атак

• Формальные модели для представления последовательностей действий нарушителя.
• Позволяет количественно сравнивать сценарии атак, выбирать оптимальные контрмеры, оценивать риск.

2.6.1 Граф атак

• Вершины — состояния системы (права доступа, конфигурации).
• Рёбра — действия, переводящие из одного состояния в другое.
• Поиск путей из начальной вершины в целевую.
• Оценка вероятности достижения цели через умножение вероятностей на рёбрах, если они независимы.
• Вычисление минимального набора защитных мер — задача о минимальном разрезе.

2.6.2 Дерево атак

• Корень — цель, листья — атомарные действия, внутренние узлы — логические операторы AND/OR.
• Вычисление вероятности успеха, стоимости, времени атаки рекурсивно:
  • для AND: \(P = \prod P_i\);
  • для OR: \(P = 1 - \prod (1-P_i)\).
• Можно расширить до ациклических графов с общими поддеревьями.

2.7 Модели надёжности и перколяции

• Оценивается связность сети при отказах или атаках.
• Анализ живучести сети, планирование резервирования, оценка критичности узлов.
• Реализация: симуляции удаления узлов, аналитические формулы для порогов, вычисление размера гигантской компоненты.

2.7.1 k-терминальная надёжность

• Вероятность того, что заданное множество из \(k\) узлов останется связным при случайных отказах рёбер с вероятностью \(p_e\).
• Точное вычисление NP-трудно, но возможны аналитические формулы для простых топологий.
• Для сложных сетей используют методы факторизации или аппроксимации (границы Эзари–Прошана).

2.7.2 Перколяция на графах

• Удаление случайной доли \(1-p\) узлов (сайт-перколяция) или рёбер (бонд-перколяция).
• Критический порог \(p_c\), при котором исчезает гигантская компонента.
• Для случайных графов \(p_c = 1/\langle k \rangle\), для безмасштабных при \(\gamma \le 3\) порог стремится к нулю (устойчивы к случайным отказам, но уязвимы к намеренным атакам на хабы).

2.8 Спектральные методы анализа графов

• Собственные значения и векторы матриц, связанных с графом.
• Вычисление спектральных характеристик, использование их как метрик для оценки безопасности.

2.8.1 Матрица смежности

• Спектральный радиус \(\lambda_1\) определяет порог эпидемии, скорость распространения информации.
• Распределение собственных значений используется для обнаружения аномалий.

2.8.2 Лапласиан

• Второе наименьшее собственное значение (алгебраическая связность) характеризует, насколько трудно разорвать граф на компоненты.
• Собственные векторы лапласиана применяются в спектральной кластеризации для выделения сообществ.
• Можно выявлять ботнет-структуры.

2.8.3 Нормализованный лапласиан

• Спектральная теория случайных блужданий.
• Собственные значения связаны со временем перемешивания.

2.9 Дифференциальные уравнения на графах

• Изменение состояния узла описывается системой ОДУ, связанных через граф.

2.9.1 Модель консенсуса

• \(\dot{x}/i = \sum/{j \in N(i)} (x_j - x_i)\)
• Состояние узлов сходится к среднему, скорость зависит от алгебраической связности.
• Применяется для моделирования распространения обновлений, синхронизации, а также для анализа децентрализованных протоколов.

2.9.2 Реакционно-диффузионные модели

• Комбинация локальной динамики (реакция) и диффузии по рёбрам
• Распространение вредоносного ПО с размножением внутри узла. \(\frac{du_i}{dt} = f(u_i) + D \sum_{j \in N(i)} (u_j - u_i)\).

2.9.3 Модели типа «хищник–жертва» на сетя

• Взаимодействие защитных механизмов и вредоносного ПО.

2.10 Теоретико-игровые модели на графах

• Взаимодействие защитника и атакующего рассматривается как игра.
• Выигрыш зависит от топологии сети.

2.10.1 Игры на графах

• Выигрыш игрока зависит только от действий его соседей.
• Поиск равновесия Нэша сводится к решению систем уравнений; для потенциальных игр существует функция потенциала.

2.10.2 Задачи размещения защитных ресурсов

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

2.10.3 Эволюционные игры на графах

• Динамика репликаторов на сетях, где приспособленность узла зависит от соседей.
• Анализ устойчивости кооперации в зависимости от структуры графа.

2.11 Оптимизационные модели на графах

• Задачи распределения ограниченных ресурсов защиты.
• Задачи математического программирования с графовыми ограничениями.

2.11.1 Минимальный разрез

• Удаление минимального множества рёбер (или вершин), чтобы разорвать все пути между источником атаки и целью.
• Алгоритм максимального потока.

2.11.2 Размещение сенсоров

• Выбрать \(k\) узлов для установки датчиков, чтобы покрыть максимальное число путей атак или рёбер.
• Целочисленное линейное программирование, NP-трудно, аппроксимируется жадным алгоритмом.

2.11.3 Укрепление графа

• Минимизировать уязвимость сети, добавляя или удаляя рёбра при бюджетных ограничениях.

3 Библиография

Литература