Systems and methods for testing and evaluating an intrusion detection system

• US 20060253906A1
• Filed: 12/05/2005
• Published: 11/09/2006
• Est. Priority Date: 12/06/2004
• Status: Active Grant

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Jha, Somesh, Rubin, Shai A., Miller, Barton P.
• Granted Patent: US 7,941,856 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1433 Vulnerability analysis
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227

Abstract

Systems, methods and devices according to this invention include a plurality of defined modification rules for modifying a sequence of packets that form an attack on an intrusion detection system. These modification rules include both rules that expand the number of packets and rules that reduce the number of packets. The reducing rules can be applied to a given attack instance to identify one or more root attack instances. The expanding rules can then be applied to each root attack instance to generate a corpus of modified attack instances. The modification rules can preserve the semantics of the attack, so that any modified attack instance generated from the given attack instance remains a true attack. To test an intrusion detection system, the corpus of modified attack instances can be used to determine whether an intrusion detection system detects every modified attack instance.

Claims

1. A method for testing an intrusion detection system usable to detect attacks against a network location, comprising:

presenting each of a plurality of attack instances corresponding to a given attack to the intrusion detection system being tested, the plurality of attack instances generated by modifying a given attack instance using a plurality of transformation rules of a formal transformation system, the transformation rules substantially preserving the semantics of the given attack instance;

determining, for each presented attack instance, whether the intrusion detection system being tested generated an alert in response to being presented with that attack instance;

evaluating the intrusion detection system being tested based on results of determining, for each presented attack instance, whether the intrusion detection system being tested generated an alert in response to being presented with that attack instance.

2. The method of claim 1, wherein presenting each of the plurality of attack instances corresponding to the given attack to the intrusion detection system being tested comprises:

selecting one of the plurality of attack instances, each attack instance comprising at least a sequence of at least one attack packet;

presenting the sequence of at least one attack packet of the selected attack instance to the intrusion detection system being tested; and

repeating the selecting and presenting steps for each of the plurality of attack instances.

3. The method of claim 1, wherein determining, for each presented attack instance, whether the intrusion detection system being tested generated an alert in response to being presented with that attack instance comprises determining, for a selected attack instance, if the intrusion detection system being tested did not generate an alert in response to being presented with that attack instance.

4. The method of claim 1, wherein evaluating the intrusion detection system being tested comprises:

identifying at least one attack instance for which the intrusion detection system failed to generate an alarm;

determining, for at least one attack instance for which the intrusion detection system failed to generate an alarm, if the intrusion detection system failed to detect that attack instance due to the intrusion detection system lacking a signature that matches that attack instance; and

if so, modifying a set of attack signatures provided to the intrusion detection system such that the set of attack signatures includes at least one attach signature that is usable to detect that attack instance.

5. The method of claim 1, wherein evaluating the intrusion detection system being tested comprises:

identifying at least one attack instance for which the intrusion detection system failed to generate an alarm;

determining, for at least one attack instance for which the intrusion detection system failed to generate an alarm, if the intrusion detection system failed to detect that attack instance due to a structural limitation in the intrusion detection system; and

if so, modifying the intrusion detection system based on that attack instance so that the intrusion detection system is able to detect that attack instance.

6. A method for generating a corpus of modified attack instances from a given attack instance using a plurality of transformation rules of a formal transformation system, the transformation rules usable to modify an attack instance, each transformation rule substantially preserving the semantics of the attack instance, the attack instance usable against a network, the given attack instance being one element of a set of available attack instances, the method comprising:

selecting an attack instance from the set of available attack instances as a selected attack instance;

selecting one of the plurality of transformation rules;

applying the selected transformation rule to transform the selected attack instance to create a modified attack instance, the modified attack instance being another element of the set of available attack instances;

repeating at least one of the attack selecting, rule selecting and rule applying steps a plurality of times to create additional modified attack instances, each such modified attack instance being another element of the set of available attack instances; and

forming the corpus of modified attack instances from at least some of the available attack instances.

7. The method of claim 6, wherein each transformation rule is sound with respect to the given attack instance.

8. The method of claim 6, further comprising testing an intrusion detection system usable to detect attacks against a network location using the corpus of modified attack instances.

9. The method of claim 8, wherein testing the intrusion detection system usable to detect attacks against a network location using the corpus of modified attack instances comprises:

presenting each of the corpus of modified attack instances to the intrusion detection system to be tested;

determining, for each presented attack instance, if the intrusion detection system being tested does not generate an alert in response to being presented with that attack instance;

evaluating the intrusion detection system being tested based on attack instances for which the intrusion detection system was determined not to have generated an alert.

10. The method of claim 8, further comprising modifying a set of attack signatures of the intrusion detection system based on results of testing the intrusion detection system using the corpus of modified attack instances.

11. The method of claim 10, wherein modifying the set of attack signatures comprises:

determining, for the corpus of modified attack instances, which of the modified attack instances is not detected by the intrusion detection system;

identifying, for each of at least one modified attack instance that did not result in the intrusion detection system generating an alarm in response to that modified attack instance, at least one attack instance that is related to that modified attack instance and that is detected by the intrusion detection system;

identifying at least one feature that is common to both that at least one modified attack instance and the identified related attack instance;

identifying at least one attack signature of the set of attack signatures that is usable to detect that at least one identified related attack instance; and

modifying at least one of the at least one identified attack signatures based on at least one of the at least one identified common features such that the at least one modified attack signature is usable to detect that at least one modified attack instance.

12. The method of claim 10, wherein modifying the set of attack signatures comprises:

determining, for the corpus of modified attack instances, which of the modified attack instances is not detected by the intrusion detection system;

identifying, for at least one modified attack instance that did not result in the intrusion detection system generating an alarm in response to that modified attack instance, at least one attack instance that is related to that modified attack instance and that is detected by the intrusion detection system;

identifying at least one feature that is common to both the at least one modified attack instance and the identified related attack instance;

creating at least one new attack signature based on the at least one identified common feature; and

adding the at least one new attack signature to the set of attack signatures.

13. The method of claim 10, wherein modifying the set of attack signatures comprises:

determining, for the corpus of modified attack instances, which of the modified attack instances is not detected by the intrusion detection system;

determining, for at least one modified attack instance that did not result in the intrusion detection system generating an alarm in response to that modified attack instance, an attack signature for that modified attack instance; and

adding at least one determined attack signature to the set of attack signatures.

14. The method of claim 6, wherein:

at least one attack instance of the set of available attack instances includes a sequence of packets implementing the attack instance, the sequence of packets including attacker packets presented to a network to be attacked and response packets corresponding to response packets that would be generated by the network in response to being presented with various ones of the attacker packets.

15. The method of claim 6, wherein:

each attack instance of the set of available attack instances is implemented as a set of packets, the content portion of the attack instance being distributed among the set of packets;

at least one of the transformation rules is a packet-modifying transformation rule that modifies the set of packets of an attack;

selecting one of the plurality of transformation rules comprises selecting one of the at least one packet-modifying transformation rule; and

applying the selected transformation rule to transform the selected attack instance to create a modified attack instance comprises applying the selected packet-modifying transformation rule to the selected attack instance to create a modified attack instance having a modified set of packets.

16. The method of claim 6, wherein:

each attack instance of the set of available attack instances has a content portion;

at least one of the transformation rules is a content-modifying transformation rule that modifies the content portion of an attack;

selecting one of the plurality of transformation rules comprises selecting one of the at least one content-modifying transformation rule; and

applying the selected transformation rule to transform the selected attack instance to create a modified attack instance comprises applying the selected content-modifying transformation rule to the selected attack instance to create a modified attack instance having a modified content portion.

17. The method of claim 6, wherein repeating at least one of the attack selecting, rule selecting and rule applying steps a plurality of times comprises:

repeatedly applying the same selected rule to each of the selected attack instances to generate at least some of the corpus of modified attack instances.

18. The method of claim 17, wherein repeating at least one of the attack selecting, rule selecting and rule applying steps a plurality of times further comprises, after repeatedly applying a current selected transformation rule to each of the selected attack instances to generate the corpus of modified attack instances:

selecting another transformation rule as the current transformation rule;

selecting an attack instance from the corpus of modified attack instances as the selected attack instance; and

applying the current transformation rule to the selected attack instance to form another modified attack instance, the corpus of modified attack instances including the another modified attack instance.

19. A corpus of modified attack instances, each attack instance usable to obtain unauthorized access to or use of a network, the corpus of modified attack instances generated by:

selecting an attack instance from a set of available attack instances as a selected attack instance;

selecting one of a plurality of transformation rules of a formal transformation system, the plurality of transformation rules usable to modify an attack instance, each transformation rule substantially preserving the semantics of the selected attack instance;

applying the selected transformation rule to transform the selected attack instance to create a modified attack instance, the modified attack instance being another element of the set of available attack instances;

repeating the attack selecting, rule selecting and rule applying steps a plurality of times to create additional modified attack instances, each such modified attack instance being another element of the set of available attack instances; and

forming the corpus of modified attack instances from at least some of the available attack instances.

20. An intrusion detection system having a set of attack signatures, the intrusion detection system usable to detect attacks against a network location based on the set of attack signatures, at least one of the set of attack signatures being a modified attack signature generated by:

presenting each of a plurality of attack instances corresponding to a given attack to the intrusion detection system, the plurality of attack instances generated by modifying a given attack instance using a plurality of transformation rules of a formal transformation system, the transformation rules substantially preserving the semantics of the given attack instance;

determining, for each presented attack instance, whether the intrusion detection system generated an alert in response to being presented with that attack instance;

identifying at least one attack instance for which the intrusion detection system failed to generate an alarm;

identifying at least one attack instance for which the intrusion detection system failed to generate an alarm due to the intrusion detection system lacking a signature that matches that attack instance; and

for at least one such identified attack instance, modifying at least one attack signature presented to the intrusion detection system to form the modified attack signature, the modified attack signature usable by the intrusion detection system to detect the attack instance for which the intrusion detection system previously failed to generate an alarm.