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

摘要

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.%针对入侵检测系统模式匹配效率低的问题,提出一种高效的模式匹配算法.该算法通过对模式进行预处理记录模式的信息,然后对子节点进行递归比较,找到重复度最大的部分,提高模式匹配的效率;通过增加附加m个节点的匹配模式结构,降低模式匹配算法的时间与空间复杂度.理论分析表明,对于包含n个节点的主题树,提出的模式匹配算法的时间复杂度为O(nlog_2~n+mlog_2~m),空间复杂度为O(n+m).详细的实验以及与现有算法的比较表明,提出的模式匹配算法在时间、空间和匹配率性能上具有更高的效率.