Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Minimizing Attack Graph Data Structures



Peter Mell, Richard Harang


An attack graph is a data structure representing how an attacker can chain together multiple attacks to expand their influence within a network (often in an attempt to reach some set of goal states). Restricting attack graph size is vital for the execution of high degree polynomial analysis algorithms. However, we find that the most widely-cited and recently-used 'condition/exploit' attack graph representation has a worst-case quadratic node growth with respect to the number of hosts in the network when a linear representation will suffice. In 2002, a node linear representation in the form of a 'condition' approach was published but was not significantly used in subsequent research. In analyzing the condition approach, we find that (while node linear) it suffers from edge explosions: the creation of unnecessary complete bipartite sub-graphs. To address the weaknesses in both approaches, we provide a new hybrid 'condition/vulnerability' representation that regains linearity in the number of nodes and that removes unnecessary complete bipartite sub-graphs, mitigating the edge explosion problem. In our empirical study modeling an operational 5968-node network, our new representation had 94 % fewer nodes and 64 % fewer edges than the currently used condition/exploit approach.
Proceedings Title
ICSEA 2015: the Tenth International Conference on Software Engineering Advances
Conference Dates
November 15-20, 2015
Conference Location
Barcelona, ES
Conference Title
Tenth International Conference on Software Engineering Advances (ICSEA 2015)


attack graph, complexity analysis, data structures, minimization, representation, security


Mell, P. and Harang, R. (2015), Minimizing Attack Graph Data Structures, ICSEA 2015: the Tenth International Conference on Software Engineering Advances, Barcelona, ES, [online], (Accessed April 16, 2024)
Created November 14, 2015, Updated April 18, 2022