Summary
This report reviews past research papers that describe how to construct attack graphs, how to use them to improve security of computer networks, and how to use them to analyze alerts from intrusion detection systems. Two commercial systems are described [I, 2], and a summary table compares important characteristics of past research studies. For each study, information is provided on the number of attacker goals, how graphs are constructed, sizes of networks analyzed, how well the approach scales to larger networks, and the general approach. Although research has made significant progress in the past few years, no system has analyzed networks with more than 20 hosts, and computation for most approaches scales poorly and would be impractical for networks with more than even a few hundred hosts. Current approaches also are limited because many require extensive and difficult-to-obtain details on attacks, many assume that host-to-host reachability information between all hosts is already available, and many produce an attack graph but do not automatically generate recommendations from that graph. Researchers have suggested promising approaches to alleviate some of these limitations, including grouping hosts to improve scaling, using worst-case default values for unknown attack details, and symbolically analyzing attack graphs to generate recommendations that improve security for critical hosts. Future research should explore these and other approaches to develop attack graph construction and analysis algorithms that can be applied to large enterprise networks.