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

arXiv: https://arxiv.org/abs/2308.05034 · HTML: https://mlsanity.com/paper/2308.05034/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 83 references that are in the map.
- First posted on arXiv 9 Aug 2023.

## Builds on (most cited first, 26 of 26)

- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Representation Learning for Dynamic Graphs: A Survey](https://mlsanity.com/paper/1905.11485/) (2019)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [GNNGuard: Defending Graph Neural Networks against Adversarial Attacks](https://mlsanity.com/paper/2006.08149/) (2020)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Dos and Don'ts of Machine Learning in Computer Security](https://mlsanity.com/paper/2010.09470/) (2020)
- [Attacking Graph-based Classification via Manipulating the Graph Structure](https://mlsanity.com/paper/1903.00553/) (2019)
- [UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats](https://mlsanity.com/paper/2001.01525/) (2020)
- [HOLMES: Real-time APT Detection through Correlation of Suspicious Information Flows](https://mlsanity.com/paper/1810.01594/) (2018)
- [Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs](https://mlsanity.com/paper/1602.04844/) (2016)
- [SLEUTH: Real-time Attack Scenario Reconstruction from COTS Audit Data](https://mlsanity.com/paper/1801.02062/) (2018)
- [POIROT: Aligning Attack Behavior with Kernel Audit Records for Cyber Threat Hunting](https://mlsanity.com/paper/1910.00056/) (2019)
- [Dynamic Malware Analysis with Feature Engineering and Feature Learning](https://mlsanity.com/paper/1907.07352/) (2019)
- [threaTrace: Detecting and Tracing Host-based Threats in Node Level Through Provenance Graph Learning](https://mlsanity.com/paper/2111.04333/) (2021)
- [Practical Whole-System Provenance Capture](https://mlsanity.com/paper/1711.05296/) (2017)
- [DeepAID: Interpreting and Improving Deep Learning-based Anomaly Detection in Security Applications](https://mlsanity.com/paper/2109.11495/) (2021)
- [Explainability in Graph Neural Networks: An Experimental Survey](https://mlsanity.com/paper/2203.09258/) (2022)
- [A baseline for unsupervised advanced persistent threat detection in system-level provenance](https://mlsanity.com/paper/1906.06940/) (2019)
- [SIGL: Securing Software Installations Through Deep Graph Learning](https://mlsanity.com/paper/2008.11533/) (2020)
- [Runtime Analysis of Whole-System Provenance](https://mlsanity.com/paper/1808.06049/) (2018)
- [FRAPpuccino: Fault-detection through Runtime Analysis of Provenance](https://mlsanity.com/paper/1711.11487/) (2017)

## Built on by (most cited first, 30 of 31)

- [Agent-Sentry: Bounding LLM Agents via Execution Provenance](https://mlsanity.com/paper/2603.22868/) (2026)
- [OCR-APT: Reconstructing APT Stories from Audit Logs using Subgraph Anomaly Detection and LLMs](https://mlsanity.com/paper/2510.15188/) (2025)
- [Towards Security-Auditable LLM Agents: A Unified Graph Representation](https://mlsanity.com/paper/2605.06812/) (2026)
- [OMNISEC: LLM-Driven Provenance-based Intrusion Detection via Retrieval-Augmented Behavior Prompting](https://mlsanity.com/paper/2503.03108/) (2025)
- [DiagChain: A Diagnostic Benchmark for Evaluating LLM Agents on Evidence-Grounded Attack Chain Reconstruction](https://mlsanity.com/paper/2608.03591/) (2026)
- [Deep Learning-based Intrusion Detection Systems: A Survey](https://mlsanity.com/paper/2504.07839/) (2025)
- [Benchmarking and Exploring the Capabilities of LLMs for Attack Investigations](https://mlsanity.com/paper/2606.10281/) (2026)
- [Carbon Filter: Real-time Alert Triage Using Large Scale Clustering and Fast Search](https://mlsanity.com/paper/2405.04691/) (2024)
- [PROVCREATOR: Synthesizing Complex Heterogenous Graphs with Node and Edge Attributes](https://mlsanity.com/paper/2507.20967/) (2025)
- [PIDSMaker: Building and Evaluating Provenance-based Intrusion Detection Systems](https://mlsanity.com/paper/2601.22983/) (2026)
- [HIDBench: Benchmarking Large Language Models for Host-Based Intrusion Detection](https://mlsanity.com/paper/2605.21773/) (2026)
- [ChainWatch: A Kill Chain-Aligned Sequential Detection Framework for Multi-Step Attacks in MCP-Based AI Agent Systems](https://mlsanity.com/paper/2607.19432/) (2026)
- [RAPID: Robust APT Detection and Investigation Using Context-Aware Deep Learning](https://mlsanity.com/paper/2406.05362/) (2024)
- [CONTINUUM: Detecting APT Attacks through Spatial-Temporal Graph Neural Networks](https://mlsanity.com/paper/2501.02981/) (2025)
- [Modeling Behavioral Preferences of Cyber Adversaries Using Inverse Reinforcement Learning](https://mlsanity.com/paper/2505.03817/) (2025)
- [PROVEX: Enhancing SOC Analyst Trust with Explainable Provenance-Based IDS](https://mlsanity.com/paper/2512.18199/) (2025)
- [An End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation](https://mlsanity.com/paper/2603.17100/) (2026)
- [GRASP -- Graph-Based Anomaly Detection Through Self-Supervised Classification](https://mlsanity.com/paper/2605.07812/) (2026)
- [TGCM: Topic-Guided Consistency Modeling for One-Step Disentanglement of Interleaved APT Technique Sequences](https://mlsanity.com/paper/2606.18651/) (2026)
- [Cross-Agent Campaign Attribution: Linking Asynchronous Attacks Across LLM Agents](https://mlsanity.com/paper/2607.18826/) (2026)
- [Beyond Heavy Log Curation: Perplexity-Based APT Detection via Unsupervised, Context-Augmented Language Models](https://mlsanity.com/paper/2607.20832/) (2026)
- [How Benchmarks and Evaluation Protocols Shape Conclusions in Provenance-Based Intrusion Detection](https://mlsanity.com/paper/2608.01454/) (2026)
- [Magnet: Detecting Cross-Session AI Misuse Through Capability Accumulation](https://mlsanity.com/paper/2608.02518/) (2026)
- [SysEvolve: An AI-native, safe, autonomous adversarial attack-defense co-evolutionary system](https://mlsanity.com/paper/2608.15012/) (2026)
- [A Graph-Based Approach for Mapping Kernel-Level Telemetry to MITRE ATT&CK](https://mlsanity.com/paper/2609.12841/) (2026)
- [Not All Relations Are Equal: Relation-Balanced and Calibrated Graph Learning for Provenance-Based Intrusion Detection](https://mlsanity.com/paper/2609.16462/) (2026)
- [On the Effectiveness of Kernel-Level Evidence for Agent Security](https://mlsanity.com/paper/2609.28915/) (2026)
- [CyberClear: A Benchmark for LLM Agent Systems on APT Attack Chain Provenance](https://mlsanity.com/paper/2609.32424/) (2026)
- [HESP: Separating What to Probe from When to Stop in Local LLM Alert-Triage Agents](https://mlsanity.com/paper/2609.33446/) (2026)
- [APTInvestBench: Evaluating Autonomous APT Investigation under Varying Telemetry](https://mlsanity.com/paper/2609.38954/) (2026)

## Abstract (arXiv)

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.