Home // ICSEA 2015, The Tenth International Conference on Software Engineering Advances // View article

Minimizing Attack Graph Data Structures

Authors:
Peter Mell
Richard Harang

Keywords: attack graph; complexity analysis; data structures; minimization; representation; security

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.

Pages: 376 to 385

Copyright: Copyright (c) The Government of United States, 2015. Used by permission to IARIA.

Publication date: November 15, 2015

Published in: conference

ISSN: 2308-4235

ISBN: 978-1-61208-438-1

Location: Barcelona, Spain

Dates: from November 15, 2015 to November 20, 2015