Generating a multiple-prerequisite attack graph

• US 7,971,252 B2
• Filed: 06/08/2007
• Issued: 06/28/2011
• 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.
• Primary Examiner(s): Popham; Jeffrey D
• Assistant Examiner(s): Reddy; Sunita
• Application Number:
  US11/760,158
• Publication Number:
  US 20090293128A1
• Time in Patent Office: 1,481 Days
• Field of Search: 726/25, 726/23, 707/999.1
• US Class Current: 726/23
• 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:

using a computer processor for;

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 by generating a first directed edge from the first state node to the prerequisite node;

coupling the first prerequisite node to a first vulnerability instance node having a second precondition satisfied by the first prerequisite node by generating a second directed edge from the first prerequisite node to the first vulnerability instance node, each vulnerability instance node on the attack graph having a single directed edge from the vulnerability instance node to exactly one state node, each vulnerability instance node indicating a presence of a vulnerability on a port, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance node;

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

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 by generating a fourth directed edge from the current node to the preexisting node; 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 by generating a fifth directed edge from the current node to the new node.

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 using a computer processor for:

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 using a computer processor for:

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 using a computer processor for 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. The method of claim 1 wherein one or more of the edges are contentless.

13. A method to generate an attack graph comprising:

using a computer processor for;

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, each vulnerability instance node on the attack graph having a single directed edge from the vulnerability instance node to exactly one state node, each vulnerability instance node indicating a presence of a vulnerability on a port, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance 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 by generating a first directed edge from the current node to the preexisting node; 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 by generating a second directed edge from the current node to the new node.

14. The method of claim 13, further comprising using a computer processor for:

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.

15. The method of claim 14, further comprising using a computer processor for 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.

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

17. 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 directed edge from the first state node to the first prerequisite node;

a first vulnerability instance node coupled to the first prerequisite node by a second directed edge from the first prerequisite node to the first vulnerability instance node and coupled to a second state node by a third directed edge from the first vulnerability instance node to the second state node, the second state node corresponding to access to a second host in the network, each vulnerability instance node on the attack graph having a single directed edge from the vulnerability instance node points to exactly one state node, each vulnerability instance node indicating a presence of a vulnerability on a port, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance node; and

a current node coupled to one of a group of preexisting nodes by a fourth directed edge from the current node to the one of the group of preexisting nodes, 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,

wherein the multiple-prerequisite attack graph is rendered by a computer processor.

18. The graph of claim 17, 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.

19. The graph of claim 18 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.

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

21. The graph of claim 20 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.

22. 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 by generating a first directed edge from the first state node to the first prerequisite node, 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 by generating a second directed edge from the first prerequisite node to the first vulnerability instance node, each vulnerability instance node on the attack graph having a single directed edge from the vulnerability instance node to exactly one state node, each vulnerability instance node indicating a presence of a vulnerability on a port, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance node;

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

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 by generating a fourth directed edge from the current node to the preexisting node; 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 by generating a fifth directed edge from the current node to the new node.

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

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

25. The apparatus of claim 22 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.

26. The apparatus of claim 22, 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.

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

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

29. An article comprising:

a non-transitory 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 by generating a first directed edge from the first state node to the first prerequisite node, 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 by generating a second directed edge from the first prerequisite node to the first vulnerability instance node, each vulnerability instance node on the attack graph having a single directed edge from the vulnerability instance node to exactly one state node, each vulnerability instance node indicating a presence of a vulnerability on a port, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance node;

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

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 by generating a fourth directed edge from the current node to the preexisting node; 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 by generating a fifth directed edge from the current node to the new node.

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

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

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

33. The article of claim 29, 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.