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

Research on complex rules matching on a large scale

作　　者：张树壮[1] 罗浩[2] 方滨兴[1,2] 

机构地区：[1]哈尔滨工业大学计算机网络与信息安全技术研究中心,哈尔滨150001 [2]中国科学院计算技术研究所,北京100190

出　　处：《高技术通讯》2010年第12期1217-1223,共7页Chinese High Technology Letters

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

摘　　要：针对当前安全系统对复杂规则的需求和复杂规则匹配技术的状况,提出了一种新的规则表示方式——字符串表达式,并给出了对应的匹配方法——基于扩展的有限状态自动机(XFA)实现大规模复杂规则匹配的算法。字符串表达式可以描述多个精确字符串之间的逻辑关系与空间位置关系,从而满足安全系统对复杂特征的描述需求。匹配使用二维结构来完成,首先用经典串匹配算法进行字符串的存在性验证,然后将其结果作为输入,驱动以表达式中字符串为"字符"的XFA完成逻辑关系的验证。基于XFA的匹配方法的空间效率和时间效率都接近多模精确串匹配算法。实验结果表明,文中提出的方法既能满足安全系统对关联特征的描述需求,又能提供高效的匹配性能,较好地解决了大规模(万条)的复杂规则匹配问题。In view of current security systems＇ needs for complex rules and the present state of the complex rules matching, this paper proposes the concept of the string expression, a new type of rule expression, and correspondingly, gives its matching method, an algorithm for complex rules matching on a large scale based on the extended finite automation. String expression can describe the logical relation and the position relation between multiple strings. The matching is achieved by using the two-level matching structure. First, it checks the existing of each string using the classical string matching algorithm, and then drives the extended finite automaton using the previous checking results. Its time complexi- ty and space complexity are near to the classical string matching algorithm. The experimental result shows that the string expression and its matching method can provide a high matching ef^ciency as well as satisfy the complex request on se- mantic of security systems. It resolves the complex rules matching problem on the scale of 10000 better.

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

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]