Investigating the Impact of Sink State Merging on Alert-Driven Attack Graphs

Abstract

This research paper focuses on the complex domain of alert-driven attack graphs. SAGE is a tool which generates such attack graphs (AGs) by using a suffix-based probabilistic deterministic finite automaton (S-PDFA). One of the substantial properties of this algorithm is to detect infrequent severe alerts while maintaining the context of attacks via the help of sink states and state IDs. This is a modelling assumption that we validate by answering the question driving this research: How does allowing the sink states to merge with other sink states affect the generated alert-driven attack graphs? Our research used a transparent methodology to obtain size, complexity and completeness statistics of the two algorithms. Afterwards, outstanding values in size and complexity allow us to filter insightful attack graphs, subject to head-to-head comparisons concerning their interpretability. We discovered that many remarkable changes happen in the outputted attack graphs, leading to an evident decrease in interpretability and increased loss of context. Concurrently, we do not detect substantial changes in size, complexity and completeness, leading us to believe that it is possible to unlock SAGE's full potential by adding specific thresholds for merging sink states. One proposed constraint is allowing only the merges of sinks at equal distance to the victim node. This alteration leads to similar results in all metrics, including interpretability, where some AGs show improvements.