  As the complexity and destructiveness of Advanced Persistent Threat (APT)
increase, there is a growing tendency to identify a series of actions
undertaken to achieve the attacker's target, called attack investigation.
Currently, analysts construct the provenance graph to perform causality
analysis on Point-Of-Interest (POI) event for capturing critical events
(related to the attack). However, due to the vast size of the provenance graph
and the rarity of critical events, existing attack investigation methods suffer
from problems of high false positives, high overhead, and high latency. To this
end, we propose SPARSE, an efficient and real-time system for constructing
critical component graphs (i.e., consisting of critical events) from streaming
logs. Our key observation is 1) Critical events exist in a suspicious semantic
graph (SSG) composed of interaction flows between suspicious entities, and 2)
Information flows that accomplish attacker's goal exist in the form of paths.
Therefore, SPARSE uses a two-stage framework to implement attack investigation
(i.e., constructing the SSG and performing path-level contextual analysis).
First, SPARSE operates in a state-based mode where events are consumed as
streams, allowing easy access to the SSG related to the POI event through
semantic transfer rule and storage strategy. Then, SPARSE identifies all
suspicious flow paths (SFPs) related to the POI event from the SSG, quantifies
the influence of each path to filter irrelevant events. Our evaluation on a
real large-scale attack dataset shows that SPARSE can generate a critical
component graph (~ 113 edges) in 1.6 seconds, which is 2014 X smaller than the
backtracking graph (~ 227,589 edges). SPARSE is 25 X more effective than other
state-of-the-art techniques in filtering irrelevant edges.
