Practical Attack Graph Generation for Network Defense

Kyle Ingols
MIT Lincoln Laboratory

Richard Lippmann
MIT Lincoln Laboratory

Keith Piwowarski
MIT Lincoln Laboratory

Attack graphs are a valuable tool to network defenders that illustrate
paths an attacker can use to gain access to a targeted network.
Defenders can then focus their efforts on patching the vulnerabilities
and configuration errors that allow the attackers the greatest amount
of access. We have created a new type of attack graph, the
multiple-prerequisite graph, that scales nearly linearly as the size
of a typical network increases. We have built a prototype system
using this graph type. The prototype uses readily available source
data to automatically compute network reachability, classify
vulnerabilities, build the graph, and recommend actions to improve
network security. We have tested the prototype on an operational
network with over 250 hosts, where it helped to discover a previously
unknown configuration error. It can evaluate large, enterprise
networks using commodity hardware in seconds, and has processed
complex simulated networks with over 50,000 hosts in under four

Keywords: attack graph, attack tree, network security

Read Paper Read Paper (in PDF)