Design Of Configurable Matching Engine For Regular Expression With FPGA

Regular expression is a kind of model for string matching, and can quickly descripe complex strings by a simple pattern because of its flexity, logicality and functionality. Regular expression usually is used to Network Intrusion Detection System as well as text processing, etc. In generally, matching regular expression is realized by software. However, by the increasement of the network's bandwidth, the surge in network data traffic, and the rapid development of cloud computing technology, the implementation by software becomes the bottleneck in high-speed regular expression matching. And hardware, for its parallel characteristic, can be used to process pattern matching rapidly. Therefore, it has become the new carrier that researchers design and construct the matching engine.FPGA. for its features such as special structure, reconfiguration, was usually used in the situation to implement high speed and multidata now. This thesis introduced a method which used FPGA to realize regular expression matching. Firstly, we sketched the several classic algorithms to convert regular expression into automata. And after analysing and comparing their advantages and disadvantages, we proposed a new NFA construction algorithm. Its space complexity is O(n) and the time complexity is O(n2) in theory, and the scale of the NFA is small relatively. The number of the states is less than the literal characters n in the regular expression, and the number of the conversion is about n. And the NFA contains one and only one final state. Then, the process of implementing string match in FPGA has been researched, the design of constructing child match module has been presented, and generated a match module library. The design can greatly save time cost in the subsequent process of design, and speed up the renewal of the feature patterns in IDS. For some special regular expression, thesis proposed certian optimization schemes to save the hardware resources in design. Finally, for some given regular expressions, which would be dealed with the S-NFA and the Thompson algorithm respectively and converted into the corresponding NFA, and the chapter four would present a method to dispose NFA logically to apply to hardware processing. We set up a Testbench test platform to test the given regular expressions, then used the child module library in the thesis to implement them and evaluated the two algorithms from the aspects of NFAs' scales and actual match time delays, and the simulation results were given.In conclusion, the thesis proposed a new NFA constructing algorithm which is based on the study of technology for matching regular expression as well as the logic method to represent the NFA, constructed a child match module library which has been verified by simulation experiment, and also compared the performance between S-NFA and Thompson. The results showed that the S-NFA algorithm was superior to the classical Thompson in many aspects including the construction process, the scale of the generated NFA and the actual delay in application. And it is also suitable for realization by FPGA.