入侵检测系统中高效的模式匹配算法  

Efficient Pattern Matching Algorithm for Intrusion Detection Systems

作　　者：杨文君[1] 魏占国[2] 王玉平[3] 

机构地区：[1]牡丹江师范学院计算机科学与技术系,黑龙江牡丹江157012 [2]北京林业大学工学院,北京100083 [3]浙江大学计算机科学与技术学院,浙江杭州310027

出　　处：《小型微型计算机系统》2009年第11期2189-2194,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60731147)资助;黑龙江省教育厅科技项目(11531389)资助;牡丹江师范学院科技项目(kY2008003)资助

摘　　要：针对入侵检测系统模式匹配效率低的问题,提出一种高效的模式匹配算法.该算法通过对模式进行预处理记录模式的信息,然后对子节点进行递归比较,找到重复度最大的部分,提高模式匹配的效率;通过增加附加m个节点的匹配模式结构,降低模式匹配算法的时间与空间复杂度.理论分析表明,对于包含n个节点的主题树,提出的模式匹配算法的时间复杂度为O(nlog2n+mlog2m),空间复杂度为O(n+m).详细的实验以及与现有算法的比较表明,提出的模式匹配算法在时间、空间和匹配率性能上具有更高的效率.To overcome the defects of low efficiency of pattern matching in intrusion detection systems （IDS）, an efficient pattern matching algorithm is proposed. The proposed algorithm first preprocesses pattern to record pattern information, then it recursive compares the nodes to find the most common part of pattern to improve efficiency. The proposed algorithm also appends auxiliary structure of nodes in pattern to reduce time and space complexity. Theoretical analysis shows that for the subject with nodes,the time complexity of the proposed algorithm is, and space complexity is. Detailed experimental results and comparisons with existed algorithms show that the proposed algorithm outperforms current state-of-the-art algorithms in terms of time efficiency, space efficiency and matching ratio.

关 键 词：入侵检测系统 模式匹配 效率 

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