Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
7194769
Lippmann , ; et al.
March 20, 2007
Title
Network security planning architecture
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.
Inventors:
Lippmann; Richard
(Wayland,
MA
)
, Scott; Chris
(Newton,
MA
)
, Kratkiewicz; Kendra
(Shirley,
MA
)
, Artz; Michael
(Catonsville,
MD
)
, Ingols; Kyle W.
(Arlington,
MA
)
Assignee:
Massachusetts Institute of Technology
(Cambridge,
MA
)
Appl. No.:
10/734,083
Filed:
December 11, 2003
PCT Pub Date:
March 21, 2007
Current U.S. Class:
726/25
726/1
Current International Class:
G06F 11/30 (20060101)
Field of Search:
713/201 726/25,1
U.S. Patent Documents
20020184504
December 2002
Hughes
20030110288
June 2003
Ramanujan et al.
20030149777
August 2003
Adler
20040199576
October 2004
Tan
20060015943
January 2006
Mahieu
5313616
May 1994
Cline et al.
5850516
December 1998
Schneier
6836888
December 2004
Basu et al.
6952779
October 2005
Cohen et al.
7013395
March 2006
Swiler et al.
Foreign Patent Documents
WO 2004/031953
Apr., 2004
WO
Other References
Steffan, Jab et al "Collaborative Attack Modeling," 2002, pp. 1-10. cited by examiner .
Tidewell et al., "Modeling Internet Attacks," Jun. 5-6, 2001, pp. 54-59. cited by examiner .
IT Guru: Intelligent Network Management for Enterprises (website: www.opnet.com/products/itguru/home.html), 2003 OPNET Technologies, Inc. cited by other .
IT Guru: Intelligent Network Management for Enterprises, OPNET Technologies, Inc. (website: www.opnet.com). cited by other .
Scalable, Graph-Based Network Vulnerability Analysis, by Paul Ammann, Duminda Wijesekera and Saket Kaushik, CCS'02, Nov. 18-22, 2002, Washington, DC. cited by other .
Attack Trees, Dr. Dobb's Journal Dec. 1999--Modeling Security Threats by Bruce Schneier. cited by other .
Compter Attack Graph Generation Tool by Laura P. Swiler Cynthia Phillips. David Ellis and Stefan Chakerian, Sandia National Laboratories, Albuquerque, NM. cited by other .
Automated Generation and Analysis of Attack Graphs by Oleg Sheyner, Joshua Haines, Somesh JHA, Richard Lippmann and Jeannette M. Wing, Proceedings of the 2002 IEEE Symposium on Security and Privacy (S&P'02). cited by oth- er .
NetSPA: A Network Security Planning Architecture by Michael Lyle Artz, S.B., Computer Science and Engineering, Massachusetts Institute of Technology (2001). cited by other .
Computer-Attack Graph Generation Tool, Laura P. Swiler et al., Sandia National Laboratories, 2001 IEEE, pp. 307-321. cited by other .
Scalable, Graph-Based Network Vulnerability Analysis, Paul Ammann et al., ACM Nov. 2002, pp. 217-224. cited by other.~
Primary Examiner:
Moise; Emmanuel L.
Assistant Examiner:
Pyzocha; Michael
Attorney, Agent or Firm:
Daly, Crowley, Mofford & Durkee, LLP
Government Interests:
STATEMENT OF GOVERNMENT INTEREST
The invention was made with Government support under contract No.
F19628-00-C-0002 by the Department of the Air Force. The Government has
certain rights in the invention.
Claims
What is claimed is:
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.
Description
BACKGROUND
1. Technical Field
This application generally relates to networks, and more particularly to network security.
2. Description of Related Art
Assessing the security of a computer network is a complex problem that depends on one or more factors that may vary with each network. Such factors include, for example, network topology, services and vulnerabilities of each host, a firewall policy, and the like. Vulnerabilities may be characterized as weaknesses within a network. Vulnerabilities in a host may be due to weaknesses in its associated hardware, software, and/or configuration by which an attacker may improperly access, perform an unauthorized operation upon, or otherwise compromise, a network.
Gathering and analyzing information for assessing the security of a network manually may be a daunting task as well as error prone. Additionally, this may be a costly option since a manual reassessment may need to be performed each time there is a change, such as, for example, a change in network topology or system software, the discovery of a new vulnerability, and the like.
Another technique for assessing network security is to use vulnerability scanners. However, existing vulnerability scanners provide information about services and vulnerabilities present on individual hosts and have a drawback of failing to take into account the impact of a network configuration. Additionally, the vulnerability scanners may not provide additional functionality that may be desirable in assessing network security, such as, for example, taking into account the removal or other variation of a vulnerability in order to assess the impact of the vulnerability removal. Such scanners may also fail to consider particular factors such as, for example, network topology and firewall rule sets.
It may be desirable to have an automated technique that efficiently identifies attack paths in a network by which an attacker may compromise a network. It may be desirable that this technique take into account the impact of a vulnerability from one host or node on the entire network providing a more global assessment. The technique may desirably consider possible attack paths of an attacker from within a network as well as external to the network. It may also be desirable to perform a risk assessment and accordingly provide a prioritized list of security improvements in an automated fashion.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention is a method for representing at least one computer attack path in a network comprising: receiving a starting point of a computer attack with respect to said network; and generating a pruned augmented attack tree representing at least one attack path possible from said starting point, wherein, said starting point is a root of said pruned augmented attack tree, for a current node being evaluated as part of said generating, a resulting node and an edge connecting said current node to said resulting node are added to said pruned augmented attack tree if said edge and said resulting node are not already included in said pruned augmented attack tree with said edge connecting an ancestor of the current node to an instance of the resulting node. The pruned augmented attack tree may be a tree including n levels in which the starting point is a root of said tree at level 0, n being at least 0. A node in said pruned augmented attack tree may represent information about at least one of: an attacker state including a host and an attacker access level on said host, and a network state. An edge from a first node at level x to a second node at level x+1 may represent an action while in a first state including a first attacker state corresponding to said first node resulting in a second state including a second attacker state. The action may exploit a vulnerability on a host in said network. The first attacker state may represent a first host and a first attacker access level on said first host, and said second attacker state may represent at least one of: a second host and a second attacker access level on said second host, and said first host and a second attacker access level on said first host wherein said 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. The current node may be at a level n, and said ancestors of said current node may be located at levels in said pruned augmented attack tree at a level less than n. The pruned augmented attack tree may be generated using a breadth first search technique in which nodes are added to said pruned augmented attack tree at an nth level prior to adding any node from level n+1 to said pruned augmented attack tree. A plurality of computer attack paths for said network may be represented using a plurality of pruned augmented attack trees, each of said pruned augmented attack trees representing computer attack paths originating from a unique starting point. The starting point may be one of: from within said network and external to said network. The method may also include: evaluating each action that exploits a vulnerability of a host in accordance with connectivity data. The connectivity data, each action, and the vulnerability may be stored in a database and determined prior to performing said generating. The pruned augmented attack tree may have a property that a resulting node at a level "n+1" and an edge connecting a current node at level "n" to said resulting node are included in said pruned augmented attack tree if said edge and said resulting node are not already included in said pruned augmented attack tree with said edge connecting an ancestor of the current node to an instance of the resulting node, said ancestor being a node at a level "x"<"n", and said instance of the resulting node being at level "x+1". The method may also include: determining which hosts in said network are equivalent forming a group; and representing said group with a single host. A first host may be equivalent to a second host if said first and second hosts have a same set of one or more vulnerabilities on a same set of one or more endpoints, said first and second hosts are not administrative hosts, said first and second hosts are not gateways, said first and second hosts have equivalent attack loss values, and said first and second hosts have equivalent connectivity. The generating step may use connectivity information, said connectivity information including a connection between two endpoints representing elements of a configuration of said network. The connectivity information may include physical connectivity between network interfaces and logical connectivity through network communications protocols. The connection may be associated with a path including one or more hops. Each of the one or more hops may be associated with at least one of: a filtering rule, a translation rule, and an interface of a host in said network. At least one of the endpoints may be associated with a vulnerability on said at least one endpoint. The vulnerability may have an associated action resulting in exploitation of said vulnerability. The associated action may be related to an entity representing at least one of: an attacker access level, attacker knowledge level, a change to a network state. The pruned augmented attack tree may be used to determine an effect of preventing at least one action. The method may also include: modifying said pruned augmented attack tree in accordance with eliminating at least one action in connection with a vulnerability associated with said host producing a modified augmented attack tree; and evaluating said modified augmented attack tree. The connectivity data may represent connectivity between pairs of endpoints in said network and may be used in said generating, and the method further include: automatically generating said connectivity data in accordance with at least one translation rule, at least one filtering rule, and network configuration information. The at least one translation rule may include at least one of: an address translation rule and a port translation rule. The method may also include: selecting at least one address of a starting point of a computer attack using at least one rule; and determining a portion of said connectivity data using said at least one address. The at least one rule may include at least one of a filtering rule and a translation rule. The at least one address may be used in said generating to represent an alternate connectivity of a host. The address may be one of an address in accordance with a communications protocol and an address associated with said network. The method may also include: using 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, where said requirements include a locality describing whether a vulnerability can be exploited remotely over a network or locally on a host, said resulting attacker state includes an effect describing an access level or privilege or knowledge after an exploit of a vulnerability, and said resulting network state includes a denial of service describing a loss of service on a host after an exploit of a vulnerability.
In accordance with another aspect of the invention is a method for assessing security of a network comprising: determining a network vulnerability score in accordance with first attack loss values for all hosts within said network that are compromised and second attack loss values associated with all hosts in said network. The method may also include determining attack loss values for all hosts compromised in all attack trees of said network, each attack tree representing at least one computer attack path originating from a unique starting point. The method may also include determining attack loss values for all hosts in said network. The method may further include: adding said attack loss values for all hosts compromised in all attack trees of said network producing a first sum; adding said attack loss values for all hosts in said network producing a second sum; and determining a ratio of said first sum to said second sum. The method may include: receiving input for a proposed change to said network; and assessing said proposed change to said network, said assessing including determining a revised value for said network vulnerability score. The attack loss values may be assigned to each host in said network in accordance with a value if said host is compromised. The attack loss value for said each host may be determined using at least one criteria selected from: criticality of data on said each host, criticality of data available through said each host, criticality of a service available at said each host, and criticality of a service available through said each host. The network vulnerability score may be represented using a ratio of a first sum of attack loss values for all hosts compromised in one or more pruned attack trees to a second sum of attack loss values for all hosts in said network. An attack tree vulnerability score may be determined for each attack tree of said network and each attack tree vulnerability score may be represented as a ratio of a first sum of attack loss values of all hosts compromised in said each attack tree to a second sum of attack loss values of all hosts in said network. The method may also include: determining a first network vulnerability score for said network without said proposed change; determining a second network vulnerability score for said network with said proposed change; and using said first and second network vulnerability scores in evaluating said proposed change with another proposed change. The method may also include: providing a prioritized set of one or more proposed changes to said network in accordance with a network vulnerability score associated with each of said one or more proposed changes. The method may include using one or more pruned attack trees in evaluating each of said one or more proposed changes. One of said proposed changes may include eliminating at least one vulnerability at a host in said network. All attack trees of said network may be pruned augmented attack trees, each of said pruned augmented attack tree having a property that a resulting node at a level "n+1" and an edge connecting a current node at level "n" to said resulting node are included in said each pruned augmented attack tree if said edge and said resulting node are not already included in said each pruned augmented attack tree with said edge connecting an ancestor of the current node to an instance of the resulting node, said ancestor being a node at a level "x"<"n", and said instance of the resulting node being at level "x+1".
In accordance with another aspect of the invention is a method of determining connectivity for a network using connectivity data comprising: receiving at least one of: a rule set of one or more rules and information obtained from a network scanner; determining at least one address of a host in said network using at least one of said rule set and said information obtained from a network scanner, said connectivity data including said at least one address of said host; and determining connectivity between pairs of endpoints in said network using said connectivity data. The method may also include determining whether connectivity is permitted in accordance with said rule set for a path between a pair of endpoints, said path including said host. The rule set may include at least one of a filtering rule, a port translation rule, and an address translation rule. The method may also include: using said at least one address in modeling a change of a network address of a host after said host is compromised. The connectivity data may be used in generating an attack tree. The at least one address may be used in said generating to represent an alternate connectivity of a host. The address may be one of an address in accordance with a communications protocol and an address associated with said network. The determining at least one address of a host further may also include: examining at least one of: a filtering rule and an address translation rule; determining an initial list of addresses; sorting said initial list in accordance with address specificity wherein a first address in said initial list is more specific than a second address in said initial list if said first address specifies a smaller address range than said second address; and forming a final list of addresses associated with said host, wherein, addresses in said initial list are examined in order from most to least specific, for each address in said initial list, said address is added to said final list if said each address is a specific address, for each address in said initial list that specifies a range an address is selected from the range for inclusion in the final list if the selected address is not already in the final list or included in a range of a more specific address in said initial list. The determining connectivity may also include: evaluating connectivity between a source endpoint and each target endpoint within a same subnet in said network; and evaluating connectivity between a source endpoint and each target endpoint within other subnets in said network. The method may also include evaluating connectivity between each pair of possible endpoints wherein all connectivity between a source and all possible target endpoints are explored prior to advancing to the next possible source endpoint.
In accordance with another aspect of the invention is a method for representing at least one computer attack path in a network comprising: receiving a starting point of a computer attack with respect to said network; and generating a data structure representing at least one attack path possible from said starting point, wherein, said starting point is a node in said data structure, and for a current node being evaluated as part of said generating, a resulting node and an edge connecting said current node to said resulting node are added to said data structure if said edge and said resulting node are not already included in said data structure with said edge connecting a predecessor of the current node to an instance of the resulting node, wherein said predecessor is a node along a path from the starting node to a node immediately preceding the current node. The data structure may be a representation of at least one of: an augmented rooted tree, a non augmented rooted tree, a free tree, a directed acyclic graph, an undirected graph, a graph and a tree. The data structure may include at least one of: an array, a linked list, a hash table, an adjacency list, and an adjacency matrix.
In accordance with another aspect of the invention is a computer program product for representing at least one computer attack path in a network comprising executable code that: receives a starting point of a computer attack with respect to said network; and generates a pruned augmented attack tree representing at least one attack path possible from said starting point, wherein, said starting point is a root of said pruned augmented attack tree, and for a current node being evaluated, a resulting node and an edge connecting said current node to said resulting node are added to said pruned augmented attack tree if said edge and said resulting node are not already included in said pruned augmented attack tree with said edge connecting an ancestor of the current node to an instance of the resulting node. The pruned augmented attack tree may be a tree including n levels, said starting point being a root of said tree at level 0, n being at least 0. A node in said pruned augmented attack tree may represent information about at least one of: an attacker state including a host and an attacker access level on said host, and a network state. An edge from a first node at level x to a second node at level x+1 may represent an action while in a first state including a first attacker state corresponding to said first node resulting in a second state including a second attacker state. The action may exploit a vulnerability on a host in said network. The first attacker state may represent a first host and a first attacker access level on said first host, and said second attacker state may represent at least one of: a second host and a second attacker access level on said second host, and said first host and a second attacker access level on said first host wherein said 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. The current node may be at a level n, and said ancestors of said current node may be located at levels in said pruned augmented attack tree at a level less than n. The computer program product may also include executable code that generates said pruned augmented attack tree using a breadth first search technique in which nodes are added to said pruned augmented attack tree at an nth level prior to adding any node from level n+1 to said pruned augmented attack tree. A plurality of computer attack paths for said network may be represented using a plurality of pruned augmented attack trees, each of said pruned augmented attack trees representing computer attack paths originating from a unique starting point. The starting point may be one of: from within said network and external to said network. The computer program product may also include executable code that evaluates each action that exploits a vulnerability of a host in accordance with connectivity data. The computer program product may include executable code that stores said connectivity data, said each action, and said vulnerability in a database prior to generating said pruned augmented attack tree. The pruned augmented attack tree may have a property that a resulting node at a level "n+1" and an edge connecting a current node at level "n" to said resulting node are included in said pruned augmented attack tree if said edge and said resulting node are not already included in said pruned augmented attack tree with said edge connecting an ancestor of the current node to an instance of the resulting node, said ancestor being a node at a level "x"<"n", and said instance of the resulting node being at level "x+1". The computer program product may also include executable code that: determines which hosts in said network are equivalent forming a group; and represents said group with a single host. A first host may be equivalent to a second host if said first and second hosts have a same set of one or more vulnerabilities on a same set of one or more endpoints, said first and second hosts are not administrative hosts, said first and second hosts are not gateways, said first and second hosts have equivalent attack loss values; and said first and second hosts have equivalent connectivity. The executable code that generates said pruned augmented attack tree may use connectivity information, said connectivity information including a connection between two endpoints representing elements of a configuration of said network. The connectivity information may include physical connectivity between network interfaces and logical connectivity through network communications protocols. The connection may be associated with a path including one or more hops. Each of said one or more hops may be associated with at least one of: a filtering rule, a translation rule, and an interface of a host in said network. At least one of said endpoints may be associated with a vulnerability on said at least one endpoint. The vulnerability may have an associated action resulting in exploitation of said vulnerability. The associated action may be related to an entity representing at least one of: an attacker access level, attacker knowledge level, a change to a network state. The computer program product may also include executable code that uses said pruned augmented attack tree to determine an effect of preventing at least one action. The computer program product may also include executable code that: modifies said pruned augmented attack tree in accordance with eliminating at least one action in connection with a vulnerability associated with said host producing a modified augmented attack tree; and evaluates said modified augmented attack tree. Connectivity data representing connectivity between pairs of endpoints in said network may be used by said executable code that generates, and the computer program product may also include executable code that automatically generates said connectivity data in accordance with at least one translation rule, at least one filtering rule, and network configuration information. The at least one translation rule may include at least one of: an address translation rule and a port translation rule. The computer program product may also include executable code that: selects at least one address of a starting point of a computer attack using at least one rule; and determines a portion of said connectivity data using said at least one address. The at least one rule may include at least one of a filtering rule and a translation rule. The at least one address may be used in said generating to represent an alternate connectivity of a host. The address may be one of an address in accordance with a communications protocol and an address associated with said network. The computer program product may also include executable code that uses 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, where said requirements include a locality describing whether a vulnerability can be exploited remotely over a network or locally on a host, said resulting attacker state includes an effect describing an access level or privilege or knowledge after an exploit of a vulnerability, and said resulting network state includes a denial of service describing a loss of service on a host after an exploit of a vulnerability.
In accordance with another aspect of the invention is a computer program product that assesses security of a network comprising executable code that: determines a network vulnerability score in accordance with first attack loss values for all hosts within said network that are compromised and second attack loss values associated with all hosts in said network. The computer program product may also include executable code that determines attack loss values for all hosts compromised in all attack trees of said network, each attack tree representing at least one computer attack path originating from a unique starting point. The computer program product may also include executable code that determines attack loss values for all hosts in said network. The computer program product may also include executable code that: adds said attack loss values for all hosts compromised in all attack trees of said network producing a first sum; adds said attack loss values for all hosts in said network producing a second sum; and determines a ratio of said first sum to said second sum. The computer program product may also include executable code that: receives input for a proposed change to said network; and assesses said proposed change to said network, said executable code that assesses including executable code that determines a revised value for said network vulnerability score. The attack loss values may be assigned to each host in said network in accordance with a value if said host is compromised. The attack loss value for said each host may be determined using at least one criteria selected from: criticality of data on said each host, criticality of data available through said each host, criticality of a service available at said each host, and criticality of a service available through said each host. The network vulnerability score may be represented using a ratio of a first sum of attack loss values for all hosts compromised in one or more pruned attack trees to a second sum of attack loss values for all hosts in said network. An attack tree vulnerability score may be determined for each attack tree of said network and each attack tree vulnerability score may be represented as a ratio of a first sum of attack loss values of all hosts compromised in said each attack tree to a second sum of attack loss values of all hosts in said network. The computer program product may include executable code that: determines a first network vulnerability score for said network without said proposed change; determines a second network vulnerability score for said network with said proposed change; and uses said first and second network vulnerability scores in evaluating said proposed change with another proposed change. The computer program product may also include executable code that provides a prioritized set of one or more proposed changes to said network in accordance with a network vulnerability score associated with each of said one or more proposed changes. The computer program product may include executable code that uses one or more pruned attack trees in evaluating each of said one or more proposed changes. One of said proposed changes may include eliminating at least one vulnerability at a host in said network. All attack trees of said network may be pruned augmented attack trees, each of said pruned augmented attack tree having a property that a resulting node at a level "n+1" and an edge connecting a current node at level "n" to said resulting node are included in said each pruned augmented attack tree if said edge and said resulting node are not already included in said each pruned augmented attack tree with said edge connecting an ancestor of the current node to an instance of the resulting node, said ancestor being a node at a level "x"<"n", and said instance of the resulting node being at level "x+1".
In accordance with another aspect of the invention is a computer program product that determines connectivity for a network using connectivity data comprising executable code that: receives at least one of: a rule set of one or more rules and information obtained from a network scanner; determines at least one address of a host in said network using at least one of said rule set and said information obtained from a network scanner, said connectivity data including said at least one address of said host; and determines connectivity between pairs of endpoints in said network using said connectivity data. The computer program product may also include executable code that determines whether connectivity is permitted in accordance with said rule set for a path between a pair of endpoints, said path including said host. The rule set may include at least one of a filtering rule, a port translation rule, and an address translation rule. The computer program may also include executable code that uses said at least one address in modeling a change of a network address of a host after said host is compromised. The connectivity data may be used by executable code that generates an attack tree. The at least one address may be used in said generating to represent an alternate connectivity of a host. The address may be one of an address in accordance with a communications protocol and an address associated with said network. The executable code that determines at least one address of a host may further comprise executable code that: examines at least one of: a filtering rule and an address translation rule; determines an initial list of addresses; sorts said initial list in accordance with address specificity wherein a first address in said initial list is more specific than a second address in said initial list if said first address specifies a smaller address range than said second address; and forms a final list of addresses associated with said host, wherein, addresses in said initial list are examined in order from most to least specific, for each address in said initial list, said address is added to said final list if said each address is a specific address, for each address in said initial list that specifies a range an address is selected from the range for inclusion in the final list if the selected address is not already in the final list or included in a range of a more specific address in said initial list.
The executable code that determines connectivity may comprise executable code that: evaluates connectivity between a source endpoint and each target endpoint within a same subnet in said network; and evaluates connectivity between a source endpoint and each target endpoint within other subnets in said network. The computer program product may also include executable code that evaluates connectivity between each pair of possible endpoints wherein all connectivity between a source and all possible target endpoints are explored prior to advancing to the next possible source endpoint.
In accordance with another aspect of the invention is a computer program product that represents at least one computer attack path in a network comprising executable code that: receives a starting point of a computer attack with respect to said network; and generates a data structure representing at least one attack path possible from said starting point, wherein, said starting point is a node in said data structure, and for a current node being evaluated as part of said generating, a resulting node and an edge connecting said current node to said resulting node are added to said data structure if said edge and said resulting node are not already included in said data structure with said edge connecting a predecessor of the current node to an instance of the resulting node, wherein said predecessor is a node along a path from the starting node to a node immediately preceding the current node. The data structure may be a representation of at least one of: an augmented rooted tree, a non augmented rooted tree, a free tree, a directed acyclic graph, an undirected graph, a graph and a tree. The data structure may include at least one of: an array, a linked list, a hash table, an adjacency list, and an adjacency matrix.
BRIEF DESCRIPTION OF THE DRAWINGS
Features and advantages of the present invention will become more apparent from the following detailed description of exemplary embodiments thereof taken in conjunction with the accompanying drawings in which:
FIG. 1 is an example of an embodiment of a network according to the present invention;
FIG. 2 is an example of an embodiment of a host that may be included in the network of FIG. 1;
FIG. 3 is an example of a representation of a path that may be included in an attack tree;
FIG. 4 is an example of a representation of an attack tree illustrating how an attacker may use multiple vulnerabilities to progress through a network;
FIG. 5 is another example of a representation of a network;
FIG. 6 is an example of an embodiment of an architecture of a system used in attack tree generation and assessing the security of a network;
FIG. 7A is a flowchart of steps of one embodiment that may be performed by a database preprocessor for determining connectivity information;
FIG. 7B is a flowchart of steps of one embodiment for performing address selection processing of FIG. 7A;
FIG. 8 is a flowchart of steps of one embodiment for assessing the security of a network using the system of FIG. 6;
FIG. 9A is a flowchart of more detailed steps of one embodiment for obtaining data and performing any associated data analysis to populate the database of FIG. 6;
FIG. 9B is an example of an embodiment of a table of attack loss values;
FIG. 10 is a representation of one embodiment of a data model used in designing the database of FIG. 6;
FIG. 11 is a flowchart of steps of one embodiment for forming a pruned attack tree;
FIG. 12A is an example of a network and components connected thereto;
FIG. 12B is an example of a full attack tree generated in accordance with the network of FIG. 12A;
FIG. 13 is an example of a pruned attack tree generated in accordance with the network of FIG. 12A;
FIG. 14 is another example of a network and associated hosts;
FIG. 15 is an example of a full attack tree in accordance with the network of FIG. 14;
FIG. 16 is an example of a pruned attack tree in accordance with the network of FIG. 14;
FIG. 17A is a flowchart of steps of one embodiment for determining the vulnerability score of each attack tree;
FIG. 17B is a flowchart of steps of one embodiment for determining a network vulnerability score;
FIG. 18 is a flowchart of steps of one embodiment for providing prioritized recommended changes for improved network security for a network under assessment;
FIG. 19 is an example of a resulting pruned attack tree and associated security metrics;
FIG. 20 is a flowchart of steps of one embodiment for assessing network security in accordance with user input selections;
FIG. 21A is an example of a portion of an attack tree;
FIG. 21B is an example of an embodiment of a network to be assessed;
FIGS. 22 28 are flowcharts of processing steps of one embodiment in performing an end-to-end connectivity evaluation for a network;
FIGS. 29A and 29B are illustrations of different entities at different points in time during processing for one example of end-to-end connectivity;
FIG. 29C is an example of one logical representation of entities used in end-to-end connectivity;
FIG. 29D is an example of a logical representation of a firewall rule set; and
FIG. 30 is an example of representation of how attack trees may be combined in one embodiment.
DETAILED DESCRIPTION OF EMBODIMENT(S)
Referring now to FIG. 1, shown is an example of an embodiment of a network according to the present invention. The network 10 includes a host 12 connected to other hosts 14a 14n through communication medium or interconnection 18. In this embodiment of the network 10, the hosts 14a 14n may access the host 12 in performing requests such as, for example, data requests. The communication medium 18 may be any one of a variety of networks or other type of communication connections as known to those skilled in the art. The communication medium 18 may be a network connection, bus, and/or other type of data link, such as a hardwire, wireless, or other connection known in the art. For example, the communication medium 18 may be the Internet, an intranet, network or other connection(s) by which the hosts 14a 14n may access and communicate with the host 12, and may also communicate with others included in the network 10.
Each of the hosts 14a 14n and the host 12 included in the network 10 may be connected to the communication medium 18 by any one of a variety of connections as may be provided and supported in accordance with the type of communication medium 18.
It should be noted that the particulars of the hardware and software included in each of the hosts 14a 14n, as well as those components that may be included in the host 12, are described herein in more detail, and may vary with each particular embodiment. Each of the hosts 14a 14n and the host 12 may all be located at the same physical site, or, alternatively, may also be located in different physical locations. Examples of the communication medium that may be used to provide the different types of connections between the hosts 14a 14n and the host 12 of the network 10 may use a variety of different communication protocols such as SCSI, Fibre Channel, or GIGE (Gigabit Ethernet), and the like. Some or all of the connections by which the hosts 12, and 14a 14n may be connected to the communication medium 18 may pass through other communication devices, such as switching equipment that may exist such as a phone line, a repeater, a multiplexer or even a satellite. The network 10 may be any one of well-known types of networks including, for example, a local area network (LAN), a wide area network (WAN), and the like.
Each of the hosts 14a 14n and 12 may perform different types of operations in accordance with different types of tasks. In the embodiment of FIG. 1, any one of the hosts 14a 14n may issue a request to the host 12 to perform an operation, such as, for example, to retrieve a Web page for display by one of the hosts 14a 14n, to perform a search, to access one of the host 12's data storage devices, and the like. It should be noted that a network may contain one or more other networks.
Referring now to FIG. 2, shown is an example of an embodiment of a host 14a. It should be noted that although a particular configuration of a host is described herein, other hosts 12, and 14b 14n may also be similarly configured. Additionally, it should be noted that each of the hosts 12, and 14a 14n may have any one of a variety of different configurations including different hardware and/or software components. Included in this embodiment of the host 14a is a processor 80, a memory, 84, one or more I/O devices 86 and one or more data storage devices 82 that may be accessed locally within the particular host. Each of the foregoing may communicate using a bus or other communication medium 90. Each of the foregoing components may be any one or more of a variety of different types in accordance with the particular host 14a.
Each of the processors included in the hosts 12, and 14a 14n may be any one of a variety of commercially available single or multi-processor system, such as an Intel-compatible x86 processor, an IBM mainframe or other type of commercially available or proprietary processor, able to support incoming traffic in accordance with each particular embodiment and application. It should be noted that a host in an embodiment may include one or more other hosts.
Computer instructions may be executed by each of the processors to perform a variety of different operations. As known in the art, executable code may be produced, for example, using a linker, a language processor, and other tools that may vary in accordance with each embodiment. Computer instructions and data may also be stored on a data storage device, ROM, or other form of media or storage. The instructions may be loaded into a memory and executed by a processor to perform a particular task.
In one embodiment, an operating system, such as the Windows operating system by Microsoft Corporation, may reside and be executed on one or more of the hosts included in the network 10 of FIG. 1.
It should be noted that each of the hosts 14a 14n may include any number and type of data storage devices. For example, each of the foregoing hosts may include a single device, such as a disk drive, as well as a plurality of devices in a more complex configuration, such as with a storage area network, and the like. Data may be stored, for example, on magnetic, optical, or silicon-based media. The particular arrangement and configuration of a data storage devices in each of the hosts may vary in accordance with the parameters and requirements associated with each embodiment. Additionally, the devices may be available locally only for use by that particular host, or available for use by one or more external hosts that may vary in accordance with each embodiment.
A host may be susceptible to computer attacks by a malicious user or attacker. An attacker of a host may come from within the host. An attacker may also be external with respect to the host and may, for example, attempt to attack the host from another host through a network.
What will now be described are techniques that may be used in connection with assessing and evaluating the security of a network. The techniques described herein may be used in performing such assessment and evaluation in an automated fashion. The techniques described herein may also be used in connection with providing a prioritized list of possible security improvements. The evaluation and assessment of the security provide a global analysis taking into account, for example, the impact of a single vulnerability on the entire network. Additionally, the techniques described herein utilize an attack tree generation technique that may be characterized as scaleable for use with large networks as well as small networks. The generated attack trees may be used to reveal what can be compromised in a given network by hypothetical attackers at various starting points, and additionally the techniques described herein may be used to produce prioritized recommendations for improving the overall security of a network while also minimizing the amount of manual data entry. The techniques described herein may be used in connection with existing tools and outputs thereof. For example, the output of a vulnerability scanner may be imported into the system described in following paragraphs as a data input. The techniques described herein may be used in connection with experimenting and evaluating hypothetical modifications to assess the impact of a change on the overall security of a network.
Networks may include numerous known vulnerabilities. It may be infeasible to eliminate all known vulnerabilities in the network due to time and cost constraints as well as the need to provide essential operational functionality. Therefore, a tool may be used to analyze a given network and determine the most cost effective way to provide network protection within the network as a whole as well as for identifying the most critical components of the network such as those most vulnerable to attack.
Attack trees are one way of representing how a malicious user or attacker may exploit vulnerabilities in a computer network to compromise hosts on the network. As will be described in following paragraphs, an attack tree may include nodes as well as edges between nodes. Nodes in the tree may represent attack states and edges between the nodes may represent transitions from one state to another. An attacker may transition from a source state to a destination state by exploiting a vulnerability provided that the exploit is possible from the source state.
Referring now to FIG. 3, shown is a representation 100 of a path that may be included within an attack tree. A path within an attack tree may be defined as a traversal from a start state to a destination or end state. The representation 100
includes nodes 102a, 102b, and 102n as well as edges 104a and 104n corresponding to transitions. In this representation 100, the node 102a may be a start node, for example, representing a start state of an attacker. Node 102n may represent a destination state that may be achieved by an attacker. Edges 104a and 104n represent vulnerabilities or other actions allowing a transition from one state to another. For example, a vulnerability corresponding to edge 104a causes an attacker's state to transition from 102a to 102b. In this embodiment described herein, a node may represent a particular attacker's access level or privilege on a particular host, knowledge gained, or network state. The arc or edge representing a transition between states may represent a particular vulnerability on a host causing a transition between states. It should be noted that a vulnerability that is exploited by an attacker performing an action on a particular host may be characterized as causing a transition from one state to another. As used herein, an attacker may transition between states by transitioning from one host to another, increasing attacker privileges or accesses on a same host, gaining knowledge or changing network state. In other words, transitioning between states in an attack graph does not always mean that an attacker advances between hosts. A vulnerability may be local and/or or remote. If a vulnerability is local, the vulnerability may be exploited locally on a host offering the vulnerable service, for example. If a vulnerability is remote, an attack may occur through a remote connection from a location other than from the host offering the service. It should be noted that how an embodiment may represent states of a node and edge are described elsewhere herein in more detail.
Referring now to FIG. 4, shown is a representation 110 of an attack tree that may be included in one embodiment to illustrate how an attacker may use multiple vulnerabilities to progress through a network. The representation 110 in this example includes the attacker at the root of the tree representing a start state of the attacker, for example, on his or her own machine. The attacker at the root node 112 progresses through each level of the attack tree to a terminal node within the tree. For example, the attacker at node 112 may be accessing a web server at the system level through a vulnerability in the web server causing a transition to node 114b. Through a subsequent action, the attacker may transition to node 116c as the database server may be remotely connected to the web server. At the database server with user level access at node 116c, the attacker may transition within the same machine to a higher state of system level access on the same database server. This last transition on the same machine to an elevated state is represented by the transition from node 116c to node 118c. The series of nodes and edges from 112 to 118c may be characterized as a path within the attack tree as previously represented by 100 of FIG. 3.
Attack trees as described herein may be used in connection with several different tasks. For example, attack trees may be used in designing new networks or identifying changes to be made to existing networks. Secondly, attack trees may be used in analyzing the vulnerability of existing networks using known and hypothesized vulnerabilities. Additionally, the attack tree may be used in forensic analysis during an attack, or after an attack has occurred. The attack tree may be used in identifying where a network may benefit most from positioning a firewall, an intrusion detection system, and the like. Additionally, the attack tree may be used in performing a vulnerability analysis or assessment of an existing network. The attack tree may also be used in "what-if" analysis if a particular change is made within the network. The attack tree may also be used in connection with identifying what an attacker may do next once an attack has occurred. For example, referring back to FIG.
4, once an attacker has progressed from the start node 112 to 114b, the attack tree may be used to determine what other possibilities or vulnerabilities an attacker may take advantage of to compromise a host. This may be represented in the attack tree by the edges transitioning to nodes 116b and 116c from node 114b.
It should be noted that the attack tree and generation technique described herein may be used for other applications besides as described herein. The particular examples and uses cited herein should not be construed as a limitation of the techniques described herein.
Referring now to FIG. 5, shown is the representation 150 of a network. It should be noted that the representation 150 may be an instance of FIG. 1 with additional details shown therein. The outside attacker 152 may be on one of the hosts, such as 14a. The outside network 156 may be the Internet connecting the host 14a, upon which the outside attacker resides, to another second host. The second host may be within an inside network shown in the representation 150. The inside network may include other hosts protected from an outside network by a firewall and a VPN or virtual private network concentrator. Also noted within the representation 150 is an inside attacker 154. The inside attacker 154 represents a hypothesized attacker located from within the inside network.
It should be noted that in connection with the foregoing attack tree, one attack tree may be used to represent the possible attack paths from the single outside attacker position 152. A second or different attack tree may be used to represent the attack paths associated with the inside attacker 154. It should be noted that other techniques will be described herein in connection with combining various attack trees representing all of the possible trees associated with individual attack sites or origins. In other words, in order to assess a network having multiple starting points for attackers, multiple attack trees may be combined using the techniques described herein.
Referring now to FIG. 6, shown is an example of one embodiment of an architecture 200 of a system that may be used in connection with attack tree generation and assessing the security of a network. One embodiment of this system 200 includes multiple data sources 202. In one embodiment, the data sources may include vulnerability scanner output data, configuration data such as from firewalls and routers, spreadsheets containing host attack loss values, vulnerability database information, and the like. It should be noted that an embodiment may preferably use automatic import utilities 204 to read one or more existing data files that include such information, or may alternatively provide for conversion of the existing data into a format for use in connection with the system 200. An embodiment may use a manual approach, an automated approach, or a combination thereof to obtain data in a format in accordance with that of the database 206.
It should be noted that an embodiment may use any one or more other or additional data sources other than as shown in the representation 200. Each of the different data sources that may be used in an embodiment are also described herein in more detail. Generally, all of the data that is input to the system 200 includes those data sources that allow for an accurate representation of the vulnerabilities in accordance with the topology as well as existing software and hardware configurations of a system. The configuration data may include, for example, the location of firewalls, routers and the like. Attack loss values may be used in connection with performing an assessment of the system and providing recommendations and prioritizing recommendations. Some the information regarding particular vulnerabilities may be stored in one or more databases, such as the ICAT Metabase described elsewhere herein. One or more tools, including, for example, vulnerability scanners such as the Nessus vulnerability scanner, may provide a data output used in connection with an import utility to import data into the system 200 in an automated fashion. The data used in the generation of the attack tree and its analysis may be stored in the database 206 from the one or more data sources 202.
The database 206 may be in any one or more of a variety of different representations. In one embodiment as will be described in more detail also herein, the database 206 may be a relational database storing the data in accordance with an entity relationship or ER model as known to those of ordinary skill in the art. The database 206 may be used by the attack tree generation and analysis module 208 to generate an attack tree and perform the necessary analysis to generate loss metrics and associated recommendations. The metrics that will be described herein may be used in connection with prioritizing the recommendations as well as other techniques.
In connection with producing information for the database 206, an embodiment may include a database preprocessor 250. Database preprocessor 250 in this embodiment performs processing steps in connection with populating the database with information for use in later steps in attack tree generation and analysis. Functionality and various processing steps that may be performed in an embodiment of 250 are described in more detail in following paragraphs.
An embodiment may also include a database query and updates module 210 which provides a user interface, for example, for querying the database 206 as well as for updating the database 206 rather than providing an update to one of the data sources
202. Additionally, the database query and updates module 210 may provide an interface by which the user may make selections causing data in the database to be modified. A new attack tree may be generated with this update or modification to the data to evaluate a change to the security of a network. The modification may include, for example, elimination or addition of new vulnerabilities, and the like.
The attack tree generation and analysis 208 uses the data included in the database 206 and produces one or more attack trees. The attack tree analysis 208 takes as input the generated attack trees and produces as output the analysis data and recommendations for improving the security of the network just analyzed. An embodiment may also include user interface 212, for example, that may be used in connection with performing operations for the system.
Each of the components of FIG. 6 is described in more detail in following paragraphs. It should be noted that an embodiment may use other systems with different architectures, components, and the like, having a different dataflow than as described herein utilizing the techniques described herein. The particular details included herein are provided by way of example and should not be construed as a limitation of the possible configurations and alternatives that may be used in connection with the techniques described herein.
Referring now to FIG. 7A, shown is a flowchart 260 of processing steps that may be performed in an embodiment in connection with populating the database with connectivity information. In this embodiment, the database preprocessor 250 may perform three tasks as included in flowchart 260 in connection with populating the database with connectivity information for the network under analysis. At step 262, address selection processing is performed which selects network addresses for attacker hosts. At step 264, end-to-end connectivity mapping determination is performed which formulates possible paths and determines if they are valid. At step 266, host collapse processing is performed in which equivalent hosts are determined.
In connection with step 262 for address selection processing, network addresses for attacker hosts are selected. Since firewall and router filtering policies rely on network addresses to identify the endpoints of a connection, the addresses used in an embodiment may be selected to yield maximum connectivity for the attacker hosts. In connection with the modeling of a network herein, attacker hosts are given network addresses before connectivity for these hosts can be computed. More than one address may be needed. If only one address is selected, connectivity may be missed since that address may be blocked by the local gateway or any intervening system or endpoint while other addresses are permitted to pass through. Therefore, the address selection processing in an embodiment may examine all the filtering and/or translation rules in the network under analysis to assemble a set of addresses that uncover all connectivity from the attacker host.
It should be noted the addresses selected for the attacker hosts can also be used for compromised hosts to model situations in which the attacker changes the network address of a host after compromising it. More detailed processing steps of one embodiment for performing address selection processing are described in connection with FIG. 7B.
An embodiment may determine the end-to-end connectivity of a network under analysis at step 264 using the connectivity processing described elsewhere herein, for example, as described in connection with FIGS. 22 29C. Using this technique, a full mapping of end-to-end connectivity within a network is prepared. End-to-end connectivity may be used in generating the attack trees. Given an attacker's current location in the network, the connectivity map may be consulted to immediately determine all hosts and network services the attacker can target from the attacker's current location.
In connection with step 266, hosts are collapsed in an embodiment in order to identify hosts that may be characterized as "equivalent". This may be used in reducing the number of unique hosts. In one embodiment, hosts are determined as equivalent when the following criteria are met for a set of host candidates:
the host candidates have the same vulnerabilities;
all vulnerabilities are on the same port numbers;
the host candidates are not administrative hosts or gateways;
the host candidates have equivalent attack loss values; and
the host candidates have equivalent connectivity.
When a group of multiple host candidates is collapsed, a single host is selected as being a representative host for the entire group. The representative host's attack loss value is the sum of the group's attack loss value.
It should be noted that host collapse processing may be an optional step in an embodiment for attack tree generation using the techniques described herein. In other words, the attack tree generation techniques may be performed using the full set of hosts or using representative hosts. If host collapse processing is performed in an embodiment, it may be performed after determining end-to-end connectivity so that connectivity equivalence may be determined. An embodiment may record any host collapse groupings in the database. In one embodiment, when the attack trees are generated using representative hosts, the generated attack tree may show the representative hosts. Recommendations generated may indicate a host as representative of a group. The ranking of the recommendation may be determined in accordance with the group's attack loss value and group members may be listed.
Referring now to FIG. 7B, shown is a flowchart of processing steps of one embodiment for performing address selection. Other embodiments may use different methods than as described herein and this example should not be construed as a limitation. At step 270, a list of all addresses referenced by all rules in the network is created. An address used in one embodiment may be a specific address (e.g., 192.168.1.1), a range of addresses expressed by an address and prefix length (e.g.,
192.168.1.128/25), or a range of addresses expressed by a beginning address and an end address (e.g., 192.168.1.1 192.168.1.10). At step 272, the network's subnetwork addresses are added to the list of addresses. The subnetwork addresses may include those for the inside subnetworks and those for the outside subnetworks. The subnetwork addresses may be expressed in prefix length notation (e.g., 192.168.0.0/24). At step 274, the list of addresses is sorted from most specific to least specific, and duplicates are eliminated. An address X in one embodiment is characterized as "more specific" than an address Y if the range of X is smaller than the range of Y. At step 276, the final addresses are determined. For each address in the list resulting from step 274, if the address to consider is a specific address, select that address and place this address into a final list of selected addresses. If the address to consider is a range, then choose an address from that range. If the chosen address is already in the final list, or within the range of a more specific address, try again, until a usable address is selected, or a retry limit is reached.
The list of addresses resulting from step 276 is assigned to all attacker hosts. Each attacker host is assigned the same list of network addresses. As will be seen in connection with determining the end-to-end connectivity processing steps described elsewhere herein, such as in connection with FIGS. 22 29C, these addresses may be blocked by egress filtering on the gateways or gateways connected to the attacker host's local subnetwork. In other words, these addresses will therefore yield no additional connectivity for the attacker host once filtering rules, such as those of a firewall policy, are applied in determining connectivity. However, these addresses may expose configuration errors, such as, for example, improper or missing egress filtering, by revealing connectivity which should not exist. These addresses may also be used in connection with generating attack trees as described elsewhere herein, such as in connection with FIG. 11, to associate alternative connectivity maps to hosts as within the current host of an attacker state. A connectivity map associated with a current host of an attacker state may be a connectivity map associated with an attacker host based on the addresses selected for an attacker host and the connectivity processing described elsewhere herein, such as in connection with FIGS. 22 29C. An alternative connectivity map may replace a connectivity map assigned to the current host based on addresses assigned to the current host where said addresses may be obtained through means described elsewhere herein, such as in connection with FIG. 9A. Prior to attack tree generation, an alternative connectivity map may be associated to all hosts which may become a current host of an attacker state, or, an alternative connectivity map may be associated with a host as a host becomes a current host of an attacker state. Use of alternative connectivity maps for compromised hosts may reflect a worst-case condition in which an attacker with sufficient privileges and access changes the network address of a compromised host to obtain such connectivity as may be made available through the use of one or more other network addresses.
Referring now to FIG. 8, shown is a flowchart 300 of steps of one embodiment for assessing the security of a network using the model or architecture 200 of FIG. 6. At step 302, the network to be analyzed is identified. It should be noted that a single network being analyzed may be made up of multiple connected networks. The entire single network may be analyzed as one network. Alternatively, each of the multiple networks may also be assessed or analyzed separately and then combined. This is described elsewhere herein in more detail. At step 303a, data needed to perform the current analysis of the current attack tree is obtained. Additionally, any analysis of the obtained data as well as any conversion may also be performed in order to put the data in a format for use with the database. At step 303b, the database is populated with the data. It should be noted that the particulars of the data that are obtained and analyzed as well as an example of one embodiment of a data model for a database populated at step 303b are described in more detail elsewhere herein. It should be noted that steps 302, 303a and 303b may be characterized as part of a data collection process rather than as part of the process for generating attack trees.
Control proceeds to step 304 where the one or more attacker starting points to the particular network are identified. Referring back to FIG. 5, it was noted that an attack may occur from within a network, such as element 154, as well as outside of the network, such as element 152. At step 304 for the configuration of FIG. 5, two attacker starting points are identified. At step 306, current entry is assigned the first attacker starting point. The processing steps that will now be described generate a pruned attack tree for each of the different attacker starting points. Subsequently, as will be described, assessments of each of the attack trees corresponding to each attacker starting point may be combined to provide an assessment with respect to the current network.
At step 312, a pruned attack tree is generated for the current entry. The particular details of how to generate a pruned attack tree are described in more detail elsewhere herein. At step 314, the current entry is assigned the next attacker starting point so that an attack tree may be generated for each different attacker starting point. At step 316, a determination is made as to whether processing is complete for the current network. In other words, at step 316 a determination is made as to whether all of the attack trees in accordance with the particular possible attacker starting points have been generated. If not, control proceeds back up to step 312. If at step 316 it is determined that processing for the current network is complete, control proceeds to step 318 where an analysis and assessment of the security of the network is performed using the pruned attack tree or trees generated. Step 318 may include generating one or more metrics. At step 320, assessment information, such as the one or more metrics from step 318, may be used to produce prioritized recommendation. It should be noted that the processing of steps 318 and 320 are described in more detail elsewhere herein. In one embodiment, steps 318 and
320 produce and utilize metrics in order to assess the current state of the network security as well as provide alternative evaluated scenarios when one or more changes are made within the network identified and currently being analyzed at step 302.
Referring now to FIG. 9A, shown is a flowchart 350 of more detailed steps of one embodiment for obtaining data and performing the needed analysis previously described in connection with flowchart 300. It should be noted that the particular data and its forms described herein should not be construed as a limitation. Other embodiments may use other data than as described herein and the data may be in one or more different forms. The embodiment described herein may use the data produced as an output of one or more tools, and further convert and/or analyze this output data in order to facilitate population of the database described elsewhere herein. At step 351, each service that may be used to remotely access hosts in the network are identified. The foregoing information may be used to determine which hosts are vulnerable to sniffing attacks (e.g., obtaining passwords through monitoring network messages), as well as which hosts may be compromised as a result of an administrative host being compromised. In one embodiment, a default set of remote access services may be included in a spreadsheet used as an input data source for the system 200. The particular service(s) and particulars of each service may vary with each embodiment.
At step 352, vulnerability scan data and ICAT data are obtained and analyzed. The ICAT Metabase is a public database available at http://icat.nist.gov which includes information concerning whether a particular vulnerability is local or remote, and the outcome of exploiting a vulnerability. In one embodiment, vulnerability scanners, such as the Nessus scanner, may be used to automatically generate vulnerability information about one or more hosts within the network being analyzed. The output of such tools, optionally in conjunction with ICAT data, can be used in populating the database. In particular, this information about the vulnerabilities and ways in which these vulnerabilities may be exploited provide information related to the different attacker states and actions to obtain these particular states. Network data as may be provided as an output of the vulnerability scanner may include, for example, host names and (Internet Protocol) IP addresses, open ports on the hosts, services and software versions running on the different ports, known vulnerabilities in the various versions and the like. The vulnerabilities reported by the vulnerability scanner may be correlated with information available from one or more databases, such as the ICAT Metabase available from NIST, as well as other sources, in order to automatically determine which attacker actions should be attached to each vulnerability. An embodiment may also acquire additional information from other sources or alternatively may use information from other sources than as described herein. It should be noted that additional detail about how the vulnerability scan data and ICAT data may be analyzed and used in an embodiment are described elsewhere herein.
At step 354, the names of administrative hosts are obtained. As used herein, an administrative host may be characterized as a host used in management of other hosts and/or resources. The administrative host may, for example, provide access to other hosts, firewalls, routers, and administrative services such as those performed with system privileges. Once an attacker compromises an administrative host, generally the attacker may have access to a large number of other hosts. The information from steps 354 and 351 may be used to determine which hosts may be compromised as a result of an administrative host being compromised. In one embodiment, the data for step 354 may be included within a spreadsheet or other input format used as a data source for the database. This, as well as other data sources described herein may be generated manually, automatically, or a combination thereof. At step 356, the names of the gateway hosts and the addresses for the network interfaces are obtained. The gateway hosts may be identified using any one or more different techniques. In one embodiment, the gateway hosts may be gathered in an electronic spreadsheet. A gateway host may be characterized as a host that serves as a gateway or a link to another network. It should be noted that there may be more than one gateway host in a network. At step 358, the particular firewall rules are obtained, analyzed, and placed in a form to populate the database model described elsewhere herein. More detailed steps are described elsewhere herein in connection with analyzing the firewall rule sets. As described in following paragraphs, the firewall rule sets may be applied in connection with determining connectivity of the network. At step 362, attack loss values are obtained for each of the hosts. The attack loss values obtained and used at step 362 represent a value associated with each of the hosts. These values may be generated using an automated technique, a manual technique, or a combination thereof. The values generated depend on the particular value associated with a host in a particular network being analyzed. This may vary in accordance with each particular embodiment. One technique may utilize a manual technique in which someone who is familiar with the network, such as an administrator, assigns a value to each of the hosts. Attack loss values and considerations that an embodiment may consider in determining these values are described elsewhere herein in more detail.
It should be noted that an embodiment may use other data, for example, in obtaining the network configuration and connectivity information needed and used as described elsewhere herein.
It should be noted that the data from the ICAT Metabase may be available in one or more different forms. One embodiment may use the ICAT data which is in a format for use with Microsoft Access. The ICAT data in this embodiment is also then exported in XML format.
What will now be described in more detail are the attack loss values. Attack loss values are a metric assigned in this embodiment on a per host basis. In one embodiment, the attack loss values may be manually assigned to each host. For example, a particular user, such as a system administrator or other individual familiar with determining a value representing a cost of a compromise associated with a particular host, may determine each of the attack loss values. Each of the attack loss values may be characterized as representing a relative value of a particular host as compared to other hosts. Generally, more important hosts have higher attack loss values than less important hosts.
An embodiment may consider any one or more different factors in evaluating a cost of a compromise associated with a particular host. The role that a host plays in a network may be considered as well as the criticality of the data stored on, or accessible through, the host. The role or particular services provided by a host as well as accessible through that host may also be considered. For example, if a host provides access either directly or indirectly to mission critical or sensitive data, or mission critical or sensitive services, then the attack loss value associated with a particular host may be high. A particular host may access data, for example, stored locally at that host. A first host may also provide an attacker access to critical data stored on a second host, a service available on a second host, and the like. Other considerations in assigning host values include, for example, a confidentiality level of data and other types of categorizations that may already exist for use in an embodiment.
It should also be noted that an embodiment may use an automated technique, a manual technique, or combination thereof in obtaining any information in an appropriate form for use by an embodiment in performing the techniques described herein.
Referring now to FIG. 9B, shown is an example 370 of a table including attack loss values that may be associated with one or more hosts. The table 370 in this example includes three columns of information. The first column 372 includes an identifier of the particular host. The second column 374 includes a description of a particular host. The third column 376 includes an attack loss value associated with the particular host designated in the first column 372 on the same row. Table 370
may be stored in any one of a variety of different formats and may be produced using any one of a variety of different automated and/or manual techniques. In one embodiment, the attack loss values may be established by consulting a system administrator to identify the most important hosts on a network. The system administrator or other person may assign these values and store them, for example, in a spreadsheet format as may be partially represented by the table 370. The attack loss values may be imported in an automated fashion using a programming tool or other technique in order to populate a database described elsewhere herein.
Referring now to FIG. 10, shown is a representation of one embodiment of a data model 400 that may be used in designing a database, such as the database 206 previously described in the system 200 of the FIG. 6. In this embodiment, the data model is represented in the form of an E-R data model or entity-relationship model. As known to those of ordinary skill in the art, each of the rectangular boxes represents an entity with associated relationships as noted by the connecting lines between each of the different entities. It should be noted that other embodiments may use other representations as well as other models in connection with representing and storing data as may be used in an embodiment.
Representation 400 includes 5 categories of entities. Category A may be referred to as the software and vulnerability category, category B is the attacker actions category, category C is the connectivity category, category D is the network category, and category E is the firewall policy category. Entities in each of the categories A through E have associated element labels with a prefix identifying the category to which each entity belongs. For example, the software and vulnerability category A entities are denoted such as A100, A200, A300, A400 and the like. Similarly, each of the other categories have their associated entities prefixed with the category letter. Category A entities describe information about particular software and associated vulnerabilities, for example, that may be used on one of the hosts. Category B entities describe information about actions that an attacker may take and the resulting attacker state, such as system or user access on a particular host defining a privilege level of the attacker. Category C entities describe under what conditions each host is allowed to connect to another host. In other words, connectivity category C describes what end-to-end connectivity is permissible between hosts in a network in accordance with the firewall policy rules. Category D entities describe information about network entities, such as the hosts, and characteristics of different types of hosts. Category E entities describe the actual firewall policy rules which, when analyzed, produce the results used in populating category C entities.
With reference to FIG. 10 element 400, the data model entities that may be populated using the vulnerability and ICAT data, as described in connection with step 352, include software and vulnerabilities A, and attacker actions B, and network configuration D. Step 352 in one embodiment populates all entities of category A except for that data regarding remote access services. The information obtained at step 354 may be used in populating information about the particular administrative hosts as indicated in entity D400 Admin Host Indicator. The information obtained at step 356 may be used in populating information about the particular gateway hosts as indicated in entity D400, Gateway Indicator. The particular firewall rules from step 358
are obtained, analyzed, and placed in a form to populate the firewall policy category E of the database model 400 of FIG. 10. Additionally, the analysis information obtained from analyzing the firewall rule sets may be used to populate entities in category C Connectivity of data model 400 of FIG. 10. Data from step 351 in this embodiment may be used to populate the portion of category A entities relating to remote access service entity A600. Remote access information includes, for example, such as whether there is encryption, and the like, when accessing a remote host with a password.
Included in category A for the software and vulnerabilities category are entities A100 A700. Entities A100, A200, A300 and A400 may represent information about a particular software product, vendor, and version. A vulnerability associated with a software product and version thereof may be represented using A500. A500 may include, for example, vulnerability identifier information, publication data regarding the vulnerability, an associated severity code, and an indicator as to whether an attacker must "sniff" a password to exploit the vulnerability. Other information for category A entities may be obtained from other data sources described elsewhere herein. A600 may be used to represent a remotely accessible service. A600 may include, for example, a port number through which a remotely accessible service is available, an indicator as to whether the service is an administration service, and an indicator as to whether encryption is used. The vulnerability status entity A700 may be used to relate each particular port with one or more associated vulnerabilities used in processing steps described herein when building a pruned attack tree.
Associated with each vulnerability in this embodiment is an attacker action described by B100 that an attacker may perform to exploit the vulnerability associated with the action. Entity B200 includes information about the resulting attacker and/or network state once the vulnerability is exploited. For example, entity B200 may be used to indicate that an attacker's state may increase from user to system level on a host when the associated vulnerability is exploited. B100 NIDS Detectable Indicator indicates if an associated action is detectable by a network Intrusion Detection System (IDS). The HIDS Detectable Indicator indicates if the action is detectable by a host IDS. Both of the foregoing (NIDS and HIDS) may be included in an embodiment for modeling a network. IDS modeling may be used to show which paths of an attack tree may be seen by an IDS and may be used to produce recommendations for IDS placements.
A physical network structure or configuration is represented by entities D100 D700 in the network category D. D100 is created for each port which in this embodiment is used as a connectivity endpoint. D300 includes data describing the particular network under assessment. Each network as represented by D300 may include one or more subnets. Each subnet may be represented by an entity D200 associated with an instance of D300. Each host in the network is represented by an instance of D400 and may have associated with it one or more network interfaces each represented by an instance of entity D500. Each port is represented by an instance of D100. Information about how a particular network interface may be referenced or is otherwise identified in the network may be described in an instance of D600 and/or D700. In D400, the Default Open Indicator indicates the default forwarding policy of a gateway when no rules are matched. The Host IDS indicator indicates if this host has a host-based IDS. Group Attack Loss is the sum of the values of hosts in a particular group if the host is a representative host of others in a group. Different indicators or fields may be used in an embodiment to indicate a time condition as related to a rule. For example, D400 includes a GMT Offset field representing the departure from GMT of the time zone where the host is located, in standard time. A Daylight Time Indicator may also be used to indicate if the time zone where the host is located observes daylight savings time.
Information regarding end to end connectivity between two points in the network under analysis is represented by entities C100 C300 in category C connectivity. C100 represents a pairing of two endpoints, such as a source or a target or destination endpoint. C200 is an identifier of the particular path. C300 includes information about a particular hop in the path. Associated with each C100 instance, for example, may be two instances of D100 in which a first instance of D100
represents a first endpoint in the connectivity and a second instance of D100 represents a second endpoint in the connectivity.
Entities E100 E500 describe the firewall rules in a particular network. Entity E100 indicates the days of the week and the times of the days when a particular firewall rule is active. Entity E300 describes a network object to which a firewall rule described by E400 applies. E200 indicates any address translation for a connection endpoint since, for example, a host may be referred to using one address on one side of a firewall and a different address on another side of a firewall. E200 is used in one embodiment for both source and destination translation rules. It should be noted that an embodiment may also have different locations for storing source and destination translation rules. The information in category E entities may be determined as part of processing and analyzing of firewall rule sets prior to generating the pruned attack trees.
Entity E500 represents a collection of interfaces where all interfaces in a zone are on a same gateway. If a gateway has multiple interfaces to the outside, and the same rule(s) apply on the outside independent of the outside interface, the interfaces may be grouped into a zone and the rules associated with the zone. This may be used as an alternative in an embodiment to, for example, associate a separate set of rules with each interface.
It should be noted that the category D entities may be used in indicating how to take the vulnerability scan information and populate the category A and B entities.
A variety of different relationships between the different entities included in each of the categories are possible as indicated in the data model representation of FIG. 10 for one particular embodiment. Other embodiments may use other representations and other entities than as described herein in accordance with the particulars of each embodiment.
Referring now to FIG. 11, shown is a flowchart 500 of steps of one embodiment that may be performed in connection with forming a pruned attack tree. The method of pruned attack tree generation as described herein represents a pruned version of what may be characterized as a full or complete attack tree. A full or complete attack tree shows all paths including indirect ones by which an attacker may start from a root node and traverse to an end point or terminal node. In other words, the full or complete attack tree shows all combinations of accesses between different nodes and different actions available to an attacker from a particular starting point. Data included in the database in this embodiment includes information for producing a full attack tree. However, using the techniques described herein, one or more pruned attack trees may be generated using the information from the database. The pruned attack trees may be used in further processing steps such as in analyzing a network represented in accordance with the generated pruned attack trees.
As described elsewhere herein, the attack trees may be used to represent how a malicious user may exploit vulnerabilities in a computer network to compromise a host on the network. The nodes of the tree represent various attacker states such as a particular host with a particular access or privilege level, such as system or user level access. The edges between the nodes represent state transitions from one state to another. An attacker transitions from a source node to a destination node by exploiting a vulnerability on the destination host provided that the exploit is possible from the source host. The techniques described in the following paragraphs use a forward chaining technique to discover all possible attack paths from a particular attacker starting state. In other words, the attack tree answers the question "What are all the hosts that may be compromised on a network from a particular attacker starting point?". The attack tree may also be used in answering other questions, for example, regarding which vulnerabilities and which attack paths may be associated with a compromise of a network.
The attack tree described in the following paragraphs may be characterized as comprehensive showing everything that may be compromised by an attacker positioned at a starting point. The attack tree described herein may be characterized as scaleable providing an efficient tree generation technique for worse case attack trees for small and or large networks. The embodiment described herein may be based on worst case assumptions, for example, that the attacker knows or can discover all connectivity for all services available, all unencrypted passwords may sniffed or obtained on the network, and all encrypted passwords may be key captured on local hosts. The tree generation technique described in the following paragraphs uses an efficient, forward chaining, breadth first search (BFS) technique providing for judicious pruning of redundant states and paths to reduce the size and storage requirements associated with each attack tree. The BFS technique generates a pruned attack tree such that all nodes at a current level are considered for addition to the pruned attack tree prior to considering nodes at a next level. The BFS technique is well-known and described, for example, in "Data Structures and Algorithms" by Aho et al. from Addison-Wesley. Generally, BFS is a way of traversing the nodes of a tree by visiting all nodes at a same level before visiting a node at a next level within the tree. Edges and resulting states achievable from a current node by exploiting vulnerabilities are evaluated and either pruned or added to the attack tree under construction using the pruning technique described in connection with flowchart 500.
The attack tree generation technique described in the following starts by generating a root node using information from the database and represents an attacker with system level access in a hypothetical host at a specified location within the network. At each level of the tree, for each node at that level, each possible vulnerability is considered which may change the attacker's state. A vulnerability may be exploited by an action causing a transition from one node to another if there is physical connectivity between a first point and a second point, such as between two hosts, if the required network traffic between the source and destination is not filtered by firewall policy, and if all requirements of the particular vulnerability are met. In other words, if it is required for a particular vulnerability that an attacker must be coming from an administrative host, this requirement is tested in order to determine if, for example, the current state represents an administrative host. An attacker's state changes or transitions if the attacker moves to a new host, increases access level within the same host, or otherwise gains something. This is described elsewhere herein in more detail.
A new node may be added to the next level of the tree to represent the resulting attacker's state unless this particular state has already been reached using the same vulnerability at a previous level in the tree as described elsewhere herein in more detail. This "unless" clause effectively prunes redundant nodes and paths to avoid generating a full tree with the generated pruned tree representing all needed information for a network security assessment. Each level of the tree is iterated through until a point is reached where no new nodes are added to the tree during the processing of a level.
Recall that as described elsewhere herein, in this embodiment, one attack tree is generated for each attacker starting point within the network. The steps of flowchart 500 may use information from the database to produce one pruned attack tree rather than a full attack tree for each attacker starting point. As described elsewhere herein, the one or more pruned attack trees may be used in evaluating and assessing the current network being analyzed.
A node in the attack tree described herein may be defined using four pieces of information: the network state, the attacker state, a list of parent nodes, and a list of child nodes. The network state describes the overall network configuration. As used herein, the term "network configuration" may be characterized as all information in the database about a network including, for example, all entity categories A E. The attacker state describes the attacker's configuration. The attacker's state may be defined using four pieces of information: the current host that an attacker is on, an attacker's access level on the current host, a list of accesses obtained by the attacker, and a list of accesses used by the attacker. An edge in the attack tree described herein may be defined using two pieces of information: an action that drives a transition from one node to another, and the target port the action is performed against. Other embodiments may represent states differently than as described herein.
At step 502, a determination is made as to whether there are any remaining attacker starting points for which an attack tree may be generated. If there are no more attacker starting points, processing stops. Otherwise, control proceeds to step
504 to begin processing steps to generate a new attack tree for the current attacker starting point by adding a root node to the new attack tree. At step 506, a tree level counter, n, is set to 0 corresponding to the level of the root node of the tree. Note that each level of the tree results in the level counter n being incremented by one (1).
At step 508, a determination is made as to whether there are more nodes at the current level n which have not yet been evaluated. If so, control proceeds to step 509 to obtain the next node to be evaluated at level n. Processing continues with step 514 where the current node is set to the next node to be evaluated. At step 516, a determination is made as to whether there are any remaining target ports associated with the current node. In this embodiment, the current node has an attacker state with a current host. The current host has interfaces, each of which has a connectivity map listing target ports. It should be noted that as described elsewhere herein, a node in the attack tree in this embodiment may be represented by several pieces of state information including an attacker state. An attacker state may be defined using multiple pieces of state information including a current host of an attacker. The target ports examined for a current node in 500, such as at steps 516,
518, and the like, are those ports associated with each interface of the current host for the current node being evaluated.
If, at step 516, a determination is made that there are no remaining target ports, control proceeds to step 508 to the next node to be processed at the current level. If there are remaining target ports, control proceeds to step 518 to get the next target port. For the current target port, a determination is made at step 520 as to whether there are any remaining vulnerabilities to be examined. If not, control proceeds to step 516. If so, the next vulnerability is obtained at step 522.
A determination is made at step 524 as to whether any ancestor of the current node has the same vulnerability and corresponding target port. In other words, the determination at step 524 asks the question "Are the proposed vulnerability and target port already included in the current attack tree as being achievable directly from any ancestor of the current node?" The ancestors of the current node as referenced in step 524 processing are the nodes along the path between the parent of the current node and the root node. If step 524 determination evaluates to true, control proceeds to step 520. It should be noted that step 524 evaluating to true results in pruning the resulting attack tree by not adding the proposed edge and resulting node from the current node. As a further consequence, any subtree which may have otherwise emanated from the resulting node is also pruned from the tree.
If, at step 524, it is determined that no ancestor of the current node has the same vulnerability and corresponding target port, control proceeds to step 526 where the action corresponding to the current vulnerability is evaluated to determine the resulting attacker state. A determination is made at step 528 as to whether the attacker improves as a result of performing the current action to exploit the current vulnerability. If not, control proceeds to step 520. Otherwise, control proceeds to step 530 where a determination is made as to whether the resulting attack state is already achievable from the current node by another vulnerability and/or target port. If so, this means that the current attack tree already has a node at level n+1
corresponding to the current resulting attack state. Accordingly, to represent the new current vulnerability and target port in the attack tree, control proceeds to step 534 where an edge is added from the current node at level n to the already existing resulting node at level n+1. Control then proceeds to step 520.
The techniques described herein create a tree known to those skilled in the art as a rooted tree, augmented by steps 530 and 534 to produce one or more edges between nodes. Steps 530 and 534 are performed as an optimization which may reduce the number of nodes in the tree. Omission of steps 530 and 534 produces a tree which is equivalent to the augmented tree produced with the inclusion of steps 530 and 534. Unless otherwise specified, all references herein to a tree refer to an augmented tree. The edges are shown as directed edges, and the presence of directed edges should be considered a further augmentation of the definition of a tree. The representation achieved by the augmented tree may be achieved through other means, such as non augmented rooted trees, free trees, directed acyclic graphs, undirected graphs, and other forms of graphs, and these representations should be considered as equivalent to the augmented tree described herein.
A variety of data structures may be used to represent trees and their equivalents as described herein. These data structures may include without limitation pointer-based, address-based, location-based, and linked data structures, and include