Practical Attack Graph Generation for Network Defense

Citation

• Kyle Ingols, Richard Lippmann and Keith Piwowarski. 22nd Annual Computer Security Applications Conference (ACSAC), Miami Beach, Florida, December 11-15, 2006.

Abstract

Attack graphs are a valuable tool to network defenders,illustrating paths an attacker can use to gain access to atargeted network. Defenders can then focus their efforts onpatching the vulnerabilities and configuration errors thatallow the attackers the greatest amount of access. We havecreated a new type of attack graph, the multiple-prerequisitegraph, that scales nearly linearly as the size of a typicalnetwork increases. We have built a prototype system using this graph type. The prototype uses readily availablesource data to automatically compute network reachability,classify vulnerabilities, build the graph, and recommend actions to improve network security. We have tested the proto-type on an operational network with over 250 hosts, whereit helped to discover a previously unknown configuration error. It has processed complex simulated networks with over50,000 hosts in under four minutes.

Annotation

Problem:

• Amount of work necessary to patch every identified vulnerability is often overwhelming for network defenders.
• Identify the bottlenecks and patch these vulnerabilities first to protect all nodes beyond the bottleneck.
• Attack graph: paths an attacker can use to gain access to a targeted network, can be used to achieve this.
• System called NetSPA? .

1. Required source data for graph generation:

• Network topology: user define map of network, firewall ruleset.
• Vulnerability information: Nessus
• Credentials: password

2. Vulnerability Evaluation: prerequisites and postconditions

3. Compute Reachability:

• Reachability matrix: host --> IP/port
• Reachability group: save time and space

4. Compute Attack Graph:

Build MP graph in a breadth-first manner

MP graph uses 3 node types:

• State nodes: represent an attacker’s level of access on a host (root, user, DoS? , other) – circles
• Prerequisite nodes: represent reachability or credential. (here the only prerequisite is reachability) -- rectangles
• Vulnerability nodes: -- triangles

5. Graph Analysis

• Graph simplification

Graphviz – graph visualization software

• Recommendation Text