一种入侵检测系统中模式匹配算法的研究

摘要

本文主要围绕着开放源码的入侵检测系统Snort中模式匹配算法展开的一系列的工作。 首先，从Snort系统入手，分析此系统工作的原理，介绍特征分析和协议分析。重点对系统中规则的格式作描述，因为它是模式匹配的基础，并对模式匹配的发展及应用作介绍。 然后，进入模式匹配算法的具体研究阶段，分别对重点的单模式匹配算法与多模式匹配算法进行分析。详细说明各算法的工作方式，给出相应的算法，并举例、作图进行分析。选取的单模式匹配算法有：朴素的模式匹配算法、无回溯的KMP(Knuth-Morris-Pratt)模式匹配算法、BM(Boyer-Moore)模式匹配算法及BMH(Boyer-Moore-Horspool)模式匹配算法。多模式匹配算法有：AC(Aho-Corasick)多模式匹配算法和ACBM多模式匹配算法。 接下来，对两种较优的单模式匹配算法BM算法和BMH算法进行分析和比较，以便找出性能相对完善的一种，应用到多模式匹配算法中去。在实验过程中，分别分析了两种算法在不同长度模式下的比较次数，BM算法进行预处理的比较次数及两种算法的执行时间。然后，将BMH算法应用到多模式匹配算法中去，此代码经调试已经实现，并与ACBM算法进行比较，其性能优于ACBM算法。 最后，指出今后研究的工作和努力的方向。

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

第一章引言

1.1研究背景

1.2研究的目的和意义

1.3论文安排

第二章入侵检测系统简介

2.1入侵检测技术的发展

2.2入侵检测技术的分类

2.2.1按照信息源的分类

2.2.2按照检测方法的分类

2.3 snort入侵检测系统简介

2.3.1特征(Signature)分析与协议(Protoclo)分析

2.3.2 Snort系统的检测规则格式

2.3.3 Snort系统中的模式匹配算法

第三章单模式匹配算法的研究

3.1模式匹配

3.2朴素的匹配算法

3.3无回溯的模式匹配算法KMP(Knuth-Morris-Pratt)

3.4 BM(Boyer-Moore)算法

3.4.1 BM算法的基本思想

3.4.2具体算法

3.5 BMH(Boyer-Moore-Horspool)算法

第四章多模式匹配算法的研究

4.1 AC(Aho-Corasick)算法

4.1.1 AC算法的模式匹配过程

4.1.2 AC算法的预处理函数结构

4.2 AC_BM算法

4.2.1 AC与BM算法的结合

4.2.2 AC_BM算法的数据结构及实现

第五章对Snort系统中模式匹配算法进行改善

5.1 SNORT系统采用多模式算法的必要性

5.1.1协议解析器

5.1.2规则检测引擎

5.2两种单模式匹配算法的比较

5.2.1算法理论分析

5.2.2实验数据与分析

5.3 BMH算法的应用

5.3.1 BMH算法在多模式匹配算法中的应用

5.3.2单模式匹配算法可选用BMH算法

第六章总结与建议

参考文献

致 谢