Automated anomaly detection

• US 7,627,543 B2
• Filed: 11/22/2004
• Issued: 12/01/2009
• Est. Priority Date: 11/27/2003
• Status: Active Grant

• Current Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Original Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Inventors: Thie, Claire Julia, Lock, Zoe Paula, Hood, Alan Barry, Peeling, Emma Cecilia, Kilvington, Simon, Brown, Neil Christopher Charles, Zakiuddin, Mohammed Irfan, Hatch, Richard
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): FERNANDEZ RIVAS, OMAR F
• Application Number:
  US10/580,767
• Publication Number:
  US 20070112824A1
• Time in Patent Office: 1,835 Days
• Field of Search: 706/20, 706/21, 706 45- 47, 706/52, 706/60, 705 2- 4, 705/18, 705/35, 705/44, 705/50, 705/51, 705/67, 705/72, 705/75, 726 22- 33
• US Class Current: 706/47
• 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 characterization 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. An automated method of detection of software vulnerabilities by applying a rule set to test for vulnerabilities in computer software, the rule set comprising at least one vulnerability characterisation rule, the method incorporating the steps of:

a) providing a training data set of computer software incorporating positive and negative vulnerability examples and expressed as programs flagged to indicate either presence or absence of vulnerability, the programs comprising instructions each incorporating an identifier to indicate its associated program, the instruction'"'"'s address, an instruction operator and a list of instruction operands,

b) defining a rule generalisation, the rule generalisation being processable to transform it into the at least one vulnerability characterisation rule, and

c) using computer apparatus to execute the steps of;

i) receiving the training data set and the rule generalisation,

ii) processing the rule generalisation to transform it into a more specific rule generalisation by employing logic of at least First-Order and adding to the rule generalisation at least one of a condition, a variable, a constant, a unification of variables and a function based on the training data set and background knowledge relating to attributes of the training data set and consisting of at least one of concepts, facts of interest and functions for calculating values of interest from items of data,

iii) evaluating the more specific rule generalisation by applying it to the training data set to identify vulnerabilities, and

iv) incorporating the more specific rule generalisation in the rule set if it classifies vulnerabilities in the training data set adequately in terms of covering at least some of the positive vulnerability examples,

v) applying the rule set to a test program for vulnerability detection therein, and

vi) providing an alert or a report to a user regarding vulnerability detection in the test program resulting from operation of the method in order to enable corrective action to be taken.

2. An automated method of detection of software vulnerabilities according to claim 1 wherein the background knowledge includes at least one of the following tests:

a) a copying loop test,

b) a length loop test,

c) a test for one block following another,

d) a test for making a call to a string length function at a specified index,

e) a test for tests that precede conditional jumps in an instruction list,

f) a test for whether or not a given list is empty,

g) a test for whether or not a given list has a single jump test (conditional), and if it is, to return a tested register, and

h) a test for whether or not a given list modifies a given register.

3. An automated method of detection of software vulnerabilities according to claim 1 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop preceded by a call to a string length function, with no conditional jumps therebetween.

4. An automated method of detection of software vulnerabilities according to claim 1 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop defined as a portion of code that copies to a register from a source pointer, changes the source pointer, copies from the register into a destination pointer, changes that destination pointer, and has a control flow path from the code portion'"'"'s end back to the code portion'"'"'s beginning thus forming a loop.

5. An automated method of detection of software vulnerabilities according to claim 1 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop with a test for zero, and one other test, but a register referenced by the other test is not used during the loop.

6. A system for computer-implemented detection software vulnerabilities by applying a rule set to test for vulnerabilities in computer software, the rule set comprising at least one vulnerability characterisation rule, the system incorporating computer apparatus incorporating a computer program stored in a hardware recording medium and being programmed by such computer program to carry out the steps of:

a) receiving a training data set of computer software incorporating positive and negative vulnerability examples and expressed as programs flagged to indicate either presence or absence of vulnerability, the programs comprising instructions each incorporating an identifier to indicate its associated program, the instruction'"'"'s address, an instruction operator and a list of instruction operands,

b) receiving a rule generalisation which is processable to transform it into the at least one vulnerability characterisation rule, and

c) processing the rule generalisation to transform it into a more specific rule generalisation by employing logic of at least First-Order and adding to the rule generalisation at least one of a condition, a variable, a constant, a unification of variables and a function based on the training data set and background knowledge relating to attributes of the training data set and consisting of at least one of concepts, facts of interest and functions for calculating values of interest from items of data,

d) evaluating the more specific rule generalisation by applying it to the training data set to identify vulnerabilities, and

e) incorporating the more specific rule generalisation in the rule set if it classifies vulnerabilities in the training data set adequately in terms of covering at least some of the positive vulnerability examples,

f) applying the rule set to a test program for vulnerability detection therein, and

g) providing an alert or a report to a user regarding vulnerability detection in the test program resulting from operation of the method in order to enable corrective action to be taken.

7. A system for detection of software vulnerabilities according to claim 6 wherein the background knowledge includes at least one of the following tests:

a) a copying loop test,

b) a length loop test,

c) a test for one block following another,

d) a test for making a call to a string length function at a specified index,

e) a test for tests that precede conditional jumps in an instruction list,

f) a test for whether or not a given list is empty,

g) a test for whether or not a given list has a single jump test (conditional), and if it is, to return a tested register, and

h) a test for whether or not a given list modifies a given register.

8. A system for detection of software vulnerabilities according to claim 6 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop preceded by a call to a string length function, with no conditional jumps therebetween.

9. A system for detection of software vulnerabilities according to claim 6 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop defined as a portion of code that copies to a register from a source pointer, changes the source pointer, copies from the register into a destination pointer, changes that destination pointer, and has a control flow path from the code portion'"'"'s end back to the code portion'"'"'s beginning thus forming a loop.

10. A system for detection of software vulnerabilities according to claim 6 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop with a test for zero, and one other test, but a register referenced by the other test is not used during the loop.

11. A computer readable hardware medium which embodies computer readable instructions for controlling operation of computer apparatus to implement detection of software vulnerabilities by applying a rule set to test for vulnerabilities in computer software, the rule set comprising at least one vulnerability characterisation rule, wherein the instructions provide for control of the computer apparatus to carry out the steps of:

a) receiving a training data set of computer software incorporating positive and negative vulnerability examples and expressed as programs flagged to indicate either presence or absence of vulnerability, the programs comprising instructions each incorporating an identifier to indicate its associated program, the instruction'"'"'s address, an instruction operator and a list of instruction operands,

b) receiving a rule generalisation which is processable to transform it into the at least one vulnerability characterisation rule, and

c) processing the rule generalisation to transform it into a more specific rule generalisation by employing logic of at least First-Order and adding to the rule generalisation at least one of a condition, a variable, a constant, a unification of variables and a function based on the training data set and background knowledge relating to attributes of the training data set and consisting of at least one of concepts, facts of interest and functions for calculating values of interest from items of data,

d) evaluating the more specific rule generalisation by applying it to the training data set to identify vulnerabilities, and

e) incorporating the more specific rule generalisation in the rule set if it classifies vulnerabilities in the training data set adequately in terms of covering at least some of the positive vulnerability examples,

f) applying the rule set to a test program for vulnerability detection therein, and

g) providing an alert or a report to a user regarding vulnerability detection in the test program resulting from operation of the method in order to enable corrective action to be taken.

12. A computer readable hardware medium according to claim 11 wherein the background knowledge includes at least one of the following tests:

a) a copying loop test,

b) a length loop test,

c) a test for one block following another,

d) a test for making a call to a string length function at a specified index,

e) a test for tests that precede conditional jumps in an instruction list,

f) a test for whether or not a given list is empty,

g) a test for whether or not a given list has a single jump test (conditional), and if it is, to return a tested register, and

h) a test for whether or not a given list modifies a given register.

13. A computer readable hardware medium according to claim 11 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop preceded by a call to a string length function, with no conditional jumps therebetween.

14. A computer readable hardware medium according to claim 11 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop defined as a portion of code that copies to a register from a source pointer, changes the source pointer, copies from the register into a destination pointer, changes that destination pointer, and has a control flow path from the code portion'"'"'s end back to the code portion'"'"'s beginning thus forming a loop.

15. A computer readable hardware medium according to claim 11 wherein the rule set incorporates a rule which classifies a program as vulnerable if there is a copying loop with a test for zero, and one other test, but a register referenced by the other test is not used during the loop.