PaperlayerView exact revision on arXiv

Source-linked AI summary

Kairos: Practical Intrusion Detection and Investigation using Whole-system Provenance

Zijun Cheng, Qiujian Lv, Jinyuan Liang, Yan Wang, Degang Sun, Thomas Pasquier, Xueyuan Han

arXiv:2308.05034v3cs.CRcs.LG

TL;DR

Existing PIDSes struggle to detect cross-application, novel, runtime attacks and reconstruct them concisely from large provenance graphs. KAIROS uses temporal-spatial graph learning and anomalous-edge analysis to generate compact attack summaries, outperforming prior systems with low overhead, though concept drift and evaluation limitations remain.

  • Problem

    Existing PIDSes do not simultaneously provide whole-system scope, attack agnosticity, runtime timeliness, and concise attack reconstruction for sophisticated intrusions.

  • Method

    KAIROS trains a graph-learning encoder-decoder on benign provenance graphs, scores streaming edges for anomalousness, and correlates anomalous edges into compact summary graphs.

  • Results

    KAIROS outperforms state-of-the-art PIDSes while incurring low overhead and accurately reconstructing attack footprints with fewer edges for sysadmins to inspect.

  • Takeaways & Limitations

    KAIROS provides system-wide, runtime anomaly detection and succinct attack graphs without prior attack knowledge.

  • Takeaways & Limitations

    KAIROS can report false positives when new benign applications introduce behavior absent from its training data, a form of concept drift.

Abstract

from arXiv · show

Provenance graphs are structured audit logs that describe the history of a system's execution. Recent studies have explored a variety of techniques to analyze provenance graphs for automated host intrusion detection, focusing particularly on advanced persistent threats. Sifting through their design documents, we identify four common dimensions that drive the development of provenance-based intrusion detection systems (PIDSes): scope (can PIDSes detect modern attacks that infiltrate across application boundaries?), attack agnosticity (can PIDSes detect novel attacks without a priori knowledge of attack characteristics?), timeliness (can PIDSes efficiently monitor host systems as they run?), and attack reconstruction (can PIDSes distill attack activity from large provenance graphs so that sysadmins can easily understand and quickly respond to system intrusion?). We present KAIROS, the first PIDS that simultaneously satisfies the desiderata in all four dimensions, whereas existing approaches sacrifice at least one and struggle to achieve comparable detection performance. Kairos leverages a novel graph neural network-based encoder-decoder architecture that learns the temporal evolution of a provenance graph's structural changes to quantify the degree of anomalousness for each system event. Then, based on this fine-grained information, Kairos reconstructs attack footprints, generating compact summary graphs that accurately describe malicious activity over a stream of system audit logs. Using state-of-the-art benchmark datasets, we demonstrate that Kairos outperforms previous approaches.

1. Introduction

Provenance-based intrusion detection systems must balance scope, attack agnosticity, timeliness, and attack reconstruction, but existing systems do not satisfy all four simultaneously. KAIROS combines temporal-spatial graph learning with runtime attack reconstruction to address these gaps.

  • Provenance graphs represent system-execution history as interactions between kernel objects, including processes, files, and sockets.
  • Existing PIDSes fail to satisfy scope, attack agnosticity, timeliness, and attack reconstruction simultaneously.Systems meeting the first three provide limited attack explanations, while reconstruction-oriented systems may be application-specific, signature-dependent, or offline.
  • KAIROS learns temporal-spatial graph behavior and scores each streaming system event by anomalousness against benign historical patterns.Its edge-level analysis accounts for temporal changes and surrounding node structure.
  • KAIROS correlates highly anomalous edges through information flow to construct compact summary graphs that describe attack scenarios without prior attack knowledge.
  • KAIROS achieves high detection accuracy on DARPA and comparison datasets, outperforming Unicorn and ThreaTrace while using low computational and memory overhead.It also reduces the number of graph edges sysadmins must inspect during attack investigation.

2. Background & Motivation

System-level provenance provides whole-system visibility into interactions among kernel objects, which is important for attacks spanning applications and hosts. The motivating APT scenario exposes why prior systems struggle with novel, sparse, timely, and interpretable attack activity, while KAIROS reconstructs the attack at runtime from anomalous edges.

  • System-level Data Provenance: System-level provenance records data flows among kernel objects as directed graphs whose nodes are objects and whose edges are dependency relationships.Kernel event logging and specialized reference monitors can capture these fine-grained interactions.
  • System-level Data Provenance: KAIROS analyzes whole-system provenance across applications and hosts, matching APTs that move across applications and infected machines.
  • Challenges: APTs can hide among benign activity: approximately 3,119 attack-related entries represented only 0.01% of 32.4 million log entries in the motivating scenario.
  • Challenges: Anomaly-based systems such as Unicorn and ThreaTrace may identify deviations without attack knowledge but leave sysadmins tracing thousands of provenance edges to reconstruct the attack.
  • Challenges: Signature-based systems can expedite understanding after a match, but Poirot’s minutes-long graph searches are unsuitable for runtime detection.
  • KAIROS’ Result: KAIROS detects and reconstructs the APT at runtime without prior attack knowledge, despite malicious activity blending into much larger benign logs.
  • KAIROS’ Result: KAIROS incrementally builds a compact attack graph from highly anomalous edges as the attack unfolds, contrasting with an original graph containing 32.4 million edges and 690K nodes.

3. Threat Model

KAIROS targets attackers seeking control and persistence through software exploitation and backdoors, assuming trustworthy, sufficiently observed benign training data. Its threat model excludes hardware, side-channel, covert-channel, kernel-level, and audit-integrity attacks, while concept drift remains outside the formal model.

  • The threat model covers attackers attempting to control systems and maintain persistence through software vulnerabilities or communication backdoors.
  • KAIROS assumes its benign training period is not attacker-influenced and thoroughly observes system activity during learning.
  • Hardware-level, side-channel, and covert-channel attacks are excluded because kernel-level audit systems typically do not explicitly capture their behavior.
  • The model excludes kernel-level attacks and assumes existing hardening protects the operating system and audit framework.
  • KAIROS assumes provenance output remains integral, relying on secure provenance or tamper-evident logging techniques to detect malicious interference.

4. KAIROS Framework

KAIROS combines streaming provenance construction, graph learning, anomaly detection, and community-based investigation into one framework. It learns benign structural and temporal behavior, detects anomalous events, and produces compact graphs that summarize attack activity.

  • Graph Construction and Learning: KAIROS analyzes provenance graphs in a streaming fashion and uses an encoder-decoder architecture to reconstruct each newly arriving edge.The encoder uses neighborhood structure and node states, while the decoder reconstructs the edge from its embedding.
  • Anomaly Detection: KAIROS groups overlapping anomalous time windows into queues, updates queue anomaly scores at run time, and triggers alerts when scores exceed a validation-set threshold.This organizes anomalous activity across time rather than evaluating isolated events alone.
  • Graph Construction and Representation: KAIROS represents audit events as directed, time-stamped edges between kernel-object nodes and encodes node attributes with hierarchical feature hashing.The hashing preserves hierarchical similarity, such as similarity between files sharing a parent directory.
  • Graph Learning: KAIROS trains its graph encoder and decoder on benign provenance graphs and assigns high reconstruction errors to events that deviate from learned structural and temporal behavior.The graph neural network produces edge embeddings from graph state, edge information, and timestamps; reconstruction error is computed from the predicted and observed edge types.
  • Anomaly Detection: KAIROS identifies suspicious nodes from anomalous edges and uses node rareness, measured with inverse document frequency, to support anomaly detection.A node is anomalous when it participates in an edge whose reconstruction error exceeds the time-window threshold; nodes absent from prior windows receive maximum IDF.
  • Anomaly Investigation: KAIROS applies community detection to anomalous edges and simplifies the resulting communities into compact summary graphs that expose attack footprints without prior attack knowledge.The summaries reduce the graph that sysadmins must inspect, although anomaly-based detection can also produce abnormal-but-benign candidate graphs.

5. Evaluation

KAIROS is evaluated on diverse provenance datasets, including controlled attacks, DARPA APT campaigns, and comparisons with existing PIDSes. Results show strong detection and reconstruction, while exposing concept-drift, retraining, and benchmarking limitations.

  • Datasets: Eight public datasets capture whole-system provenance across Linux, FreeBSD, and Android, with benign and attack activity.The evaluation uses datasets from Manzoor et al. and DARPA, including large-scale APT data.
  • Datasets: The Manzoor et al. dataset supports comparison with Unicorn and ThreaTrace but lacks fine-grained attack ground truth for reconstruction evaluation.Its attack scenario is a drive-by download exploiting a Flash vulnerability, while the exact attack procedure is not public.
  • Detection performance: 100% recall is reported across all attacks, although false positives arise when compromised entities remain active or when unseen benign applications appear during testing.The latter case is identified as concept drift; screencap behavior in E5-ClearScope was absent from training data.
  • Detection performance: Incremental retraining lets KAIROS learn from false-positive windows and address recurring concept drift, but regular updates may expose the model to poisoning.The authors leave thorough exploration and evaluation of poisoning defenses to future work.
  • Comparison study: Comparisons with prior PIDSes are constrained by differences between signature- and anomaly-based systems, unavailable datasets, proprietary components, runtime issues, and inconsistent metrics.The authors exclude signature-based systems and leave broader PIDS benchmarking to future work.
  • Comparison study: KAIROS matches or outperforms Unicorn and ThreaTrace, while graph-level evaluation can obscure incomplete identification of attack activity.ThreaTrace comparison is favorable despite its broader labeling of neighboring nodes; it also produced over 63K false-positive nodes in E5-THEIA.

5.4. Hyperparameter Impact on Performance

KAIROS’s hyperparameters trade off detection quality, memory, and processing time, with streaming execution keeping runtime overhead low. Its compact summary graphs support practical attack investigation alongside detection.

  • Evaluation setup: KAIROS varies each hyperparameter independently and reports effects on detection and runtime, using E3-THEIA for detailed results.Results for all TC datasets appear in the appendix.
  • Hyperparameter effects: A node embedding dimension of 16 is ideal across datasets because larger dimensions create sparse features and memory overhead, while smaller ones increase hash collisions.The embedding encodes initial node features.
  • Hyperparameter effects: A node state dimension that is too small loses past-event information, whereas an oversized state retains outdated history and increases memory overhead.Node states capture the temporal evolution of neighborhood structure.
  • Hyperparameter effects: A neighborhood sampling size of 20 is ideal across datasets; larger neighborhoods stop improving detection and add non-proportional memory overhead.Neighborhoods encode a node’s structural role.
  • Hyperparameter effects: A 15-minute time window is ideal across datasets because shorter windows weaken context, while longer windows slightly increase memory overhead.KAIROS processes the provenance graph in a streaming fashion rather than retaining the entire graph.
  • End-to-end performance: CPU utilization remains below 1% across E3-THEIA experiments, and the time-window approach supports runtime monitoring.KAIROS raises alerts when anomalous time-window queues are detected.
  • Attack reconstruction: KAIROS’s attack reconstruction produces compact summary graphs that closely match ground truth, while benign graphs are small and easy for sysadmins to disregard.The reconstruction can still miss communications that resemble ordinary Firefox network activity.
  • End-to-end performance: KAIROS processes 15-minute windows containing about 2.5M edges in at most 228.8 seconds, while median 57K-edge windows take 11.6 seconds.It processes about 11K edges per second, slightly slower than StreamSpot’s approximately 14K, but with higher detection accuracy.

6. Discussion

The discussion examines robustness to poisoned training data and evasion, while also identifying broader limitations in evaluating provenance-based intrusion detectors. KAIROS detected a camouflaged attack but reconstructed only part of its activity in one evaluation.

  • Data Poisoning: Data poisoning can cause future attacks to remain undetected when malicious activity enters anomaly-detector training data, posing a threat to anomaly-based PIDSes.The discussion notes that robust poisoning evaluations are limited among prior systems.
  • Evasion: KAIROS detected a camouflaged E3-THEIA attack, but its summary graph reported only a small subset of the activity in the original ground truth.The authors found that the published evasion dataset contained only behavior KAIROS had identified, rather than the complete original traces.
  • Limitations of Evaluation: PIDS evaluation is constrained by the lack of open-source implementations and limited publicly accessible data.These issues are identified as general limitations of benchmarking PIDSes.

7. Related Work

Prior provenance-based intrusion detectors trade off attack agnosticity, whole-system scalability, attack reconstruction, or offline operation. KAIROS is presented as addressing these limitations together while maintaining comparable or better detection and computational performance.

  • Provenance-based Intrusion Detection: Signature-based PIDSes match known attack behavior but are not attack agnostic and therefore struggle with unknown attacks.Their detection depends on manually crafted graph-matching rules or other prior attack knowledge.
  • Provenance-based Intrusion Detection: Anomaly-based approaches avoid requiring prior APT characteristics but may fail to scale to whole systems, reconstruct attack stories, or operate online.The discussion presents these as recurring limitations across prior systems.
  • KAIROS: KAIROS is presented as overcoming these limitations simultaneously while achieving similar or better detection and computational performance.The paper frames this as reconciling scope, attack agnosticity, timeliness, and attack reconstruction.

8. Conclusion

KAIROS detects system-wide anomalies and generates succinct attack graphs without prior attack knowledge, while monitoring long-running systems at run time with minimal performance overhead.

  • KAIROS detects system-wide anomalies and generates succinct attack graphs without prior attack knowledge.
  • KAIROS effectively monitors long-running systems at run time and outperforms the state of the art.
  • KAIROS incurs minimal performance overhead during runtime monitoring.

Appendix A. DARPA Dataset Details

The DARPA datasets are prepared for training, validation, and detection using noise reduction and an allow-list of trusted data objects excluded from causal analysis.

  • Table 11 summarizes the attack scenarios in the DARPA datasets.The scenarios are described in detail in a separate document.
  • Table 12 summarizes the DARPA data used for training, validation, and detection.
  • Noise reduction and an allow-list of trusted data objects are used before causal analysis.Trusted data objects are removed from the causal analysis.

Appendix B. Hyperparameter Impact on Performance

The appendix evaluates how hyperparameter values affect KAIROS’s detection performance, resource overhead, and execution time across all DARPA datasets.

  • AUC results are reported for all DARPA datasets with varying hyperparameter values.
  • Memory and computational overhead are reported for all DARPA datasets with varying hyperparameter values.
  • Average time-window execution time is reported for all DARPA datasets with varying hyperparameter values.

Appendix C. Attack Reconstruction Examples

The appendix presents attack-reconstruction examples from DARPA datasets alongside figures evaluating detection and resource behavior under varying hyperparameters.

  • E3-CADETS: KAIROS’s E3-CADETS summary graph captures an attacker obtaining a shell through a vulnerable Nginx server and downloading a malicious payload.The payload is downloaded to /tmp/vUgefal; an attempted process injection fails.
  • DARPA datasets: The DARPA evaluation uses attack scenarios and data splits for training, validation, and testing, with attack days containing both benign and attack windows.
  • Hyperparameter impact: AUC, memory usage, CPU utilization, and execution time are evaluated across DARPA datasets with varying hyperparameter values.The corresponding figures report these detection and overhead measures.
  • E5-ClearScope: The E5-ClearScope scenario includes malicious app installation, attacker control, privilege escalation, data exfiltration, and a screenshot.Corrupted provenance data led the authors to omit some malicious activity from the summary graph.
  • OpTC Day 1: The OpTC Day 1 scenario includes credential collection, network scanning, lateral movement, and information collection through PowerShell scripts.

Appendix D. Benign Summary Graph Examples

The appendix presents benign summary graphs from three DARPA datasets and explains how sysadmins can assess whether associated activity warrants investigation.

  • The examples cover benign summary graphs from DARPA’s E3-CADETS, E5-ClearScope, and OpTC datasets.
  • E3-CADETS: For E3-CADETS, wget activity may require checking connected IPs against blocklists and confirming downloaded files with the user.Unrecognized files might have been downloaded by an attacker through a C&C server.
  • E5-ClearScope: For E5-ClearScope, sysadmins should confirm installed APK identities and inspect APKs for legitimate vendors.
  • OpTC: For OpTC, Installagent requires investigation when suspicious files, such as files outside the system path, appear in its activity.Installagent is associated with Microsoft Windows Store updates and uses System, backgroundTaskHost, and svchost.
Loading 2308.05034v3…