Method and apparatus for detecting predefined signatures in packet payload using Bloom filters

• US 7,444,515 B2
• Filed: 08/14/2003
• Issued: 10/28/2008
• Est. Priority Date: 08/14/2003
• Status: Active Grant

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Krishnamurthy, Praveen, Dharmapurikar, Sarang, Lockwood, John, Sproull, Todd
• Primary Examiner(s): Sheikh; Ayaz
• Assistant Examiner(s): Moorthy; Aravind K
• Application Number:
  US10/640,513
• Publication Number:
  US 20050086520A1
• Time in Patent Office: 1,902 Days
• Field of Search: 713/176
• US Class Current: 713/176
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

The present invention relates to a method and apparatus based on Bloom filters for detecting predefined signatures (a string of bytes) in a network packet payload. A Bloom filter is a data structure for representing a set of strings in order to support membership queries. Hardware Bloom filters isolate all packets that potentially contain predefined signatures. Another independent process eliminates false positives produced by the Bloom filters. The system is implemented on a FPGA platform, resulting in a set of 10,000 strings being scanned in the network data at the line speed of 2.4 Gbps.

Claims

1. A method for detecting a predefined signature in a network packet payload, said packet constituting traffic on a digital network, said method comprising the steps of:

storing said predefined signature in at least one of a plurality of Bloom filters, said predefined signature comprising a string of bytes, said string having a predetermined length;

monitoring a data stream on the network;

receiving from the data stream a string having said predetermined length;

membership testing said received string for an indication of membership in a Bloom filter; and

testing for a false positive indication of membership.

2. The method according to claim 1, wherein each of said Bloom filters contains at least one predefined signature.

3. The method according to claim 2, wherein said indication of membership comprises a correspondence between said received string and said predefined signature.

4. The method according to claim 3, wherein said step of testing for a false positive comprises using an analyzer to determine whether said indication of membership is a false positive.

5. The method according to claim 4, wherein when said received string matches a predefined signature, an appropriate action is taken on said received string.

6. The method according to claim 5, wherein said appropriate action comprises at least one of dropping a network packet containing the received string, forwarding said network packet, and logging said network packet.

7. The method according to claim 4 wherein a plurality of received strings are monitored in a window of a predetermined number of bytes to achieve a number of received sub-strings, and said received sub-strings are verified for membership in said Bloom filters.

8. The method according to claim 7, wherein, when multiple received sub-strings are verified for membership within said window, the longest sub-string among said multiple received sub-strings is considered first in order down to the shortest sub-signature until verification of membership of one of said sub-signatures in one of said Bloom filters is obtained by said analyzer.

9. The method according to claim 2, wherein said plurality of Bloom filters constitute an engine, and a plurality of predefined signatures are grouped according to length and stored in said engine.

10. The method according to claim 9, wherein said data stream arrives at a rate of one byte per clock cycle for said engine.

11. The method according to claim 10, wherein each of said Bloom filters is tested for membership once per clock cycle.

12. The method according to claim 10, wherein said membership is verified in a single clock cycle.

13. The method according to claim 12, wherein, after membership of the received string is tested in said Bloom filters, said network data stream advances by one byte.

14. The method according to claim 2, wherein said plurality of Bloom filters constitute a plurality of parallel engines, each said engine coupled to a corresponding one of a plurality of analyzers.

15. The method according to claim 14, wherein each said engine advances said network data stream by a corresponding number of bytes.

16. The method according to claim 4, wherein said analyzer comprises a hash table of signatures.

17. The method according to claim 16, wherein a set of received strings is inserted into said hash table, with collisions resolved by chaining colliding received strings together in a linked list.

18. The method according to claim 17, wherein a number of bits allocated to a membership of said received string in a Bloom filter decides a number of hash functions needed for said Bloom filter.

19. The method according to claim 18, wherein each of said hash functions corresponds to one random lookup in an m-bit long memory array.

20. The method according to claim 16, wherein said hash table is one of an off-chip commodity SRAM and a SDRAM.

21. The method according to claim 16, wherein said Bloom filters are counting Bloom filters each of which maintains a vector of counters corresponding to each bit in a bit vector.

22. The method according to claim 21, wherein said counters are maintained in software and a bit corresponding to each of said counters is maintained in hardware.

23. The method according to claim 9, wherein a plurality of said engines are employed to increase throughput by a multiple of a quantity of said engines.

24. The method according to claim 23, wherein said throughput is greater than 2.4 Gbps.

25. The method according to claim 9, wherein a set of multiple mini-Bloom filters is allocated to each Bloom filter.

26. The method according to claim 25, further comprising:

uniformly distributing said predefined signatures into said set of said mini-Bloom filters.

27. The method according to claim 26, wherein each of said predefined signatures is stored in only one of said mini-Bloom filters.

28. The method according to claim 27, wherein said uniform distribution is achieved by calculating a primary hash over each of said predefined signatures.

29. The method according to claim 28, wherein said primary hash is calculated on network sub-strings from said data stream to determine which of said mini-Bloom filters within said set should be probed for membership of said network sub-string.

30. The method according to claim 29, wherein each of said network sub-strings is used to probe only one of said mini-Bloom filters within said set dedicated for a particular string length.

31. The method according to claim 1, wherein said membership testing is performed on each received string of every predetermined length in every packet.

32. The method according to claim 1, wherein no false negatives are obtained.

33. The method according to claim 1, wherein said data stream comprises TCP/IP data.

34. The method according to claim 1, wherein at least one of said Bloom filters utilizes an embedded memory.

35. The method according to claim 34, wherein a retrieval time from said memory of said predefined signature depends on said predetermined length.

36. The method according to claim 34, wherein multiple memories are used to create each of said Bloom filters, and no more than a restricted number of hash functions map to a particular memory.

37. The method according to claim 34, wherein increasing a size of said embedded memory enables a proportional increase in a number of received strings.

38. The method according to claim 34, wherein said embedded memory is an embedded RAM in a VLSI chip.

39. The method according to claim 1, wherein said Bloom filters are implemented in an FPGA.

40. An apparatus for detecting a predefined signature in a network packet payload, said packet constituting traffic on a digital network, said apparatus comprising:

means for storing said predefined signature in at least one of a plurality of Bloom filters, said predefined signature comprising a string of bytes, said string having a predetermined length;

means for monitoring a data stream on the network;

means for receiving from the data stream a string having an apparent correspondence to said predefined signature; and

means for determining, using an analyzer, whether said apparent correspondence is a false positive.

41. An apparatus for detecting predefined signatures in packet payload traffic on a digital network, the apparatus comprising:

an FPGA having a plurality of embedded block memories for storm said predefined signatures, said FPGA being used to construct a plurality of Bloom filters, and said FPGA being disposed on a platform;

a switch adapted to multicast data in a data stream from the network to a router, wherein traffic from the network to said router is processed in said FPGA; and

a monitor adapted to check all packets marked as containing a possible match to at least one of said predefined signatures stored in said Bloom filters.

42. The apparatus of claim 41, wherein said FPGA comprises embedded memories.

43. The apparatus according to claim 42, wherein said embedded memories are embedded RAMs in a VLSI chip.

44. The apparatus according to claim 43, wherein said plurality of Bloom filters comprise at least one set of parallel Bloom filters and each set of parallel Bloom filters comprises an engine adapted to increase throughput by a multiple of a quantity of said engines.

45. The apparatus according to claim 44, wherein said throughput is greater than 2.4 Gbps.

46. The apparatus according to claim 41, wherein said monitor is an analyzer.

47. The apparatus according to claim 46, wherein said analyzer comprises a table of hashed signatures.

48. The apparatus according to claim 47, wherein said hash table is one of an off-chip commodity SRAM and a SDRAM.

49. The apparatus according to claim 41, wherein said monitor comprises a computer.

50. The apparatus according to claim 41, wherein said Bloom filters are counting Bloom filters each adapted to maintain a vector of counters corresponding to each bit in a bit vector.

51. The apparatus according to claim 50, wherein said counters are maintained in software and a bit corresponding to each of said counters is maintained in hardware.

52. The apparatus according to claim 41, wherein a set of multiple mini-Bloom filters is allocated to each of said Bloom filters.

53. The apparatus according to claim 52, wherein said predefined signatures are uniformly distributed into said set of said mini-Bloom filters.

54. The apparatus according to claim 53, wherein each of said predefined signatures is stored in only one of said mini-Bloom filters.

55. The apparatus according to claim 54, wherein said uniform distribution is achieved by calculating a primary hash over each of said predefined signatures.

56. The apparatus according to claim 55, wherein said primary hash is calculated on network sub-strings from said data stream to determine which of said mini-Bloom filters within said set should be probed for membership of said network sub-string.

57. The apparatus according to claim 56, wherein each of said network sub-strings is used to probe only one of said mini-Bloom filters within said set dedicated for a particular string length.