韦安垒 李开科 张榆

摘 要：基于已有的单模式匹配算法，论文设计了一种改进的快速单模式匹配算法，实现了一个基于DPI技术的下一代防火墙系统，并将改进后的算法应用于该系统。测试发现，新设计的下一代防火墙的性能和功能都得到了优化。

关键词：模式匹配算法；DPI技术；下一代防火墙

中图分类号：TN915.08 文献标识码：C

Design and implementation of a fast single pattern matching algorithm

Abstract： Based on the existing single pattern matching algorithm， a next generation firewall system based on DPI technology is designed and implemented. And the improved algorithm is applied to this system. Tests have found that the performance and functionality of the next generation firewall are optimized.

Key words： pattern matching algorithm； DPI technology； next generation firewall

1 引言

针对KMP算法可保证字符适配后，模式串不回溯，但由于跳转距离较小，算法平均性能较BM算法要低；BMH2C算法具有较大的跳转距离，具有较好的平均性能，但由于不能保证字符适配后模式不回溯，在最坏和较坏的情况下，具有较差的性能，其复杂度为O（mn）。结合二者优点，本文提出一种改进的快速单模式匹配算法——BMH2CKMP算法。通过将该算法应用于下一代防火墙，从而测试该算法的是否有效。

2 BMH2CKMP算法

BMH2CKMP算法结合了KMP算法和BMH2C算法二者的优势，弥补各算法的不足，从而解决既能大幅跳转又无需回溯的问题。

2.1 算法设计思想

KMP算法复杂度为O（n），可保证字符适配后，模式串不回溯，则在最坏情况（模式串位于文本串的末尾处）下，具有较高的性能。但由于跳转距离较小，算法平均性能较BM算法要低。BM算法及其改进算法具有较大的跳转距離，具有较好的平均性能，但由于不能保证字符适配后模式不回溯，在最坏和较坏的情况下，具有较差的性能，其复杂度为O（mn）。本文结合KMP于BMH2C算法各自的优势提出一种新的单模式匹配算法BMH2CKMP算法。BMH2CKMP算法的设计思想是：

第一步：以BMH2C算法为基础，将其修改为正向匹配；

第二步：预处理对patten串求next数组；

第三步：模式匹配时，若字符失配，则判断跳跃值为正向还是负向。正向则选择跳跃，获取最大位移，负向则查找next数组，挪动j的位置，来强制i不回溯。

2.2 算法描述

在KMP算法中，为了确保在字符失配后，下次匹配时j的位置，引入了next数组，next[j]的值表示P[0...j-1（不含j本身）]中最长的后缀等于前缀的长度。

对于next数组的定义如下：

next[]函数取值如表1所示。

即next[j]=k>0时，表示P[0...k-1]=P[j-k，j-1].

因此KMP算法的思想就是：在匹配过程中，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较，复杂度为O（n）。

在BMH2C这个算法中，我们将与模式的最后一个字符相对应的文本字符及其下一个字符作为一个子串，当子串在模式中出现时，则模式向右移，使得该子串与它在模式中最右边的出现对齐；否则，模式右移时，直接跳过这个子串，即右移量为m+1。

由于使用两个字符来决定右移量，所以用二维数组来表示偏移量数组skip[char1][char2]，在数组初始化时，第一步就将二维数组的值全部设置为m+1。同时还考虑到一种特殊情况，即当子串S[i]S[i+1]的后一个字符S[i+1]与模式的第一个字符P[0]相同时，虽然子串S[i]S[i+1]不在模式中出现，但如果右移m+1很可能漏掉一种匹配情况，因此只应该右移m，使模式的第一个字符P[0]与子串的后一个字符S[i+1]对齐。因此我们在初始化的第二步就对skip数组的值做了修正，将skip[i][p[0]]置为m。初始化的第三步是为模式串中出现的所有子串设置相应的右移量。由于BMH2C算法不能确保j不回溯，所以复杂度为O（mn）。

本算法结合KMP和BMH2C算法各自的优势，初始化构建skip和next数组，匹配时，文本串S与模式串P左对齐，然后依次匹配字符。失配后，查找skip数组，获取位移。此时判断位移为正还是负。若位移为正，则按位移跳转。若位移为负，则查询next数组，获取新位移。直至匹配成功或到文本串末尾为止。由于next数组位移恒为正，则可保证该算法的j值永不回溯，尽量以最大位移跳转，且复杂度为O（n）。

算法流程如图1所示。

算法C语言实现如下：

2.3 算法分析

BMH2CKMP算法基于KMP和BMH2C算法的优势，实现一种更加快速的单模式匹配算法，进一步提升模式匹配速度，应用于下一代防火墙DPI技术，可进一步提升下一代防火墙的工作效率。

算法效果演示分析：

（1）预处理得到next数组

（2）预处理得到Skip跳转表：

（3）进行模式匹配

（4）匹配结果演示：

由以上演示过程我们可以得出几个结论：

（1）最好情况下，BMH2C算法复杂度O（n），性能要好于KMP（复杂度O（m+n））算法；新算法与BMH2C算法速度几乎一致；

（2）最坏情况下，BMH2C算法由于i的回溯，复杂度为O（mn）性能低于KMP算法；新算法与KMP算法速度几乎一致；

（3）一般情况下，新算法的复杂度为O（n），性能最高；

（4）新算法性能在各种情况下总是优于或等于两种算法。

3 实验

3.1 系统设计

下一代防火墙系统系统由帐户管理、系统管理、安全策略管理、日志管理、安全检测、网络计费、VPN虚拟专网等七大部分组成，其中包括了网络配置、路由管理、IP-MAC绑定、规则配置等多个功能模块。

（1）系统物理架构如图2所示，用户使用浏览器跟HTTP服务器双向交互，HTTP服务器联通防火墙用户管理接口，用户无需和防火墙底层结构打交道，通过浏览器可以直接访问管理防火墙。

（2）系统程序架构如图3所示，各个功能模块间通过用户接口相互协作，共同完成防火墙系统功能。

（3）系统逻辑流程如图4所示，防火墙系统包括账户管理、系统管理、安全检测、日志管理、安全策略、网络计费和虚拟专网等七大功能模块。其中系统管理和安全策略模块又分为多个子功能模块。

3.2 系统测试

测试硬件条件：下一代防火墙一台（配置为：处理器Intel Core I3-4160，CPU主频3.6G，内存DDR3 8G，硬盘SSD120G，接口数8*GE RJ45、4*GE SFP），Win2000 服务器三台，100MbpsHub一台，网络连接均为100Mbps以太网。本节主要对下一代防火墙的最大并发连接数、吞吐量、每秒TCP新建连接数等性能指标进行测试。

3.2.1 最大并发连接数

防火墙最大并发连接数代表着防火墙可以支持的最大的网络同时建立连接的数量，它的大小表示了防火墙对网络规模大小的支持程度，最大并发连接数越大意味着支持的网络规模越大。使用Smart Bits网络性能测试仪和WebSuite测试软件测试防火墙的并发连接数指标，测试网络拓扑如图5所示。

改进前防火墙最大并发连接数为700 Mbps，改进后防火墙实际测试最大并发连接数750 Mbps，使用新算法后的防火网最大并发连接数高于使用新算法之前的并发连接数。

3.2.2 吞吐量

防火墙吞吐量是以待测设备不丢弃数据包为前提的最大速率，吞吐量越大意味着防火墙的性能越高。为了全面衡量防火墙的吞吐能力，按照RFC建议，采用双向测试，整个测试时长为120秒，并设置多流的情况进行吞吐率测试。多流设置为双向、100对流、UDP（即内、外网的地址共200个且互不相同），源和目标地址都同时变化，即在防火墙的状态表内会存在200个状态连接。使用Smart Bits网络性能测试仪和SmartFlow测试软件测试防火墙的双向吞吐量指标。预计吞吐量：64字节帧长500Mbps，512字节帧长4Gbps，1518字节帧长10Gbps，并且规则数对吞吐量的影响应该小于2%。实际测试结果如表2所示。

3.2.3 每秒钟可打开的TCP连接数

防火墙每秒钟能打开的TCP连接数越多，即意味着防火墙同时处理的请求越多，也就意味着防火墙的速度越快。使用Smart Bits网络性能测试仪测试防火墙的每秒钟可打开的TCP连接数。测试网络拓扑如图6所示。

4 结束语

针对KMP算法跳转距离较小以及BMH2C算法不能保证字符适配后模式不回溯的问题，本文设计了一种快速的单模式匹配算法——BMH2CKMP算法，并应用于下一代防火墙，通过测试可以发现。本文设计的使用了改进后的模式匹配算法的下一代防火墙从吞吐量、最大并发连接数、每秒新建连接数等关键性能指标均优于改进前的防火墙。

参考文献

[1] MORRIS J H， PRATT V R. A linear pattern-matching algorithm [J]. 1970，

[2] KNUTH D E， JR J H M， PRATT V R. Fast Pattern Matching in Strings [J]. 1974， 6（2）： 323-10.

[3] DENNING D E. An Intrusion-Detection Model [M]. IEEE Press， 1987.

[4] 錢屹， 侯义斌. 一种快速的字符串匹配算法 [J]. 小型微型计算机系统， 2004， 25（3）： 410-3.

[5] BOYER R S， MOORE J S. A fast string searching algorithm， F， 1977 [C].

[6] 闵联营， 赵婷婷. BM算法的研究与改进 [J]. 武汉理工大学学报（交通科学与工程版）， 2006， 30（3）： 528-30.

[7] 燕红文. 基于Snort的改进BMH单模式匹配算法研究 [J]. 计算机工程与应用， 2012， 48（31）： 78-81.