1、 本科 毕业 设计 (论文 ) （二零 届） 入侵检测系统模式匹配算法研究 所在学院 专业班级 计算机科学与技术 学生姓名 学号 指导教师 职称 完成日期 年 月 摘要： 作为网络安全的最后一道防线，入侵检测系统的作用有着不可忽视的作用。而入侵检测技术中的主要技术难点之一就是模式匹配算法，模式 匹配算法的优劣直接影响着入境检测系统的效率。本文主要对经典的模式匹配算法做简单的介绍包括单模式匹配 BF算法、 BMH算法、 BMHS 算法和多模式匹配 AC算法等。并在对算法的研究上，提出新的算法，以希望提高模式匹配算法的效率。新算法为 NBMHS算法和 NBMHS2 算法。 关键字 ： 网络；入境检
2、测系统；模式匹配算法； BMHS算法； 2 Intrusion detection system pattern matching algorithms Abstract: As the last line of defense network safety, the role of intrusion detection system having the effect that cannot ignore. And the intrusion detection technology is one of the main technical difficulties, pattern ma
3、tching algorithm of pattern matching algorithm fit and unfit quality directly affects the efficiency of entry detection system. This active focuses on the classic pattern matching algorithm simple introduction include single BF algorithm, BMH mode matching algorithm, BMHS algorithm and many pattern
4、matching AC algorithm, etc. And proposeing new algorithm, wanting to improve the efficiency of the pattern matching algorithm. The new algorithm is NBMHS algorithm and NBMHS2 algorithm. Key words: network; Intrusion detection system; Pattern matching algorithms; BMHS algorithms; 3 目 录 1 绪论 . 1 1.1 网
5、络的重要性 . 1 1.2 网络安全技术 . 1 1.2.1 研究的意义 . 2 1.3 入侵检测的发展与现状 . 2 1.4 模式匹配算法的发展与现状 . 3 1.5 本文的工作及结构安排 . 3 1.5.1 本文主要工作 . 3 1.5.2 全文的组织结构 . 3 2 入侵检测系统概述 . 5 2.1 什么是“入侵检测” . 5 2.2 入侵检测系统 . 5 2.3 入侵的常用 方法和特征 . 6 2.4 入侵检测系统发展趋势 . 7 2.5 入侵检测目前存在的问题 . 7 2.6 小结 . 7 3 模式匹配算法的研究 . 8 3.1 入侵检测系统中的模式匹配 . 8 3.1.1 模式匹配
6、算法的背景及原理 . 8 3.1.2 模式匹配算法概述 . 8 3.1.3 单模式匹配算法 . 8 3.1.4 多模式匹配算法 . 9 3.1.5 基于模式匹配系统的特点 . 9 3.2 典型的单模式匹配算法 . 9 3.2.1 BF算法 . 9 3.2.2 BMH算法 . 10 3.2.3 BMHS算法 . 11 3.3 小结 . 13 4 4 需求分析 . 14 4.1 提出问题 . 14 4.2 设计目标 . 14 4.3 开发环境 . 14 4.4 运行环境 . 15 5.1 技术可行性 . 16 5.2 实用性 . 16 6.1 NBMHS算法 . 17 6.1.1 NBMHS算法思
7、想 . 17 6.1.2 NBMHS核心代码 . 17 6.1.3 NBMHS匹配过程 . 19 6.2 NBMHS2算法 . 20 6.2.1 NBMHS2核心思想 . 20 6.2.2 NBMHS2核心代码 . 20 6.2.2 NBMHS2匹配过程 . 22 7.3 算法柱状图 . 27 7.4 算法分析 . 28 7.5 小结 . 28 1 1 绪论 1.1 网络的重要性 目前，计算机已经融入到了生活和生产的各个方面。网络的重要性也凸显出来。文献 1中对网络的重要性做了如下的描述： 1）信息化的时代，任何方面都会涉及到计算机的存储和处理。一旦计算机出现了问题，就会影响到国家的信息安全及
8、一些部门、机构、组织的个人信息、或者商业秘密，对于社会和国家的安全和谐有着至关重要的作用。 2）随着目前计算机的发展，系统中各方面的功能越来 越强的同时也越来也复杂，规模越来越大，存取控制、逻辑连接等一系列不断增加，任何的小的问题都可能导致大问题的发生 1。 3）随着社会的发展，人民对计算机的需求增加了，特别是一些特殊行业，使用计算机显得格外的方便和安全，但是却要要求极高的低出错率和可靠性 2。 4）计算机涉及的范围越来越广，技术、方法都在发展和变化 3。 1.2 网络安全技术 网络安全技术是指运用手段保证传输数据的安全的手段，主要包括物理安全分析技术，网络结构安全分析技术，系统安全分析技术，
9、管理安全分析技术，及其它的安全服务和安全机 制策略 4。 文献 5对目前的网络安全产品的特点做了如下描述： 第一 ,策略的多样化。 第二 ,安全机制与技术的日新月异 ; 第三 ,技术的多样化； 因此 ,网络安全技术是一项内容十分复杂但是却十分重要的工程 .好的网络安全体系的建立 ,需要国家、社会等的合力协作。 文 献 6对目前市 场上的网络安全产品描述如下： 一 .防火墙技术 网络防火墙技术的主要目的在于用来加强各个网络之间访问并对访问进行一定的控制 ,防止外部网络的用户通过一定的以非法手段通过外部网络对内部的资源等一系列的信息进行破坏等 ,防火墙做到了保护内部网络资 源 ,保护内部网络操作环
10、境的特殊网络互联设备 . 二 .病毒防护技术 2 主要内容为在防火墙、网络服务器、群件服务器等上安装病毒过滤软件。用防病毒软件检查和清除病毒。 三 .入侵检测技术 入侵检测系统可分为两类：基于主机和基于网络入侵检测系统。 基于主机的入侵检测系统主要是为保护关键应用的服务器，并进行实时监视可疑的连接、系统日志检查，非法访问的闯入等。 基于网络的入侵检测系统主要为实时监控网络关键路径的信息，对数据包进行分析，并进行一系列的操作。 1.2.1 研究的意义 网络的是否安全，直接关系到了社会的安全和谐 发展。目前的网络正面临着消息不安全的困境，对生产、生活带来的极大的影响，所以如何建好网络的安全显得十分
11、的重要。为止，我们必须在这方面不懈的努力。 1.3 入侵检测的发展与现状 从计算机的发展以来，人们对入侵检测系统的研发就在不断推进的汉中，且在入侵检测的智能化和分布式等方面取得了重大的成就。 近些年，国内外研究了一些典型的入侵检测系统 （ IDS） ，分别为基础主机和基于网络的。国外的主要的产品有： NetRanger； RealSecure。 文献 7对目前的 入侵检测系统做了如下描述： NetRanger是思科 公司的。它主要分为两部分：监测网络包和发告警的传感器，以及接收并分析告警和启动对策的控制器。主要特点为： 1、高性能。速度在以往的入侵检测系统上得到了巨大的发展。 2、易组合。控制
12、器程序可以综合多站点的信息并监视散布在整个互联网网上的攻击。 3、综合考虑。检测问题时不单观察单个包的内容，而且还根据上下文进行综合判断，即从多个包中得到线索。 文献 8对目前的 RealSecure做了如下描述： ISS RealSecure 是一种包含控制台、网络引擎和系统代理三个部分的实时监控软件。它是对 C类网段的内容进行分析 ，抓取数据包，分析包头和数据段内容，与规则库中定义的事件进行匹配，若匹配，则作出相应的反应。 RealSecure对事件反应的处理是多样的，且及时有效。用户可设置的响应方式包括通3 知主控台、中断连接、记录日志、实时回放攻击操作、通知网管等等。 国外的主要的产品
13、有：紫光网络的 UnisIDS；重庆爱思软件技术有限公司的 ODD_NIDS；上海金诺网络安全技术发展股份有限公司的 KIDS。 文献 9对目前的 UnisIDS做了如下描述： UnisIDS 主要包括管理中心 Admin、基于网络的入侵检测引擎 Network Agent 和基于主机的入侵检测引擎 Host Agent(即将推出 )三个部分，用户可根据自己的不同需求选择相应的模块，实时监测黑客的入侵并对入侵进行报警、响应和防范的入侵检测系统，它实现了基于主机检测功能和基于网络检测功能的无缝集成。它主要是对系统事件和网络上传输的数据进行监视对进行分析，如果发现入侵行为和异常数据包，立即报警并做
14、出响应，将安全风险降低，有效的保护系统的资源和数据。 1.4 模式匹配算法的发展与现状 模式匹配时指在目标文本串检索子串的过程，其中字串成为模式。目前字模式匹配算法 10分主要为多 模式匹配算法和单模式匹配算法。 在长久的发展过程中，已经有了一些经典的算法，例如 多模式匹配算法主要有 AC算法、WM 算法等；而单模式匹配算法主要有 BF 算法、 KMP 算法、 BM 算法及其一些改进算法（ BMH算法和 BMHS算法等）。 随着黑客技术的提高，描述攻击行为的特征数目急剧上升，模式匹配算法的效率己成为误用检测技术的瓶颈，直接影响系统的实时性能。模式匹配算法是基于特征匹配的入侵检测系统中的核心算法
15、，直接决定了入侵检测系统的性能。因而，如何改进模式匹配算法，提高检测效率，是目前 IDS研究的重点之一。 1.5 本 文的工作及结构安排 1.5.1 本文主要工作 本文对入侵检测系统及其模式匹配算法进行介绍。提出了模式匹配算法在入侵检测系统中的重要性。根据目前已有的匹配算法为基础，考虑各种算法的性能并进行了详细的设计，最后提出了基于 BMHS 算法的改进算法 NBMHS算法和 NBMHS2算法，算法的目的在于改进模式匹配算法的效率，提高了模式匹配的速度。 1.5.2 全文的组织结构 本文的主要内容安排如下： 第一章 绪论。介绍了本文的研究背景，模式匹配在入侵检测技术研究的现状及本文研4 究的内
16、容和意义。 第二章 入侵检测技术的概述 。主要为阐述入侵检测的概念、系统分类及主要技术，并简要介绍和分析现有的入侵检测技术。 第三章 入侵检测中模式匹配算法的介绍。概略介绍 BF 算法， BM 算法， BMH 算法及 BMHS算法原理和代码实现。 第四章 需求分析。分析目前对于匹配算法的需求。 第五章 可行性分析。分析算法设计的可行性。 第六章 详细设计。在详细分析各类算法的优劣性的基础上，设计 NBMHS算法和 NBMHS2算法，详细介绍该算法的设计思路和实现细节。 第七章 实验测试。通过代码实现，尝试使用模式串的各种情况进行测试，比较算法的性能。 5 2 入侵检测系统概述 2.1 什么是“
17、入侵检测” 文献 11中对入侵检测做了这样的描述： 入侵检测（ Intrusion Detection）顾名思义就是对入侵行为的检测。它主要通过收集和分析网络行为、安全日志、审计数据、其它网络上可以获得的信息以及计算机系统中若干关键点的信息，去检查网络或系统中是否存在违反安全策略的行为和被攻击的迹象，并作出相应的反应。 入侵检测是一种积极主动地安全防护技术，它提供了对内部攻击、外部攻击和误操作的实时保护，做到在网络系统受到危害之前对入侵进 行拦截和响应。因此被认为是防火墙之后的第二道安全闸门，在不影响网络性能的情况下能对网络进行监测。 入侵检测通过执行以下任务来实现： 1、监视、分析用户及系统
18、活动：通过对端口等的数据包的检测和分析。 2、审计：对系统中存在的问题或者构造中的弱点进行分析和审计。 3、报警：如果检测到已知的进攻活动模式，则发出相应的系统报警； 4、分析：对网络或主机的异常行为模式进行统计分析。 5、评估完整性：对系统和重要的数据文件进行评估。 入侵检测是防火墙的补充，帮助系统在应对网络攻击中，提高安全能力。从计算机网络系统中的若 干关键点收集信息，并分析这些信息，查看网络中是否有违反安全策略的行为和遭到袭击的迹象。 2.2 入侵检测系统 入侵检测系统 12是一种对网络传输进行即时监视，在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。 IDS是一种积极主动的安全防护技术。 James P. Anderson 13于 1980年的计算机安全威胁监控与监视第一次详细阐述了入侵检测的概念 ;提出计算机系统威胁分类 ;提出了利用审计跟踪数据监视入侵活动的思想。 随后，在 1990年，加州大学戴维斯分校的 L. T. Heberlein等人开发出了 NSM(Network Security Monitor)系统。将网络流作为审计数据的来源。 下图为入侵检测系统系统流程图。
