snort入侵检测系统算法研究

《snort入侵检测系统算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Snort入侵检测系统算法研究随着X络流量的增大，Snort入侵检测系统处理数据的能力要求更高，一般可以通过配置Snort设置或者改进其模式匹配算法。利用正向和反向有限自动机，同时进行自后向前和自前向后的搜索，设计出一个有效的算法。相对已有的模式匹配算法，此算法在增加一定内存开销和多构造一个反向自动机的时间开销下，检索时间将近减少一半。通过实验测试，该算法使Snort入侵检测系统的效率有了大大的提高。关键词：Snort；入侵检测；模式匹配随着X络应用的增多，X络数据流量不断增大，这对基于X络的Snort入侵检测系统的数据检测能力有了更高的要求。一般采取简单方式，更改Sno

2、rt的配置设置，让其丢去部分X络数据包，只检测部分数据包来进行判断。这种做法是在牺牲一定X络数据判断正确率的条件下，提高Snort入侵检测系统的能力。在X络安全要求越来越高和数据流量越来越大的情况下，这种方法常常达不到要求。在Snort入侵检测系统中，影响其效率的主要部分是模式匹配的检测。提高模式匹配算法的效率，对整个入侵检测系统的效率提高起着非常关键的作用。　　模式匹配是指：设有给定的两个串T和P，长度为n的文本字符串T=T[1]T[2]……T[n]，长度为m（m<<n）的模式字符串P=P[1]P[2]……P[m],看T中是否存在长度为m的字串P。通常T的长

3、度远远大于P的长度，若在T中找到等于P的子串，匹配成功，否则匹配失败。模式匹配算法有单模式匹配算法和多模式匹配算法两种。单模式匹配算法中典型的算法有BM算法，多模式匹配中典型的算法有AC算法。文献[1]中提出了一种类似于AC和BM的算法，即：AC-BM混合算法。该算法根据包过滤规则前缀共同信息较多的特点，采取自后向前的搜索，在速度上有较明显的优势[2]。　　我们在AC-BM算法中引入反向有限自动机，让搜索从正向和反向同时进行，可以使检测时间减少到一半。1.算法简介　　AC-BM算法是在AC算法的基础上，结合BM算法的跳跃思想，产生的一种组合算法。AC-BM算法包括三个主要

4、部分：为给定的模式串集合构造一个AC自动机；计算给定字符串集合的移位函数；利用AC自动机和移位函数扫描对象文本串。其匹配过程如下：　　(1)用要查找的多个模式串集合构建一个模式树，模式树构建是基于字符串的前缀而不是后缀，相同的前缀作为树的根节点，用模式树中最短的模式串右端的字符P[m]和文本串的最右字符T[n]对齐。　　(2)匹配时采取自后向前的搜索方法。字符的比较是从左至右进行的（从模式树的根字符开始向节点方向按层逐个字符进行）。比较之前需要进行预处理，来减少大量不必要的比较。　　(3)模式树移动时同时使用坏字符和好后缀规则移动，坏字符移动：当模式树中的字符与文本串的字

5、符Q不匹配时，将模式树移动到下一个Q出现的位置，让模式树中的Q和文本串中的Q对应，如果字符Q在模式树中不存在，将模式树向左移动模式树的最小字符串长度。好后缀移动：当模式树中的字符与文本串中的字符Q不匹配时，将模式树移动到模式树中最先与文本串部分匹配的下一位置。这里的部分匹配模式树中某字符串的字串，特殊情况是字符串的后缀。在移动过程中一定要保证模式树的移动量不大于模式树中最短的模式串。　　设有模式串集合{BPMRERDO,BPMGYVJVGLOPID,先构建模式串集合的有限自动机，然后将构建的有限自动机（模式串集合中位数最少的模式串右端）和文本串的右端对齐（如图1中字符O（

6、红色）和字符D（红色）），字符比较从有限自动机的根节点开始（如图1中字符B（粉红色）），字符B和字符M不匹配，有限自动机的下一个M（蓝色）出现在深度为3的位置，根据坏字符跳跃，有限自动机向左移动2个字符（如图2所示）。图1AC-BM算法匹配前对齐　　　　　　　　　　　　　　　　　　　　　　　　　图2AC-BM算法移动后2.算法分析　　AC-BM算法是AC算法和BM算法的组合，它聚集了AC算法和BM的优点于一身，AC算法的优点是移动函数、失效函数和模式树的妙用。如果字符串集合中，字符串的最小长度为minl，字符组的最大长度为maxl，要进行匹配正文长度为n，则：时间复杂度在

7、最优情况下为O(n/minl)，在最坏情况下为O(n*maxl)。　　规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系是多模式匹配算法的测试项目。测试项目的结果表明AC—BM算法在上述3项测试中取得了很好的平衡性能。这正是新版的Snort中选用AC—BM算法的重要原因。3.算法改进　　尽管AC-BM算法结合了AC算法和BM算法的所有优点，但它对文本串的匹配比较总得从一端开始到另一端结束，匹配比较速度还有提高的余地。我们应用正、反有限自动机对AC-BM算法进行改进，得到比AC-BM算法更快的匹配算法。3.1反向有限自