入侵检测中一类允许误差的多模式匹配算法  

Error-tolerant multi-pattern matching algorithms for intrusion detection

作　　者：宋华[1] 戴一奇[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《清华大学学报（自然科学版）》2003年第7期977-980,共4页Journal of Tsinghua University(Science and Technology)

基　　金：国家"九七三"重点基础研究发展项目(G1998030409)

摘　　要：入侵检测系统中所采用的各种分析方法存在很多问题。设计了一类允许误差的多模式匹配算法来解决这些问题。设计了3个算法来解决这一类允许误差的模式匹配问题,其中一个是单一模式匹配算法,两个是允许误差的多模式匹配算法,最后分析了这些算法的复杂性。在动态编程算法的基础上,新算法能够同时检测多种允许误差的攻击模式,允许攻击者攻击时所产生的事件序列存在一定的误差。通过分析和实验可以看出,新的允许误差的多模式匹配算法使得检测速度快,能够检测的模式数量多,检测性能有很大的提高。Many problems in intrusion d etection can be solved by error-tolerant multi-pattern matching algorithms. Th ree algorithms were designed for intrusion detection. The first algorithm was a single pattern matching algorithm while the other two were multi-pattern matchi ng algorithms. All three algorithms implemented as dynamic programming algorithm s detected the occurrences of any pattern from a given pattern set in a text, allowing a limited number of errors in the attack event sequences. The algorithms exploited the ability to arrange the pattern set in a searching t ree and detect multi intrusion patterns simultaneously. Analytical and experimental results show that all three error-tolerant multi- pattern matching algorithms are fast when searching large sets of patterns. 

关 键 词：网络安全 入侵检测系统 允许误差 多模式匹配算法 计算机网络 攻击模式 

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