MotifTrace: multi-stage attack investigation via automated stage discovery and path reconstruction on provenance graphs

Multi-stage cyber attacks spanning extended periods pose significant challenges for security investigation, as analysts must reconstruct the complete attack sequence from voluminous system audit logs. Existing provenance graph-based investigation methods either rely on predefined attack knowledge to map activities to known stages, or analyze the graph from alert events using a single set of analysis criteria that fail to adapt to the behaviorally distinct phases of an attack. Consequently, attack activities that are temporally or causally distant from the triggering alert are often inadequately recovered. We observe that different attack stages produce distinct distributions of temporal subgraph patterns in provenance graphs, providing a basis for automated stage partitioning without prior attack knowledge. Based on this observation, we propose MotifTrace , a two-phase framework that automates multi-stage attack investigation on provenance graphs without predefined attack knowledge or labeled data. MotifEmbed learns edge-level representations that preserve stage-specific temporal subgraph structures and clusters them into behaviorally coherent stage partitions that support downstream reconstruction. PathRank then identifies critical attack paths within each stage through topology-aware causal path scoring, and merges them across stages through shared entities to reconstruct the complete attack scenario. Evaluations on six attack campaigns of varying complexity, including DARPA Transparent Computing benchmarks, demonstrate that MotifTrace achieves an average Macro- F₁ F 1 of 0.88 in multi-stage reconstruction, outperforming state-of-the-art methods by over 21%. By eliminating the need for manual stage annotation and predefined attack signatures, MotifTrace automates a labor-intensive phase of the security investigation workflow, reducing analyst effort from provenance graph construction to structured attack summaries.