Threat Detection and Investigation with System-level Provenance Graphs: A Survey

1. Introduction

• The paper argues that existing mitigation strategies are challenged by evolving attack surfaces and motivates more robust detection of known and previously unseen attacks.It identifies provenance graphs as promising for their semantic expression and attack-history correlation capabilities.Source: §1 · p. 1
• Provenance graphs represent system interactions and execution history, supporting semantic-aware detection and investigation of long-running attacks.Their spatial and temporal information is described as harder to forge than unstructured audit logs.Source: §1 · p. 1
• The collection module gathers provenance, data management provides efficient queries and economical storage, and detection seeks stealthy malicious behavior with low overhead and latency.The survey describes collection as the foundation and data management as a bridge between collection and detection.Source: §1 · pp. 1–2
• The survey asks how to reduce storage while preserving semantics, balance storage and query efficiency, balance true and false positives, and shorten detection and forensic response time.These questions are presented as considerations for an ideal provenance graph-based system.Source: §1 · p. 2
• The survey presents a typical provenance-based system architecture and taxonomizes representative techniques, comparing dozens of detection systems to guide technology selection and future research.It identifies data collection, data management, and threat detection as the system’s three modules.Source: §1 · p. 2

2.1. Definition of System-level Provenance Graph

• A provenance graph represents subjects and objects as nodes and operations as timed edges; causality links events when one event’s object is the next event’s subject and its time is earlier.Such dependencies indicate possible data or control flow, but may include false dependencies that contribute to dependence explosion.Source: §2.1 · pp. 2–3

2.2. Typical Design of Provenance Graph-based Detection System

• Collectors produce provenance events, data management reduces and stores them for queries, and detection must handle high-volume data and locate suspicious events promptly.Coarse-grained collection can use built-in auditing; fine-grained collection requires extra infrastructure, has higher overhead, and may require vendor support.Source: §2.2 · p. 3

2.3. A Brief History of The Adoption of Provenance Graph in Threat Detection

• Research trends include fine-grained collection to mitigate dependence explosion and streaming detection to reduce delays associated with investigating only after a complete graph is built.Fine-grained collection has higher overhead; streaming graph-based detection targets real-time detection and investigation.Source: §2.3 · p. 4

3. Related Work and Scope of this Survey

• The survey reviews research related to system-level provenance graph-based threat detection, defines its scope, and describes its survey methodology.Its focus is provenance graphs recording information flow between system-level objects.Source: §3 · p. 4, §3.2 · p. 5

3.1. Intrusion Detection

• Intrusion detection includes signature-based, anomaly-based, and hybrid approaches, while provenance graphs offer causal correlation for stealthy threats beyond single-point detection.Signature methods target known attacks; anomaly methods can detect zero-day attacks but may produce many false positives.Source: §3.1 · pp. 4–5

3.2. Provenance

• Data provenance records data origins, whereas this survey focuses on system-level provenance graphs that detail information flow and can help locate potentially malicious behavior.The passage describes provenance as also known as data lineage.Source: §3.2 · p. 5

3.3. Graphs for Security Purpose

• The survey focuses on provenance graphs because the other discussed graph approaches do not effectively model information flow between system-level objects with acceptable overhead.It states that provenance graphs also support correlation analysis naturally.Source: §3.3 · p. 5

3.4. Survey Methodology

• The survey combines keyword searches across databases with Connected Papers and snowballing to find related work missed by keyword combinations alone.The keyword groups correspond to the three modules in the typical system design.Source: §3.4 · p. 5

4.1. Coarse-grained Provenance Collection

• Coarse-grained collectors track provenance among system-level objects using sources such as operating-system audits or third-party tools, with event lists customizable to balance overhead and functionality.Examples include Linux Auditd and Windows ETW; the passage notes that event lists vary by operating system.Source: §4.1 · pp. 5–6, §4 · p. 5

4.2. Fine-grained Provenance Collection

• Fine-grained collection can reduce dependence explosion by associating inputs and outputs more accurately, but taint analysis can slow programs by 2× to 10× or more.Execution-partition approaches seek a middle ground but rely on assumptions about causal units and may require extra infrastructure or vendor support.Source: §4.2 · p. 6
• Causality inference can reduce false positives by comparing master and slave output buffers or by modeling summaries of many nodes’ behavior.The survey describes dual-execution inference and Winnower as examples.Source: §4.2 · p. 6

5.1. Data Storage Models

• Graph databases support semantic graph queries but can require loading large graphs into memory; streaming graphs cache event history, while vertex-centric relational databases can use disk and in-memory cache.The survey associates streaming graphs with algorithms that consume each event once and vertex-centric databases with abnormal-analysis detection.Source: §5.1 · pp. 6–7

5.2. Data Reduction Algorithms for Provenance Graphs

• Provenance compression removes unnecessary nodes and edges while balancing retained semantics, computational complexity, and compression effectiveness.The management module also weighs storage savings against query-time efficiency.Source: §5 · p. 6, §5.2 · p. 7

5.2.1. Data Reduction for Edges

• CPR removes repeated reads or writes when no intervening access changes causality; FDR and SDR enable further compaction but require more expensive global reachability.CPR preserves graph topology but loses statistics such as access frequency, so reduction choice depends on subsequent analysis.Source: §5.2.1 · p. 8

5.2.2. Data Reduction for Nodes

• Web-graph and common-subgraph compression can impose costly runtime overhead, while node-reduction methods described here have lower compression ratios than edge-based methods.Garbage collection can remove isolated temporary nodes without affecting causality; nodemerge finds common access patterns during program initialization.Source: §5.2.1 · p. 7, §5.2.2 · p. 8

5.3. Query Interface

• Specialized query systems add causality tracking, reusable attack-pattern matching, real-time multi-host stream queries, and expert-defined anomaly models beyond generic interfaces.Generic interfaces may not be flexible enough for customized investigation requirements.Source: §5.3 · p. 8

• Naive backtracking can struggle to distinguish normal data flow from malicious control flow, creating dependence explosion and low accuracy.It also requires a complete provenance graph and substantial human intervention, limiting timeliness and efficiency.Source: §6 · pp. 8–9
• The section seeks detection systems that are real-time, efficient, and produce few false positives while supporting threat detection and forensic traceability.Source: §6 · p. 9
• The design questions are how to balance true and false positives while making detection and forensic traceability faster.Source: §6 · p. 9

6.1.1. Multi-Stage APT Attack (APT) Model

• The multi-stage APT model uses attacks' staged structure to support threat identification despite missing stages and to filter false alerts.Real-world attacks usually involve three or more stages, and forensic techniques can help complete missing pieces.Source: §6.1.1 · p. 9

6.1.2. Information Leakage (Leakage) Model

• The information-leakage model monitors whether sensitive information flows to unauthorized destinations, without focusing on particular attack technologies.Source: §6.1.2 · p. 9

6.1.3. General Attack (General) Model

• The general-attack model addresses varied threats, from stealthy APTs to overt ransomware, whose goals include both information theft and destruction.Source: §6.1.3 · p. 9

6.2. Threat Detection and Investigation System Design

• Detection must balance fast response, efficiency, and accuracy despite the space and computing overhead of large provenance graphs.The survey groups approaches by their primary detection design.Source: §6.2 · p. 9
• Tag propagation processes events incrementally and supports streaming input; approaches use tags to trace causality, but dependency explosion can produce false positives.HOLMES raises an aggregation threshold, while MORSE uses tag decay and attenuation to limit propagation.Source: §6.2 · p. 9, §6.2.3 · p. 11
• Table 3's taxonomy links attack models, detection algorithms, and data-management models, which the survey describes as interdependent design choices.Source: §6.2 · p. 10, Table 3 · p. 10

6.2.1. Graph Matching-based Detection

• Graph matching detects malicious substructures but is NP-complete; POIROT relies on manually extracted query graphs, while embedding methods require training data and cached graphs.UNICORN uses an incrementally updatable, fixed-size longitudinal graph sketch, but retains limitations of anomaly detection.Source: §6.2.1 · p. 10

6.2.2. Anomaly Score-based Detection

• Anomaly-score methods use historical statistics to assess suspicious access and require fewer parameters than graph-based anomaly detection; their vertex-centric databases are faster than graph databases.Source: §6.2.2 · pp. 10–11

6.2.3. Tag Propagation-based Detection

• Tag-based methods replace costly graph matching with node-tag initialization and propagation, enabling quick streaming updates and intrusion-point tracing without tedious backtracking.HOLMES requires multiple tags to meet a threshold, while MORSE reduces impact across transmission rounds using decay and attenuation.Source: §6.2.3 · p. 11

7.1. How the Selection of Data Models and Detection Models Will Affect Performance?

• Cached graph databases are inefficient and not recommended; vertex-centric databases speed node access but make edge access slower and more complicated.NoDoze pairs vertex-centric storage with anomaly-score detection, which needs node information; SLEUTH processes nodes and edges once and caches tags for streaming detection.Source: §7.1 · p. 11
• Tag propagation handles provenance graphs as streams in real time and has the shortest response time, while cached-graph detection is common but inefficient.The discussion identifies three frequent pairings: anomaly score with vertex-centric databases, tag propagation with streaming graphs, and cached graphs with other models.Source: §7.1 · p. 11

7.2. How to Solve the Dependence Explosion Problem?

• Coarse-grained provenance and causality analysis can cause dependence explosion, adding false positives and overhead; fine-grained collection can address it but is costly to deploy.The authors say fine-grained methods bring significant runtime or development overhead, making real-world use difficult.Source: §7.2 · p. 11
• Algorithmic mitigations rely on assumptions attackers can evade, and existing approaches only mitigate dependence explosion, leaving a need for more efficient and robust solutions.Anomaly scoring assumes attacks involve unusual edges, while tag decay assumes attacks happen quickly; the discussion describes counterexamples to both assumptions.Source: §7.2 · p. 12

7.3. How to Balance the True-positive and False-positive?

• More complicated detection models can distinguish malicious from benign behavior more accurately, but tend to incur higher overhead.Multi-stage models can improve accuracy through alert correlation compared with single-point models.Source: §7.3 · p. 12
• High true-positive and low false-positive rates can conflict; HOLMES uses broad signatures and alert correlation, while POIROT uses sophisticated signatures but cannot detect previously unseen behavior.HOLMES parameter tuning is often empirical and can make results unstable; POIROT needs a database built from extensive real-world threat intelligence.Source: §7.3 · p. 12

7.4. Other Practical Challenges

• The discussion flags limited unified datasets and missing evasion studies; existing datasets include only dozens of attacks in most self-collected sets.The only publicly available datasets identified are Engagement 3 and 5, and the authors say anti-evasion studies are still missing for this detection setting.Source: §7.4 · p. 13

7.5. An Ideal Detection Approach

• An ideal system would process streaming provenance graphs with low overhead and short response time while using sufficiently complex graph-based models for robust, effective detection.The discussion favors tag propagation for performance and graph-based modeling for distinguishing malicious from benign behavior.Source: §7.5 · p. 13

8. Conclusion

• Provenance graphs are widely accepted as a system-behavior abstraction for endpoint threat detection.Source: §8 · p. 13
• The survey presents a typical architecture for provenance graph-based threat detection.Source: §8 · p. 13
• It compares the techniques involved and identifies existing research challenges for future study.Source: §8 · p. 13