Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters
Sarang Dharmapurikar · Open Scholarship Institutional Repository (Washington University in St. Louis) · 2004
Modern Network Intrusion Detection Systems (NIDS) inspect the network packet payload to check if it conforms to the security policies of the given network. This process, often referred to as deep packet inspection, involves detection of predefined signature strings or keywords starting at an arbitrary location in the payload. String matching is a computationally intensive task and can become a potential bottleneck without high-speed processing. Since the conventional software-implemented string matching algorithms have not kept pace with the increasing network speeds, special purpose hardware solutions have been introduced. In this paper we show how Bloom filters can be used effectively to perform string matching for thousands of strings at wire speed. We describe how Bloom filters can be implemented feasibly with FPGA. Technology analysis shows that this approach for string matching is more effective than the current FPGA-based string matching circuits which use Deterministic or Non-deterministic Finite Automata (DFA or NFA). Finally, we give the details of our implementation of string matching technique on Xilinx XCV 2000E FPGA. 1