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はフィールドマッピングエンコーディングでフィールドレベルの冗長性を除去し、階層的エンコーディングで構造レベルの冗長性を除去し、最後に深層ニューラルネットワークを学習してバッチクエリをサポートします。10億件を超えるログエントリを含む7つのデータセットで評価した結果、DEHYDRATORはストレージスペースを84.55%削減し、PostgreSQLより7.36倍、Neo4jより7.16倍、Leonardより16.17倍効率的です。

研究背景と動機

問題背景

ネットワーク脅威の急増：2024年5月時点で9,478件のデータ漏洩事件が発生しており、2024年1月のMOAB事件では260億件のレコードが漏洩しました
溯源グラフの重要性：溯源グラフは有向グラフ構造として、ノードはシステムエンティティ（プロセス、ファイル、ソケット）を表し、エッジはシステムイベントを表し、強力なセマンティック表現と攻撃履歴の関連付け能力を持ちます
ストレージの課題：4つの現象がストレージの困難さをもたらします：
- 不可逆的成長：データ完全性を維持するため、追加のみで削除なし
- 急速な拡張：マシンあたり1日あたりGB級のログを生成
- 長期間の継続：侵入が発見されるまで平均188日間継続
- クエリ要件：脅威ハンティングと因果分析の大規模クエリをサポートする必要

既存方法の限界

既存の効率的な溯源グラフストレージシステム（ESSPGs）は2つのカテゴリに分類されます：

剪定ベースの方法（LogGC、CPR、NodeMerge、DPRなど）：ロスのある圧縮で、上位コンポーネントに偽陰性をもたらす可能性があります
エンコーディングベースの方法（SEAL、SLEUTH、ELISE、Leonardなど）：クエリをサポートできないか、補助コンポーネントが大量のストレージスペースを占有します

研究動機

既存の方法は3つの重要な要件を同時に満たすことができません：

コンテンツロスレス：偽陰性を避けるためすべてのデータを保持
ストレージ効率：ストレージオーバーヘッドを最小化
クエリサポート：大規模クエリ要件に対応

核心的貢献

DEHYDRATORシステムの提案：既存方法の限界を克服する効率的な溯源グラフストレージシステム。フィールドマッピングエンコーディングでフィールドレベルの冗長性を除去し、階層的エンコーディングで構造レベルの冗長性を除去し、深層ニューラルネットワークでバッチクエリをサポートします
プロトタイプシステムの構築と大規模評価：7つのデータセット（合計10億件を超えるログ）で評価。ストレージスペースを84.55%削減し、PostgreSQL、Neo4j、Leonardと比較してそれぞれ7.36倍、7.16倍、16.17倍効率的です
包括的な評価分析：コンポーネント影響、適用シナリオ、パフォーマンス下限を探索。ストレージオーバーヘッドと遅延のバランスを取る遅延ストレージ比（LSR）指標を定義します

ログ解析：正規表現を使用して生ログから重要フィールドを抽出
溯源グラフ構築：ノードテーブルNT（IdentiID、Name、Type）とエッジテーブルET（SrcID、DstID、TimeStamp、Operation）を構築
フィールドマッピングエンコーディング：3種類のフィールドレベルの冗長性を処理
- 一意の値：より短い数字文字で置換
- 繰り返し値：インデックスで置換
- 増分値：オフセットで置換

2. ストレージ段階（Storage）

階層的エンコーディング：

溯源グラフを階層的有向グラフとしてモデル化
各ノードvについて、すべてのソースノードと入辺情報を記録
マージマッピングテーブルMMTと階層的エッジテーブルEThiを構築
ネストされたリスト構造：Operation: timeOffset: nodeOffset

モデルトレーニング：

単層デコーダのみのTransformerを選択
ストレージタスクをシーケンス生成タスクとしてモデル化
char2vecエンコーディングを使用し、自動回帰生成
モデル予測エラーを処理するための誤り訂正テーブルECTを構築

3. クエリ段階（Query）

ノード情報：マッピングテーブルMTを通じてインデックスを取得し、ノード情報を検索
エッジ情報：インデックスをDNNモデルに入力し、シーケンスを生成。ECTで誤り訂正し、階層的デコーディングで読み取り可能な情報を取得

技術的革新点

階層的エンコーディング設計：
- 因果分析の逆方向クエリ特性に基づく
- 複数の並列エッジをコンパクトなエンコーディング形式に圧縮
- 情報密度を増加させ、モデルトレーニングを加速
DNNモデルの選択：
- 複数層LSTMの代わりに単層デコーダTransformerを使用
- より優れた並列化能力と特徴抽出能力
- ストレージタスクの低レベルの繰り返しパターン認識に適切
誤り訂正メカニズム：
- ECTテーブルは位置と正しい文字を記録
- DNNの圧縮をサポートしながらコンテンツロスレスを保証