An End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation

1. Problem Statement

Advanced Persistent Threats (APTs) are stealthy attacks that blend into normal system operations, making them difficult to detect using traditional signature-based methods. Provenance graphs, which model causal interactions between system entities (processes, files, network connections) derived from logs, are a powerful tool for anomaly detection. However, existing approaches face three critical challenges:

1. Brittle Construction: Current methods rely on manually engineered regular expression (regex) rules to parse logs. These rules do not scale across heterogeneous log formats (e.g., Windows Audit, Linux Theia, DNS) and break easily when log structures evolve or new software is introduced.
2. Lack of Functional Context: Existing anomaly detectors often represent nodes using coarse-grained types (e.g., "process") or generic embeddings. They fail to capture the functionality of an entity (e.g., distinguishing a "document editor" from a "system driver"). This leads to false positives/negatives because detectors cannot determine if an interaction is semantically appropriate for a specific entity type.
3. Poor Analyst Interpretability: Detected alerts are often presented as complex, low-level graphs that are overwhelming for human analysts. There is limited support for summarizing these attacks into natural language or mapping them to high-level threat tactics (e.g., MITRE ATT&CK).

2. Methodology: Auto-Prov Framework

The authors propose Auto-Prov, an adaptive, end-to-end framework that leverages Large Language Models (LLMs) to automate graph construction, enrich nodes with functional context, and summarize threats. The framework operates in five key stages:

A. Automatic Log Type Discovery (Clustering)

• Challenge: Logs are unstructured and evolve over time.
• Solution: Auto-Prov samples streaming logs and uses RoBERTa embeddings to encode them. It employs the DBStream density-based clustering algorithm to group logs with similar structural formats into distinct "log types." This allows the system to discover new log formats without prior knowledge.

B. Candidate Provenance Extractor (CPE)

• Role: Acts as a "teacher" to generate high-quality reference extractions.
• Mechanism: A powerful, proprietary LLM (e.g., GPT-4o) processes a small set of representative logs for each discovered type. It performs a multi-step decomposition:
  1. Summarization: Converts raw logs into natural language describing interactions.
  2. Entity Extraction: Identifies interacting entities and their coarse types.
  3. Edge Extraction: Infers interaction direction and type (read/write/execute).
• Output: A set of "candidate provenance records" serving as ground truth for rule generation.

C. Rule Generator (Scalability)

• Challenge: Running a large LLM on high-volume log streams is computationally infeasible.
• Solution: A smaller, open-source LLM (e.g., LLaMA-3) analyzes the candidate records and the raw logs to induce regular expression (regex) rules. These rules replicate the CPE's extraction logic.
• Result: The system can now process massive log streams efficiently using lightweight regex rules, while the rule database is incrementally updated as new log types are discovered.

D. Node Enricher (Functional Context)

• Goal: Embed functional attributes (e.g., "browser," "driver") into graph nodes to aid anomaly detection.
• Mechanism:
  1. LLM Inference: For known entities, an LLM infers functionality based on names, paths, and domains.
  2. Behavioral Classifier: For unknown or unseen entities, the system uses a behavior-based classifier. It compares the entity's one-hop interaction patterns (neighbors) against a database of known functional profiles using cosine similarity to assign a functional label.
• Integration: These functional labels are embedded as node features, allowing downstream anomaly detectors to learn "normal" behavior specific to an entity's function.

E. Graph Assistant (Threat Interpretation)

• Goal: Translate detected attack graphs into actionable intelligence.
• Mechanism: An LLM (LLaMA-3) takes the detected attack graph, linearizes the edges into a narrative, and generates a natural language summary.
• Tactic Mapping: The assistant maps the summarized behaviors to MITRE ATT&CK tactics (e.g., Initial Access, Privilege Escalation), providing reasoning for why specific interactions align with these tactics. It handles unknown entities by injecting the inferred functional labels from the Node Enricher.

3. Key Contributions

1. Adaptive Framework: Auto-Prov is the first framework to automatically construct provenance graphs from heterogeneous, evolving logs without manual rule engineering, using a zero-shot LLM approach.
2. Functional Context Representation: It introduces a novel method to embed system-level functionality into graph nodes, combining LLM inference for known entities with behavior-driven estimation for unseen ones.
3. Scalable Architecture: It successfully bridges the gap between the reasoning power of large LLMs and the efficiency requirements of streaming logs by distilling LLM outputs into reusable regex rules.
4. Interpretable Summarization: It provides a post-detection layer that converts complex attack graphs into concise natural language summaries mapped to APT tactics, directly supporting analyst investigation.

4. Experimental Results

The framework was evaluated on two diverse datasets (DARPA THEIA and ATLAS) covering Windows, Linux, DNS, and browser logs, against four state-of-the-art anomaly detectors (Flash, MAGIC, OCR-APT, Kairos).

• Detection Performance: Auto-Prov consistently improved detection metrics across all detectors.
  • AUC-ROC: Improved by an average of 0.23 on THEIA and 0.15 on ATLAS.
  • Attack Detection Precision (ADP): Achieved near-perfect scores (often 1.0), meaning the system successfully prioritized at least one malicious node for every attack, including stealthy ones that baseline methods missed.
• Ablation Studies:
  • Graph Quality: Auto-Prov's LLM-derived graphs outperformed manually engineered rule-based graphs, proving that LLM reasoning captures higher-fidelity causal relationships.
  • Functional Features: Adding functional context significantly boosted performance. However, adding functional features to poorly constructed baseline graphs yielded negative results, highlighting that both graph structure and functional context are essential.
  • LLM Selection: GPT-4o was superior for the Candidate Extractor (handling cross-log heterogeneity), while LLaMA-3 was sufficient and effective for Rule Generation and Node Enrichment.
• Robustness: The Graph Assistant remained robust even when entity names were "poisoned" (obfuscated), maintaining high tactic correctness and summary similarity by relying on the behavioral classifier's functional estimates.

5. Significance

Auto-Prov represents a significant shift in system security monitoring:

• From Static to Adaptive: It moves away from fragile, manual rule maintenance toward an adaptive system that evolves with the software environment.
• From Structure to Semantics: By embedding functional context, it enables detectors to understand why an entity behaves a certain way, not just that it behaved that way, reducing false positives caused by semantic mismatches.
• Bridging the Human Gap: By automating the translation of complex graph data into natural language and tactical mappings, it lowers the barrier for analysts to investigate APTs, making provenance-based detection more practical for real-world deployment.

The authors have released their code and artifacts to facilitate reproducibility and further research in automated threat detection.