Minimizing Attack Graph Data Structures

Published

November 14, 2015

Author(s)

Peter Mell, Richard Harang

Abstract

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)

Pub Type

Conferences

Download Paper

Local Download

Keywords

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

Citation

Mell, P. and Harang, R. (2015), Minimizing Attack Graph Data Structures, ICSEA 2015: the Tenth International Conference on Software Engineering Advances, Barcelona, ES, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=917681 (Accessed April 25, 2024)