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
- Renzhi Tang (ORCID: https://orcid.org/0000-0001-6493-8047)
- Yunhe Cui (ORCID: https://orcid.org/0000-0002-0880-675X)
- Guowei Shen (ORCID: https://orcid.org/0000-0002-1329-4058)
- Chun Guo (ORCID: https://orcid.org/0000-0002-3341-220X)
- Yi Chen
Institutions
- Guizhou University (CN)
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