ProHunter: A Comprehensive APT Hunting System Based on Whole-System Provenance

1. Problem Statement

Advanced Persistent Threats (APTs) are difficult to detect due to their stealthy, long-term nature and ability to blend into normal system activities. While provenance-based threat hunting (using whole-system audit logs to reconstruct attack paths) combined with Cyber Threat Intelligence (CTI) is a promising defense, existing systems face three critical limitations:

• C1: Efficiency & Scalability: Real-world systems generate massive provenance graphs (millions of nodes/edges). Existing solutions often require gigabytes of memory to store these graphs or rely on heavy frameworks (e.g., NetworkX), making long-term analysis (e.g., 90-day campaigns) infeasible under tight resource budgets (<100 MB/host).
• C2: Attack Activity Sampling: Malicious events are rare and entangled with benign operations. Current methods rely on explicit Indicators of Compromise (IoCs) as "Points of Interest" (POIs) to sample threat graphs. This fails when attackers hide IoCs or when "dependency explosion" (e.g., common processes like explorer.exe accumulating massive dependencies) obscures malicious interactions.
• C3: Semantic Gaps: CTI reports describe attacks in high-level domain terms (e.g., "ARP scan"), while audit logs capture low-level events (e.g., cmd.exe execution). This mismatch leads to poor alignment between CTI-derived Query Graphs and system Provenance Graphs, resulting in high false positives or missed detections when using coarse-grained matching.

2. Methodology: ProHunter Architecture

ProHunter is a platform-independent system designed to address these challenges through three core components:

A. Memory-Efficient Provenance Graph (PPG) Construction

To solve C1, ProHunter introduces a compact, bit-level data structure for storing provenance graphs:

• Semantic Abstraction: Instead of storing full node names and types (which consume significant memory), nodes are mapped to intermediate-level abstract types (e.g., sys_process, util_process, public_netflow). Node identifiers are replaced with 32-bit integer indices.
• Hierarchical Encoding: The system observes that most nodes have sparse dependencies. It uses a hierarchical encoding strategy:
  • Sparse Nodes: Store relative indices of connected nodes using minimal bits (e.g., 11-bit offsets).
  • Dependency Explosion Nodes: A small subset of nodes with dense connections are promoted to an "extended structure" with larger bit allocations (e.g., 27-bit/32-bit indices) to handle large dependency distances.
• Result: This allows storing daily provenance graphs in 3–25 MB, enabling long-term retention.

B. Heuristic-Driven Threat Graph Sampling

To solve C2, ProHunter moves away from strict IoC reliance:

• Propagation-Aware Sampling: Instead of starting only from known IOCs, the system uses a heuristic Breadth-First Search (BFS) algorithm that traces suspicious information flows based on abstracted node semantics.
• Sampling Rules: The algorithm applies specific rules based on node types (e.g., web_process, sys_file) and dependency flags. For instance, it prioritizes network flows from system files to public addresses or modifications to configuration files, while filtering out benign noise from dependency-explosion nodes.
• Flexibility: It can accept arbitrary system nodes as POIs, not just known IOCs, making it robust against evasion techniques.

C. Adaptive Graph Representation & Matching

To solve C3, ProHunter bridges the semantic gap between CTI Query Graphs and Threat Graphs:

• Feature Initialization: Uses the intermediate-level abstract types (from PPG) as node features to balance specificity and generalization.
• Adaptive Graph Isomorphism Network (GIN):
  • Intra-Graph Message Passing: Aggregates local neighborhood features to capture localized behavior.
  • Inter-Graph Message Passing: Uses an attention mechanism to exchange features between the Query Graph and the Threat Graph. This allows the model to identify functionally equivalent patterns (e.g., matching a specific cmd.exe sequence in the log to a generic "command execution" pattern in the CTI) despite structural differences.
• Contrastive Learning: The model is trained using contrastive loss to maximize similarity between behaviorally analogous graphs and minimize it for dissimilar ones, using augmented benign data to prevent overfitting.

3. Key Contributions

1. ProHunter System: A comprehensive APT hunting system integrating graph compaction, heuristic sampling, and adaptive matching.
2. Compact PPG Structure: A novel storage architecture using semantic abstraction and hierarchical encoding that reduces memory usage by 47%–75% compared to state-of-the-art baselines (e.g., Sleuth), enabling 90-day analysis within tight memory budgets.
3. Heuristic Sampling Algorithm: A dependency-aware sampling method that extracts precise attack patterns without relying on explicit IOCs, effectively handling dependency explosion and reducing noise.
4. Adaptive Representation Model: A GIN-based approach with inter-graph message passing that successfully bridges the semantic gap between high-level CTI and low-level audit logs, capturing both localized and globalized attack semantics.
5. Extensive Evaluation: Validated on the DARPA TC E3, E5, and OpTC datasets (covering 28 attack scenarios across Windows, Linux, FreeBSD, and Android).

4. Experimental Results

ProHunter was evaluated against state-of-the-art systems (MEGR-APT, DeepHunter, ProvG-Searcher, Sleuth) and standard GNNs (GCN, GraphSAGE, GAT).

• Efficiency:
  • Memory: Stores daily provenance graphs in 3–25 MB (vs. GBs for others).
  • Speed: Processes 5-minute event windows in 0.67 seconds; threat hunting completes in 0.18 seconds per graph.
• Sampling Quality:
  • Achieves >70% attack semantic coverage (Recall) while introducing only 2–3 irrelevant nodes on average (Noise Rate < 20%).
• Hunting Performance:
  • Recall: 100% across all datasets (detects all APT campaigns).
  • False Positive Rate (FPR): <1% on average (significantly lower than baselines which often exceed 10-15%).
  • Robustness: Maintains high accuracy even when no explicit IOCs are provided (using arbitrary system nodes as POIs).
• Comparison: Outperforms all baselines in Accuracy, AUC, and FPR, particularly in large-scale datasets like OpTC where other systems suffer from high false positives due to semantic mismatches.

5. Significance

ProHunter represents a significant advancement in proactive cybersecurity defense:

• Operational Feasibility: By drastically reducing memory overhead, it makes continuous, long-term APT hunting viable in production environments where resources are constrained.
• Resilience to Evasion: By decoupling from explicit IOCs and focusing on semantic information flows, it remains effective against attackers who mutate file names or use fileless techniques.
• Semantic Alignment: It solves the critical "translation" problem between human-readable threat intelligence and machine-generated logs, reducing the manual effort required for analysts to interpret alerts.
• Scalability: The system is designed to handle the massive scale of modern enterprise networks (e.g., 1,000+ hosts generating billions of events), providing a blueprint for next-generation threat hunting platforms.

The code for ProHunter is publicly available, facilitating further research and adoption in the cybersecurity community.