9.3. Attack Graphs are Scenario Graphs
In the security community, Red Teams construct attack graphs to show how a system is vulnerable to attack. Each path in an attack graph shows a way in which an intruder can compromise the security of a system. These graphs are drawn by hand. A typical result of such intensive manual effort is a floor-to-ceiling, wall-to-wall “white board” attack graph, such as the one produced by a Red Team at Sandia National Labs for DARPA’s CC20008 information battlespace preparation experiment (Figure 9.3). Each box in the graph designates a single intruder action. A path from one of the leftmost boxes in the graph to one of the rightmost boxes is a sequence of actions corresponding to an attack scenario. At the end of any such scenario, the intruder has broken the network security in some way. The graph is included here for illustrative purposes only, so we omit the description of specific details.
Since these attack graphs are drawn by hand, they are prone to error: They might be incomplete (missing attacks), they might have redundant paths or redundant subgraphs, or they might have irrelevant nodes, transitions, or paths.
The correspondence between scenario graphs and attack graphs is simple. For a given desired security property, we generate the scenario graph for a model of the system to be protected. An example security property is that an intruder should never gain root access to a specific host. Since each scenario graph is property specific, in practice, we might need to generate many scenario graphs to represent the entire attack graph that a Red Team might construct manually.
Our main contribution is that we automate the process of producing attack graphs: (1) our technique scales beyond what humans can do by hand, and (2) since our algorithms guarantee to produce scenario graphs that are sound, exhaustive, and succinct, our attack graphs are not subject to the errors that humans are prone to make.