"Automated Generation and Analysis of Attack Graphs," Oleg Sheyner (Carnegie Mellon University), Somesh Jha (University of Wisconsin), Jeannette Wing (Carnegie Mellon University), Richard Lippmann (MIT Lincoln Labs), Joshua Haines (MIT Lincoln Labs), 2002 IEEE Symposium on Security and Privacy

Summary

Host-specific attacks have been the major focus of vulnerability analysis. This is primarily because of simplicity. It is easy to look for vulnerabilities on a specific machine, and take necessary measures. However, more surreptitious attacks exist, whereby an attacker can attain previously unexpected privileges by compromising several machines on the network, which eventually leads to success (e.g., root access on a certain machine). The authors claim that red teams generate attack graphs by hand to analyze such vulnerabilities in the network. However, as the networks get larger, and the attacks more diverse, these attack graphs get extremely complicated. It is obviously desirable to automate this process. The authors use model checking for the analysis of attack graphs. They model the network as a finite state machine and specify the desired safety property (e.g., an attacker should not have root access on machine x). The model is fed into NuSMV, which then generates an attack graph. The authors propose two uses of these attack graphs. A minimal set of attacks can be determined, fixing which would guarantee the safety property. Administrators can then focus their attention on these vulnerabilities first. This has obvious economic benefits. Secondly, probabilistic analysis can be carried out to see how fixing certain vulnerabilities affect overall security. The authors claim that their method results in a significant savings in space compared to current approaches. Further, this approach can be extended to model liveness properties, and can potentially discover previously unknown attacks.

Issues raised:

- If the attacks on machines are known, why not patch them up instead of doing all this analysis?

- Looks like this is easier for attackers to use. Attackers need only one "path" in the attack graph, so computation requirements are much less. Besides, attackers usually have many zombies that can help in analyzing the model for an attack path

- Maybe administrators/attackers can use the Seti@Home approach to analyze the models. Google compute client for example.

- Another suggestion for the use of attack graphs - one could assume that certain machines are vulnerable (even if they're not) to buffer overflow for example, and see how vulnerable the network is on the whole. This would help administrators to concentrate on securing machines that are the highest risks to the network.

Strong Accept 3
Weak Accept 7
Weak Reject 6
Strong Reject 0