Runtime Analysis of Whole-System Provenance

Thomas Pasquier, Xueyuan Han, Thomas Moyer, Adam Bates, Olivier Hermant, David Eyers, Jean Bacon, and Margo Seltzer.
25th ACM Conference on Computer and Communications Security (CCS'18).
Toronto, Ontario, Canada. October 15, 2018.
(acceptance rate=16.6%)
Available Media


Investigating the root causes and impacts of system intrusions represents a foundational challenge in computer security. Recently, provenance-based auditing techniques have been demonstrated to be of tremendous value in forensic analysis. Digital provenance provides a detailed history of the flow of information within a computing system, allowing investigators to easily attribute suspicious events to their root causes. However, existing provenance systems assume that analysis takes place retrospectively, limiting the value of provenance to realtime security applications; moreover, even for forensic tasks, provenance has been shown to exhibit poor performance and scalability, jeopardizing the timeliness of query responses.

In this work, we propose that these obstacles should be addressed through inlining the analysis of provenance with its capture within the operating system. We introduce ProvRT, the first general framework for realtime analysis of whole-system provenance. ProvRT is a Linux Security Module that offers support for both userspace and in-kernel execution of analysis applications We demonstrate the applicability of ProvRT to a variety of runtime security applications including data loss prevention, intrusion detection, and regulatory compliance. In evaluation, we demonstrate that ProvRT reduces the latency of realtime query mechanisms at least 89% while imposing minimal overheads on system execution. ProvRT thus enables the further deployment of provenance-based technologies to address central challenges in computer security.