APTrace: A Responsive System for Agile Enterprise Level Causality Analysis

Publication Date: 4/24/2020

Event: 36th IEEE International Conference on Data Engineering (ICDE 2020)

Reference: pp. 1701-1712, 2020

Authors: Jiaping Gui, NEC Laboratories America, Inc.; Ding Li, NEC Laboratories America, Inc.; Zhengzhang Chen, NEC Laboratories America, Inc.; Junghwan Rhee, NEC Laboratories America, Inc.; Xusheng Xiao, Case Western Reserve University; Mu Zhang, University of Utah; Kangkook Jee, University of Texas at Dallas; Zhichun Li, Stellar Cyber; Haifeng Chen, NEC Laboratories America, Inc.

Abstract: While backtracking analysis has been successful in assisting the investigation of complex security attacks, it faces a critical dependency explosion problem. To address this problem, security analysts currently need to tune backtracking analysis manually with different case-specific heuristics. However, existing systems fail to fulfill two important system requirements to achieve effective backtracking analysis. First, there need flexible abstractions to express various types of heuristics. Second, the system needs to be responsive in providing updates so that the progress of backtracking analysis can be frequently inspected, which typically involves multiple rounds of manual tuning. In this paper, we propose a novel system, APTrace, to meet both of the above requirements. As we demonstrate in the evaluation, security analysts can effectively express heuristics to reduce more than 99.5% of irrelevant events in the backtracking analysis of real-world attack cases. To improve the responsiveness of backtracking analysis, we present a novel execution-window partitioning algorithm that significantly reduces the waiting time between two consecutive updates (especially, 57 times reduction for the top 1% waiting time).

Publication Link: https://ieeexplore.ieee.org/document/9101446