High-Performance Context-Free Parser for Polymorphic Malware Detection

• US 20090070459A1
• Filed: 04/18/2006
• Published: 03/12/2009
• Est. Priority Date: 04/18/2005
• Status: Abandoned Application

• Current Assignee: William H. Mangione-Smith, Young H. Cho
• Original Assignee: William H. Mangione-Smith, Young H. Cho
• Inventors: Cho, Young H., Mangione-Smith, William H.
• Application Number:
  US11/918,592
• Publication Number:
  US 20090070459A1
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

The invention provides a method and apparatus for advanced network intrusion detection. The system uses deep packet inspection that can recognize languages described by context-free grammars. The system combines deep packet inspection with one or more grammar parsers (409A-409M). The invention can detect token streams (408) even when polymorphic. The system looks for tokens at multiple byte alignments and is capable of detecting multiple suspicious token streams (408). The invention is capable of detecting languages expressed in LL(I) or LR(I) grammar. The result is a system that can detect attacking code wherever it is located in the data stream (408).

Claims

1. An apparatus for inspecting a packet stream comprising:

an inspection block for inspecting the packet stream;

a tokenizer coupled to the inspection block for converting the output of the inspection block to a stream of tokens;

a parser for receiving the token stream and for verifying grammatical structure of the token stream.

2. The apparatus of claim 1 wherein the inspection block includes a header inspector and a payload inspector.

3. The apparatus of claim 2 wherein the inspection block outputs a pattern index.

4. The apparatus of claim 3 further including a plurality of parsers coupled to the tokenizer.

5. The apparatus of claim 4 wherein the packet stream is examined at each byte alignment.

6. The apparatus of claim 3 wherein the tokenizer comprises:

an adder coupled to the pattern index stream;

a FIFO control block coupled to the adder;

a FIFO coupled to the FIFO control block.

7. The apparatus of claim 6 further including a plurality of FIFO controllers and a plurality of FIFOs.

8. The apparatus of claim 6 wherein the FIFO controller adds the length of a newly detected token to a detection time to determine a next expected valid token.

9. The apparatus of claim 1 wherein the parser is an LL parser.

10. The apparatus of claim 1 wherein the parser is an LR parser.

11. The apparatus of claim 1 wherein the parser is a combined LL and LR parser.

12. The apparatus of claim 1 wherein the parser includes a stack.

13. The apparatus of claim 12 wherein the stack is a multiple thread stack.

14. The apparatus of claim 12 wherein the stack is two thread stack.