大规模复杂规则匹配技术研究

摘要：

针对当前安全系统对复杂规则的需求和复杂规则匹配技术的状况,提出了一种新的规则表示方式--字符串表达式,并给出了对应的匹配方法--基于扩展的有限状态自动机(XFA)实现大规模复杂规则匹配的算法.字符串表达式可以描述多个精确字符串之间的逻辑关系与空间位置关系,从而满足安全系统对复杂特征的描述需求.匹配使用二维结构来完成,首先用经典串匹配算法进行字符串的存在性验证,然后将其结果作为输入,驱动以表达式中字符串为"字符"的XFA完成逻辑关系的验证.基于XFA的匹配方法的空间效率和时间效率都接近多模精确串匹配算法.实验结果表明,文中提出的方法既能满足安全系统对关联特征的描述需求,又能提供高效的匹配性能,较好地解决了大规模(万条)的复杂规则匹配问题.

关键词：串匹配、正则表达式、字符串表达式、扩展字符串匹配、扩展有限自动机

所属期刊栏目：20

分类号：TP3;TN9

资助基金：863计划2009AA01Z437,2007AA01Z442,2007AA010501,2007AA01Z474;973计划2007CB311101;国家自然科学基金60903209

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

页数：共7页

页码：1217-1223