对模式串匹配算法WuManber的复杂度攻击  

Algorithmic Complexity Attacks Against WuManber

作　　者：张宇[1,2] 刘萍[1] 刘燕兵[1,2] 谭建龙[1] 郭莉[1] 

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院研究生院,北京100049

出　　处：《计算机研究与发展》2011年第8期1381-1389,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61070026);国家"九七三"重点基础研究计划基金项目(2007CB311100);国家"242"信息安全计划基金项目(2010A018)

摘　　要：模式匹配问题是计算机科学的基础问题之一,是网络信息安全、信息检索与过滤、计算生物学等众多领域的核心问题.模式匹配技术在网络信息安全领域的广泛应用,导致了许多安全问题.WuManber算法是一种经典的多模式匹配算法,通过对WuManber算法实现原理的分析,给出了一种对WuManber算法进行复杂度攻击的方法,并对攻击数据的构造问题给出了问题描述和最优求解.实验表明,WuManber算法检测攻击数据的速度明显慢于检测随机数据和网络真实数据的速度,并发现只需已知少量的模式串,就可以构造有效的攻击数据.根据攻击数据的构造方法,在给出攻击方法的同时,也给出了防守方面的建议,可以有效地提高使用WuManber算法系统的安全性.Pattern matching is one ot the fundamental problems in computer science.It is the kcy problem of many important scopes such as network information security, information retrieval and filtration, computational biology, etc. A great number of security problems have arisen with the wide application of pattern matching, especially in network information security systems, such as intrusion detection and prevention systems, anti-virus systems, anti-spare systems, firewall, etc. A method of algorithmic complexity attacks against WuManber which is a classical multi-patterrn algorithm, and the optimal solution of creating the attacking data are presented in this article. Compared with random data and the data from network, the attacking data can greatly reduce the searching speed of WuManher. Experiments on random data sets show that the larger character set, the better attacking performance. And experiments on the data from the network show that the attacking data can reduce WuManber searching speed by more than 50~. It is found that if a small part of the pattern set is known, the attack data can be created. Defensively speaking, it is important that the pattern set must be kept secret. This article also provides some strategies of improving the security of network information security systems. The attacking data can also be used in checking the system security.

关 键 词：算法复杂度攻击 WuManber算法 模式匹配 算法安全性 入侵检测 

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