Computer Science Department
School of Computer Science, Carnegie Mellon University
Minimization and Reliability Analyses of Attack Graphs
Somesh Jha*, Oleg Sheyner, Jeannette M. Wing
Parts of this report will appear in our paper accepted by the
IEEE Symposium on Security and Privacy, May 2002;
Security analysts use attack graphs for detection, defense, and forensics. In this paper we present a minimization technique that allows analysts to decide which minimal set of security measures would guarantee the safety of the system. We provide a formal characterization of this problem: we prove that it is polynomially equivalent to the minimum hitting set problem and we present a greedy algorithm with provable bounds. We also present a reliability technique that allows analysts to perform a simple cost-benefit analysis depending on the likelihoods of attacks. By interpreting attack graphs as Markov Decision Processes we can use a standard MDP value iteration algorithm to compute the probabilities of intruder success for each attack the graph.
We illustrate our work in the context of a small example that includes models of a firewall and an intrusion detection system.
*Computer Science Department, University of Wisconsin, Madison, WI.