Method and apparatus for data packet pattern matching

• US 20040151382A1
• Filed: 02/04/2003
• Published: 08/05/2004
• Est. Priority Date: 02/04/2003
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: TippingPoint Technologies, Inc. (Trend Micro Inc.)
• Inventors: Aviles, Joaquin J., Stellenberg, Gerald S.
• Granted Patent: US 7,134,143 B2
• Time in Patent Office: Days
• US Class Current: 382/219
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A pattern matching engine supports high speed (up to at least 2.4. Gbits per second line rate speeds) parallel pattern matching operations in an unanchored fashion. The engine is preferably implemented as a hardware device. A shift register serially receives a string of data stream bytes which are partitioned into a plurality of multi-byte overlapping adjacent stream chunks. Library patterns of bytes to be searched for are similarly partitioned into multi-byte overlapping adjacent table chunks for storage in a look-up table. The plurality of multi-byte overlapping adjacent stream chunks are applied by the register in parallel to the look-up table, with a result being returned which is indicative of whether each stream chunk matches one of the look-up table stored table chunks. The results of the parallel look-up operation are then logically combined to make a match determination.

Claims

1. A pattern matching device implemented in hardware and operable to match multi-byte data stream patterns against multi-byte library patterns in an unanchored fashion.

2. The device of claim 1 wherein the pattern matching device operates to match at data stream line rates greater than or equal to one gigabit per second.

3. The device of claim 2 wherein the pattern matching device operates to match at data stream line rates greater than or equal to two gigabits per second.

4. The device of claim 3 wherein the pattern matching device operates to match at data stream line rates greater than or equal to 2.4 gigabits per second.

5. The device of claim 1 wherein the pattern matching device receives a data stream comprising data packet payloads and wherein the unanchored match is performed with respect to the data packet payloads.

6. The device of claim 1 wherein the pattern matching device receives a data stream comprising data packets having headers and payloads and wherein the unanchored match is performed with respect to both the data packet headers and payloads.

7. The device of claim 1 further including:

a shift register storing a string portion of a data stream and operable to partition the string portion into a plurality of overlapping adjacent stream byte chunks;

a look-up table storing overlapping adjacent table byte chunks of the library patterns, the look-up table receiving the stream byte chunks for the string portion in parallel for simultaneous look-up against the stored table byte chunks; and

a logic circuit operable to collect results of the parallel look-ups and process those results to make a match determination.

8. The device of claim 7 wherein the data stream comprises a multiplicity of data bytes, the shift register further operable to shift a block comprising plural data bytes into the register with each clock cycle.

9. The device of claim 8 wherein each block shift retains at least one byte in common between consecutive strings within the register.

10. The device of claim 7 wherein the look-up table comprises a plurality of look-up tables, each look-up table storing overlapping adjacent table byte chunks for different classes of library patterns to be found.

11. The device of claim 10 wherein the different classes of library patterns comprise different length patterns for each look-up table.

12. The device of claim 10 wherein the different classes of library patterns comprise different traffic category patterns for each look-up table.

13. The device of claim 12 further including a traffic processor operable to examine and categorize the data stream before pattern matching, the logic circuit further including a logic process that emphasizes those results collected from the look-up table whose traffic category patterns are pertinent to the data stream categorization in making the match determination.

14. The device of claim 10 wherein the stream byte chunks for the string portion are simultaneously applied in parallel to the plurality of look-up tables.

15. The device of claim 10 wherein the logic circuit comprises a separate logic process for processing the results collected from each look-up table.

16. The device of claim 7 wherein the shift register has N cells and the library patterns have P bytes, and wherein N=P.

17. The device of claim 7 wherein the shift register has N cells and the library patterns have P bytes, and wherein N<

P.

18. The device of claim 7 wherein the shift register has N cells and the library patterns have P bytes, and wherein N>

P.

19. The device of claim 7 further including a hash table that processes the stream byte chunks before application to the look-up table.

20. The device of claim 7 wherein the string portion is the stream pattern to be matched against the library patterns.

21. The device of claim 7 wherein the string portion is a portion of the stream pattern to be matched against the library patterns.

22. The device of claim 7 wherein the string portion includes the stream pattern to be matched against the library patterns.

23. The device of claim 7 wherein the data stream comprises a multiplicity of data bytes, the shift register further operable to shift a block comprising plural data bytes into the register with each clock cycle, the device further including an historical memory for storing look-up results collected from the look-up table in a previous clock cycle with respect to the stream byte chunks of a previous block of data bytes, the logic circuit operable to process collected results from a current clock cycle with the stored results from the previous clock cycle to make the match determination.

24. The device of claim 23 wherein the historical memory stores look-up results collected from the look-up table with respect to a plurality of previous clock cycles.

25. The device of claim 23 wherein the data stream comprises a plurality of distinct flows of interleaved data packets, the historical memory storing the look-up results collected from previous clock cycles with respect to each flow, and the logic circuit operable to process the stored results from the historic memory pertinent to the data bytes of the flow currently in the register.

26. The device of claim 7 further including a decoder operable to decode encoded portions of the data stream before pattern matching.

27. The device of claim 26 wherein the overlapping adjacent table byte chunks of the library patterns are stored in the look-up table in both encoded and decoded format, and match determinations are made with respect to both the encoded and decoded portions of the data stream.

28. The device of claim 7 further including a reassembly buffer operable to reassemble out of order data packets within the data stream before pattern matching.

29. The device of claim 1 wherein the pattern matching device receives a data stream comprising plural distinct flows of interleaved data packets and wherein the unanchored match is performed with respect to each flow of data packets.

30. A method for matching multi-byte data stream patterns against multi-byte library patterns, the multi-byte library patterns being partitioned into overlapping adjacent table byte chunks, comprising the steps of:

receiving a string portion of a data stream;

partitioning the string portion into a plurality of overlapping adjacent stream byte chunks;

determining whether each of the stream byte chunks matches an overlapping adjacent table byte chunk;

logically combining results of determining step to make a match determination.

31. The method of claim 30 wherein the data stream comprises a plurality of distinct flows of interleaved packets, and the step of logically combining includes the step of making the match determination with respect to each flow.

32. The method of claim 30 wherein the data stream comprises a plurality of distinct flows of interleaved packets, further including the step of determining to which flow a certain packet belongs, the step of logically combining including the step of considering results associated with the flow to which the certain packet belongs in making the match determination.

33. The method of claim 30 wherein the step of determining comprises the step of matching the plurality of overlapping adjacent stream byte chunks against the overlapping adjacent table byte chunks in parallel.

34. The method of claim 30 further including the step of storing the overlapping adjacent table byte chunks in a look-up table.

35. The method of claim 30 further including the step of storing the overlapping adjacent table byte chunks in a plurality of look-up tables, each look-up table storing overlapping adjacent table byte chunks for different classes of library patterns to be found.

36. The method of claim 35 wherein the different classes of library patterns comprise different length patterns for each look-up table.

37. The method of claim 35 wherein the different classes of library patterns comprise different traffic category patterns for each look-up table.

38. The method of claim 37 further including the step of:

categorizing the data stream before pattern matching;

wherein the step of logically combining includes the step of emphasizing those results collected from the look-up table whose traffic category patterns are pertinent to the data stream categorization in making the match determination.

39. The method of claim 35 wherein the stream byte chunks for the string portion are simultaneously applied in parallel to the plurality of look-up tables.

40. The method of claim 35 wherein the step of logically combining comprises the step of separately processing the results collected from each look-up table in making match determinations.

41. The method of claim 30 wherein the matching is performed in an unanchored fashion.

42. The method of claim 41 wherein the data stream comprises data packet payloads and wherein the unanchored match is performed with respect to the data packet payloads.

43. The method of claim 41 wherein the data stream comprises data packets having headers and payloads and wherein the unanchored match is performed with respect to both the data packet headers and payloads.

44. The method of claim 30 wherein the matching occurs at data stream line rates greater than or equal to one gigabit per second.

45. The method of claim 44 wherein the matching occurs at data stream line rates greater than or equal to two gigabits per second.

46. The method of claim 45 wherein the matching occurs at data stream line rates greater than or equal to 2.4 gigabits per second.

47. A pattern matcher, comprising:

a shift register connected to receive a data flow including multi-byte data stream patterns, the shift register partitioning a stored string portion of the received data flow into overlapping adjacent substrings;

a look-up table that is accessed by the shift register to search for each overlapping adjacent substring simultaneously in parallel, the look-up table generating a return for each search indicative of whether the overlapping adjacent substring is present; and

an accumulator that collects the returns from the look-up and determines whether the multi-byte data stream pattern matches a multi-byte library pattern.

48. The pattern matcher of claim 47 wherein the data stream comprises a plurality of distinct flows of interleaved packets, and the accumulator operates to make the match determination with respect to each flow.

49. The pattern matcher of claim 47 wherein the data stream comprises a plurality of distinct flows of interleaved packets, each packet having a state which associates the packet to a certain one of the distinct flows, the pattern matcher determining packet state and the accumulator collecting the returns associated with the certain flow indicated by determined state to which the packet belongs in making the match determination.

50. The pattern matcher of claim 47 wherein the matching of multi-byte data stream patterns against multi-byte library patterns is performed in an unanchored fashion with respect to the data stream.

51. The pattern matcher of claim 50 wherein the matching of multi-byte data stream patterns against multi-byte library patterns is performed at a data stream line rate in excess of one gigabits per second.

52. The pattern matcher of claim 50 wherein the matching of multi-byte data stream patterns against multi-byte library patterns is performed at a data stream line rate in excess of two gigabits per second.

53. The pattern matcher of claim 47 wherein the data stream comprises a multiplicity of data bytes, the shift register further operable to shift a block comprising plural data bytes into the register with each clock cycle.

54. The pattern matcher of claim 47 wherein each multi-byte library pattern is partitioned into overlapping adjacent table byte chunks which are stored in the look-up table, the look-up table generated return indicating that the overlapping adjacent substring is present when it matches one of the overlapping adjacent table byte chunks.

55. The pattern matcher of claim 54 wherein the look-up table comprises a plurality of look-up tables, each look-up table storing overlapping adjacent table byte chunks for different classes of library patterns.

56. The pattern matcher of claim 55 wherein the different classes of library patterns comprise different length patterns for each look-up table.

57. The pattern matcher of claim 55 wherein the different classes of library patterns comprise different traffic characterization patterns for each look-up table.

58. The pattern matcher of claim 57 further including a data stream processor operable to characterize the data stream before pattern matching, the accumulator further including a logic process that emphasizes those returns collected from the look-up table whose traffic characterization patterns are pertinent to the data stream characterization in making the match determination.

59. The pattern matcher of claim 55 wherein the accumulator comprises separate logic processes for combining the returns collected from different look-up tables.

60. The pattern matcher of claim 47 further including a hash table that converts a bit address of each stream byte chunk to a reduced bit address before application to the look-up table.

61. The pattern matcher of claim 47 further including an historical memory for storing look-up returns collected from the look-up table in previous clock cycle(s), the accumulator including logic processes for combining collected returns from a current clock cycle with the stored returns from previous clock cycle(s) to make the match determination.

62. The pattern matcher of claim 47 further including a decoder operable to decode encoded portions of the data stream before pattern matching.

63. The pattern matcher of claim 47 further including a reassembly buffer operable to reassemble out of order data packets within the data stream before pattern matching.