Causality-preserving compression method on provenance graph

ZHANG Zilong; DONG Weiyu; WANG Yisen

doi:10.11959/j.issn.2096-109x.2025068

您当前的位置：

首页 >

文章列表页 >

Causality-preserving compression method on provenance graph

Papers | 更新时间：2026-01-28

- Causality-preserving compression method on provenance graph
- Chinese Journal of Network and Information Security Vol. 11, Issue 6, Pages: 105-119(2025)
- 作者机构：
  
  信息工程大学，河南郑州 450001
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2025068
  CLC： TP393
- Received：24 January 2025，
  
  Revised：2025-08-28，
  
  Published：25 December 2025
- 稿件说明：
移动端阅览
张子龙, 董卫宇, 王奕森. 保留因果关系的溯源图压缩方法[J]. 网络与信息安全学报, 2025, 11(6): 105-119.

ZHANG Zilong, DONG Weiyu, WANG Yisen. Causality-preserving compression method on provenance graph[J]. Chinese Journal of Network and Information Security, 2025, 11(6): 105-119.
张子龙, 董卫宇, 王奕森. 保留因果关系的溯源图压缩方法[J]. 网络与信息安全学报, 2025, 11(6): 105-119. DOI： 10.11959/j.issn.2096-109x.2025068.

ZHANG Zilong, DONG Weiyu, WANG Yisen. Causality-preserving compression method on provenance graph[J]. Chinese Journal of Network and Information Security, 2025, 11(6): 105-119. DOI： 10.11959/j.issn.2096-109x.2025068.

摘要

溯源图是检测与调查复杂网络攻击的一种有效工具，但其存储和分析所需的高昂开销使得图压缩成为该领域不可或缺的环节。然而，现有的大多数压缩方法会破坏溯源图中节点间的重要因果关联，从而影响攻击调查的有效性。尤其是现有能够保留攻击调查能力的压缩算法，通常难以有效处理节点间循环交互产生的冗余问题。针对这一挑战，提出了一种图压缩算法CPC，可在确保节点间的因果关系不受损害的同时，实现对溯源图的有效压缩。该算法通过深入分析节点间的因果关系，记录节点依赖等关键信息，能够精准识别并剔除多余的依赖传递边，在维护攻击调查结果的情况下，显著提升了溯源图边数据的压缩效率。此外，针对离线与在线溯源图构建场景，分别实现了全依赖保留压缩CPC-A、部分依赖保留压缩CPC-P。在公开数据集上的实验表明，与当前先进的压缩算法相比，这两种算法在压缩性能上具有明显优势，整体压缩率提升幅度为9.3%～86.4%。

Abstract

Provenance graphs were widely used for detecting and investigating sophisticated network attacks. However

their high storage and analysis overhead made graph compression indispensable. Most existing compression methods were found to disrupt critical causal dependencies among nodes

thereby compromising the effectiveness of attack investigations. In particular

current compression algorithms that preserved investigative capabilities struggled to handle redundancies arising from cyclic interactions between nodes. To address this challenge

a novel graph compression algorithm

CPC

was proposed. By thoroughly analyzing causal relationships and recording essential node dependency information

redundant transitive dependency edges were precisely identified and removed

significantly improving edge compression efficiency while preserving the integrity of attack investigation results. Two variants of the algorithm were developed: CPC-A

which retains full dependencies for offline provenance graph construction

and CPC-P

which preserves partial dependencies for online scenarios. Experimental evaluations on public datasets showed that

compared with current state-of-the-art compression algorithms

the proposed approaches achieved substantially higher compression performance

with overall compression ratios improved by 9.3%~86.4%.

关键词

Keywords

references

HOSSAIN M N , MILAJERDI S M , WANG J , et al . SLEUTH: real-time attack scenario reconstruction from COTS audit data [C ] // Proceedings of the 26th USENIX Security Symposium (USENIX Security 17) . Berkeley : USENIX Association , 2017 : 487 - 504 .

MILAJERDI S M , GJOMEMO R , ESHETE B , et al . HOLMES: real-time APT detection through correlation of suspicious information flows [C ] // Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2019 : 1137 - 1152 .

XU Z , WU Z Y , LI Z C , et al . High fidelity data reduction for big data security dependency analyses [C ] // Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM , 2016 : 504 - 516 .

HOSSAIN M N , WANG J , SEKAR R , et al . Dependence-preserving data compaction for scalable forensic analysis [C ] // Proceedings of the 27th USENIX Conference on Security Symposium . Berkeley : USENIX Association , 2018 : 1723 - 1740 .

ZHU T T , WANG J Y , RUAN L Q , et al . General, efficient, and real-time data compaction strategy for APT forensic analysis [J ] . IEEE Transactions on Information Forensics and Security , 2021 , 16 : 3312 - 3325 .

LI Z Y , CHEN Q A , YANG R Q , et al . Threat detection and investigation with system-level provenance graphs: a survey [J ] . Computers & Security , 2021 , 106 : 102282 .

冷涛 , 蔡利君 , 于爱民 , 等 . 基于系统溯源图的威胁发现与取证分析综述 [J ] . 通信学报 , 2022 , 43 ( 7 ): 172 - 188 .

LENG T , CAI L J , YU A M , et al . Review of threat discovery and forensic analysis based on system provenance graph [J ] . Journal on Communications , 2022 , 43 ( 7 ): 172 - 188 .

ZIPPERLE M , GOTTWALT F , CHANG E , et al . Provenance-based intrusion detection systems: a survey [J ] . ACM Computing Surveys , 2023 , 55 ( 7 ): 1 - 36 .

INAM M A , CHEN Y F , GOYAL A , et al . SoK: history is a vast early warning system: auditing the provenance of system intrusions [C ] // Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2023 : 2620 - 2638 .

XIE Y L , MUNISWAMY-REDDY K K , LONG D D E , et al . Compressing provenance graphs [C ] // Proceedings of the Workshop on the Theory and Practice of Provenance . 2015 .

LEE K H , ZHANG X Y , XU D Y . LogGC: garbage collecting audit log [C ] // Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security - CCS '13 . New York : ACM , 2013 : 1005 - 1016 .

PEI K X , GU Z S , SALTAFORMAGGIO B , et al . HERCULE: attack story reconstruction via community discovery on correlated log graph [C ] // Proceedings of the 32nd Annual Conference on Computer Security Applications . New York : ACM , 2016 : 583 - 595 .

NI X Y , CHEN R R , HU M H , et al . Sardine: a threat-aware compression and querying system [C ] // Proceedings of the 2023 7th Asian Conference on Artificial Intelligence Technology (ACAIT) . Piscataway : IEEE Press , 2023 : 1289 - 1296 .

DING H L , ZHAI J , DENG D , et al . The case for learned provenance graph storage systems [C ] // Proceedings of the 32nd USENIX Security Symposium . Berkeley : USENIX Association , 2023 : 3277 - 3294 .

仇晶 , 陈荣融 , 朱浩瑾 , 等 . 基于溯源图的网络攻击调查研究综述 [J ] . 电子学报 , 2024 , 52 ( 7 ): 2529 - 2556 .

QIU J , CHEN R R , ZHU H J , et al . A survey of network attack investigation based on provenance graph [J ] . Acta Electronica Sinica , 2024 , 52 ( 7 ): 2529 - 2556 .

TANG Y T , LI D , LI Z C , et al . NodeMerge: template based efficient data reduction for big-data causality analysis [C ] // Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security . New York : ACM , 2018 : 1324 - 1337 .

HASSAN W U , LEMAY M , AGUSE N , et al . Towards scalable cluster auditing through grammatical inference over provenance graphs [C ] // 2018 Network and Distributed System Security Symposium . 2018 .

SETAYESHFAR O , ADKINS C , JONES M , et al . GrAALF: supporting graphical analysis of audit logs for forensics [J ] . Software Impacts , 2021 , 8 : 100068 .

MA S , ZHAI J , KWON Y , et al . Kernel-supported cost-effective audit logging for causality tracking [C ] // Proceedings of the 2018 USENIX Conference on Usenix Annual Technical Conference . Berkeley : USENIX Association , 2018 : 241 - 253 .

LEE K H , ZHANG X , XU D . High accuracy attack provenance via binary-based execution partition [C ] // 20th Annual Network and Distributed System Security Symposium . 2013 .

HASSAN W U , GUO S J , LI D , et al . NoDoze: combatting threat alert fatigue with automated provenance triage [C ] // 2019 Network and Distributed System Security Symposium . Internet Society . 2019 .

李霄翔 . 基于正常行为建模的溯源图压缩算法研究与实现 [D ] . 北京 : 清华大学 , 2024 .

LI X X . Research and Implementation of provenance graph compression algorithm based on normal behavior modeling [D ] . Beijing ： Tsinghua University , 2024 .

LI J W , ZHANG R , LIU J Y . ProvGRP: a context-aware provenance graph reduction and partition approach for facilitating attack investigation [J ] . Electronics , 2024 , 13 ( 1 ): 100 .

LI Z , WEI Y , SHEN X , et al . TAGS: real-time intrusion detection with tag-propagation-based provenance graph alignment on streaming events [J ] . arXiv: 2403.12541 , 2024 .

XIONG C L , ZHU T T , DONG W H , et al . Conan: a practical real-time APT detection system with high accuracy and efficiency [J ] . IEEE Transactions on Dependable and Secure Computing , 2020 , 19 ( 1 ): 551 - 565 .

KING S T , CHEN P M . BackTracking intrusions [J ] . ACM SIGOPS Operating Systems Review , 2003 , 37 ( 5 ): 223 - 236 .

MUNISWAMY-REDDY K K , HOLLAND D A , BRAUN U , et al . Provenance-aware storage systems [C ] // Proceedings of the USENIX Annual Technical Conference , General Track . Berkeley : USENIX Association , 2006 : 43 - 56 .

GEHANI A , TARIQ D . SPADE: support for provenance auditing in distributed environments [M ] // Middleware 2012 . Berlin, Heidelberg : Springer , 2012 : 101 - 120 .

PASQUIER T , HAN X Y , GOLDSTEIN M , et al . Practical whole-system provenance capture [C ] // Proceedings of the 2017 Symposium on Cloud Computing . New York : ACM , 2017 : 405 - 418 .

MOREAU L , CLIFFORD B , FREIRE J , et al . The open provenance model core specification (v1.1) [J ] . Future Generation Computer Systems , 2011 , 27 ( 6 ): 743 - 756 .

MOREAU L , HUYNH T D . The PROV-JSONLD serialization: a JSON-LD representation for the PROV data model [C ] // Proceedings of Provenance and Annotation of Data and Processes . Cham : Springer , 2021 : 51 - 67 .

ALSAHEEL A , NAN Y , MA S , et al . ATLAS: a sequence-based learning approach for attack investigation [C ] // Proceedings of the 30th USENIX Security Symposium . Berkeley : USENIX Association , 2021 : 3005 - 3022 .

HASSAN W U , NOUREDDINE M A , DATTA P , et al . OmegaLog: high-fidelity attack investigation via transparent multi-layer log analysis [C ] // Proceedings of 2020 Network and Distributed System Security Symposium . SanDiego : NDSS , 2020 .

FANG P , GAO P , LIU C , et al . Back-propagating system dependency impact for attack investigation [C ] // Proceedings of the 31st USENIX Security Symposium (USENIX Security 22) . Berkeley : USENIX Association , 2022 : 2461 - 2478 .

HOSSAIN M N , SHEIKHI S , SEKAR R . Combating dependence explosion in forensic analysis using alternative tag propagation semantics [C ] // Proceedings of the 2020 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2020 : 1139 - 1155 .

CHENG Z J , LV Q J , LIANG J Y , et al . Kairos: practical intrusion detection and investigation using whole-system provenance [C ] // Proceedings of the 2024 IEEE Symposium on Security and Privacy (SP) . Piscataway : IEEE Press , 2024 : 3533 - 3551 .

LI S F , DONG F , XIAO X S , et al . NODLINK: an online system for fine-grained APT attack detection and investigation [J ] . arXiv: 2311.02331 , 2023 .

梁若舟 , 高跃 , 赵曦滨 . 基于序列特征提取的溯源图上APT攻击检测方法 [J ] . 中国科学: 信息科学 , 2022 , 52 ( 8 ): 1463 - 1480 .

LIANG R Z , GAO Y , ZHAO X B . Sequence feature extraction-based APT attack detection method with provenance graphs [J ] . Scientia Sinica (Informationis) , 2022 , 52 ( 8 ): 1463 - 1480 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰