Paul Ammann
George Mason University
USA

Joseph Pamula
George Mason University
USA

Ronald Ritchey
Booz Allen & Hamilton
USA

Julie Street
George Mason University
USA

The typical means by which an attacker breaks into a network is through a chain of exploits, where each exploit in the chain lays the groundwork for subsequent exploits. Such a chain is called an attack path, and the set of all possible attack paths form an attack graph. Researchers have proposed a variety of methods to generate attack graphs. In this paper, we provide a novel alternative approach to analyzing network vulnerabilities. Our approach has the following benefits with respect to existing proposals: 1) It provides a more intuitive model in which an analyst working to secure a network can proceed, and 2) Its algorithmic complexity is polynomial in the size of the network, and so has the potential of scaling well to practical networks. The drawback is that we track only "good" attack paths, as opposed to all possible attack paths. Hence, an analyst may make suboptimal choices when repairing the network. Since attack graphs grow exponentially with the size of the network, we argue that suboptimal solutions are an unavoidable cost of scalability, and hence
practical utility.

Keywords: network security, vulnerability, exploit, monotonic analysis, scalability, penetration testing

Read Paper (in PDF)