Provenance Graphs

In the realm of modern cybersecurity, traditional logs (like simple lists of system calls) often fail to capture the complex, long-term behavior of sophisticated attacks like "Advanced Persistent Threats" (APTs).

Data Provenance offers a solution by structuring system logs into a graph that represents the history of interactions between system entities. This guide explains what Provenance Graphs are, how they are constructed, and how they are used for Intrusion Detection and Forensics.

info

The content of this guide is synthesized from recent academic research, including surveys on Provenance-based Intrusion Detection Systems (PIDS). Check the references section for more details.

What is a Provenance Graph?

At its core, Data Provenance refers to a record trail representing an event's origin and explaining how and why it reached its current state.

In computer systems, we represent this as a Provenance Graph. Technically, it is a Directed Acyclic Graph (DAG), denoted as $G = (N, E)$, where:

• $N$ (Nodes): Represent system entities (also called vertices).
• $E$ (Edges): Represent system operations (events) describing the information flow.

Core Components

1. Nodes (System Entities)

Nodes represent the "nouns" of the system. Common node types include:

• Process: An executing program (e.g., nginx, bash.exe).
• File: Data stored on disk (e.g., /etc/passwd, malware.exe).
• Network Socket: Communication endpoints (e.g., 192.168.1.5:80).
• Memory Object: Shared memory segments.

2. Edges (System Operations)

Edges represent the "verbs" or actions connecting the nodes. They are directed to show the flow of data or control.

• Information Flow: read, write, send, receive.
• Control Flow: execute, fork, clone.

Visual Example

Imagine a simplified Phishing Attack scenario:

1. User receives an email.
2. Outlook (Process) downloads an attachment malware.doc (File).
3. Word (Process) opens malware.doc.
4. Word executes a malicious macro, spawning cmd.exe (Process).
5. cmd.exe reads passwords.txt (File) and sends it to IP: 1.2.3.4 (Socket).

In a provenance graph, this is a chain of causal dependencies:

Why Use Provenance Graphs?

Traditional Host-based Intrusion Detection Systems (HIDS) often look at events $\color{red}{\text{in isolation}}$. Provenance graphs provide $\color{blue}{\text{Context and Causality}}$.

1. The "Holistic View"

Provenance provides an attack-vector-agnostic view of system execution. Instead of looking for a specific virus signature, it looks for abnormal relationships. As noted in security research, even if an attacker changes their malware's binary hash, the behavioral graph (download -> execute -> exfiltrate) often remains the same.

2. Causality Analysis

Because the graph captures history, security analysts can ask complex questions:

• Backward Tracing: "Where did this malicious file come from?" (Root Cause Analysis).
• Forward Tracing: "What files did this malicious process touch?" (Impact Analysis).

Fundamental Operations

When analyzing provenance graphs for forensics, two algorithms are essential.

Backward Tracing

Backward tracing determines the lineage of a node. It is used to find the "Patient Zero" or the entry point of an attack.

Pseudocode for Backward Tracing

def backward_tracing(graph, node_of_interest):
    trace = []
    # Find all edges pointing TO the node
    incoming_edges = graph.find_incoming(node_of_interest)
    
    for edge in incoming_edges:
        source_node = edge.source
        trace.append(edge)
        trace.append(source_node)
        # Recursively trace backwards
        trace.extend(backward_tracing(graph, source_node))
        
    return trace

Forward Tracing

Forward tracing discovers the influence of a node. It is crucial for assessing data leakage or corruption.

Pseudocode for Forward Tracing

def forward_tracing(graph, node_of_interest):
    trace = []
    # Find all edges starting FROM the node
    outgoing_edges = graph.find_outgoing(node_of_interest)
    
    for edge in outgoing_edges:
        target_node = edge.target
        trace.append(edge)
        trace.append(target_node)
        # Recursively trace forwards
        trace.extend(forward_tracing(graph, target_node))
        
    return trace

Provenance-based Intrusion Detection (PIDS)

PIDS utilize these graphs to detect intrusions automatically. Unlike simple antivirus software, PIDS can detect "living off the land" attacks where attackers use legitimate tools (like PowerShell) for malicious purposes.

Detection Strategies

Strategy	Description	Pros	Cons
Anomaly-based	Learns "normal" graph patterns and flags deviations.	Detects zero-day attacks.	High false-positive rate if not tuned.
Rule-based	Uses predefined graph query rules (e.g., "Process A launched by B connecting to Port C").	Low false positives.	Cannot detect unknown attack patterns.
Tag Propagation	"Taints" data from untrusted sources (e.g., internet) and tracks where it goes.	Very precise.	Can suffer from "tag explosion" (too many things get tagged).

Data Capture Levels

To build these graphs, data must be captured from the Operating System.

• System-Level: Captures system calls (e.g., via Linux Auditd, ETW, CamFlow). Good balance of detail and performance.
• Unit-Level: Breaks long-running processes into smaller "units" to prevent the graph from becoming a giant "hairball."
• Instruction-Level: Captures CPU instructions. Extremely detailed but very slow (high overhead).

Challenges

While powerful, Provenance Graphs come with challenges:

• Data Explosion: A single host can generate gigabytes of provenance data per day.
• Graph Summarization: Techniques are needed to compress these graphs without losing security-critical information (e.g., merging repetitive read events).
• Dependency Explosion: In long-running processes (like a web browser), everything eventually connects to everything, making the graph dense and hard to analyze.

References

For a deeper dive, consider exploring these academic resources:

• Provenance-based Intrusion Detection Systems: A Survey
• Provenance-based Intrusion Detection by Thomas Pasquier, University of Bristol, UK Cyber Security Winter School, Newcastle, 15/01/2020
• Provenance-based Intrusion Detection: Opportunities and Challenges