Snort入侵检测中模式匹配算法的研究和改进

刘凯

摘要：入侵检测系统Snort是一种常用的入侵检测软件，该文其分析系统的检测引擎及其采用的模式匹配算法尤其是BM算法进行了深入的分析和讨论，在分析的基础中对BM算法进行改进，使用一种新的模式匹配算法，以减少匹配时间，提高匹配效率，达到提高算法的平均性能和较少资源消耗的目的。

关键词：入侵检测；模式匹配；算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）34-8117-02

入侵检测系统（Intrusion detection system，简称“IDS”）[1]是一种对网络传输进行即时监控，在发现可以传输数据时发出警报或者采取主动反应措施的网络安全设备。

1 入侵检测系统Snort

Snort[2]入侵检测是一个基于Libpcap的轻量级入侵检测系统软件，是从著名的tcpdump软件发展而来的。它是个基于Libpcap包的网络监视软件，是一个十分有效的网络入侵监测系统。Snort入侵检测系统基本由四部分组成：嗅探器，预处理器，检测引擎，日志报警[3]。如图1所示。

其中检测引擎， 是 Snort 的核心部件， 主要功能是规则分析和特征检测。当数据包从预处理器送过来后， 检测引擎依据预先设置的规则检查数据包，使用某种模式匹配算法 一旦发现数据包中的内容和某条规则相匹配， 就通知报警模块。

2 单模式匹配算法研究与改进

为了提高入侵检测系统的准确率，减少误报率，在实际的入侵检测系统中一般大都采用精确的模式串匹配算法。模式匹配问题分为单模式匹配算法和多模式匹配算法[4]。该文主要对单模式匹配算法（BM）进行研究和改进。

2.1 单模式匹配算法（BM）

仅一次在文本串中查找一个模式串出现的过程，称为单模式匹配，相应的算法称为单模式匹配算法。目前比较常见的单模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了启发式搜索，采用从右向左的比较方式， 使用好后缀和坏字符来决定模式串移动的距离，通常同时使用两个来加快查找速度。能够在搜索过程中跳过大部分文本，从而使执行效率得到很大的提高，因而在 IDS 中运用最为广泛。

Boyer-Moore算法（简称为BM算法）[5]是一个著名的字符串匹配算法，它把被匹配的字符串模板与匹配字符串自左向右对齐，并从字符串的最后一个字符开始自右向左进行比较。BM算法并不是对每个字符依次进行比较，当出现不匹配的字符时，它使用两步启发式搜索过程来决定字符串向右移动多少个字符继续与文本串进行比较，从而减少比较次数。

其中：n>m，需要从T中查找出与P完全匹配的子串，并返回该子串在正文串的首字母的位置。

BM算法采用从右向左比较 的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。 BM算法的基本流程： 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 。若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。

2.2 BM算法改进

尽管BM算法是拥有高效，考虑全面，简便易懂等优点，但是由于其使用了两个数组，预处理时间较大，匹配次数较多，造成许多重复、不必要的比较，还是存在很多需要改进的地方。

通过对BM算法的分析，我们可以发现，原算法虽然是用到了两种启发式规则，即坏字符规则和好后缀规则。但是，在算法的分析中我们看到，当进行字符或者字符串匹配时，大多数匹配都用到的规则是坏字符规则。因此我们可以只用坏字符规则，通过移动量和规定字符这两个方面对BM算法进行一些改进。

根据改进算法的思想，可以对BM算法进行如下改进。由文本串和模式串最后一个位置对应的字符的下一个字符做启发向右滑动。其作用在于在每次匹配失败后，把模式向右滑动的距离变大，减少了模式匹配中一些不必要的和重复的比较，缩短了模式匹配的时间。

首先，对模式串和文本串进行分析，将文本串中文本串与模式串最后一个位置对应的字符的下一个字符（假设为x）与模式串进行匹配。当字符x在模式串中不存在时，那么显然从x开始的m个文本不可能与模式串 匹配成功，所以直接跳过，移动距离为模式串长度+1。当x在模式串中出现，并且x的前一位字符也存在于模式串中。移动模式串使字符对齐，计算偏移量。利用原BM算法进行匹配。当x在模式串中出现，但是x的前一位字符不存在于模式串中，计算移动模式串使字符x对齐时的偏移量和原BM算法中字符不存在模式串中时的偏移量，进行比较，取两者中的偏移量大的进行匹配。

2.3 算法性能比较

分别对BM算法和改进后的BM算法进行性能测试，用同一主程序分别调用BM算法和改进后的BM算法进行匹配测试，匹配算法实验中均插入CPU内部时间戳进行高精度计时，同时统计两种算法在匹配时模式串向右移动的次数。

初始条件：文本串：whiccmnxmxammm 模式串： emam

下图是分别用BM算法和改进后的BM算法对文本串和模式串进行匹配后所得到的数据。

3 结论

本文以目前最著名、最活跃的、基于误用检测的Snort为基础，针对目前应用最广泛的模式匹配算法BM算法的缺陷进行改进。但由于各个方面的局限性，该文研究还有不足和待改进的地方。总之，网络安全是技术问题，也是管理的问题。只有提高使用者的安全意识，合理使用网络及安全工具，才能达到网络的真正安全。

参考文献：

[1] 蒋建春，冯登国.网络入侵检测原理与技术[M].北京：国防工业出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵检测[M].宋劲松，译.北京：国防出版社，2004.

[3] Jack Koziol.Snort入侵检测实用解决方案[M].吴薄峰，许诚，译.北京：机械工业出版社，2005.

[4] 李晓芳，姚远.入侵检测工具Snort的研究与使用[J].计算机应用与软件，2006，23（3）：123-124.

[5] 胡大辉，刘乃齐.高效的snort规则匹配机制[J].微计算机信息，2006（2）.

[6] 2009年中国互联网网络安全报告[R].北京：电子工业出版社，2010.

[7] 杨薇薇，廖翔.一种改进的BM模式匹配算法[J].计算机应用，2006（2）：64-65.endprint

摘要：入侵检测系统Snort是一种常用的入侵检测软件，该文其分析系统的检测引擎及其采用的模式匹配算法尤其是BM算法进行了深入的分析和讨论，在分析的基础中对BM算法进行改进，使用一种新的模式匹配算法，以减少匹配时间，提高匹配效率，达到提高算法的平均性能和较少资源消耗的目的。

关键词：入侵检测；模式匹配；算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）34-8117-02

入侵检测系统（Intrusion detection system，简称“IDS”）[1]是一种对网络传输进行即时监控，在发现可以传输数据时发出警报或者采取主动反应措施的网络安全设备。

1 入侵检测系统Snort

Snort[2]入侵检测是一个基于Libpcap的轻量级入侵检测系统软件，是从著名的tcpdump软件发展而来的。它是个基于Libpcap包的网络监视软件，是一个十分有效的网络入侵监测系统。Snort入侵检测系统基本由四部分组成：嗅探器，预处理器，检测引擎，日志报警[3]。如图1所示。

其中检测引擎， 是 Snort 的核心部件， 主要功能是规则分析和特征检测。当数据包从预处理器送过来后， 检测引擎依据预先设置的规则检查数据包，使用某种模式匹配算法 一旦发现数据包中的内容和某条规则相匹配， 就通知报警模块。

2 单模式匹配算法研究与改进

为了提高入侵检测系统的准确率，减少误报率，在实际的入侵检测系统中一般大都采用精确的模式串匹配算法。模式匹配问题分为单模式匹配算法和多模式匹配算法[4]。该文主要对单模式匹配算法（BM）进行研究和改进。

2.1 单模式匹配算法（BM）

仅一次在文本串中查找一个模式串出现的过程，称为单模式匹配，相应的算法称为单模式匹配算法。目前比较常见的单模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了启发式搜索，采用从右向左的比较方式， 使用好后缀和坏字符来决定模式串移动的距离，通常同时使用两个来加快查找速度。能够在搜索过程中跳过大部分文本，从而使执行效率得到很大的提高，因而在 IDS 中运用最为广泛。

Boyer-Moore算法（简称为BM算法）[5]是一个著名的字符串匹配算法，它把被匹配的字符串模板与匹配字符串自左向右对齐，并从字符串的最后一个字符开始自右向左进行比较。BM算法并不是对每个字符依次进行比较，当出现不匹配的字符时，它使用两步启发式搜索过程来决定字符串向右移动多少个字符继续与文本串进行比较，从而减少比较次数。

其中：n>m，需要从T中查找出与P完全匹配的子串，并返回该子串在正文串的首字母的位置。

BM算法采用从右向左比较 的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。 BM算法的基本流程： 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 。若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。

2.2 BM算法改进

尽管BM算法是拥有高效，考虑全面，简便易懂等优点，但是由于其使用了两个数组，预处理时间较大，匹配次数较多，造成许多重复、不必要的比较，还是存在很多需要改进的地方。

通过对BM算法的分析，我们可以发现，原算法虽然是用到了两种启发式规则，即坏字符规则和好后缀规则。但是，在算法的分析中我们看到，当进行字符或者字符串匹配时，大多数匹配都用到的规则是坏字符规则。因此我们可以只用坏字符规则，通过移动量和规定字符这两个方面对BM算法进行一些改进。

根据改进算法的思想，可以对BM算法进行如下改进。由文本串和模式串最后一个位置对应的字符的下一个字符做启发向右滑动。其作用在于在每次匹配失败后，把模式向右滑动的距离变大，减少了模式匹配中一些不必要的和重复的比较，缩短了模式匹配的时间。

首先，对模式串和文本串进行分析，将文本串中文本串与模式串最后一个位置对应的字符的下一个字符（假设为x）与模式串进行匹配。当字符x在模式串中不存在时，那么显然从x开始的m个文本不可能与模式串 匹配成功，所以直接跳过，移动距离为模式串长度+1。当x在模式串中出现，并且x的前一位字符也存在于模式串中。移动模式串使字符对齐，计算偏移量。利用原BM算法进行匹配。当x在模式串中出现，但是x的前一位字符不存在于模式串中，计算移动模式串使字符x对齐时的偏移量和原BM算法中字符不存在模式串中时的偏移量，进行比较，取两者中的偏移量大的进行匹配。

2.3 算法性能比较

分别对BM算法和改进后的BM算法进行性能测试，用同一主程序分别调用BM算法和改进后的BM算法进行匹配测试，匹配算法实验中均插入CPU内部时间戳进行高精度计时，同时统计两种算法在匹配时模式串向右移动的次数。

初始条件：文本串：whiccmnxmxammm 模式串： emam

下图是分别用BM算法和改进后的BM算法对文本串和模式串进行匹配后所得到的数据。

3 结论

本文以目前最著名、最活跃的、基于误用检测的Snort为基础，针对目前应用最广泛的模式匹配算法BM算法的缺陷进行改进。但由于各个方面的局限性，该文研究还有不足和待改进的地方。总之，网络安全是技术问题，也是管理的问题。只有提高使用者的安全意识，合理使用网络及安全工具，才能达到网络的真正安全。

参考文献：

[1] 蒋建春，冯登国.网络入侵检测原理与技术[M].北京：国防工业出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵检测[M].宋劲松，译.北京：国防出版社，2004.

[3] Jack Koziol.Snort入侵检测实用解决方案[M].吴薄峰，许诚，译.北京：机械工业出版社，2005.

[4] 李晓芳，姚远.入侵检测工具Snort的研究与使用[J].计算机应用与软件，2006，23（3）：123-124.

[5] 胡大辉，刘乃齐.高效的snort规则匹配机制[J].微计算机信息，2006（2）.

[6] 2009年中国互联网网络安全报告[R].北京：电子工业出版社，2010.

[7] 杨薇薇，廖翔.一种改进的BM模式匹配算法[J].计算机应用，2006（2）：64-65.endprint

摘要：入侵检测系统Snort是一种常用的入侵检测软件，该文其分析系统的检测引擎及其采用的模式匹配算法尤其是BM算法进行了深入的分析和讨论，在分析的基础中对BM算法进行改进，使用一种新的模式匹配算法，以减少匹配时间，提高匹配效率，达到提高算法的平均性能和较少资源消耗的目的。

关键词：入侵检测；模式匹配；算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）34-8117-02

入侵检测系统（Intrusion detection system，简称“IDS”）[1]是一种对网络传输进行即时监控，在发现可以传输数据时发出警报或者采取主动反应措施的网络安全设备。

1 入侵检测系统Snort

Snort[2]入侵检测是一个基于Libpcap的轻量级入侵检测系统软件，是从著名的tcpdump软件发展而来的。它是个基于Libpcap包的网络监视软件，是一个十分有效的网络入侵监测系统。Snort入侵检测系统基本由四部分组成：嗅探器，预处理器，检测引擎，日志报警[3]。如图1所示。

其中检测引擎， 是 Snort 的核心部件， 主要功能是规则分析和特征检测。当数据包从预处理器送过来后， 检测引擎依据预先设置的规则检查数据包，使用某种模式匹配算法 一旦发现数据包中的内容和某条规则相匹配， 就通知报警模块。

2 单模式匹配算法研究与改进

为了提高入侵检测系统的准确率，减少误报率，在实际的入侵检测系统中一般大都采用精确的模式串匹配算法。模式匹配问题分为单模式匹配算法和多模式匹配算法[4]。该文主要对单模式匹配算法（BM）进行研究和改进。

2.1 单模式匹配算法（BM）

仅一次在文本串中查找一个模式串出现的过程，称为单模式匹配，相应的算法称为单模式匹配算法。目前比较常见的单模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了启发式搜索，采用从右向左的比较方式， 使用好后缀和坏字符来决定模式串移动的距离，通常同时使用两个来加快查找速度。能够在搜索过程中跳过大部分文本，从而使执行效率得到很大的提高，因而在 IDS 中运用最为广泛。

Boyer-Moore算法（简称为BM算法）[5]是一个著名的字符串匹配算法，它把被匹配的字符串模板与匹配字符串自左向右对齐，并从字符串的最后一个字符开始自右向左进行比较。BM算法并不是对每个字符依次进行比较，当出现不匹配的字符时，它使用两步启发式搜索过程来决定字符串向右移动多少个字符继续与文本串进行比较，从而减少比较次数。

其中：n>m，需要从T中查找出与P完全匹配的子串，并返回该子串在正文串的首字母的位置。

BM算法采用从右向左比较 的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。 BM算法的基本流程： 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 。若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。

2.2 BM算法改进

尽管BM算法是拥有高效，考虑全面，简便易懂等优点，但是由于其使用了两个数组，预处理时间较大，匹配次数较多，造成许多重复、不必要的比较，还是存在很多需要改进的地方。

通过对BM算法的分析，我们可以发现，原算法虽然是用到了两种启发式规则，即坏字符规则和好后缀规则。但是，在算法的分析中我们看到，当进行字符或者字符串匹配时，大多数匹配都用到的规则是坏字符规则。因此我们可以只用坏字符规则，通过移动量和规定字符这两个方面对BM算法进行一些改进。

根据改进算法的思想，可以对BM算法进行如下改进。由文本串和模式串最后一个位置对应的字符的下一个字符做启发向右滑动。其作用在于在每次匹配失败后，把模式向右滑动的距离变大，减少了模式匹配中一些不必要的和重复的比较，缩短了模式匹配的时间。

首先，对模式串和文本串进行分析，将文本串中文本串与模式串最后一个位置对应的字符的下一个字符（假设为x）与模式串进行匹配。当字符x在模式串中不存在时，那么显然从x开始的m个文本不可能与模式串 匹配成功，所以直接跳过，移动距离为模式串长度+1。当x在模式串中出现，并且x的前一位字符也存在于模式串中。移动模式串使字符对齐，计算偏移量。利用原BM算法进行匹配。当x在模式串中出现，但是x的前一位字符不存在于模式串中，计算移动模式串使字符x对齐时的偏移量和原BM算法中字符不存在模式串中时的偏移量，进行比较，取两者中的偏移量大的进行匹配。

2.3 算法性能比较

分别对BM算法和改进后的BM算法进行性能测试，用同一主程序分别调用BM算法和改进后的BM算法进行匹配测试，匹配算法实验中均插入CPU内部时间戳进行高精度计时，同时统计两种算法在匹配时模式串向右移动的次数。

初始条件：文本串：whiccmnxmxammm 模式串： emam

下图是分别用BM算法和改进后的BM算法对文本串和模式串进行匹配后所得到的数据。

3 结论

本文以目前最著名、最活跃的、基于误用检测的Snort为基础，针对目前应用最广泛的模式匹配算法BM算法的缺陷进行改进。但由于各个方面的局限性，该文研究还有不足和待改进的地方。总之，网络安全是技术问题，也是管理的问题。只有提高使用者的安全意识，合理使用网络及安全工具，才能达到网络的真正安全。

参考文献：

[1] 蒋建春，冯登国.网络入侵检测原理与技术[M].北京：国防工业出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵检测[M].宋劲松，译.北京：国防出版社，2004.

[3] Jack Koziol.Snort入侵检测实用解决方案[M].吴薄峰，许诚，译.北京：机械工业出版社，2005.

[4] 李晓芳，姚远.入侵检测工具Snort的研究与使用[J].计算机应用与软件，2006，23（3）：123-124.

[5] 胡大辉，刘乃齐.高效的snort规则匹配机制[J].微计算机信息，2006（2）.

[6] 2009年中国互联网网络安全报告[R].北京：电子工业出版社，2010.

[7] 杨薇薇，廖翔.一种改进的BM模式匹配算法[J].计算机应用，2006（2）：64-65.endprint