Research On Multi-pattern Matching Algorithms Based On Regular Expressions And Hardware Implementation

With the global increasing levels of information，Network and information security isbecoming increasingly important.Current network and information security industry has become anational security, political stability, economic development, social life, health and cultural aspectsof life and security of a supporting role in the key industries,Network and information securityindustry in the whole pattern of industrial distribution and even the national strategy has a pivotalposition and role.China since 2003 has made great progress in the network and informationsecurity , but overall is relatively backward. Network and information security research is thepriority of current information industry research .This paper describes some classic multi-pattern matching algorithm ,such as theAho-Corasick、Aho-Corasick-Boyer-Moore、Wu-Manber and so on,we describes the developmentof pattern-matching technology status and future trends.With the escalation of network bandwidthand more and more complex application, software-based multi-pattern matching algorithm hasbeen far from satisfying the needs of the application, even some of the hardware implementationbased on exact pattern matching algorithm in the case of complex models can not meet the impactof tens of Gbps traffic, there are serious scalability issues, Therefore, hardware-based patternmatching algorithm is an inevitable trend of development.this paper introduce the principle and the application of the bloom filter，analysis the impactof Bloom filter performance factors,On this basis,we implement the Bloom filters based onFPGA,by analyzing hash function which affect the hardware computing time to select theappropriate number of hash function and the function and the size of the mapping space,so weimprove the hardware performance of Bloom filters.Through the decomposition of the inputcollection information,after several hash,optimize and improve the performance of Bloomfilters,compared to the traditional Bloom filter,improved Bloom filter have a good improvementin the number of hash function, mapping the size and space perations.In order to overcome the bottleneck of the classic Aho-Corasick algorithm which is acontinuous need to match the speed of RAM access ,this paper finally designed a K stepsmulti-pattern matching algorithm based on FPGA circuit.Matching circuit including split inputdata module、process failed state module、match engine module、analysis and arbitration module、memory access interface and so on.For an input，After entering Bloom Filter，wait, after Hashoperation, lookup array, determine, after four clock cycles，we will get the results of BloomFilter.however in practical applications,less than 3% of the data matching may occur,so we designed an approach“Bloom Filter+matching assembly line”.input data enter the matchingassembly lines in orders , there’s no need waiting for the results of Bloom Filter one by one ,Forthose secure data,by Bloom Filter and pipeline processing ,it can be quickly filtered.When aBloom Filter hit it,assembly line will stop,it match the input data one by one,after the matchfinished,restart the assembly line,This greatly increased the efficiency of the process.