Dehydrator: Enhancing Provenance Graph Storage via Hierarchical Encoding and Sequence Generation

As the scope and impact of cyber threats have expanded, analysts utilize provenance graphs constructed from kernel logs to hunt for threats and investigate attacks. The high frequency of kernel events and the persistence of attacks pose challenges for the efficient storage of provenance graphs. Current approaches can be categorized into two types: pruning-based storage (e.g., LogGC, CPR, and NodeMerge) and encoding-based storage (e.g., DeepZip, SLEUTH, ELISE, and Leonard). However, none of these methods simultaneously satisfy the following three requirements: 1) lossless content, 2) storage efficiency, and 3) query support. To address this gap, we propose <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Dehydrator</small>, an efficient provenance graph storage system that fulfills all these requirements. For the logs generated by auditing frameworks, <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Dehydrator</small> uses field mapping encoding to filter field-level redundancy, hierarchical encoding to filter structure-level redundancy, and finally learns a deep neural network to support batch querying. We have conducted evaluations on seven datasets totaling over one billion log entries. Experimental results show that <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Dehydrator</small> reduces the storage space by 84.55%. <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Dehydrator</small> is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$7.36\times $ </tex-math></inline-formula> more efficient than PostgreSQL, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$7.16\times $ </tex-math></inline-formula> than Neo4j, and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$16.17\times $ </tex-math></inline-formula> than Leonard (the work most closely related to <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Dehydrator</small>, published at Usenix Security’23).