BM算法在IDS中的实现

1.2 本课题研究的意义
随着网络技术的快速发展，网络入侵行为也越来越严重。入侵检测系统作为防火墙技术的合理补充，越来越受到人们的重视，逐渐成为网络安全体系的一个重要组成部分。它对网络或操作系统上的可疑行为做出策略反应，及时切断入侵源，记录并通过各种途径通知网络管理员，以求最大幅度的保障系统安全。在IDS中数据包的捕获与解析是其中最重要的两个部分。但是在实际的网络运行中，数据包的捕获速度与解释速度不能匹配，这样就造成了IDS中的一个比较普遍的丢包率较高的问题。为了解决这个问题，各种各样的IDS技术被广泛采用。这些技术中，模式匹配是IDS的一个最基本也是关键的技术，它通过对照一系列已有的攻击比较用户活动，从而发现入侵。它的匹配速度的快慢直接影响到IDS的丢包率以及误报率。尤其对于基于规则的入侵检测来说，模式匹配算法非常重要，它直接影响到系统的准确性和实时性能。 【www.think58.com计算机毕业论文网】
2 入侵检测系统概述
2.1 入侵检测的概念
入侵，是指任何试图危及计算机资源的完整性、机密性或可用性的行为。Smaha从策略角度将入侵分为尝试性闯入、伪装攻击、安全控制系统渗透、泄漏、拒绝服务和恶意使用等6种类型。
入侵检测，是对入侵行为的发觉，它通过从计算机网络或系统中的若干关键点收集信息，并对这些信息进行分析，从而发现网络或系统中是否有违反安全策略的行为和遭到攻击的迹象。实现入侵检测功能的软件与硬件的组合就是入侵检测系统。

think58.com

2.2 入侵检测系统的组成及部署
2.2.1 入侵检测系统的组成
IETF(The Internet Engineering Task Force，互联网工程任务组)阐述了一个入侵检测系统的通用模型，将一个入侵检测系统分为四个组件：
事件产生器(Event generators)
事件分析器(Event analyzers)
响应单元(Response units)
事件数据库(Event databases)
事件产生器也称为探测器或传感器，它的目的是从整个计算环境中获得事件，并向系统的其他部分提供此事件。事件分析器又可称为检测引擎，它分析得到数据，并产生分析结果。响应单元则是对分析结果做出反应的功能单元，它可以做出切断连接、改变文件属性等强烈反应，也可以只是简单的报警。事件数据库是存放各种中间和最终数据地方的统称，它可以是复杂的数据库，也可以是简单的文本文件。
在实际的产品中，入侵检测系统通常是由传感器、分析系统、存储系统和控制台等四部分组成，其中存储系统一般用来存储系统运行的数据和入侵攻击过程，而控制台起其集中管理的作用。图2-1给出了通用入侵检测系统结构。 think58 [版权所有：http://think58.com]

数据 数据 数据 结果

think58 [来源：http://think58.com]

提取 分析 处理
图2-1 通用入侵检测系统结构
2.2.2 入侵检测系统的部署
在大型网络中，分析系统工作负载大，存储系统工作量也大，所以在不同的计算机上。网络入侵检测系统的传感器位置非常重要，如果放置位置不正确，入侵检测系统的工作就可能不在最佳状态。
(1)放在防火墙外
传感器通常放置在防火墙的DMZ中(Demilitarized Zone，非军事区)。DMZ是介于ISP和最外端防火墙之间的区域，这种安排使入侵检测系统可以看见所有来自Internet的攻击。
(2)放在防火墙内
把传感器放在防火墙内部，这种做法有几个充分理由。传感器放在防火墙外部，攻击者就能够发现传感器，就可能对传感器进行攻击，从而减小攻击者的行动被审计的机会。防火墙内的系统会比外面的系统脆弱性少一些，如果传感器放在防火墙内就会少一些干扰，从而有可能减少误报警。如果本应该被防火墙封锁的攻击渗透进来，传感器在防火墙内就能发现防火墙的设置失误。将传感器放在防火墙内部的最大理由就是设置良好的防火墙能够阻止大部分简单的攻击，使传感器不用将大部分的注意力分散在这类攻击上。
(3)放在防火墙外和内
如果不考虑成本，在防火墙外和防火墙内都放置传感器是最佳的选择。这样做有以下优点：无须猜测是否有攻击渗透过防火墙；可以检测来自内部和外部的攻击；可以帮助系统管理员检测到由于设置有问题而无法通过防火墙的内部系统。 本文来自think58

[来源：http://www.think58.com]

2.3 网络入侵检测系统Snort
2.3.1 Snort系统概述
Snort系统是一个以开放源代码形式发行的网络入侵检测系统，由Martin Roesch编写，并由遍布世界各地的众多程序员共同维护和升级。Snort运行在Libpcap库函数基础上，并支持多种系统软硬件平台，如RedHat Linux、Debian Linux、HP-UX、Solaris、x86Free/Net/OpenBSD、NetBSD、MacOS X以及Windows等。
与许多昂贵而庞大的商用系统相比较，Snort系统具有系统尺寸小、易于安装、便于配置、功能强大、使用灵活等诸多优点。实质上，Snort不仅是一个网络入侵检测系统，它还可以作为网络数据分析器和记录器来使用。它采用基于规则的工作方式，对数据包进行规则匹配来检测多种不同的入侵行为和探测活动，例如缓存溢出、隐蔽端口扫描、CGI攻击、SMB探测等等。Snort具备实时报警功能，可以发送警报消息到系统日志文件、SMB消息或者是指定的警报文件中。系统采用命令行选项和可选BPF命令的形式进行配置。系统检测引擎采用了一种简单规则语言进行编程，用于描述对每一个数据包所应进行的测试和对应的可能响应动作。
2.3.2 Snort系统简要分析
整个Snort系统架构的着眼点在于强调性能、简洁和灵活性三个方面。大体上，Snort系统由三个子系统构成：数据包解析器、检测引擎和日志/警子系统。所有这些子系统都是建立在数据包截获库函数接口Libpcap的基础上，Libpcap为它们提供了一个可移植的数据包截获和过滤机制。整个程序的配置、规则的解析以及数据结构的初始化都在系统进行数据包分析和检测之前完成，以保证对每个数据包的处理时间压缩到最少，以获得最好的运行性能。 think58

[来源：http://think58.com]

系统模块的总体执行顺序及调用关系大致如下所示。
(1)首先执行主函数main，其中包括对命令行参数的解析及各种标识符的设置。同时，主函数还调用相关例程对预处理器模块、输出模块和规则选项关键字模块进行初始化工作，其实质是构建包含各种处理模块或者初始化模块的链表结构。接下来，调用的是关键的规则解析进程，最后，主函数启动数据包的截获和处理进程。
(2)在对数据包进行处理时，首先是调用各种网络协议解析例程，对当前数据包进行分层协议格式字段的分析，并将分析结果存入到重要的数据结构Packet中。
(3)之后，系统依次调用预处理例程和入侵检测例程，根据给定的各种规则和当前所截获的数据包的协议分析结果，做出相应的是否发生入侵行为的判断。
(4)如果当前数据包符合某条检测规则所指定的情况，则系统可根据该条规则所定义的响应方式以及输出模块的初始化定义情况，选择各种方式的日志进行记录和报警操作。
由于系统所有重要的分析和操作工作，都是围绕着各自所涉及的数据结构类型而展开的，所以在对系统的源代码的分析过程中，主要是对各种重要的数据结构的分析，例如在数据包协议解析、各种处理模块的初始化过程以及关键的规则解析进程所涉及到的各种数据结构类型。 内容来自think58 [来源：http://think58.com]
首先对系统架构的三大主要组成部分进行一个简单的介绍。
(1)数据包解析器
解析引擎的全部工作都是围绕着网络协议层中的各层协议展开的，包括了数据链路层协议和TCP/IP协议的定义。解析引擎中的每个子例程使用事先定义好的数据结构，从网络数据流中解析出协议信息。这些子例程按照网络协议层自下而上的顺序调用，从数据链路层到传输层，直到应用层协议结束。在协议解析的过程中，强调执行的速度，所完成的主要功能是设置数据结构Packet中的各种指针，使其指向数据包中不同位置，以便检测引擎执行下一步的分析工作。Snort提供对多种底层协议的支持，如Ethernet、SLIP、PPP等。
(2)检测引擎
Snort系统将其检测规则组织成一个二维的链表结构，主要分为两个部分:链表头和链表项，在链表头中包含的是多个规则中的共有属性，而不同的检测属性选项则包含在不同的链表项中。例如，如果在一个规则文件中指定了45条检测CGI-BIN探测活动的规则，而它们都具有相同的源/目的IP地址以及端口号。为了加快检测的速度，这些共同属性就会压缩到一个单独的链表头中，而第一个不同的检测属性将在与相关链的各个链表选项结构中保存。
对于每个数据包，系统都会在二维的链表结构上对此规则链进行递归搜索工作。系统的检测引擎将只检查那些在运行时已经由规则解析器设定好的链表选项。一旦检测引擎搜索到一个检测属性与解析后数据包相匹配的规则，则触发定义好的规则动作并返回。 think58 [资料来源：www.THINK58.com]
检测引擎的编程采用“插件”模式，即各种检测功能都是通过各种插件模块来完成。采用此种灵活的结构模式，有利于用户加入自己编写的检测模块来增强系统功能，或者定制用户特殊需求的系统。每一个插件地与对应的规则关键字进行绑定，以保证在执行检测引擎时被正确调用。Snort系统代码的一个重要组成部分就是插件管理例程。更进一步的，不仅是检测引擎，系统的其他部分如预处理器和输出部分也采用了插件模式。
(3)日志/警报子系统
日志/警报子系统在运行时使用命令行开关选项进行选择。目前，可用3种日志模式和5种警报模式。日志模式可以设定为3种:关闭、以可读格式记录数据包和以Tcpdump二进制格式记录数据包。以可读形式记录数据包的模式有利于快速分析，而以Tcpdump格式记录数据包的模式能够提高系统运行性能。为了获得更高的运行性能，可以关闭日志功能，只保留警报功能。
警报信息可以发送到系统日志文件(Syslog)，以两种不同格式记录到警报文本文件，以Winpopup消息形式发送或者关闭。发送到系统日志文件中的警报可以使用适当的软件工具进行分析，而采用Winpopup消息形式的警报可以发送到用户定义的一组运行Winpopup软件的Windows控制台。当发送到文本文件时，存在两种记录选项:完整和快速警报模式。完整警报模式记录警报消息和完整的传输层数据包头信息，而快速模式只记录数据包头信息的压缩子集，从而提高系统性能。 think58
2.3.3 Snort系统部分源码简介
这里使用snort-1.6-beta7进行讲解。展开snort的压缩包，有约50个c程序和头文件，另有约30个其它文件(工程、数据或者说明文件)。
snort.c(.h)是主程序所在的文件，实现了main函数和一系列辅助函数。
decode.c(.h)将数据包层层剥开，确定使用了哪种协议，有什么特征，并标记到全局结构变量pv中。
log.c(.h)实现日志和报警功能。snort有多种日志格式，一种按tcpdump二进制的格式存储，另一种按snort编码ASCII格式存储到日志目录下，日志目录的名字根据“外”主机的ip地址命名。报警有不同的级别和方式，可以记录到syslog中，或者记录到用户指定的文件，另外还可以通过linux socket发送报警消息，以及利用SMB向Windows系统发送winpopup消息。
mstring.c(.h)实现字符串匹配算法。在snort中，采用的是BM算法。
plugbase.c(.h)实现了初始化检测以及登记检测规则的一组函数。snort中的检测规则以链表的形式存储，每条规则通过登记过程添加到链表中。
rule.c(.h)实现了规则设置和入侵检测所需要的函数。规则设置主要的作用是把一个规则文件转化为实际运作中的规则链表。检测函数根据规则实施攻击特征的检测。
sp_*_check.c(.h)是不同类型的检测规则的具体实现。

[来源：http://www.think58.com]

spo_*.c(.h)实现输出规则。
spp_*.c(.h)实现预处理规则。
将改进的BM算法应用到snort系统中，只需要对mstring.c进行修改即可，其它部分保持原样。
3 BM算法
3.1 BM算法
3.1.1 BM算法具体介绍
朴素的模式匹配算法在一次字符比较失败后，只是简单的把模式匹配串向右移动了一个字符位置，这样做的缺点是完全丢弃了在前面已经作过的字符匹配过程中得到的信息，BM匹配算法正是充分利用了上次匹配比较中己得到的部分结果，使模式匹配算法在时间复杂性和空间复杂性上得到了一定程度的优化。
假设有一长度为n的文本字符串T，长度为m的模式字符串P，两者都是由字符构成的有序集合，文本T(如中英文等自然语言文本)定义在一个有限的字母表∑上，字母表大小为 。匹配的目的是确定P在T内的位置，或者T中不包含P。设T和P中的字母由0开始从左至右顺序编号。如果对于一个指定偏移或移动s，每个字符Pi∈P1……Pm匹配相应字符Ti+s∈T1……Tn。若P发生在T中的偏移s处，可以将等式写为：
Ti+s……Tm+s=Pi……Pm
BM算法的基本思想是先对模式匹配串P进行预处理，计算两个偏移函数:Badchar(针对某个字符)和GoodSuffix(针对某个子串)，然后将文本和模式对齐，从右往左进行匹配，当文本字符与模式字符不匹配时，根据函数Badchar和GoodSuffix计算出的偏移值，取两者中的大者。将文本指针往右移，匹配成功则予以输出。

copyright think58 [资料来源：www.THINK58.com]

BM算法分为两阶段：预处理阶段和查找阶段。
若考虑Badchar函数的约束，则当文本在字符c与模式不匹配时，下次应移动的距离为Badchar[c]十1-(m-j)，其中j为c在本次匹配中的位置。这样就可以实现下次匹配时文本中的c与模式中的c位置对齐，从而加快匹配的速度。匹配过程是:
(1)将文本中的字符T[i+j]和它在P[0…m-2]中从右至左首次出现的位置对齐。如下图3-1所示：
T

think58好，好think58 [资料来源：http://www.THINK58.com]

[资料来源：http://www.THINK58.com]

P think58好，好think58

P

图3-1 P中包含匹配字符
(2)如果模式P中没有T[i+j]，则将窗口的左终点与T[i+j]的右侧字符对齐。如下图3-2所示：

copyright think58 [资料来源：http://THINK58.com]

[资料来源：http://think58.com]

T think58.com

[资料来源：www.THINK58.com]

P [资料来源：THINK58.com]

P

图3-2 P中不包含匹配字符
若考虑GoodSuffix函数的约束，则在模式字符中位置为j的字符与文本中位置为i+j的字符不匹配的情况下，文本中T[i+j+1 ....i+m+1]与模式中P[j+1 ....m-1]是匹配的。匹配过程如下:
(1)从P的最右边开始寻找与该后缀相同的片断，并且该片断的前面(左侧)是与P[j]不同的字符，将此片断和后缀对齐。如下图3-3所示：
T think58 [资料来源：http://THINK58.com]

P 内容来自think58

[资料来源：http://think58.com]

P

图3-3 P中包含匹配字符串
(2)如果在P中不存在这样一个片断(即，在P中只有一个后缀u)，则应让模式字符指针移动后出现一个即是匹配后缀又是模式前缀的字符串v，并让这个前缀v尽可能大，这也大大加快了匹配速度。如下图3-4所示：
T think58 [资料来源：http://THINK58.com]

P [来源：http://think58.com]

P

图3-4 P中不包含匹配字符串
3.1.2 BM算法预处理
在BM算法中，预处理阶段的任务是计算Badchar和Goodsuffix两个偏移量函数。
Badchar计算字符集∑中每个字符所对应的偏移量，如果某个字符在模式P中出现多次，则由最右边的那次出现确定偏移量，可表示为：对于∑中的每个字符a：若a在P中出现，那么Badchar[a]＝min｛i｜1≤m-1且P[m-1-i]=a｝；若a没有在P中出现，那么Badchar[a]=m。
Goodsuffix函数用来计算模式中的某个后缀被匹配成功时文本指针可以右移的偏移量，由两个因素决定：
(1)该后缀在模式中除去自身外，从最右端开始再次出现的位置；
(2)在第一个条件不成立的情况下，该后缀的某个后缀同时又是模式的前缀。
对于每个k，使得i＜k＜m，s≥k或x[k-s]=x[k]，这个条件用于计算模式的某个后缀除去自身外的从最右侧开始重新出现时所对应的偏移量；若s＜i，则P=[i-s]≠P[i]，这个条件确保计算到模式的第i个位置。
综合两方面的考虑，设j是文本与模式某次不匹配时字符在模式中的位置(0≤j≤m-1)。
3.1.3 BM算法查找
首先将模式匹配串P与文本在左端对齐，然后从模式字符串最右端开始与文本字符串开始匹配，在某次匹配中，文本字符T[i+j]与模式字符P[j]匹配不成功，按BM算法，则比较Badchar[T[i+j]]-(m-j)与Goodsuffix[j]的值，取大者作为偏移量，然后将文本指针i往后移动偏移量，然后再从后往前进行比较。如果模式被扫描完，则找到了模式的一次出现，文本指针右移GoodSuffix[0]。

copyright think58 [来源：http://www.think58.com]

3.2 BM算法字符匹配实例
下面给出一个例子来具体说明BM算法的基本思想：
假设T=I LOVE YOU，P=YOU
左端对齐P与T，使P1与T1对齐；与普通模式匹配相反，从右到左搜索，并且向左移动直到匹配失败。Tm=L，Pm=U，Tm≠Pm，不匹配。如下所示：
T1 Tn
I L O V E Y O U
Y O U
P1 Pm
正如许多先进的模式匹配算法一样，BM预处理模式并且获得一些有启发性的信息。同时，BM算法会使用这些信息来计算文本字符串T向右移动的数值。由于“L”并没有在模式字符串P中出现，因此，我们可以将文本字符串T右移3个位置，这里因为模式字符串P的长度为3，所以移动3个位置。如下所示： think58好，好think58 [来源：http://think58.com]

T1 Tm+3 Tn
I L O V E Y O U
Y O U
P1 Pm
同上从右到左搜索，并且向左移动直到匹配失败。Tm+3=E,Pm＝U，Tm+3≠Pm，不匹配。如下所示：
T1 Tm+3 Tn
I L O V E Y O U
Y O U
P1 Pm
由于Tm+3=E并没有在模式P中出现，因此，我们可以将文本字符串T右移3个位置。如下所示：
T1 Tm+6
I L O V E Y O U
Y O U
P1 Pm
同上从右到左搜索，并且向左移动直到匹配失败。Tm+6=0，Pm=U，Tm+6≠Pm，不匹配。如下所示：
T1 Tm+6
I L O V E Y O U
Y O U
P1 Pm
由于Tm+6＝P2＝O，因此，我们可以将文本字符串T右移１个位置使Tm＋6与P2对齐。如下所示：
T1 Tm+6
I L O V E Y O U
Y O U
P1 Pm
同上从右到左搜索，并且向左移动直到匹配失败。这次匹配成功。
下面给出一个例子来具体说明BM算法的基本移动：
假设
模式串 P：GCAGAGAG
匹配文本串 T：GCATCGCAGAGAGTATACAGTACG [版权所有：http://think58.com]

根据Badchar函数计算公式得到：
表3-1 Badchar函数预处理结果
c A C G T
Badchar 1 6 2 8
根据Goodsuffix[i]函数计算公式得到：
表3-2 Goodsuffix函数预处理结果
i 0 1 2 3 4 5 6 7
char G C A G A G A G
Goodsuffix[i] 7 7 7 2 7 4 7 1
第一次比较
G C A T C G C A G A G A G T A T A C A G T A C G
1
G C A G A G A G
0 1 2 3 4 5 6 7 j=7
移动距离为： 1
Goodsuffix[7]=Badchar[A]+1-(m-j)=1+1-(8-7)=1
字符比较次数： 1
第二次比较
G C A T C G C A G A G A G T A T A C A G T A C G
3 2 1
G C A G A G A G
0 1 2 3 4 5 6 7 j=5
移动距离为： 4
Goodsuffix[5]= Badchar[C]+1-(m-j)=6+1-(8-5)=4
字符比较次数： 3
第三次比较
G C A T C G C A G A G A G T A T A C A G T A C G
8 7 6 5 4 3 2 1
G C A G A G A G
0 1 2 3 4 5 6 7
移动距离为： 0
字符比较次数： 8

[资料来源：http://think58.com]

字符串长度： 24
模式串长度： 8
比较次数： 3
字符比较次数：12
BM算法在最差情况下的时间复杂度为O(mn)，平均时间复杂度为O(n/m)，Badchar和Goodsuffix两个偏移量函数进行预处理的时间至少为O(m)。