# Minimization and Reliability Analyses of Attack Graphs

**Author:**Somesh Jha, Oleg Sheyner, and Jeannette M. Wing
Click here for the
PostScript
of technical report.

## Abstract

An attack graph is a succinct representation of all paths through a system
that end in a state where an intruder has successfully achieved his
goal. Today Red Teams determine the vulnerability of networked systems by
drawing gigantic attack graphs by hand. Constructing attack graphs by hand
is tedious, error-prone, and impractical for large systems. By viewing an
attack as a violation of a safety property, we can use model
checking to produce attack graphs automatically: a successful
path from the intruder's viewpoint is a counterexample produced by the
model checker. In this paper we present an algorithm for generating attack
graphs using model checking.
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.