Implementation Results of Bloom Filters for String Matching

Attig, Dharmapurikar, Lockwood

bloom filters fpga intrusion detection deep packet inspection string matching

@inproceedings{attig:fccm-2004,
  title={Implementation Results of {Bloom} Filters for String Matching},
  author={Attig, M. and Dharmapurikar, S. and Lockwood, J.},
  booktitle={{IEEE} Symposium on Field-Programmable
             Custom Computing Machines ({FCCM})},
  year={2004},
  pages={322--323}
}

Implements a fast signature matching mechanism in hardware for network intrusion detection

• Built in a single FPGA, which watches network traffic
• Periodically receives updates on new signatures from software controller
• If any matches are detected, message is sent to software controller

Multiple Bloom filters are used in parallel to scan for signatures between 2 and 26 bytes long

• This is enough to cover most unique strings in the SNORT rules
• Each filter uses a 16,384 bit vector (2048 bytes)
  • Reduces false positive rate to 0.0039, permits 1419 signatures at optimal rate
• With 25 filters (2 to 26 byte signatures), can scan for 35475 signatures at optimal false positive rate

Second stage does a precise check, ensuring no false positives

• Not exactly clear how it efficiently determines what exactly to check against
  • Though it clearly knows the index & length that potentially matched