An End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation

Kushankur Ghosh; Mehar Klair; Kian Kyars; Euijin Choo; Jörg Sander

cs.CRMar 17, 2026

An End-to-End Framework for Functionality-Embedded Provenance Graph Construction and Threat Interpretation

Authors: Kushankur Ghosh, Mehar Klair, Kian Kyars, Euijin Choo, Jörg Sander

Organizations: University of Alberta

Abstract

Provenance graphs model causal system-level interactions from logs, enabling anomaly detectors to learn normal behavior and detect deviations as attacks. However, existing approaches rely on brittle, manually engineered rules to build provenance graphs, lack functional context for system entities, and provide limited support for analyst investigation. We present Auto-Prov, an adaptive, end-to-end framework that leverages large language models (LLMs) to automatically construct provenance graphs from heterogeneous and evolving logs, embed system-level functional attributes into the graph, enable provenance graph-based anomaly detectors to learn from these enriched graphs, and summarize the detected attacks to assist an analyst's investigation. Auto-Prov clusters unseen log types and efficiently extracts provenance edges and entity-level information via automatically generated rules. It further infers system-level functional context for both known and previously unseen system entities using a combination of LLM inference and behavior-based estimation. Attacks detected by provenance-graph-based anomaly detectors trained on Auto-Prov's graphs are then summarized into natural-language text. We evaluate Auto-Prov with four state-of-the-art provenance graph-based detectors across diverse logs. Results show that Auto-Prov consistently enhances detection performance, generalizes across heterogeneous log formats, and produces stable, interpretable attack summaries that remain robust under system evolution.

Figures & tables

Figure 1: Examples of Different Log Entries

Provenance Framework	Flash [ rehman2024flash ]				MAGIC [ jia2024magic ]				OCR-APT [ aly2025ocr ]				Kairos [ cheng2024kairos ]
Provenance Framework	Attack	AUC-ROC	AUC-PR	ADP	Attack	AUC-ROC	AUC-PR	ADP	Attack	AUC-ROC	AUC-PR	ADP	Attack	AUC-ROC	AUC-PR	ADP
( $\beta$ )	FBI	0.666	0.0000	0.5	FBI	0.593	0.027	0.507	FBI	0.47	0.0000	1.0	FBI	0.803	0.0027	0.666
	BED	0.671	0.0001		BED	0.79	0.0013		BED	0.65	0.0001		BED	0.806	0.0008
	Avg.	0.668	0.0000		Avg.	0. 691	0.014		Avg.	0.56	0.0000		Avg.	0.804	0.0014
Auto-Prov	FBI	0.901	0.001	1.0	FBI	0.81	0.015	1.0	FBI	0.962	0.0036	1.0	FBI	0.858	0.0053	0.666
	BED	0.853	0.001		BED	0.869	0.017		BED	0.826	0.006		BED	0.813	0.0001

Table 1: Detection results on the THEIA dataset [ darpa_tc_e3 ] .

Provenance Framework	Kairos [ cheng2024kairos ]				MAGIC [ jia2024magic ]
Provenance Framework	Attack	AUC-ROC	AUC-PR	ADP	Attack	AUC-ROC	AUC-PR	ADP
( $\beta$ )	MAD	0.498	0.024	0.997	MAD	0.5	0.046	0.385
	PONY	0.498	0.024		PONY	0.498	0.138
	SPAM	0.504	0.008		SPAM	0.503	0.044
	WEB	0.498	0.007		WEB	0.499	0.052
	Avg.	0.499	0.015		Avg.	0.5	0.07

Table 2: Detection results on ATLAS datasets [ alsaheel2021atlas ] .

Panel of Figure 3 — Figure 3: (a): Clustering performance of DBStream [ hahsler2016clustering ] across different log embedding models. (b): Clustering performance of DBStream [ hahsler2016clustering ] and DenStream [ cao2006density ] . (c) – (d): Detection performance on THEIA [ darpa_tc_e3 ] and ATLAS [ alsaheel2021atlas ] with different embedding models for node features, respectively. (e): Number of edges generated by different LLMs as the candidate provenance extractor .

Configuration	THEIA [ darpa_tc_e3 ] + OCR-APT [ aly2025ocr ]				ATLAS [ alsaheel2021atlas ] + Kairos [ cheng2024kairos ]
	FBI		BED		MAD		PONY		SPAM		WEB
	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR	AUC-ROC	AUC-PR
( $\beta$ ) + $\tau_{f}$	0.48	0.0000	0.344	0.0001	0.5	0.024	0.5	0.024	0.503	0.08	0.5	0.007
Auto-Prov - $\tau_{f}$	0.532	0.0007	0.7	0.0001	0.529	0.022	0.544	0.023	0.52	0.007	0.514	0.006
Auto-Prov	0.962	0.0036	0.826	0.006	0.683	0.037	0.622	0.031	0.625	0.01	0.606	0.009

Table 3: Detection performance comparison between Auto-Prov and its variants: (1) “(

\beta

) +

\tau_{f}

”: baseline provenance graphs with Auto-Prov’s functionality features; (2) “Auto-Prov -

\tau_{f}

”: Auto-Prov-generated provenance graphs with the baseline node features.

Panel of Figure 4 — Figure 4: (a) – (c): Detection performance with different LLMs as candidate provenance extractor , rule generator , and node enricher , respectively. (d): Number of entities for which functionality features cannot be inferred due to insufficient LLM knowledge. (e): Assistant robustness under entity-name poisoning, measured by tactic correctness $\alpha_{TC}$ , summary similarity $\alpha_{BERT}$ , and tactic consistency $\alpha_{R}$ , averaged over attacks in THEIA [ darpa_tc_e3 ] and ATLAS [ alsaheel2021atlas ] at varying poisoning rates.

Figure 5: Tactic correctness across attacks in THEIA [ darpa_tc_e3 ] and ATLAS [ alsaheel2021atlas ] .

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: An example of malvertising dominate attack graph from ATLAS [ alsaheel2021atlas ] .

Figure 7: An example of graph assistant’s output on the attack graph in Fig. 6 .

Data Provenance

Data provenance tracks where data and AI outputs come from, how they are transformed, and what evidence supports their attribution and use.

See all 188 papers

May 9, 2026

Detect, Localize, and Explain: Interactive Hierarchical Log Anomaly Analytics with LLM Augmentation

Logs are ubiquitous in modern systems. Unfortunately, their unstructured nature in flat sequences limits understanding of execution behaviors, hindering effective anomaly diagnosis. To address this, Krone introduces a novel hierarchical log abstraction that transforms flat log sequences into semantically coherent units across entity, action, and status levels. Building on this abstraction, Krone introduces a hierarchical orchestration framework that decomposes flat log sequences into hierarchical execution units and performs modular detection over them. It executes and optimizes the modular detection tasks across levels, enabling precise anomaly detection, localization, and explanation with selective invocation of LLM-based reasoning. In this work, we present Krone-viz, an interactive visualization system based on Krone, which makes hierarchical log analysis interpretable and actionable for software engineers and system operators. Demonstrated on the widely used HDFS benchmark dataset, Krone-viz supports: 1) examining hierarchical decompositions of flat log sequences, 2) inspecting detection results and abnormal segments identified by Krone with LLM-generated explanations, and 3) reusing, reviewing, and revising knowledge generated by LLMs with human-in-the-loop guardrails. The code of Krone-viz is available at https://github.com/LeiMa0324/KRONE_Demo_official, and we deploy a live demo at https://leima0324.github.io/KRONE_Demo_official.

Lei Ma, Suhani Chaudhary, Ethan Shanbaum +5

Worcester Polytechnic Institute, USA · UC Riverside, USA · University of Nevada, Las Vegas, USA

Online Anomaly Detection Interpretable Anomaly Detection Anomaly Localization Anomaly Detection

Ask PDF

Apr 22, 2026

Evaluating Assurance Cases as Text-Attributed Graphs for Structure and Provenance Analysis

An assurance case is a structured argument document that justifies claims about a system's requirements or properties, which are supported by evidence. In regulated domains, these are crucial for meeting compliance and safety requirements to industry standards. We propose a graph diagnostic framework for analysing the structure and provenance of assurance cases. We focus on two main tasks: (1) link prediction, to learn and identify connections between argument elements, and (2) graph classification, to differentiate between assurance cases created by a state-of-the-art large language model and those created by humans, aiming to detect bias. We compiled a publicly available dataset of assurance cases, represented as graphs with nodes and edges, supporting both link prediction and provenance analysis. Experiments show that graph neural networks (GNNs) achieve strong link prediction performance (ROC-AUC 0.760) on real assurance cases and generalise well across domains and semi-supervised settings. For provenance detection, GNNs effectively distinguish human-authored from LLM-generated cases (F1 0.94). We observed that LLM-generated assurance cases have different hierarchical linking patterns compared to human-authored cases. Furthermore, existing GNN explanation methods show only moderate faithfulness, revealing a gap between predicted reasoning and the true argument structure.

Fariz Ikhwantri, Dusica Marijan

Simula Research Laboratory Oslo, Norway

AI Assurance AI-Generated Text Detection Data Provenance Text-Attributed Graph Learning

Ask PDF

May 8, 2026

GRASP -- Graph-Based Anomaly Detection Through Self-Supervised Classification

Advanced persistent threat (APT) attacks remain difficult to detect due to their stealth, adaptability, and use of legitimate system components. Provenance-based intrusion detection systems (PIDS) offer a promising defense by capturing detailed relationships between system components and actions. However, current PIDS rely on predefined or subset-determined thresholds, which limit detection stability and the ability to detect any anomalous behavior in general. Furthermore, related work often neglects the role of process executables, which describe system activity by interacting through a process with files, network components, and other processes. We introduce GRASP, a PIDS based on masked self-supervised classification. GRASP masks the executable information of processes and learns to infer it from their two-hop provenance graph neighborhood, marking misclassified processes as anomalies. It captures behavior patterns for the learned executables without thresholding, making it robust against interference and unknown activities. Evaluations on the DARPA TC and OpTC datasets demonstrate that GRASP consistently detects anomalous behavior, including known attack-related activities, outperforming existing systems. Our PIDS identifies all documented attacks on datasets where the behavior of executables is learnable. In addition, compared to existing systems, GRASP uncovers potentially malicious anomalous behavior not labeled as an attack in the documentation.

Robin Buchta, Carsten Kleiner, Felix Heine +1

Cybersecurity Anomaly Detection

Ask PDF

Abstract

Data Provenance

Explore similar work

Detect, Localize, and Explain: Interactive Hierarchical Log Anomaly Analytics with LLM Augmentation

Evaluating Assurance Cases as Text-Attributed Graphs for Structure and Provenance Analysis

GRASP -- Graph-Based Anomaly Detection Through Self-Supervised Classification