一種適于HTTP數(shù)據(jù)還原的QS改進(jìn)算法*

錢松波，劉嘉勇

(四川大學(xué) 電子信息學(xué)院，四川 成都 610065)

一種適于HTTP數(shù)據(jù)還原的QS改進(jìn)算法*

錢松波，劉嘉勇

(四川大學(xué) 電子信息學(xué)院，四川 成都 610065)

為了更快速、準(zhǔn)確地對HTTP應(yīng)用數(shù)據(jù)進(jìn)行還原，文中研究了改進(jìn)的單模式匹配算法。對BM算法、BMH算法和QS算法進(jìn)行了分析，并重點(diǎn)研究了QS算法的改進(jìn)思路，最后提出了一種適用于HTTP應(yīng)用數(shù)據(jù)還原的CIQS算法。CIQS算法考慮了HTTP模式串的字符特點(diǎn)，改進(jìn)了模式串的字符比較順序，并對壞字符跳躍思想進(jìn)行了改進(jìn)，增大了跳躍距離。實(shí)驗(yàn)結(jié)果表明，CIQS算法有效減少了匹配次數(shù)，相比其他幾種算法有更好的時間性能。

HTTP還原 模式匹配 CIQS算法

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)安全問題也隨之產(chǎn)生，信息的有效檢測和監(jiān)控已成為一個重要問題。而HTTP協(xié)議是互聯(lián)網(wǎng)上應(yīng)用最廣泛、最重要的通信協(xié)議[1]，對它的通信數(shù)據(jù)的實(shí)時檢測和有效還原顯得十分有必要。

在對HTTP應(yīng)用數(shù)據(jù)還原時，主要利用字符串匹配技術(shù)來提取有用信息，而模式匹配算法正是字符串匹配的重要方法，為了能更快速、精確地對內(nèi)容進(jìn)行識別和還原，需要改進(jìn)匹配算法，提升匹配效率。

本文首先分析了三種典型的單模式匹配算法的優(yōu)缺點(diǎn)，然后重點(diǎn)在QS算法[2]的基礎(chǔ)上進(jìn)行改進(jìn)，并加入了對HTTP模式串字符特點(diǎn)的考慮，提出了一種改進(jìn)算法，稱之為Character Improved Quick Search算法，簡稱為CIQS算法。

1 三種典型的算法

為了方便算法描述，進(jìn)行以下定義：對于長度為n的待匹配文本字符串T=T1T2…Tn和長度為m的模式串P=P1P2…Pm(一般n≥m)，如果對它們進(jìn)行匹配，存在TiTi+1…Ti+mTi+m-1=P1P2…Pm-1Pm(其中1≤i≤n-m+1)，則稱匹配成功，且返回模式串在文本串中匹配的位置，否則稱匹配失敗。

1.1 BM算法

BM算法[3]是由Boyer和Moore在1977提出的單模式匹配算法。其思想是：匹配時，先將模式串和待匹配文本串左對齊，比較從右向左進(jìn)行，若發(fā)生失配，則用壞字符規(guī)則和好后綴規(guī)則來計(jì)算模式串的右移量，它的大小由較大的值決定。

壞字符規(guī)則：當(dāng)文本串字符Ti與模式串字符Pj不匹配時，如果Ti不在模式串中出現(xiàn)，則右移量為m；若Ti在模式串中出現(xiàn)，則移動模式串，使Ti與它在模式串中最右出現(xiàn)的位置對齊，再開始下一輪匹配。右移量的具體確定方法如下

好后綴規(guī)則：在模式串與文本串進(jìn)行匹配時，如果發(fā)現(xiàn)字符Ti≠Pj，而Pj+1…Pm已經(jīng)匹配成功，則偏移量的確定分為兩種情況：當(dāng)模式串中的某一子串Pj-s+1…Pm-s和已匹配部分Pj+1…Pm相同，則模式串需要向右移動的距離為s位；如果Pj+1…Pm的后綴Ps+1…Pm與模式串的前綴P1…Pm-s相同，則右移量為s位。

BM算法的匹配階段，最壞情況的時間復(fù)雜度為O(m*n)。

1.2 BMH算法

Horspool提出的BMH 算法[4]相對于BM算法更易實(shí)現(xiàn)，它在預(yù)處理階段只使用壞字符規(guī)則，對匹配過程中的判斷也做了簡化，當(dāng)字符失配時，僅考慮文本串當(dāng)前窗口的末尾字符來計(jì)算右移量。

BMH算法的匹配思想是：將模式串和文本串左對齊，先匹配文本串當(dāng)前窗口的末尾字符，如果匹配成功，再順序匹配其余的m-1位字符；當(dāng)文本串中有字符發(fā)生失配時，則由文本串當(dāng)前窗口的末尾字符來啟發(fā)模式串向右移動。匹配過程中的失配字符表如下式所示

下面用實(shí)例來說明BMH算法的匹配過程，假設(shè)待匹配的文本串為“catchpostteachmatch”，模式串為“match”，具體匹配的過程如表1所示(加粗字體的字符表示需要比較的字符，點(diǎn)表示不用比較的字符，下同，不再說明)。

表1 BMH算法匹配過程

BMH算法在匹配階段的時間復(fù)雜度為O(m*n)，并沒比BM算法更好，但是BMH算法簡化了初始化的過程，減少了比較次數(shù)，因此在實(shí)際使用情況時要比BM算法的效率高。

1.3 QS算法

QS算法是Daniel M. Sunday在1990年提出的，該算法只采用壞字符規(guī)則，在匹配時把模式串與待匹配字符串左對齊，文本串與模式串的字符比較既可以從左向右也可以從右向左。

QS的思想是：當(dāng)發(fā)生失配時，考慮文本串當(dāng)前匹配窗口的下一位字符來確定模式串向右移動的距離，然后產(chǎn)生一個新的窗口，繼續(xù)嘗試下一輪匹配，直到待匹配文本串T結(jié)束為止。匹配過程中的失配字符表如下式所示

繼續(xù)用前面的例子來說明QS算法的匹配過程，匹配過程如表2所示。

表2 QS算法匹配過程

通過比較表1和表2的匹配結(jié)果可以發(fā)現(xiàn)，QS算法的比較次數(shù)和字符比較個數(shù)比BMH算法都要小一些，跳躍的距離更大。

QS算法在匹配階段的時間復(fù)雜度仍為O(m*n)，但是它進(jìn)一步減少了比較次數(shù)并增大了跳躍距離，因此QS算法的效率更高。

1.4 改進(jìn)算法的提出

通過上面對三種典型算法的分析和比較可知，QS算法的最大移動距離可以達(dá)到m+1，比BM算法和BMH算法都要大，一定程度上的匹配效率最優(yōu)。因此在考慮將單模式匹配算法應(yīng)用到HTTP協(xié)議檢測還原中時，優(yōu)先考慮使用QS算法。

但是QS算法僅用一個字符來計(jì)算右移量，會增加一些不必要的字符比較和移動；此外，在某些情況下，QS算法的效率不如BMH算法[5]；最后，適當(dāng)?shù)淖址容^順序?qū)ζヅ湫室灿幸欢ǖ奶嵘；谶@些考慮，本文提出了一種對QS算法進(jìn)行改進(jìn)的單模式匹配算法：CIQS算法。

2 CIQS算法思想與實(shí)現(xiàn)

2.1 對QS算法的改進(jìn)

通過上面的分析，發(fā)現(xiàn)QS算法在增大跳躍距離以及減少字符比較次數(shù)方面還有很多改進(jìn)的空間，對它的改進(jìn)主要考慮三個方面。

1)第一個方面：由于QS算法只用一個字符計(jì)算右移量，會增加一些不必要的字符比較和移動。針對此問題提出的改進(jìn)算法有很多，其中曾傳璜等人提出的Sunday2算法：利用窗口對文本串進(jìn)行切片，使模式串的最大右移量從m+1增加到2m+1，有效減少了字符匹配次數(shù)，提高了算法的性能[6]。但是Sunday2算法也有不足，它在預(yù)處理階段使用兩個壞字符函數(shù)，即要建立兩個預(yù)處理表，增大了計(jì)算開銷。

CIQS算法對此做的改進(jìn)：在預(yù)處理階段仍然只使用QS算法的壞字符規(guī)則，并對匹配過程進(jìn)行了改進(jìn)，詳述在2.2節(jié)。CIQS算法的最大右移量仍可達(dá)到2m+1，如圖1所示。

圖1 最大右移距離對比

由圖1的結(jié)果可以看出，當(dāng)字符發(fā)生失配時，QS算法使模式串向右移動了6位，而CIQS算法使模式串向右移動了11位，即模式串移動了更大的距離，減少了字符匹配次數(shù)。

2)第二個方面：考慮文本串當(dāng)前窗口的末尾字符Ti+m-1沒有在模式串中出現(xiàn)而Ti+m在模式串中出現(xiàn)時的情況，如圖2所示，這里待匹配文本串都用“contentmatch”，模式串用“match”，并從同一位置開始匹配。

圖2 QS與BMH匹配對比

由圖2可知，當(dāng)發(fā)生失配時，用QS算法計(jì)算的右移量為2，用BMH算法計(jì)算的值為5，此時QS算法的效率反而沒有BMH算法高。

CIQS算法做的改進(jìn)：當(dāng)字符發(fā)生失配時，如果當(dāng)前窗口末尾字符的下一位字符在模式串中，則繼續(xù)判斷當(dāng)前窗口的末尾字符是否在模式串中，如果沒在，則右移距離增大為m，否則不變，借此增大了右移距離。

3)第三個方面：針對HTTP應(yīng)用數(shù)據(jù)還原時的模式串的特點(diǎn)，設(shè)計(jì)適當(dāng)?shù)淖址容^順序，可以有效減少字符比較次數(shù)，提高算法匹配效率。

對HTTP應(yīng)用數(shù)據(jù)還原時會用到的一部分模式串進(jìn)行了整理，比如有content、title、email、word、me-ssage、username、nickname、subject等，這些模式串的特點(diǎn)是：大多為一些常用單詞或是與常用單詞十分相近的字符串，其后綴通常比較常見，在單詞表中存在大量的與它們相同后綴的單詞[7]。

由于QS算法大多采用從右向左的順序來比較字符，如果在文本串中存在很多與模式串同后綴的字符串，則在匹配時就會出現(xiàn)如圖3所示的情況：即在模式串的末尾字符附近會連續(xù)成功匹配多個字符，但是直到模式串的首字符附近才出現(xiàn)不匹配，這顯然增加了大量不必要的字符比較，因此QS算法在這個應(yīng)用背景下還有改進(jìn)的空間。

圖3 字符比較順序?qū)Ρ?/p>

CIQS算法對此做的改進(jìn)：在QS算法從右向左順序比較字符的基礎(chǔ)上做了改進(jìn)，在匹配的過程中，先匹配文本串當(dāng)前窗口的末尾字符Ti+m-1，如果末尾字符已經(jīng)匹配成功，不再繼續(xù)匹配末尾字符的前一個字符Ti+m-2，而是先去匹配文本串當(dāng)前窗口的首字符Ti，當(dāng)首字符和尾字符都匹配成功的情況下，再去逐個匹配剩余的字符。

2.2 CIQS算法的實(shí)現(xiàn)

CIQS算法的實(shí)現(xiàn)分為預(yù)處理和匹配處理兩部分。在預(yù)處理階段，CIQS算法與QS算法的處理方式相同，都是利用壞字符表函數(shù)求出文本串中每個字符的偏移量。而在匹配處理階段，CIQS算法的匹配步驟可以表述如下：

1)將模式串P和待匹配文本串T左對齊，形成當(dāng)前窗口。

2)在當(dāng)前窗口中先從末尾字符Ti+m開始匹配，如果成功，則去匹配首字符Ti，當(dāng)首字符和末尾字符同時匹配成功時，再繼續(xù)匹配剩余字符，當(dāng)全部匹配成功或出現(xiàn)失配時，當(dāng)前窗口字符匹配結(jié)束，然后求出模式串P的右移量。

3)如果右移量不是m+1，要繼續(xù)判斷Ti+m-1是否在模式串中出現(xiàn)，如果Ti+m-1不在則右移量增加到，m否則不變。

4)如果模式串的右移量是m+1，接著判斷文本串下一窗口的尾字符Ti+2m是否在模式串中，如果不在，則右移量為2m+1，否則不變。

5)模式串每次都根據(jù)右移量向右移動相應(yīng)距離，產(chǎn)生一個新的窗口，繼續(xù)嘗試下一輪匹配；如果模式串與文本串匹配成功，則返回在文本串中對應(yīng)的位置。

6)當(dāng)文本串的指針位置超出了文本串長度時，說明匹配過程結(jié)束。整個匹配處理階段的算法邏輯流程如圖4所示。

圖4 匹配過程流程

2.3 CIQS算法的性能分析

為了分析改進(jìn)算法的性能優(yōu)勢，將CIQS算法與BMH算法和QS算法進(jìn)行對比，繼續(xù)用前面提到的例子來說明CIQS的匹配過程，即假設(shè)待匹配的文本串為“catchpostteachmatch”，模式串為“match”，匹配的過程如表3所示。

表3 CIQS算法匹配過程

通過對比表1、表2和表3的匹配過程可以發(fā)現(xiàn)，當(dāng)文本字符串中出現(xiàn)多個與模式串有相同后綴的字符時(這里為“atch”)，CIQS算法做的字符比較次數(shù)明顯減少；且在某些情況下，CIQS算法的最大右移量可以達(dá)到2m+1，增大了移動距離。

3 實(shí)驗(yàn)測試與結(jié)果

由上面的分析可知，CIQS算法在理論上有更好的性能。為了測試該算法的效率，將用實(shí)驗(yàn)驗(yàn)證。

實(shí)驗(yàn)在虛擬機(jī)上進(jìn)行，實(shí)驗(yàn)環(huán)境：物理機(jī)系統(tǒng)Windows 7，配置為Intel(R) Core(TM)2 T5750， 2.10 GHz，2 GB內(nèi)存；虛擬機(jī)為VMware Workstation 8，系統(tǒng)為CentOS5.2，內(nèi)存1 GB，采用C++編程。

待匹配文本：用抓包軟件抓取一些諸如網(wǎng)頁論壇、網(wǎng)頁搜索、郵件等通信數(shù)據(jù)包，并隨機(jī)地將一些已重組的HTTP應(yīng)用層數(shù)據(jù)保存成txt文件，大小為6.9 MB。模式串：從待匹配樣本中隨機(jī)選取6個長度分別為3、4、5、6、7、8的字符串。

對不同長度的每個模式串，分別用BMH算法、QS算法和CIQS算法對樣本進(jìn)行匹配，統(tǒng)計(jì)匹配成功次數(shù)，并對每次匹配過程進(jìn)行計(jì)時。算法匹配成功次數(shù)統(tǒng)計(jì)結(jié)果如表4所示。

表4 三種算法匹配成功次數(shù)

從表4的結(jié)果可以看出，在不同的模式串長度下，使用BMH算法、QS算法和CIQS算法的匹配成功次數(shù)是一樣的，說明模式串在待匹配的文本串中已全部被找出，CIQS算法沒有出現(xiàn)漏報，該算法在查找字符串的準(zhǔn)確率上具有一定的可靠性。

對同一個模式串用三種算法做耗時比較，分別重復(fù)匹配過程10次，對運(yùn)行時間取平均值后的統(tǒng)計(jì)結(jié)果如圖5所示。

圖5 算法匹配時間對比

由圖5的結(jié)果可以看出，BMH算法、QS算法和CIQS算法在模式串長度增大的情況下，它們所需的匹配時間都在逐漸減小，這是因?yàn)檫@三種算法的最大安全跳躍距離都與模式串長度m有關(guān)，m越大，跳躍的距離就越大，匹配時間就越短。

此外，在同一個長度的模式串下，比較三種算法的運(yùn)行時間，發(fā)現(xiàn)CIQS算法的匹配耗時最少，且隨著模式串長度的增加，CIQS算法比QS算法有更優(yōu)越的時間性能，這是因?yàn)殡S著模式串長度的增加，文本串中出現(xiàn)與模式串相同后綴的機(jī)率也增大，因此改進(jìn)算法的優(yōu)勢就會體現(xiàn)出來，使字符比較次數(shù)減少，提升了匹配效率。

實(shí)驗(yàn)說明CIQS算法比QS算法有更大的安全跳躍距離和更少的字符匹配次數(shù)，在HTTP應(yīng)用數(shù)據(jù)還原中有更好的時間性能。

4 結(jié) 語

本文在對BM算法、BMH算法和QS算法進(jìn)行了分析和比較，重點(diǎn)對QS算法進(jìn)行了改進(jìn)，在理論上證明了CIQS算法的可行性，并通過實(shí)驗(yàn)驗(yàn)證了該算法在HTTP數(shù)據(jù)還原應(yīng)用場景下的良好性能。但是隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)協(xié)議檢測還原中的模式匹配算法逐漸向多模式匹配方向發(fā)展，多模式匹配算法有更好的效率，因此如何對CIQS算法進(jìn)行改進(jìn)，使其從單模式匹配向多模式匹配技術(shù)方向發(fā)展是下一步的方向研究。

[1] 陳雷,劉嘉勇.基于HTTP協(xié)議的POST數(shù)據(jù)分析與還原[J].通信技術(shù),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ìn)的單模式匹配算法[J].制造業(yè)自動化,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].江西理工大學(xué)學(xué)報,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—)，男，博士，教授，博士生導(dǎo)師，主要研究方向?yàn)樾畔踩?/p>

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—)，男，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)通信與網(wǎng)絡(luò)安全；

10.3969/j.issn.1002-0802.2015.03.020

2014-09-05；

2014-12-21