一种面向高速网络的模式匹配方法

摘要

本发明公开了一种面向高速网络的模式匹配方法，由计算机对每种攻击网络的数据流提取出特征值并按照规则语言将其写成规则模式；网络通信中，计算机通过检测系统将捕获到的数据包与所述规则模式进行匹配；如果匹配成功，则检测系统将其判断为攻击行为。本发明所述匹配步骤结合已有BM方法从比较方式和移动策略两个方面出发实现创新突破，大大提高了匹配效率。本发明适合于高速网络环境下网络入侵检测、网络入侵保护和计算机病毒特征码匹配等需要进行快速字符匹配的领域应用。

权利要求

1.一种面向高速网络的模式匹配方法，首先由计算机对每种攻击网络的数据流提取出特征值并按照规则语言将其写成规则模式；网络通信中，计算机通过检测系统将捕获到的数据包与所述规则模式进行匹配；如果匹配成功，则检测系统将其判断为攻击行为，其特征在于，所述匹配包括如下步骤：(1)设所述捕获到的数据包中的正文串T＝T[1]…T[n]，其中长度为n；

所述规则模式的模式串P＝P[1]...P[m]，其中长度为m，n＞＞m；

(2)给出滑动距离函数

上述函数给出了正文串中可能出现的任意字符c在模式串中的位置；

(3)给出判断字符在模式串中出现的频次的函数；

(4)T[1]和P[1]对齐，对P[m]与T[m]匹配；

若P[m]与T[m]匹配不成功，则按步骤(5)计算出模式串向右移动的距离，右移相应距离；若P[m]与T[m]匹配成功，则比较模式P[1]与文本相应的字符，若P[1]匹配不成功，则按步骤(5)将模式串右移；若p[1]匹配成功，则依次对P[m-1]P[2]P[m-2]P[3]...进行匹配，依次类推，直到匹配完成；

(5)计算向右移动距离，其移动步骤为：

1)：在失去匹配时，首先计算出由文本串最后一个字符，设为T[k]，启发得到的右移位置k+Skip[k]，其值记为k1；

2)：计算由文本串的下一个字符T[k+1]启发得到的右移位置k+1+Skip[k+1]，其值记为k2；

3)：判断k1、k2的大小，如果k1＞k2，再判断T[k+1]在模式串出现频次，用步骤(3)中的函数B(c)判断T[k+1]在模式串出现的频次；若B(T[k+1])＝1，即T[k+1]在模式串只出现一次，则将模式串末端和T[k+1+m]处对齐进行新一轮的匹配；若B(T[k+1])＝0，即T[k+1]在模式串只出现大于一次，则将模式串末端和T[k1]处对齐进行新一轮的匹配；如果k2＞＝k1，则将模式串末端和T[k2]对齐进行新一轮的匹配。

说明书

技术领域

本发明是一种字符串模式匹配的方法，适用于高速网络环境下网络入侵检测、网络入侵保护、计算机病毒特征码匹配等需要进行字符匹配的领域的应用。

背景技术

目前模式匹配方法很多，其中应用最广泛的就是基于BM方法原理实现的模式匹配方法。BM模式匹配方法是一种精确单匹配方法，该方法利用启发式策略跳过不必要的比较来减少模式串与文本的比较次数来提高匹配效率。在进行匹配时将模式串与文本左端对齐，由模式串右端起向左逐个字符比较。开始阶段先对模式串的后缀与文本进行匹配，在完成一次尝试(无论匹配失败或者成功)后，利用移位函数将模式串向右滑动一定的距离，重新从模式串的后缀进行匹配。
著名的轻量级入侵检测系统Snort的核心部分检测引擎中就采用了BM方法进行规则的匹配。但是由于该方法没有考虑已匹配的后缀与导致匹配失败的当前字符之间的相邻关系，使得字符串匹配的效率不够高。

发明内容

本发明要解决的问题是，通过分析已有模式匹配方法，针对现有字符串匹配方法的缺陷，适应当前高速网络对模式匹配高效率的需求，提出一种面向高速网络的模式匹配方法，即HPMM方法，用于高速网络环境下网络入侵检测、网络入侵保护和计算机病毒特征码匹配等需要进行字符匹配的领域，提高匹配效率。
本发明的解决方案是，结合BM方法的比较方式，提出一种面向高速网络的模式匹配方法，首先由计算机对每种攻击网络的数据流提取出特征值并按照规则语言将其写成规则模式；网络通信中，计算机通过检测系统将捕获到的数据包与所述规则模式进行匹配；如果匹配成功，则检测系统将其判断为攻击行为；所述匹配具体包括如下步骤：
(1)设所述捕获到的数据包中的正文串T＝T1…Tn(长度为n)
所述规则模式的模式串P＝P1...Pm(长度为m)，(n>>m)
(2)给出滑动距离函数

上述函数给出了正文串中可能出现的任意字符c在模式串中的位置
(3)给出判断字符在模式串中出现的频次的函数；

(4)T[1]和P[1]对齐，对P[m]与T[m]匹配；
若P[m]与T[m]匹配不成功，则按步骤(5)计算出模式串向右移动的距离，右移相应距离；若P[m]与T[m]匹配成功，则比较模式P[1]与文本相应的字符，若P[1]匹配不成功，则按步骤(5)将模式串右移；若p[1]匹配成功，则依次对P[m-1]P[2]P[m-2]P[3]...进行匹配，依次类推，直到匹配完成。
(5)计算向右移动距离，其移动步骤为：
1)：在失去匹配时，首先计算出由文本串最后一个字符，设为T[k]，启发得到的右移位置k+Skip[k]，其值记为k1；
2)：计算由文本串的下一个字符T[k+1]启发得到的右移位置k+1+Skip[k+1]，其值记为k2；
3)：判断k1、k2的大小，如果k1>k2，再判断T[k+1]在模式串出现频次，用步骤(2)中的函数B(c)判断T[k+1]在模式串出现的频次。若B(T[k+1])＝1，即T[k+1]在模式串只出现一次，则将模式串末端和T[k+1+m]处对齐进行新一轮的匹配；若B(T[k+1])＝0，即T[k+1]在模式串只出现大于一次，则将模式串末端和T[k1]处对齐进行新一轮的匹配；如果k2>＝k1，则将模式串末端和T[k2]对齐进行新一轮的匹配。
本发明提供的上述面向高速网络的模式匹配方法HPMM，结合BM方法从比较方式和移动策略两个方面出发实现创新突破：一是打破了传统的从左向右或是从右向左的匹配方式，采用从模式两端向中间位置交替的匹配顺序，减少了在BM方法匹配过程中，出现模式的一部分后缀与文本匹配，而模式的前缀却不匹配情况下不必要的比较；二是同时考虑字符串后一位字母的唯一性，提高最大位移m+1的出现概率。本发明适合于高速网络环境下网络入侵检测、网络入侵保护和计算机病毒特征码匹配等需要进行快速字符匹配的领域应用。

附图说明

图1是本发明所述模式匹配方法的移动策略示意图；
图2是实施例中BM与HPMM方法的测试数据结果；
图3是实施例中测试数据包类型统计；
图4是Snort中用BM方法和HPMM方法的处理时间的比较；
图5是Snort中用BM方法和HPMM方法的所需内存的比较；
图6是HPMM方法总体流程图；
图7是Snort工作流程图。

具体实施方式

本实施例是HPMM方法在轻量级入侵检测系统Snort中的应用及性能测试，从图7可以看出，轻量级入侵检测系统Snort由数据包嗅探器、预处理器、检测引擎、报警输出模块四个基本模块组成。其最基本的功能部件是数据包嗅探器，数据包嗅探器只是Snort工作的开始，Snort取得数据包后先用预处理器进行处理，然后经过检测引擎中的所有规则链，如果有符合规则链的数据就会被检测出来。Snort有三种工作模式：嗅探器、数据包记录器、网络入侵检测系统。嗅探器模式仅仅是从网络上读取数据包并作为连续不断的流显示在终端上；数据包记录模式将数据包记录在硬盘上；网络入侵检测模式是最复杂的，而且是可配置的，其可以让Snort分析网络数据流以匹配用户定义的一些规则，并根据检测结果采取一定的动作。Snort就是先对每种攻击提取出其特征值并按照规则语言把它写成规则，然后把捕获来的数据包进行解析再与规则匹配，若匹配成功则为攻击行为。在运行中，入侵检测系统将当前操作系统的审计数据和网络中流经的数据包进行分析处理，从中筛选出与安全有关的信息，然后将其与数据库中的攻击模式相匹配，当发现有匹配的行为时，认为有入侵行为发生，然后就按照一定的策略进行响应，移动思路如图1。
具体的匹配过程包括如下步骤：
(1)设所述捕获到的数据包中的正文串T＝T1…Tn(长度为n)
所述规则模式的模式串P＝P1...Pm(长度为m)，(n>>m)
(2)给出滑动距离函数

上述函数给出了正文串中可能出现的任意字符c在模式串中的位置
(3)给出判断字符在模式串中出现的频次的函数；

(4)T[1]和P[1]对齐，对P[m]与T[m]匹配；
若P[m]与T[m]匹配不成功，则按步骤(5)计算出模式串向右移动的距离，右移相应距离；若P[m]与T[m]匹配成功，则比较模式P[1]与文本相应的字符，若P[1]匹配不成功，则按步骤(5)将模式串右移；若p[1]匹配成功，则依次对P[m-1]P[2]P[m-2]P[3]...进行匹配，依次类推，直到匹配完成。
(5)计算向右移动距离，其移动步骤为：
1)：在失去匹配时，首先计算出由文本串最后一个字符，设为T[k]，启发得到的右移位置k+Skip[k]，其值记为k1；
2)：计算由文本串的下一个字符T[k+1]启发得到的右移位置k+1+Skip[k+1]，其值记为k2；
3)：判断k1、k2的大小，如果k1>k2，再判断T[k+1]在模式串出现频次，用步骤(2)中的函数B(c)判断T[k+1]在模式串出现的频次。若B(T[k+1])＝1，即T[k+1]在模式串只出现一次，则将模式串末端和T[k+1+m]处对齐进行新一轮的匹配；若B(T[k+1])＝0，即T[k+1]在模式串只出现大于一次，则将模式串末端和T[k1]处对齐进行新一轮的匹配；如果k2>＝k1，则将模式串末端和T[k2]对齐进行新一轮的匹配。
本实施例将BM方法和HPMM方法分别应用到Snort进行比较，操作过程为：
(1)找到BM方法在Snort源文件中所在的位置。
BM方法应用在Snort源文件中的mstring.c文件中的mSearch函数中，mSearch函数在检测插件sp_pattern_match.c中的函数uniSearchReal中调用。
(2)将mSearch函数中BM方法的实现替换为HPMM方法来实现，并修改相应的参数与接口。
HPMM方法的核心实现程序按图6的方法流程用C语言来实现。
(3)增加相应变量，测试系统性能。
在Snort源程序文件detect.c中的Preprocess(Packet*P)函数里，增加了计算时间的计时变量，用来计算执行时间，在这个函数里增加了三个变量，在函数执行前增加当前时间start，在这个函数执行结尾增加finish，两者相差得出函数执行的时间spenttime.因为最后显示结果在Util.c文件里，于是在输出结果后面添加一条输出语句，用以显示执行时间spenttime。
(4)编译Snort源文件，重新生成Snort可执行程序。
在VC环境中生成应用了HPMM方法的snort.exe文件，为安装Snort作好准备，然后在Snort的配置文件snort.conf中进行设置，配置网络环境及相应的参数。在Linux操作系统下，在安装好Libpcap后，利用安装Snort，待Snort成功安装后即可开始对系统性能进行测试。性能比较步骤：
(1)规则匹配方法处理时间比较
将Snort工作在入侵检测模式进行数据采集(采集1000个数据包，数据包类型如图3)，然后使用采集的数据分别使用BM方法及HPMM方法进行测试，比较它们各自处理的时间。结果如图3，图4所示，HPMM方法由于提高了最大位移出现的概率，减少了移动次数进而减少了匹配次数，使得检测时间比BM方法减少了20％。
(2)系统资源消耗比较
在进行时间比较的同时，我还进行了两种方法在内存使用上的比较，如图5所示，对于相同的样式库，BM方法的所需内存差不多为HPMM方法所需的60％，HPMM方法以内存的增加换取了速度的提高，在当前内存价格不断下降，计算机内存不断增加，入侵特征不断增加的情况下，使用HPMM方法具有现实意义。
(3)系统丢包率测试
不适当的规则将极大的消耗内存或者造成丢包，对系统进行压力测试，可验证极限处理能力，对NIDS而言就是验证它的处理分析数据能力。丢包可能是由于硬件不足或规则不当而消耗过多的CPU。通过加大数据流量检测系统的丢包率，从产生的报警信息看出，在数据流量越大的情况下，应用BM方法的系统的丢包率明显增加，而应用HPMM方法系统的丢包率不明显。
以上测试结果显示，改进前后的系统在性能上比较，原系统比较节约内存，而改进后系统匹配速度快，对于现在内存比较便宜，增加内存比较容易实现，所以新系统的改进很具有现实意义的。