Automated Generation and Analysis of Attack Graphs

An integral part of modeling the global view of network security is constructing \emph{attack graphs}. In practice, attack graphs are produced manually by Red Teams. Construction by hand, however, is tedious, error-prone, and impractical for attack graphs larger than a hundred nodes. In this paper we present an automated technique for generating and analyzing attack graphs. We base our technique on {\em symbolic model checking}~\cite{ClarkeGrumbergPeled} algorithms, letting us construct attack graphs automatically and efficiently. We also describe two analyses to help decide which attacks would be most cost-effective to guard against. We implemented our technique in a tool suite and tested it on a small network example, which includes models of a firewall and an intrusion detection system.
Somesh Jha
Last modified: Fri Apr 11 14:48:49 CDT 2003