IDS Sensor Placement Using Attack Graphs

• US 20100058456A1
• Filed: 08/26/2009
• Published: 03/04/2010
• Est. Priority Date: 08/27/2008
• Status: Abandoned Application

• Current Assignee: Steven E. Noel, Sushil Jajodia
• Original Assignee: Steven E. Noel, Sushil Jajodia
• Inventors: Jajodia, Sushil, Noel, Steven E.
• Application Number:
  US12/548,115
• Publication Number:
  US 20100058456A1
• Time in Patent Office: Days
• US Class Current: 726/11
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227

Abstract

Embodiments of the present invention identify locations to deploy IDS sensor(s) within a network infrastructure and prioritize IDS alerts using attack graph analysis. An attack graph that describes exploitable vulnerability(ies) within a network infrastructure is aggregated into protection domains. Edge(s) that have exploit(s) between two protection domains are identified. Sets that contain edge(s) serviced by a common network traffic device are defined. Set(s) that collectively contain all of the edge(s) are selected. The common network traffic device(s) that service the selected sets are identified as the location(s) to deploy IDS sensor(s) within the network infrastructure.

Claims

1. A computer readable storage medium that contains instructions that when executed by at least one processor, causes the at least one processor to perform a method for identifying locations to deploy at least one IDS sensor within a network infrastructure, the method comprising

a) aggregating an attack graph into at least two protection domains, the attack graph describing at least one exploit in at least a part of the network infrastructure;

b) identifying at least one edge, each of said “

at least one edge”

having at least one of the at least one exploit between two of the at least two protection domains;

c) define at least two sets, each set containing at least one of the at least one edge, all of the at least one of the at least one edge serviced by a common network traffic device;

d) selecting at least one of the at least two sets that collectively contain all of the at least one edge;

e) identifying the common network traffic device that services the selected sets as the locations to deploy the at least one IDS sensor within the network infrastructure.

2. The medium according to claim 1, wherein the selecting includes at least one of the at least two sets that cover at least one critical path through the network infrastructure that leads to a critical asset.

3. The medium according to claim 1, wherein the selecting includes at least one of the at least two sets that cover at least one critical path through the network infrastructure that starts at an assumed threat source.

4. The medium according to claim 1, wherein the selecting selects the fewest number of sensors necessary to cover at least one critical path through the network infrastructure.

5. The medium according to claim 1, further including using the selected sets to plan an attack response.

6. The medium according to claim 1, wherein the selecting uses a greedy algorithm.

7. The medium according to claim 6, wherein greedy algorithm favors large sets that contain at least one of the at least one edge that is infrequently used.

8. The medium according to claim 1, wherein the protection domain encompasses at least part of a subnet.

9. The medium according to claim 1, further including prioritizing alerts from IDS sensors deployed within the network infrastructure using at least one attack graph distance to at least one critical asset.

10. The medium according to claim 1, further including prioritizing alerts from IDS sensors deployed within the network infrastructure using at least one predictive attack response.

11. A IDS location deployment identification module comprising

a) an attack graph aggregation module configured to aggregate an attack graph into at least two protection domains, the attack graph describing at least one exploit in at least a part of a network infrastructure;

b) an edge identification module configured to identify at least one edge, each of the at least one edge having at least one of the at least one exploit between two of the at least two protection domains;

c) a set definition module configured to define at least two sets, each set containing at least one of the at least one edge, all of the at least one of the at least one edge serviced by a common network traffic device;

d) a set selection module configured to select at least one of the at least two sets that collectively contain all of the at least one edge; and

e) an IDS sensor location module configured to identify the common network traffic device that services the selected sets as the locations to deploy the at least one IDS sensor within the network infrastructure.

12. The module according to claim 11, wherein the set selection module is further configured to select at least one of the at least two sets that cover at least one critical path through the network infrastructure that leads to a critical asset.

13. The module according to claim 11, wherein the set selection module is further configured to select at least one of the at least two sets that cover at least one critical path through the network infrastructure that starts at an assumed threat source.

14. The module according to claim 11, wherein the set selection module is further configured to select the fewest number of sensors necessary to cover at least one critical path through the network infrastructure.

15. The module according to claim 11, further including a response module configured to use the selected sets to plan an attack response.

16. The module according to claim 11, wherein the set selection module is further configured to use a greedy algorithm.

17. The module according to claim 16, wherein greedy algorithm favors large sets that contain at least one of the at least one edge that is infrequently used.

18. The module according to claim 11, wherein protection domain encompasses at least part of a subnet.

19. The module according to claim 11, further a prioritization module configured to prioritize alerts from IDS sensors deployed within the network infrastructure using at least one attack graph distance to at least one critical asset.

20. The module according to claim 11, further including a prioritization module configured to prioritize alerts from IDS sensors deployed within the network infrastructure using at least one predictive attack response.