Dependence-Preserving Data Compaction for Scalable Forensic Analysis

on YouTube ↗23m

" summary

Introduces two graph reductions, full dependence preservation and source dependence preservation, that drop 4.6–19× fewer events while provably preserving backtracking and impact analysis; converts timestamped audit streams into a versioned dependence graph and applies redundant-edge/node and cycle-collapsing optimizations to cut versions to 1.26 per node on average. Implements compact on-disk encoding that is ~35× smaller (41× with source technique), uses ~5 bytes per original event in memory, and analyzes nearly 1 million events/sec per core.

AI-written summary · about

" chapters (26)

1. 0:00Intro
2. 0:43Motivation
3. 1:29Goals
4. 2:16Contributions
5. 3:12Background: Dependence Graphs
6. 4:46Reduction Techniques
7. 5:17Log-based reduction: Run-Merging
8. 6:32Log-based reduction: Limitations
9. 7:15Our Approach: Full Dependence (FD) Preservation
10. 8:02Source Dependence (SD) Preservation
11. 9:17Efficient Implementation
12. 10:41Redundant Edge Optimization (RED)
13. 11:19Redundant node optimization (RNO)
14. 11:52Cycle-Collapsing Optimization (CCD)
15. 12:08Optimized Versioned Graph
16. 12:24Evaluation Dataset
17. 13:16Data Size (Millions of events)
18. 13:30Reduction Factor
19. 14:01Average No. of Versions per node
20. 14:38Total Size on Disk (GB)
21. 15:13Dependence Graph Size (MB)
22. 15:40(Preliminary) Results on DARPA 3 Engagement
23. 16:58Do reductions interfere with forensic analysis?
24. 17:47Example Graph Constructed after Analysis
25. 18:38Related Work
26. 19:23Summary

" related talks

• 09mLogCrisp: Fast Aggregated Analysis on Large-scale Compressed Logs by Enabling...Qi Zhou, Junyu Wei, Guangyan Zhang, Junchao Chen · USENIX ATC '25
• 19mScalable Language Agnostic Taint Tracking using Explicit Data DependenciesSedick David Baker, Xavier Pinho, Andrei Michael Dreyer, Fabian Yamaguchi · SOAP 2025
• 17mShieldReduce: Fine-Grained Shielded Data ReductionJingwei Li, Patrick P. C. Lee, Xiaosong Zhang, Jingyuan Yang, Jun Wu, Ruilin Wu, Xiong Li · USENIX ATC '25
• 29mWide Event AnalyticsIgor Wiedler · LISA19
• 32mLarge-Scale Graph Processing on Emerging Storage DevicesChangho Choi, Nima Elyasi, Anand Sivasubramaniam · FAST '19
• 29mSliding Look-Back Window Assisted Data Chunk Rewriting for Improving Deduplication...Bingzhe Li, Zhichao Cao, Fenggang Wu, David H.C. Du, Shiyong Liu, Guohua Wang · FAST '19
• 01h 24mStreaming, Sketching and Sufficient Statistics IGraham Cormode · Big Data Boot Camp 2013
• 50mBig Data on Smallish MachinesGuy Blelloch · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)