Generating a multiple-prerequisite attack graph

• US 9,344,444 B2
• Filed: 05/10/2011
• Issued: 05/17/2016
• Est. Priority Date: 06/09/2006
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Lippmann, Richard P., Ingols, Kyle W., Piwowarski, Keith J.
• Primary Examiner(s): GOLDBERG, ANDREW C
• Application Number:
  US13/104,454
• Publication Number:
  US 20110231937A1
• Time in Patent Office: 1,834 Days
• Field of Search: 713/164
• US Class Current: 1/1
• 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 computer-implemented method comprising:

in response to a real or simulated cyber attack at a starting node, using a computer to generate an attack graph comprising;

generating a first state node representing the starting node of the cyber attack and corresponding to access to a first host in a network;

generating a first directed edge from the first state node to a first prerequisite node, the first prerequisite node having a first precondition satisfied by the first state node;

generating a second directed edge from the first prerequisite node to a first vulnerability instance node, the first vulnerability instance node having a second precondition satisfied by the first prerequisite node;

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

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; and

using the attack graph to identify the vulnerabilities in the network.

2. The method of claim 1, wherein the processing further comprises generating a fourth directed edge from the current node to a preexisting node providing the precondition equivalent to the fifth precondition in response to the fifth precondition being equivalent to one of the preconditions provided by the group of preexisting nodes.

3. The method of claim 1, wherein the processing further comprises generating the potential node as a new node on the attack graph and generating a fourth directed edge from the new node to the current node in response to the fifth precondition not being equivalent to one of the preconditions provided by the group of preexisting nodes.

4. The method of claim 1 wherein each vulnerability instance node on the attack graph has a single directed edge originating therefrom and connecting the vulnerability instance node to one state node.

5. The method of claim 1 wherein each vulnerability instance node indicates a presence of a vulnerability on a port.

6. The method of claim 1 wherein each prerequisite node represents a prerequisite required to access at least one port associated with a vulnerability instance node.

7. 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.

8. The method of claim 1, wherein the processing further comprises:

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.

9. 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.

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

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

12. 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:

an other level;

a user level;

or a system administrator level.

13. The method of claim 1, wherein the processing further comprises performing the determining for each potential node.

14. The method of claim 1, wherein the processing further comprises:

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.

15. The method of claim 14 wherein the data store is a queue.

16. The method of claim 1, wherein the processing further comprises 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.

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

circuitry to generate an attack graph in response to a real or simulated cyber attack at a starting node comprising circuitry to;

generate a first state node representing the starting point of the cyber attack and corresponding to access to a first host in a network;

generate a first directed edge from the first state node to a first prerequisite node, the first prerequisite node having a first precondition satisfied by the first state node;

generate a second directed edge from the first prerequisite node to a first vulnerability instance node, the first vulnerability instance node having a second precondition satisfied by the first prerequisite node;

generate a third directed edge from the first vulnerability instance node to a second state node, the second state node having a third precondition satisfied by the first vulnerability instance node; and

determine 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,

wherein the attack graph is configured to be used to identify vulnerabilities in a network.

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

19. The apparatus of claim 17, further comprising circuitry to generate a fourth directed edge from the current node to a preexisting node providing the precondition equivalent to the fifth precondition in response to the fifth precondition being equivalent to one of the preconditions provided by the group of preexisting nodes.

20. The apparatus of claim 17, further comprising circuitry to generate the potential node as a new node on the attack graph and generating a fourth directed edge from the new node to the current node in response to the fifth precondition not being equivalent to one of the preconditions provided by the group of preexisting nodes.

21. An article comprising:

a non-transitory machine-readable medium that stores executable instructions to generate an attack graph response to a real or simulated cyber attack at a starting node, the instructions causing a machine to;

generate a first state node representing the starting point of the cyber attack and corresponding to access to a first host in a network;

generate a first directed edge from the first state node to a first prerequisite node, the first prerequisite node having a first precondition satisfied by the first state node;

generate a second directed edge from the first prerequisite node to a first vulnerability instance node, the first vulnerability instance node having a second precondition satisfied by the first prerequisite node;

generate a third directed edge from the first vulnerability instance node to a second state node, the second state node having a third precondition satisfied by the first vulnerability instance node; and

determine 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,

wherein the attack graph is configured to be used to identify vulnerabilities in a network.

22. The apparatus of claim 21, further comprising instructions causing the machine to generate a fourth edge directed from the current node to a preexisting node providing the precondition equivalent to the fifth precondition in response to the fifth precondition being equivalent to one of the preconditions provided by the group of preexisting nodes.

23. The apparatus of claim 21, further comprising instructions causing the machine to generate the potential node as a new node on the attack graph and generating a fourth directed edge from the new node to the current node in response to the fifth precondition not being equivalent to one of the preconditions provided by the group of preexisting nodes.

24. A computer-implemented method comprising:

in response to a real or simulated cyber attack at a starting node, using a computer to generate an attack graph comprising;

generating a first state node representing the starting node of the cyber attack;

generating a first directed edge from the first state node to a first prerequisite node, the first prerequisite node having a first precondition satisfied by the first state node;

generating a second directed edge from the first prerequisite node to a first vulnerability instance node, the first vulnerability instance node having a second precondition satisfied by the first prerequisite node;

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

identifying one or more potential nodes for inclusion in the attack graph; and

determining if a first one of the one or more potential nodes 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; and

using the attack graph to identify the vulnerabilities in a network.

25. The method of claim 24 wherein the processing further comprises, in response to the fifth precondition being equivalent to one of the preconditions provided by the group of preexisting nodes, constructing a fourth directed from the current node to a preexisting node providing the precondition equivalent to the fifth precondition.

26. The method of claim 24 wherein the processing further comprises in response to the fifth precondition not being 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 constructing a fifth directed edge from the new node to the current node.

27. The method of claim 24 wherein each vulnerability instance node on the attack graph has a single directed edge originating therefrom and connecting the vulnerability instance node to one state node.

28. The method of claim 27 wherein each vulnerability instance node indicates a presence of a vulnerability on a port.

29. The method of claim 28 wherein each prerequisite node represents a prerequisite required to access at least one port associated with a vulnerability instance node.

30. A computer implemented method comprising:

in response to a real or simulated cyber attack at a starting node, using a computer to generate an attack graph comprising;

determining if a potential node being considered for inclusion in the attack graph includes a precondition equivalent to one or more of a plurality of preconditions provided by a group of preexisting nodes on the attack graph, the group of preexisting nodes comprising a first state node, at least one vulnerability instance node, at least one 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 wherein each vulnerability instance node indicating a presence of a vulnerability, each prerequisite node representing a prerequisite required to access at least one port associated with a vulnerability instance node; and

using the attack graph to identify the vulnerabilities in a network.

31. The computer implemented method of claim 30, wherein in response to the first precondition being equivalent to one of the preconditions provided by the group of preexisting nodes, the processing further comprises 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

wherein in response to the first precondition not being equivalent to one of the preconditions provided by the group of preexisting nodes, the processing further comprise 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.