一种快速且节约存储器的多模式匹配算法

摘要：

同时对数百个模式进行比较的多模式匹配算法是入侵侦测/预防系统的一项关键技术.但是在Gbps级的高速网络中,多模式匹配过度仍是一个瓶颈.提出一个基于确定性有限自动机(DFA)的算法,能在一个周期内处理多个字符.该算法持DFA的头部抽取出来,构造一个子DFA,称为Head DFA(HDFA),将其余部分构成另一个子DFA-General DFA(GDFA).针对这两个子DFA,分别设计了两套硬件,并让它们同时运行,然后根据当前状态和各自的匹配情况决定取用哪套硬件的结果.这样不仅可以提高匹配速度,还可以利用两个子DFA之间的联系较大地减小其存储需求.

关键词：模式匹配、内容过滤、回滚机制、确定性有限状态机、算法

所属期刊栏目：30

分类号：TP393(计算技术、计算机技术)

在线出版日期：2009-10-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1521-1527