Identification of anomalous data records

• US 7,668,843 B2
• Filed: 12/14/2005
• Issued: 02/23/2010
• Est. Priority Date: 12/22/2004
• Status: Active Grant

• Current Assignee: Regents of The University of Minnesota (University of Minnesota)
• Original Assignee: Regents of The University of Minnesota (University of Minnesota)
• Inventors: Kumar, Vipin, Ertoz, Levent
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US11/302,989
• Publication Number:
  US 20060161592A1
• Time in Patent Office: 1,532 Days
• Field of Search: None
• US Class Current: 706/20
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• 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

Abstract

Identifying anomalies or outliers in a set of data records employs a distance or similarity measure between features of record pairs that depends upon the frequencies of the feature values in the set. Feature distances may be combined for a total distance between record pairs. An outlier is indicated for a certain score that may be based upon the pairwise distances. Outliers may be employed to detect intrusions in computer networks.

Claims

1. A method for execution by one or more digital processors, the method for detecting whether a current record in a dataset of records is an anomalous record, comprising:

defining a feature of the records in the dataset;

calculating, by the one or more digital processors, a plurality of pairwise distances between a value of the feature in the current record and values of the feature in at least some of the records in the dataset, where each pairwise distance is either;

(A) small for mismatches between the values when both of the values rarely occur in the dataset records or where the distance is large for mismatches between the values when both of the values commonly occur in the dataset records;

or

(B) large for mismatches between the values when both of the values rarely occur in the dataset records or where the distance is small when both of the values commonly occur in the dataset records; and

in response to the plurality of distances d, producing a score for the current record;

indicating that the current record is anomalous if the score meets a predetermined criterion;

wherein the distances are responsive to the frequency Freq(v_i) of the value v_i of the feature in the current record and to the frequency Freq(v_j) of the value v_j of the feature in another of the records in the dataset; and

calculating each of the pairwise distances d from a value v_i of the feature in the current record and a value v_j of the feature in the other of the dataset records according to the relation

2. The method of claim 1 comprising defining d=0 for v_i=v_j.

3. The method of claim 1 further comprising:

defining a plurality of features of the records in the dataset;

for each of the features, calculating one of the pairwise distances between the each feature of the current record and a corresponding feature of another of the dataset records;

combining the distances to produce a total distance between the current record and the other of the dataset records; and

calculating the score for the current record in response to the total distance.

4. The method of claim 3 where at least some of the distances d_k are summed to produce the total distance D.

5. The method of claim 1 where the feature is categorical rather than numeric, comprising attaching a numeric value to different values of the feature.

6. The method of claim 5 where the numeric value is unique for each value of the categorical value.

7. The method of claim 1 further comprising:

selecting a subset of the dataset records as samples;

calculating the pairwise distances from the current record only to the samples.

8. The method of claim 7 where the number of the samples is sufficiently large enough to include small modes of behavior of the dataset.

9. The method of claim 1 where the current record is indicated as anomalous if the score bears a predetermined relationship to a threshold.

10. The method of claim 9 where the threshold is variable.

11. The method of claim 1 further comprising:

defining a neighborhood amount for each of the values; and

determining that a match exists between the values if they differ by less than the neighborhood amount.

12. A storage medium containing instructions executable in a digital processor for carrying out a method comprising:

defining a feature of the records in the dataset;

calculating a plurality of pairwise distances between a value v_i of the feature in the current record and values v_j of the feature in at least some of the records in the dataset, where each pairwise distance d is either;

(A) small for mismatches between v_i and v_j when both v_i and v_j rarely occur in the dataset records or where the distance is large for mismatches between v_i and v_j when both v_i and v_j commonly occur in the dataset records;

or

(B) large for mismatches between v_i and v_j when both v_i and v_j rarely occur in the dataset records or where the distance is small when both v_i and v_j commonly occur in the dataset records; and

in response to the plurality of distances d, producing a score for the current record;

indicating that the current record is anomalous if the score meets a predetermined criterion;

wherein the distances are responsive to the frequency Freq(v_i) of the value v_i of the feature in the current record and to the frequency Freq(v_j) of the value v_j of the feature in another of the records in the dataset; and

calculating each of the pairwise distances d from a value v_i of the feature in the current record and a value v_j of the feature in the other of the dataset records according to the relation

13. The medium of claim 12 where the method further comprises:

defining a plurality of features of the records in the dataset;

for each of the features, calculating one of the pairwise distances between the each feature of the current record and a corresponding feature of another of the dataset records;

combining the distances to produce a total distance between the current record and the other of the dataset records; and

calculating the score for the current record in response to the total distance.

14. Apparatus for detecting whether a current record in a dataset is an anomalous record, comprising:

a feature digital preprocessor for defining a feature of the records in the dataset;

a distance calculator for calculating a plurality of pairwise distances between a value of the feature in the current record and a value of the feature in at least some of the records in the dataset, where each pairwise distance is either;

(A) small for mismatches between the values when both values rarely occur in the dataset records or where the distance is large for mismatches between the values when both of the values commonly occur in the dataset records;

or

(B) large for mismatches between the values when both values rarely occur in the dataset records or where the distance is small when both of the values commonly occur in the dataset records;

an outlier detector for producing a score for the current record in response to the plurality of distances, and for indicating that the current record is anomalous if the score meets a predetermined criterion;

wherein the distances are responsive to the frequency Freq(v_i) of the value v_i of the feature in the current record and to the frequency Freq(v_j) of the value v_j of the feature in another of the records in the dataset; and

each of the pairwise distances d from a value v_i of the feature in the current record and a value v_j of the feature in the other of the dataset records is calculated according to the relation

15. The apparatus of claim 14 where:

the feature digital preprocessor is adapted for defining a plurality of features of the records in the dataset;

the distance calculator is adapted for calculating one of the pairwise distances d_k between the each feature of the current record and a corresponding feature of another of the dataset records for each of the features; and

the outlier detector is adapted for combining the distances to produce a total distance representing a total distance between the current record and the other of the dataset records, and for calculating the score for the current record in response to the total distance.

16. A system for detecting intrusions in a computer attached to a network, comprising:

a data-capture module for receiving message records from the network;

a feature digital preprocessor for defining a feature of the records in the dataset;

a distance calculator for calculating a plurality of pairwise distances between a value of the feature in the current record and a value of the feature in at least some of the records in the dataset, where each pairwise distance is either;

(A) small for mismatches between the values when both values rarely occur in the dataset records or where the distance is large for mismatches between the values when both of the values commonly occur in the dataset records;

or

(B) large for mismatches between the values when both values rarely occur in the dataset records or where the distance is small when both of the values commonly occur in the dataset records;

an outlier detector for producing a score for the current record in response to the plurality of distances, and for indicating that the current record is anomalous if the score meets a predetermined criterion;

wherein the distances are responsive to the frequency Freq(v_i) of the value v_i of the feature in the current record and to the frequency Freq(v_j) of the value v_j of the feature in another of the records in the dataset; and

each of the pairwise distances d from a value v_i of the feature in the current record and a value v_j of the feature in the other of the dataset records is calculated according to the relation

17. The system of claim 16 further comprising a filter for removing certain records from the dataset.

18. The system of claim 16 further comprising a known-detector for detecting records having known attacks, and for removing such records from the dataset.

19. The system of claim 18 further comprising a pattern analyzer for summarizing a group of the anomalous records.

20. The system of claim 19 where the pattern analyzer is adapted to develop models for intrusions, and to send the models to the known-detector.

21. The system of claim 16 comprising defining d=0 for v_i=v.