ORTHRUS: Achieving High Quality of Attribution in Provenance-based Intrusion Detection Systems

ORTHRUS: Achieving High Quality of Attribution in Provenance-based Intrusion Detection Systems

Speakers: Baoxiang Jiang

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=_FpCefZeObw

Overview

In an era of escalating cyber threats, system provenance has emerged as a critical technique for advanced intrusion detection. This talk, presented by Baoxiang Jiang from Shan University, introduces ORTHRUS, a novel system designed to significantly enhance the attribution quality of provenance-based intrusion detection systems (PIDS). While PIDS are adept at recording intricate system interactions—representing them as dynamic provenance graphs to identify anomalous behaviors indicative of attacks—current anomaly-based PIDS often fall short in providing precise, actionable intelligence.

The core challenge addressed by ORTHRUS is the overwhelming volume of contextual information and high false positive rates that plague existing systems, leading to severe analyst fatigue and burnout. Jiang identifies two primary factors contributing to this limitation: data imbalance within provenance graphs, where malicious activities are statistically rare, and improper validation strategies that broadly label entire neighborhoods or batches of nodes as malicious. ORTHRUS directly tackles these issues, offering a robust solution that not only detects cyber attacks but also pinpoints the specific malicious entities and reconstructs the attack chain with unprecedented accuracy.

ORTHRUS is a groundbreaking contribution to the field, offering a practical and effective method for delivering high-quality attack signals. By open-sourcing its system and a meticulously curated ground truth dataset—devoid of the aforementioned improper evaluation biases—ORTHRUS sets a new standard for evaluating and deploying anomaly-based PIDS. Its ability to provide precise attribution, coupled with superior performance across key metrics, positions it as an invaluable tool for fortifying defenses against sophisticated cyber attacks.

Background

▶ Watch: Identifying the challenge of low attribution quality in PIS (1:00)

The foundation of ORTHRUS lies in system provenance, a powerful concept that meticulously records the interactions between system objects. These interactions, often termed system events, are then represented as a directed, attributed, and dynamic graph, known as a provenance graph. In this graph, nodes typically represent system objects (e.g., processes, files, network sockets), and edges denote events or interactions between them, with the edge direction following the flow of data or control. When a cyber attack unfolds, the malicious activities manifest as abnormal system behaviors, which, in turn, create distinct, anomalous structures within this provenance graph.

To leverage these graphs for security, provenance-based intrusion detection systems (PIDS) were developed. A significant category within PIDS is anomaly-based PIDS, which operate by learning patterns of normal system behaviors from benign provenance graphs. Once these normal patterns are established, the system can then identify deviations or "abnormal graph patterns" that are flagged as potentially malicious. This approach holds immense promise for detecting advanced, unknown cyber attacks that might bypass signature-based detection mechanisms. Consequently, numerous anomaly-based PIDS have been proposed and applied in real-world intrusion detection scenarios.

However, despite their potential, current anomaly-based PIDS suffer from a critical limitation: the low quality of attribution in their reported attack signals. This often translates into an "overwhelmingly large amount of contextual information," forcing security analysts to wade through vast quantities of data to pinpoint the actual malicious activity. This problem is primarily rooted in two fundamental issues:

1. Data Imbalance: Provenance graphs, by their nature, are heavily skewed towards benign activities. The prevalence of malicious nodes, representing actual attack components, is exceedingly small compared to the vast number of normal system operations. This severe class imbalance makes it inherently difficult for machine learning models to precisely identify these rare malicious nodes amidst the noise of legitimate system events. Models tend to be biased towards the majority class (benign), leading to poor detection of the minority class (malicious).

1. Improper Validation Strategies: Many existing works apply validation strategies that overestimate the scope of an attack. For instance, given an identified attack node, some systems consider all nodes in its immediate neighborhood, all nodes within the same processing batch, or all nodes sharing the same source node as equally malicious. This broad-brush approach, while simplifying evaluation, artificially inflates the number of "malicious" nodes, leading to a high false positive rate. Jiang highlights that ORTHRUS addresses this by utilizing a meticulously crafted ground truth where only truly attack-related nodes are considered malicious, providing a much more accurate basis for evaluation and attribution. By tackling these deeply ingrained issues, ORTHRUS aims to deliver PIDS that are not only effective at detection but also highly practical for security operations.

Key Findings

▶ Watch: Orthrus's attention-based GNN encoder for learning graph embeddings (3:50)

ORTHRUS demonstrates a significant leap forward in the field of provenance-based intrusion detection, delivering high-quality attack signals with superior performance across multiple critical metrics. The comprehensive evaluation, conducted against benchmark datasets from RTC programs and compared with five state-of-the-art anomaly-based PIDS, yielded several key findings:

1. Universal Attack Detection: ORTHRUS successfully detected all attacks present in the public benchmark datasets used for evaluation. This 100% attack-level detection rate underscores its robust capability to identify diverse forms of cyber threats.

1. Superior Attribution Quality and Precision: At the node level, ORTHRUS reported true positives with only a few false positives, achieving the best precision among all compared systems. In stark contrast, other systems either failed to report any true positives or generated a large number of false positives, rendering their outputs less actionable. This is a direct consequence of ORTHRUS's improved strategies for handling data imbalance and validation.

1. Enhanced Learning Capability: The anomaly scores calculated by ORTHRUS's graph learning models showed a larger margin differentiating malicious and benign anomalies compared to other systems. This indicates that ORTHRUS possesses a superior capability to learn and distinguish between normal and abnormal system behaviors, providing a clearer signal for malicious activity.

1. High Computational Efficiency: In most evaluation cases, ORTHRUS demonstrated the best computational efficiency among the compared systems. This is a crucial factor for real-time intrusion detection systems, as it allows for faster processing of provenance data without compromising detection quality.

1. Robustness to Hyperparameter Changes: The system exhibited remarkable robustness across variations in hyperparameters. Even when parameters were significantly altered, ORTHRUS consistently detected all attacks in most scenarios, indicating its stability and reliability in diverse operational environments.

1. Component Contribution: An ablation study confirmed that all individual components of ORTHRUS contribute positively to its overall performance, impacting both precision and computational efficiency. This validates the design choices and the synergistic effect of its architectural elements.

In summary, ORTHRUS not only effectively detects attacks but also provides attack signals with significantly higher attribution quality, making it a powerful and practical solution for modern cyber defense.

Technical Deep Dive

▶ Watch: Reconstructing attacks by identifying entry and exit nodes (5:00)

ORTHRUS is engineered with a sophisticated multi-stage workflow designed to overcome the limitations of existing provenance-based intrusion detection systems, particularly in achieving high attribution quality. The overall process unfolds as follows: first, it meticulously collects system provenance data and constructs a provenance graph. Next, the edges of this graph are transformed into feature vectors. These vectors are then processed by an encoder-decoder architecture to learn intricate temporal and spatial patterns. Anomalies are subsequently detected through an automatic thresholding mechanism. Finally, ORTHRUS reconstructs the full attack path, starting from the identified anomalous nodes.

Provenance Graph Construction and Edge Featurization

The foundation of ORTHRUS is the provenance graph. In this graph, nodes represent system objects such as processes, files, network sockets, or users, while edges signify system events or interactions between these objects. The direction of an edge meticulously follows the flow of data or control. For instance, a process writing to a file would be represented by an edge from the process node to the file node.

To make this graph amenable to machine learning, the edges are featurized into vectors. This involves a multi-step process:

1. Node Attribute Tokenization: Attributes associated with nodes (e.g., process names, file paths, user IDs) are first tokenized into sentences.
2. Word Embeddings: Each word within these tokenized sentences is then embedded using a Word2Vec model. This transforms words into dense numerical vectors that capture semantic relationships.
3. Node Embedding Averaging: The embedding for each node is derived by averaging the Word2Vec embeddings of all words in its attributes.
4. Feature Vector Composition: The final edge feature vector is composed of the embeddings of the connected nodes, concatenated with one-hot encoded node types. This comprehensive featurization allows the model to capture rich semantic and structural information about system events.

Encoder-Decoder Architecture for Temporal and Spatial Learning

At the heart of ORTHRUS's learning capability is an encoder-decoder architecture, specifically designed to extract both temporal and spatial information from the vector-represented provenance graph.

1. GEN-based Encoder: The encoder component is a Graph Event Network (GEN)-based model. Its primary role is to learn and generate robust edge embeddings. For each target edge, the encoder samples the N most recent events (edges) that are causally related or spatially proximate. This sampling ensures that temporal context is preserved.

1. Attention-based Graph Neural Network (GNN): Within the encoder, an attention-based GNN model is employed to aggregate information from these sampled neighbors to the target node. This is a critical mechanism for capturing spatial dependencies. Attention coefficients are calculated between the target node and each sampled neighbor. These coefficients act as weights, determining the importance of information aggregated from each neighbor. The attention mechanism allows the model to dynamically focus on the most relevant neighboring information, effectively filtering out noise and highlighting significant interactions. The aggregated, attention-weighted information is then used to generate an embedding for the target node.

1. Decoder: The decoder takes the learned embeddings from the encoder and predicts the edge types. For example, it might predict if an edge represents a "process creation," "file write," or "network connection."

1. Reconstruction Error and Loss: The model calculates a reconstruction error by comparing the predicted edge types with the actual edge types. This error is typically set as the cross-entropy loss across type predictions. By optimizing this loss through backpropagation, the model is forced to learn the normal temporal and spatial patterns of benign system behaviors. When an event deviates from these learned normal patterns, it results in a high reconstruction error, signaling a potential anomaly.

Anomaly Detection

During the detection phase, events that yield a high reconstruction error are assigned to their respective nodes, serving as their anomaly scores. The process for identifying true anomalies from these scores involves two steps:

1. Automatic Thresholding: Before the training phase, a batch of benign data is reserved specifically for validation. ORTHRUS calculates the highest loss observed within this validation set and designates it as the anomaly threshold. This threshold effectively represents the largest acceptable deviation in anomaly score for benign activities. Any node whose anomaly score exceeds this threshold is considered potentially anomalous.

1. C-means Clustering: To refine the anomaly detection and reduce false positives, ORTHRUS employs a C-means clustering model. All nodes with an anomaly score higher than the established threshold are fed into this clustering algorithm, which divides them into two distinct clusters. The cluster exhibiting a higher average anomaly score is then confidently reported as true malicious, while the other cluster, representing benign anomalies or noise, is filtered out. This intelligent clustering step significantly enhances attribution quality by distinguishing actual threats from benign but unusual system behaviors.

Attack Reconstruction

The final, crucial step in ORTHRUS's workflow is the reconstruction of the attack from the precisely detected anomalies. This process provides security analysts with a clear, actionable narrative of the attack:

1. Causality Analysis: ORTHRUS conducts a causality analysis starting from the detected anomalous nodes. This analysis traces back the causal chain of events to identify potential entry nodes (the initial root cause or point of compromise) and forward to identify exit nodes (the final impact or objective of the attack, e.g., data exfiltration, system compromise).

1. Dependency Graph Identification: A dependency graph is defined as the subgraph connecting an entry node to an exit node, passing through one or more anomaly nodes. There can be multiple such dependency graphs for a given set of anomalies.

1. Critical Score Calculation: ORTHRUS calculates critical scores for each identified dependency graph. This score likely quantifies the severity, impact, or certainty of the attack path. The dependency graph with the most critical score is then selected and presented as the reconstructed attack, offering a concise and highly relevant visualization of the entire attack chain.

This comprehensive technical architecture allows ORTHRUS to not only detect anomalies but also to precisely attribute them to specific malicious entities and reconstruct the full attack narrative, significantly improving the utility and actionability of provenance-based intrusion detection.

Demo / Proof of Concept

▶ Watch: Orthrus achieves best precision with few false positives (6:30)

While the talk did not feature a live demonstration of the ORTHRUS system in action, the speaker presented a comprehensive evaluation of its capabilities. The system's effectiveness was rigorously tested using benchmark datasets published by RTC programs. ORTHRUS was compared against five of the most recent anomaly-based PIDS, with results highlighting its superior performance in attack detection, precision, computational efficiency, and robustness, thereby serving as a strong empirical proof of concept.

Defensive Implications

▶ Watch: Summary of contributions and open-sourcing Orthrus with ground truth (8:00)

The advancements introduced by ORTHRUS have profound implications for defensive security operations, offering actionable improvements that address critical pain points in modern incident response and threat hunting:

1. Reduced Alert Fatigue: By significantly improving the attribution quality and drastically reducing false positives, ORTHRUS directly tackles the pervasive problem of alert fatigue among security analysts. Instead of sifting through overwhelming amounts of contextual information, defenders receive highly precise and relevant attack signals, allowing them to focus their efforts on genuine threats.

1. Precise Malicious Node Identification: ORTHRUS's ability to precisely differentiate malicious nodes from benign anomalies, even in the presence of data imbalance, means that security teams can identify the exact compromised processes, files, or network connections. This level of granularity is crucial for effective containment and eradication strategies.

1. Faster Incident Response and Root Cause Analysis: The attack reconstruction feature, which identifies entry nodes (root cause) and exit nodes (final impact) through causality analysis, provides an invaluable narrative for incident responders. This allows teams to quickly understand the initial compromise vector and the ultimate objective of the attack, accelerating the investigation and recovery process.

1. Optimized Resource Allocation: With more accurate and actionable intelligence, security teams can allocate their resources more efficiently. Instead of chasing numerous false positives, they can prioritize and respond to verified threats, leading to more effective use of personnel and tools.

1. Enhanced Threat Hunting: The detailed provenance graphs and the ability to highlight critical attack paths provide excellent material for proactive threat hunting. Analysts can leverage ORTHRUS's insights to explore subtle indicators of compromise that might otherwise be missed, strengthening an organization's overall security posture.

1. Integration Potential: The structured output of ORTHRUS, detailing specific anomalies and reconstructed attack graphs, makes it a strong candidate for integration into existing Security Information and Event Management (SIEM) or Security Orchestration, Automation, and Response (SOAR) platforms. This could enable automated triage, enrichment, and even initial response actions based on high-quality attack signals.

In essence, ORTHRUS transforms provenance-based intrusion detection from a promising but often noisy technique into a highly practical and indispensable tool for cybersecurity professionals, empowering them with clarity and precision in the face of complex attacks.

Key Takeaways

• Provenance-based intrusion detection systems (PIDS) are powerful for detecting cyber attacks by modeling system behaviors as graphs, but suffer from low attribution quality due to data imbalance and improper validation strategies.
• ORTHRUS introduces a novel approach that significantly improves the precision of attack attribution, reducing false positives and providing clearer attack signals.
• The system employs an advanced encoder-decoder architecture with an attention-based GNN to learn normal temporal and spatial system patterns from provenance graphs.
• ORTHRUS utilizes automatic thresholding based on benign validation data and C-means clustering to precisely distinguish true malicious anomalies from benign deviations.
• Its attack reconstruction capability leverages causality analysis to identify entry nodes (root cause) and exit nodes (final impact), providing a complete narrative of the attack path.
• Evaluations show ORTHRUS achieves 100% attack detection, superior precision with significantly fewer false positives, better learning capability, high computational efficiency, and robustness compared to state-of-the-art PIDS.

About the Speaker(s)

Baoxiang Jiang is a researcher from Shan University. In this talk, he presented ORTHRUS, his work on achieving high-quality attribution in provenance-based intrusion detection systems.