Network security planning architecture

• US 7,194,769 B2
• Filed: 12/11/2003
• Issued: 03/20/2007
• Est. Priority Date: 12/11/2003
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Ingols, Kyle W., Scott, Chris, Lippmann, Richard, Kratkiewicz, Kendra, Artz, Michael
• Primary Examiner(s): Moise; Emmanuel L.
• Assistant Examiner(s): PYZOCHA, MICHAEL J
• Application Number:
  US10/734,083
• Publication Number:
  US 20050138413A1
• Time in Patent Office: 1,195 Days
• Field of Search: 713/201, 726/25, 726/1
• US Class Current: 726/25
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: H04L 2463/141 Denial of service attacks against endpoints in a network
• CPC Class Codes: H04L 63/1433 Vulnerability analysis

Abstract

Described are techniques used for assessing the security of a network. Pruned attack trees are generated using a forward chaining, breadth-first technique representing the attack paths of a possible attacker in the network. A vulnerability score is determined for each network and attacker starting point using attack loss values assigned to each host and information extracted from the attack tree(s) concerning compromised hosts. Different hypothetical alternatives may be evaluated to improve security of the network and each alternative may be evaluated by recomputing the network vulnerability score and comparing the recomputed score to the original network vulnerability score. Also disclosed is a method for determining end-to-end connectivity of a network. The resulting end-to-end connectivity information is used in generating the pruned attack tree.

Claims

1. A method comprising:

using a computer to generate a pruned attack tree, using the computer comprises;

designating a root node of the pruned attack tree, the root node representing a starting point of an attack; and

for a current node included in the pruned attack tree, connecting a resulting node having a first state, representing a first host and access to the first host, and an edge, having a first transition value corresponding to one of a plurality of vulnerability types, to the current node if determined that;

another edge, having a second transition value corresponding to one of the plurality of vulnerability types, does not connect an ancestor of the current node to another node having a second state equivalent to the first state; and

the second transition value is equal to the first transition value.

2. The method of claim 1 wherein the pruned attack tree is a tree including n levels, the root node is at level 0, n being at least 0.

3. The method of claim 2 wherein the first state represents at least one of:

an attacker state including the first host and an attacker access level on the first host, and a network state.

4. The method of claim 3 wherein the edge from the current node at a level x to the resulting node at a level x+1 represents an action while in the first state including a first attacker state corresponding to the current node resulting in the second state including a second attacker state.

5. The method of claim 4 wherein the first attacker state represents the first host and a first attacker access level on the first host, and the second attacker state represents at least one of:

a second host and a second attacker access level on the second host, and the first host and a second attacker access level on the first host; and

wherein the second attacker access level represents at least one of;

an increase in attacker privilege, an increase in attacker access, and an increase in attacker knowledge.

6. The method of claim 5 wherein using the computer further comprises evaluating each action that exploits a vulnerability of a host in accordance with connectivity data.

7. The method of claim 6 wherein the connectivity data, the each action, and the vulnerability are stored in a database.

8. The method of claim 1 wherein the plurality of vulnerability types includes vulnerabilities being indicative of providing a same access level on a host.

9. The method of claim 1 wherein the current node is at a level n, and the ancestors of the current node are located at levels in the pruned attack tree at a level less than n.

10. The method of claim 9 wherein the pruned attack tree is generated using a breadth first search technique in which nodes are added at an nth level prior to adding any node from level n+1.

11. The method of claim 1 wherein computer attack paths for a network are represented using pruned attack trees, the pruned attack trees representing the computer attack pats originating from a unique starting point.

12. The method of claim 1 wherein the root node is one of:

from within a network and external to a network.

13. The method of claim 1 wherein using the computer further comprises:

determining which hosts in the network are equivalent forming a group; and

representing the group with a single host.

14. The method of claim 1 wherein using the computer further comprises using connectivity information to generate the pruned attack tree, the connectivity information including a connection between two endpoints representing elements of a configuration of the network.

15. The method of claim 14 wherein the connectivity information includes physical connectivity between network interfaces and logical connectivity through network communications protocols.

16. The method of claim 14 wherein the connection is associated with a path including one or more hops.

17. The method of claim 16 wherein the one or more hops is associated with at least one of:

a filtering rule, a translation rule, and an interface of a host in the network.

18. The method of claim 16 wherein at least one of the endpoints is associated with a vulnerability on the at least one endpoint.

19. The method of claim 18 Wherein the vulnerability has an associated action resulting in exploitation of the vulnerability.

20. The method of claim 19 wherein the associated action is related to an entity representing at least one of:

an attacker access level, attacker knowledge level, a change to a network state.

21. The method of claim 1 wherein using the computer further comprises:

using connectivity data representing connectivity between pairs of endpoints in the network; and

automatically generating the connectivity data in accordance with at least one translation rule, at least one filtering rule, and network configuration information.

22. The method of claim 21 wherein the at least one translation rule includes at least one of:

an address translation rule and a port translation rule.

23. The method of claim 21 wherein using the computer further comprises:

selecting at least one address of a starting point of a computer attack using at least one rule; and

determining a portion of the connectivity data using the at least one address.

24. The method of claim 23 wherein the at least one rule includes at least one of a filtering rule and a translation rule.

25. The method of claim 23 wherein the at least one address is used in the generating to represent an alternate connectivity of a host.

26. The method of claim 23 wherein the at least one address is one of an address in accordance with a communications protocol and an address associated with the network.

27. An article comprising a machine-readable medium that stores executable instructions for generating a pruned attack tree, the instructions causing a machine to:

designate a root node of the pruned attack tree, the root node representing a starting point of an attack; and

for a current node included in the pruned attack tree, connecting a resulting node having a first state, representing a first host and access to the first host, and an edge, having a first transition value corresponding to one of a plurality of vulnerability types, to the current node if determined that;

another edge, having a second transition value corresponding to one of the plurality of vulnerability types, does not connect an ancestor of the current node to another node having a second state equivalent to the first state; and

the second transition value is equal to the first transition value.

28. The article of claim 27 wherein the pruned attack tree is a tree including n levels, the root node being at level 0, n being at least 0.

29. The article of claim 28 wherein the first state represents at least one of:

an attacker state including the first host and an attacker access level on the first host, and a network state.

30. The article of claim 29 wherein the edge from the current node at a level x to the resulting node at a level x+1 represents an action while in a first state including a first attacker state corresponding to the current node resulting in the second state including a second attacker state.

31. The article of claim 30 wherein the first attacker state represents the first host and a first attacker access level on the first host, and the second attacker state represents at least one of:

a second host and a second attacker access level on the second host and the first host and a second attacker access level on the first host wherein the second attacker access level represents at least one of;

an increase in attacker privilege, an increase in attacker access, and an increase in attacker knowledge.

32. The article of claim 31, further comprising instructions causing a machine to evaluate each action that exploits a vulnerability of a host in accordance with connectivity data.

33. The article of claim 32, further comprising instructions causing the machine to store the connectivity data, the each action, and the vulnerability in a database prior to generating the pruned attack free.

34. The article of claim 27 wherein the plurality of vulnerability types includes vulnerabilities being indicative of providing a same access level on a host.

35. The article of claim 27 wherein the current node is at a level n, and the ancestors of the current node are located at levels in the pruned attack tree at a level less than n.

36. The article of claim 35, further comprising executable code that generates the pruned attack tree using a breadth first search technique in which nodes are added to the pruned attack tree at an nth level prior to adding any node from level n+1 to the pruned attack tree.

37. The article of claim 27 wherein computer attack paths for a network are represented using pruned attack trees, the pruned attack trees representing computer attack paths originating from a unique starting point.

38. The article of claim 27 wherein the starting point is one of:

from within a network and external to a network.

39. The article of claim 27, further comprising instructions causing the machine to:

determine which hosts in the network are equivalent forming a group; and

represent the group with a single host.

40. The article of claim 32 further comprising instructions causing a machine to use connectivity information to generate the pruned attack tree, the connectivity information including a connection between two endpoints representing elements of a configuration of the network.

41. The article of claim 40 wherein the connectivity information includes physical connectivity between network interfaces and logical connectivity through network communications protocols.

42. The article of claim 40 wherein the connection is associated with a path including one or more hops.

43. The article of claim 42 wherein the one or more hops is associated with at least one of:

a filtering rule, a translation rule, and an interface of a host in the network.

44. The article of claim 40 wherein at least one of the endpoints is associated with a vulnerability on the at least one endpoint.

45. The article of claim 44 wherein the vulnerability has an associated action resulting in exploitation of the vulnerability.

46. The article of claim 45 wherein the associated action is related to an entity representing at least one of:

an attacker access level, attacker knowledge level, a change to a network state.

47. The article of claim 27 wherein connectivity data representing connectivity between pairs of endpoints in the network is used by the executable code that generates, and further comprising instructions causing a machine to:

automatically generates the connectivity data in accordance with at least one translation rule, at least one filtering rule, and network configuration information.

48. The article of claim 47 wherein the at least one translation rule includes at least one of:

an address translation rule and a port translation rule.

49. The article of claim 47, further comprising instructions causing the machine to select at least one address of a starting point of a computer attack using at least one rule;

and determine a portion of the connectivity data using the at least one address.

50. The article of claim 49 wherein the at least one rule includes at least one of a filtering rule and a translation rule.

51. The article of claim 50 wherein the at least one address is used in the generating to represent an alternate connectivity of a host.

52. The article of claim 51 wherein the at least one address is one of an address in accordance with a communications protocol and an address associated with the network.

53. The article of claim 27, further comprising instructions causing the machine to use vulnerability data to determine at least one of:

requirements for an action, an attacker state resulting from an action, and a network state resulting from an action,

wherein the requirements include a locality describing whether a vulnerability can be exploited remotely over a network or locally on a host, the resulting attacker state includes an effect describing an access level or privilege or knowledge after an exploit of a vulnerability, and the resulting network state includes a denial of service describing a loss of service on a host after an exploit of a vulnerability.