NODLINK: An Online System for Fine-Grained APT Attack Detection and Investigation

NODLINK: An Online System for Fine-Grained APT Attack Detection and Investigation

Speakers: Shaofei Li

Conference: NDSS Symposium

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

Overview

Advanced Persistent Threats (APT attacks) pose a significant and costly challenge to modern enterprises, often characterized by their multi-stage, stealthy, and complex nature. Traditional Endpoint Detection and Response (EDR) systems frequently fall short in detecting these sophisticated threats because they struggle to reconstruct the intricate causal relationships between disparate attack steps. While provenance graphs, which model system entities and their dependencies, have emerged as a powerful tool to bridge this gap, most existing provenance analysis systems are designed for post-mortem analysis, leading to detection delays that can extend up to a week. Such delays are financially crippling, with studies indicating potential losses of approximately $32,000 per day an attacker remains undetected within a network.

The need for near real-time detection has spurred the development of online provenance-based systems. However, these systems face a fundamental trade-off: they often sacrifice detection granularity to reduce computational complexity. This results in the generation of massive provenance graphs, sometimes exceeding 100,000 nodes, which are incredibly difficult for security administrators to interpret. Pinpointing the actual attack steps within a sea of benign activities becomes akin to "finding a needle in a haystack," rendering the detection less actionable.

NODLINK, presented by Shaofei Li, is engineered to overcome this critical challenge. It represents the first online detection system capable of maintaining high detection accuracy without compromising detection granularity. The core innovation lies in formally modeling the APT attack detection process as an Online Steiner Tree Problem (STP). This allows NODLINK to leverage efficient online approximation algorithms to recover concise, attack-related provenance graphs with theoretically bounded errors. The system incorporates a novel in-memory cache design, an efficient attack screening method, and a new, optimized STP approximation algorithm. Evaluated in a production environment through an open-world experiment, NODLINK significantly outperforms state-of-the-art online provenance analysis systems like HOLMES and UNICORN, achieving magnitudes higher detection and investigation accuracy while maintaining comparable or superior throughput.

Background

▶ Watch: Introduction to APTs, challenges, and NODLINK's overview (0:00)

Provenance analysis systems are built upon the collection of system auditing events, such as kernel-level system calls, using tools like Sysdig and Linux Audit. These events are then used to construct a provenance graph, a directed graph where nodes represent system entities (processes, files, IP addresses) and edges depict control and data flows. For instance, an edge from process P1 to P2 signifies P1 forked P2, or an edge from P1 to file F1 indicates P1 wrote data to F1. Despite their analytical power, provenance analysis systems generate colossal volumes of data, placing immense pressure on log processing infrastructure. This inherent data volume is the primary reason why most existing systems are limited to post-mortem analysis.

Recent research has focused on enabling online, near real-time provenance-based detection. However, these systems still grapple with significant challenges. A real-world APT29 attack, for example, might generate a provenance graph with over 20,000 events, yet only approximately 200 of these are truly attack-relevant. This implies that over 99% of the recorded activities are benign, creating an imbalanced ratio that severely hampers precise detection. Furthermore, benign activities can often mimic malicious ones; a common example is PowerShell, used legitimately by system administrators but also frequently leveraged by attackers, making simple blacklisting ineffective.

Existing online provenance detection techniques broadly fall into two categories:

• Rule-based systems (e.g., HOLMES): These systems rely on predefined rules to identify malicious patterns. Their primary drawback is low node-level accuracy due to incomplete rule sets. As observed in the APT29 example, HOLMES failed to detect several attack steps because its rules, often initiated from external untrusted IPs, couldn't capture internal attack stages lacking direct connections to these initial points. This results in fragmented output graphs, impeding root cause analysis, and generates numerous false positives because static rules struggle to model dynamic system features.
• Learning-based systems (e.g., UNICORN): These systems employ machine learning to identify anomalies. While designed for online detection, UNICORN projects the provenance graph into low-dimensional hashing vectors to reduce computational complexity. This over-approximation, however, leads to low node-level precision, as it prevents the system from pinpointing specific attack-relevant nodes. In the APT29 scenario, UNICORN struggled to distinguish attack-relevant nodes from benign data, achieving a node-level precision of less than 1%.

NODLINK addresses these limitations by modeling APT detection as an Online Steiner Tree Problem (STP). STP is a combinatorial optimization problem known to be NP-Complete, but efficient online approximation solutions exist. Given an undirected graph G with non-negative edge weights and a sequence of online-revealed vertices (termed "terminals"), the objective is to find a subgraph that spans these terminals with minimal total cost. Greedy approaches for online STP typically achieve a competitive ratio of O(log(k)), where k is the number of terminals.

NODLINK operates under a specific threat model aligned with prior work on learning-based provenance detection:

1. Attacks possess distinct, identifiable features (statistical patterns or rules).
2. System-level auditing frameworks are secure and reliable, providing accurate and detailed provenance data. Issues related to log integrity and security are outside the scope of this work.
3. Attacks performed using implicit flows, such as side channels, are not considered, as they typically bypass kernel-layer auditing.
4. While training data may contain minor attacks, the majority is assumed to be benign, enabling effective model learning.

Key Findings

▶ Watch: Provenance analysis background and limitations of existing systems (2:00)

NODLINK introduces several significant contributions and key findings to the field of online APT attack detection:

• Novel Formal Model: NODLINK is the first system to formally model APT attack detection as an Online Steiner Tree Problem (STP). This provides a rigorous mathematical framework for efficient and accurate detection of APT attacks with theoretically bounded approximation errors, a first in this domain.
• Efficient STP Framework: Beyond merely applying the standard STP model, NODLINK proposes a novel, more efficient STP framework specifically tailored for online APT detection. This includes the development of an Importance-Score-Guided Search (ISG) algorithm, which significantly reduces computational complexity while maintaining theoretical approximation guarantees.
• Online System Design: NODLINK is designed and implemented as a full-fledged online APT detection system that achieves fine-grained detection with timeliness and limited resources, directly resolving the critical trade-off between detection granularity and computational complexity faced by existing online systems.
• Open-World Evaluation: To the best of the authors' knowledge, NODLINK is the first provenance-based APT attack detection system to undergo a rigorous open-world evaluation in real production environments. This experiment involved monitoring over 300 servers across 10 industrial customers, demonstrating its practical effectiveness and robustness in realistic, unseen scenarios.
• Superior Performance: The comprehensive evaluation, particularly the open-world experiment, reveals that NODLINK significantly outperforms two state-of-the-art online provenance analysis systems, HOLMES (rule-based) and UNICORN (learning-based). It achieves magnitudes higher detection and investigation accuracy, specifically in node-level precision, while maintaining comparable or even higher throughput. For instance, in open-world tests, NODLINK achieved 1.00 recall and 0.14 precision at the node-level, compared to UNICORN's 1.00 recall but extremely low 3.61 x 10^-4 precision, and HOLMES's complete failure to detect any attacks.
• Actionable Intelligence: By generating concise, attack-centric provenance graphs (e.g., typically hundreds of nodes compared to tens or hundreds of thousands for UNICORN), NODLINK significantly reduces the burden on security administrators, enabling more efficient and effective attack investigation.
• Open-Source Release: The project includes the release of an open-source version of NODLINK, along with a new public provenance dataset simulating Sangfor's internal environments, fostering further research and development in this crucial area.

Technical Deep Dive

▶ Watch: Explaining the Online Steiner Tree Problem (STP) (4:00)

The core of NODLINK's innovation lies in its novel approach to modeling APT attack detection as an Online Steiner Tree Problem (STP). This mathematical framework provides conciseness, efficiency, and accuracy with theoretically bounded errors. The mapping is as follows: attack-related processes are considered terminals in the STP, and the underlying provenance graph (converted to an undirected graph with uniform edge weights of 1) serves as the graph G. The objective is to identify the terminal set T and find the minimal edge set S that connects all these attack-related nodes, minimizing total cost, thus recovering a concise subgraph highlighting only attack-relevant activities.

However, applying STP directly to online APT detection presents three main challenges, each addressed by NODLINK's design:

1. Detecting Long-Term Attacks: Standard STP algorithms require the entire graph upfront, which is infeasible for online provenance data due to its sheer volume. Disk-based solutions introduce prohibitive I/O bottlenecks, and naive time window approaches miss long-running attacks.

• NODLINK's Solution: A novel in-memory cache design prioritizes events likely to cause APT attacks using a scoring method. Low-priority or outdated events are evicted to a Neo4j graph database on disk and retrieved only when necessary, enabling the capture of long-running attacks within the STP's time window.

1. Efficient Terminal Identification: Existing methods for identifying suspicious nodes (terminals) often rely on computationally intensive random walking or message passing, too slow for online systems.

• NODLINK's Solution: An IDF-weighted three-layered Variational AutoEncoder (VAE) model is employed. This model requires minimal computation to identify suspicious process nodes as terminals by analyzing their local features.

1. Efficient STP Approximation: Even with terminals identified, conventional STP approximation algorithms (e.g., shortest path computations) have a complexity of O(N^2), which remains too expensive for online APT detection.

• NODLINK's Solution: An importance-oriented greedy algorithm for online STP optimization is developed. This algorithm achieves a lower computing complexity of O(N) while maintaining a bounded competitive ratio.

System Design and Architecture: NODLINK Workflow

NODLINK operates as a continuous online APT attack detection system, processing a stream of system provenance events. Its primary output is concise alert provenance graphs. The workflow, executed every Δ seconds (set to 10 seconds in the implementation), comprises four main phases:

1. In-Memory Cache Building: Incoming events are fetched and stored in a specialized in-memory cache. This cache is crucial for tracking event causalities, especially for long-running attacks, without the overhead of slow I/O.
2. Terminal Identification: Within the cached provenance graph, suspicious process nodes are identified. They are assigned anomaly scores based on local features (command lines, process names, accessed files) and designated as terminals for the STP phase.
3. Hopset Construction: For each identified terminal, NODLINK constructs a hopset, which is an approximated Steiner tree solution representing the local context around a set of event-level anomalies. This phase uses the importance-oriented greedy algorithm (ISG) to efficiently connect topologically close anomalies.
4. Comprehensive Detection: Hopsets from the current time window are merged with existing cached hopsets. The aggregated Hopset Anomaly Scores (HAS) of these merged subgraphs are analyzed. If a subgraph's HAS exceeds a predefined threshold, NODLINK raises an alert, reporting a concise provenance graph of the detected APT attack.

System Design Details

In-Memory Cache: The cache stores provenance graph edges (srcid, dstid, attr) and essential node attributes (command lines, PIDs for processes; file paths for files; IPs with ports for IP addresses). Unique UUIDs (MD5 hash of key attributes) enable O(1) lookup.

The cache updates with new STP solutions (hopsets) every Δ seconds. Each hopset h is assigned a Hopset Anomaly Score (HAS). To manage memory, an energy metric E = e(age) * HAS(h) is used, where e is a decaying factor (0.8) and age is the number of time windows since the last update. Higher energy hopsets remain in memory; those with the lowest energy are evicted to a Neo4j graph database. If an evicted node is needed, its attributes and containing hopset are retrieved from Neo4j and merged back into memory.

Terminal Identification: This phase converts raw node-level features into numerical vectors and then identifies anomalies.

1. Embedding Node-Level Features: Command lines, file paths, and IP addresses are converted into natural language-like sentences (e.g., /etc/tmp/log.txt becomes etc tmp log txt). Nostril 48 filters non-natural-linguistic tokens. FastText 18 then converts these sentences into numerical vectors efficiently. The final embedding vector Vp for a process p is a weighted sum: Vp = Wc Vc + Σ Wfi Vfi + Σ Wni * Vni. Weights Wfi and Wni are calculated using log(P/Pf) (where P is total processes, Pf is processes operating on fi), which degrades the impact of commonly shared, benign entities (e.g., libc).
2. Anomaly Detection: A lightweight Variational AutoEncoder (VAE) 60 calculates an anomaly score (AS). The reconstruction error (RE) (normalized MSELoss between Vp and Vp') indicates rareness. To reduce false positives from unstable benign processes (e.g., web browsers), a stability score (SV) is introduced, representing the cluster number of processes with the same name in historical data (calculated offline using DBSCAN 58). The final anomaly score AS(p) = log(RE(P) / SV(p)). A process is marked as a terminal if its AS is higher than the 90th percentile of AS in historical data. FastText, VAE, and SV models are trained offline using historical data.

Hopset Construction: This phase solves the STP within the current time window using the Importance-Score-Guided Search (ISG) algorithm, a greedy approach that optimizes shortest path finding from O(N^2) to O(N). For each identified terminal, NODLINK starts a greedy search, exploring a bounded number of θ nodes (set to 10) based on an Importance Score (IV). This bound is motivated by the "attack polymerism" principle, suggesting attack actions are topologically close. Overlapping hopsets are then merged.

The Importance Score (IV(n)) for a node n is defined as: IV(n) = a^i (β AS(n) + γ * FANOUT(n)).

• a: Distance decaying factor (0.9).
• i: Hops from the nearest terminal.
• AS(n): Anomaly score of node n.
• FANOUT(n): out_degree(n) / (in_degree(n) + 1), deprioritizing leaf nodes.
• β, γ: Weights, with β much larger than γ (e.g., 100:1) to prioritize AS(n).

The Hopset Anomaly Score (HAS(Hi)) for each hopset Hi is the sum of the anomaly scores of all nodes within it: HAS(Hi) = Σn∈Hi AS(n).

Comprehensive Detection: This final phase integrates hopsets and identifies attack campaigns. The in-memory cache is updated by merging current hopsets with existing ones, limiting each terminal's hopset to θ nodes and replacing lower-IV nodes with higher-IV ones during merging. HAS values are recalculated. Finally, Grubbs's test 10, a robust statistical outlier test, is applied to the HAS values of cached hopsets to identify and flag attack campaigns.

Theoretical Analysis:

• Complexity: Terminal identification is O(E). Hopset construction is O(θN) (for N nodes, θ exploration per terminal). The overall complexity of NODLINK is dominated by Hopset Construction, making it O(θN), significantly more efficient than O(N^2) algorithms.
• Competitive Ratio: NODLINK maintains a competitive ratio of O(log(k)), specifically 2θlog(k), where k is the number of terminals and θ is the constant search scope (10). This demonstrates that the importance-score-guided search maintains theoretical worst-case performance guarantees despite its improved efficiency.

Demo / Proof of Concept

▶ Watch: NODLINK's threat model and key assumptions (4:09)

While the talk did not feature a live "demo" in the traditional sense, the evaluation section, particularly RQ5: Attacks Detected In Production, serves as a robust proof-of-concept for NODLINK's real-world efficacy. This open-world experiment involved deploying NODLINK to a beta version of Sangfor's EDR, monitoring over 300 servers across 10 industrial customers (hospitals, universities, factories) without prior knowledge of their data.

NODLINK successfully detected all seven real APT attack campaigns identified by a professional security team from 135,700 initial alerts over two days, which were then manually reduced to 2,000 true attack-relevant events. In stark contrast, HOLMES failed to detect any of these attacks because its rule set lacked coverage for common open-world attack techniques like webshell code injection. UNICORN, while detecting all attacks, generated provenance graphs that were overwhelmingly large (often over 100,000 nodes), making investigation extremely difficult for security administrators.

NODLINK's key advantage in these production scenarios was its ability to generate concise alert provenance graphs, significantly improving node-level precision. Several illustrative case studies highlighted this:

• Attack 1 (Figure 3): An attacker hijacked a Windows IIS Web Server via webshell injection, executed a trojan, uploaded remote persistence tools, and performed intranet blasting. NODLINK generated a graph of about 260 nodes with a node-level precision of 0.27, clearly identifying core attack steps like w3wp.exe, csc.exe, and fscan.exe as terminals. UNICORN, conversely, generated over 100,000 nodes, including many benign explorer.exe events.
• Attack 2 (Figure 4): An attacker hijacked an SQL Server, downloaded a backdoor, added a hidden user for persistence, and exfiltrated data. NODLINK produced a graph of about 50 nodes with a node-level precision of 0.34, pinpointing sqlservr.exe, FgB.exe, and other Living-Off-The-Land tools. UNICORN generated over 5,000 nodes, cluttered with irrelevant normal SQL Server behavior.
• Attack 3 (Figure 5): An adversary injected a webshell into Tomcat, left backdoors, used frpc.exe for lateral movement, and scanned for sensitive information. NODLINK's graph contained about 350 nodes with 0.22 precision, identifying Tomcat8.exe, backdoor processes, and 1.exe as terminals. UNICORN generated over 33,000 nodes.
• Attack 4 (Figure 6): An attacker hijacked an SQL Server, downloaded a CS Trojan (scvhost.exe), set up a reverse proxy, collected system info, and scanned the intranet. NODLINK generated a highly precise graph of about 80 nodes with 0.75 precision, identifying sqlservr.exe, backdoor processes, and scvhost.exe. UNICORN produced over 10,000 nodes.
• Attack 5 (Figure 7): An attacker used WMI (wmiprvse.exe) for remote commands, copied Tomcat.exe to Proxy.exe, set up a reverse proxy, and created scheduled tasks for persistence. NODLINK's graph had about 900 nodes with 0.22 precision, accurately identifying wmiprvse.exe, Tomcat.exe, and scheduled task processes. UNICORN generated over 63,000 nodes.
• Attack 6 (Figure 8): Malicious code was injected into rundll32.exe, setting up external connections, implanting intranet proxy/scanning tools (fscan.exe), and modifying the registry for privilege escalation. NODLINK's graph was about 400 nodes with 0.20 precision, identifying rundll32.exe, fscan.exe, and registry modifications. UNICORN produced over 25,000 nodes.
• Attack 7 (Figure 9): An attacker connected to a webshell backdoor, uploaded numerous malicious files (including a Godzilla webshell and dog-tunnel proxy), and set up dt.exe as a reverse proxy. NODLINK generated a graph of about 1800 nodes with 0.24 precision, identifying Tomcat.exe, dt.exe, and file explorer listing malicious files. UNICORN generated over 289,000 nodes.

These real-world examples underscore NODLINK's superior ability to provide security administrators with highly actionable, concise, and attack-centric provenance graphs, significantly streamlining the investigation of complex APT attacks.

Defensive Implications

▶ Watch: Core technical approach: APT detection as Online STP (6:00)

NODLINK's advancements have several crucial implications for cybersecurity defenders seeking to improve their resilience against sophisticated APT attacks:

1. Prioritize Granular and Causal Detection: Defenders should move beyond systems that merely flag individual anomalous events. NODLINK demonstrates the paramount importance of systems that can reconstruct the causal chain of an attack with high granularity. This shift from "event-level anomaly" to "attack path reconstruction" is critical for understanding the full scope and impact of a breach.
2. Actionable Intelligence for Incident Response: The problem of "too many alerts, too little context" is a major challenge for security operations centers (SOCs). NODLINK's ability to produce concise, attack-centric provenance graphs directly addresses this. Defenders can leverage such systems to dramatically reduce the time and effort required for incident investigation, moving from sifting through thousands of irrelevant events to focusing on hundreds of highly relevant ones. This translates to faster containment and remediation.
3. Defense Against Long-Running, Stealthy Attacks: APTs often operate over extended periods, making their detection challenging for systems with short memory windows. NODLINK's novel in-memory cache and disk retrieval mechanism (Neo4j) are vital defensive components. They enable the system to link attack steps spanning across long time intervals, effectively countering attacker attempts to evade detection by extending the time between malicious actions or introducing benign decoy events.
4. Robustness in Real-World Environments: The success of NODLINK in open-world production environments provides confidence that such systems can perform effectively outside of controlled lab settings. Defenders should seek out solutions validated in similar real-world scenarios, as these are less prone to overfitting and more likely to handle the inherent noise and diversity of live networks.
5. Securing the Auditing Pipeline: NODLINK's threat model assumes secure and reliable system-level auditing frameworks. This implicitly highlights the foundational importance for defenders to ensure the integrity, availability, and security of their log collection, storage, and transmission mechanisms. If an attacker can compromise the provenance data itself, even the most sophisticated analysis system will be rendered ineffective.
6. Leveraging Machine Learning for Specificity: While learning-based systems like UNICORN offer high recall, their low precision (due to over-approximation) makes them less useful for fine-grained investigation. NODLINK's combination of VAE for anomaly scoring and the Importance-Score-Guided Search (ISG) algorithm for graph reduction demonstrates how machine learning can be effectively tuned to provide both high recall and high precision, offering a more balanced and practical defensive capability.
7. Continuous Improvement through Open Source: The release of NODLINK as an open-source project along with a new public dataset fosters community collaboration. Defenders, researchers, and vendors can contribute to and benefit from this foundation, accelerating the development of even more robust and adaptive APT detection techniques.

Key Takeaways

• APT Detection as Online STP: NODLINK innovatively models APT attack detection as an Online Steiner Tree Problem (STP), providing a theoretically sound framework for generating concise, attack-relevant provenance graphs with bounded approximation errors.
• Granularity and Efficiency Achieved: It successfully resolves the long-standing trade-off in online provenance analysis, delivering fine-grained detection accuracy (high node-level precision) without sacrificing computational efficiency (high throughput) for real-time operation.
• Novel System Components: Key to NODLINK's performance are its novel in-memory cache design (for long-running attacks), an IDF-weighted VAE for efficient terminal identification, and the Importance-Score-Guided Search (ISG) algorithm for efficient STP approximation (O(N) complexity).
• Superior Real-World Performance: In comprehensive open-world experiments on production networks, NODLINK significantly outperforms state-of-the-art online systems like HOLMES (rule-based) and UNICORN (learning-based) in both graph-level and node-level accuracy, detecting all attacks while generating magnitudes fewer false positives and more interpretable outputs.
• Actionable Intelligence for Investigators: By producing concise provenance graphs (e.g., hundreds of nodes vs. tens or hundreds of thousands), NODLINK drastically reduces the burden on security administrators, enabling more efficient and effective investigation of complex multi-stage APT attacks.
• Robustness and Future Contributions: The system demonstrates robustness to minor training data contamination and supports multiple operating systems. Its open-source release and new public dataset contribute significantly to advancing research in this critical security domain.

About the Speaker(s)

The talk "NODLINK: An Online System for Fine-Grained APT Attack Detection and Investigation" was presented by Shaofei Li. While the transcript does not provide specific title or affiliation, the discussion of NODLINK's implementation and evaluation mentions its integration into Sangfor's commercial EDR solution and the use of Sangfor's internal environments for custom datasets. This suggests Shaofei Li is likely a researcher or engineer affiliated with Sangfor, contributing to advanced cybersecurity solutions.