Anomaly detection for database systems

• US 8,504,876 B2
• Filed: 04/30/2010
• Issued: 08/06/2013
• Est. Priority Date: 04/30/2010
• Status: Active Grant

• Current Assignee: Mitre Corporation
• Original Assignee: Mitre Corporation
• Inventors: Mork, Peter, Chapman, Adriane, Samuel, Ken, Vayndiner, Irina, Moore, David
• Primary Examiner(s): TRUONG, LOAN
• Application Number:
  US12/771,263
• Publication Number:
  US 20110271146A1
• Time in Patent Office: 1,194 Days
• Field of Search: 714/25, 714/37, 707/713
• US Class Current: 714/37
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures

Abstract

Methods, systems and computer program products for detecting anomalies for a database system are provided. A method may include extracting workload features from a query optimizer based on a query workload and generating feature models for the extracted workload features. The method may also include extracting instance features from the query optimizer based on a query instance. Instance feature values may be obtained. The method may further include applying a query instance to the workload feature models to produce a prediction value for each workload feature. Anomalies may be reported based on a comparison of each instance feature value with a corresponding prediction value. A system for detecting anomalies for a database system may include a query optimizer, a feature modeler and an anomaly detector.

Claims

1. A method for detecting anomalies for a database system, comprising:

extracting one or more workload features from a query optimizer based on a query workload of legitimate database queries, the workload features including numerical, categorical, Boolean and set-valued features appearing in the legitimate database queries;

generating a submodel for each of the one or more extracted workload features;

extracting values of the workload features from the query optimizer based on a database query instance; and

comparing a value of each workload feature of the database query instance to prediction values of the submodel to produce a decision being one of legitimate and suspicious for each workload feature and reporting an anomaly based on an overall decision that is based on decisions for all of the workload features before the database query instance is applied to the database system.

2. The method of claim 1, wherein the reporting includes determining a rejection count number based on a number of values that do not meet a threshold value for a corresponding prediction.

3. The method of claim 1, wherein the reporting further comprises classifying the database query instance as legitimate based on a number of correct predictions.

4. The method of claim 1, wherein generating the submodel includes generating a decision tree for at least one of the one or more extracted workload features.

5. The method of claim 1, wherein generating the submodel includes generating a regression tree for at least one of the one or more extracted workload features.

6. The method of claim 1, wherein the one or more extracted workload features includes two or more of numerical, categorical, Boolean and set-valued features.

7. The method of claim 1, wherein the query workload includes query logs of known legitimate database queries.

8. The method of claim 1, wherein the query workload includes query logs for performance testing.

9. The method of claim 1, wherein the one or more extracted workload features include at least one of an expected result size and query attribute.

10. The method of claim 1, wherein the one or more extracted workload features include at least one feature based on query complexity.

11. The method of claim 1, the reporting further comprising reporting an attack on the database system before the query instance is applied to the database system.

12. A system for detecting anomalies for a database system, comprising:

at least one processor configured to process;

a query optimizer configured to execute queries;

a feature modeler configured to;

extract one or more workload features from the query optimizer based on a query workload of legitimate database queries, the workload features including numerical, categorical, Boolean and set-valued features appearing in the legitimate database queries;

generate a submodel for each of the one or more extracted workload features; and

extract values of the workload features from the query optimizer based on a database query instance; and

an anomaly detector configured to;

compare a value of each workload feature of the database query instance to prediction values of the submodel to produce a decision being one of legitimate and suspicious for each workload feature and report an anomaly based on an overall decision that is based on decisions for all of the workload features before the database query instance is applied to the database system.

13. The system of claim 12, wherein the anomaly detector is further configured to determine a rejection count number based on a number of values that do not meet a threshold value for a corresponding prediction.

14. The system of claim 12, wherein the anomaly detector is further configured to classify the database query instance as legitimate based on a number of correct predictions.

15. The system of claim 12, wherein the feature modeler is further configured to generate a decision tree for at least one of the one or more extracted workload features.

16. The system of claim 12, wherein the feature modeler is further configured to generate a regression tree for at least one of the one or more extracted workload features.

17. The system of claim 12, the anomaly detector further configured to report an attack on the database system before the query instance is applied to the database system.

18. A non-transitory computer readable medium having control logic stored therein, the control logic enabling a processor to perform operations to detect anomalies for a database system, the operations comprising:

extracting one or more workload features from a query optimizer based on a query workload of legitimate database queries, the workload features including numerical, categorical, Boolean and set-valued features appearing in the legitimate database queries;

generating a submodel for each of the one or more extracted workload features;

extracting values of the workload features from the query optimizer based on a database query instance; and

comparing a value of each workload feature of the database query instance to prediction values of the submodel to produce a decision being one of legitimate and suspicious for each workload feature and reporting an anomaly based on an overall decision that is based on decisions for all of the workload features before the query instance is applied to the database system.

19. The non-transitory computer readable medium of claim 18, the operations further comprising:

determining a rejection count number based on a number of values that do not meet a threshold value for a corresponding prediction.

20. The non-transitory computer readable medium of claim 18, the operations further comprising:

reporting an attack on the database system before the query instance is applied to the database system.