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

MadRadar: A Black-Box Physical Layer Attack Framework on mmWave...

David Hunt (Duke University), Kristen Angell (Duke University), Zhenzhou Qi (Duke University), Tingjun Chen (Duke University), Miroslav Pajic (Duke University)

Read More

AAKA: An Anti-Tracking Cellular Authentication Scheme Leveraging Anonymous Credentials

Hexuan Yu (Virginia Polytechnic Institute and State University), Changlai Du (Virginia Polytechnic Institute and State University), Yang Xiao (University of Kentucky), Angelos Keromytis (Georgia Institute of Technology), Chonggang Wang (InterDigital), Robert Gazda (InterDigital), Y. Thomas Hou (Virginia Polytechnic Institute and State University), Wenjing Lou (Virginia Polytechnic Institute and State University)

Read More

Maginot Line: Assessing a New Cross-app Threat to PII-as-Factor...

Fannv He (National Computer Network Intrusion Protection Center, University of Chinese Academy of Sciences, China), Yan Jia (DISSec, College of Cyber Science, Nankai University, China), Jiayu Zhao (National Computer Network Intrusion Protection Center, University of Chinese Academy of Sciences, China), Yue Fang (National Computer Network Intrusion Protection Center, University of Chinese Academy of Sciences, China),…

Read More

Certificate Transparency Revisited: The Public Inspections on Third-party Monitors

Aozhuo Sun (Institute of Information Engineering, Chinese Academy of Sciences), Jingqiang Lin (School of Cyber Science and Technology, University of Science and Technology of China), Wei Wang (Institute of Information Engineering, Chinese Academy of Sciences), Zeyan Liu (The University of Kansas), Bingyu Li (School of Cyber Science and Technology, Beihang University), Shushang Wen (School of…

Read More