Automated anomaly detection

• US 20070112824A1
• Filed: 11/22/2004
• Published: 05/17/2007
• Est. Priority Date: 11/27/2003
• Status: Active Grant

• Current Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Original Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Inventors: Hatch, Richard, Kilvington, Simon, Brown, Neil, Lock, Zoe, Hood, Alan, Thie, Claire, Zakiuddin, Mohammed, Peeling, Emma
• Granted Patent: US 7,627,543 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0754 by exceeding limits
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 5/025 Extracting rules from data

Abstract

A method of anomaly detection applicable to telecommunications or retail fraud or software vulnerabilities uses inductive logic programming to develop anomaly characterisation rules from relevant background knowledge and a training data set, which includes positive anomaly samples of data covered by rules. Data samples include 1 or 0 indicating association or otherwise with anomalies. An anomaly is detected by a rule having condition set which the anomaly fu,lfils. Rules are developed by addition of conditions and unification of variables, and are filtered to remove duplicates, equivalents, symmetric rules and unnecessary conditions. Overfitting of noisy data is avoided by an encoding cost criterion. Termination of rule construction involves criteria of rule length, absence of negative examples, rule significance and accuracy, and absence of recent refinement. Iteration of rule construction involves selecting rules with unterminated construction, selecting rule refinements associated with high accuracies, and iterating a rule refinement, filtering and evaluation procedure to identify any refined rule usable to test data. Rule development may use first order logic or Higher Order logic.

Claims

1. A method of anomaly detection incorporating the steps of:

a) developing a rule set of at least one anomaly characterisation rule from a training data set and any available relevant background knowledge using at least first order logic, a rule covering a proportion of positive anomaly examples of data in the training data set, and

b) applying the rule set to test data for anomaly detection therein.

2. An automated method of anomaly detection incorporating using computer apparatus to execute the steps of:

a) developing a rule set of at least one anomaly chacterisation rule from a training data set and any available relevant background knowledge using at least first order logic, a rule covering a proportion of positive anomaly examples of data in the training data set, and

b) applying the rule set to test data for anomaly detection therein.

3. A method according to claim 2 wherein the positive anomaly examples are associated with fraud or software vulnerabilities.

4. A method according to claim 2 including developing the rule set using Higher-Order logic.

5. A method according to claim 4 including developing the rule set by:

a) forming an alphabet having selector functions allowing properties of the training data set to be extracted, together with at least one of the following;

additional concepts, background knowledge constant values and logical AND and OR functions,

b) forming current rules from combinations of items in the alphabet such that type consistency and variable consistency is preserved,

c) evaluating the current rules for adequacy of classification of the training data set,

d) if no current rule adequately classifies the training data set, generating new rules by applying at least one genetic operator to the current rules, a genetic operator having one of the following functions;

i) combining two rules to form a new rule, ii) modifying a single rule by deleting one of its conditions or adding a new condition to it, or iii) changing one of a rule'"'"'s constant values for another of an appropriate type, and

e) designating the new rules as the current rules and iterating steps c) onwards until a current rule adequately classifies the training data set or a predetermined number of iterations is reached.

6. A method according to claim 2 wherein data samples in the training data set have characters indicating whether or not they are associated with anomalies.

7. A method according to claim 6 for detecting telecommunications or retail fraud from anomalous data.

8. A method according to claim 7 employing inductive logic programming to develop the rule set.

9. A method according to claim 8 wherein the at least one anomaly characterisation rule has a form that an anomaly is detected or otherwise by application of the rule according to whether or not a condition set of at least one condition associated with the rule is fulfilled.

10. A method according to claim 9 wherein the at least one anomaly characterisation rule is developed by refining a most general rule by at least one of:

a) addition of a new condition to the condition set; and

b) unification of different variables to become constants or structured terms.

11. A method according to claim 10 wherein a variable in the at least one anomaly characterisation rule which is defined as being in constant mode and is numerical is at least partly evaluated by providing a range of values for the variable, estimating an accuracy for each value and selecting a value having optimum accuracy.

12. A method according to claim 11 wherein the range of values is a first range with values which are relatively widely spaced, a single optimum accuracy value is obtained for the variable, and the method includes selecting a second and relatively narrowly spaced range of values in the optimum accuracy value'"'"'s vicinity, estimating an accuracy for each value in the second range and selecting a value in the second range having optimum accuracy.

13. A method according to claim 12 including filtering to remove rule duplicates and rule equivalents, i.e. any rule having like but differently ordered conditions compared to another rule, and any rule which has conditions which are symmetric compared to those of another rule.

14. A method according to claim 13 including filtering to remove unnecessary ‘

less than or equal to’

(“

Iteq”

) conditions.

15. A method according to claim 14 wherein the unnecessary Iteq conditions are associated with at least one of ends of intervals, multiple Iteq predicates and equality condition and Iteq duplication.

16. A method according to claim 8 including implementing an encoding length restriction to avoid overfitting noisy data by rejecting a rule refinement if the refinement encoding cost in number of bits exceeds a cost of encoding positive examples covered by the refinement.

17. A method according to claim 8 including stopping construction of a rule in response to fulfilment of least one of three stopping criteria, such criteria being:

a) the number of conditions in any rule in a beam of rules being processed is greater than or equal to a prearranged maximum rule length,

b) no negative examples are covered by a most significant rule, which is a rule that;

i) is present in a beam currently being or having been processed,

ii) is significant,

iii) has obtained a highest likelihood ratio statistic value found so far, and

iv) has obtained an accuracy value greater than a most general rule accuracy value, and

c) no refinements were produced which were eligible to enter the beam currently being processed in a most recent refinement processing step.

18. A method according to claim 17 including adding the most significant rule to a list of derived rules and removing positive examples covered by the most significant rule from the training data set.

19. A method according to claim 8 including:

a) selecting rules which have not met rule construction stopping criteria,

b) selecting a subset of refinements of the selected rules associated with accuracy estimate scores higher than those of other refinements of the selected rules, and

c) iterating a rule refinement, filtering and evaluation procedure to identify any refined rule usable to test data.

20. Computer apparatus for anomaly detection programmed to execute the steps of:

a) developing a rule set of at least one anomaly characterisation rule from a training data set and any available relevant background knowledge using at least first order logic, a rule covering a proportion of positive anomaly examples of data in the training data set, and

b) applying the rule set to test data for anomaly detection therein.

21. Computer apparatus according to claim 20 wherein the positive anomaly examples are associated with fraud or software vulnerabilities.

22. Computer apparatus according to claim 20 programmed to develop the rule set using Higher-Order logic.

23. Computer apparatus according to claim 22 programmed to develop the rule set by:

a) forming an alphabet having selector functions allowing properties of the training data set to be extracted, together with at least one of the following;

additional concepts, background knowledge constant values and logical AND and OR functions,

b) forming current rules from combinations of items in the alphabet such that type consistency and variable consistency is preserved,

c) evaluating the current rules for adequacy of classification of the training data set,

d) if no current rule adequately classifies the training data set, generating new rules by applying at least one genetic operator to the current rules, a genetic operator having one of the following functions;

i) combining two rules to form a new rule, ii) modifying a single rule by deleting one of its conditions or adding a new condition to it, or iii) changing one of a rule'"'"'s constant values for another of an appropriate type, and

e) designating the new rules as the current rules and iterating steps c) onwards until a current rule adequately classifies the training data set or a predetermined number of iterations is reached.

24. Computer apparatus according to claim 20 wherein data samples in the training data set have characters indicating whether or not they are associated with anomalies.

25. Computer apparatus according to claim 20 wherein the at least one anomaly characterisation rule has a form that an anomaly is detected or otherwise by application of such rule according to whether or not a condition set of at least one condition associated with that rule is fulfilled.

26. Computer apparatus according to claim 20 programmed to develop the at least one anomaly characterisation rule by refining a most general rule by at least one of:

a) addition of a new condition to the condition set; and

b) unification of different variables to become constants or structured terms.

27. Computer apparatus according to claim 26 wherein a variable in the at least one anomaly characterisation rule is defined as being in constant mode and is numerical, and the computer apparatus is programmed to evaluate the at least one anomaly characterisation rule at least partly by providing a range of values for the variable, estimating an accuracy for each value and selecting a value having optimum accuracy.

28. Computer apparatus according to claim 25 programmed to filter out at least one of rule duplicates, rule equivalents and unnecessary Iteq conditions.

29. Computer apparatus according to claim 25 programmed to stop construction of a rule in response to fulfilment of at least one of three stopping criteria, such criteria being:

a) the number of conditions in any rule in a beam of rules being processed is greater than or equal to a prearranged maximum rule length,

b) no negative examples are covered by a most significant rule, which is a rule that;

i) is present in a beam currently being or having been processed,

ii) is significant,

iii) has obtained a highest likelihood ratio statistic value found so far, and

iv) bas obtained an accuracy value greater than a most general rule accuracy value, and

c) no refinements were produced which were eligible to enter the beam currently being processed in a most recent refinement processing step.

30. A computer software product comprising a computer readable medium containing computer readable instructions for controlling operation of computer apparatus to implement anomaly detection, wherein the computer readable instructions provide a means for controlling the computer apparatus to execute the steps of:

a) developing a rule set of at least one anomaly characterisation rule from a training data set and any available relevant background knowledge using at least first order logic, a rule covering a proportion of positive anomaly examples of data in the training data set, and

b) applying the rule set to test data for anomaly detection therein.

31. A computer software product according to claim 30 wherein the positive anomaly examples are associated with fraud or software vulnerabilities.

32. A computer software product according to claim 30 wherein the computer readable instructions provide for controlling computer apparatus to develop the rule set using Higher-Order logic.

33. A computer software product according to claim 32 wherein the computer readable instructions provide for controlling computer apparatus to develop the rule set by:

a) forming an alphabet having selector functions allowing properties of the training data set to be extracted, together with at least one of the following;

additional concepts, background knowledge constant values and logical AND and OR functions,

b) forming current rules from combinations of items in the alphabet such that type consistency and variable consistency is preserved,

c) evaluating the current rules for adequacy of classification of the training data set,

d) if no current rule adequately classifies the training data set, generating new rules by applying at least one genetic operator to the current rules, a genetic operator having one of the following functions;

i) combining two rules to form a new rule, ii) modifying a single rule by deleting one of its conditions or adding a new condition to it, or iii) changing one of a rule'"'"'s constant values for another of an appropriate type, and

e) designating the new rules as the current rules and iterating steps c) onwards until a current rule adequately classifies the training data set or a predetermined number of iterations is reached.

34. A computer software product according to claim 30 wherein data samples in the training data set have characters indicating whether or not they are associated with anomalies.

35. A computer software product according to claim 30 wherein the at least one anomaly characterisation rule has a form that an anomaly is detected or otherwise by application of such rule according to whether or not a condition set of at least one condition associated with that rule is fulfilled.

36. A computer software product according to claim 30 wherein the computer readable instructions provide for controlling computer apparatus to develop the at least one anomaly characterisation rule by refining a most general rule by at least one of:

a) addition of a new condition to the condition set; and

b) unification of different variables to become constants or structured terms.

37. A computer software product according to claim 36 wherein the computer readable instructions provide for controlling computer apparatus to at least partly evaluate a variable in the at least one anomaly characterisation rule which is defined as being in constant mode and is numerical by providing a range of values for the variable, estimating an accuracy for each value and selecting a value having optimum accuracy.

38. A computer software product according to claim 35 wherein the computer readable instructions provide for controlling computer apparatus to filter out at least one of rule duplicates, rule equivalents and unnecessary Iteq conditions.

39. A computer software product according to claim 35 wherein the computer readable instructions provide for controlling computer apparatus to stop construction of a rule in response to fulfilment of at least one of three stopping criteria, such criteria being:

a) the number of conditions in any rule in a beam of rules being processed is greater than or equal to a prearranged maximum rule length,

b) no negative examples are covered by a most significant rule, which is a rule that;

i) is present in a beam currently being or having been processed,

ii) is significant,

iii) has obtained a highest likelihood ratio statistic value found so far, and

iv) has obtained an accuracy value greater than a most general rule accuracy value, and

c) no refinements were produced which were eligible to enter the beam currently being processed in a most recent refinement processing step.