曾传璜，黄侃

江西理工大学信息工程学院，江西赣州 341000

提高Snort规则匹配速度新方法的研究与实现

曾传璜，黄侃

江西理工大学信息工程学院，江西赣州 341000

ZENG Chuanhuang,HUANG Kan.Research and implementation of new method on increasing speed of rule-matching in Snort.Computer Engineering and Applications,2014,50（22）：102-105.

1 引言

随着网络技术的不断发展，网络安全问题在互联网中越来越严峻，入侵检测系统（Network Intrusion Detection System，NIDS）在网络安全扮演着越来越重要的角色，并且已经被广泛应用于各种网络环境中。Snort[1]是一个开源的、具有高匹配精确度的网络入侵检测系统。对于每一种入侵行为，Snort系统按照检测规则[2]，将捕获的数据包与检测规则进行匹配，若匹配成功，则认为构成入侵行为，将数据包信息反馈出来。

2 提高Snort规则匹配速度

改进Snort系统使用的BM[3]算法（或BM改进算法），能够有效提高Snort规则匹配速度，下面介绍BM及BM改进算法。

2.1 BM算法

1977年，Boyer和Moore提出了BM算法（Boyer-Moore）。BM算法的基本思想：采用两种启发式方法：坏字符启发式方法（Badchar）好后缀启发式方法（Goodsuffix）。

坏字符启发式方法（Badchar）：算法在匹配过程中，若某个字符x不匹配：（1）如果字符x在模式串P中没有出现，那么移动至x字符之后。（2）如果x在模式串P中出现，则移动至与x字符对齐进行再匹配。

好后缀启发式方法（Goodsuffix）：若发现某个字符不匹配的同时，但有部份字符匹配，利用已经匹配成功的部份最长子串，将模式串中的匹配最长前缀或后缀字符串的相应位置对齐。

两种方法都产生了一个移动距离，BM算法取较大的一个作为移动距离。BM算法是继BF算法和KMP算法之后提出的，相比BF算法和KMP算法，是一种具有较高匹配效率的算法，可以达到接近线性的时间复杂度。……