GENERATING A MULTIPLE-PREREQUISITE ATTACK GRAPH

• US 20090293128A1
• Filed: 06/08/2007
• Published: 11/26/2009
• Est. Priority Date: 06/09/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Ingols, Kyle W., Lippmann, Richard P., Piwowarski, Keith J.
• Granted Patent: US 7,971,252 B2
• Time in Patent Office: Days
• US Class Current: 726/25
• CPC Class Codes: H04L 63/1433 Vulnerability analysis
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227

Abstract

In one aspect, a method to generate an attack graph includes determining if a potential node provides a first precondition equivalent to one of preconditions provided by a group of preexisting nodes on the attack graph. The group of preexisting nodes includes a first state node, a first vulnerability instance node, a first prerequisite node, and a second state node. The method also includes, if the first precondition is equivalent to one of the preconditions provided by the group of preexisting nodes, coupling a current node to a preexisting node providing the precondition equivalent to the first precondition using a first edge and if the first precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes, generating the potential node as a new node on the attack graph and coupling the new node to the current node using a second edge.

Claims

1. A method to generate an attack graph, comprising:

selecting a first state node as a starting point of a cyber attack, the first state node corresponding to access to a first host in a network;

coupling the first state node to a first prerequisite node having a first precondition satisfied by the first state node using a first edge;

coupling the first prerequisite node to a first vulnerability instance node having a second precondition satisfied by the first prerequisite node using a second edge;

coupling the first vulnerability instance node to a second state node having a third precondition satisfied by the first vulnerability instance node using a third edge;

determining if a potential node, having a fourth precondition satisfied by a current node on the attack graph, provides a fifth precondition equivalent to one of preconditions provided by a group of preexisting nodes, the group of preexisting nodes comprising the first state node, the first vulnerability instance node, the first prerequisite node and the second state node;

if the fifth precondition is equivalent to one of the preconditions provided by the group of preexisting nodes, coupling the current node to a preexisting node providing the precondition equivalent to the fifth precondition using a fourth edge; and

if the fifth precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes,

generating the potential node as a new node on the attack graph; and

coupling the new node to the current node using a fifth edge.

2. The method of claim 1 wherein at least one of the first state node or the second state node is coupled to more than one prerequisite node.

3. The method of claim 1, further comprising:

generating a second prerequisite node on the attack graph; and

generating a second vulnerability instance node on the attack graph;

wherein the second vulnerability instance node has preconditions satisfied by the first prerequisite node and the second prerequisite node.

4. The method of claim 1 wherein at least one of the first state node or the second state node satisfies preconditions of more than one prerequisite node.

5. The method of claim 1 wherein the first prerequisite node is at least one of a credential node or a reachability group node.

6. The method of claim 5 wherein the credential node is associated with a credential comprising at least one of a password or passphrase used to gain access to protected data or systems.

7. The method of claim 1 wherein at least one of the first state node or the second state node represents access to a system at a specific level, the specific level comprising at least one of “

other”

level, a user level, or system administrator level.

8. The method of claim 1 further comprising performing the determining for each potential node.

9. The method of claim 1, further comprising:

placing the first state node in a data store; and

if the fifth precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes, placing the potential node in the data store.

10. The method of claim 9 wherein the data store is a queue.

11. The method of claim 1, further comprising selecting a third state node as a second starting point of the cyber attack, the third state node corresponding to access to a third host in the network.

12. A method to generate an attack graph comprising:

determining if a potential node provides a first precondition equivalent to one of preconditions provided by a group of preexisting nodes on the attack graph, the group of preexisting nodes comprising a first state node, a first vulnerability instance node, a first prerequisite node, and a second state node;

if the first precondition is equivalent to one of the preconditions provided by the group of preexisting nodes, coupling a current node on the attack graph to a preexisting node providing the precondition equivalent to the first precondition using a first edge; and

if the first precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes, generating the potential node as a new node on the attack graph and coupling the new node to the current node using a second edge.

13. The method of claim 12, further comprising

selecting the first state node as a starting point of a cyber attack, the first state node corresponding to access to a first host in a network;

coupling the first state node to the first prerequisite node using a first edge; and

coupling the first prerequisite node to the first vulnerability instance node using a second edge.

14. The method of claim 13, further comprising selecting a second state node as a second starting point of the cyber attack, the second state node corresponding to access to a second host in the network.

15. The method of claim 12 wherein the first prerequisite node is at least one of a credential node or a reachability group node.

16. A multiple-prerequisite attack graph, comprising:

a first state node corresponding to access to a first host in a network, the first host being a starting point of a cyber attack on the network;

a first prerequisite node coupled to the first state node by a first edge;

a first vulnerability instance node coupled to the first prerequisite node by a second edge and coupled to a second state node by a third edge, the second state node corresponding to access to a second host in the network, the first vulnerability instance node corresponding to a vulnerability instance on a vulnerable poit on the second host; and

a current node coupled to one of a group of preexisting nodes by a fourth edge, the one of a group of preexisting nodes satisfying a precondition equivalent to a precondition provided by a potential node, the group of preexisting nodes comprising the first state node, the first vulnerability instance node and the first prerequisite node.

17. The graph of claim 16, further comprising a new node coupled to the current node by a fifth edge, the new node providing a precondition not equivalent to preconditions provided by the group of preexisting nodes.

18. The graph of claim 17 wherein the new node is one of a third state node representing one of new higher-level privileges on the second host or access to a new host;

a second vulnerability instance node;

or a second prerequisite node.

19. The graph of claim 16 wherein the first prerequisite node is one of a reachability node or a credential node.

20. The graph of claim 19 wherein the credential node is associated with a credential comprising at least one of a password used to gain access to protected data or systems.

21. An apparatus to generate an attack graph, comprising:

circuitry to;

couple a first state node to a first prerequisite node having a first precondition satisfied by the first state node using a first edge, the first state node being a starting point of a cyber attack and corresponding to access to a first host in a network;

couple the first prerequisite node to a first vulnerability instance node having a second precondition satisfied by the first prerequisite node using a second edge;

couple the first vulnerability instance node to a second state node having a third precondition satisfied by the first vulnerability instance node using a third edge;

determine if a potential node, having a fourth precondition satisfied by a current node on the attack graph, provides a fifth precondition equivalent to preconditions provided by a group of preexisting nodes, the group of preexisting nodes comprising the first state node, the first vulnerability instance node, the first prerequisite node and the second state node;

if the fifth precondition is equivalent to one of the preconditions provided by the group of preexisting nodes, couple the current node to a preexisting node providing the precondition equivalent to the fifth precondition using a fourth edge; and

if the fifth precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes,

generate the potential node as a new node on the attack graph; and

couple the new node to the current node using a fifth edge.

22. The apparatus of claim 21 wherein the circuitry comprises at least one of a processor, a memory, programmable logic or logic gates.

23. The apparatus of claim 21 wherein at least one of the first state node or the second state node is coupled to more than one prerequisite node.

24. The apparatus of claim 21 further comprising circuitry to:

select the first state node as the starting point of the cyber attack; and

select a third state node as a second starting point of the cyber attack, the third state node corresponding to access to a third host in the network.

25. The apparatus of claim 21 further comprising circuitry to:

generate a second prerequisite node on the attack graph; and

generate a second vulnerability instance node on the attack graph;

wherein the second vulnerability instance node has preconditions satisfied by the first prerequisite node and the second prerequisite node.

26. The apparatus of claim 21 wherein at least one of the first state node or the second state node satisfies preconditions of more than one prerequisite node.

27. The apparatus of claim 21 wherein the first prerequisite node is at least one of a credential node or a reachability group node.

28. An article comprising a machine-readable medium that stores executable instructions to generate an attack graph, the instructions causing a machine to:

couple a first state node to a first prerequisite node having a first precondition satisfied by the first state node using a first edge, the first state node being a starting point of a cyber attack and corresponding to access to a first host in a network;

couple the first prerequisite node to a first vulnerability instance node having a second precondition satisfied by the first prerequisite node using a second edge;

couple the first vulnerability instance node to a second state node having a third precondition satisfied by the first vulnerability instance node using a third edge;

determine if a potential node, having a fourth precondition satisfied by a current node on the attack graph, provides a fifth precondition equivalent to preconditions provided by a group of preexisting nodes, the group of preexisting nodes comprising the first state node, the first vulnerability instance node, the first prerequisite node and the second state node;

if the fifth precondition is equivalent to one of the preconditions provided by the group of preexisting nodes, couple the current node to a preexisting node providing the precondition equivalent to the fifth precondition using a fourth edge; and

if the fifth precondition is not equivalent to one of the preconditions provided by the group of preexisting nodes,

generate the potential node as a new node on the attack graph; and

couple the new node to the current node using a fifth edge.

29. The article of claim 28 wherein at least one of the first state node or the second state node is coupled to more than one prerequisite node.

30. The article of claim 28 wherein at least one of the first state node or the second state node satisfies preconditions of more than one prerequisite node.

31. The article of claim 28 wherein the first prerequisite node is at least one of a credential node or a reachability group node.

32. The article of claim 28, further comprising instructions causing a machine to:

select a first state node as the starting point of a cyber attack; and

select a third state node as a second starting point of the cyber attack, the third state node corresponding to access to a third host in a network.