CMU-CS-02-109Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-02-109
Somesh Jha*, Oleg Sheyner, Jeannette M. Wing February 2002
CMU-CS-02-109.ps
Keywords:Attack graph, model checking, minimization analysis,
reliability analysis, Markov Decision Processes, network vulnerability,
security
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. 17 pages *Computer Science Department, University of Wisconsin, Madison, WI. | |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |