SparseCalib: a reconstruction-free query-oriented storage framework for provenance graphs

Provenance graphs have become a fundamental data representation for security auditing and APT investigation, as they preserve causal dependencies among system entities. Large-scale provenance graphs incur prohibitive storage and query costs, especially when analysts repeatedly perform target-centric filtering, forward tracing, and backward tracing. However, existing approaches still struggle to simultaneously achieve lossless preservation, compact storage, and efficient query execution. Recent lossless provenance storage systems such as Leonard and Dehydrator reduce storage cost but rely on auxiliary calibration data, which introduces significant space and time overhead. In addition, their query capabilities have limited coverage, reducing efficiency in multi-scenario batch analysis. Therefore, we propose SPARSECALIB, a query-native storage framework for lossless provenance graph analysis. SPARSECALIB first characterizes common investigation workloads using three query semantics and decomposes provenance graphs into three corresponding substructures: FORWARD, BACKWARD, and NODEATTR. It then applies field-level redundancy reduction, structural normalization, and a query-oriented position-mapping mechanism to support compact storage and reconstruction-free batch querying. Evaluations on five provenance graphs constructed from one CADETS file family in the DARPA Transparent Computing Engagement #5 release demonstrate that SPARSECALIB improves storage efficiency and query performance compared with the evaluated systems. On average across the five graphs, it reduces storage space and the derived process-parallel construction makespan by 64.8% and 63.3%, respectively, relative to Dehydrator, and reduces storage space by 97.2% relative to Neo4j.

Authors

Institutions

Publication Details

Journal
Journal of King Saud University - Computer and Information Sciences
Published
2026-11-19
DOI
https://doi.org/10.1007/s44443-026-01439-2
Primary Topic
Digital and Cyber Forensics
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

SparseCalib: a reconstruction-free query-oriented storage framework for provenance graphs

Renzhi Tang, Yunhe Cui, Guowei Shen, Chun Guo et al.
Journal of King Saud University - Computer and Information Sciences
Digital and Cyber Forensics
article

SparseCalib: a reconstruction-free query-oriented storage framework for provenance graphs

Renzhi Tang, Yunhe Cui, Guowei Shen, Chun Guo, Yi Chen
article en

Abstract

Provenance graphs have become a fundamental data representation for security auditing and APT investigation, as they preserve causal dependencies among system entities. Large-scale provenance graphs incur prohibitive storage and query costs, especially when analysts repeatedly perform target-centric filtering, forward tracing, and backward tracing. However, existing approaches still struggle to simultaneously achieve lossless preservation, compact storage, and efficient query execution. Recent lossless provenance storage systems such as Leonard and Dehydrator reduce storage cost but rely on auxiliary calibration data, which introduces significant space and time overhead. In addition, their query capabilities have limited coverage, reducing efficiency in multi-scenario batch analysis. Therefore, we propose SPARSECALIB, a query-native storage framework for lossless provenance graph analysis. SPARSECALIB first characterizes common investigation workloads using three query semantics and decomposes provenance graphs into three corresponding substructures: FORWARD, BACKWARD, and NODEATTR. It then applies field-level redundancy reduction, structural normalization, and a query-oriented position-mapping mechanism to support compact storage and reconstruction-free batch querying. Evaluations on five provenance graphs constructed from one CADETS file family in the DARPA Transparent Computing Engagement #5 release demonstrate that SPARSECALIB improves storage efficiency and query performance compared with the evaluated systems. On average across the five graphs, it reduces storage space and the derived process-parallel construction makespan by 64.8% and 63.3%, respectively, relative to Dehydrator, and reduces storage space by 97.2% relative to Neo4j.

Journal of King Saud University - Computer and Information SciencesVol. 38(10)
Guizhou University (CN)
Digital and Cyber Forensics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon