Efficient Minimum-Cost Network Hardening via Exploit Dependency Graphs

Steven Noel, Sushil Jajodia, Brian O'Berry, Michael Jacobs
George Mason University

Global analysis of network security vulnerability must consider attacker exploits not just in isolation, but also in combination. The general approach to this problem is to compute attack paths (combinations of exploits), from which one can decide whether a given set of network hardening measures guarantees the safety of given critical resources. In this paper, we go beyond attack paths to consider the assignment version of this problem, which is much more important from the standpoint of network defense. That is, we compute actual sets of hardening measures (assignments of initial network conditions) that guarantee the safety of given critical resources. Moreover, for given costs associated with individual hardening measures, we compute assignments that minimize overall cost. By doing our minimization at the level of initial conditions rather than exploits, we resolve hardening irrelevancies and redundancies in a way that cannot be done through previously proposed exploit-level approaches. Moreover, we use an efficient exploit dependency representation based on monotonic logic that has low-order polynomial complexity, in contrast to many previously proposed attack graph representations with exponential complexity.

Keywords: Network attack modeling, vulnerability analysis, network hardening, attack graphs, exploit dependencies

Read Paper Read Paper (in PDF)