Behind the scenes of attack graphs: Vulnerable network generator for in-depth experimental evaluation of attack graph scalability

An Attack Graph represents potential paths for attackers to compromise a computer network and security analysts use it to pinpoint vulnerable areas for cyber risk assessment. Due to their combinatorial complexity, designing scalable algorithms for generating these graphs without sacrificing their accuracy remains a challenge. Previous research focused on improving scalability, but evaluations often overlooked key parameters beyond network size, thus raising the natural question of their application in real-world settings. One of the main causes is the lack of data that the cybersecurity community faces in different areas, and cyber risk assessment in particular. To address this problem and support the comprehensive evaluation of attack graph algorithms, we introduce a dataset generator of vulnerable networks, which includes realistic reachability graphs and vulnerability inventories. This enables the design of an analytical framework to assess attack graph scalability comprehensively, considering diverse network and vulnerability dimensions. According to the proposed framework, we perform an in-depth experimental evaluation of the time and space complexities of attack graphs, offering novel insights into the critical parameters affecting them, and we extensively discuss how they inform and benefit future approaches. • Dataset generator of realistic vulnerable networks. • In-depth experimental evaluation and analysis of Attack Graph scalability issues. • Application of Attack Graph algorithms on real networks.