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 network vulnerability analysis by utilizing a penetration tester's perspective of maximal level of penetration possible on a host. Our approach has the following benefits: it provides a more intuitive model in which an analyst can work, and 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. A working prototype tool has been implemented to demonstrate the practicality of our approach.

The individual vulnerabilities of hosts on a network can be combined by an attacker to gain access that would not be possible if the hosts were not interconnected. Currently available tools report vulnerabilities in isolation and in the context of individual hosts in a network. Topological vulnerability analysis (TVA) extends this by searching for sequences of interdependent vulnerabilities, distributed among the various network hosts. Model checking has been applied to the analysis of this problem with some interesting initial results. However previous efforts did not take into account a realistic representation of network connectivity. These models were enough to demonstrate the usefulness of the model checking approach but would not be sufficient to analyze real-world network security problems. This paper presents a modem of network connectivity at multiple levels of the TCP/IP stack appropriate for use in a model checker. With this enhancement, it is possible to represent realistic networks including common network security devices such as firewalls, filtering routers, and switches.

Even well administered networks are vulnerable to attacks due to the security ramifications of offering a variety of combined services. That is, services that are secure when offered in isolation nonetheless provide an attacker with a vulnerability to exploit when offered simultaneously. Many current tools address vulnerabilities in the context of a single host. We address vulnerabilities due to the configuration of various hosts in a network. In a different line of research, formal methods are often useful for generating test cases, and model checkers are particularly adept at this task due to their ability to generate counterexamples. We address the network vulnerabilities problem with test cases, which amount to attack scenarios, generated by a model checker. We encode the vulnerabilities in a state machine description suitable for a model checker and then assert that an attacker cannot acquire a given privilege on a given host. The model checker either offers assurance that the assertion is true on the actual network or provides a counterexample detailing each step of a successful attack.