《Snort入侵检测系统算法研究.docx》由会员分享，可在线阅读，更多相关《Snort入侵检测系统算法研究.docx（3页珍藏版）》请在三一文库上搜索。
1、Snort入侵检测系统算法研究摘要：随着网络流量的增大，Snort入侵检测系统处理数据的能力要求更高，一般可以通过配置Snort设置或者改进其模式匹配算法。利用正向和反向有限自动机，同时进行自后向前和自前向后的搜索，设计出一个有效的算法。相对已有的模式匹配算法，此算法在增加一定内存开销和多构造一个反向自动机的时间开销下，检索时间将近减少一半。通过实验测试，该算法使Snort入侵检测系统的效率有了大大的提高。关键词：Snort；入侵检测；模式匹配随着网络应用的增多，网络数据流量不断增大，这对基于网络的Snort入侵检测系统的数据检测能力有了更高的要求。一般采取简单方式，更改Snort的配置设置，
2、让其丢去部分网络数据包，只检测部分数据包来进行判断。这种做法是在牺牲一定网络数据判断正确率的条件下，提高Snort入侵检测系统的能力。在网络安全要求越来越高和数据流量越来越大的情况下，这种方法常常达不到要求。在Snort入侵检测系统中，影响其效率的主要部分是模式匹配的检测。提高模式匹配算法的效率，对整个入侵检测系统的效率提高起着非常关键的作用。模式匹配是指：设有给定的两个串T和P，长度为n的文本字符串T=T【1】T【2】T，长度为m（m图2 AC-BM算法移动后2 .算法分析AC-BM算法是AC算法和BM算法的组合，它聚集了AC算法和BM的优点于一身，AC算法的优点是移动函数、失效函数和模式树
3、的妙用。如果字符串集合中，字符串的最小长度为minl，字符组的最大长度为maxl，要进行匹配正文长度为n，则：时间复杂度在最优情况下为O(n/minl)，在最坏情况下为O(n*maxl)。规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系是多模式匹配算法的测试项目。测试项目的结果表明ACBM算法在上述3项测试中取得了很好的平衡性能。这正是新版的Snort中选用ACBM算法的重要原因。3 .算法改进尽管AC-BM算法结合了AC算法和BM算法的所有优点，但它对文本串的匹配比较总得从一端开始到另一端结束，匹配比较速度还有提高的余地。我们应用正、反有限自动机对AC-BM算法进行改进，得到比A
4、C-BM算法更快的匹配算法。3.1反向有限自动机反向有限自动机也是根据转移函数、失效函数和输出函数来构建。从模式串集的末尾开始，也是设初始状态为0，由当前状态和读到的下一个字符决定下一状态的边、节点、标签都和正向模式树一样的标注，只是扫描模式串时是从模式串集得末尾开始，反向有限自动机是根据构建模式树的方向来命名的。它的构建和正向自动机的构建基本上一样，不同的是正向自动机是用前缀作为根节点，反向自动机是用后缀作为根节点。设模式串集合BPMRERDO,BPMGYWRDO,BPMVJWRDO，构建模式树过程：同样是用移动函数、失效函数和输出函数，扫描模式串集合的顺序是从模式串的后面开始，向前扫描。构
5、造的反向有限自动机如图3，由于书写的习惯，这里排序是从左到右排序的。图3 反向模式树模式匹配前对模式串集进行预处理，构建反向有限自动机。用上面的反向模式树来模式匹配，设要检查的文本串内容为DISHGLBRWOZBSJMVGLOPID，匹配时把反向有限自动机中最短模式串最左字符P【1】和文本串的最左字符T【1】对齐，匹配时采取从前向后移动模式树，字符比较从模式树的右端开始进行，即按PPP【1】的次序进行比较。遇到不匹配的字符采用BM算法的坏字符规则和好后缀规则来移动反向模式树。匹配过程如图4。图4 反向模式树模式匹配前对齐模式匹配时（如图4所示），字符B（红色）和字符D（红色）对齐，字符比较从模
6、式树的最右端点开始，模式串字符O(粉红色)和文本串字符R（粉红色）不匹配，模式串中下一出现字符R（鲜绿色）为P的位置，即把反向模式树向右移动2个位置。使模式树中的字符R和文本串中的字符R对齐，然后继续匹配。图5 反向模式树匹配移动后3.2反向自动机在AC-BM算法中的妙用把上面介绍反向有限自动机和反向有限自动机的匹配方法加入到AC-BM算法中去，和AC-BM算法结合起来，既在AC-BM算法原来的基础上添加反向有限自动机从前向后移动模式树的模式匹配方法。在预处理时生成两个模式树，一个正向模式树，用来从后向前移动模式树匹配文本串，另一个是反向模式树，用来从前向后移动模式树匹配文本串，从两端对文本串
7、进行模式匹配，这样大大减少模式匹配所需的时间，对于同一文本串而言，采用从两端进行模式匹配的时间比AC-BM算法进行模式匹配的时间减少一半。设模式串集合BPMRERDO, BPMGYWRDO, BPMVJWRDO，要检查的文本串内容为DISHGLBRWOZBSJMVGLOPID，用AC-BM算法对文本串进行模式匹配，同时把反向有限自动机的模式匹配方法引用进来对文本串进行模式匹配，用反向自动机的最短字符串的最左字符B(粉红色)和文本串最左字符D（粉红色）对齐。用正向自动机中最短的模式串的最右边的字符O(红色)和文本串的最后一个字符D（红色）对齐，如图6。图6 双向模式匹配反向自动机和正向自动机与文
8、本串进行字符比较都是从模式树的根节点开始的，如图6中反向模式树的最右字符O(鲜绿色)和文本串的字符R（鲜绿色）开始比较，但是字符O和字符R不匹配，模式树中下一出现字符R（天蓝色）的位置为P【3】，把反向模式树右移动2个位置；正向模式树的最左字符B(蓝色)和文本串的字符M（蓝色）开始比较，字符B和字符M也不匹配，模式树中下一出现M（天蓝色）的位置为P【3】，将正向模式树左移动2个位置，如图7所示。图7 双向模式匹配移动后上面从文本串前后同时进行模式匹配的方法就是改进的AC-BM算法。对于从前后同时进行模式匹配在什么地方匹配结束，值得研究，绝不是文本串的正中间，也不是遍历匹配，解决这个问题，系统应
9、该对匹配过的文本串字符角标作记载，当反向自动机跳转到的字符角标比正向自动机跳转到的角标加上模式串集合中最长模式串位数大时结束匹配，或者正向自动机跳转到的角标比反向自动机跳转到的字符角标减去模式串集合中最长模式串位数小时结束匹配（设正跳转到的角标为N正，反跳转到的角标为N反，模式串集合中最长模式串长度为Lmax，当N反N正+L max,或N正参考文献：【1】 Aho A, Corasick M. Efficient string matching: An aid to bibliographic search. Communications of the ACM, 1975, 18(6): 33
10、3-343.【2】 Jason C C, Staniford S, McAlemey J. Towards faster string for intrusion detection or exceeding the sped of snort. http:/ 唐正军,李建华.入侵检测技术.北京：清华大学出版社，2004.【4】 王成，刘金刚. 一种改进的字符串匹配算法.计算机工程 2006,02:45-49 .【5】 谭汉松，彭诗力.?一种新的快速多模式匹配算法.计算机工程，2005,18:32-36.【6】 万国根，秦志光. 改进的AC-BM字符串匹配算法.电子科技大学学报，2006,35(04):351-355.【7】 王永成，沈州，许一震.改进的多模式匹配算法切.计算机研究与发展，2002, 39(1): 55-60.