Research And Design Of FPGA-based High Performance Pattern Matching Engines

As one of fundamental problems in computer science, pattern matching is widely used in various fields, especially in high-speed intrusion detecting and deep packet content filtering. Traditional software-based pattern matching engine is unable to finish various testing task at wire-speed under high-speed network environment, and become the main performance bottleneck of various practical application. Using auxiliary hardware units with a variety of optimization strategies to design high-speed pattern matching engine based on high-speed parallel hardware architecture such as AC automaton, Bloom Filter and TCAM became a top research direction. AC algorithm which performs stably on high-speed hardware platform was preferred by most hardware-based pattern matching engine. However, how to design an efficient pattern matching architecture which can improve the matching speed while reducing the storage overhead is still a challenging problem.After reviewing and analysing existing hardware-based pattern matching algorithm and their corresponding hardware architecture, this thesis designs and implements a FPGA-based high-performance pattern matching engine based on AC automaton. A multi-stride algorithm is proposed to improve the matching speed firstly, and then, two optimization methods are proposed to reduce the engine storage overhead. The designed matching engine can achieve high matching speed with little resource consumption. The contributions made in this thesis including:1. To improve the speed of single-stride AC automaton, we propose a multi-stride algorithm to extend the automaton step. The algorithm constructed an multi-stride automaton which is equivalent to the original automaton by selecting the key nodes, mapping"goto"and"Next"transition. Meanwhile a small amount of nodes called"transition nodes"were introduced to receive the offset characters and to ensure the correct match of any pattern string.2. To reduce the engine's storage overhead, M-1 character cache and some transitions are added to the multi-stride automaton, which can eliminate all the cross-transitions pointed to states with depth less than or equal to M, was account for up to 98% of the total transitions. The idea of pipelining to pattern matching is also introduced to create pipeline stages and multiple threads, so that all the patterns can be matched in parallel. Since the pipeline stages can record the historical matching information, all the cross-transitions in the automaton are eliminated.3. To assist with the implementation of hardware matching engine, two pre-processing software are programmed to finish the snort rule abstraction and multi-stride automaton construction job respectively. A matching engine prototype system containing 200 different strings selected from snort database is implemented in the Xilinx Virtex-5 chip. The matching speed can achieve 10+ Gbps according to different stride length of the automaton. By adopting the packet classification algorithm, a wire-speed hardware intrusion detection system with Bloom Filter is designed to filter high-speed network flow and improve the detection throughput dramatically.