Detecting code injection attacks against databases

• US 7,444,331 B1
• Filed: 03/02/2005
• Issued: 10/28/2008
• Est. Priority Date: 03/02/2005
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Nachenberg, Carey S., Yung, Pak Wai
• Primary Examiner(s): Vital; Pierre M.
• Assistant Examiner(s): Nofal; Christopher P
• Application Number:
  US11/071,400
• Time in Patent Office: 1,336 Days
• Field of Search: 707/2, 707/3, 707/4, 707/9, 707/10, 707/100, 707/102, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A database server receives an incoming query and converts the query into its canonical form. The database server compares the canonical incoming query with stored template queries. If the incoming query matches one of the stored template queries, then the query is legitimate and the query is executed on the database. If the canonical incoming query does not match one of the stored template queries, then the database server determines whether the incoming query is malicious or anomalous. The database server identifies tokens in the incoming query that are not present in a similar template query. If the tokens have meaning in the language utilized to express the query, the database server declares the query malicious. Otherwise, the database server declares the query anomalous.

Claims

1. A computer-implemented method of determining whether an incoming database query represented in a query language is malicious, comprising:

representing the incoming database query as an ordered set of tokens;

representing a plurality of template queries as ordered sets of tokens;

comparing the ordered set of tokens representing the incoming database query with the ordered sets of tokens representing the template queries;

identifying a template query of the plurality of template queries that is similar to the incoming database query, the similar template query being represented as an ordered set of tokens;

identifying a portion of the ordered set of tokens representing the incoming database query not found in the ordered set of tokens representing the similar template query as an extra token;

determining if all of the tokens in the set of tokens representing the similar template query are in the same order as the set of tokens representing the incoming database query and if the extra token has meaning in the query language;

declaring the incoming query malicious if all of the tokens in the set of tokens representing the similar template query are in the same order as the set of tokens representing the incoming database query, if the set of tokens representing the incoming database query includes the extra token not found in the set of tokens representing the similar template query, and if the extra token has meaning in the query language;

declaring the incoming database query anomalous if the extra token does not have meaning in the query language; and

reporting the result of the declaration.

2. The method of claim 1, wherein identifying the portion of the incoming database query not found in the similar template query as the extra token comprises:

searching for each token of the similar template query in the incoming database query, in order; and

for adjacent tokens in the similar template query that are found in order in the incoming database query, identifying any portion of the incoming database query between the adjacent tokens as the extra token.

3. The method of claim 2, wherein a last token of the similar template query is found in the incoming database query, the method further comprising:

identifying any portion of the incoming database query occurring after the token matching the last token of the similar template query as the extra token.

4. The method of claim 1, wherein identifying the portion of the incoming database query not found in the similar template query as the extra token comprises:

identifying only a portion of the incoming database query occurring after a specified position in the incoming database query.

5. The method of claim 4, wherein the specified position is a first literal occurring in the incoming database query.

6. The method of claim 1, wherein identifying the template query of the plurality of template queries that is similar to the incoming database query comprises:

applying a similarity metric to the incoming database query and the plurality of template queries; and

identifying a set of template queries where the similarity metric produces a score above a threshold.

21. The method of claim 1, wherein representing the incoming database query as the ordered set of tokens comprises:

representing the incoming database query in a canonical form.

7. A computer system for determining whether an incoming database query is malicious, comprising:

a processor adapted to execute computer program modules;

a memory device coupled to the processor;

a representation module adapted to load into the memory device and cause the processor to represent the incoming database query as an ordered set of tokens and represent a plurality of template queries as ordered sets of tokens;

a comparing module adapted to load into the memory device and cause the processor to compare the ordered set of tokens representing the incoming database query with the ordered sets of tokens representing the template queries, to identify a template query of the plurality of template queries that is similar to the incoming database query, the similar template query being represented as an ordered set of tokens, to identify a portion of the ordered set of tokens representing the incoming database query not found in the ordered set of tokens representing the similar template query as an extra token and to determine if all of the tokens in the set of tokens representing the similar template query are in the same order as the set of tokens representing the incoming database query and if the extra token has meaning in the query language; and

a reporting module adapted to load into the memory device and cause the processor to declare the incoming query malicious if all of the tokens in the set of tokens representing the similar template query are in the same order as the set of tokens representing the incoming database query, if the set of tokens representing the incoming database query includes the extra token not found in the set of tokens representing the similar template query, and if the extra token has meaning in the query language, the reporting module further adapted to cause the processor to declare the incoming database query anomalous if the extra token does not have meaning in the query language, and the reporting module further adapted to cause the processor to report the result of the declaration.

8. The computer system of claim 7, wherein the query language is SQL.

9. The computer system of claim 7, wherein to identify the portion of the incoming database query not found in the similar template query as the extra token comprises to:

search for each token of the similar template query in the incoming database query, in order; and

for adjacent tokens in the similar template query that are found in order in the incoming database query, identify any portion of the incoming database query between the adjacent tokens as the extra token.

10. The computer system of claim 9, wherein a last token of the similar template query is found in the incoming database query, the reporting module is further adapted to cause the processor to:

identify any portion of the incoming database query occurring after the token matching the last token of the similar template query as the extra token.

11. The computer system of claim 7, wherein to identify the portion of the incoming database query not found in the similar template query as the extra token comprises to:

identify only a portion of the incoming database query occurring after a specified position in the incoming database query.

12. The computer system of claim 11, wherein the specified position is a first literal occurring in the incoming database query.

13. The computer system of claim 7, wherein to identify the template query of the plurality of template queries that is similar to the incoming database query comprises to:

apply a similarity metric to the incoming database query and the plurality of template queries; and

identify a set of template queries where the similarity metric produces a score above a threshold.

22. The computer system of claim 7, wherein the representation module is further adapted to cause the processor to represent the incoming database query in a canonical form.

14. A computer program product having a computer-readable storage medium having encoded therein computer program instructions for determining whether an incoming database query is malicious, comprising:

a representation module adapted to represent the incoming database query as an ordered set of tokens and represent a plurality of template queries as ordered sets of tokens;

a comparing module adapted to compare the ordered set of tokens representing the incoming database query with the ordered sets of tokens representing the template queries, to identify a template query of the plurality of template queries that is similar to the incoming database query, the similar template query being represented as an ordered set of tokens, to identify a portion of the ordered set of tokens representing the incoming database query not found in the ordered set of tokens representing the similar template query as an extra token, and to determine if all of the tokens in the set of tokens representing the similar template query are in the same order as the set of tokens representing the incoming database query and if the extra token has meaning in the query language; and

a reporting module adapted to declare the incoming query malicious if all of the tokens in the set of tokens representing the similar template query are in the same order as the set of tokens representing the incoming database query, if the set of tokens representing the incoming database query includes the extra token not found in the set of tokens representing the similar template query, and if the extra token has meaning in the query language, the reporting module further adapted to declare the incoming database query anomalous if the extra token does not have meaning in the query language, and the reporting module further adapted to report the result of the declaration.

15. The computer program product of claim 14, wherein the query language is SQL.

16. The computer program product of claim 14, wherein to identify the portion of the incoming database query not found in the similar template query as the extra token comprises to:

search for each token of the similar template query in the incoming database query, in order; and

for adjacent tokens in the similar template query that are found in order in the incoming database query, identify any portion of the incoming database query between the adjacent tokens as the extra token.

17. The computer program product of claim 16, wherein a last token of the similar template query is found in the incoming database query, the reporting module is further adapted to

identify any portion of the incoming database query occurring after the token matching the last token of the similar template query as the extra token.

18. The computer program product of claim 14, wherein to identify the portion of the incoming database query not found in the similar template query as the extra token comprises to:

identify only a portion of the incoming database query occurring after a specified position in the incoming database query.

19. The computer program product of claim 18, wherein the specified position is a first literal occurring in the incoming database query.

20. The computer program product of claim 14, wherein to identify the template query of the plurality of template queries that is similar to the incoming database query comprises to:

apply a similarity metric to the incoming database query and the plurality of template queries; and

identify a set of template queries where the similarity metric produces a score above a threshold.

23. The computer program product of claim 14, wherein the representation module is further adapted to represent the incoming database query in a canonical form.