Minimizing Attack Graph Data Structures

Published: November 15, 2015


Peter M. 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, -1
Conference Title: Tenth International Conference on Software Engineering Advances (ICSEA 2015)
Pub Type: Conferences

Download Paper


attack graph, complexity analysis, data structures, minimization, representation, security
Created November 15, 2015, Updated February 19, 2017