基于多字符DFA的高速正则表达式匹配算法
作者：贺炜　郭云飞　莫涵　扈红超
来源：《计算机应用》2013年第08期
        摘 要：基于确定性有限自动机（DFA）的传统正则表达式匹配方法存在单周期处理单字符的速度瓶颈。为提升处理速率，提出一种单周期处理多字符的匹配算法MCDFA，该算法基于DFA实现，支持匹配位置的精确定位。MCDFA将传统DFA中的单字符跳转合并为多字符跳转，实现了单周期处理多个输入字符。通过状态转移矩阵二阶压缩算法，MCDFA分别对矩阵行内以及行间冗余进行消除，减少了内存使用。300条规则下，单周期处理8字符时，MCDFA吞吐率能够达到7.88Gb/s，内存占用小于6MB，预处理时间为19.24s。实验结果表明，MCDFA能够有效提升系统吞吐率，并且保证内存占用在可接受范围之内，性能优于现有正则表达式匹配算法。
        关键词：正则表达式；高速；多字符；精确定位；矩阵压缩
        中图分类号： TP393
        文献标志码：A
        0 引言
        近年来，作为网络信息过滤、文字处理等应用中的关键部分，正则表达式匹配技术得到了快速发展，作为实现模式匹配的主要手段，广泛应用于二进制序列分析、扩展标记语言处理及入侵检测系统[1-2]。
        目前正则表达式匹配主要通过不确定性有限自动机（Nondeterministic Finite Automata，NFA）以及确定性有限自动机（Deterministic Finite Automata，DFA）实现[3]。NFA的缺点在于时间复杂度比较高，对于有n个状态的NFA，空间和时间复杂度均为O（n）；DFA处理一个字符则只需要访问一个状态，时间复杂度降低为O（1），但空间复杂度增加为O（2n）[4-5]。
        由于理论模型限制，每个周期内，标准NFA和DFA最快只能处理一个字符，成为速度瓶颈[6-7]。为进一步提升匹配速率，当前众多研究都集中于如何构建支持单周期多字符处理的自动机结构。
        本文提出一种基于DFA的单周期多字符处理算法MCDFA（MultiCharacter DFA），利用
了多字符处理的优势以及DFA时间复杂度低的特点，提升了系统处理速率，减少了内存访问次数。该算法支持每个周期处理2k个字符（k为任意自然数），并加入内存压缩技术，以减少内存消耗。通过现场可编程门阵列（Field Programmable Gate Array， FPGA）平台部署，算法的处理速率以及内存使用等性能得到了验证。
        1 相关工作
        传统的单字符匹配算法中， Liu等[8]提出的CSCA（Clusterbased Splitting Compression Algorithm）通过切分状态转移矩阵减少内存使用； Yang等[9]提出的SFA（Semideterministic Finite Automata）算法通过将部分DFA转化为NFA实现内存缩减；Qi等[10]提出的FEACAN（FrontEnd Acceleration for ContentAware Network）算法通过压缩状态转移矩阵取得较好的内存性能。
        Clark等[11]给出了一种基于多字符偏移并行处理的NFA结构。对于n位的目标字符串，首先求得偏移0到n-1位的n个字符串，将n个字符串送入n个相同的并行处理的NFA结构，得到匹配结果；该算法缺点在于多个NFA的复制导致内存消耗过大。
        Sutton等[12]给出了基于字符编码的多字符NFA匹配在FPGA中的实现方法，该算法在Clark等[11]提出的算法基础上，将并行处理的NFA结构修改为串行处理的寄存器结构，避免了NFA的多次复制；但随着字符串长度的增加，系统处理延时增大，无法保证处理频率，影响吞吐率性能。
        在Sutton等[12]的基础上， Yamagaki等[13]给出了任意正则表达式到多字符NFA结构的构建方法，与之前的方法相比， Yamagaki等[13]最大的突破在于实现了单个NFA结构处理多字符输入的功能，但是处理速率仍然受到NFA本身特性的影响，且算法依赖于硬件实现。
        由于NFA时间复杂度较高，上述基于NFA的方法不能很好地改善系统吞吐率。为进一步提升处理速率，克服NFA的缺点，本文采用时间复杂度较低的DFA作为结构基础。
        4 结语
        本文提出的MCDFA算法打破了传统的DFA算法单周期处理单字符的速度瓶颈，以一定的状态转移数量增长为代价，较好地提升了系统处理速率。MCDFA算法通过合并状态转移达到多字符处理目标，辅以相应的SST压缩算法，缓解了状态转移数量增长带来的内存损耗
压力。通过FPGA部署实现，测试验证了算法的性能，给出了相应参数的选取标准，证明了算法的可行性和有效性。随着单周期处理字符数的增多，内存读写、内存损耗问题会带来较大影响，使得MCDFA算法处理速率增长速度降低，不能成倍提升处理速率。
        针对单周期多字符处理的研究并不仅限于文中提出的方法，其他的方法例如合并状态、并行处理等均据有一定的可行性。下一步的研究工作主要集中于算法在硬件中的优化以及算法的进一步性能提升。
        参考文献：
        [1]ANTONELLO R，字符常量合法 FERNANDES S， SADOK D， et al. Deterministic finite automaton for scalable traffic identification： the power of compressing by range [C]// Proceedings of the 2012 IEEE Network Operations and Management Symposium. Piscataway： IEEE， 2012： 155-162.
        [2]ZHENG K， ZHANG X， CAI Z， et al. Scalable NIDS via negative pattern matching and exclusive pattern matching [C]// INFOCOM 2010： Proceedings of 2010 IEE
E International Conference on Computer Communications， Joint Conference of the IEEE Computer and Communications Societies. Washington， DC： IEEE Computer and Communications Societies， 2010： 1-9.
        [3]LIU T W， SUN Y， GUO L， et al. SDFA： series DFA for memoryefficient regular expression matching [C]// CIAA12： Proceedings of the 17th International Conference on Implementation and Application of Automata， LNCS 7381. Berlin： SpringerVerlag， 2012： 337-344.
        [4]WOODS L， TEUBNER J， ALONSO G. Complex event detection at wire speed with FPGAs [J]. Proceedings of the VLDB Endowment， 2010， 3（1/2）： 660-669.
        [5]YANG Y H E， JIANG W， PRASANNA V K. Compact architecture for highthroughput regular expression matching on FPGA [C]// Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. New York： ACM， 2008： 30-39.
        [6]MITRA A， NAJJAR W， BHUYAN L. Compiling PCRE to FPGA for accelerating snort IDS [C]// Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Networking and Communications Systems. New York： ACM， 2007： 127-136.
        [7]JIANG L， TAN J L， LIU Y B. ClusterFA： a memoryefficient DFA structure for network intrusion detection [C]// ASIACCS 12： Proceedings of the 7th ACM Symposium on Computer and Communications Security Information. New York： ACM， 2012： 65-66.
        [8]LIU T W， YANG Y F， LIU Y B， et al. An efficient regular expressions compression algorithm from a new perspective [C]// INFOCOM 2011： Proceedings of 30th IEEE International Conference on Computer Communications， Joint Conference of the IEEE Computer and Communications Societies. Washington， DC： IEEE Computer and Communications Societies， 2011： 2129-2137.
        [9]YANG YH E， PRASANNA V K. Spacetime tradeoff in regular expression matching with semideterministic finite automata [C]// INFOCOM 2011： Proceedings of 30th IEEE Int
ernational Conference on Computer Communications.Joint Conference of the IEEE Computer and Communications Societies.Washington， DC： IEEE Computer and Communications Societies， 2011： 1853-1861.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。