PaperlayerView exact revision on arXiv

Source-linked AI summary

UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats

Xueyuan Han, Thomas Pasquier, Adam Bates, James Mickens, Margo Seltzer

arXiv:2001.01525v2cs.CR

TL;DR

APTs are difficult to detect because their attacks unfold slowly and often use zero-day exploits. UNICORN analyzes streaming provenance graphs with compact sketches and evolutionary models, improving precision and accuracy over previous work while detecting real-life campaigns with high accuracy.

  • Problem

    Detecting long-term APT behavior remains challenging because streaming graph analysis requires similarity modeling for changing, non-fixed-length provenance data and evolutionary system behavior.

  • Method

    UNICORN uses compact fixed-size provenance graph sketches and temporally ordered evolutionary models to analyze streaming system behavior.

  • Results

    Precision and accuracy improve by 24% and 30%, respectively, over previous work, while UNICORN detects real-life APT campaigns with high accuracy and low false alarm rates.

  • Takeaways & Limitations

    The evaluation supports provenance-based evolutionary modeling as a practical approach for detecting diverse APT attacks across audit systems.

  • Takeaways & Limitations

    When normal system behavior changes, UNICORN may raise false positives because it does not dynamically adjust its model, despite concept-drift mitigation.

Abstract

from arXiv · show

Advanced Persistent Threats (APTs) are difficult to detect due to their "low-and-slow" attack patterns and frequent use of zero-day exploits. We present UNICORN, an anomaly-based APT detector that effectively leverages data provenance analysis. From modeling to detection, UNICORN tailors its design specifically for the unique characteristics of APTs. Through extensive yet time-efficient graph analysis, UNICORN explores provenance graphs that provide rich contextual and historical information to identify stealthy anomalous activities without pre-defined attack signatures. Using a graph sketching technique, it summarizes long-running system execution with space efficiency to combat slow-acting attacks that take place over a long time span. UNICORN further improves its detection capability using a novel modeling approach to understand long-term behavior as the system evolves. Our evaluation shows that UNICORN outperforms an existing state-of-the-art APT detection system and detects real-life APT scenarios with high accuracy.

I. INTRODUCTION · II. BACKGROUND · A. Challenges of Syscall Traces

UNICORN addresses the long-term, stealthy behavior of APTs with a provenance-based anomaly detector that compactly analyzes longitudinal execution history. The paper motivates this design by limitations of signature, syscall-trace, and prior provenance approaches, including weak historical context, evasion, overhead, and reliance on predefined attack knowledge.

  • I. INTRODUCTION: APT campaigns seek prolonged undetected control of systems, often using zero-day exploits and low-and-slow attack patterns.Their extended timescale distinguishes them from conventional attacks.
  • I. INTRODUCTION: Signature-based detectors miss new vulnerabilities, while anomaly systems struggle to model long-term behavior and can be evaded through short-sequence inspection.Some systems limit analysis to event co-occurrence to avoid computational and memory overheads.
  • I. INTRODUCTION: Data provenance represents execution as a DAG linking causally related subjects and objects even when events are separated by long periods.This makes provenance a promising data source for APT detection.
  • I. INTRODUCTION: Provenance-based APT analysis remains difficult because graphs grow continuously, contextual analysis requires large components, and edge-matching rules depend on prior attack knowledge.These constraints hinder scalable detection of new APT classes.
  • I. INTRODUCTION: UNICORN uses an incrementally updatable, fixed-size graph sketch to efficiently compute statistics and explore longitudinal provenance for stealthy intrusions.The sketch is a compact, time-weighted encoding that summarizes provenance over long periods.
  • I. INTRODUCTION: UNICORN tracks provenance history from boot to shutdown without storing the full graph, while freezing post-training models to prevent attacker-driven poisoning.Its fixed-size representation provides low computational and storage overheads.
  • II. BACKGROUND: Traditional IDS rely on syscall traces, but whole-system provenance is identified as a superior data source for APT detection.System calls are the operating-system service interface and a common entry point for attackers.
  • A. Challenges of Syscall Traces: Point-wise or short-sequence syscall analysis lacks historical context, producing false positives and enabling mimicry attacks; capture mechanisms also face bypass, runtime, and race-condition limitations.The cited mechanisms include library wrappers, ptrace, and in-kernel systems, with TOCTTOU, TOATTOU, and TORTTOU bugs reported.

B. Whole-System Provenance … IV. DESIGN

UNICORN addresses APT detection as real-time anomaly detection over complete, streaming whole-system provenance, combining contextual graph analysis, long-term behavior modeling, and fixed-size sketches. Its design assumes trustworthy provenance collection and detects deviations from learned normal execution across evolving system behavior.

  • B. Whole-System Provenance: Whole-system provenance captures system activities and interactions at the operating-system level, preserving long-distance causal relationships for contextualized APT analysis.OS-level systems provide strong security and completeness guarantees for information-flow capture.
  • C. Summary and Problem Statement: UNICORN’s prior-work analysis identifies four limitations: sensitive edge-matching rules, constrained graph exploration, unsuitable behavior models, and in-memory-only provenance analysis.These limitations hinder zero-day detection, contextual understanding, dynamic behavior modeling, and long-term scalability.
  • C. Summary and Problem Statement: UNICORN formulates system-wide intrusion detection as real-time graph-based anomaly detection on large, attributed, streaming whole-system provenance graphs.The complete graph from system boot to the current state is compared with known-good provenance graphs, and significant deviation indicates an attack.
  • C. Summary and Problem Statement: The detector continuously analyzes complete execution histories efficiently, avoids assumptions about attack behavior, and learns only normal system changes rather than attacker-directed changes.These requirements define the intended properties of an APT-focused provenance-based intrusion detector.
  • III. THREAT MODEL: UNICORN targets extended, multi-phase host intrusions and aims to detect them at any stage by interpreting provenance generated by the host.The threat model assumes an attacker gains illegitimate access and remains undetected for an extended period while using varied techniques.
  • III. THREAT MODEL: UNICORN assumes trusted kernel, provenance, and analysis components, with LSM integrity provided through an attested boot sequence for CamFlow.The same integrity assumptions apply to other data-collection frameworks.
  • IV. DESIGN: UNICORN accepts labeled streaming attributed edges from one or more hosts and represents them as a whole-system provenance DAG supporting efficient streaming and contextualized analysis.The design is presented with CamFlow but can obtain provenance from systems including LPM and Spade.
  • IV. DESIGN: UNICORN builds an in-memory histogram over the entire execution history, explores expanding graph neighborhoods for causal context, periodically discounts irrelevant history, hashes histograms into fixed-size sketches, and clusters them into an evolutionary normal model.The model captures behavioral changes across execution stages while identifying abnormal activity without attack knowledge.

A. Provenance Graph · B. Constructing Graph Histograms

UNICORN compares entire provenance graphs using causal structure to detect long-running, low-and-slow attacks while tolerating normal execution variation. It constructs streaming graph histograms from iterative R-hop neighborhood labels and applies exponential decay to adapt to concept drift.

  • A. Provenance Graph: Provenance graphs encode causal relationships between events, enabling reasoning across temporally distant activities characteristic of low-and-slow APTs.This contrasts with audit-log analysis that frequently relies on temporal relationships.
  • A. Provenance Graph: UNICORN compares two executions through similarity between their corresponding provenance graphs and always considers the entire graph for long-running attacks.The design avoids overly restrictive measures such as graph isomorphism because normal executions can produce slightly different graphs.
  • B. Constructing Graph Histograms: The graph-comparison representation must capture long-term causal relationships and operate on realtime streaming data to thwart intrusions during execution.These are the two stated criteria for the comparison algorithm.
  • B. Constructing Graph Histograms: UNICORN adapts a linear-time Weisfeiler-Lehman subtree graph kernel to construct discriminative graph representations.The method is based on the one-dimensional WL isomorphism test and its subtree-kernel variation.
  • B. Constructing Graph Histograms: It bins vertices by augmented labels describing each vertex’s R-hop incoming neighborhood, capturing surrounding graph structure and causal context.Labels include neighborhood edge information and vertex identities.
  • B. Constructing Graph Histograms: In streaming mode, UNICORN recomputes histograms only for newly arriving vertices and vertices whose incoming neighborhoods change.For versioned provenance entities or activities, each new edge requires updating only its destination vertex’s neighborhood under the stated arrival ordering.
  • B. Constructing Graph Histograms: UNICORN uses exponential weight decay to gradually forget outdated histogram data as streaming provenance exhibits concept drift.The decay rate is controlled by λ, preserving emphasis on recent execution while retaining fading memory of causally related past behavior.

C. Generating Graph Sketches · D. Learning Evolutionary Models

UNICORN maintains compact, fixed-size sketches of continuously updated provenance-graph histograms for efficient streaming analysis. It then models system evolution by clustering temporally ordered sketches into execution meta-states and tracking their runtime transitions, reducing false positives from long-term behavioral changes.

  • C. Generating Graph Sketches: UNICORN continuously updates graph histograms as new edges arrive, making similarity analysis challenging because histogram elements change continuously.Similarity should reflect the underlying distribution of graph features rather than a fixed, known set of elements.
  • C. Generating Graph Sketches: Enumerating all histogram elements can create sparse representations with prohibitive space and time complexity when graphs have many labels and neighborhood iterations.Manual feature engineering is an alternative, but it is presented as a way to reduce histogram size.
  • C. Generating Graph Sketches: UNICORN uses HistoSketch, based on locality-sensitive hashing and consistent weighted sampling, to maintain compact, fixed-size sketches for streaming histograms.HistoSketch runs in constant time, supporting real-time analysis of rapidly growing provenance data.
  • D. Learning Evolutionary Models: Conventional clustering misses evolutionary system behavior, which can cause excessive false positives in sufficiently long-term APT scenarios.UNICORN instead uses streaming capability to create evolutionary models that capture normal behavioral changes.
  • D. Learning Evolutionary Models: During training, UNICORN creates temporally ordered sketches, clusters each server’s sequence with K-medoids, and selects K using the silhouette coefficient.The resulting clusters represent execution meta-states such as startup, initialization, and steady-state behavior.
  • D. Learning Evolutionary Models: For each training instance, UNICORN builds a runtime model that captures changes in execution states and combines sub-models from the training provenance graphs.The model is analogous to an automaton tracking execution state transitions.
  • D. Learning Evolutionary Models: The evolution trace takes time-ordered sketches S(t), for t = 0, · · · , T, as input and produces an evolution list E.This algorithmic representation organizes the streaming provenance graph’s state progression over time.
  • D. Learning Evolutionary Models: Evolutionary modeling learns system behavior at many points in time while gradually forgetting older information to emphasize the most relevant activities.This lets UNICORN focus on current activities at any point during runtime.

E. Detecting Anomalies · V. IMPLEMENTATION · VI. EVALUATION

UNICORN detects anomalies by comparing periodically generated provenance-graph sketches against learned sub-models while tracking system state transitions from boot. Its GraphChi-based implementation supports memory-independent streaming analysis, and evaluation on approximately 1.5 TB of monitoring data—including real and simulated APT datasets—compares it with StreamSpot and assesses detection, efficiency, and design choices.

  • E. Detecting Anomalies: UNICORN periodically generates graph sketches from the streaming provenance graph and compares each sketch with all learned sub-models.Monitoring starts at system boot, with system state transitions tracked within each sub-model.
  • V. IMPLEMENTATION: UNICORN uses GraphChi for vertex-centric graph processing in C++, with data parsing and modeling implemented in Python.GraphChi enables efficient computation on large graphs without storing the entire provenance graph in memory.
  • V. IMPLEMENTATION: GraphChi’s Parallel Sliding Windows algorithm shards graphs by edge count and processes shards in parallel, allowing UNICORN to analyze whole provenance graphs independent of memory constraints.It supports fast disk updates with only a small number of non-sequential disk accesses.
  • V. IMPLEMENTATION: Streaming-graph computation, selective scheduling, partial ordering, and batched edge additions reduce I/O and computation during provenance analysis.Guaranteed partial ordering minimizes visited vertices even when the neighborhood hop parameter, R, is large.
  • VI. EVALUATION: UNICORN is compared with StreamSpot, and its higher detection accuracy is attributed to multi-hop graph exploration and evolutionary modeling suited to provenance-based APT detection.These factors correspond to the evaluation’s design and modeling questions.
  • VI. EVALUATION: UNICORN detects anomalies in three publicly available real-life DARPA APT datasets and demonstrates detection, processing speed, and CPU and memory efficiency on simulated supply-chain attacks.The simulated datasets, SC-1 and SC-2, use CamFlow in a controlled lab environment and include diverse normal and background activities.

A. UNICORN vs. State-of-the-Art

UNICORN is compared with StreamSpot on StreamSpot’s own dataset using matched and larger neighborhood analyses. Larger neighborhoods improve UNICORN’s precision and accuracy while reducing false positives, whereas StreamSpot cannot be evaluated on the paper’s larger APT datasets because of graph complexity and scalability limits.

  • Experimental setup: UNICORN is compared with StreamSpot on StreamSpot’s own dataset using sketch size |S| = 2000 and neighborhood sizes R = 1 and R = 3.R = 1 is equivalent to StreamSpot.
  • Experimental results: Larger-neighborhood analysis greatly reduces UNICORN’s false-positive rate, supporting the importance of contextual analysis.UNICORN raises false-positive alarms only on the Download dataset, the most diverse of StreamSpot’s benign datasets.
  • Limitations: StreamSpot cannot be evaluated on the real-life and simulated APT datasets because it cannot handle their many edge types or graph sizes.These limitations prevent a direct comparison between UNICORN and StreamSpot on those datasets.

B. DARPA TC Datasets · C. Supply Chain Attack Scenarios

UNICORN is evaluated on heterogeneous DARPA provenance datasets and controlled supply-chain attack scenarios, demonstrating generalization across capture systems and early attack detection. The supply-chain experiments also show lower performance than DARPA scenarios because attackers begin with prior knowledge and leave no preceding unusual behavior.

  • B. DARPA TC Datasets: DARPA datasets were collected over two weeks from hosts running Linux, Windows, and BSD during a Transparent Computing adversarial engagement.The engagement included attack execution, audit-data collection, and forensic analysis by separate teams.
  • B. DARPA TC Datasets: UNICORN was tested across provenance captured by CADETS on FreeBSD, ClearScope on Android, and THEIA on Ubuntu Linux.These systems capture provenance at different platform and instrumentation scopes.
  • B. DARPA TC Datasets: UNICORN generalizes to different provenance capture systems and graph structures, detecting attacks comprising less than 0.001% of audit-data volume.The results indicate accurate anomaly detection in long-running systems across various platforms.
  • B. DARPA TC Datasets: Unlike rule-based Holmes and Poirot models requiring prior expert knowledge, UNICORN uses unsupervised learning without expert input while achieving comparable attack-detection performance.The comparison is based on the number of detected attacks, with UNICORN detecting all attacks on FreeBSD and Li…
  • C. Supply Chain Attack Scenarios: The controlled supply-chain experiments simulated two three-day attacks, SC-1 and SC-2, against a Continuous Integration platform using CamFlow whole-system provenance capture.The traces included background activity during benign and attack scenarios, and virtualization plus automated scripts supported reproduction.
  • C. Supply Chain Attack Scenarios: UNICORN detected the supply-chain attacks with high accuracy and few false alarms, while its evolutionary model identified attacks during early system-state clusters.Evaluation used 5-fold cross validation with 125 benign graphs and 25 attack graphs per scenario.
  • C. Supply Chain Attack Scenarios: Evolutionary modeling reduces false positives by defining normal system behavior precisely yet flexibly as the system state changes.Static-snapshot clustering can produce many false positives that overwhelm administrators and contribute to threat fatigue.
  • C. Supply Chain Attack Scenarios: Supply-chain attacks are harder to detect than DARPA attacks because the attacker has prior target knowledge and can act without preceding unusual behavior.This absence of reconnaissance-like behavior partially explains UNICORN’s lower performance on the supply-chain datasets.

D. Influence of Graph Analysis on Detection Performance

UNICORN’s detection performance depends on how graph context and temporal evolution are represented in sketches. Sketch size and sketch-generation interval require balancing information fidelity against similarity, dimensionality, and attack visibility.

  • Graph-analysis parameters: Batch size does not affect UNICORN’s detection performance.It only controls how many edges are submitted to GraphChi at once.
  • Graph-analysis parameters: Larger hop counts capture more context, but irrelevant information can mask potential attacks.Hop count determines the neighborhood size used to characterize each vertex and the expressiveness of sketch features.
  • Graph-analysis parameters: Detection precision, recall, and accuracy improve with sketch size up to a point, after which the curse of dimensionality causes degradation.Larger sketches better represent the evolving graph and reduce normalized min-max similarity approximation error before clustering becomes adversely affected.
  • Graph-analysis parameters: SG = 500 edges per new sketch yields 0 recall, undefined precision, and undefined F-score, while an interval around 3,000 produces optimal SC-1 results.Both smaller and larger intervals can make adjacent or successive graphs too similar, respectively increasing false negatives or producing coarser-grained changes.
  • Graph-analysis parameters: A slow decay rate around 0.02 balances past and current graph components better than never-forget or always-forget settings.The never-forget setting is λ = 0.0, and the always-forget setting is λ = 1.0; both yield unsatisfactory results.

E. Processing Speed · F. CPU & Memory Utilization

UNICORN maintains real-time processing with runtime largely insensitive to its parameters, while its heavy-workload resource costs remain modest: average CPU utilization stabilizes around 12.3% on one CPU, and memory usage is primarily driven by neighborhood hops and sketch generation.

  • E. Processing Speed: E. Processing Speed — Increasing batch size improves runtime performance, with BS 6,000 selected because it approximates CamFlow and larger values providing only marginal improvement.Runtime performance improves as batch size increases, but gains above 6,000 are marginal.
  • E. Processing Speed: E. Processing Speed — Sketch size minimally affects runtime after initialization, because UNICORN uses fast, incremental sketch updates.Larger sketches require more computation only at the beginning of the experiment.
  • E. Processing Speed: E. Processing Speed — Sketch-generation interval and weighted decay factor do not affect runtime performance.The weighted decay factor is omitted from the figure.
  • E. Processing Speed: E. Processing Speed — UNICORN’s runtime is relatively insensitive to these parameters, enabling real-time intrusion detection with settings optimized for detection accuracy.The processing-speed analysis illustrates a tradeoff between accuracy and runtime performance.
  • F. CPU & Memory Utilization: F. CPU & Memory Utilization — 12.3% average CPU utilization stabilizes on a single CPU during a long-running, heavy-workload experiment, and the evaluated parameters do not significantly change it.The workload involves continuous integration performing kernel compilation.
  • F. CPU & Memory Utilization: F. CPU & Memory Utilization — Direct comparison with commercial and research IDS is difficult because available benchmarks or reported metrics do not support meaningful comparison.The paper leaves the design of meaningful IDS performance benchmarks to future work.
  • F. CPU & Memory Utilization: F. CPU & Memory Utilization — Memory consumption is primarily determined by the graph histogram and random variables sampled for sketch generation, with neighborhood hops increasing histogram memory requirements.Other parameters in the basic configurations do not significantly influence memory consumption; the histogram size depends on unique labels determined by each vertex’s explored neighborhood.

VII. DISCUSSION & LIMITATIONS · VIII. RELATED WORK

UNICORN’s anomaly-based provenance approach inherits limitations involving modeling assumptions, evolving or heterogeneous behavior, tuning, and comparison scope. Relative to prior syscall-, graph-, and rule-based systems, it models contextual execution relationships without predefined APT knowledge.

  • VII. DISCUSSION & LIMITATIONS: UNICORN assumes a safe modeling period and that most finite system behavior patterns are observed; genuinely normal unseen behavior can trigger false alarms requiring human intervention.These assumptions are shared with other anomaly-based intrusion detection systems.
  • VII. DISCUSSION & LIMITATIONS: Mimicry attacks may target learned models, but imitating provenance graphs or graph sketches is harder than imitating syscall sequences because of their complex structural information.The passage also notes that randomized consistent weighted sampling makes sketch generation harder to predict.
  • VII. DISCUSSION & LIMITATIONS: UNICORN requires sufficient benign traces and aligned model and monitoring starting states; snapshot restoration can cause false alarms unless model state is restored correspondingly.Closer integration could save and restore UNICORN’s model state alongside system snapshots.
  • VII. DISCUSSION & LIMITATIONS: Changing normal behavior can produce false positives because UNICORN does not dynamically adjust its model, although quick updates are possible when new training data is malware-free.Graph-analysis parameters also require system-specific tuning, and heterogeneous hosts are less suitable than environments with well-defined activities.
  • VII. DISCUSSION & LIMITATIONS: Comparisons with existing IDS are difficult because many are closed-source, datasets may be outdated or require difficult provenance translations, and private datasets are superficially described.The passage frames larger cross-evaluation as constrained by these factors.
  • VIII. RELATED WORK: Traditional syscall-based HID evolved from fixed- and variable-length patterns toward stateful models, but UNICORN argues these approaches are poorly suited to APT attacks.UNICORN instead represents and analyzes provenance graphs to describe complex data-object relationships without costly control-flow construction or state-transition automata.
  • VIII. RELATED WORK: Prior graph-anomaly methods target graph similarity, network flows, software behavior, dynamic web graphs, social networks, or homogeneous streams, limiting direct applicability to large provenance graphs.Classy’s evaluation was limited to graphs with no more than 3,000 vertices, while real system execution yields graphs orders of magnitude larger.
  • VIII. RELATED WORK: Unlike rule-based provenance and EDR systems requiring expert knowledge of APT patterns, UNICORN performs anomaly detection without prior expert knowledge of APT attack patterns and behaviors.StreamSpot uses locally constrained features and single training snapshots, whereas UNICORN’s features embody execution context; other provenance systems emphasize forensic analysis or attack reconstruction.

IX. CONCLUSION

UNICORN is a realtime anomaly detection system that uses whole-system data provenance to detect advanced persistent threats. It models behavior with structured provenance graphs, efficiently summarizes streaming graphs, and uses evolutionary models to detect APT attacks across different audit systems.

  • UNICORN detects advanced persistent threats using realtime anomaly detection and whole-system data provenance.It targets threats considered difficult for traditional detection systems.
  • Structured provenance graphs expose causality relationships between system objects while representing whole-system behavior.UNICORN accounts for the entirety of each graph through efficient summarization as data streams into its analytic pipeline.
  • Evolutionary models successfully detect various APT attacks captured from different audit systems, including real-life scenarios.

APPENDIX · B. HistoSketch

This appendix defines HistoSketch’s locality-sensitive hashing foundation, sketch construction, and incremental update process for efficient graph-similarity computation and real-time detection. It also explains how sketch size balances information loss against computational efficiency and how decay incorporates newly arriving data.

  • B. HistoSketch: HistoSketch uses locality-sensitive hashing to project high-dimensional graph histograms into a low-dimensional space while preserving similarity.LSH is defined as a distribution over hash functions whose behavior depends on a similarity function sim(m, n).
  • B. HistoSketch: HistoSketch measures similarity between histogram vectors using normalized min-max similarity.The superscripts a and b identify the compared histograms.
  • B. HistoSketch: HistoSketch generates fixed-size sketches from positive real-valued histograms using a variation of consistent weighted sampling.The sketch size |S| controls the tradeoff between information loss and computation efficiency for real-time detection.
  • B. HistoSketch: Each sketch element is selected as the histogram element whose hashed value is minimal in the corresponding matrix column.The construction uses random variables for each h ∈ϵ, with r, c, and β fixed for each sketch element.
  • B. HistoSketch: The graph-sketch creation algorithm takes histogram L and parameters r, c, and β as input and outputs sketch S with corresponding hash values A.This summarizes Algorithm 3’s specified inputs and outputs.
  • B. HistoSketch: HistoSketch incrementally updates its sketch as new data arrives using the weighted histogram, previous sketch and hash values, new item x_t+1, and decay factor λ.At time t + 1, the process produces S(t + 1) and A(t + 1), incorporating exponential decay.

C. Metrics

The section defines the classification outcomes used for evaluation and describes precision, recall, and F-score as relevance and combined-performance measures. Precision and recall are evenly weighted in the F-score calculation.

  • False positives, false negatives, true positives, and true negatives are denoted by fp, fn, tp, and tn, respectively.
  • Precision measures classification exactness, whereas recall measures completeness.
  • F-score combines precision and recall through their harmonic mean, with both measures evenly weighted.
Loading 2001.01525v2…