Programmable hardware for deep packet filtering

• US 7,519,995 B2
• Filed: 04/19/2005
• Issued: 04/14/2009
• Est. Priority Date: 04/19/2004
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Mangione-Smith, William H., Cho, Young H.
• Primary Examiner(s): LAFORGIA, CHRISTIAN A
• Application Number:
  US11/587,292
• Publication Number:
  US 20080047008A1
• Time in Patent Office: 1,456 Days
• Field of Search: None
• US Class Current: 726/22
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

An improved deep packet filter system designed to optimize search of dynamic patterns for a high speed network traffic. The improved deep packet filter system is a hardware-based system with optimized logic area. One optimization technique is the sharing of common sub-logic in the hardware design to reduce the number of gates that are required. Another optimization technique is the use of a built-in memory to store portions of the pattern set, also resulting in a reduction of gates. The reduction of the logic area allows the deep packet filter system to be implemented onto a single field-programmable array chip.

Claims

1. A deep packet filter comprising:

prefix search logic configured to compare a first non-header portion of incoming data against a prefix pattern;

memory coupled to the prefix search logic, the memory storing a plurality of suffix patterns;

means for generating a suffix index based on a match of the first non-header portion of the incoming data to the prefix pattern; and

comparator logic configured to compare a second non-header portion of the incoming data against a suffix pattern selected from the plurality of suffix patterns,

wherein the suffix pattern is identified based on the generated suffix index, and

wherein the incoming data is allowed to pass or not based on the comparison of the second non-header portion.

2. The deep packet filter of claim 1, wherein the prefix search logic Concurrently compares the first non-header portion of the incoming data against a plurality of prefix patterns.

3. The deep packet filter of claim 2, wherein the prefix search logic concurrently compares a plurality of bytes of the first non-header portion of the incoming data against a plurality of bytes of each of the plurality of prefix patterns.

4. The deep packet filter of claim 3, wherein the prefix search logic concurrently compares a plurality of bytes of the first non-header portion of the incoming data against different byte alignments for each of the plurality of prefix patterns.

5. The deep packet filter of claim 1, wherein the prefix search logic includes a chain of decoders for detecting a particular substring of the prefix pattern.

6. The deep packet filter of claim 5, wherein the chain of decoders for detecting the particular substring are shared by a plurality of prefix search logic units configured to detect different prefix patterns that include the particular substring.

7. The deep packet filter of claim 1, wherein the prefix search logic, memory, means for generating the suffix index, and the comparator logic are implemented on a single field-programmable gate array.

8. The deep packet filter of claim 7, wherein the memory stores a list of sorted suffix patterns, wherein patterns in even entries of the list are stored from a first entry of the memory to a last entry, and patterns in odd entries of the list are stored from the last entry of the memory to the first entry.

9. The deep packet filter of claim 1, wherein the means for generating the suffix index includes means for generating each bit of the suffix index based on a logic equation derived from a binary tree of OR gates coupled to an output of the prefix search logic.

10. The deep packet filter of claim 1, wherein the prefix search logic indicates a byte alignment, and the comparator logic includes a shifter for shifting the second non-header portion of the incoming data according to the indicated byte alignment.

11. The deep packet filter of claim 1, wherein the first and second non-header portions of the incoming data are payload portions of the data.

12. The deep packet filter of claim 1, wherein the suffix index addresses a location of the memory storing the suffix pattern, and the comparator logic is configured to retrieve the stored suffix pattern from the addressed location to compare the second non-header portion of the incoming data against the retrieved suffix pattern.

13. A deep packet filtering method comprising:

partitioning a plurality of patterns into a prefix portion and a suffix portion;

storing the suffix portion of each of the plurality of patterns in a memory;

concurrently comparing at least a portion of a first non-header portion of incoming data against at least a portion of the prefix portion of each of the plurality of patterns;

generating a suffix index based on a match of the first non-header portion of the incoming data to a prefix portion of a particular pattern;

identifying a suffix portion of the particular pattern stored in the memory based on the suffix index;

comparing a second non-header portion of the incoming data against the identified suffix portion; and

forwarding the incoming data or not, based on the comparison of the second non-header portion to the identified suffix portion.

14. The method of claim 13, wherein the concurrently comparing includes concurrently comparing a plurality of bytes of the first non-header portion of the incoming data against different byte alignments of the prefix portion of each of the plurality of patterns.

15. The method of claim 13, wherein the comparing is achieved via a chain of decoders configured to detect a particular substring.

16. The method of claim 15, wherein the chain of decoders for detecting the particular substring are shared by a plurality of prefix search logic units configured to detect different prefix portions of the plurality of patterns that include the particular substring.

17. The method of claim 13, wherein the memory is a read-only memory built-into a field-programmable gate array.

18. The method of claim 13, wherein the memory stores a list of sorted suffix portions of the plurality of patterns, wherein suffix portions listed in even entries of the list are stored from a first entry of the memory to a last entry, and suffix portions listed in odd entries of the list are stored from the last entry of the memory to the first entry.

19. The method of claim 13, wherein the generating of the suffix index includes generating each bit of the suffix index based on a logic equation derived from a binary tree of OR gates coupled to an output of a prefix search logic concurrently comparing the at least a portion of the first non-header portion of incoming data against the at least a portion of the prefix portion of each of the plurality of patterns.

20. The method of claim 13 further comprising:

identifying a byte alignment associated with the match of the first non-header portion of the incoming data to the prefix portion of the particular pattern; and

shifting the second non-header portion of the incoming data according to the indicated byte alignment.

21. The method of claim 13, wherein the first and second non-header portions of the incoming data are payload portions of the data.