TL;DR
This paper introduces Prov2vec, a novel system for unsupervised detection of Advanced Persistent Threats (APTs) by learning compact, canonical representations of host behavior from system event logs. Prov2vec utilizes a unique provenance graph kernel that generates significantly smaller representations than existing methods, leading to improved prediction accuracy and efficiency in detecting sophisticated, low-and-slow attacks.
What Problem Does This Paper Address?
Modern cyberattacks, particularly APTs, are increasingly sophisticated, employing zero-day exploits and evasion techniques to remain undetected for extended periods. Traditional signature-based defenses are often bypassed, and while anomaly detection systems can flag deviations, they struggle with the temporal and causal relationships in "low and slow" attacks. Existing endpoint detection and response (EDR) systems can generate a high volume of alerts, leading to alert fatigue and the risk of critical threats being missed. Furthermore, analyzing the vast amount of data generated by these systems for APT detection is computationally challenging, especially for real-time detection. The paper aims to address these challenges by providing an efficient and effective unsupervised method for detecting APTs by learning robust representations of normal host behavior.
Methods
Prov2vec's core innovation lies in its novel provenance graph kernel. This kernel works by:
- Provenance Graph Creation: System event logs are parsed into (subject, action, object) triplets to build a directed provenance graph, capturing the flow of information. Node versioning and redundant edge elimination are used to manage graph size.
- Label-Aware Backward Walks: For each node in the graph, the system performs label-aware backward walks up to a user-defined length
h. These walks capture the causal history of a node. - Node Label Histograms: The labels from these walks are aggregated into node label histograms. This process creates a compact representation of a node's historical context.
- Histosketching: To handle variable-sized histograms and enable efficient comparison, a probabilistic data structure called
histosketchis used to convert histograms into fixed-size vectors. This is crucial for downstream machine learning tasks. - Downstream Prediction Tasks: The fixed-size feature vectors are then fed into machine learning models for tasks like graph classification, graph clustering, and anomaly detection to identify deviations from normal behavior.
The key novelty is the provenance graph kernel's ability to generate a canonical representation that is significantly more compact than existing graph kernels (like Weisfeiler-Lehman subtree kernels) while maintaining or improving prediction accuracy.
Datasets
The paper evaluates Prov2vec on three datasets:
- StreamSpot Dataset: This dataset contains information flow graphs from one attack scenario and five benign scenarios (YouTube, downloads, browsing, Gmail, video games). It was generated on a Linux machine and includes system calls from boot to shutdown.
- SupplyChain Attack Scenarios Dataset: This dataset simulates two APT supply chain attacks (SC-1 and SC-2) on a Continuous Integration (CI) platform. It includes background activity captured by CamFlow and exploits vulnerabilities in GNU wget and GNU Bash.
- Operational Transparent Cyber (OpTC) Data: This dataset, collected from a simulated network of 1000 Windows 10 hosts over nine days, mimics daily user activities. It includes three red-team APT exercises, making it a more realistic representation of enterprise network behavior.
Key Insights and Ideas
- Compactness is Key for Generalization: The paper demonstrates that a more compact representation of host behavior (via smaller histograms) leads to better generalization and improved anomaly detection, reducing false positives.
- Causality Over Temporal Order for APTs: For detecting sophisticated APTs, understanding the causal relationships between system entities (captured by backward walks) is more critical than strict temporal ordering of events, especially for "low and slow" attacks.
- Unsupervised Learning for APTs is Feasible: Prov2vec shows that unsupervised learning on provenance graphs can effectively identify anomalous behaviors without prior knowledge of specific attack signatures.
- Histosketching for Scalability: The use of
histosketchis a crucial enabler for scaling Prov2vec to large, streaming datasets by providing fixed-size representations for variable-sized histograms.
Key Results
- Improved Prediction Ability: Prov2vec consistently outperformed or matched existing graph kernels (WLSubtree and Unicorn) in graph classification, novelty detection, and anomaly detection tasks across the evaluated datasets.
- Significantly Smaller Representations: The provenance graph kernel produced histograms that were an order of magnitude smaller than those generated by existing methods, while still achieving comparable or better performance.
- Efficient Anomaly Detection: In real-time anomaly detection on the OpTC dataset, Prov2vec achieved high precision (1.0000) and accuracy across multiple attack campaigns, often outperforming other kernels. For instance, on Day 3 of the OpTC attack, Prov2vec achieved perfect precision, recall, accuracy, and F1-score (1.0000).
- Robustness to Sketch Size: The performance of Prov2vec with
histosketchsaturated at a relatively small sketch size (128), indicating its efficiency and ability to capture essential information.
Limitations and Future Work
- Closed-World Assumption: Prov2vec assumes that all benign behaviors have been observed during training. Unseen normal behaviors could lead to false alarms. The authors suggest periodic model updates with new benign data.
- Training Data Integrity: The system assumes the integrity of training data and is vulnerable to poisoning attacks or graph backdoors.
- Dataset Realism: The datasets used, while realistic, are still synthetic. Testing on actual enterprise systems and more realistic APT scenarios is a priority.
- Granularity of Data Provenance: Some attacks might not leave sufficient traces in the provenance graph (e.g., file/thread-based attacks with text information). Future work could involve incorporating more host-based data or improving information capture for finer-grained provenance.
- Explainability: The black-box nature of machine learning models can make anomaly explanations challenging. Future work could explore methods like LIME or EDR systems for better explainability.
- Continuous Attributes: The current kernel supports discrete labels, limiting its ability to capture continuous attributes. Future work might explore deep learning or graph kernels that handle continuous data.
Summary updated