Methods and systems for full pattern matching in hardware

• US 8,458,796 B2
• Filed: 03/08/2011
• Issued: 06/04/2013
• Est. Priority Date: 03/08/2011
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Stites, Ronald S., Botkin, Craig D., Campbell, Brian K.
• Primary Examiner(s): Flynn, Nathan
• Assistant Examiner(s): Almamun, Abdullah
• Application Number:
  US13/043,287
• Publication Number:
  US 20120233693A1
• Time in Patent Office: 819 Days
• Field of Search: 726 13- 25, 713/164, 713/188, 709/231, 707/706, 707/776, 707/999, 706/46, 711/100, 711/103, 711/108
• US Class Current: 726/23
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Methods and systems are provided for hardware-based pattern matching. In an embodiment, an intrusion-prevention system (IPS) identifies a full match between a subject data word comprising subject-data blocks and a signature data pattern comprising signature-data blocks. The IPS receives the subject data word via a network interface, and thereafter makes a partial-match determination that two or more but less than all of the subject-data blocks respectively match the same number of the signature-data blocks stored in partial-match hardware with respect to both value and position. Thereafter, the IPS makes a full-match determination that all of the subject-data blocks respectively match all of the signature-data blocks stored in the IPS'"'"'s full-match hardware with respect to both value and position. The IPS then stores an indicator that the full-match determination has been made, and may carry out one or more additional intrusion-prevention responses as well.

Claims

1. A method of examining a subject data word, the subject data word comprising a plurality of subject-data blocks, and identifying a full match between the subject data word and a signature data pattern, the signature data pattern comprising a plurality of signature-data blocks, wherein each of the subject-data blocks and each of the signature-data blocks has (i) a respective value and (ii) a respective position, the method carried out by an intrusion-prevention system (IPS) comprising at least one processor, at least one network interface, partial-match hardware having at least part of the signature data pattern stored therein, and full-match hardware having the signature data pattern stored therein, the method comprising:

the IPS receiving the subject data word via the at least one network interface;

the IPS making a partial-match determination comprising a determination that a partial-match number of the subject-data blocks respectively match the same partial-match number of the signature-data blocks stored in the partial-match hardware with respect to both value and position, wherein the partial-match number is (i) greater than or equal to two and (ii) less than a total number of the subject-data blocks;

subsequent to making the partial-match determination, the IPS making a full-match determination comprising a determination that all of the subject-data blocks respectively match all of the signature-data blocks stored in the full-match hardware with respect to both value and position; and

the IPS storing a full-match indicator, the full-match indicator indicating that the full-match determination has been made.

2. The method of claim 1, wherein each of the subject-data blocks and each of the signature-data blocks is at least one of (i) a fixed number of one or more bits and (ii) a fixed number of one or more bytes.

3. The method of claim 1, wherein receiving the subject data word comprises receiving the subject data word from a public data network.

4. The method of claim 1, wherein the IPS further comprises pre-processing hardware having at least one pre-processing-signature-hash result flagged therein, the method further comprising, prior to making the partial-match determination, the IPS making a pre-processing determination that a pre-processing number of pre-processing-subject-hash results are flagged as being pre-processing-signature-hash results in the pre-processing hardware.

5. The method of claim 4, wherein the pre-processing number is 2 or 4.

6. The method of claim 4, wherein the pre-processing hardware comprises Block random access memory (RAM).

7. The method of claim 4, wherein each pre-processing-signature-hash result and each pre-processing-subject-hash result corresponds to a respective pre-processing address in the pre-processing hardware.

8. The method of claim 7, wherein a pre-processing-signature-hash result being flagged comprises a trigger indicator being set at the corresponding pre-processing address.

9. The method of claim 1, wherein the respective positions of the subject-data blocks matched in the partial-match determination are adjacent.

10. The method of claim 9, wherein the partial-match number is 2.

11. The method of claim 9, wherein the subject-data blocks matched in the partial-match determination comprise a subject-data block having a position that is either (i) at the beginning of the subject-data word or (ii) at the end of the subject-data word.

12. The method of claim 9, wherein the subject-data blocks matched in the partial-match determination comprise a subject-data block having a position that is neither (i) at the beginning of the subject-data word or (ii) at the end of the subject-data word.

13. The method of claim 11, wherein the partial-match number is 2.

14. The method of claim 1, wherein the partial-match number is 2.

15. The method of claim 1, wherein the partial-match hardware comprises static random access memory (SRAM).

16. The method of claim 1, wherein the signature-data blocks stored in the partial-match hardware are stored in a memory block that begins at a partial-match address in the partial-match hardware.

17. The method of claim 16, wherein making the partial-match determination further comprises using at least part of the subject data word to determine a partial-match-subject-hash result corresponding to the partial-match address.

18. The method of claim 16, wherein making the partial-match determination further comprises identifying the partial-match address based at least in part on at least one pre-processing-subject-hash result.

19. The method of claim 1, wherein the full-match hardware comprises dynamic random access memory (DRAM).

20. The method of claim 1, wherein the signature-data blocks stored in the full-match hardware are stored in a memory block that begins at a full-match address in the full-match hardware.

21. The method of claim 20, wherein making the full-match determination further comprises using at least part of the subject data word to determine a full-match-subject-hash result corresponding to the full-match address.

22. The method of claim 20, wherein making the full-match determination further comprises identifying the full-match address based at least in part on at least one pre-processing-subject-hash result.

23. The method of claim 1, wherein the subject data word is one of a plurality of subject data words that the IPS examines in accordance with a given clock cycle for the presence of a matching word in a trigger set that includes the signature data word, and wherein a total number of subject data words in the plurality of subject data words is equal to a product of (i) a number of subject-data blocks received in accordance with the given clock cycle and (ii) a number of different lengths of subject data words that the IPS examines in accordance with the given clock cycle.

24. The method of claim 23, wherein the total number of subject data words in the plurality of subject data words is 136, wherein the number of subject-data blocks received in accordance with the given clock cycle is 8, and wherein the number of different lengths of subject data words that the IPS examines in accordance with the given clock cycle is 17.

25. The method of claim 24, wherein, in accordance with the given clock cycle, the IPS examines data words ranging in length in integer increments from 4 subject-data blocks to 20 subject-data blocks, inclusive.

26. The method of claim 23 wherein the total number of subject data words in the plurality of subject data words is 72, wherein the number of subject-data blocks received in accordance with the given clock cycle is 8, and wherein the number of different lengths of subject data words that the IPS examines in accordance with the given clock cycle is 9.

27. The method of claim 26, wherein in accordance with the given clock cycle, the IPS examines data words ranging in length in integer increments from 4 subject-data blocks to 12 subject-data blocks, inclusive.

28. The method of claim 23, wherein the subject data word comprises (i) at least one subject-data block received in accordance with the given clock cycle and (ii) at least one subject-data block received during a clock cycle occurring prior to the given clock cycle.

29. The method of claim 1, further comprising, subsequent to making the full-match determination, the IPS carrying out at least one of the following:

(i) quarantining the subject data word, (ii) quarantining a collection of data comprising the subject data word, (iii) blacklisting a source of the subject data word, (iv) sending an alert to a source of the subject data word, (v) sending an alert to an intended recipient of the subject data word, and (vi) generating a data-examination report.

30. An intrusion-prevention system (IPS) for examining a subject data word, the subject data word comprising a plurality of subject-data blocks, and for identifying a full match between the subject data word and a signature data pattern, the signature data pattern comprising a plurality of signature-data blocks, wherein each of the subject-data blocks and each of the signature-data blocks has (i) a respective value and (ii) a respective position, the IPS comprising:

at least one network interface;

at least one processor;

partial-match hardware having at least part of the signature data pattern stored therein;

full-match hardware having the signature data pattern stored therein; and

data storage containing instructions executable by the at least one processor for causing the IPS to carry out a set of functions, the set of functions comprising;

receiving the subject data word via the at least one network interface;

making a partial-match determination comprising a determination that a partial-match number of the subject-data blocks respectively match the same partial-match number of the signature-data blocks stored in the partial-match hardware with respect to both value and position, wherein the partial-match number is (i) greater than or equal to two and (ii) less than a total number of the subject-data blocks;

subsequent to making the partial-match determination, making a full-match determination comprising a determination that all of the subject-data blocks respectively match all of the signature-data blocks stored in the full-match hardware with respect to both value and position; and

storing a full-match indicator, the full-match indicator indicating that the full-match determination has been made.

31. The IPS of claim 30, wherein the partial-match hardware comprises static random access memory (SRAM).

32. The IPS of claim 30, wherein the full-match hardware comprises dynamic random access memory (DRAM).

33. The IPS of claim 30, wherein an operating speed that is characteristic of the partial-match hardware is greater than an operating speed that is characteristic of the full-match hardware.

34. The IPS of claim 30, further comprising pre-processing hardware having at least one pre-processing-signature-hash result flagged therein, wherein the set of functions further comprises, prior to making the partial-match determination, making a pre-processing determination comprising a determination that a pre-processing number of pre-processing-subject-hash results are flagged as being pre-processing-signature-hash results in the pre-processing hardware.

35. The IPS of claim 34, wherein the pre-processing hardware comprises Block random access memory (Block RAM).

36. The IPS of claim 34, wherein an operating speed that is characteristic of the pre-processing hardware is greater than an operating speed that is characteristic of the partial-match hardware, and further wherein the operating speed that is characteristic of the partial-match hardware is greater than an operating speed that is characteristic of the full-match hardware.

37. The IPS of claim 30, embodied in a single network device.

38. The IPS of claim 30, distributed across multiple network devices.

39. A method of examining a subject data word, the subject data word comprising a plurality of subject-data blocks, and identifying a full match between the subject data word and a signature data pattern, the signature data pattern comprising a plurality of signature-data blocks, wherein each of the subject-data blocks and each of the signature-data blocks has (i) a respective value and (ii) a respective position, the method carried out by an intrusion prevention system (IPS) comprising at least one processor, at least one network interface, partial-match hardware having at least part of the signature data pattern stored therein, and full-match hardware having the signature data pattern stored therein, the method comprising:

the IPS receiving the subject data word via the at least one network interface;

the IPS making a partial-match determination comprising;

an identification of a partial-match address based at least in part on at least part of the subject data word, and

a determination that at least one of the following is stored in the partial-match hardware in association with the partial-match address;

(i) a set overflow indicator and (ii) a partial-match number of the signature-data blocks that respectively match the same partial-match number of the subject-data blocks with respect to both value and position, wherein the partial-match number is (i) greater than or equal to two and (ii) less than a total number of the subject-data blocks;

subsequent to making the partial-match determination, the IPS making a full-match determination comprising;

an identification of a full-match address based at least in part on at least part of the subject data word, and

a determination that the signature data pattern is stored in the full-match hardware in association with the full-match address; and

the IPS storing a full-match indicator, the full-match indicator indicating that the full-match determination has been made.

40. The method of claim 39, wherein the determination that at least one of (i) a set overflow indicator and (ii) the partial-match number of the signature data blocks is stored in the partial-match hardware in association with the partial-match address comprises a determination that at least one of (i) a set overflow indicator and (ii) the partial-match number of the signature data blocks is stored in association with a memory block that begins at the partial-match address.

41. The method of claim 40, wherein there is not a set overflow indicator stored in the partial-match hardware in the memory block that begins at the partial-match address, and wherein the partial-match determination comprises a determination that stored in the partial-match hardware in association with the partial-match address is the partial-match number of the signature-data blocks that respectively match the same partial-match number of the subject-data blocks with respect to both value and position.

42. The method of claim 40, wherein there is a set overflow indicator stored in the partial-match hardware in the memory block that begins at the partial-match address, and wherein the partial-match determination comprises a determination that that indicator is stored in the partial-match hardware in the memory block that begins at the partial-match address.

43. The method of claim 40, wherein at least the partial-match number of signature-data blocks from each of at least one additional signature data pattern other than the signature data pattern are stored in the memory block that begins at the partial-match address.

44. The method of claim 40, wherein there is a set overflow indicator stored in the partial-match hardware in the memory block that begins at the partial-match address, and wherein at least the partial-match number of signature-data blocks from each of a given positive integer number of one or more additional signature data patterns other than the signature data pattern are also stored in the memory block that begins at the partial-match address, and wherein the memory block that begins at the partial-match address does not have the signature data pattern stored therein.

45. The method of claim 44, wherein the given positive integer number is four.

46. The method of claim 39, wherein the signature data pattern is stored in a memory block that begins at the full-match address.

47. The method of claim 39, wherein the signature data pattern is stored in a memory block that begins at a full-match-overflow address that is stored in a memory block that begins at the full-match address.

48. The method of claim 47, wherein the full-match determination further comprises a determination that the full-match-overflow address is stored in the memory block that begins at the full-match address.

49. The method of claim 47, wherein at least one additional signature data pattern other than the signature data pattern is also stored in the memory block that begins at the full-match address.

50. The method of claim 49, wherein the at least one additional signature data pattern comprises at least three additional signature data patterns.

51. The method of claim 39, wherein the full-match determination further comprises a determination that a length indicator that is stored in the full-match hardware in association with the signature data pattern is equal to a length of the subject data word, the length indicator reflecting a length of the signature data pattern.

52. An intrusion-prevention system (IPS) for examining a subject data word, the subject data word comprising a plurality of subject-data blocks, and for identifying a full match between the subject data word and a signature data pattern, the signature data pattern comprising a plurality of signature-data blocks, wherein each of the subject-data blocks and each of the signature-data blocks has (i) a respective value and (ii) a respective position, the IPS comprising:

at least one network interface;

at least one processor;

partial-match hardware having at least part of the signature data pattern stored therein;

full-match hardware having the signature data pattern stored therein; and

data storage containing instructions executable by the at least one processor for causing the IPS to carry out a set of functions, the set of functions comprising;

receiving the subject data word via the at least one network interface;

making a partial-match determination comprising;

an identification of a partial-match address based at least in part on at least part of the subject data word, and

a determination that at least one of the following is stored in the partial-match hardware in association with the partial-match address;

(i) a set overflow indicator and (ii) a partial-match number of the signature-data blocks that respectively match the same partial-match number of the subject-data blocks with respect to both value and position, wherein the partial-match number is (i) greater than or equal to two and (ii) less than a total number of the subject-data blocks;

subsequent to making the partial-match determination, making a full-match determination comprising;

an identification of a full-match address based at least in part on at least part of the subject data word; and

a determination that the signature data pattern is stored in the full-match hardware in association with the full-match address; and

storing a full-match indicator, the full-match indicator indicating that the full-match determination has been made.

53. The IPS of claim 52, wherein the partial-match hardware comprises static random access memory (SRAM).

54. The IPS of claim 52, wherein the full-match hardware comprises dynamic random access memory (DRAM).

55. The IPS of claim 52, wherein an operating speed that is characteristic of the partial-match hardware is greater than an operating speed that is characteristic of the full-match hardware.

56. The IPS of claim 52, further comprising pre-processing hardware having at least one pre-processing-signature-hash result flagged therein, wherein the set of functions further comprises, prior to making the partial-match determination, making a pre-processing determination comprising a determination that a pre-processing number of pre-processing-subject-hash results are flagged as being pre-processing-signature-hash results in the pre-processing hardware.

57. The IPS of claim 56, wherein the pre-processing hardware comprises Block random access memory (Block RAM).

58. The IPS of claim 56, wherein an operating speed that is characteristic of the pre-processing hardware is greater than an operating speed that is characteristic of the partial-match hardware, and further wherein the operating speed that is characteristic of the partial-match hardware is greater than an operating speed that is characteristic of the full-match hardware.

59. The IPS of claim 52, embodied in a single network device.

60. The IPS of claim 52, distributed across multiple network devices.