PiDFA: A practical multi-stride regular expression matching engine based On FPGA
Jiajia Yang, Lei Jiang, Qiu Hua Tang, Qiong Dai, Jianlong Tan · 2016
DPI technology has been widely deployed in networking intrusion detection system (NIDS) to detect attacks or viruses. State-of-the-art NIDS uses deterministic finite automata (DFA) algorithms to perform regular expression matching for its stable matching speed. However, traditional DFA algorithm's throughput is limited by the input character's width (usually one character per time). Although the multi-stride method (process multiple characters per time) can increase the throughput, it leads the DFA transition table to an exponentially increased memory consumption. In this paper, we propose a novel multi-stride regular expression matching engine called PiDFA based on Field-Programmable Gate Array (FPGA). It applies two methods to solve traditional multi-stride algorithms' memory explosion problem: DFA Transition Merging method and top-k state extraction method. Experiment results show that PiDFA achieves more than 30-fold better performance than original DFA algorithm. Whats more, PiDFA is orthogonal to existing transition table compression algorithms. Implemented with PiDFA algorithm, ClusterFA's matching speed is increased by 6-50 times while maintaining ClusterFA's low memory consumption.