Matching with a large vulnerability signature ruleset for high performance network defense

• US 8,522,348 B2
• Filed: 07/29/2010
• Issued: 08/27/2013
• Est. Priority Date: 07/29/2009
• Status: Expired due to Fees

• Current Assignee: Northwestern University
• Original Assignee: Northwestern University
• Inventors: Chen, Yan, Li, Zhichun, Xia, Gao, Liu, Bin
• Primary Examiner(s): GEORGANDELLIS, ANDREW C
• Application Number:
  US12/846,541
• Publication Number:
  US 20110030057A1
• Time in Patent Office: 1,125 Days
• Field of Search: 726/23
• US Class Current: 726/23
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1433 Vulnerability analysis
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Systems, methods, and apparatus are provided for vulnerability signature based Network Intrusion Detection and/or Prevention which achieves high throughput comparable to that of the state-of-the-art regex-based systems while offering improved accuracy. A candidate selection algorithm efficiently matches thousands of vulnerability signatures simultaneously using a small amount of memory. A parsing transition state machine achieves fast protocol parsing. Certain examples provide a computer-implemented method for network intrusion detection. The method includes capturing a data message and invoking a protocol parser to parse the data message. The method also includes matching the parsed data message against a plurality of vulnerability signatures in parallel using a candidate selection algorithm and detecting an unwanted network intrusion based on an outcome of the matching.

Claims

1. A computer-implemented method for network intrusion detection, said method comprising:

capturing a data message;

invoking a protocol parser to extract content of a protocol field from the data message;

constructing a signature table, where each row of the signature table represents a vulnerability signature, each column of the signature table represents a protocol field to be matched, and each cell of the signature table represents how the corresponding field is matched on the corresponding vulnerability signature;

for each column in the signature table, examining the contents of the protocol field against corresponding entries for all vulnerability signatures in the signature table and labelling each vulnerability signature that matches the contents of the protocol field as a candidate signature;

iteratively combining candidate signatures from different columns to produce a final matching outcome; and

detecting an unwanted network intrusion based on the final matching outcome.

2. The method of claim 1, further comprising classifying the data message according to an application protocol.

3. The method of claim 2, further comprising generating the protocol parser according to the application protocol.

4. The method of claim 1, further comprising routing the data message based on the outcome of the matching.

5. The method of claim 1, wherein the protocol parser conducts multiple layer parsing using a multiple layer parsing state machine.

6. The method of claim 1, wherein the protocol parser conducts data flow analysis to merge consecutive fields that are not Type-I or Type-II fields.

7. The method of claim 1, wherein iteratively combining further comprises determining a match order to order more selective columns before less selective columns in determining a final matching outcome.

8. A vulnerability-based network intrusion detection/prevention system comprising:

a processor configured to implement;

a protocol parser including a parsing state machine to extract content of a protocol field from a protocol data unit according to an associated application protocol specification; and

a matching engine configured to;

construct a signature table, where each row of the signature table represents a vulnerability signature, each column of the signature table represents a protocol field to be matched, and each cell of the signature table represents how the corresponding field is matched on the corresponding vulnerability signature, the matching engine configured to, for each column in the signature table, examine the contents of the protocol field against corresponding entries for all vulnerability signatures in the signature table and label each vulnerability signature that matches the contents of the protocol field as a candidate signature;

iteratively combine candidate signatures from different columns to produce a final matching outcome; and

detect an unwanted network intrusion based on the final matching outcome.

9. The system of claim 8, further comprising an automated parser generator to generate code for the protocol parser according to the associated application protocol specification.

10. The system of claim 8, wherein the protocol parser comprises a multiple layer parsing state machine to perform multiple layer parsing of a protocol data unit.

11. The system of claim 8, wherein the protocol parser conducts data flow analysis to merge consecutive fields of the protocol data unit that are not Type-I or Type-II fields.

12. The system of claim 8, wherein iteratively combining further comprises determining a match order to order more selective columns before less selective columns in determining a final matching outcome.

13. The system of claim 8, further comprising a rule compiler to compile rules from a vulnerability ruleset for use by the matching engine.

14. The system of claim 8, wherein the protocol parser outputs a plurality of protocol fields from the protocol data unit based on the associated application protocol specification and the matching engine performs an incremental matching process when a parsed field is received from the protocol parser in a pipelined fashion.

15. A non-transitory computer-readable storage medium having a set of instructions stored thereon which, when executed, instruct a processor to implement a vulnerability-based network intrusion detection system comprising:

a protocol parser including a parsing state machine to extract content of a protocol field from a protocol data unit according to an associated application protocol specification; and

a matching engine configured to;

construct a signature table, where each row of the signature table represents a vulnerability signature, each column of the signature table represents a protocol field to be matched, and each cell of the signature table represents how the corresponding field is matched on the corresponding vulnerability signature, the matching engine configured to, for each column in the signature table, examine the contents of the protocol field against corresponding entries for all vulnerability signatures in the signature table and label each vulnerability signature that matches the contents of the protocol field as a candidate signature;

iteratively combine candidate signatures from different columns to produce a final matching outcome; and

detect an unwanted network intrusion based on the final matching outcome.

16. The computer-readable storage medium of claim 15, further comprising an automated parser generator to generate code for the protocol parser according to the associated application protocol specification.

17. The computer-readable storage medium of claim 15, wherein the protocol parser comprises a multiple layer parsing state machine to perform multiple layer parsing of a protocol data unit.

18. The computer-readable storage medium of claim 15, wherein iteratively combining further comprises determining a match order to order more selective columns before less selective columns in determining a final matching outcome.

19. The computer-readable storage medium of claim 15, further comprising a rule compiler to compile rules from a vulnerability ruleset for use by the matching engine.

20. The computer-readable storage medium of claim 15, wherein the protocol parser outputs a plurality of protocol fields from the protocol data unit based on the associated application protocol specification and the matching engine performs an incremental matching process when a parsed field is received from the protocol parser in a pipelined fashion.