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

• US 7,814,548 B2
• Filed: 09/13/2005
• Issued: 10/12/2010
• Est. Priority Date: 09/13/2005
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Banerjee, Satyajit, Mukhopadhyay, Debapriyay
• Primary Examiner(s): Moazzami; Nasser
• Assistant Examiner(s): Lewis; Lisa
• Application Number:
  US11/224,880
• Publication Number:
  US 20070061882A1
• Time in Patent Office: 1,855 Days
• Field of Search: 726/23, 726/24
• US Class Current: 726/24
• 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 instance-based learning 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 by converting streams of shell command traces into fixed length instances;

profiling the fixed length instances to identify normal behavior using a single data structure and a clustering algorithm with respect to the data structure, the data structure comprising a list of tables, the tables among said list of tables having a size that is limited by an upper bound;

determining a representative instance;

comparing the representative instance to the fixed length instances utilizing the clustering algorithm in order to create clusters that are mapped to the tables among said list of tables;

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 identify test data that falls outside of previously identified clusters,

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

calculating similarity scores between query instances and each of the representative instances,

using the similarity metric, producing a real, non-negative root for each similarity score within a predefined interval,

using each root, determining the representation in the list of tables of each respective query instance

displaying a notification upon identifying the test data falling outside previously identified clusters.

2. The method of claim 1 wherein the profiling of the historical data further comprises updating a user behavioral profile periodically.

3. The method of claim 2 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.

4. The method of claim 1 further comprising

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.

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

6. The method of claim 4 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.

7. The method of claim 4 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.

8. 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.

9. The method of claim 8 wherein the predetermined range is defined by a maximum similarity score and a lower bound of the similarity scores.

10. 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.

11. The method of claim 10 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.

12. The method of claim 11 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.

13. 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 predetermined similarity metric.

14. A non-transitory computer-readable medium having computer-executable instructions for performing steps to detect intruders into a computer, said steps comprising:

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

profiling the historical data during the training mode by converting streams of shell command traces into fixed length instances;

profiling the fixed length instances to identify normal behavior using a single data structure and a clustering algorithm with respect to the data structure, the data structure comprising a list of tables, the tables among the list of tables having a size that is limited by an upper bound;

determining a representative instance;

comparing the representative instance to the fixed length instances utilizing the clustering algorithm in order to create clusters that are mapped to the tables among said list of tables;

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 test data that falls outside of previously identified clusters,

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

calculating similarity scores between query instances and each of the representative instances,

using the similarity metric, producing a real, non-negative root for each similarity score within a predefined interval,

using each root, determining the representation in the list of tables of each respective query instance;

wherein the profiling of the historical data further comprises updating a user behavioral profile periodically; and

displaying a notification upon identifying the test data falling outside previously identified clusters.

15. The computer-readable medium claim 14 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.

16. The computer-readable medium of claim 14 said steps further comprising;

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.

17. The computer-readable medium of claim 14 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.

18. The computer-readable medium of claim 17 wherein the predetermined range is defined by a maximum similarity score and a lower bound of the similarity scores.

19. A computer implemented method utilizing an instance based learning framework 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 by converting streams of shell command traces into fixed length instances;

profiling the fixed length instances to identify normal behavior using a single data structure and a clustering algorithm with respect to the data structure, the data structure comprising a list of tables, the tables among said list of tables having a size that is limited by an upper bound;

determining a representative instance;

comparing the representative instance to the fixed length instances utilizing the clustering algorithm in order to create clusters that are mapped to the tables among said list of tables;

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 test data that falls outside of previously identified clusters,

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

calculating similarity scores between query instances and each of the representative instances,

using the similarity metric, producing a real, non-negative root for each similarity score within a predefined interval,

using each root, determining the representation in the list of tables of each respective query instance;

determining a set of training data falling within a predetermined range of the similarity results produced from the predetermined similarity metric; and

displaying a notification upon identifying the test data falling outside previously identified clusters.

20. The method of claim 19 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.

21. The method of claim 20 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.