Instance based learning framework for effective behavior profiling and anomaly intrusion detection

• US 20070061882A1
• Filed: 09/13/2005
• Published: 03/15/2007
• Est. Priority Date: 09/13/2005
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Mukhopadhyay, Debapriyay, Banerjee, Satyajit
• Granted Patent: US 7,814,548 B2
• Time in Patent Office: Days
• US Class Current: 726/23
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

Intruders into a computer are detected by capturing historical data input into the computer by a user during a training mode, by profiling the historical data during the training mode to identify normal behavior, by capturing test data input by the user into the computer during an operational mode, by comparing the test data with the profiled historical data in accordance with a predetermined similarity metric during the operational mode to produce similarity results, and by evaluating the similarity results during the operational mode to identify abnormal data.

Claims

1. A computer implemented method for detecting intruders into a computer comprising:

capturing historical data input into the computer by a user during a training mode;

profiling the historical data during the training mode to identify normal behavior;

capturing test data input by the user into the computer during an operational mode;

comparing the test data with the profiled historical data in accordance with a predetermined similarity metric during the operational mode to produce similarity results; and

,

evaluating the similarity results during the operational mode to identify abnormal data.

2. The method of claim 1 wherein the capturing of test data comprises:

converting streams of command traces into a set of fixed length instances of temporally adjacent actions;

labeling each instance with a time stamp.

3. The method of claim 1 wherein the profiling of the historical data comprises partitioning the historical data into a set of clusters, wherein each of the clusters represents a specific behavioral pattern of the user.

4. The method of claim 3 wherein the profiling of the historical data further comprises updating the user behavioral profile periodically.

5. The method of claim 4 wherein the updating of the user behavioral profile periodically comprises:

identifying an oldest cluster;

deleting the identified cluster; and

,

adding a new cluster for newly added instances of historical data.

6. The method of claim 3 wherein the partitioning of the historical data comprises:

selecting dynamically a set of representative instances, wherein each of the representative instances represents a corresponding one of the clusters;

calculating similarity scores between a query instance and only the representative instances; and

,

assigning the query instance to a particular cluster if and only if the similarity score between the query instance and the particular cluster is in a predetermined range.

7. The method of claim 6 wherein the partitioning of the historical data further comprises compressing the query instance with respect to the representative instance of the particular cluster.

8. The method of claim 6 wherein the assigning of the query instance to a particular cluster comprises assigning the query instance to the particular cluster if the query instance is not identical to the representative instance of the particular cluster and otherwise incrementing a frequency count associated with the representative instance of the particular cluster.

9. The method of claim 6 wherein the assigning of the query instance to the particular cluster comprises creating a new cluster if the similarity scores between the query instance and the clusters of the set are not within the predetermined range.

10. The method of claim 1 wherein the profiling of the historical data comprises partitioning the historical data into a set of clusters such that each of the clusters represents a specific behavioral pattern of the user, wherein the comparing of the test data with the profiled historical data comprises calculating a set of similarity scores between the test data and the set of clusters in accordance with the predetermined similarity metric, and wherein the evaluating of the similarity results comprises determining a possible intrusion if each of the similarity scores is not within a predetermined range.

11. The method of claim 10 wherein the predetermined range is defined by a maximum similarity score and a lower bound of the similarity scores with one data point mismatch.

12. The method of claim 1 wherein the evaluating of the similarity results comprises identifying whether a pattern of the test data matches the profile of the historical data.

13. The method of claim 12 wherein the profiling of the historical data comprises partitioning the historical data into a set of clusters such that each of the clusters represents a specific behavioral pattern of the user, and wherein the evaluating of the similarity results comprises labeling the test data as normal if the pattern of the test data matches the profile of the historical data for at least one of the clusters and otherwise labeling the test data as intrusive.

14. The method of claim 13 wherein the comparing of the test data with the profiled historical data comprises comparing the test data with representative instances of the clusters in the set of clusters.

15. The method of claim 1 further comprising determining a set of training data falling within a predetermined range of the similarity results produced from the similarity metric.

16. A computer implemented method for detecting intruders into a computer system comprising:

establishing clusters of training data input into the computer system by a user during a training mode, wherein each cluster includes a representative instance, a frequency associated with the representative instance, and pointers that point to a list of non-representative instances whose similarity scores with the representative instance is above a predetermined threshold, and wherein the similarity scores are based on a predetermined similarity metric;

comparing test data with the representative instances of the clusters in accordance with the predetermined similarity metric during an operational mode to produce similarity results, wherein the test data is input by the user into the computer system; and

,

evaluating the similarity results during the operational mode to identify intrusions.

17. The method of claim 16 wherein each of the clusters includes a time stamp for the corresponding representative instance.

18. The method of claim 16 wherein the test data comprises command traces of fixed length.

19. The method of claim 16 wherein the establishing of clusters comprises:

calculating similarity scores between a training instance and the representative instances; and

,

assigning the training instance to a particular cluster only if the similarity score corresponding to the particular cluster is within a predetermined range.

20. The method of claim 19 wherein the assigning of the training instance to a particular cluster comprises assigning the training instance to the particular cluster if the training instance is not identical to the representative instance of the particular cluster and otherwise incrementing the frequency associated with the representative instance of the particular cluster.

21. The method of claim 19 wherein the assigning of the training instance to the particular cluster comprises creating a new cluster with the training instance as the representative instance of the new cluster if the similarity scores between the training instance and the clusters of the set are not within the predetermined range.

22. The method of claim 16 wherein the evaluating of the similarity results comprises labeling the test data as normal if the test data has a similarity score with the representative instance of at least one of the clusters that is within a predetermined range and otherwise labeling the test data as intrusive.

23. The method of claim 22 wherein the predetermined range comprises values greater than d_i−

σ

_i, wherein d_i and σ

_i denote, respectively, the weighted mean and the standard deviation of the similarity scores.

24. A computer implemented method for detecting intruders into a computer system comprising:

capturing first data input into the computer system;

establishing clusters of the first data, wherein each cluster includes a representative instance, a frequency associated with the representative instance, and pointers that point to a list of non-representative instances whose similarity scores with the representative instance are within a predetermined range, and wherein the similarity scores are based on a predetermined similarity metric;

capturing second data input into the computer system;

comparing the second data with the representative instances in accordance with the predetermined similarity metric to produce similarity results; and

,

evaluating the similarity results to identify abnormal data.

25. The method of claim 24 wherein the capturing of second data comprises converting command traces into corresponding fixed length instances of temporally adjacent actions.

26. The method of claim 24 wherein the establishing of clusters comprises:

calculating similarity scores between a query instance and the representative instances; and

,

assigning the query instance to a particular cluster only if the similarity score corresponding to the particular cluster is within a predetermined range.

27. The method of claim 26 wherein the assigning of the query instance to a particular cluster comprises assigning the query instance to the particular cluster only if the query instance is not identical to the representative instance of the particular cluster and otherwise incrementing the frequency of the representative instance of the particular cluster.

28. The method of claim 24 wherein the establishing of clusters comprises:

calculating similarity scores between a query instance and the representative instances; and

,

creating a new cluster with the query instance as the representative instance of the new cluster only if the none of the similarity scores are within a predetermined range.

29. The method of claim 24 further comprising updating the clusters periodically by identifying an oldest cluster, by deleting the identified cluster, and by adding a new cluster for newly added instances of the first data.