Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Tang et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: