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: Verbesserung der Speicherung von Herkunftsgraphen durch hierarchische Kodierung und Sequenzgenerierung

Grundinformationen

  • Paper-ID: 2501.00446
  • Titel: DEHYDRATOR: Enhancing Provenance Graph Storage via Hierarchical Encoding and Sequence Generation
  • Autoren: Jie Ying, Tiantian Zhu*, Mingqi Lv, Tieming Chen (Zhejiang University of Technology)
  • Klassifizierung: cs.CR (Kryptographie und Sicherheit)
  • Veröffentlichtes Journal: IEEE Transactions on Information Forensics and Security
  • Paper-Link: https://arxiv.org/abs/2501.00446

Zusammenfassung

Mit der Ausweitung des Umfangs und der Auswirkungen von Cyber-Bedrohungen nutzen Analysten Audit-Protokolle zur Verfolgung von Bedrohungen und Untersuchung von Angriffen. Herkunftsgraphen, die aus Kernel-Protokollen konstruiert werden, werden zunehmend als ideale Datenquelle angesehen, da sie starke semantische Ausdrucksfähigkeit und die Fähigkeit zur Verfolgung von Angriffshistorien bieten. Aufgrund der hohen Häufigkeit von Kernel-Ereignissen und der Persistenz von Angriffen stellt die Verwendung traditioneller Datenbanken zur Speicherung von Herkunftsgraphen jedoch eine Herausforderung mit hohem Speicheraufwand dar. Um dieses Problem zu lösen, wird DEHYDRATOR, ein effizientes Speichersystem für Herkunftsgraphen, vorgestellt. Für von Audit-Frameworks generierte Protokolle verwendet DEHYDRATOR Feldmappings-Kodierung zur Filterung von Feldebenen-Redundanz, hierarchische Kodierung zur Filterung von Strukturebenen-Redundanz und trainiert schließlich tiefe neuronale Netze zur Unterstützung von Batch-Abfragen. Die Evaluierung auf sieben Datensätzen mit insgesamt über einer Milliarde Protokolleinträge zeigt, dass DEHYDRATOR den Speicherplatz um 84,55% reduziert, 7,36-mal effizienter als PostgreSQL, 7,16-mal effizienter als Neo4j und 16,17-mal effizienter als Leonard ist.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Zunahme von Cyber-Bedrohungen: Bis Mai 2024 gab es 9.478 Datenschutzverletzungen, wobei das MOAB-Ereignis im Januar 2024 26 Milliarden Datensätze offenlegte
  2. Bedeutung von Herkunftsgraphen: Herkunftsgraphen als gerichtete Graphstrukturen, bei denen Knoten Systementitäten (Prozesse, Dateien, Sockets) darstellen und Kanten Systemereignisse darstellen, bieten starke semantische Ausdrucksfähigkeit und Verfolgung von Angriffshistorien
  3. Speicherherausforderungen: Vier Phänomene führen zu Speicherschwierigkeiten:
    • Irreversibler Wachstum: Zur Wahrung der Datenvollständigkeit werden Daten nur hinzugefügt, nicht gelöscht
    • Schnelle Expansion: Jede Maschine generiert täglich GB-Protokolle
    • Lange Dauer: Eindringungen werden durchschnittlich nach 188 Tagen entdeckt
    • Abfrageanforderungen: Unterstützung großflächiger Abfragen für Threat Hunting und Kausalanalyse erforderlich

Einschränkungen bestehender Methoden

Bestehende effiziente Speichersysteme für Herkunftsgraphen (ESSPGs) fallen in zwei Kategorien:

  1. Pruning-basierte Methoden (z.B. LogGC, CPR, NodeMerge, DPR): Verlustbehaftete Kompression, kann zu falschen Negativen in übergeordneten Komponenten führen
  2. Kodierungsbasierte Methoden (z.B. SEAL, SLEUTH, ELISE, Leonard): Unterstützen entweder keine Abfragen oder Hilfskomponenten benötigen großen Speicherplatz

Forschungsmotivation

Bestehende Methoden können nicht gleichzeitig drei kritische Anforderungen erfüllen:

  • Inhaltsverlustfrei: Beibehaltung aller Daten zur Vermeidung falscher Negative
  • Speichereffizienz: Minimierung des Speicheraufwands
  • Abfrageunterstützung: Verarbeitung großflächiger Abfrageanforderungen

Kernbeiträge

  1. Vorstellung des DEHYDRATOR-Systems: Ein effizientes Speichersystem für Herkunftsgraphen, das Einschränkungen bestehender Methoden überwindet, indem es Feldmappings-Kodierung zur Filterung von Feldebenen-Redundanz, hierarchische Kodierung zur Filterung von Strukturebenen-Redundanz und tiefe neuronale Netze zur Unterstützung von Batch-Abfragen verwendet
  2. Konstruktion eines Prototypsystems und großflächige Evaluierung: Evaluierung auf sieben Datensätzen (insgesamt über eine Milliarde Protokolle), Speicherplatzreduktion um 84,55%, 7,36-mal, 7,16-mal bzw. 16,17-mal effizienter als PostgreSQL, Neo4j und Leonard
  3. Umfassende Evaluierungs- und Analysen: Erforschung von Komponentenauswirkungen, anwendbaren Szenarien und Leistungsgrenzen, Definition der Latenz-Speicher-Verhältnis (LSR)-Metrik zum Ausgleich von Speicheraufwand und Latenz

Methodische Details

Aufgabendefinition

Eingabe: Von Audit-Frameworks erfasste rohe Kernel-Protokolle Ausgabe: Effizient gespeicherte Herkunftsgraphen, die Abfrageanforderungen übergeordneter Komponenten unterstützen Einschränkungen: Inhaltsverlustfrei, Speichereffizienz, Abfrageunterstützung

Systemarchitektur

DEHYDRATOR verwendet ein dreistufiges Framework:

1. Vorverarbeitungsphase (Pretreatment)

  • Protokollanalyse: Verwendung regulärer Ausdrücke zur Extraktion von Schlüsselfeldern aus rohen Protokollen
  • Herkunftsgraph-Konstruktion: Konstruktion von Knotentabelle NT (IdentiID, Name, Type) und Kantentabelle ET (SrcID, DstID, TimeStamp, Operation)
  • Feldmappings-Kodierung: Behandlung von drei Arten von Feldebenen-Redundanz
    • Eindeutige Werte: Ersetzung durch kürzere numerische Zeichen
    • Wiederholte Werte: Ersetzung durch Indizes
    • Inkrementelle Werte: Ersetzung durch Offsets

2. Speicherphase (Storage)

Hierarchische Kodierung:

  • Modellierung des Herkunftsgraphen als hierarchischer gerichteter Graph
  • Für jeden Knoten v werden alle Quellknoten und eingehende Kanteninformationen aufgezeichnet
  • Konstruktion von Merge-Mapping-Tabelle MMT und hierarchischer Kantentabelle EThi
  • Verschachtelte Listenstruktur: Operation: timeOffset: nodeOffset

Modelltraining:

  • Auswahl eines einschichtigen Nur-Decoder-Transformers
  • Modellierung der Speicheraufgabe als Sequenzgenerierungsaufgabe
  • Verwendung von char2vec-Kodierung, autoregressive Generierung
  • Konstruktion einer Fehlerkorrektur-Tabelle ECT zur Behandlung von Modellvorhersagefehlern

3. Abfragephase (Query)

  • Knoteninformationen: Abruf des Index durch Mapping-Tabelle MT, Abruf von Knoteninformationen
  • Kanteninformationen: Eingabe des Index in das DNN-Modell, Sequenzgenerierung, ECT-Fehlerkorrektur, hierarchische Dekodierung zur Abruf lesbarer Informationen

Technische Innovationspunkte

  1. Hierarchische Kodierungsdesign:
    • Basierend auf Rückwärts-Abfrageeigenschaften der Kausalanalyse
    • Kompression mehrerer paralleler Kanten in kompakte Kodierungsform
    • Erhöhung der Informationsdichte, Beschleunigung des Modelltrainings
  2. DNN-Modellauswahl:
    • Einschichtiger Decoder-Transformer ersetzt mehrschichtige LSTM
    • Bessere Parallelisierungsfähigkeit und Merkmalsextraktionsfähigkeit
    • Geeignet für Erkennung von Wiederholungsmustern auf niedriger Ebene in Speicheraufgaben
  3. Fehlerkorrekturmechanismus:
    • ECT-Tabelle zeichnet Position und korrektes Zeichen auf
    • Gewährleistung von Inhaltsverlustfreiheit bei gleichzeitiger Unterstützung von DNN-Kompression

Experimentelle Einrichtung

Datensätze

Sieben Datensätze mit insgesamt über einer Milliarde Protokollen:

  • G1-G4: DARPA TC E3 CADETS, THEIA, TRACE-Gruppen
  • G5-G6: DARPA TC E4 TRACE-Gruppen
  • G7: Teilmenge des DEPIMACT-Datensatzes
  • Durchschnittliche Kantenzahl: 17.754.566 (9,6-mal größer als Leonard)

Bewertungsmetriken

  • Speicheraufwand: BPpre (Vorverarbeitung) und BPpost (Nachverarbeitung) Bytes
  • Speicherlatenz: Ts Zeitkosten
  • Latenz-Speicher-Verhältnis: LSR = (BPpre - BPpost)/Ts

Vergleichsmethoden

  • PostgreSQL: Relationale Datenbank
  • Neo4j: Graphdatenbank
  • Leonard: DNN-basiertes Speichersystem (Usenix Security'23)

Implementierungsdetails

  • Umgebung: Python 3.9, PyTorch 1.13.1, AMD EPYC 7513-Prozessor, RTX A6000 GPU
  • Hyperparameter: Batch-Größe 4096, Adam-Optimierer, Lernrate 0,001, maximale Trainingsrunden 5

Experimentelle Ergebnisse

Hauptergebnisse

SystemDurchschnittlicher Speicheraufwand (MB)Durchschnittliche Latenz (s)Verbesserung gegenüber DEHYDRATOR
PostgreSQL1.818457,36×
Neo4j1.770217,16×
Leonard3.99130.23316,17×
DEHYDRATOR2473.205-

Abfrageleistung

In BFS-Abfragetests unterschiedlicher Tiefe:

  • Neo4j zeigt beste Leistung (~4,92s)
  • DEHYDRATOR an zweiter Stelle (~32,02s)
  • PostgreSQL am schlechtesten (~32,08s)

Ablationsexperimente

Komponentenbeitragsanalyse:

  • Ursprünglicher Graph: 1.598,69 MB
  • Nach Feldmappings-Kodierung: 405,2 MB (25,3%)
  • Nach hierarchischer Kodierung: 75,98 MB (4,7%)
  • Nach Modelltraining: 192,42 MB (12%)

Auswirkung hierarchischer Kodierung:

  • Mit hierarchischer Kodierung: EThi 20,19M, Trainingszeit 660,69s, ECT 50,79M
  • Ohne hierarchische Kodierung: EThi 268,31M, Trainingszeit 5.814,42s, ECT 1.064,25M
  • Hierarchische Kodierung reduziert Trainingszeit um 8,8-fach, ECT-Größe um 20,95-fach

Analyse anwendbarer Szenarien

Theoretische Herleitung zeigt: Wenn durchschnittlicher Grad davg ≥ 3, ist hierarchische Kodierung wirksam Experimentelle Validierung: Hierarchische Kodierung ist auf Datensätzen mit Grad 3, 4, 5 wirksam

Verwandte Arbeiten

Eindringlingserkennung

  • Heuristische Methoden: HOLMES, SLEUTH, Poirot und andere basieren auf MITRE ATT&CK-Matching-Regeln
  • Anomalieerkennung: Streamspot, Unicorn, KAIROS und andere erkennen Eindringlinge durch Identifikation von Abweichungen vom normalen Verhalten

Angriffsuntersuchung

  • RapSheet, HERCULE, NODOZE und andere Systeme führen Bedrohungsbewertung und Kausalanalyse durch
  • DEPIMPACT, ATLAS und andere führen Abhängigkeitsanalyse und Angriffsmustererkennung durch

Graphkompression

  • Verlustbehaftete Methoden: LogGC, CPR, NodeMerge, DPR und andere Pruning-Techniken
  • Verlustfreie Methoden: SEAL, ELISE, Leonard und andere Kodierungstechniken

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

  1. DEHYDRATOR löst erfolgreich die drei großen Herausforderungen der Herkunftsgraph-Speicherung: Inhaltsverlustfreiheit, Speichereffizienz, Abfrageunterstützung
  2. Hierarchische Kodierung ist die Schlüsselinnovation zur effektiven Behandlung von Strukturebenen-Redundanz
  3. Einschichtiger Transformer ist besser geeignet als mehrschichtiges LSTM für Speicheraufgaben
  4. Signifikante Überlegenheit gegenüber bestehenden Methoden bei großflächigen Datensätzen

Einschränkungen

  1. Hohe Speicherlatenz: Durchschnittlich 3.205 Sekunden, entspricht 13,29% des Datensatz-Zeitraums
  2. Abfrageeffizienz: Autoregressive Generierung führt zu hoher Latenz bei langen Sequenzabfragen
  3. Modellkapazitätsauswahl: Mangel an theoretischer Anleitung zur Bestimmung optimaler Modellkapazität η
  4. Anwendungsbereich: Hauptsächlich für Cold-Storage-Szenarien geeignet, unterstützt keine ACID-Eigenschaften

Zukünftige Richtungen

  1. Nutzung von KI-Beschleunigungstechniken zur Verbesserung von Trainings- und Inferenzeffizienz
  2. Theoretische Analyse zur Auswahl optimaler Modellkapazität
  3. Erweiterung auf universelle Graphdatenbank-Anwendungen
  4. Optimierung von Abfragealgorithmen zur Latenzreduktion

Tiefgreifende Bewertung

Stärken

  1. Problemwichtigkeit: Löst praktische Schmerzpunkte im Bereich Cybersicherheit
  2. Methodische Innovativität: Hierarchische Kodierung kombiniert geschickt Domäneneigenschaften und DNN-Vorteile
  3. Experimentelle Vollständigkeit: Großflächige Datensatzvalidierung, umfassende Ablations- und Vergleichsanalysen
  4. Ingenieurwert: Signifikante Speichereffizienzbverbesserung, starke Praktikabilität

Mängel

  1. Latenzbroblem: Speicher- und Abfragelatenz bleiben hoch, begrenzt Echtzeitanwendungen
  2. Theoretische Analyse: Mangel an theoretischer Anleitung zur Modellkapazitätsauswahl
  3. Anwendungsbereich: Hauptsächlich auf spezifische Herkunftsgraph-Szenarien ausgerichtet, begrenzte Verallgemeinerbarkeit
  4. Baseline-Vergleich: Leonard-Implementierung könnte unfaire Vergleiche aufweisen

Einflussfähigkeit

  1. Akademischer Beitrag: Bietet neuen technischen Weg für Herkunftsgraph-Speicherung
  2. Praktischer Wert: Bedeutsam für Cybersicherheits-Infrastruktur
  3. Reproduzierbarkeit: Zusage zur Veröffentlichung von Code und Daten
  4. Förderungspotenzial: Methoden erweiterbar auf andere Graphspeicher-Szenarien

Anwendbare Szenarien

  1. Cybersicherheit: EDR-Systeme, Threat Hunting, Angriffsuntersuchung
  2. Cold Storage: Archivierung und Analyse historischer Daten
  3. Großflächige Graphdaten: Speicherung hochgradiger, hochredundanter Graphstrukturen
  4. Batch-Abfragen: Anwendungsszenarien mit großflächigen parallelen Abfrageanforderungen

Literaturverzeichnis

Das Paper zitiert 93 relevante Literaturquellen, die wichtige Arbeiten in den Bereichen Cybersicherheit, Graphkompression und Deep Learning abdecken und eine solide theoretische Grundlage für die Forschung bieten.