基于Snort入侵检测系统模式匹配改进算法研究

1、基于Snort入侵检测系统模式匹配改进算法研究    摘 要：网络技术的应用已经从传统的小型业务系统逐渐扩展到大型的关键业务系统中，但是在浩瀚的 Internet 网络中，系统容易受到外界的攻击与破坏，信息被窃取和修改等网络安全问题越来越严重。研究现有的 snort 入侵检测系统算法，并进行优化改进，使其在实际应用中提高信息安全防范能力。关键词 ：网络入侵检测 ；Snort ；BM 算法 ；Wu-Manber 算法1 入侵检测技术的现状自从计算机网络诞生以来，人们对网络安全的保护最传统的方法就是防火墙技术，但是防火墙只是一种被动防御性的网络安全工具，由于

2、网络日趋复杂化，传统防火墙是不足以满足如今复杂多变的网络安全问题。入侵检测从二十世纪八十年代产生以来，它就受到了各界人士的密切关注。它是一种积极主动的安全防护技术，其核心在于它的检测引擎，如何实现高效快速的检测是入侵检测技术的一个重要研究重点。目前入侵检测技术主要分为两大类，分别是基于异常的入侵检测和基于规则的入侵检测。其检测算法种类繁多，诸如专家系统、模式匹配、数据挖掘、统计方法以及免疫学等，其中模式匹配算法具有较高的时间效率的优点，人们一直关注并研究如何能提高模式匹配算法的效率，模式匹配算法的发展方向就是提高算法的平均性能和较少资源消耗，其主要方法就是在实际的匹配过程中设法减少实际匹配的次

3、数，同时设法将部分匹配算法移植到硬件中或在并行的体系结构下实现，从而减少匹配所消耗的时间和空间1。2 Snort 工作流程分析Snort 是一个用 C 语言编写的轻量级开放源代码的软件，它是目前入侵检测系统中最主要的工具，现已被广泛的安装和使用。它有很多有用的功能 ：数据包嗅探、数据包记录、入侵检测等。其工作原理是基于共享网络上的原始网络传输数据，通过分析所捕获的数据包，将这些数据包与 Snort 规则特征库进行模式匹配来检测异常行为，发现入侵行为进行报警，并将报警信息记录以便进行分析。Snort 系统工作流程如图 1 所示。Snort 从体系结构上看，它充分考虑了扩展的需求，大量使用了插件机

4、制 ；从功能模块上看，各个模块功能清晰、相对独立、设计合理 ；从检测机制上看，它不仅具有基于规则的误用检测方法，而且还有基于异常的检测方法 ；从编码上看，具有很好的设计风格和详细的注释，易于理解。Snort 可以执行几大简单功能，如果我们要更深地去了解Snort 的结构并对其进行配置，它就可以实现强大的功能，Snort 功能的强大主要体现在其拥有重要的功能模块。这些模块主要包括 ：主控模块、解码模块、规则处理模块、预处理插件模块、输出插件模块等等2。具体模块的性能和要求参照 Snort 使用说明，这里不再赘述。3 Snort 系统中模式匹配算法Snort 工具本身提供了多种模式匹配算法，比如

5、Boyer-Moore 算法、AC 算法以及 Wu-Manber算法等，Snort 早期版本的系统检测引擎主要采用单模式 BM 模式匹配算法，随着网络流量的不断增加，现在的版本多采用多模式匹配算法来加快系统的匹配速度，下面对几种比较常用的快速算法分别进行分析。3.1 单模式 Boyer-Moore 算法分析BM 算法3归类为一种精确、单模式匹配算法，它是利用启发式策略，它以减少算法时间来提高匹配效率。算法描述为 ：模式串记为 P，文本串记为T。左对齐 P 与 T，把模式串与文本串从右向左开始匹配，如果 Pi=Ti，就同时向左挪一个位置再比较，否则就要滑动 P 进行重新对齐，模式串就要向后滑动。

6、移动距离时要对模式串 P 定义一个滑动距离函数 dist，dist 函数的具体定义如图 2 所示。情况一 ：根据算法描述，开始比对位不匹配，即从右向左比较时，第一个字符不匹配，而且这个未匹配上的字符在 P 中不存在，那么 P 可以直接右移模式串长度个单位，如图 2 中 j 与 z 不匹配，且z 在 P 中不存在，那么我们可以把 P 右滑 4 个单位，如图 3 所示。情况二 ：根据算法描述，开始比对位也不匹配，但这个未匹配上的字符串在 P 中存在，如果有多个，那就找最靠右的那个与模式串 P 中相同的字符串直接对齐，如图 3 中 2 与 j 不匹配，但 2 存在于 P 中，右移 P 使得两个 2

7、对上，移动后如图 4 所示。情况三 ：若 T 与 P 有部分已经匹配上，且已经匹配上的部分在 T 中后其他地方也存在，那么就将P 右移，直接将已匹配部分对齐即可，这里可以说是 BM 算法中的好后缀思想，如图 5 所示。BM 算法是目前基于主机的入侵检测系统应用中最为常用、效率较高的单模式匹配算法之一，进行模式串匹配时是从右到左，并且用好后缀和坏字符两种启发方式来进行智能启发跳跃，在基于主机的入侵检测系统中能够发挥较好的作用。3.2 多模式 Wu-Manber 算法分析在多模式串匹配算法中，模式串数量越多 , 模式串后端出现相同的概率也相应增大，根据 Wu-Manber 算法中 SHIFT 表描

8、述可以看出，模式串的移动距离也就减小，从而模式匹配算法效率就大大降低。Wu-Manber 算法4是一种快速实用的多模式串匹配算法，目前主要是用在基于网络的入侵检测系统中，它是借鉴单模式串 BM 算法的一些思想构造出来的，Wu-Manber 算法采用字符块 B(B 是字符块的长度 ) 扩展坏字符移动规则来解决这个问题，同时用散列表来筛选匹配阶段应进行匹配运算的模式，从而减少算法匹配时间，提高运行效率5。Wu-Manber 算法首先对模式串进行预处理，也就是我们熟知的在预处理阶段建立三个表格 ：SHIFT表 ,HASH 表和 PREFIX 表。SHIFT 表存储着字符集中所有字符块在模式串中出现时

9、的移动距离，HASH 表用来存储块尾字符散列值相同的模式串的值，REFIX 表用来存储块尾字符散列值相同的模式串的首块字符散列值，匹配过程很简单，就是利用这三个表来完成文本的扫描和寻找，在计算匹配移动距离时有以下两个原则6：(1) 如果窗口中的字符块 B 不出现在任何模式串中，则利用计算公式 SHIFTh=m-B+1，其中，h 为字符块 B 的 hash 值。其中 B 取决于最短模式串的长度和模式串个数，字符块 B 通常取 2 或3，m 是模式的最短长度，SHIFT 的移动距离是计算每个块字符与匹配窗口内模式串串尾的距离。(2) 如 果 字 符 块 B 出 现 在 某 些 模 式 串 中 ,而

10、且在所有模式串中的最右出现位置为 l，则SHIFTh=m l。算法匹配步骤如下 ：1) 选取所有模式串中最短的模式串的长度记为m ；2) 构建 HASH 表，值记为 HASHh ；3) 构建 PREFIX 表，值记为 PREFIXh ；4) 检查 SHIFTh 的值，如果 SHIFTh>0,将窗口向右移动 SHIFTh 大小位置 SHIFTh=0，则进入第 5) 步进行进一步验证 ；5) 对符合 HASHh P<HASHh+1 的每一个 p 值 , 检验是否存在 PREFIXp=PREFIXh。如果相等，那么模式串和文本串匹配成功。4 改进的 Snort 模式匹配算法4.1 改进的

11、 Boyer-Moore 算法分析通过对 BM 算法的分析，发现它在基于主机的入侵检测系统中的应用还是有一些不足 ：(1) 仍旧存在重复的比较 ；(2) 如果模式串只有一个字符，那么它和 BF 算法就没有区别 ；(3) 随着匹配规则的增多，多次训练的话效果越来越不明显。现在对 BM 算法进行如下改进 ：假如把模式串的整体长度作为一个块单位，一块一块进行比较，就可以按如下方法改进，首先还是比较文本指针所指字符和模式的最后一个字符，如相等再比较前一个字符，无论文本中哪个字符造成了匹配失败 , 现都将由文本中和模式最后一个位置对应的下一个字符之后向右的滑动。例如 , 文本串 T 为“fatefine

12、gwxcicl”，模式串 P 为“wxcicl”。若仍用 BM 算法进行匹配的过程如图 6 所示，如用 BM原算法进行匹配如下 ：说明 ：第一次，i 与 l 不匹配 , 但 i 存在于模式串中 , 向右滑 2 个字符使两个 i 对齐。第二次，e与 l 仍不匹配，但 e 不存在于模式串中，则向右滑6 个字符的距离。第三次，指针 =14，dc=1，向右滑 1 个字符，匹配成功。接下来看 BM 算法的改进 ：由文本串和模式串最后一个位置对应的字符的下一个字符做启发向右滑动。其作用在于在每次匹配失败后，把模式向右滑动位数又会增大，减少重复比较次数。示例如下 ：同样把“fatefinegwxcicl”作

13、为文本串 T，“wxcicl”作为模式串 P，用改进的BM 算法匹配过程如图 7 所示。图 7 改进 BM 算法在匹配过程中，第一次用文本串末尾 i 的下一个字符 n 做启发，n 在模式串中不存在，那么就将模式串向右移动 6+1 个位置，第二次再用文本串的第 14 位的 c 做启发，因为 c 存在于模式串中，但上例中模式串有多个 c，取模式串最靠右的那个与文本串中的 c 对齐，匹配成功。通过示例可以看出，本文提出的改进的 BM 算法比原算法比较次数提高了一次，从而提高了模式匹配的速度。4.2 改进的 Wu-Manber 算法分析通过分析Wu-Manber 算法，可以看出以下不足：(1) 随着模

14、式串数量的增加，许多模式串所拥有相同后缀的概率也会增加，即所构建的 HASH 表相应表项内的指针所指向的模式串链表长度增加，从而增加查找 PREFIX 表的次数，这样必然使匹配过程需要更多的比较次数。(2) 如果模式串最小长度 m 的值很小，则移动距离的值也就不可能很大，对匹配效率也有很大影响，从而影响算法性能。改进的 Wu-Manber 算法 ：1) 改进 Wu-Manber 算法的思想通过对 Wu-Manber 算法的分析，由于 Wu-Manber 算法中 PREFIX 表中存储的是模式串前缀hash 值，HASH 表中存储的是模式串后缀模式串的 hash 值，在这种情况下 PREFIX

15、表与 HASH表功能类似，因此，在改进的 Wu-Manber 算法中可以取消 PREFIX 表的构建，那么修改 HASH 表的结构，将其分成两个区。2) 改进 Wu-Manber 算法的设计步骤(1) 首先选取模式串中最小模式串的长度 m ；(2)确定 B 的值 ,B 的值取 2 或 3 ；(3) 构建 SHIFT 表 ：与 Wu-Manber 算法的 SHIFT 表构建方法相同 ；(4)构建 HASH 表 ：这一步很关键，现在把 HASH 表分成左右两个半区，左半区存储原算法中的 hash 值，右半区用来存储原算法 PREFIX 表的值。3) 改进 Wu-Manber 算法的匹配过程(1)

16、计算 SHIFT 表。(2) 计算当前文本窗口的前缀和后缀，将其hash 值分别存储在 HASH 表的左右半区。(3) 整体开始匹配从左向右，根据 SHIFT 表进行扫描，匹配从文本串左端的第 m 个字符开始，对模式的匹配从右向左进行，每次扫描字符块 B 个字符。如果移动距离大于 0，则将模式串向后移动SHIFT 表所指示值的距离，如果移动距离等于 0则转入 (4)。(4) 查看此后缀是否在 HASH 表的左半区，如果存在 , 就再查找 HASH 表的右半区，查看右半区是否有与其匹配的字符串，如果有则完全匹配，如果没有与其匹配的字符串，说明没有模式串满足这样的条件，则返回 3)，直到比较结束。

17、如此看来，改进的 Wu-Manber 算法比原来省去了 PREFIX 表的构建，它是通过把 HASH 表分成左右半区，代替 PREFIX 表的功能，从而节省系统开销空间，提高了算法的查找匹配效率，举例分析改进的 Wu-Manber 算法如下 ：假设在文本串“Each of us will have abetter tomorrow”中匹配模式串 have 和 better。取 B=2，匹配步骤如下 ：步骤 1 ：计算 SHIFT 表。计算每个块字符与匹配窗口内模式串串尾的距离，即当该块字符在文本中出现时的转移距离。其他未出现在匹配窗口内的块字符的 SHIFT 表值均为 m-B+1=4-2+1=

18、3。SHIFT 表如表 1 所示。步骤 2 ：计算 HASH 表。( 左半区存储原算法中 HASH 表的值，右半区存储原算法中 PREFIX表的值 ) 如表 2 所示。步骤 3 ：算法匹配过程 ：文本串为“Each ofus will have a better tomorrow”首先从右向左扫描文本串的前端的 4 个字符，因为取 B 为 2，就通过此 4 个字符的后 2 位来查找 SHIFT 表，发现ch 在 SHIFT 表的移动距离为 3，那么就向后移动3 个距离，接下来考察 of，发现 of 在 SHIFT 表的移动距离也为 3，以此往下匹配，直到发现 ve的移动距离为 0，转入 HASH 表的左半区，发现有 have，然后再计算 have 在 HASH 表右半区的hash 值，发现也有 have，因此判断完全匹配，剩余文本匹配也即如此。5 结论本文分别对 Snort 系统中模式匹配的算法进行举例分析改进，通过对改进算法与原算法的匹配过程对比分析，明显减少了匹配次数，改进了算法效率。通过实验证明，它们可以在入侵检测系统中能够发挥更好的作用。参考文献：1 何一凡 . 入侵检测引擎的设计研究 D. 杭州 ：浙江大学 ,2006.2 马 伟 华 , 刘 玉 梅 , 叶 飞 , 杨 旭 东 . 一 种 改 进 的Wu-Manber