搜索
Snort入侵检测系统的算法分析研究摘要：本文对snom入侵检测系统的几种算法进行了介绍和分析，分析了各种不同的算法对入侵检测系统效率的影响，通过改进匹配算法来提高匹配的效率，使检测系统的效率得到了提高。关键词：snort；ac算法；kmp算法；bm算法中图分类号：tp393．08文献标识码：a文章编号：1006-3315(2011)12-177-002随着网络技术的不断发展和网络用户的不断增加，人们得益于网络带来的便利的同时，计算机和网络系统的安全问题也越显突出。目前的网络安全技术如：防火墙、信息加密，作为网络安全的第一道防线远不能有效阻止来自网络上的入侵。针对网络系统攻击的普遍性，攻击手法的复杂性，入侵检测技术也随着网络技术和相关学科的发展日趋成熟，成为网络安全的第二道防线。它对计算机和网络资源上的恶意使用行为进行识别和响应，它不仅可以检测到来自外部的入侵，也可以监督内部用户的未授权活动。一、入侵检测系统snonsnort是由sourcefire公司mar-tyroeseh等人开发的一个基于libpcap的轻量级入侵检测系统，是一个开放源代码的网络安全解决方案，是一个多功能的轻量级网络入侵检测系统。从检测机制上看，它不仅具有基于规则的误用检测方法，而且还有基于异常的检测方法预处理功能。从体系结构上看，它充分考虑到扩展的需求，大量使用了插件机制。从功能模块上看，各个模块功能明晰，相对独立，设计合理。从编码上看，具有很好的设计风格和详细的注释，易于理解的体系结构功能模块设计独立，功能明晰。sno,总体模块图[1]如下图1所示：二、入侵检测系统snort算法1．ac算法aho-corasick[2]算法简称(ac)算法，是多模式检测算法之一，该算法的基本思想是：在预处理阶段，有限自动机算法建立三个函数，转向函数goto，失效函数failure和输出函数output，由此构造一个树型有限自动机。这样模式匹配的处理过程就变成了状态转换的处理过程，由“start”状态开始。在搜索查找阶段，通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。snort应用ac算法时，做了以下改进，使得该算法在运行时具有更好的性能：(1)同时支持确定型和不确定型有限状态自动机；(2)采用线性链表来初始化状态转移表；(3)执行过程中，自动机的状态转移表转换成全矩阵形式，有利于减少内存开销；(4)在每一个状态转移链表中增加一个布尔型变量，来指示状态中是否存在一个匹配的模式。aho-corasick算法在对文本进行搜索的过程中没有跳跃，而是按顺序输入文本yi，无法跳过不必要的比较。因此在实际搜索过程中，aho-corasick算法不是性能最佳的搜索算法，并且有限自动机算法是以空间换时间的经典算法。当模式集较大时可能产生空间膨胀问题，这是因为对于一个总长度为m个字节的模式集，根据有限自动机的构造原理，在最坏的情况下具有m个状态，对于每个状态可能有256种不同的输入。因此描述有限自动机的二维表所需内存空间为256*m字节，当模式集较大时对于内存的要求将会变得很高。2．kmp算法kmp算法的基本思想是每当一趟匹配过程中出现字符比较不等时，不需回溯j指针，而是利用已经得到的部分匹配的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。设s为目标串，t为模式串，设i指针和j指针分别指示目标串和模式串中正待比较的字符，开始时，令i=o，j=0。如果s=tj，则使i和j的值分别增加1；反之，i不变，j的值退回到j=next[j]的位置(即模式串右滑)，然后再对si和tj进行比较。依此类推，直到出现下列两种情况之一：(1)j值退回到某个j=next[j]时，有si=tj，则指针的值各增加l后，再继续匹配；(2)j值退回到j=-1，此时令指针的值各增加1，也即下一次对si+l和t0进行比较。模式匹配kmp算法的时间复杂度为0(m+n)，只有当模式与珠串之间存在许多“部分匹配”的情况下显得比朴素字符匹配算法快得多。但是kmp算法最大的特点就是指示主串的指针不需要回溯，整个过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以便读入边匹配，而无需回头重读。3．bm算法boyer-moore算法(简称为bm算法)是一个著名的字符串匹配算法，它把被匹配的字符串模板(下文简称为“文本串”)与匹配字符串(下文简称为“字符串”)自左向右对齐，并从字符串的最后一个字符开始自右向左进行比较。在用于查找子字符串的算法当中，bm算法是目前相当有效又容易理解的一种，一般情况下，比kmp算法快3--5倍。bm算法的规则如下：1从后向前匹配。我们看到图2中指针是从pat的最后一个字符开始比较的。与英文的单词组成相关，英文单词很多都是采用相同前缀构造的，还有就是一个单词的很多形式前缀也都是相同的，而后缀不同，所以这样可以尽快地排除不符合要求的单词，使指针在string中快速前移。