基于并行字符索引的多步长正则表达式匹配算法

来源：计算机研究与发展杂志2015年第3期北京时间：

作者：丁麟轩,黄昆,张大方,

摘要：深度包检测(deeppacketinspection,DPI)是网络入侵检测与防御系统(networkintrusiondete-ctionandpreventionsystem,NIDPS)的核心.基于三态内容可寻址存储器(ternarycontentaddressablememory,TCAM)的正则表达式匹配算法提高了数据包的处理速度，成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性，且能耗与存储空间成正比.由于DFA的存储空间开销比较大，且存储空间大小随着DFA步长数的增加而指数倍增，基于TCAM的DFA面临高能耗的问题，特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法(multi-strideparallelcharacter-indexedDFA,PCIDFA)，对确定型有限自动机(deterministicfiniteautomaton,DFA)构造并行字符索引，通过比特位图取交集，减少匹配时激活的TCAM块数，显著降低TCAM能耗.实验结果表明：与多步长DFA相比，多步长PCIDFA在TCAM能耗上减少了99.8%以上，在TCAM存储空间开销上减少了48.5%~65.3%，在吞吐量上提高了1.9~2.6倍.

关键词：正则表达式匹配, 三态内容可寻址存储器, 并行字符索引, 分块存储, 低能耗,