Methods for cost-sensitive modeling for intrusion detection and response

• US 7,818,797 B1
• Filed: 10/11/2002
• Issued: 10/19/2010
• Est. Priority Date: 10/11/2001
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Miller, Matthew, Fan, Wei, Stolfo, Salvatore J., Lee, Wenke
• Primary Examiner(s): Parthasarathy; Pramila
• Application Number:
  US10/269,718
• Time in Patent Office: 2,930 Days
• Field of Search: 709/246, 709/209, 713/182, 713/189
• US Class Current: 726/22
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

A method of detecting an intrusion in the operation of a computer system based on a plurality of events. A rule set is determined for a training set of data comprising a set of features having associated costs. For each of a plurality of events, the set of features is computed and a class is predicted for the features with a rule of the rule set. For each event predicted as an intrusion, a response cost and a damage cost are determined, wherein the damage cost is determined based on such factors as the technique of the intrusion, the criticality of the component of the computer system subject to the intrusion, and a measure of progress of the intrusion. If the damage cost is greater than or equal to the response cost, a response to the event.

Claims

1. A method of modeling a cost-sensitive intrusion detection model, comprising:

(a) generating a training set of data suitable as input for machine learning, said training set of data comprising a set of features having associated costs;

(b) automatically determining, using a computer programmed to do so, at least one model based on said training set of data using machine learning;

(c) for each of a plurality of events, computing, using a computer programmed to do so, said set of features and predicting a class of said event using said at least one model;

(d) determining a response cost to be incurred by a computer system in responding to an event predicted as an intrusion in (c), wherein said response cost is estimated based upon the resources of the computer system to be expended in responding to the event, and determining a damage cost for an event predicted as an intrusion in (c), wherein said damage cost is determined based on at least one of the group consisting of a technique of the intrusion, a criticality of a component of the computer system subject to the intrusion, and a progress of the intrusion; and

(e) initiating a response to the event if the damage cost is greater than or equal to the response cost.

2. The method as recited in claim 1, wherein said generating a training set of data comprises training a sequence of training sets of data, wherein the training sets are ordered such that a first set of features of a first training set is a subset of a next subsequent set of features of a next subsequent training set, and wherein an associated cost of the first set of features is less than an associated cost of the next subsequent set of features.

3. The method as recited in claim 2, wherein said determining at least one model comprises determining an ordered sequence of rule sets for each respective training set in said ordered sequence of training sets, wherein the rule sets are ordered corresponding to the order of the respective training sets.

4. The method as recited in claim 3, further comprising, after said determining at least one model, for each rule in the ordered sequence of rule sets, determining a precision measurement indicative of the accuracy of the rule in predicting a class.

5. The method as recited in claim 4, wherein said determining a precision measurement comprises determining a ratio of positive counts of the rule to the total counts of the rule.

6. The method as recited in claim 4, further comprising, after said determining a precision measurement, for each said class, determining a threshold value indicative of a minimum precision for each class.

7. The method as recited in claim 6, wherein said computing said set of features comprises, beginning with a first rule set of said ordered sequence of rule sets, computing said set of features and predicting a class of said event with a rule of said rule set;

and if the precision measurement corresponding to said rule is less than the threshold corresponding to the class, repeating said computing said features with the next rule set in said ordered sequence of rule sets.

8. The method as recited in claim 6, wherein the threshold value is determined as the precision value for the rule in the rule set corresponding to said feature set having a greatest cost.

9. The method as recited in claim 1, wherein a set of features comprises features computed using data available at the beginning of an event.

10. The method as recited in claim 1, wherein a set of features comprises features computed at any time during a duration of an event, and is maintained throughout the duration of the event.

11. The method as recited in claim 1, wherein a set of features comprises features computed using data from a plurality of events within a predetermined duration of time.

12. The method as recited in claim 1, wherein said determining at least one model comprises learning a rule set using a RIPPER algorithm.

13. The method as recited in claim 12, wherein said determining at least one model comprises learning an unordered rule set.

14. The method as recited in claim 1, further comprising logging an attack report if the damage cost is less than the response cost.

15. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with providing an automated response.

16. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with terminating a session.

17. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with implementing an operational rule.

18. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with rebooting the system.

19. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with recording a session.

20. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with providing a notification.

21. The method as recited in claim 1, wherein determining a response cost comprises estimating a cost associated with providing a manual response.

22. A method of modeling a cost-sensitive intrusion detection model, using at least one model, comprising:

(a) for each of a plurality of events, computing, using a computer programmed to do so, said set of features and predicting a class of said event using said at least one model;

(b) determining a response cost to be incurred by a computer system in responding to an event predicted as an intrusion in (a), wherein said response cost is estimated based upon the resources of the computer system to be expended in responding to the event; and

determining a damage cost for an event predicted as an intrusion in (a), wherein said damage cost is determined based on at least one of the group consisting of a technique of the intrusion, a criticality of a component of the computer system subject to the intrusion, and a progress of the intrusion; and

(c) initiating a response to the event if the damage cost is greater than or equal to the response cost.

23. The method as recited in claim 22, wherein the at least one model comprises a plurality of rule sets that are in an ordered sequence such that a first set of features evaluated by a first rule set is a subset of a next subsequent set of features evaluated by a next subsequent rule set, and wherein an associated cost of the first set of features is less than an associated cost the next subsequent set of features, and wherein said computing said set of features comprises, for each of a plurality of events, beginning with said first rule set, computing said set of features and predicting a class of said event with a rule of said rule set.

24. The method as recited in claim 23, wherein said computing said set of features and predicting a class of said event with a rule of said rule set comprises repeating said computing said set of features and predicting a class of said event with the next rule set in said ordered sequence of rule sets if a precision measurement indicative of the accuracy of said rule in predicting a class is less than a threshold value indicative of a minimum precision for said class.

25. The method as recited in claim 22, wherein said at least one model comprises a rule set learned using a RIPPER algorithm.

26. The method as recited in claim 25, further comprising learning an unordered rule set.

27. The method as recited in claim 22, further comprising logging an attack report if the damage cost is less than the response cost.

28. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with providing an automated response.

29. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with terminating a session.

30. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with implementing an operational rule.

31. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with rebooting the system.

32. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with recording a session.

33. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with providing a notification.

34. The method as recited in claim 22, wherein determining a response cost comprises estimating a cost associated with providing a manual response.

35. A method of modeling a cost-sensitive intrusion detection model, comprising:

(a) generating a training set of data suitable as input for machine learning, said training set of data comprising a set of features having associated costs;

(b) automatically determining, using a computer programmed to do so, at least one model based on said training set of data using machine learning;

(c) for each of a plurality of events, computing, using a computer programmed to do so, said set of features and predicting a class of said event using said at least one model;

(d) determining a response cost to be incurred by a computer system in responding to an event predicted as an intrusion in (c), wherein said response cost is estimated based upon the resources of the computer system to be expended in responding to the event,

(e) determining a damage cost for an event predicted as an intrusion in (c), wherein said damage cost is determined based on at least one of the group consisting of a technique of the intrusion, a criticality of a component of the computer system subject to the intrusion, and a progress of the intrusion;

(f) determining a metric for comparing the response cost and the damage costs; and

(g) initiating a response to the event if the damage cost is greater than or equal to the response cost.