Research And Application Of Multi-pattern Matching Engine Based On Bloom Filter

With the development of computer networks, network security issues become increasingly prominent. To detect these attacks online, pattern matching demands exceptionally high performance. However , software-based implementations cannot meet the application requirements, hardware-based implementations can significantly improve performance, achieve higher throughput.This paper surveys the hardware implementations of the multi-pattern matching, a multi-pattern matching engine providing larger throughput, low latency and scalability was designed. Main content, innovation and contribution in this paper are as follows:two commonly used multi-pattern algorithms, Aho-Corasick's automata based algorithm and Wu-Manber algorithm are introduced,and A lot of research works have been done in the hardware based implementations of the multi-pattern matching. Especially, the features and defects of the method based on TCAM and reconfigurable FPGA ware analyzed.By using Bloom filter and bit-split state machine, a two-level multi-pattern matching engine suitable for hardware implementation was designed. Bloom filter is a data structure using hash functions mapping to compress the parameter space, which may achieve high-speed matching, but there are false positives. The suspicious strings are picked up by the bloom filter engine, and then sent to a bit-split state machine for verification. Bloom filter engine reduces the stings which the bit-split state machine should inspect, overcomes the shortcomings of its slow-speed; the bit-split state machine avoid false positives of the Bloom filter to improve the efficiency of the whole engine.The analysis and the experimental results show that the high throughput of the algorithm can satisfy the wire speed detection requirement when the low resource consumption in hardware resource further improves the scalability of for improvement in throughput and scalability.The application of high speed multi-pattern matching engine on network intrusion detection system is introduced and a performance test is carried out. The result proves that the engine designed in this paper can effectively improve the performance of NIDS.