CSCProv: causal-semantic consistent provenance graph compression for attack detection

Abstract

Abstract Provenance graphs have become an important foundation for attack investigation and anomaly detection in enterprise systems. However, system audit logs generate massive numbers of events, resulting in extremely large provenance graphs that not only hinder efficient security analysis but also impose significant storage and computational overhead. Although existing graph reduction techniques can alleviate this problem to some extent, many approaches focus primarily on structural redundancy and often ignore the semantic differences between system entities, which may lead to the loss of attack-critical dependencies. To address this challenge, we present CSCProv, a causal-semantic consistent provenance graph compression framework designed to reduce graph size while preserving attack-relevant dependencies for efficient security analysis. The key idea is to perform node aggregation only when both structural dependency patterns and behavioral semantics remain consistent, ensuring that compression does not obscure critical attack propagation paths. To achieve this, we introduce a novel metric called Causal-Semantic Consistency (CSC), which jointly models topology-dominant event-induced provenance dependencies, referred to as causal dependencies in the provenance sense, and fine-grained behavioral semantics to guide graph compression. By integrating structural dependency information with security-specific semantic representations, CSCProv effectively eliminates redundant provenance structures while maintaining attack-critical contexts required for downstream security analytics. We evaluate CSCProv on the DARPA Engagement 3 (E3) dataset. Results show that CSCProv achieves up to 30× provenance graph reduction while preserving attack-critical dependencies. Despite aggressive compression, the compressed graphs maintain nearly identical detection performance with negligible accuracy degradation. In addition, CSCProv improves the efficiency of downstream attack detection, reducing detection time by 32.7–48.3% across different datasets and detection frameworks. These results demonstrate that CSCProv provides an effective balance between provenance graph reduction, attack information preservation, and security analysis efficiency.

The authors' abstract, as published at the source. Cybersecurity, 2026 · DOI ↗