基于FPGA改进电路的高性能正则表达式匹配算法

针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。

High-performance regular expressions matching algorithm based on improved FPGA circuit

Concerning the low throughput and too much logic resource usage in the process of regular expressions matching, an improved Deterministic Finite Automaton (DFA) regular expression matching algorithm fully based on Field-Programmable Gate Array (FPGA) logic circuit was designed. Firstly, the result that most transfer edges of each state in DFA would point intensively to the same state characteristics was counted; then an acquiescent transfer edge for each state setting in DFA was provided according to the transfer matrix of regular expressions; finally, simplified logical circuit was given, and measurement was conducted on the L7-filter rule set. The experimental result shows that, compared with the former Nondeterministic Finite Automaton (NFA) algorithm, 10%-60% rules get a higher throughput, and 62%-87% rules cost less logic resources.