一种适于HTTP数据还原的QS改进算法*

钱松波，刘嘉勇

(四川大学 电子信息学院，四川 成都 610065)

一种适于HTTP数据还原的QS改进算法*

钱松波，刘嘉勇

(四川大学 电子信息学院，四川 成都 610065)

为了更快速、准确地对HTTP应用数据进行还原，文中研究了改进的单模式匹配算法。对BM算法、BMH算法和QS算法进行了分析，并重点研究了QS算法的改进思路，最后提出了一种适用于HTTP应用数据还原的CIQS算法。CIQS算法考虑了HTTP模式串的字符特点，改进了模式串的字符比较顺序，并对坏字符跳跃思想进行了改进，增大了跳跃距离。实验结果表明，CIQS算法有效减少了匹配次数，相比其他几种算法有更好的时间性能。

HTTP还原 模式匹配 CIQS算法

0 引 言

随着网络技术的飞速发展，网络安全问题也随之产生，信息的有效检测和监控已成为一个重要问题。而HTTP协议是互联网上应用最广泛、最重要的通信协议[1]，对它的通信数据的实时检测和有效还原显得十分有必要。

在对HTTP应用数据还原时，主要利用字符串匹配技术来提取有用信息，而模式匹配算法正是字符串匹配的重要方法，为了能更快速、精确地对内容进行识别和还原，需要改进匹配算法，提升匹配效率。

本文首先分析了三种典型的单模式匹配算法的优缺点，然后重点在QS算法[2]的基础上进行改进，并加入了对HTTP模式串字符特点的考虑，提出了一种改进算法，称之为Character Improved Quick Search算法，简称为CIQS算法。

1 三种典型的算法

为了方便算法描述，进行以下定义：对于长度为n的待匹配文本字符串T=T1T2…Tn和长度为m的模式串P=P1P2…Pm(一般n≥m)，如果对它们进行匹配，存在TiTi+1…Ti+mTi+m-1=P1P2…Pm-1Pm(其中1≤i≤n-m+1)，则称匹配成功，且返回模式串在文本串中匹配的位置，否则称匹配失败。

1.1 BM算法

BM算法[3]是由Boyer和Moore在1977提出的单模式匹配算法。其思想是：匹配时，先将模式串和待匹配文本串左对齐，比较从右向左进行，若发生失配，则用坏字符规则和好后缀规则来计算模式串的右移量，它的大小由较大的值决定。

坏字符规则：当文本串字符Ti与模式串字符Pj不匹配时，如果Ti不在模式串中出现，则右移量为m；若Ti在模式串中出现，则移动模式串，使Ti与它在模式串中最右出现的位置对齐，再开始下一轮匹配。右移量的具体确定方法如下

好后缀规则：在模式串与文本串进行匹配时，如果发现字符Ti≠Pj，而Pj+1…Pm已经匹配成功，则偏移量的确定分为两种情况：当模式串中的某一子串Pj-s+1…Pm-s和已匹配部分Pj+1…Pm相同，则模式串需要向右移动的距离为s位；如果Pj+1…Pm的后缀Ps+1…Pm与模式串的前缀P1…Pm-s相同，则右移量为s位。

BM算法的匹配阶段，最坏情况的时间复杂度为O(m*n)。

1.2 BMH算法

Horspool提出的BMH 算法[4]相对于BM算法更易实现，它在预处理阶段只使用坏字符规则，对匹配过程中的判断也做了简化，当字符失配时，仅考虑文本串当前窗口的末尾字符来计算右移量。

BMH算法的匹配思想是：将模式串和文本串左对齐，先匹配文本串当前窗口的末尾字符，如果匹配成功，再顺序匹配其余的m-1位字符；当文本串中有字符发生失配时，则由文本串当前窗口的末尾字符来启发模式串向右移动。匹配过程中的失配字符表如下式所示

下面用实例来说明BMH算法的匹配过程，假设待匹配的文本串为“catchpostteachmatch”，模式串为“match”，具体匹配的过程如表1所示(加粗字体的字符表示需要比较的字符，点表示不用比较的字符，下同，不再说明)。

表1 BMH算法匹配过程

BMH算法在匹配阶段的时间复杂度为O(m*n)，并没比BM算法更好，但是BMH算法简化了初始化的过程，减少了比较次数，因此在实际使用情况时要比BM算法的效率高。

1.3 QS算法

QS算法是Daniel M. Sunday在1990年提出的，该算法只采用坏字符规则，在匹配时把模式串与待匹配字符串左对齐，文本串与模式串的字符比较既可以从左向右也可以从右向左。

QS的思想是：当发生失配时，考虑文本串当前匹配窗口的下一位字符来确定模式串向右移动的距离，然后产生一个新的窗口，继续尝试下一轮匹配，直到待匹配文本串T结束为止。匹配过程中的失配字符表如下式所示

继续用前面的例子来说明QS算法的匹配过程，匹配过程如表2所示。

表2 QS算法匹配过程

通过比较表1和表2的匹配结果可以发现，QS算法的比较次数和字符比较个数比BMH算法都要小一些，跳跃的距离更大。

QS算法在匹配阶段的时间复杂度仍为O(m*n)，但是它进一步减少了比较次数并增大了跳跃距离，因此QS算法的效率更高。

1.4 改进算法的提出

通过上面对三种典型算法的分析和比较可知，QS算法的最大移动距离可以达到m+1，比BM算法和BMH算法都要大，一定程度上的匹配效率最优。因此在考虑将单模式匹配算法应用到HTTP协议检测还原中时，优先考虑使用QS算法。

但是QS算法仅用一个字符来计算右移量，会增加一些不必要的字符比较和移动；此外，在某些情况下，QS算法的效率不如BMH算法[5]；最后，适当的字符比较顺序对匹配效率也有一定的提升。基于这些考虑，本文提出了一种对QS算法进行改进的单模式匹配算法：CIQS算法。

2 CIQS算法思想与实现

2.1 对QS算法的改进

通过上面的分析，发现QS算法在增大跳跃距离以及减少字符比较次数方面还有很多改进的空间，对它的改进主要考虑三个方面。

1)第一个方面：由于QS算法只用一个字符计算右移量，会增加一些不必要的字符比较和移动。针对此问题提出的改进算法有很多，其中曾传璜等人提出的Sunday2算法：利用窗口对文本串进行切片，使模式串的最大右移量从m+1增加到2m+1，有效减少了字符匹配次数，提高了算法的性能[6]。但是Sunday2算法也有不足，它在预处理阶段使用两个坏字符函数，即要建立两个预处理表，增大了计算开销。

CIQS算法对此做的改进：在预处理阶段仍然只使用QS算法的坏字符规则，并对匹配过程进行了改进，详述在2.2节。CIQS算法的最大右移量仍可达到2m+1，如图1所示。

图1 最大右移距离对比

由图1的结果可以看出，当字符发生失配时，QS算法使模式串向右移动了6位，而CIQS算法使模式串向右移动了11位，即模式串移动了更大的距离，减少了字符匹配次数。

2)第二个方面：考虑文本串当前窗口的末尾字符Ti+m-1没有在模式串中出现而Ti+m在模式串中出现时的情况，如图2所示，这里待匹配文本串都用“contentmatch”，模式串用“match”，并从同一位置开始匹配。

图2 QS与BMH匹配对比

由图2可知，当发生失配时，用QS算法计算的右移量为2，用BMH算法计算的值为5，此时QS算法的效率反而没有BMH算法高。

CIQS算法做的改进：当字符发生失配时，如果当前窗口末尾字符的下一位字符在模式串中，则继续判断当前窗口的末尾字符是否在模式串中，如果没在，则右移距离增大为m，否则不变，借此增大了右移距离。

3)第三个方面：针对HTTP应用数据还原时的模式串的特点，设计适当的字符比较顺序，可以有效减少字符比较次数，提高算法匹配效率。

对HTTP应用数据还原时会用到的一部分模式串进行了整理，比如有content、title、email、word、me-ssage、username、nickname、subject等，这些模式串的特点是：大多为一些常用单词或是与常用单词十分相近的字符串，其后缀通常比较常见，在单词表中存在大量的与它们相同后缀的单词[7]。

由于QS算法大多采用从右向左的顺序来比较字符，如果在文本串中存在很多与模式串同后缀的字符串，则在匹配时就会出现如图3所示的情况：即在模式串的末尾字符附近会连续成功匹配多个字符，但是直到模式串的首字符附近才出现不匹配，这显然增加了大量不必要的字符比较，因此QS算法在这个应用背景下还有改进的空间。

图3 字符比较顺序对比

CIQS算法对此做的改进：在QS算法从右向左顺序比较字符的基础上做了改进，在匹配的过程中，先匹配文本串当前窗口的末尾字符Ti+m-1，如果末尾字符已经匹配成功，不再继续匹配末尾字符的前一个字符Ti+m-2，而是先去匹配文本串当前窗口的首字符Ti，当首字符和尾字符都匹配成功的情况下，再去逐个匹配剩余的字符。

2.2 CIQS算法的实现

CIQS算法的实现分为预处理和匹配处理两部分。在预处理阶段，CIQS算法与QS算法的处理方式相同，都是利用坏字符表函数求出文本串中每个字符的偏移量。而在匹配处理阶段，CIQS算法的匹配步骤可以表述如下：

1)将模式串P和待匹配文本串T左对齐，形成当前窗口。

2)在当前窗口中先从末尾字符Ti+m开始匹配，如果成功，则去匹配首字符Ti，当首字符和末尾字符同时匹配成功时，再继续匹配剩余字符，当全部匹配成功或出现失配时，当前窗口字符匹配结束，然后求出模式串P的右移量。

3)如果右移量不是m+1，要继续判断Ti+m-1是否在模式串中出现，如果Ti+m-1不在则右移量增加到，m否则不变。

4)如果模式串的右移量是m+1，接着判断文本串下一窗口的尾字符Ti+2m是否在模式串中，如果不在，则右移量为2m+1，否则不变。

5)模式串每次都根据右移量向右移动相应距离，产生一个新的窗口，继续尝试下一轮匹配；如果模式串与文本串匹配成功，则返回在文本串中对应的位置。

6)当文本串的指针位置超出了文本串长度时，说明匹配过程结束。整个匹配处理阶段的算法逻辑流程如图4所示。

图4 匹配过程流程

2.3 CIQS算法的性能分析

为了分析改进算法的性能优势，将CIQS算法与BMH算法和QS算法进行对比，继续用前面提到的例子来说明CIQS的匹配过程，即假设待匹配的文本串为“catchpostteachmatch”，模式串为“match”，匹配的过程如表3所示。

表3 CIQS算法匹配过程

通过对比表1、表2和表3的匹配过程可以发现，当文本字符串中出现多个与模式串有相同后缀的字符时(这里为“atch”)，CIQS算法做的字符比较次数明显减少；且在某些情况下，CIQS算法的最大右移量可以达到2m+1，增大了移动距离。

3 实验测试与结果

由上面的分析可知，CIQS算法在理论上有更好的性能。为了测试该算法的效率，将用实验验证。

实验在虚拟机上进行，实验环境：物理机系统Windows 7，配置为Intel(R) Core(TM)2 T5750， 2.10 GHz，2 GB内存；虚拟机为VMware Workstation 8，系统为CentOS5.2，内存1 GB，采用C++编程。

待匹配文本：用抓包软件抓取一些诸如网页论坛、网页搜索、邮件等通信数据包，并随机地将一些已重组的HTTP应用层数据保存成txt文件，大小为6.9 MB。模式串：从待匹配样本中随机选取6个长度分别为3、4、5、6、7、8的字符串。

对不同长度的每个模式串，分别用BMH算法、QS算法和CIQS算法对样本进行匹配，统计匹配成功次数，并对每次匹配过程进行计时。算法匹配成功次数统计结果如表4所示。

表4 三种算法匹配成功次数

从表4的结果可以看出，在不同的模式串长度下，使用BMH算法、QS算法和CIQS算法的匹配成功次数是一样的，说明模式串在待匹配的文本串中已全部被找出，CIQS算法没有出现漏报，该算法在查找字符串的准确率上具有一定的可靠性。

对同一个模式串用三种算法做耗时比较，分别重复匹配过程10次，对运行时间取平均值后的统计结果如图5所示。

图5 算法匹配时间对比

由图5的结果可以看出，BMH算法、QS算法和CIQS算法在模式串长度增大的情况下，它们所需的匹配时间都在逐渐减小，这是因为这三种算法的最大安全跳跃距离都与模式串长度m有关，m越大，跳跃的距离就越大，匹配时间就越短。

此外，在同一个长度的模式串下，比较三种算法的运行时间，发现CIQS算法的匹配耗时最少，且随着模式串长度的增加，CIQS算法比QS算法有更优越的时间性能，这是因为随着模式串长度的增加，文本串中出现与模式串相同后缀的机率也增大，因此改进算法的优势就会体现出来，使字符比较次数减少，提升了匹配效率。

实验说明CIQS算法比QS算法有更大的安全跳跃距离和更少的字符匹配次数，在HTTP应用数据还原中有更好的时间性能。

4 结 语

本文在对BM算法、BMH算法和QS算法进行了分析和比较，重点对QS算法进行了改进，在理论上证明了CIQS算法的可行性，并通过实验验证了该算法在HTTP数据还原应用场景下的良好性能。但是随着网络技术的发展，网络协议检测还原中的模式匹配算法逐渐向多模式匹配方向发展，多模式匹配算法有更好的效率，因此如何对CIQS算法进行改进，使其从单模式匹配向多模式匹配技术方向发展是下一步的方向研究。

[1] 陈雷,刘嘉勇.基于HTTP协议的POST数据分析与还原[J].通信技术,2011,44(04):132-134. CHEN Lei, LIU Jia-yong. Analysis and Reversion of POST Data based on HTTP Protocol[J].COMMUNICATIONS TECHNOLOGY,2011,44(4):132-134.

[2] SUNDAY Daniel M.A Very Fast Substring Search Algorit-hm[J].Communications of the ACM,1990,33(3):132-142.

[3] BOYER Robert Stephen,MOORE J Strother．A Fast String Searching Algorithm[J]．Communications of the ACM,1977,20:762-772．

[4] HORSPOOL R Nigel.Practical Fast Searching in Strings [J] . Software Practice and Experience,1980,10(6):501-506.

[5] 张玉新,李成海,白瑞阳.一种改进的单模式匹配算法[J].制造业自动化,2014 (11):15-17. ZHANG Yu-xin, LI Cheng-hai, BAI Rui-yang. Improved Single Pattern Matching Algorithm [J]. Manufacturing Automation, 2012,34(1):208-212.

[6] 曾传璜,段智宏.一种基于窗口切片的单模式匹配算法[J].江西理工大学学报,2011,32(03):22-25. ZENG Chuan-huang, DUAN Zhi-hong. Design and Realization of the Improved Sunday Pattern Matching Algorithm[J].Journal of Harbin University of Science and Technology,2011,32(3):22-25.

[7] 陈杰.一种基于BMH算法的模式匹配算法[EB/OL].(2011-08-03)[2014-11-08].http://www.paper.edu.cn/releasepaper/content/201108-50. CHEN Jie.A New Algorithm for Pattern Match Based on BMH Algorithm[EB/OL].Beijing: Sciencepaper Online,2011-08-03[2014-11-08].http://www.paper.edu.cn/releasepaper/content/201108-50.

QIAN Song-bo(1989-),male, graduate student, mainly working at network communication and network security.

刘嘉勇(1962—)，男，博士，教授，博士生导师，主要研究方向为信息安全。

LIU Jia-yong(1962-),male,Ph.D.,professor, doctoral tutor,principally working at information security.

A Modified Quick Search Algorithm for HTTP Data Reduction

QIAN Song-bo， LIU Jia-yong

(College of Electronic Information,Sichuan University,Chengdu Sichuan 610065,China)

In order to achieve fairly quick and accurate reduction of HTTP application data, this paper discusses the modified single pattern matching algorithms, analyzes BM, BMH and QS algorithms,with focus on the improved idea of QS algorithm，and finally proposes a CIQS algorithm suitable for HTTP application data reduction. The characteristics of HTTP pattern strings in CIQS algorithm are considered，and the matching sequence of characters in the matching process is modified. Meanwhile, the idea for bad character jumping is improved，thus the jumping distance is increased. Experiment results show that CIQS algorithm effectively reduces the number of matching times，and enjoys better time performance as compared with other algorithms.

HTTP reduction; pattern matching; CIQS algorithm

date:2014-09-05；Revised date：2014-12-21

TP301.6

A

1002-0802(2015)03-0351-06

钱松波(1989—)，男，硕士研究生，主要研究方向为网络通信与网络安全；

10.3969/j.issn.1002-0802.2015.03.020

2014-09-05；

2014-12-21