2025-11-15T15:52:10.939408

DEHYDRATOR: Enhancing Provenance Graph Storage via Hierarchical Encoding and Sequence Generation

Ying, Zhu, Lv et al.
As the scope and impact of cyber threats have expanded, analysts utilize audit logs to hunt threats and investigate attacks. The provenance graphs constructed from kernel logs are increasingly considered as an ideal data source due to their powerful semantic expression and attack historic correlation ability. However, storing provenance graphs with traditional databases faces the challenge of high storage overhead, given the high frequency of kernel events and the persistence of attacks. To address this, we propose Dehydrator, an efficient provenance graph storage system. For the logs generated by auditing frameworks, Dehydrator uses field mapping encoding to filter field-level redundancy, hierarchical encoding to filter structure-level redundancy, and finally learns a deep neural network to support batch querying. We have conducted evaluations on seven datasets totaling over one billion log entries. Experimental results show that Dehydrator reduces the storage space by 84.55%. Dehydrator is 7.36 times more efficient than PostgreSQL, 7.16 times than Neo4j, and 16.17 times than Leonard (the work most closely related to Dehydrator, published at Usenix Security'23).
academic

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

Основная информация

  • ID статьи: 2501.00446
  • Название: DEHYDRATOR: Enhancing Provenance Graph Storage via Hierarchical Encoding and Sequence Generation
  • Авторы: Jie Ying, Tiantian Zhu*, Mingqi Lv, Tieming Chen (Чжэцзянский технологический университет)
  • Категория: cs.CR (Криптография и безопасность)
  • Журнал публикации: IEEE Transactions on Information Forensics and Security
  • Ссылка на статью: https://arxiv.org/abs/2501.00446

Аннотация

С расширением масштабов и влияния киберугроз аналитики используют журналы аудита для отслеживания угроз и расследования атак. Графы происхождения, построенные из журналов ядра, все чаще рассматриваются как идеальный источник данных благодаря их мощной семантической выразительности и способности отслеживать историю атак. Однако из-за высокой частоты событий ядра и устойчивости атак использование традиционных баз данных для хранения графов происхождения сталкивается с проблемой высоких затрат на хранение. Для решения этой проблемы в статье предлагается DEHYDRATOR — эффективная система хранения графов происхождения. Для журналов, генерируемых фреймворками аудита, DEHYDRATOR использует кодирование сопоставления полей для фильтрации избыточности на уровне полей, иерархическое кодирование для фильтрации избыточности на уровне структуры и, наконец, глубокую нейронную сеть для поддержки пакетных запросов. При оценке на семи наборах данных с общим количеством более одного миллиарда записей журналов результаты экспериментов показывают, что DEHYDRATOR сокращает пространство хранения на 84,55%, что в 7,36 раза эффективнее PostgreSQL, в 7,16 раза эффективнее Neo4j и в 16,17 раза эффективнее Leonard.

Исследовательский контекст и мотивация

Предпосылки проблемы

  1. Рост киберугроз: По состоянию на май 2024 года произошло 9478 утечек данных, при этом событие MOAB в январе 2024 года привело к утечке 26 миллиардов записей
  2. Значимость графов происхождения: Графы происхождения как структуры ориентированных графов, где узлы представляют системные сущности (процессы, файлы, сокеты), а рёбра представляют системные события, обладают мощной семантической выразительностью и способностью отслеживать историю атак
  3. Проблемы хранения: Четыре явления создают трудности при хранении:
    • Необратимый рост: Для сохранения целостности данных добавляются только новые данные, удаление исключено
    • Быстрое расширение: Каждая машина генерирует журналы размером в гигабайты в день
    • Длительный период: Среднее время обнаружения вторжения составляет 188 дней
    • Требования к запросам: Необходимо поддерживать крупномасштабные запросы для охоты на угрозы и причинно-следственного анализа

Ограничения существующих методов

Существующие эффективные системы хранения графов происхождения (ESSPGs) делятся на две категории:

  1. Методы на основе обрезки (LogGC, CPR, NodeMerge, DPR): Сжатие с потерями, которое может привести к ложноотрицательным результатам в компонентах верхнего уровня
  2. Методы на основе кодирования (SEAL, SLEUTH, ELISE, Leonard): Либо не поддерживают запросы, либо вспомогательные компоненты занимают значительное пространство хранения

Исследовательская мотивация

Существующие методы не могут одновременно удовлетворить трём ключевым требованиям:

  • Сохранение содержимого: Сохранение всех данных для избежания ложноотрицательных результатов
  • Эффективность хранения: Минимизация затрат на хранение
  • Поддержка запросов: Обработка крупномасштабных запросов

Основные вклады

  1. Предложение системы DEHYDRATOR: Эффективная система хранения графов происхождения, преодолевающая ограничения существующих методов, использующая кодирование сопоставления полей для фильтрации избыточности на уровне полей, иерархическое кодирование для фильтрации избыточности на уровне структуры и глубокую нейронную сеть для поддержки пакетных запросов
  2. Построение прототипной системы и крупномасштабная оценка: Оценка на семи наборах данных (более одного миллиарда журналов) показывает сокращение пространства хранения на 84,55%, что в 7,36 раза эффективнее PostgreSQL, в 7,16 раза эффективнее Neo4j и в 16,17 раза эффективнее Leonard
  3. Комплексный анализ оценки: Исследование влияния компонентов, применимых сценариев и нижних границ производительности, определение метрики коэффициента задержки хранения (LSR) для балансирования затрат на хранение и задержки

Подробное описание методологии

Определение задачи

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

Архитектура системы

DEHYDRATOR использует трёхэтапный фреймворк:

1. Этап предварительной обработки (Pretreatment)

  • Анализ журналов: Использование регулярных выражений для извлечения ключевых полей из исходных журналов
  • Построение графа происхождения: Построение таблицы узлов NT (IdentiID, Name, Type) и таблицы рёбер ET (SrcID, DstID, TimeStamp, Operation)
  • Кодирование сопоставления полей: Обработка трёх типов избыточности на уровне полей
    • Уникальные значения: Замена более короткими числовыми символами
    • Повторяющиеся значения: Замена индексами
    • Дополнительные значения: Замена смещениями

2. Этап хранения (Storage)

Иерархическое кодирование:

  • Моделирование графа происхождения как иерархического ориентированного графа
  • Для каждого узла v запись всех исходных узлов и информации о входящих рёбрах
  • Построение объединённой таблицы сопоставления MMT и иерархической таблицы рёбер EThi
  • Структура вложенного списка: Operation: timeOffset: nodeOffset

Обучение модели:

  • Выбор однослойного декодера Transformer
  • Моделирование задачи хранения как задачи генерации последовательности
  • Использование кодирования char2vec, авторегрессивная генерация
  • Построение таблицы исправления ошибок ECT для обработки ошибок предсказания модели

3. Этап запроса (Query)

  • Информация узла: Получение индекса через таблицу сопоставления MT, извлечение информации узла
  • Информация ребра: Ввод индекса в модель DNN, генерация последовательности, исправление ошибок ECT, иерархическое декодирование для получения читаемой информации

Технические инновации

  1. Проектирование иерархического кодирования:
    • На основе характеристик обратного запроса причинно-следственного анализа
    • Сжатие нескольких параллельных рёбер в компактную форму кодирования
    • Увеличение плотности информации, ускорение обучения модели
  2. Выбор модели DNN:
    • Однослойный декодер Transformer вместо многослойного LSTM
    • Лучшие возможности параллелизации и извлечения признаков
    • Подходит для распознавания низкоуровневых повторяющихся паттернов в задачах хранения
  3. Механизм исправления ошибок:
    • Таблица ECT записывает позицию и правильный символ
    • Гарантирует сохранение содержимого при поддержке сжатия DNN

Экспериментальная установка

Наборы данных

Семь наборов данных с общим количеством более одного миллиарда журналов:

  • G1-G4: CADETS, THEIA, TRACE группы DARPA TC E3
  • G5-G6: TRACE группа DARPA TC E4
  • G7: Подмножество набора данных DEPIMACT
  • Среднее количество рёбер: 17 754 566 (в 9,6 раза больше, чем Leonard)

Метрики оценки

  • Затраты на хранение: BPpre (предварительная обработка) и BPpost (постобработка) в байтах
  • Задержка хранения: Ts временные затраты
  • Коэффициент задержки хранения: LSR = (BPpre - BPpost)/Ts

Методы сравнения

  • PostgreSQL: Реляционная база данных
  • Neo4j: Графовая база данных
  • Leonard: Система хранения на основе DNN (Usenix Security'23)

Детали реализации

  • Окружение: Python 3.9, PyTorch 1.13.1, процессор AMD EPYC 7513, GPU RTX A6000
  • Гиперпараметры: Размер пакета 4096, оптимизатор Adam, скорость обучения 0,001, максимум 5 эпох обучения

Результаты экспериментов

Основные результаты

СистемаСреднее хранилище (МБ)Средняя задержка (с)Улучшение относительно DEHYDRATOR
PostgreSQL1 818457,36×
Neo4j1 770217,16×
Leonard3 99130 23316,17×
DEHYDRATOR2473 205-

Производительность запросов

При тестировании BFS запросов на разных глубинах:

  • Neo4j показывает лучший результат (~4,92 с)
  • DEHYDRATOR занимает второе место (~32,02 с)
  • PostgreSQL показывает худший результат (~32,08 с)

Абляционные эксперименты

Анализ вклада компонентов:

  • Исходный граф: 1598,69 МБ
  • После кодирования сопоставления полей: 405,2 МБ (25,3%)
  • После иерархического кодирования: 75,98 МБ (4,7%)
  • После обучения модели: 192,42 МБ (12%)

Влияние иерархического кодирования:

  • С иерархическим кодированием: EThi 20,19 М, время обучения 660,69 с, ECT 50,79 М
  • Без иерархического кодирования: EThi 268,31 М, время обучения 5814,42 с, ECT 1064,25 М
  • Иерархическое кодирование сокращает время обучения в 8,8 раза, размер ECT уменьшается в 20,95 раза

Анализ применимых сценариев

Теоретический анализ доказывает: когда среднее степень davg ≥ 3, иерархическое кодирование эффективно Экспериментальная проверка: Иерархическое кодирование эффективно на наборах данных со степенью 3, 4, 5

Связанные работы

Обнаружение вторжений

  • Эвристические методы: HOLMES, SLEUTH, Poirot и другие, основанные на построении правил сопоставления MITRE ATT&CK
  • Обнаружение аномалий: Streamspot, Unicorn, KAIROS и другие, определяющие вторжения путём выявления отклонений от нормального поведения

Расследование атак

  • Системы RapSheet, HERCULE, NODOZE проводят оценку угроз и причинно-следственный анализ
  • DEPIMPACT, ATLAS проводят анализ зависимостей и распознавание паттернов атак

Сжатие графов

  • Методы с потерями: Техники обрезки LogGC, CPR, NodeMerge, DPR
  • Методы без потерь: Методы кодирования SEAL, ELISE, Leonard

Заключение и обсуждение

Основные выводы

  1. DEHYDRATOR успешно решает три основные проблемы хранения графов происхождения: сохранение содержимого, эффективность хранения, поддержка запросов
  2. Иерархическое кодирование является ключевой инновацией, эффективно обрабатывающей избыточность на уровне структуры
  3. Однослойный Transformer более подходит для задач хранения, чем многослойный LSTM
  4. Значительное превосходство над существующими методами на крупномасштабных наборах данных

Ограничения

  1. Высокая задержка хранения: Средняя 3205 секунд, составляющая 13,29% временного периода набора данных
  2. Эффективность запросов: Авторегрессивная генерация приводит к высокой задержке запросов для длинных последовательностей
  3. Выбор ёмкости модели: Отсутствие теоретического руководства для определения оптимальной ёмкости модели η
  4. Область применения: Главным образом подходит для сценариев холодного хранилища, не поддерживает свойства ACID

Направления будущих исследований

  1. Использование технологий ускорения AI для повышения эффективности обучения и вывода
  2. Теоретический анализ выбора оптимальной ёмкости модели
  3. Расширение на универсальные приложения графовых баз данных
  4. Оптимизация алгоритмов запросов для снижения задержки

Глубокая оценка

Преимущества

  1. Значимость проблемы: Решение практических проблем в области кибербезопасности
  2. Инновационность метода: Иерархическое кодирование умело сочетает особенности предметной области и преимущества DNN
  3. Полнота экспериментов: Проверка на крупномасштабных наборах данных, комплексные абляционные эксперименты и сравнительный анализ
  4. Инженерная ценность: Значительное улучшение эффективности хранения, высокая практическая применимость

Недостатки

  1. Проблема задержки: Задержка хранения и запросов остаётся высокой, ограничивая приложения в реальном времени
  2. Теоретический анализ: Отсутствие теоретического руководства для выбора ёмкости модели
  3. Область применения: Главным образом ориентирована на специфический сценарий графов происхождения, ограниченная обобщаемость
  4. Сравнение базовых линий: Реализация Leonard может содержать несправедливые сравнения

Влияние

  1. Академический вклад: Предоставление нового технического пути для хранения графов происхождения
  2. Практическая ценность: Важное значение для инфраструктуры кибербезопасности
  3. Воспроизводимость: Обещание открытого исходного кода и данных
  4. Масштабируемость: Методология может быть расширена на другие сценарии хранения графов

Применимые сценарии

  1. Кибербезопасность: Системы EDR, охота на угрозы, расследование атак
  2. Холодное хранилище: Архивирование и анализ исторических данных
  3. Хранение крупномасштабных графовых данных: Хранение структур графов с высокой степенью и высокой избыточностью
  4. Пакетные запросы: Сценарии приложений, требующие большого количества параллельных запросов

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

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