基于snort的入侵检测系统的研究

摘要

随着网络技术的快速发展和网络应用环境的不断普及，网络安全问题日益突出。入侵检测技术作为一种全新的安全手段，越来越显示出其重要性。随着计算机应用技术和通信技术的发展，互联网已经成为信息传播的重要媒介。计算机网络正在逐渐改变人们的工作和生活方式,对世界经济和文化的发展也产生了深远的影响。然而，网络技术的快速发展以及广泛应用也给人们带来了一定问题。其中尤为突出的就是网络信息安全问题，入侵检测系统正是在这种背景下产生和发展起来的。通过对主机日志或者网络数据的分析，入侵检测系统能够及时的发现入侵行为并进行报警。Snort 是目前最常用的一个强大的轻量级网络入侵检测系统。

首先，本文深入研究了入侵检测技术，概述了入侵检测系统的研究现状，探讨了入侵检测系统的概念、体系架构以及不同分类。并简要描述了入侵检测系统的发展历程.而后着重研究了Snort轻量级入侵检测系统的关键技术,介绍了Snort系统的整体检测流程、插件机制和检测规则等，为项目的设计与开发做了必要的知识储备。接下来明确指出了系统的设计目标和整体设计架构。本文对 Snort 进行了深入的研究，从它的特点、体系结构、工作原理等方面进行了分析。实现了 Snort 入侵检测系统在 Windows 下的构建，利用 MySQL 数据库和日志分析控制台 ACID 来对报警信息进行图形化管理。针对其中规则匹配算法 BM 算法匹配速度比较慢、效率比较低的弱点，采用了一种改进的 Sunday 算法来取代 BM 算法，此算法结合了BM算法和Sunday算法的优点，使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮的匹配，且降低了匹配次数，并将该算法在 snort系统中进行了实现。

关键词：入侵检测 Snort Sunday 算法 BM算法

Abstract

Along with the fast development of the network technology and the universal application of the network environment, the security problem in network is increasingly outstanding. And as a new security means, intrusion detection techniques have displayed its important role. With the development of the computer application technology and communications technology, the Internet has become an important medium of information dissemination. Computer network is gradually changing the way people work and live. On the economic and cultural development of the world it also takes a profound impact. However, the rapid development of network technology and extensive application also gave a series of questions to people, which especially is the network information security. Intrusion detection system is in this context produced and developed. Through the analysis of the host log or network packet, intrusion detection system can prompt the discovery of intrusion and the alarm.

First, this thesis deeply researches the technology of intrusion detection, and explores the concept of intrusion detection system. The thesis discusses the concept of intrusion detection systems, including system architecture and the different categories and a brief description of the development process of intrusion detection system. Then, focuses on key technology research of Snort, which is used as lightweight intrusion detection system, introduces the overall detection system proposes that the system design goals and overall design of the structure. this thesis deeply researches the snort from its characteristic, system structure and working principle. Implements the Snort intrusion detection system in the building under the Windows, use the MySQL database and log analysis console ACID to graphical alarm information management. For the rule matching algorithm BM algorithm matching speed is slow, low efficiency of the weaknesses,so proposed an improved algorithm of Sunday to replace the BM algorithm, this algorithm combines the advantages of BM algorithm and Sunday, so that each can be skipped after a match is not successful as many characters for the next round of matches, and reduces the number of matches, and the algorithm was realized in the snort system.

KEYWORDS: Intrusion detection Snort Sunday algorithm BM algorithm

目录

1 课题研究背景与意义 ............................................... 1

1.1课题研究的背景 ............................................... 1

1.2课题研究的意义 ............................................... 1

2 国内外研究现状 ................................................... 3

3 入侵检测系统概述 ................................................. 5

3.1入侵检测系统介绍 ............................................. 5

3.1.1 入侵检测系统基本结构 ..................................... 5

3.1.2 入侵检测系统工作流程 ..................................... 6

3.1.3 入侵检测系统体系结构 ..................................... 6

3.2入侵检测系统的相关技术 ....................................... 7

3.2.1 snort简介 ................................................ 7

3.2.2 snort体系结构及工作流程 .................................. 8

3.2.3 snort规则 ................................................ 8

3.3 SNORT处理数据包的瓶颈 ......................................... 9

4 基于改进匹配算法的SNORT的设计 .................................. 10

4.1 SNORT的匹配算法及缺陷 ........................................ 10

4.1.1 BM 算法 ................................................. 10

4.1.2 AC 算法 ................................................. 11

4.1.3 Sunday 算法 ............................................. 11

4.2 匹配算法的优化 .............................................. 12

4.2.1 确定首字符串 ............................................ 13

4.2.2 模式匹配过程 ............................................ 14

4.3改进匹配算法的SNORT实现 ..................................... 15

5 实验结果及评估 .................................................. 17

5.1系统平台 .................................................... 17

5.2 实验部署及流程 .............................................. 17

5.2.1 实验部署 ................................................ 17

5.2.2 实验流程 ................................................ 18

5.3 实验结果及分析 .............................................. 20 6 总结与展望 ...................................................... 22

6.1总结 ........................................................ 22

6.2展望 ........................................................ 22

致谢 .............................................................. 23

参考文献 .......................................................... 24

1 课题研究背景与意义

1.1课题研究的背景

随着计算机网络和信息化技术的发展，越来越多的电子商务系统、企业信息化平台建立在互联网上，人们在享受网络带来的资源共享及信息交流的同时，也不得不面对黑客和网络入侵者给网络安全带来的威胁。随着计算机和网络技术的不断普及，越来越多的漏洞被人们发现，入侵者的水平也越来越高，手段变得更加高明和隐蔽。所以，网络中计算机系统的安全问题日益成为人们关注的热点。

入侵检测技术[1]作为一种积极主动的防御手段，已成为当今网络安全体系的重要组成部分。而 Snort 作为一种开放源代码的入侵检测系统[2]已经得到广泛的应用。它采用的是基于规则的网络信息搜索机制，通过对数据包内容进行模式匹配[3]来检测多种不同的入侵行为和探测活动。但是，由于Snort 只按照规则归类的方法进行规则匹配，而且对数据包内容的模式匹配采用的是 Boyer-Moore( 简称 BM) 算法，使得其对规则匹配的重复次数过多，模式匹配效率不高，影响了检测系统的整体性能。随着网络资源逐渐增加、网络流量不断提高以及网络攻击类型变化多端，致使Snort 不能满足网络发展的要求，从而漏掉一些复杂的网络攻击行为[4]，给系统造成严重后果。因此，如何提高 Snort 的检测效率，增强其检测性能己成为入侵检测领域研究的重要内容。

因此，本文试图将规则匹配策略[5]并行化，对于各条件既按照规则本身进行分类，也按照条件分类 ；同时引入横向淘汰方法，如果一个规则中的一个条件为假，那么就不匹配此规则中的其他条件，在模式匹配过程中采用一种改进的匹配算法，从而能有效地减少数据包的匹配时间，提高了基于 Snort 的入侵检测系统的检测效率。

1.2课题研究的意义

论文的选题来源于国家自然科学基金重点项目：基于网络探测的IP网络拓扑[6]发现和性能分析的研究。该项目研究IP网络探测[7]及性能分析技术，包括网络性能、拓扑、无线IP的探测和分析原理及技术、网络性能评价及分析预测技术等。论文主要负责网络入侵检测模块。本文深入研究以开放源代码的形式发行的网络入侵检测系统(NIDS)—Snort入侵检测系统。

面对软件漏洞、内部攻击等网络安全威胁，要想建立完全安全、没有隐患的系统是不可行的，安全不是绝对的，要想提高系统的安全性只能采取一些技术手段来降低风险。传统的安全手段都是集中在“防”上，如在网络边界设置防火墙，防火墙[8]能够具有一定的防范作用，但是防火墙是静态防御，随着攻

击手段的花样迭出，这种传统防火墙的静态防御技术已经没有办法满足需求。首先，黑客能够找到防火墙的后门，进而对内部网络发起进攻；其次，防火墙对于源于网络内部的攻击无能为力；而且防火墙不能实时监测入侵；最后防火墙不能防毒，因此，认为在网络的出口处设置好防火墙就万事皆休的想法是错误的，需要将防火墙与别的安全技术相结合，来建立一种纵深的、动态的防护体系。入侵检测技术是一种主动防御技术，它可以在发生攻击时对攻击行为进行记录，并发出警报消息，甚至可以追踪黑客。入侵检测系统作为整个防护体系的重要部分具有其他安全策略所不可比拟的地位，它能在入侵行为发生前就检测到攻击；在发现攻击行为时，它能将攻击所造成的危害减小到最低；还能将攻击发生时的入侵行为记录下来，并将其作为防范知识加入到策略中，以防止系统再遭受类似攻击。入侵检测系统因其实时性及主动防御的特点，弥补了防火墙的静态防御系统的不足，是网络安全中值得进行深入研究的一个方向。

Snort 入侵检测系统一种著名的开源入侵检测系统，能够有效保护系统信信息安全。目前在全世界已经得到广泛应用。Snort作为一个典型的网络入侵检测系统，将Snort构建于网络中，可在不影响网络性能的情况下对网络进行监测，从而提供对内部攻击、外部攻击和误操作的实时保护。其若干设计原理和实现特点，是目前多数商用入侵检测系统的研发基石。对Snort系统的研究具有较强的商业价值。

本文对 Snort 系统的优缺点的分析研究，利用其开源性和支持插件的优势，针对其对新的入侵行为无法检测，漏报率较高和检测速度较低等问题，在Snort 已有的匹配模式[9]上做了一些改进。 本文提出的在 snort 上应用改进的模式匹配算法，进行网络管理上的应用。如何解决 Snort 的检测速度较低、误报率和漏报率较高以及 Snort 入侵检测系统无法实时动态检测到新的入侵攻击行为等问题，在应对当网络上的数据随着网络应用的变化、攻击手段变化多端及其变种攻击越来越复杂的具有重要的学术意义和实用价值。

2 国内外研究现状

入侵检测系统(Intrusion Detection System)作为目前网络安全体系中的一种动态防范技术[10]最早源于国外，其研究历史可以追溯到上世纪八十年代初。最初的研究动机是由于人们发现计算机系统的审计记录可以用于识别计算机误用，研究人员可以在对威胁分类的基础上改进审计系统以便其具有误用检测功能。这一时期入侵检测系统的研究还处于试验阶段，主要检测手段是对主机日志的分析，大多是为了保护特殊的网络而进行专门的研究和设计，具有很强的局限性，不能广泛的应用到其它网络环境中。

进入上世纪九十年代，随着网络数据包截获和审计数据分析等技术的成熟，关于入侵检测系统的研究进入了快速发展时期，其主要研究方向也从基于主机的入侵检测系统[11]向基于网络的入侵检测系统转移，入侵检测系统的功能及作用也不仅仅局限于对系统日志的分析，而是逐渐增加了监测并分析网络的活动、检查系统漏洞等功能。直到此时，入侵检测系统才开始由早期的实验室产品逐步转型成为商业产品。计算机互联网行业的高速发展使得网络安全问题变得尤为重要，因而越来越多的研究机构和商业组织开始从事入侵检测等安全技术的研究。随着研究人员的增多，一些其他领域的研究方法也逐渐被引入到了入侵检测系统的研究中。

目前入侵检测系统中应用较为广泛的技术包括神经元网络、人工智能、数据挖掘技术[12]等，这些技术的应用使得规则解析和协议分析等入侵检测方法迅速发展和完善起来。入侵检测系统已经能够针对攻击行为做出适当的反应，并且在有效降低误报率的同时能够对未知的攻击行为进行自学习。在入侵检测产品方面，由于对入侵检测技术的研究比较成熟，国外的研究机构已经成功开发出了多个应用于不同操作系统的典型的入侵检测商业产品。这些商业产品通常是基于服务器或网络进行入侵行为检测的，而且大多采用了误用检测模型。国外主要的入侵检测系统商用产品包括CISco公司的NetRanger Iniemctsec而tysystem公司的Realsecure NetworkAssoeiates公司的CyberCop等等。另外就是最著名的开放源码的Snort轻量级入侵检测系统。

国内的研究工作完全在国际研究范畴之内，很多关键技术都在借鉴国外的经验，没有突破性的进展，在遭遇大规模的或者是突发性的攻击行为时，收效甚微。总体来说，我国商用产品采用的技术主要为误用检测技术，并且向分布式系统方向发展，近年来，我国加大了对整个网络安全方向的研究，同时启动了 863 计划，各大高校及研究机构都建立了专门从事网络安全研究的开发团队。总体来说，我国对入侵检测技术的研究还处于初级阶段，技术水平也有待于进一步提高，但是随着人们对网络安全认识的逐步深刻以及国家在这个方向的投入加大，相信用不了多久，我国在入侵检测领域一定能够有所建树。

如今，数据挖掘技术已经渗透于社会各个领域，而且在实际中应用的范例也非常多，但是数据挖掘技术在入侵检测技术中的应用却起步稍晚，时至今日

也只限于尝试探索阶段的实验研究。目前已经有一些研究机构将数据挖掘技术应用于入侵检测中。国内在数据挖掘方面的研究主要是一些高校和研究机构，对其的研究基本还处于产品的研发阶段，不过有很多人提出了比较先进的检测模型和检测技术，例如：浙江大学计算机学院的胡敏等人提出的了实时环境下基于数据挖掘的入侵检测技术。相对于国外大量的商用入侵检测产品,国内对于入侵检测技术研究起步较晚，所以相关产品的商用化程度不高。目前，国内的入侵检测系统商业产品大多是在对Snort系统进行修改的基础上开发出来的。国内主要的入侵检测产品主要有：（1） 绿盟科技生产的冰之眼入侵检测系统；（2） 方正信息安全技术有限公司生产的方正入侵检测系统；（3） 联想网御科技（北京）有限公司生产的联想网御入侵检测系统等等。其中较为著名的产品有北京天融网络安全技术公司的网络卫士系列入侵检测系统，东软的NctEye系列入侵检测系统，中科网威的/天眼0入侵检测系统等。

近些年来，入侵检测的主要创新包括：Forrest 等将免疫原理运用到分布式入侵检测领域；1998 年 Ross Anderson 和 Abida Khattak 将信息检索技术引进到入侵检测。2000 年 2 月，对 Yahoo、Amazon、CNN 等大型网站的分布式拒绝服务（DDos, Distributed Deny of Service）攻击引发了对 IDS 系统的新一轮研究热潮。

.

3 入侵检测系统概述

3.1入侵检测系统介绍

3.1.1 入侵检测系统基本结构

入侵检测系统通常由以下4个部分组成,其基本结构如图3-1所示：

图3-1 入侵检测系统基本结构

（1）事件产生器

事件产生器是入侵检测系统中负责原始数据采集的部分，它对数据流和日志文件等进行追踪，然后将搜集到的原始数据转换为事件，并向系统的其他部分提供此事件。

（2）事件分析器

事件分析器接收事件信息，然后对信息进行分析，判断所接收信息是否为入侵行为或异常现象，最后将判断的结果转变为警告信息。

（3）事件数据库

事件数据库是存放各种中间和最终数据的地方。它从事件产生器或者事件分析器接收数据，一般会将数据进行较长时间的保存。事件数据库可以是复杂的数据库，也可以是简单的文本文件。

（4）响应单元

响应单元根据警告信息做出反应，其可以做出切断连接，改变文件属性等强烈反应，也可以只是简单的报警。

以上4部分只是入侵检测系统的基本组成部分。从具体实现的角度看，入侵检测系统一般包括硬件和软件两部分。硬件设备主要完成数据的采集和响应的实施；软件部分主要完成数据的处理，入侵的判断和响应的决策等功能。

3.1.2 入侵检测系统工作流程

入侵检测系统是一个典型的“窥探设备”，它不跨接多个物理网段（通常只有一个监听端口），无需转发任何流量，而只需要在网络上被动的、无声息的收集它所关心的报文即可。对收集来的报文入侵检测系统提取相应的流量，统计特征值，并利用内置的入侵知识库与这些流量特征进行智能分析、比较匹配。根据预设的闭值，匹配耦合度较高的报文流量将被认为是入侵行为，系统将进行报警或有限度的反击，入侵检测的工作流程主要有以下四步：

（1）信息收集

入侵检测的第一步是信息收集，内容包括系统、网络、数据及用户活动的状态和行为，而且需要在计算机网络系统中的若干不同关键点(不同网段和不同主机)收集信息。

（2）信息分析

信息分析是指对上述四类收集到的有关系统、网络、数据及用户活动的状态和行为等信息，一般通过模式匹配、统计分析和完整性分析三种技术手段进行分析。其中前两种方法用于实时的入侵检测，而完整性分析则用于事后分析。

（3） 信息存储

当入侵检测系统捕获到有攻击发生时，为了便于系统管理人员对攻击信息进行查看和对攻击行为进行分析，还需要将入侵检测系统收集到的信息进行保存，这些信息通常存储到用户指定的日志文件中，同时存储的信息也为攻击保留了数字证据。

（4） 攻击响应

对攻击信息进行了分析并确定攻击的类型后，入侵检测系统会根据用户的设置，对攻击行为进行相应的处理：如发出警报、给系统管理员发邮件等方式提醒用户，或者利用自动装置直接进行处理。如切断连接，过滤攻击者的 IP 地址等，从而使系统能够较早的避开或阻断攻击。

3.1.3 入侵检测系统体系结构

当前，在网络环境中主要存在以下三种入侵检测体系结构:

（1） 基于主机的入侵检测系统(HIDS)

基于主机的入侵检测通常从主机的审计记录和日志文件中获得所需的主要数据源，并辅之以主机的其他信息，例如文件系统属性、进程状态、CPU 和内存的使用情况等，在此基础上完成检测攻击行为的任务。从技术发展的历程来看，入侵检测是从主机审计的基础上开始发展的，因而早期的入侵检测系统都是基于主机的入侵检测技术。其有很多缺点:首先，由于它严重依赖于特定的操作系统平台，所以，对不同的平台系统而言，它是无法移植的。其次，它在所保护主机下运行，将影响到宿主机的运行性能，特别是当宿主机是服务器的情况。另外，它通常无法对网络环境下发生的大量攻击行为做出及时的反应。

（2） 基于网络的入侵检测系统(NIDS)

随着网络环境的普及，出现了大量的基于网络的入侵检测系统。基于网络的入侵检测系统通过监听网络中的数据包来获得必要的数据来源，并通过协议分析、特征匹配、统计分析等手段发现当前攻击行为。

基于网络的入侵检测能够实时监控网络中的数据流量，发现潜在的攻击行为，并做出迅速响应。另外，它的分析对象是网络协议，通常而言是标准化的，独立于主机的操作系统类型，因此 NIDS 一般没有移植性的问题。同时它的运行丝毫不影响主机或服务器的自身运行。

（3）分布式入侵检测系统(DIDS)

进入 20 世纪 90 年代后，出现了把基于主机和基于网络的入侵检测结合起来的早期尝试，最早实现此种集成能力的原型系统是分布式入侵检测系统 DIDS,它将 NSM和 Haystack 组件集成到一起，并采用中央控制台来解决关联处理和用户接口的问题。典型的 DIDS 是管理端/探测器结构，NIDS 作为探测器放置在网络的各个地方，并向中央管理平台汇报情况。攻击日志定时地传送到管理平台，并保存在中央数据库中，新的攻击特征库则能发送到各个探测器上。每个探测器能根据所在网络的实际需要配置不同的规则集。报警信息能发到管理平台的消息系统，用各种方式通知 IDS管理员。现在有人根据此种数据来源混合的方式，称此类系统为“混合型”(Hybrid)系统。最著名的明确体现分布式架构的早期系统为 SRI 的 EMERALD 系统，它明确将分布式检测架构进行层次化的处理，并实现了不同层次上的分析单元，同时提供了开放的 API 接口，实现基本架构下的组件互换功能，这也是处理可扩展性问题的一次有益尝试。后来的 Purdue大学设计并原型实现的 AAFID 系统体现了基于自治代理的分布式架构思想。

3.2入侵检测系统的相关技术

3.2.1 snort简介

Snort系统[13]是一个以开放源代码形式发行的一个轻量级网络入侵检测系统，由Martin Roesch编写，并由遍布世界各地的众多程序员共同维护和升级。直到今天，Snort已发展为一个多平台的强大的网络入侵检测系统。

Snort IDS是一个轻量级的网络入侵检测系统。它运行在一个传感器(Sensor)主机上，负责监听网络数据。Snort能够把网络数据和系统的检测规则进行模式匹配，从而检测出可能的入侵企图。Snort可以完成数据包嗅探、数据包记录、入侵检测及实时发送报警信息。Snort 是一个基于 libpcap 的数据包嗅探器[14]可以作为一个轻量级的网络入侵检测系统 NIDS。这里轻量级的意思是占用的资源非常少，能运行在不同的操作系统上。另外，它还能提供一些以前只有商业NIDS才能提供的功能。Snort系统支持多种系统软硬件平台，如Unix系统平台，当前也已出现基于Windows平台的Snort系统。

3.2.2 snort体系结构及工作流程

Snort由以下几个部分组成:数据包嗅探器、预处理器、检测引擎、报警输出模块,如图3-2所示：

图3-2 snort基本组成

Snort首先利用嗅探器在网络中获取数据包,然后通过预处理插件对数据包进行初步的处理,例如格式处理和基本分类。接着按照规则判断这些数据包是否引入安全问题。如果有，则确定如何处理这些数据包（报警或者保存到日志）。它的预处理器、检测引擎和报警模块都是以插件的形式存在，插件程序按照Snort提供的插件函数接口完成，使用时动态加载，在不用修改核心代码的前提下让snort的代码紧密相关，又保证了核心代码的良好扩展性。

3.2.3 snort规则

Snort 规则是 Snort 完成入侵检测功能必不可少的一部分，它是以文本形式存在的，位于 Snort 目录下，表示的是攻击行为的特征，通过与规则的匹配就可以识别攻击。它根据不同的攻击内容来分组，启动 Snort 时，全部的规则文件会形成一个三维链表。Snort 规则现在发布了有 8000 多条，并且还在不停的扩充中。Snort规则由规则头和规则体组成。规则头描述了本条规则的处理动作（记录或者报警）、数据包的协议类型（TCP、UDP、ICMP、IP等）、源信息（源地址和源端口）及目的信息（目的地址和目的端口）。规则体中是要检测的内容。

Snort规则文件是一个ASCll文本文件,可以用常用的文本编辑器对其进行编辑。规则文件的内容由以下几部分组成：

①变量定义：在这里定义的变量可以在创建Snort规则时使用。

②Snort规则：在入侵检测时起作用的规则,这些规则应包括总体的策略。

③预处理器:即用来扩展Snort功能的插件"如用Portscan来检测端口扫描。 ④包含文件Include Files：可以包括其它Snort规则文件。

⑤输出模块:Snort管理员通过它来指定记录日志和告警的输出。当Snort调用告警及日志子系统时会执行输出模块。

3.3 snort处理数据包的瓶颈

虽然snort功能强大，可移植性极强，跨平台性极佳，扩展性好并且能够支持插件。但是snort入侵检测方法也有很多缺陷并面临着以下问题：

Snort 的检测速度较低，Snort 系统对数据包的处理速度一直是影响其性能的一个重大因素，从其捕获网络的一个数据包开始，中间经过解码、预处理并分析、匹配这个过程需要花费大量的时间和系统资源，当其检测速度达不到网络数据的传输速度的要求时，系统就会出现堵塞现象，甚至被迫放弃部分数据包，这种情况不但造成了系统检测的实效，同时也会给检测系统带来很大的危险，导致系统崩溃。

Snort 的误报率和漏报率较高，误报就是把非入侵行为当作入侵行为，而漏报是没有报告真正的入侵行为。Snort 系统是误用入侵检测系统，它根据系统自身的规则库进行入侵行为的匹配，由于每天都可能有新的攻击方法产生和新漏洞发布，而其系统的规则库却不能及时更新，那么 Snort 就无法检测到新的入侵行为，从而使得 Snort 系统的漏报率大大增加；Snort 入侵检测系统是重要的特征匹配 IDS，Snort 系统对所有与特征匹配的数据包都会发出警报，但是很多合法应用程序产生的流量也会引起其错误的警报。

Snort 入侵检测系统无法实时动态检测到新的入侵攻击行为，Snort 入侵检测的是基于特征库的预先定义好的规则检测的，这就导致了其自适应性能相对较差，当网络上的数据随着网络应用变化时，其特征 Snort 系统预先是不能识别的，这就意味着它不能自适应地修改检测模式。因此，在当今攻击手段变化多端及其变种攻击越来越复杂的情况下，Snort 入侵检测系统的检测就显得捉襟见肘了。

由于 Snort 是利用规则进行检测的，所以首先要根据攻击行为的特征制定规则。数据包嗅探器在网络中是并联的，它的主要功能是对数据包进行捕获并且按照 TCP/IP 协议族的协议对其进行解码。预处理器是指在对数据包模式匹配之前，先对其异常检查和代码转换。预处理器的组成元素是模块，所有模块的作用各不相同，可以根据实际需要对相关插件进行调用或停止。随着预处理器加入到 Snort 中，用户可以根据需要把一些插件很容易的融入到 Snort 系统中，从不同程度上对 Snort 的功能进行了延伸。IDS 的核心部分为检测引擎，它将经过预处理的数据包与规则进行匹配来判定是否有攻击发生，它必须有很高的准确率和很快的速度。所以规则的制定是否准确对 Snort 系统影响很大，其次检测引擎所采用的模式匹配算法如果速度很快的话，就可以大大提高检测引擎的效率。

4 基于改进匹配算法的snort的设计

4.1 snort的匹配算法及缺陷

4.1.1 BM 算法

BM算法[15]是入侵检测系统中应用最广泛的一种单模式匹配算法。Snort 2.0以前的版本主要采用BM算法进行数据包和规则的内容模式的匹配。2.0及以后的版本中BM算法应用的较少，但它是现行版本中多模式匹配算法的基础。

BM算法的基本思想是字符从右到左进行比较，模式串从左到右移动。假设模式串P=p0p1 pm-1,文本串T=t0t1 tn-1。开始时使p0与t0对齐，判断pm-1与tm-1是否相等，如果相等则向左移动判断pm-2与tm-2是否相等，直到全部匹配成功或发现有不匹配的情况出现。当出现不匹配时，BM算法采用坏字符规则和好后缀规则计算模式串右移的距离。右移的距离由两条规则中较大的值决定。对于P在T中位置i处的尝试，也就是比较模式串P=p0p1 pm-1与T中子titi+1ti+m-1是否相等。若前m-j-1次比较成功完成，而在第m-j次比较时出现不匹配，即ti+j+1ti+j+2 ti+m-1=pj+1pj+2 pm-1=u并且ti+j=a，pj=b（a≠b）。在这种情况下根据坏字符和好字符规则如下：

① 坏字符规则：在 p0p1 pj-1中自右向左查找字符 t

i+j出现的第一个位置，若找到则使 ti+j与该字符对齐，若没有找到则将 P 移动到 ti+j后的第一个位置对齐，既使 p0与 ti+j+1对齐，继续匹配。

②好后缀规则：从 pj处开始从右到左查找 u 串，若能找到 u 串并且其前一字符不是 a，则将 P 移动到该 u 串与 T 中已匹配的 u 串对齐的位置。若没有找到这样的 u 串，则在 T 中 u 的后缀中查找与 P 的前缀相同的最长子串 v，若存在这样的串 v，移动 P 使 T 的后缀 v 与 P 的前缀 v 对齐。如果这样的u 串与 v 串均未找到，将 P 右移 m 个字符。即使 p0与 ti+m对齐，继续匹配。BM算法匹配过程如图4-1所示：

尽管 BM 算法在单模式匹配中执行效率较高，但是 Snort 在检测入侵时数据包需要与上千条规则进行匹配，此时需重复多遍执行 BM 算法，制约了系统运行速率。而且BM算法主要利用了正文串的信息 ，对模式串的信息使用的很少，其实模式串的内容信息还可以进行挖掘，如果利用的好，可以在一定程度上提升算法的效率。

图4-1 BM算法匹配过程

4.1.2 AC 算法

Aho-Corasick 算法[16]（简称 AC 算法）是同时搜索多个模式的经典匹配算法。AC 算法利用多个模式串构建一个有限状态模式匹配自动机。自动机是结构化的，每个前缀都可用唯一的状态来标志。当文本中的下一个字符不是模式中预期的下一个字符中的一个时，会出现一条失败链指向那个状态，代表最长的模式前缀，同时也是当前状态的相应后缀。

Snort 应用 AC 算法时，做了以下改进，使得该算法在运行时具有更好的性能。（1）同时支持确定型和不确定型有限状态自动机；（2）采用线性链表来初始化状态转移表；（3）执行过程中，自动机的状态转移表转换成全矩阵形式，有利于减少内存开销；（4）在每一个状态转移链表中增加一个布尔型变量，来指示状态中是否存在一个匹配的模式。

4.1.3 Sunday 算法

Sunday 算法[17]是 Daniel M Sunday 于 1990 年提出的一种比 BM 算法搜索速度更快的算法。该算法的核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行过下一步的匹配，从而提高了匹配的效率。

假设在发生不匹配时 T[i]≠P[j], 1≤j≤M。此时已经匹配的部分为u，并假设字符串u的长度为L。这个时候，我们很显然知道此时的T[L+i+1]肯定要参加下一轮的匹配。并且 P[M]至少要移动到这个位置（即模式串 P至少向右移

动一个字符的位置）。

下面分两种情况讨论（我们只讨论模式串从左向右移动，字符按 P[M]、P[M-1]、 、P[3]的次序从右向左比较的情况。相反的情况可用类似的方法讨论）：

①T[L+i+1]在模式串 P 中没有出现。这个时候模式串 P 移动到T[L+i+1]（包括 T[L+i+1]本身）之前的任何位置，都没有意义。因此，P[0]必须移动到 T[L+i+1]之后的字符的位置。

② T[L+i+1]在模式串 P 中出现。这里所说的 T[L+i+1]在模式串 P中能够出现是指 T[L+i+1]从模式串的右侧，即按 P[M-1]、P[M-2]、 、P[0]的次序查找。如果发现 T[L+i+1]和 P 中的某个字符相同，则记下这个位置，即为 k，1≤k≤M，且 P[k]= T[L+i+1]。此时，应该把模式串 P向右移动 M-k 个字符的位置，即移动到 P[k]和 T[L+i+1]对齐的位置。

按照这种字串移动算法，然后按照字符从右向左的次序匹配。如果完全匹配了，则匹配成功；否则，在进行下一轮的移动，直到正文 T 的最右端结束。该算法最坏情况下的时间复杂度为 O（N*M）。对于短模式串的匹配问题，该算法执行速度较快。Sunday 算法的匹配过程如图4-2所示：

图4-2 Sunday 算法匹配过程

Snort采用了Boyer—Moore字符串匹配算法进行模式匹配。

BM 算法在匹配效率上有一定的缺陷，目前许多算法已经能够在进行模式匹配时，使模式串获得更大的移动距离，提高了匹配效率。下面介绍的一种算法就是建立在对模式串信息分析和利用的基础上实现的。

4.2 匹配算法的优化

通过上述算法分析，根据将要建立的入侵检测系统的实际应用环境的具体情况，决定采用优化的Sunday算法作为入侵检测系统的模式匹配算法。Sunday改进算法的核心思想是：在原Sunday算法之中增加了预处理过程。把原来的模

式串P分成两部分，一部分是首字符串，记作head_string，一部分是尾字符串首，记作foot_string。其中首字符串设为模式串P中的一个最长的真首子串(len(head_string)<len(P))，把它作为新的模式串和正文T匹配，当发生不匹配时，利用Sunday算法移动尽可能远的距离；当匹配时，再用尾字符串foot_string与文本串T相应位置的字符进行匹配，当foot_string匹配失败时，移动head_string到foot_string刚刚匹配失败的位置，继续匹配。当foot_string也匹配成功时，则整个匹配过程完成，匹配成功。

4.2.1 确定首字符串

设模式串为P[1 M]，文本串为T[1 N]，首字符串为head_string。为了要找最长的子串，在初始匹配时，令head_string=P[1 M]作为新的模式串，若不符合最长字串的要求，则再继续尝试head_string=P[1 M-1]， 依此类推。获取head_string串的方法是：设模式串head_string的最右边的元素为head_string[j]，文本串T的T[i]是紧跟在head_string[j]和正文对齐的元素之后的元素。如图4-3所示：

文本T

head_string

图4-3 head_string获取过程

然后用 T [i]依次去匹配head_string[l j-1]， 一旦发现匹配，则将head_string的最后一个元素去掉，生成新的head_string，进入下一轮匹配（T [i-1]依次去匹配head_string[l j-2]）；

如果head_string和T[i]不匹配，则有两种处理方式：

(1)如果T[i]=head_string[j]时，则将串head_string右移j+l个单位；

(2)如果T[i]≠head_string[j]时，则将串head_string右移j+2个位。

如果按照这个规则head_string串一直能移动到正文T的最右端，则成功找到head_string；否则将head_string 的最后一个元素去掉，生成新的head_string，

跳过尽可能多的字符以进行下一轮的匹配，且降低了匹配次数。不考虑算法的预处理过程，主要以匹配过程中所需的匹配次数作为算法的时耗。改进的Sunday算法在最坏的情况下所需的字符比较次数小于2N。这是因为，假设匹配至T[i]时，head_string匹配成功，则T[i]之前的(i-1)个字符最多比较(i-I)次，而其后得(N-i+1)个正文字符每个字符最多会比较2次，1次是匹配foot_string时进行的，1次是foot_string匹配失败后，重新匹配head_string时进行的。

4.2.2 模式匹配过程

确定首字符串head_string后，我们也就得到了尾字符串foot_string，foot_string=P-headstring，接着就可以应用Sunday算法进行模式匹配了。匹配过程如图4-4所示：

假设模式串P为{America}，文本串为{He is from Amersfoort, he likes America}，根据确定首字

符串的算法可知，head_string=Amer，foot_string=ica。匹配流程图如图4-5所示：

在第三次移动时，出现首字符串Amer匹配的情况，此时用尾字符串ica进行相应位置到字符匹配，发现匹配失败，于是首字符串移动到尾字符串匹配失败的地方进行下一轮匹配。利用Sunday算法进行第八次移动时，又发生了首字符串匹配的情况，而此时尾字符串也与相应位置的字符匹配成功，至此模式匹配成功。

图4-4 模式匹配过程

图4-5 模式匹配流程图

4.3改进匹配算法的snort实现

我们把改进的 Sunday 算法应用到 snort 系统，首先设文本串为 T(k)，长度为n；模式串为 P，长度为 o，真首子串为 H(j),长度 m，尾子串 F(i),长度为 o-m。算法流程如图4-6所示：

根据流程图，改进的Sunday 算法使每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮的匹配，且降低了匹配次数。从而大大提高了snort处理数据包的速度。

图4-6 改进的算法流程图

5 实验结果及评估

5.1系统平台

实验过程所需软件：

（1） apache2.2.3；（2） php5.2.5；（3） adodb498；（4） mysql4.1.22；

（5） winPcap4.0.1；（6） jpgraph-2.3；（7） snort2.8；

（8） acid 0.9.6b23.1；（9） visual C++ 6.0；（10）cygwin。

5.2 实验部署及流程

5.2.1 实验部署

（1）入侵检测系统体系

入侵检测系统安装在两台基于 windows操作系统的计算机上。其中一台我们称为事件收集与检测服务器，用于捕获局域网中的网络数据，进行规则匹配后生成报警数据。另外一台称为分析与处理服务器，用于接收事件收集与检测服务器生成的报警数据，对报警事件进行分析与处理。入侵检测系统构建框架如图5-1所示：

图5-1入侵检测系统框架图

（2） 事件收集与检测服务器的安装

首先，在安装了 cygwin 和 vc6.0 的计算机下通过 vc 编译修改过算法的 snort 源码，然后将生成的 snort.exe 文件和 LibnetNT.dll 文件，以及 snort.conf，拷贝至事件收集与检测服务器的 C：\snort 目录下。其次，修改

本文来源：https://www.bwwdw.com/article/6p6j.html