Method and apparatus for detecting predefined signatures in packet payload using Bloom filters
AssigneeWashington University
InventorsSarang Dharmapurikar, Praveen Krishnamurthy, Todd Sproull, John Lockwood
Life of this patent
Estimating the term…
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.
Claims57
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.
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.
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.
Dependencies are inferred from the claim text.