Shaofei Li (Key Laboratory of High-Confidence Software Technologies (MOE), School of Computer Science, Peking University), Feng Dong (Huazhong University of Science and Technology), Xusheng Xiao (Arizona State University), Haoyu Wang (Huazhong University of Science and Technology), Fei Shao (Case Western Reserve University), Jiedong Chen (Sangfor Technologies Inc.), Yao Guo (Key Laboratory of High-Confidence Software Technologies (MOE), School of Computer Science, Peking University), Xiangqun Chen (Key Laboratory of High-Confidence Software Technologies (MOE), School of Computer Science, Peking University), Ding Li (Key Laboratory of High-Confidence Software Technologies (MOE), School of Computer Science, Peking University)

Advanced Persistent Threats (APT) attacks have plagued modern enterprises, causing significant financial losses. To counter these attacks, researchers propose techniques that capture the complex and stealthy scenarios of APT attacks by using provenance graphs to model system entities and their dependencies. Particularly, to accelerate attack detection and reduce financial losses, online provenance-based detection systems that detect and investigate APT attacks under the constraints of timeliness and limited resources are in dire need. Unfortunately, existing online systems usually sacrifice detection granularity to reduce computational complexity and produce provenance graphs with more than 100,000 nodes, posing challenges for security admins to interpret the detection results. In this paper, we design and implement NodLink, the first online detection system that maintains high detection accuracy without sacrificing detection granularity. Our insight is that the APT attack detection process in online provenance-based detection systems can be modeled as a Steiner Tree Problem (STP), which has efficient online approximation algorithms that recover concise attack-related provenance graphs with a theoretically bounded error. To utilize the frameworks of the STP approximation algorithm for APT attack detection, we propose a novel design of in-memory cache, an efficient attack screening method, and a new STP approximation algorithm that is more efficient than the conventional one in APT attack detection while maintaining the same complexity. We evaluate NodLink in a production environment. The open-world experiment shows that NodLink outperforms two state-of-the-art (SOTA) online provenance analysis systems by achieving magnitudes higher detection and investigation accuracy while having the same or higher throughput.

View More Papers

Differentially Private Dataset Condensation

Tianhang Zheng (University of Missouri-Kansas City), Baochun Li (University of Toronto)

Read More

Using Behavior Monitoring to Identify Privacy Concerns in Smarthome...

Atheer Almogbil, Momo Steele, Sofia Belikovetsky (Johns Hopkins University), Adil Inam (University of Illinois at Urbana-Champaign), Olivia Wu (Johns Hopkins University), Aviel Rubin (Johns Hopkins University), Adam Bates (University of Illinois at Urbana-Champaign)

Read More

Timing Channels in Adaptive Neural Networks

Ayomide Akinsanya (Stevens Institute of Technology), Tegan Brennan (Stevens Institute of Technology)

Read More

ReqsMiner: Automated Discovery of CDN Forwarding Request Inconsistencies and...

Linkai Zheng (Tsinghua University), Xiang Li (Tsinghua University), Chuhan Wang (Tsinghua University), Run Guo (Tsinghua University), Haixin Duan (Tsinghua University; Quancheng Laboratory), Jianjun Chen (Tsinghua University; Zhongguancun Laboratory), Chao Zhang (Tsinghua University; Zhongguancun Laboratory), Kaiwen Shen (Tsinghua University)

Read More