Progressive attack graph: a technique for scalable and adaptive attack graph generation

Abstract In modern computer networks where sophisticated cyber attacks occur daily, a timely cyber risk assessment becomes paramount. Attack Graph (AG) constitutes a highly effective solution for performing cyber risk assessment in the context of multi-step attacks on computer networks. However, its construction is hindered by significant scalability challenges arising from the inherent combinatorial complexity of the process. This sequential methodology results in prolonged delays before analytical capabilities can be leveraged. Moreover, due to the extended time required for AG generation, existing techniques poorly capture the dynamic evolution of network structures, thereby limiting their ability to provide real-time adaptability in response to environmental changes. To mitigate these problems, this paper rethinks the classic AG analysis through StatAG , a novel workflow in which the analyst can query the system anytime, thus enabling real-time analysis before the completion of the AG generation with quantifiable statistical significance. To achieve this goal, we leverage progressive data analysis combined with statistical analysis. Beyond the real-time capabilities enabled by progressive computation, we further speed up the AG generation with two algorithms that accelerate the convergence of the statistical significance of generated AG. The former is about the weighted path sampling to avoid the possible high number of collisions introduced by random walks. The latter proposes an approximated version of the Kolmogorov-Smirnov distance linear in the number of attack paths. While statistical significance enables the progressive AG generation for every analysis, we present SteerAG to accelerate the generation by steering it with the analysis query. SteerAG leverages Machine Learning (ML) models, specifically decision trees, to learn vulnerability features from already generated attack paths to derive the steering rules enabling acceleration. To show the capabilities of the proposed workflow, we perform an extensive quantitative validation and present a realistic case study on networks of unprecedented size. It demonstrates the advantages of our approach in terms of scalability and fitting to common attack path analyses.