TeRed: Normal Behavior-Based Efficient Provenance Graph Reduction for Large-Scale Attack Forensics
Xiaoxiang Li, Xinyu Jiang, Hai Yang Wan, Xibin Zhao · IEEE Transactions on Information Forensics and Security · 2025
System intrusions, particularly Advanced Persistent Threats (APTs), pose significant threats to enterprises and organizations. Provenance graph-based attack detection and investigation methods are crucial for defending against these intrusions. To detect various attacks, security systems collect comprehensive operating system event data, resulting in massive provenance graphs that increase storage costs and complicate analysis and querying. Efficiently optimizing these provenance graphs has thus become a core issue. However, existing data reduction methods often mistakenly delete critical security information, significantly impacting attack detection and investigation. This paper introduces TeRed, a novel method for reducing provenance graphs based on normal behavior patterns. Our approach employs unit tests to learn the system’s normal behavior patterns, which are then used to streamline the provenance graph. Experiments on five datasets show that our method reduces the provenance graph while preserving all attack-related information. Importantly, it does not compromise attack detection and investigation, showcasing significant advantages over other data reduction techniques.