一种面向入侵检测系统的模式匹配算法的改进

杜广林 顾炳根

桂林理工大学信息科学与工程学院 广西 541004

0 引言

随着互联网技术的不断发展，人们在享受其带来的越来越多的便利的同时，也遭受着日趋增多的针对企业公司和网络用户的攻击。黑客事件频频发生，企业和用户的重要数据及财产安全面临严重威胁。据报道，全球平均每 20秒钟就有一次入侵事件发生，仅美国每年造成的损失就高达100亿美元。为了确保网络上主机的安全，通常使用如下的几种防范技术如：数据加密技术，数字签名技术，访问控制技术，防火墙技术和入侵检测技术等等。这其中，入侵检测技术作为一种主动防御技术，相较于其他被动防御技术发挥着更为重要的作用。目前，入侵检测技术已经成为网络安全工具的主要研究和发展方向。

所谓入侵检测技术是指对外来入侵行为进行防范和检测的一种技术，通过采集系统日志和网络中数据来进行分析比对，从而检测出威胁网络安全的行为。如图1所示一般的入侵检测系统(Intrusion Detection System，IDS)通常由以下几个部分组成：事件产生器(Event-Box)，分析引擎(Analysis-Engine)，事件数据库(Database-Box)和响应单元(Response-Box)。分析引擎是 IDS的核心模块，负责对原始数据的采集和分析，通过检测算法比对判断是否是入侵行为。在IDS的实现中，许多研究都集中于对于分析引擎的改进，以期望提高入侵检测的效率和准度。改进模式匹配算法是提高分析引擎效率的就是一种可行性很高的方法。

图1 IDS结构图

1 介绍和分析几种经典的模式匹配算法

模式匹配算法是指在长度为n的正文T串中找出长度为m的模式串S第一次出现的位置，一旦找到就称产生一次匹配。在实际应用中，有的系统可能需要找出所有匹配。IDS中使用的模式匹配算法，按照每次能够匹配的模式串的个数主要分两类：单模式匹配算法和多模式匹配算法。

所谓单模式匹配算法指的是在模式匹配中，一次只对一个模式串进行匹配。而多模式匹配算法则是在模式匹配中，能同时对多个模式串进行匹配。常用的单模式匹配算法有：BM算法，BMH算法和BMHS算法等。常用的多模式匹配算法有：WM算法，AC算法等。在入侵检测系统中，通常较多采用单模式的BM 算法或多模式的WM算法。相比较而言，BM算法在空间性能上要优于WM算法，其在内存空间的消耗更小。

1.1 BM算法

BM(Boyer-Moore)算法是 Boyer和 Moore在 1977年提出的一种经典的单模式匹配算法。它是一种基于后缀搜索的算法，也就是说此算法从右向左进行逐字符的比较。如果字符相等，则左移一位，继续进行比较；如果在比较中，出现了某个字符的不匹配，则会触发两种启发性规则之一即：坏字符(Badcharcter)和好后缀(Goodsuffix)，并取两者的最大值进行位置偏移。

(1) 坏字符(Badcharcter)规则

所谓坏字符规则是指若文本串T和模式串S在某个位置出现了不匹配，则根据T串在不匹配位置的字符c是否出现

在S串中的原则进行位移，坏字符的右移公式：公式(1)

(2) 好后缀(Goodsuffix)规则

好后缀规则是针对模式串S中的子串r，r是文本串T与模式串S已匹配的一段字符串，它分为如下两种情况：

① 若已匹配的子串r在S串的中间某个位置重复出现，则将S串右移移动到r最右端出现的位置与T串中的r对齐。

② 若已匹配的子串r在S中不再出现，但是r的一个子串r′在S串的前缀出现，则将S右移，使得S串和T串中的r′对齐。

好后缀的右移公式如公式(2)所示：

1.2 BMH算法

尽管在BM算法在理论上很完备，但是由于其比较复杂，尤其是好后缀规则计算复杂且难以理解。在实际应用中，它也并不是最快的匹配算法。因此在实践中，IDS通常采用它的简化算法。

BMH(Boyer-Moore-Horspool)算法是首个对 BM 算法的改进算法，是Horspool于1980年提出的一种简化算法。它仅仅保留了 BM 算法中的坏字符(Badcharcter)规则，并对其做了一定的修改。其修改后的规则如下：若模式串S与字符串T在某个字符发生了不匹配，则坏字符是模式串S末尾所对应文本串T中的字符c，并根据c在S串中是否出现向右移动。若c在S串中不存在，则S直接右移m长度；反之，则使S右移至c在S串中最右出现的位置与T串中的c对齐。

1.3 BMHS算法

BMHS(Boyer-Moore-Horspool-Sunday)算法是 Sunday于1990年在BMH算法的基础上的一种改进算法，利用文本窗口的下一位字符进行启发，即一位启发规则，可实现最大为m+1的偏移量。BMHS算法的思想具体如下：当文本串T与模式串 S出现失配时，则判断文本窗口的下一位，即启发位字符c是否在S串中出现。若c不存在于S串中，则S就可进行一个偏移量为m+1的一个右移；反之，若c存在于S中，则右移S串使S串中c出现的最右边的位置与T串中的c对齐。于是可以看出，当启发字符不存在与S串中的时候，BMHS算法的移动距离是要高于BM算法和BMH算法的，从而实现了一个更高的效率。

2 对于BMHS算法提出的一种改进算法BMHSN

虽然BMHS算法可以实现最大值为m+1的偏移量，但是它的缺点也很明显，就是若启发位的字符存在于模式串 S中的时候，BMHS算法的移动距离是要小于BMH算法的。因此，假如启发位的字符在S串中出现的频率较高的话，那么BMHS的效率将大大降低，反而会低于BMH算法。怎样更好的保证最大距离m+1出现的频率，就成为了下一步算法改进的重点。

当启发字符c不存在于S串时，右移量即为m+1，所以BMHS算法的这一部分保留不做改动。而所需要改动的部分就是当c存在于S串中，右移量计算的方法。因此提出了如下几点改进策略：

(1) 若启发字符c存在于S串中，首先判断c首次出现的位置是否是S串的第一个字符，如果是则右移 m位使 S串的第一个字符与c对齐；否则对比T串中c的前一个字符与S串中c的前一个字符是否相同。

(2) 若不相同，则右移S串m+1个位置；如果相同，则判断c是否是S串的最后一个字符。

(3) 若c是S串的最后一个字符，则将S串右移一个位置；否则，判断S串中c后一字符与启发字符后一个字符是否相同。

(4) 若不相同，则右移S串m+1个位置；若相同则将S串右移使S串中的c与T中的启发字符对齐继续比较。

图2 BMHSN算法流程图

改进后算法BMHSN的流程图如图2。下面来看一个三种算法一次移步后的例子，如表1。

表1 三种算法一次移步后的例子

通过表1可以看出，BMH算法的位移量为m，而BMHSN为 m+1；假如启发位的字符存在于模式串中，那么 BMHS的位移量要小于BMH算法；BMHSN算法与BMHS算法相比m+1位移量的出现几率要大于BMHS算法。

3 结束语

本文重点分析了单模式匹配算法中的几种经典算法：BM，BMH和BMHS，指出了几种算法的优点和缺点。结合几种算法的优缺点，提出了一种更高效的算法—BMHSN算法。此算法提高了最大位移量m+1的出现几率，并且大大减小了当启发位字符存在于模式串时，位移量小于BMH算法的几率。

[1]雒明世,张群良.浅析网络的入侵检测.电信减缓.2005.

[2]唐正军,李建华.入侵检测技术[M].北京:清华大学出版社.2004.

[3]Robert S.Boyer,J.Strother Moore.A fast string searching algorithm[J].Communication of the ACM.1997.

[4]Horspool R N.Practical fast searching in strings [J].Software-Practics&Experience.1980.

[5]Sunday D M.A very fast substring search algorithm[J].Comm unications of the ACM.1990.