Method and system for detecting intrusive anomalous use of a software system using multiple detection algorithms

• US 20060085854A1
• Filed: 10/19/2004
• Published: 04/20/2006
• Est. Priority Date: 10/19/2004
• Status: Active Grant

• Current Assignee: StrataCloud, Inc. (Exitlag LLC)
• Original Assignee: Reflex Security, Inc. (Exitlag LLC)
• Inventors: Agrawal, Subhash C., Young, Jonathan H., Wimer, Scott M.
• Granted Patent: US 8,108,929 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A method of detecting an intrusion into (or an anomaly in a behavior of) a target software system begins by instrumenting the target software system to generate behavior data representing a current observation or observation aggregate. The method then determines whether the current observation or observation aggregate warrants a second level examination; preferably, this determination is made by processing the current observation or observation aggregate through a first level detection algorithm that provides a first, provisional indication of a possible intrusion. If a result of executing the first level detection algorithm indicates that the current observation or observation aggregate warrants a second level examination, the method continues by processing the current observation or observation aggregate through at least one or more second level detection algorithms to provide a second, more definite, fine grain indication of a possible intrusion. The observation aggregates used by the first and second level detection algorithms may be the same or different. The first and second level detection algorithms may be executed in the same or different systems, machines or processors. The target software system operation may be suspended as the current observation or observation aggregate is processed through the one or more second level detection algorithms. A given action (e.g., sending an alert, logging the event, activating a countermeasure, or the like) may be taken if the result of the second level examination indicates a possible intrusion. Multiple algorithms may be executed together within a single examination level, with the individual results then analyzed to obtain a composite result or output indicative of intrusive or anomalous behavior.

Claims

1. A method of detecting an intrusion into a target software system, comprising:

instrumenting the target software system to generate behavior data representing a current observation or observation aggregate;

processing the current observation or observation aggregate through a first level detection algorithm that provides a first, provisional indication of a possible intrusion;

determining whether an intrusion has occurred or whether the current observation or observation aggregate warrants a second level examination; and

if a result of executing the first level detection algorithm indicates that the current observation or observation aggregate warrants a second level examination, processing the current observation or observation aggregate through at least one or more second level detection algorithms to provide a second, more definite indication of a possible intrusion.

2. The method of detecting an intrusion as described in claim 1 wherein the first level detection algorithm has a computational-efficiency that is greater than a computational-efficiency of the second level detection algorithm, wherein computational efficiency is measured as a given function of memory and processing requirements.

3. The method of detecting an intrusion as described in claim 2 wherein the second level detection algorithm uses floating point arithmetic operations.

4. The method of detecting an intrusion as described in claim 1 wherein the target software system comprises a kernel mode and a user mode, the first level detection algorithm being executed in the kernel mode and at least one second level detection algorithm being executed in the user mode.

5. The method of detecting an intrusion as described in claim 1 wherein the step of processing the current observation or observation aggregate through at least one or more second level detection algorithms processes the current observation or observation aggregate through at least a pair of second level detection algorithms whose outputs are analyzed according to a given function to provide the second, more definite indication of the possible intrusion.

6. The method as described in claim 5 wherein the given function is selected from a set of functions, namely, linear functions, non-linear functions, rules-based functions, and logical combinations thereof.

7. The method as described in claim 5 wherein the outputs are combined according to the given function concurrently.

8. The method of detecting an intrusion as described in claim 1 wherein the first level detection algorithm computes a metric from the current observation or observation aggregate and compares the metric against a given threshold value to determine whether the current observation or observation aggregate warrants the second level examination.

9. The method of detecting an intrusion as described in claim 1 wherein the first level detection algorithm implements a given mathematical process using non-floating point computations to determine whether the current observation or observation aggregate warrants the second level examination.

10. The method of detecting an intrusion as described in claim 9 wherein the given mathematical process is a Markov model process or an ellipsoidal model process.

11. The method of detecting an intrusion as described in claim 1 wherein the one or more second level detection algorithms are selected from a set of mathematical models that are executed using floating-point computations and that include:

ellipsoidal models, k-means models, decision tree models, support vector machine (SVM) models, Markov process models, and combinations thereof.

12. The method of detecting an intrusion as described in claim 1 further including the step of suspending operation of the target software system during the step of processing the current observation or observation aggregate through the one or more second level detection algorithms.

13. The method of detecting an intrusion as described in claim 1 wherein the the suspending step conditionally suspends a given operation of the target software system that is suspected of being a target of the intrusion.

14. The method of detecting an intrusion as described in claim 1 further including the step of executing the one or more second level detection algorithms in a distinct machine.

15. The method of detecting an intrusion as described in claim 1 further including the step of taking a given action if the result of the second level examination indicates a possible intrusion.

16. A method of detecting an anomaly in a behavior of a target software system, comprising:

instrumenting the target software system to generate behavior data representing a current observation or observation aggregate;

determining whether the current observation or observation aggregate warrants a second level examination by processing the current observation or observation aggregate through a set of one or more first level detection algorithms to provides a first provisional indication of a possible anomaly; and

if a result of executing the set of one or more first level detection algorithms indicates that the current observation or observation aggregate warrants a second level examination, processing the current observation or observation aggregate through at least one or more second level detection algorithms to provide a second, more definite indication of a possible anomaly.

17. The method as described in claim 16 further including the step of conditionally suspending a given operation of the target software system that is suspected of causing the anomaly while executing the one or more second level detection algorithms.

18. The method as described in claim 16 wherein at least one of the second level detection algorithms is executed in an off-line process.

19. The method as described in claim 16 wherein at least one of the second level detection algorithms is executed in a processor distinct from a processor that executes the first level detection algorithm.

20. The method as described in claim 16 further including the step of processing the current observation or observation aggregate through at least one or more second level detection algorithms to provide a second, more definite indication even if executing the one or more first level detection algorithms does not indicate a possible anomaly.

21. The method as described in claim 20 wherein the processing provides a baseline indication of an operating status of the target software system.

22. The method as described in claim 16 wherein the target software system comprises a kernel mode and a user mode, at least one first level detection algorithm being executed in the kernel mode and at least one second level detection algorithm being executed in the user mode.

23. The method as described in claim 22 wherein the first level detection algorithm is executed a protected memory area of the kernel.

24. The method as described in claim 16 wherein the step of processing the current observation or observation aggregate through at least one or more second level detection algorithms processes the current observation or observation aggregate through at least a pair of second level detection algorithms whose outputs are analyzed according to a given function.

25. The method as described in claim 24 wherein the given function is selected from a set of functions, namely, linear functions, non-linear functions, rules-based functions, and logical combinations thereof.

26. The method as described in claim 16 wherein execution of the target software system continues despite the possible anomaly while the second level examination is performed.

27. A method of detecting an intrusion into a target software system comprises a kernel mode and a user mode, comprising:

instrumenting the target software system to generate behavior data representing a current observation or observation aggregate;

in first level examination, determining whether the current observation or observation aggregate warrants a second level examination by processing, in a sequential manner, the current observation or observation aggregate through a set of first level detection algorithms executing in the kernel mode and that provides a first indication of a possible intrusion;

if a result of the first level examination indicates that the current observation or observation aggregate warrants a second level examination, processing the current observation or observation aggregate through at least one or more second level detection algorithms executing in the user mode to provide a second indication of a possible intrusion; and

as a result of the second level examination, taking a given action.

28. The method of detecting an intrusion as described in claim 27 wherein the given action generates an output indicating that an intrusion has occurred or initiates a given counter action.

29. The method of detecting an intrusion as described in claim 27 wherein a given first level detection algorithm computes a metric from the current observation or observation aggregate and compares the metric against a given threshold value to determine whether the current observation or observation aggregate warrants the second level examination.

30. The method of detecting an intrusion as described in claim 27 wherein the one or more second level detection algorithms are selected from a set of mathematical models that are executed using floating-point computations and that include:

ellipsoidal models, k-means models, decision tree models, support vector machine (SVM) models, Markov process models, and combinations thereof.

31. A method of detecting an intrusion into a target software system that has been instrumented to generate behavior data representing a current observation or observation aggregate, comprising:

determining whether the current observation or observation aggregate warrants a second level examination by processing the current observation or observation aggregate through a first level detection algorithm executing that provides a first indication of a possible intrusion; and

if a result of executing the at least first level detection algorithm indicates that the current observation or observation aggregate warrants a second level examination, processing the current observation or observation aggregate through a second level detection algorithm to provide a second indication of a possible intrusion;

wherein, as compared to the second level detection algorithm, the first level detection algorithm has greater computational efficiency.

32. The method of detecting an intrusion as described in claim 31 further including the step of:

as a result of the second level examination, taking a given action.

33. The method of detecting an intrusion as described in claim 31 wherein the target software system comprises a kernel mode space and at least one second level detection algorithm being executed in the user mode.

34. In a software system that has been instrumented to generate behavior data representing a current observation or observation aggregate, comprising:

an intrusion detection mechanism, comprising;

first level detection code executable in a processor to determine whether the current observation or observation aggregate represents a possible intrusion;

second level detection code, executable in a processor in response to a determination by the first level detection code that a possible intrusion is occurring, to attempt to verify occurrence of the possible intrusion; and

code executable in a processor and that outputs a given indication upon a determination by the second level detection code that the possible intrusion has occurred.

35. A method of detecting intrusive or anomalous behavior associated with a target software system that has been instrumented to generate behavior data representing a current observation or observation aggregate, comprising:

at a given examination level within a hierarchical set of one or more examination levels, determining whether the current observation or observation aggregate is indicative of intrusive or anomalous behavior using a set of two or more algorithms executed in parallel or in sequence to produce a given output;

taking a given action in response to the given output.

36. The method as described in claim 35 wherein the two or more algorithms comprise a first, temporal-based algorithm and a second, frequency-based algorithm.

37. The method as described in claim 35 wherein the two or more algorithms comprise first and second instances of a given algorithm executed against first and second data.

38. The method as described in claim 35 wherein the two or more algorithms generate respective outputs and wherein a given function of those respective outputs generates the given output.