PaperlayerView exact revision on arXiv

Source-linked AI summary

Runtime Analysis of Whole-System Provenance

Thomas Pasquier, Xueyuan Han, Thomas Moyer, Adam Bates, Olivier Hermant, David Eyers, Jean Bacon, Margo Seltzer

arXiv:1808.06049v2cs.CRcs.OS

TL;DR

Existing provenance auditing is largely retrospective, and conventional architectures impose latency that limits runtime security analysis. CamQuery analyzes live provenance through a kernel-layer framework and supports runtime security applications. The paper reports reduced detection latency and minimal execution overhead, while noting that provenance signatures can be impractical at scale.

  • Problem

    Existing provenance systems primarily support post-hoc forensic analysis, while runtime security applications need low-latency analysis of provenance streams.

    Source: §1 · p. 1, §2.2 · p. 2

  • Method

    CamQuery pairs kernel-layer provenance capture with query modules that analyze live provenance and can mediate system events.

    Source: §1 · p. 1, §3.4 · p. 4

  • Results

    CamQuery demonstrates runtime security applications and reports reduced time from an event to its detection, with minimal execution overhead.

    Source: §1 · p. 2, §9 · p. 14

  • Takeaways & Limitations

    CamQuery supports runtime provenance applications while allowing provenance to be persisted for post-mortem forensic analysis.

    Source: §1 · p. 1

    The provenance graph signature scheme is impractical at scale, and practical provenance integrity schemes remain an open problem beyond this paper’s scope.

    Source: §5 · p. 9

Abstract

from arXiv · show

Identifying the root cause and impact of a system intrusion remains a foundational challenge in computer security. Digital provenance provides a detailed history of the flow of information within a computing system, connecting suspicious events to their root causes. Although existing provenance-based auditing techniques provide value in forensic analysis, they assume that such analysis takes place only retrospectively. Such post-hoc analysis is insufficient for realtime security applications, moreover, even for forensic tasks, prior provenance collection systems exhibited poor performance and scalability, jeopardizing the timeliness of query responses. We present CamQuery, which provides inline, realtime provenance analysis, making it suitable for implementing security applications. CamQuery is a Linux Security Module that offers support for both userspace and in-kernel execution of analysis applications. We demonstrate the applicability of CamQuery to a variety of runtime security applications including data loss prevention, intrusion detection, and regulatory compliance. In evaluation, we demonstrate that CamQuery reduces the latency of realtime query mechanisms, while imposing minimal overheads on system execution. CamQuery thus enables the further deployment of provenance-based technologies to address central challenges in computer security.

1 INTRODUCTION

Provenance can connect suspicious events to their causes, but post-hoc investigations are slow and existing provenance systems were not designed for low-latency runtime security. CamQuery analyzes live provenance and is demonstrated across several security applications.

1 INTRODUCTION

  • Investigations can take months and thousands of employee hours, while existing provenance systems can require hours or days for forensic queries and were not designed for realtime security analysis.The delay leaves attackers time to continue exploiting a system while defenders investigate.Source: §1 · p. 1
  • Provenance graphs capture relationships among system events and objects, allowing investigators to trace a security indicator backward to an entry point and forward to an attacker’s subsequent actions.The paper describes provenance as records parsed into causal relationship graphs.Source: §1 · p. 1
  • CamQuery combines a runtime kernel-layer reference monitor with a query mechanism that analyzes live provenance, while provenance can also be persisted for forensic analysis.The framework supports runtime security applications and mediation of system events.Source: §1 · p. 1
  • CamQuery is demonstrated through data-loss prevention, provenance-based intrusion detection, information-flow constraints, and provenance signatures.The paper also identifies whole-system provenance modelling and performance evaluation among its contributions.Source: §1 · pp. 1–2

2 BACKGROUND

Whole-system provenance represents system activity as a causal graph of kernel objects, tasks, and users. Conventional capture architectures were built for post-mortem analysis, limiting their suitability for runtime security.

2.1 Whole-System Provenance

  • Whole-system provenance models kernel objects as entities, tasks as activities, and users and groups as agents in a directed acyclic graph.Object versions preserve acyclicity as information flows through mutable processes and files.Source: §2.1 · p. 2
  • For provenance-based prevention to be trustworthy, capture must be complete and faithful: missing events can break information-flow links, while erroneous records can implicate benign processes.Whole-system provenance uses a reference-monitor approach to mediate events from system initialization to shutdown.Source: §2.1 · p. 2

2.2 Issues With Provenance Architectures

  • Traditional provenance architectures separate capture, collection, storage, querying, and analysis, but were not designed for realtime security applications.The conventional stack can impose latency because data must be stored before it is queried or analyzed.Source: §2.2 · p. 2
  • Prior systems demonstrated runtime security applications on conventional provenance stacks, but delaying analysis until after storage is impractical when analysis must mediate actions.The paper proposes vertex-centric, real-time analysis of streaming provenance for such applications.Source: §2.2 · p. 2

3 RUNTIME ANALYSIS FRAMEWORK

CamQuery is a framework for runtime analysis of provenance, designed to support security applications against a remote attacker. It applies stream-based analysis to provenance captured in the kernel and exposes a developer API for implementing queries.

3.1 Threat Model & Assumptions

  • CamQuery assumes a remote attacker without physical access, a trusted kernel, secure provenance storage when forensic records are retained, and no checkpointing.Its trusted computing base includes provenance capture and runtime query mechanisms.Source: §3.1 · p. 3

3.2 Motivating Example

  • Realtime label propagation can replace repeated ancestry traversal for loss prevention, enabling constant-time authorization decisions while retaining graph-based propagation constraints.The framework also targets path constraints, access control, and runtime feature generation for intrusion detection.Source: §3.2 · p. 3

3.3 Overview

  • CamQuery converts events captured through LSM and NetFilter hooks into provenance graph elements, which feed stacked queries and can be sent to userspace, stored, or transmitted remotely.Queries may be built into the kernel or implemented as loadable kernel modules.Source: §3.3 · pp. 3–4

3.4 Provenance Monitor

  • The kernel provenance monitor provides complete mediation, tamperproofness, and verifiability, and CamQuery lets applications authorize or deny accesses using provenance history.The monitor extends capture systems that previously denied access mainly when they could not create a record.Source: §3.4 · p. 4

3.5 CamQuery API

  • CamQuery’s vertex-centric API lets developers express queries through initialization and incoming- and outgoing-edge functions, processed in graph order.The API exposes kernel-object attributes and supports labels or values on graph elements, enabling compact taint-tracking, information-flow-control, and access-control mechanisms.Source: §3.5 · p. 4
  • Developers can associate complex data structures with kernel objects and compute graph analytics during traversal, including runtime feature vectors for intrusion detection.The framework decouples analysis implementations from kernel infrastructure to reduce engineering effort.Source: §3.5 · p. 5

4 IMPLEMENTATION

CamQuery extends CamFlow to capture and analyze provenance at runtime, with mechanisms for ordering events, modeling provenance completeness and accuracy, and running queries in kernel or user space.

4.1 Capture Mechanism

  • CamFlow tracks shared states conservatively as graph entities, adds process-to-state and state-to-process relations for reads and writes, and represents process memory shared between threads.This thread-level tracking is intended to improve provenance accuracy, but assuming flows can produce false positives.Source: §4.1 · p. 5
  • CamFlow generates provenance graphs at capture time and publishes graph components during execution with ordering guarantees that CamQuery uses to process edges and vertices.The guarantees place incoming edges before outgoing edges at each vertex and publish edges and vertices along a path in order.Source: §4.1 · p. 5
  • CamFlow embeds limited provenance metadata in kernel objects to avoid cycles using local node properties, creating a new object version when a sender later receives information.This rule guarantees global acyclicity without maintaining global state.Source: §4.1 · p. 5

4.2 Ensuring Completeness and Accuracy

  • CamFlow uses static analysis of Linux kernel code to model provenance for supported LSM hooks and identify hooks associated with system calls; models are manually verified.The models are updated in continuous integration as the capture mechanism and kernel evolve, although manual verification requires significant Linux-kernel knowledge.Source: §4.2 · pp. 5–6
  • The authors maintain an LSM patch intended to intercept all information flows, building on prior static-analysis work to strengthen whole-system provenance completeness.They describe their modeling work as a first attempt toward formalizing whole-system provenance, while formalizing the ordering guarantees remains future work.Source: §4.2 · pp. 5–6

4.3 CamQuery Query Configurations

  • CamQuery offers kernel, local user-level, and remote user-level query configurations; kernel objects retain about 20 bytes of provenance state, and long-lived state can persist across reboots through extended attributes.User-level queries maintain edge lists and vertex maps; garbage collection uses object-lifecycle events and would require different domain knowledge for other provenance types such as Spark.Source: §4.3 · pp. 6–7
  • CamQuery supports kernel-level queries that run before the actions they describe, enabling prevention; user-space and remote queries can detect violations only after the fact.Kernel queries can access kernel objects and prevent events, while user-space configurations process provenance streams from relayfs or messaging middleware.Source: §4.3 · pp. 6–7
  • CamQuery’s user-space utility merges per-core edge lists using a QoS threshold, while edge IDs preserve capture ordering and packet causality helps order data across machines.The query then processes the merged edge list sequentially.Source: §4.3 · pp. 6–7

5 EXAMPLE APPLICATIONS

CamQuery supports runtime applications ranging from data-loss prevention and provenance-based anomaly detection to information-flow queries, compliance policies, and graph integrity checks. The signature scheme illustrates a boundary: it is impractical at scale for whole-system provenance.

Example #1: Data Loss Prevention

  • The loss-prevention scheme propagates labels only over policy-relevant flows and warns when sensitive information reaches a system exit such as a socket.Its stated correctness assumptions cover explicit information flow, not side channels.Source: §5 · p. 7

Example #2: Intrusion Detection

  • CamQuery's intrusion-detection example builds per-vertex feature vectors from attributes, changes over time, and structural identity to detect anomalous graph structures.Structural identity vectorizes a vertex's ancestor neighborhood using in-degree sequences; the example IDS uses a replicator neural network to reconstruct feature vectors.Source: §5 · p. 8

Example #3: Information Flow

  • CamQuery's single-pass information-flow queries support path-existence checks and other primitives, each implemented in a few dozen lines of C.The loss-prevention scheme uses a path-existence query.Source: §5 · p. 8

Regulatory Compliance

  • CamQuery policies can audit data access and constrain data paths between financial-data generation and SEC filing under SOX examples.The examples include checking that activities along the path are acceptable or that prohibited activities do not appear.Source: §5 · p. 9

Example #4: Graph Integrity

  • The graph-integrity example signs hashes generated according to provenance-graph structure, enabling verification against the signed value.The example uses a directed acyclic graph signature scheme.Source: §5 · p. 9
  • The graph-signature scheme is impractical at scale and inadequate for whole-system provenance capture.The authors identify practical, scalable provenance-integrity schemes as an open problem.Source: §5 · p. 9

6 EXPERIMENTAL EVALUATION

The evaluation measures capture and query overhead in kernel and user-space implementations. Online querying adds relatively little overhead in the tested workloads, while concurrent-query costs and user-space resource use vary with workload and query.

6.1 In-kernel Queries

  • LMbench results show that online querying introduces relatively little overhead, with system-call cost increasing according to the graph's edges and vertices.The execution-time model includes capture and query costs for each edge and capture costs for each vertex.Source: §6.1 · pp. 9–10, Table 2 · p. 10, Figure 9 · p. 10
  • A prior system took 21 ms to evaluate the same policy, while CamQuery's comparable LPS overhead is contrasted with an estimated 2.31 ms after assumed proportional pre-pruning gains.The 2.31 ms figure is an estimate based on an assumed query-time improvement proportional to reported graph-size reduction, not an evaluated result.Source: §6.1 · p. 10
  • Up to 15% overhead occurs for Postmark, while provenance capture is negligible for the kernel build benchmark; comparisons with PASS and LPM provide context only.The prior-system evaluations used different kernel versions and hardware, so the authors say the results do not support direct comparison.Source: §6.1 · p. 10, Table 3 · p. 11
  • Overhead increases linearly with concurrent queries; Postmark is especially costly because it spends 85% of its time in the kernel and makes 253,000 system calls per second.The authors note that hundreds of concurrent queries are unrealistic for production and leave query merging for future work.Source: Figure 10 · p. 10, §6.1 · p. 11

6.2 User space queries

  • User-space LPS overhead is only minimally larger than in-kernel overhead in the unpack, build, and Postmark benchmarks.The user-space service reads provenance from relayfs on the same machine as the workload.Source: Table 4 · p. 11, §6.2 · p. 11
  • During kernel compilation, the ids processing core reaches about 9% CPU utilization and nil reaches 4%, while other cores use 0%–2%; memory stabilizes at 305 MB and 125 MB, respectively.The ids query builds feature vectors for intrusion detection; each query processes just over 25 million edges in this workload.Source: §6.2 · pp. 11–12, Figure 11 · p. 11, Figure 12 · p. 12

7 CHALLENGES & DISCUSSION

CamQuery leaves open questions around query-language design, distributed enforcement and trust, provenance storage, and false-positive flow inference. Some extensions require additional mechanisms or make trade-offs explicit.

Query Language

  • CamQuery expresses policies with programmable graph processing rather than a user-friendly DSL; a general DSL is difficult because applications such as intrusion detection require different query needs.The authors consider DSL design important but place it within individual applications rather than a general framework.Source: §7 · p. 12

Distributed Systems

  • Extending the user-space implementation to distributed systems is relatively easy but eliminates policy enforcement; distributed enforcement would require partitioned queries and machine-integrity validation.A machine that validates another system's integrity and suitability must also generate proof that the policy was enforced.Source: §7 · p. 12
  • Distributed enforcement could support secure taint propagation, but requires minimally invasive network-stack integration, compatibility with non-provenance-aware hosts, and authenticated, tamperproof transmission.The text identifies IPSec as a possible way to address transmission security, while noting that technical challenges remain.Source: §7 · p. 12

Trust

  • Distributed-system proofs need to cover system integrity, loaded policies, and processed-data state; IMA and TPM-backed remote attestation can measure integrity, but policy enforcement still needs verification.IMA can measure policies loaded as a kernel module when root loads them; mechanisms to validate that policies are correctly enforced remain needed.Source: §7 · p. 12

Storage

  • Provenance storage is orthogonal to this paper, while whole-system systems still need back ends that combine high-throughput ingestion, integrity, non-repudiability, large-volume handling, and low-latency queries.Decoupling query performance from storage overhead opens different possible architectures.Source: §7 · p. 12

False positives from flow tracking

  • Conservative inference of information flow, including through shared memory, can produce false positives; application-level capture could reduce false inferences but its analysis and scalability remain relatively unexplored.The text gives reading a file and writing another as an example of an inferred transfer that may not have occurred.Source: §7 · p. 13

8 RELATED WORK

Related work addresses provenance capture and reduction, provenance applications, information-flow control, taint tracking, and security monitoring. CamQuery’s runtime graph analysis differs from approaches that query accumulated graphs or lack execution-wide context.

Provenance Systems

  • LPM queries provenance DAGs at sink points to enforce information-flow constraints, but database-query latency grows linearly with graph size as provenance accumulates.CamQuery instead runs queries over the provenance stream at runtime, with bounded overhead independent of graph size.Source: §8 · p. 13

Provenance Reduction

  • LogGC [60], BEEP, MPI, and PrioTracker target storage or post-mortem query efficiency, while CamQuery integrates analysis with provenance capture.ProTracer also merges capture and storage layers, but the text describes CamQuery’s goal as orthogonal and interrelated: improving performance through integration of analysis routines with capture.Source: §8 · p. 13

Provenance Applications

  • Prior anomaly-detection approaches accumulate provenance into analysis windows, whereas CamQuery can generate feature vectors as the graph is produced.The passage also says CamQuery could implement the graph-parsing detection stage of Bates et al.’s work.Source: §8 · p. 13
  • CamQuery uses observed provenance like most provenance-based access-control systems, while disclosed provenance and layered provenance are discussed as possible future extensions.The text notes that it is not aware of a layered PBAC enforcement model.Source: §8 · p. 13

Information Flow Control Systems

  • Unlike object-labeling information-flow controls such as HiStar, Flume, Weir, and SELinux, CamQuery implements mechanisms directly on a graph abstraction.The passage says object-labeling abstractions do not take advantage of the graph representation and can be difficult to reason about when defining policies.Source: §8 · p. 13

Taint Tracking Systems

  • CamQuery can achieve results similar to taint tracking, with more control over taint propagation through its query mechanism and provenance records available for forensic analysis.TaintDroid is given as an example of detecting disclosure of personal information to an unexpected third party.Source: §8 · p. 13

Security Monitoring

  • Security-monitoring indicators provide limited context and lack the full execution history; CamQuery supports runtime monitoring over that history rather than relegating attack reconstruction to offline forensics.Prior work attempted to compensate for missing lineage by fusing or correlating multiple indicators.Source: §8 · p. 14

9 CONCLUSION

CamQuery separates runtime detection over live provenance streams from post-mortem forensic analysis backed by databases. This architecture reduces the time from events to detection while retaining data for later investigation.

9 CONCLUSION

  • CamQuery separates runtime detection over live provenance streams from post-mortem forensic applications that use database support for explanations, reducing event-to-detection time by several orders of magnitude while retaining data for forensics.The text frames this as a rethinking of provenance applications’ conventional link to database back ends.Source: §9 · p. 14
Loading 1808.06049v2…