-1-
中国科技论文在线
基于 BM算法的入侵检测系统的研究
王建
武汉理工大学信息工程学院，武汉（430070）
摘 要：本文研究了网络入侵检测的核心技术——模式匹配。研究从模式匹配方法的原理出
发，提出了其面临的问题。在此基础上，对当前入侵检测系统中最流行的 BM算法从原理到
性能进行了详细地分析。BM算法拥有较高的匹配效率，但在网络字符匹配的环境下，存在
一些非必须的字符比较，本文对算法进行了改进，最后利用著名的开源入侵检测系统 Snort
和实际的网络环境，对改进的算法进行了测试分析，并与 BM算法进行了比较。实验证明，
改进的算法在能提高入侵检测的效率，从而验证了该改进是有效的。
关键词：入侵检测；模式匹配；BM算法； BM算法改进
中图分类号：
1．引言
入侵检测是一种动态的安全防护手段，它能主动识别入侵信息[1]，为网络系统提供安全
保护。模式匹配技术是入侵检测系统识别攻击行为的主要技术，它能够快速探测攻击的存在，
具有误报率低、准确性高、实用性强等优点。在高速网络环境下，入侵检测的速度有可能跟
不上数据包传输速率，导致攻击行为的漏报，因而入侵检测系统的检测速度越来越成为其获
得实效的瓶颈之一。降低入侵检测中常用的模式匹配算法的时间复杂度和空间复杂度是提高
检测性能的一种有效途径[2]。本文的研究重点是对入侵检测中使用的模式匹配算法进行研究
和改进。
本文对入侵检测的现状进行了分析，重点研究了网络入侵检测的核心技术—模式匹配。
目前主要的字符的模式匹配算法主要有[3]BM 算法、KMP 算法、和 BF 算法等，研究从模式
匹配方法的原理出发，提出了其面临的问题。在此基础上，对当前最流行的 BM 算法从原理
到性能进行了详细地分析和讨论。BM 算法拥有较好的匹配效率，但是它不能记录上一次匹
配结果，而且算法的预处理过程也会带来较大的内存占有量。BM 算法本身有许多无用的比
较，这是其需要改进的地方。因此，在这里提出一种改进的算法，可以减少不必要的比较次
数，解决 BM 算法存在的问题。这种改进的算法是在运行 BM 算法前，进行一些预处理。
2. BM 算法分析与改进
算法简介
BM 算法（Boyer-Moore algorithm）是 1997 年由 Boyer 和 Moore 共同设计的一个字符串
单模式精确匹配算法[4]。该算法在应用上通常被认为是最有效的字符串匹配算法，很多文本
编辑器的“查找”和“替换”功能就是使用 BM 算法的完整或简化版本。下面我们介绍一下 BM
模式匹配算法的原理。在讨论 BM 算法之前我们先做下述假设：
●入侵特征模式串，也就是我们要查找的字符串表示为 P；
●待检测的数据包，也就是我们将要从中查找 P 的数据，表示为 T；
● P 的长度为 m；
● T 的长度表示为 n(n>=m)；
● P 的第一个字符和最后一个字符分别表示为 P1，P2，．．．Pm；
● T 的第一个字符和最后一个字符分别表示为 T1，T2，．．．Tn。
-2-
中国科技论文在线
⑴从右向左移动。先使 P 与 T 从左端对齐，即使 T1与 P1左对齐，匹配则从 P 的最右端
字符开始，比较 Pm与 Tm是否相同，若匹配成功，则向左移一位，比较 Pm-1 与 Tm-1 是否相
同，以此类推，直到 P 全部匹配成功或有不匹配成功的情况出现。
⑵坏字符移动。若匹配失败发生在 Pj≠Ti,此时可采用坏字符来右移 P，向右移动的距离
可以通过函数 R(x)求得。
{ P x P( ) PmR x = 中 最 右 端 出 现 x的 位 置 x在 中不 在 中
⑶好后缀移动。该规则是指出 P 与 T 部分匹配情况下的移动。假设 P 与 T 部分匹配子
串 t，这时的移动可以分为三种情况：
①模式串 P 中还会出现子串 t(记为 t’)，则将 P 向右移动，使得 P 中最右端的子串 t’与 T
中已匹配的子串 t 对齐，且 t’前的字符要不同于 P 中已匹配子串 t 前的那个字符。
②模式串 P 不再有这样的子串 t，但是 P 的最左端有一个子串 s，而已有部分入侵检测
系统研究与实现匹配的子串 t 中也有这样的子串 s，则在这种情况下，将 P 向右移动，使得
P 中的 s 与 T 中的 s 对齐。
③P 中既没有这样的子串 t，也没有这样的子串 s，这样的话将 P 直接向右移动的距离为
m。
BM 算法分析
⑴BM 算法是从右向左进行字符的比较，而一般的字符串匹配算法是从左向右进行字符
的比较。
⑵一般的字符串查匹配算法，当查找匹配失败的时候，则将目标串 T 向后移动一个字
符从头再重复比较，而 BM 算法则可以根据匹配失败之前获得的信息移动多个字符。
⑶BM 算法完成搜索的时间复杂度是 ( )o m rn+ [5]（ r为模式串在文本串中出现的次数）。
查找阶段最坏情况下的时间复杂度为 ( * )o m n ，最好情况下的时间复杂度是 ( / )o m n 。
⑷BM 算法由于没有考虑匹配的后缀及导致匹配失败的当前字符之间的相邻关系，使得
算法的整体效率不高。
BM 算法改进
BM 算法本身有许多无用的比较，这是其需要改进的地方。因此，在这里提出一种改进
的算法，可以减少不必要的比较次数，解决 BM 算法存在的问题。这种改进的算法是在运行
BM 算法前，进行一些预处理。
改进思想为：在匹配 P 和 T 的时候，考虑 P 中的每个字符是否都包含在 T 中。假如 P
中至少有一个字符不在 T 中出现，则可以肯定不匹配，不要进行下面的匹配了。否则需用
BM 算法进行匹配。其次，考虑如果 P 中的每个字符都出现在 T 中，那么他们的顺序是否相
同。在这里我们利用图的方式来判断 P 中的字符是否在 T 中出现。首先预处理 T，给出一个
包括 256 个字符单元的图，对于在 T 中出现的字符，用 1 来标记其在图中的相应位置，若
不存在则用 0 来标记位置。
算法描述：下面给出这种算法的伪代码：
preprocess(char*T,int len)//预处理阶段
{
int map[256];
-3-
中国科技论文在线
for(int i=0;i<len;i++)
map[t[i]]=1;
}
search(char*P,char*T,int len_P,int len_T)//搜索阶段
{
for(int i=0;i<len_p;i++)
{
if(map[p[i]]!=1)
return NOT_EXIST;
}
retrun BM_New(P,len_P,T,len_T);
}
算法分析：从上面的伪代码可以看出，预处理阶段的时间复杂度与数据包负载的大小成
线形关系，搜索阶段的时间复杂度与所有模式的长度和成线性关系。改进后的算法避免了对
字符的逐个检查，减少了不必要的比较，可以有效的提高运算效率。目前，一些黑客故意发
送大量经过精心设计的数据包，使得一些检测引擎所采用的 BM 算法在处理这些数据包时一
直处在最坏情况下搜索，造成检测引擎处理数据速度变得非常缓慢，在这种情况下，为了适
应网络的速度，不至于影响 IDS 的性能，检测引擎不得不丢弃大量的数据包。这样，黑客
就会达到其攻击的目的。改进算法在运行 BM 算法之前进行预处理，可以避免这种数据包的
大量出现对算法的攻击。预处理的加入能够快速地排除负载中不包含匹配模式串的数据包。
由于在大多数的数据包中，入侵数据包占少数，因此需要调用标准的字符串匹配算法几率较
小，缩短了检测时间。
3. 实验分析
测试环境
为了测试前文中两种改进算法在 NIDS 中的工作状况，首先需要构建一个测试环境。
本次测试的实验环境如表 1 所示。
表 1 测试实验环境
CPU Pentium(R)4
物物理内存 1GB RAM
操作系统 windows xp professional
数据库
NIDS
在这里，本文选用 NIDS 的典型代表 来侧试模式匹配算法。作为一个轻量级
网络入侵检测系统，Snort 具有易于安装、系统尺寸小、便于配置、使用灵活、功能强大、
规则库更新快等优点。更为重要的，Snort 是开放源代码软件，因此可以非常方便地通过修
改其配置文件来满足测试改进算法的要求。
其次，对 Snort 的配置文件 进行网络环境参数配置。在每一次测试之前，都
必须用改进后的算法去代替系统原来的 BM 算法。具体的方法是测试改进 BM 算法时，在
配置文件里增加一句：config detection:seareh method GJBM；而在测试改进 BM 算
法时，重新设置为：config detection:seareh method BM。
-4-
中国科技论文在线
为了便于进行算法性能的比较，首先应使 Snort 工作于嗅探器模式下，然后对采集的数
据分别使用改进算法进行测试，为了对比算法改进前后的性能优化，测试过程中同时还记录
了 Snort 系统使用默认的 BM 算法匹配时的性能参数。
本次采集的数据包共 1000 个，其数据类型统计如表 2 所示。
表 2 采集数据包类型统计表
数据包类型 数量 比例
TCP 849 %
UDP 75 %
ICMP 21 %
其他 55 %
测试过程中首先采用其中的 50 条 Web 内容检测规则，分别使用三种算法进行检测，记
录每种算法完成规则模式匹配需要的时间。接着将检测规则每次递增 50 条直至 274 条，依
次记录。为了更客观真实地获取实验数据，按相同的方法对每一个算法重复测试 3 次，并将
测试结果取平均值。最终得到的算法运行时间比较结果如图 3 所示。
表 3 原算法与改进算法运行时间表
50 100 150 200
原 BM 算法
改进 BM 算法
从表 3 可以看出，随着有关内容检测规则的增多，需要检测的内容增加，两种算法的检
测时间基本都呈线性增长，因为它们都需要逐个规则匹配。相比原 BM 算法而言，改进的
BM 算法在运行速度上有所改善，改进的算法的运行时间少了大约 20%。
4．总结
本文介绍了介绍网络安全状况，模式匹配在入侵检测中的作用，对入侵检测中 BM 模式
匹配算法进行了分析，针对原 BM 算法的缺陷，改进可原算法，通过实验证明，改进后的算
法能提高入侵检测的速度。模式匹配是是入侵检测的核心部分，如何减少算法的空间复杂度，
减小系统开销也是今后研究的重点。
规
则
数
时
间
算 法 类 型
-5-
中国科技论文在线
参考文献
[1] Jack Koziol．Intrusion Detection with Snort，2005
[2] 韩东海，王超，李群．入侵检测入侵检测系统实例剖析．北京：清华大学出版社，2007 年 5 月
[3] Wang Hun,Zhou yang,Xu Shuijiang．Research of IPv6 IDS based on Snort[C]．通信与信息技术会议论文集
(下)，2006 年
[4] 曹元大，薛静锋，祝烈煌等．入侵检测技术．北京：人民邮电出版社，2007 年 5 月
[5] 李昀，李伟华.面向入侵检测的模式匹配算法研究.计算机工程与应用，2008，6(6)：1~2
Research of Intrusion Detection System based on BM
algorithm
Wang Jian
Wuhan University of Technology, Wuhan (430070)
Abstract
In this paper, we researched the core of the network intrusion detection techniques - pattern
comes from the pattern matching principle, we put forward the problems they
this basis, we detailed analysised the performance of the current most popular BM algorithm.
It has a higher matching efficiency, but the characters match the network environment, there are some
non-essential character comparison, the paper improved it, at last the improved algorithms were tested
and compared with the BM algorithm,using the famous open-source Snort intrusion detection system in
the actual network environment, Experiment shows that the improved algorithm can improve the
efficiency of intrusion detection, which verifies that the improvements are effective.
Keywords: Intrusion Detection; Pattern Matching; BM Algorithm; Improvement of BM Algorithm
