SParse: Semantic Tracking and Path Analysis for Attack Investigation in Real-Time

As Advanced Persistent Threats (APTs) become more complex and destructive, attack investigation has gained importance. Analysts use provenance graphs for causality analysis on Point-Of-Interest (POI) events to capture critical events. However, existing methods suffer from problems of high false positives, high overhead, and high latency due to the vast size of the provenance graph and the rarity of critical events. We propose <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SPARSE</small> for constructing critical component graphs (i.e., consisting of critical events) from streaming logs in real time. Our approach is based on two key observations: 1) Critical events exist in suspicious semantic graphs (SSGs) composed of interaction flows between suspicious entities, and 2) Information flows accomplishing the attacker's goal exist as paths. <sc xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SPARSE</small> uses a two-stage framework that first constructs the SSG using a state-based mode with semantic transfer rules and storage strategies. Then, it identifies suspicious flow paths (SFPs) related to the POI event and quantifies each path's influence to filter irrelevant events. Evaluation on a large-scale attack dataset shows our system generates a critical component graph (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim$</tex-math></inline-formula> 113 edges) in 1.6 seconds, which is 2014 × smaller than the backtracking graph (<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\sim$</tex-math></inline-formula> 227,589 edges). It is also 25 × more effective in filtering irrelevant edges compared to other state-of-the-art techniques.