Implementation Results
of Bloom Filters for String Matching
Abstract. Network
Intrusion Detection and Prevention Systems (IDPS) use
string matching to scan Internet packets for malicious
content. Bloom filters offer a mechanism to search for
a large number of strings efficiently and concurrently
when implemented with Field Programmable Gate Array (FPGA)
technology. A string matching circuit has been implemented
within the FPX platform using Bloom filters. Using 155
block RAMs on a single Xilinx VirtexE 2000 FPGA, the
circuit scans for 35,475 unique signatures.
1. Architecture
By using Bloom filters,
an IDPS can be implemented that scans for tens of thousands
of strings at Gigabit per second rates, all within a single
FPGA.We have built a system with Bloom filters that scans
Internet traffic. An overview of our string matching architecture
is shown below. Packets enter the system and are processed
by Internet Protocol (IP) wrappers. The data in the packet
goes to the input buffer and then flows through the content
pipeline. As the packet passes through the pipeline, multiple
Bloom engines scan different window lengths for signatures
of different lengths. Data leaves the content pipeline, flows
to the output buffer, streams through the wrappers, and then
packets are re-injected into the network. If a Bloom engine
detects a match, a hash table is queried to determine if
an exact match occurred. If the queried signature is an exact
match, the malicious content can be blocked and an alert
message is generated within an User Datagram Protocol (UDP)
packet, informing a network administrator, an end user, or
an automated process that a matching signature has been detected.
|
