1、 本 科 毕 业 论 文 BM 算法的研究和改进 及其 在 Snort 系统 中的应用 Research and Improvement on BM Algorithm And its Implementation in Snort System 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年 月I 摘 要 目前，基于误用的入侵检测系统主要实现方法是基于模 式匹配技术。高效的模式匹配算法对于基于特征的入侵检测系统来说非常重要， 它 直接影响着检测系统的准确性和实时性。提高字符串匹配的效率就能提高整个入侵检测系统的效率。学者们已提出大量模式匹配算法
2、 ,如 Knuth等人构造出 KMP算法 、 Boyer等人于 1977年设计出 BM算法 。 在这些常用的字符模式匹配算法中 , KMP和 BM算法是其中较为著名的两种算法。 Snort是一个轻量级的 基于特征的 网络入侵检测系统 。 本文 分析了 Snort的 体系结构 和工作流程，对 Snort中使用 的 BM字符 串 匹配算法进行深入研究 ，并 调研了 各种 已有的 BM改进算法。 在深入理解其算法思想的基础上， 用 C语言将其实现，充分进行 实验比较和理论分析， 最终设计了 本文的 新 改进算法。 该算法分情况使用坏字符和好后缀的策略和增加 模式串的末字符 唯一性的 判断，可达到较高
3、 的优化率。 实验结果表明， 与原算法相比， 改进后的算法能有效加快 模式 匹配速度。 最后实现在 Snort系统中的应用， 从而 提高 Snort的 检测 效率 。 关键词： 入侵检测 ； Snort 系统； 模式 匹配算法； BM 算法 ； II Abstract Nowadays, the implementation of misuse-based intrusion is based on pattern match technology. High-performance pattern match algorithm is significant for signature-ba
4、sed intrusion detection system, which influences the accuracy and real time of intrusion detection system directly. As a result, improvement of pattern match algorithm can improve the efficiency of intrusion detection system. At present, scholars have advanced many pattern matching algorithms. For e
5、xample, Knuth and his team created KMP algorithm, and Boyer and his team worked out BM algorithm in 1977. Among all the usual pattern matching algorithms, KMP and BM algorithm are relative well-known. Snort is a lightweight signature-based intrusion detection system. This thesis analyses the archite
6、cture and procedure of Snort, studies the BM algorithm applied in Snort, and researches different improved BM algorithms advanced by others. Based on the deep understanding of each improved BM algorithm, this thesis implements them by C language. Through experiment comparison and theoretical analysi
7、s, this thesis designs own improvement BM algorithm, which adopts the strategy of dividing cases at using Bad Character rule and Good Suffix rule with the judgment of unique last character. Experiment shows that compared with old algorithm, the improvement algorithm can quicken pattern match. After
8、implementing in Snort system, the efficiency of detection engine can be improved. Key words: Intrusion Detection; Snort System; Pattern Matching Algorithm; BM Algorithm; III 目 录 第一章 绪论 . 1 1.1 引言 . 1 1.2 论文组织结构 . 2 第二章 系统相关定义概述 . 3 2.1 入侵检测 . 3 2.2 入侵检测系统 . 3 2.3 SNORT 简介 . 6 2.3.1 Snort 的发展历程 . 6 2
9、.3.2 Snort 的体系结构 . 6 2.3.3 Snort 的工作流程 . 9 2.4 模式匹配 . 11 2.5 本章小结 . 12 第三章 BM 算法 . 13 3.1 BM 算法的核心思想 . 13 3.2 BM 算法的匹配规则 . 14 3.2.1 坏字符规则（ Bad Character） . 14 3.2.2 好后缀规则 (Good Suffix) . 15 3.3 BM 算法分析 . 16 3.4 本章小结 . 17 第四章 现有的 BM 改进算法 . 18 4.1 BMH 算法 . 18 4.1.1 BMH 的提出 . 18 4.1.2 BMH 与 BM 的比较 . 18
10、 4.1.3 好后缀规则（ Good Suffix）的分析 . 19 4.1.4 BMH 算法分析 . 22 4.2 BMHS 算法 . 23 4.2.1 BMHS 算法的提出 . 23 4.2.2 BMHS 与 BM 的比较 . 24 4.2.3 BMHS 算法分析 . 24 4.3 复化的 BM 算法 . 26 4.3.1 复化的 BM 算法的提出 . 26 IV 4.3.2 复化的 BM 算法与 BM 算法的比较 . 28 4.3.3 复化的 BM 算法分析 . 30 4.4 本章小结 . 30 第五章 本文的 BM 改进算法 . 32 5.1 算法的设计 . 32 5.2 改进算法与
11、BM 算法的比较 . 33 5.3 改进算法与已有算法的比较 . 34 5.3.1 改进算法与 BMH 算法的比较 . 34 5.3.2 改进算法与 BMHS 算法的比较 . 35 5.3.3 改进算法与复化的 BM 算法的比较 . 35 5.4 改进算法的分析 . 36 5.5 本章小结 . 38 第六章 算法在 Snort 中的应用 . 39 6.1 部署 Snort . 39 6.2 Snort 源码的修改及运行 . 42 6.3 本章小结 . 44 第七章 总结与展望 . 45 7.1 论文总结 . 45 7.2 工作展望 . 46 参 考文献 . 47 致 谢 . 49 V Cont
12、ent Chapter 1 Introduction . 错误 !未定义书签。 1.1 Background .错误 !未定义书签。 1.2 The Structure of this Thesis .错 误 !未定义书签。 Chapter 2 System Related Concepts Outline . 错误 !未定义书签。 2.1 Intrusion Detection .错误 !未定义书签。 2.2 Intrusion Detection System .错误 !未定义书签。 2.3 Snort .错误 !未定义书签。 2.3.1 General Knowledge of Snor
13、t .错误 !未定义书签。 2.3.2 Architecture of Snort.错误 !未定义书签。 2.3.3 Procedure of Snort .错误 !未定义书签。 2.4 Pattern Match .错误 !未定义书签。 2.5 Summary .错误 !未定义书签。 Chapter 3 BM Algorithm . 错误 !未定义书签。 3.1 The Core Idea of BM Algorithm .错误 !未定义书签。 3.2 Match Rules.错误 !未定义书签。 3.2.1 Bad Character .错误 !未定义书签。 3.2.2 Good Suff
14、ix.错误 !未定义书签。 3.3 Analysis of BM Algorithm .错误 !未定义书签。 3.4 Summary .错误 !未定义书签。 Chapter 4 Existing Improved BM Algorithm . 错误 !未定义书签。 4.1 BMH .错误 !未定义书签。 4.1.1 Main Idea of BMH.错误 !未定义书签。 4.1.2 Comparison Between BMH and BM.错误 !未定义书签。 4.1.3 Analysis of Good Suffix . 19 4.1.4 Analysis of BMH Algorithm
15、.错误 !未定义书签。 4.2 BMHS.错误 !未定义书签。 4.2.1 Main Idea of BMHS .错误 !未定义书签。 4.2.2 Comparison between BMHS and BM .错误 !未定义书签。 4.2.3 Analysis of BMHS Algorithm .错误 !未定义书签。 4.3 Complicated BM .错误 !未定义书签。 4.3.1 Main Idea of Complicated BM .错误 !未定义书签。 VI 4.3.2 Comparison between Complicated BM and BM .错误 !未定义书签。
16、 4.3.3 Analysis of Complicated BM Algorithm .错误 !未定义书签。 4.4 Summary .错误 !未定义书签。 Chapter 5 Improved BM of this Thesis. 错误 !未定义书签。 5.1Main idea .错误 !未定义书签。 5.2Comparison between Improved BM and Old BM.错误 !未定义书签。 5.3 Comparison among Existing Algorithms.错误 !未定义书签。 5.3.1Comparision between Improved BM a
17、nd BMH.错误 !未定义书签。 5.3.2 Comparision between Improved BM and BMHS .错误 !未定义书签。 5.3.3 Comparision between Improved BM and Complicated BM错误 !未定义书签。 5.4Analysis of this Improved Algorithm .错误 !未定义书签。 5.5 Summary .错误 !未定义书签。 Chapter 6 Implementation in Snort. 错误 !未定义书签。 6.1 Snort Deployment . 39 6.2 Snort
18、 Coding Modifying and Running .错误 !未定义书签。 6.3 Summary .错误 !未定义书签。 Chapter 7 Conclusions and Further Works . 错误 !未定义书签。 7.1 Summary of this Thesis .错误 !未定义书签。 7.2 Improvements and Further Works .错误 !未定义书签。 References. 错误 !未定义书签。 Acknowledgements . 49 绪论 1 第一章 绪论 1.1 引言 21 世纪是信息的时代 ， 随着计算机技术和电子通信技术特别是
19、 网络 的快速发展和普及 ， 人类已经进入了信息化时代。但是由于计算机网络具有开放性和互联性等特征 ，致使网络容易受到 “ 黑客 ” 、 恶意软件和其他不轨行为的攻击。所以现在的用户面临着日益严重的网络安全问题 ， 网络入侵已经成为 计算机安全和网络安全的最大威胁。为了抵御这些威胁 ， 将它们的危害降低到最低限度 ， 入侵检测技术成为当前的研究重点和热点 1。 一些专门针对 IDS 的攻击使 IDS 产生报警泛洪 ， 消耗系统资源甚至使其瘫痪 。 比如欺骗攻击、崩溃攻击及针对 IDS 的拒绝服务攻击等 。 如果 IDS 因受攻击而停止工作 ， 则其保护的网络将暴露在攻击者面前 。 显然 ， 在
20、研究如何提高 IDS 的检测全面性和准确性的同时也要增强系统的安全性 ， 保证 IDS 在受到攻击情况下能正常工作 。 在入侵检测系统的实现中 ， 关键的部分是检测引擎的实现 。 而在检测引擎的实现中 ， 关键是数据分析模块 。 数据分析模块涉及到两个问题 : （一） 如何描述入侵行为 ；（二）如何 快速准确地检测出入侵行为 .。 文中主要探讨第二个问题 ， 对于基于 特征 的入侵检测来说 ， 模式匹配算法非常重要 ， 它直接影响到系统的准 确性和实时性能 2。 Snort 是一个强大的轻量级的网络入侵检测系统，具有实时数据流量分析和网络 IP 数据包 记录 的能力，能够进行协议分析， 对内容
21、进行搜索 、 匹配，能够检测各种不同的攻击方式，对攻击进行实时报警 3。 进行字符串匹配是一种非常耗时的工作，尤其是现在网络数据流量巨大的情况下。根据实验统计： Snort 在进行检测的时候调用字符串匹配函数所需用的时间占检测时间总时间的 25.2%。 所以 ，高效的字符串匹配算法 对 Snort 来说很重要，提高字符串匹配的效率就能提高 Snort 整个系统的效率 3。 本文对著名开放源码的入侵检测系统 Snort 进行研究 ，并通过改进模式匹配算法改进 Snort 系统。 Snort 中应用的是 BM（ Boyer-Moore） 模式匹配算法，所以本文对 各种 主流的 BM 改进算法进行
22、调查 、研究和比较 。最后 ， 在各种已有改进 算法 的基础上，设计 出一种新的 改进 算法 。 BM 算法的研究和改进及其在 Snort 系统中的应用 2 1.2 论文组织结构 本论文 首先阐述了 BM 算法基本思想，对目前主流的 BM 改进方案，在了解其算法思想的基础上，用 C 语言将它们 实现用于实验比较，记录各个算法在指定长度的字符串下匹配次数和消耗 时间，并进行实验结果 比较和理论分析；在研究各种已有改进算法的基础上，设计出 一种 新的 BM 改进 算法， 且通过实验验证该算法的效率，并在 Snort 系统中实现，验证该算法的可行性 。 论文具体安排如下： 第一章 揭示当前用户面临的
23、严重的网络安全问题，并强调入侵检测系统在当今网络中的重要性，而入侵检测系统中的关键部分是检测引擎，提高检测引擎的效率尤为重要，优化模式匹配算法便是有 效手段之一 。 第二章 阐述入侵检测和入侵检测系统的概念，对 Snort 的体系结构和工作流程作 简要介绍，引入模式匹配的概念。 第三章 详解 BM 算法， 剖析坏字符和好后缀规则， 分析其算法的效率 。 第四章 列举各种已有的 BM 改进 算法，揭示算法的提出缘由，阐述其 主要思想，展示其与 BM 算法 的实验 比较 结果，分析其优化之处。 第五章 在各种已有改进 算法的基础上，设计了一种 新的 改进 算法 。 通过实验， 将此算法与 BM 算
24、法和已有的改进的 BM 算法做比较。深入分析 该算法的优势所在 。 第 六章 将本文设计 的算法在 Snort 系统 中实现，验证其可 行性。 第 七 章 总结 全文 ， 指出 不足和改进之处。 第二章 系统相关定义概述 3 第二章 系统相关 定义 概述 在叙述算法的研究 和改进 之前， 本章将 介绍一些与入侵检测相关的定义 并进行 Snort 的简介 。 这些 基本 概念和定义的理解 对于模式匹配算法的研究也是非常有必要的 。 2.1 入侵检测 入侵检测是指用来检测针对网络及主机的可疑活动的一系列技术和方法。 它通过收集和分析网络行为、 安全日志 、审计数据、其它 网络 上可以获得的 信息
25、以及 计算机系统 中若干关键点的信息，检查网络或系统中是否存在违反 安全策略 的行为和被攻击的迹象。入侵检测作为一种积极主动地安全防护技术，提供了对内部攻击、外部攻击和误操作的实时保护，在网络系统受到危害之前 拦截 和响应入侵。因此被认为是 防火 墙 之后的第二道安全闸门，在不影响网络性能的情况下能对网络进行监测。 入侵检测系统基本可以分为两大类：基于特征的入侵检测系统和异常行为检测系统。入侵者常具有用软件可以检测到的特征，如病毒。入侵检测系统将检测包含已知入侵行为特征或者异常于 IP 协议的数据包。基于一系列的特征及规则，入侵检测系统能够发现并记录可疑行为并产生告警。基于异常的入侵检测系统通
26、常是分析数据包中协议头部的异常，在某些情况下这种方式要比基于特征的入侵检测系统要更好一些。通常情况下，入侵检测系统在网络上捕获数据包与规则比对或者检测其中的异常 5。 2.2 入侵检测系统 入侵检测系统（ Intrusion Detection System, 简称 IDS） 是一个既能运用静态防御又能进行动态防御的系统 (依据其采用的入侵检测技术所确定 )， 是一种对网络传输进行即时监视，在发现可疑传输时发出警报或者采取主动反应措施的网络安全 设备。它与其他网络安全设备的不同之处便在于， IDS是一种积极主动的安全防护技术。 IDS最早出现在 1980年 4月。该年 ， James P.Anderson为美国空军做了一份题为 Computer Security Threat Monitoring and Surveillance的技术报告，在其中他提出了 IDS的概念 。 1980年代中期， IDS逐渐发展成为入侵
