基于BB-BM 算法的網(wǎng)絡(luò)協(xié)議內(nèi)容符合性測(cè)試方法

李 濤 胡愛(ài)群 高 尚

(1 東南大學(xué)信息科學(xué)與工程學(xué)院，南京210096)

(2 香港理工大學(xué)電子計(jì)算學(xué)系，香港999077)

網(wǎng)絡(luò)通信協(xié)議的實(shí)現(xiàn)依據(jù)標(biāo)準(zhǔn)協(xié)議規(guī)范，但由于不同實(shí)現(xiàn)者對(duì)協(xié)議有著不同的理解，設(shè)計(jì)的通信設(shè)備可能不盡相同.攻擊者可以通過(guò)對(duì)安全協(xié)議進(jìn)行部分修改以降低協(xié)議的安全性，竊取使用者數(shù)據(jù).目前，主要利用一致性檢測(cè)方法來(lái)研究實(shí)際通信協(xié)議與標(biāo)準(zhǔn)協(xié)議之間的差異［1］.但協(xié)議一致性檢測(cè)偏重于對(duì)協(xié)議運(yùn)行狀態(tài)的檢測(cè)，針對(duì)協(xié)議內(nèi)容字段的檢測(cè)方法則較為缺乏，從而導(dǎo)致在檢測(cè)結(jié)果不一致的情況下，無(wú)法判斷協(xié)議實(shí)現(xiàn)者是對(duì)標(biāo)準(zhǔn)協(xié)議進(jìn)行了更加安全的修改還是省略部分安全過(guò)程以達(dá)到非法目的［2］.因此，在協(xié)議一致性檢測(cè)之后，需要對(duì)協(xié)議的內(nèi)容進(jìn)行符合性檢測(cè).

內(nèi)容符合性檢測(cè)通過(guò)模式識(shí)別方法來(lái)判斷協(xié)議實(shí)現(xiàn)是否與協(xié)議標(biāo)準(zhǔn)規(guī)定的字段內(nèi)容相符.對(duì)于模式識(shí)別方法，關(guān)鍵問(wèn)題是如何增加跳躍距離來(lái)減少匹配次數(shù)，最后達(dá)到降低匹配時(shí)間、提高算法效率的目的［3］.

在模式識(shí)別方法的研究中，暴力匹配(BF)算法最先被引入［4］，該算法順序比較字符串中每個(gè)字符，但由于對(duì)回溯的處理過(guò)于簡(jiǎn)單導(dǎo)致算法效率較低，匹配的時(shí)間復(fù)雜度為O(mn)，其中m，n 分別為模式串和目標(biāo)串長(zhǎng)度.針對(duì)BF 算法的不足，Cook［5］從理論上論證了模式匹配問(wèn)題可以在O(m+n)時(shí)間內(nèi)解決.基于此思想，Sunday［6］提出了KMP 算法，Cho 等提出了BM 算法［7］，匹配效率都得到了提高.尤其是BM 算法，其通過(guò)逆向匹配思想最大限度地增加了匹配失敗時(shí)的跳躍距離，減少了匹配字符數(shù)目，在最優(yōu)情況下算法的時(shí)間復(fù)雜度減少到O(n/m);但由于匹配過(guò)程中規(guī)則較多，實(shí)現(xiàn)過(guò)程相對(duì)復(fù)雜.基于此，學(xué)者們對(duì)BM 算法進(jìn)行了改進(jìn)，出現(xiàn)了BMH 算法［8］和BMHS 算法［9］，即利用BM 算法中壞字符跳躍規(guī)則，將最大跳躍距離分別增大到m 和m +1;但這些算法并沒(méi)有解決BM 算法中模式串與目標(biāo)串之間塊未對(duì)齊的問(wèn)題，導(dǎo)致匹配效率較低，甚至在塊匹配時(shí)會(huì)產(chǎn)生不可預(yù)知的錯(cuò)誤.

本文設(shè)計(jì)了一種針對(duì)協(xié)議內(nèi)容符合性的測(cè)試方法，并針對(duì)該方法下的特殊模式匹配環(huán)境，將BM 算法進(jìn)行了改進(jìn)，提出了一種基于塊的BM(BB-BM)算法，以提高檢測(cè)效率.

1 系統(tǒng)設(shè)計(jì)

協(xié)議安全檢測(cè)是根據(jù)相關(guān)標(biāo)準(zhǔn)中描述的語(yǔ)義、語(yǔ)法、時(shí)序，對(duì)具體實(shí)現(xiàn)的協(xié)議進(jìn)行符合性檢測(cè)［10］.在測(cè)試過(guò)程中，通常將測(cè)試對(duì)象看作一個(gè)無(wú)法打開(kāi)的黑盒，在不考慮黑盒內(nèi)部結(jié)構(gòu)與實(shí)現(xiàn)的前提下，通過(guò)黑盒提供的接口對(duì)其進(jìn)行測(cè)試.因此，對(duì)某個(gè)協(xié)議的檢測(cè)，需要在與待測(cè)設(shè)備通信的另一端進(jìn)行，通過(guò)相關(guān)接口與測(cè)試對(duì)象交互操作.這就需要在設(shè)計(jì)通信協(xié)議安全檢測(cè)方法時(shí)，將檢測(cè)系統(tǒng)與協(xié)議服務(wù)器分離.

在進(jìn)行協(xié)議安全檢測(cè)時(shí)各實(shí)體之間的關(guān)系如圖1所示.圖中，被測(cè)實(shí)現(xiàn)是指待檢測(cè)協(xié)議的客戶端軟件實(shí)現(xiàn);協(xié)議服務(wù)器是指被測(cè)協(xié)議的服務(wù)器端，其功能是在收到被測(cè)實(shí)現(xiàn)的反饋數(shù)據(jù)后，將數(shù)據(jù)交付至協(xié)議安全檢測(cè)系統(tǒng)進(jìn)行檢測(cè)，在檢測(cè)完成后，反饋協(xié)議服務(wù)器信息，根據(jù)反饋信息對(duì)被測(cè)實(shí)現(xiàn)進(jìn)行響應(yīng);協(xié)議安全檢測(cè)系統(tǒng)是實(shí)現(xiàn)協(xié)議內(nèi)容符合性檢測(cè)的核心，在收到協(xié)議服務(wù)器的報(bào)文輸入后，通過(guò)分析正常檢測(cè)序列與被測(cè)實(shí)現(xiàn)之間的完整通信數(shù)據(jù)，判斷報(bào)文各字段的內(nèi)容是否與標(biāo)準(zhǔn)協(xié)議中的規(guī)定相符，檢測(cè)流程見(jiàn)圖2.

圖1 協(xié)議安全檢測(cè)系統(tǒng)檢測(cè)框架

圖2 內(nèi)容符合性檢測(cè)流程

2 基于塊的BM 算法

匹配算法是協(xié)議內(nèi)容符合性檢測(cè)的核心.本文針對(duì)協(xié)議安全檢測(cè)環(huán)境，對(duì)BM 算法進(jìn)行改進(jìn)，提出了基于塊的BM 算法，以提高檢測(cè)效率.

2.1 BM 算法

BM 算法的特點(diǎn)是從模式串的尾部開(kāi)始匹配.在模式串和目標(biāo)串對(duì)齊后，從最右邊的對(duì)齊位置開(kāi)始向左逐個(gè)進(jìn)行掃描匹配.在一輪匹配結(jié)束后，BM 算法采用壞字符規(guī)則和好后綴規(guī)則2 種啟發(fā)式規(guī)則將窗口右移.

假設(shè)P={p1，p2，…，pm}為模式串，T={t1，t2，…，tn}為目標(biāo)串，則壞字符規(guī)則為

式中，tj為匹配成功字符;skip(tj)為tj處失敗時(shí)P右移的長(zhǎng)度;location(tj)為tj在P 中出現(xiàn)的位置;m 為模式串長(zhǎng)度.

好后綴規(guī)則為

式中，k 為已匹配成功的字符串長(zhǎng)度;shift(pm-k)為pm-k匹配失敗時(shí)P 右移的長(zhǎng)度;r 為對(duì)于任意s，滿足{pm-r+1，pm-r+2，…，pm}={ps-r+1，ps-r+2，…，ps}條件的最大值;s 為在確定r 之后，滿足{pm-r+1，pm-r+2，…，pm}= {ps-r+1，ps-r+2，…，ps}條件的最大值.

BM 算法是一種高效的模式匹配算法，但在協(xié)議安全檢測(cè)環(huán)境中，匹配對(duì)象有其固有的特性:通常協(xié)議幀的格式由不同塊組成，不同塊之間由特定的分割符號(hào)來(lái)區(qū)分，或者是有固定的塊長(zhǎng)度.因此，在進(jìn)行匹配檢測(cè)時(shí)以數(shù)據(jù)塊為單位，而非以字符為單位.例如，對(duì)于一個(gè)由{aa}，{bbbb}，{ccc}，g0gggggg組成的目標(biāo)串{aa，bbbb，ccc，d}以及由{ccc}，g0gggggg組成的模式串{ccc，d}，直接應(yīng)用BM 算法匹配，經(jīng)過(guò)第1 次右移后的結(jié)果見(jiàn)圖3.由圖可知，模式串的塊與目標(biāo)串的塊并未對(duì)齊，從而導(dǎo)致效率降低.

圖3 BM 算法的匹配結(jié)果

針對(duì)好后綴規(guī)則，令本輪模式串和目標(biāo)串對(duì)應(yīng)的位置如圖4所示.由圖可知，{t4，t5}={p4，p5}={a，b}為好后綴，并且t3≠p3.由于{p2，p3}={p4，p5}，p1≠p3，則好后綴將使p1和t3對(duì)齊.如果p1≠t3，對(duì)p2，p3，p4，p5進(jìn)行匹配是無(wú)意義的.

圖4 好后綴規(guī)則示例

2.2 BB-BM 算法

針對(duì)2.1 節(jié)中的問(wèn)題，在協(xié)議安全檢測(cè)的應(yīng)用場(chǎng)景下，本文對(duì)BM 算法進(jìn)行了改進(jìn)，提出了BBBM 算法.

首先，在使用好后綴規(guī)則前，使用一次壞字符規(guī)則來(lái)進(jìn)行對(duì)齊決策.改進(jìn)后的好后綴規(guī)則為

式中，tbad為好后綴中的壞字符.在此規(guī)則下，字符串將持續(xù)移動(dòng)直到tbad=ps-r.

其次，將以字符為單位進(jìn)行匹配改成以塊為單位進(jìn)行匹配，并對(duì)每一個(gè)塊進(jìn)行Hash 操作，將得到的數(shù)據(jù)重新組成一個(gè)新的序列進(jìn)行匹配.對(duì)于模式串的右移，BB-BM 算法繼承了壞字符和好后綴規(guī)則，僅將距離單位由字符長(zhǎng)度改為塊長(zhǎng)度.

BB-BM 算法的匹配步驟如下:

①估算目標(biāo)串中塊的數(shù)目b.若估算困難，計(jì)算目標(biāo)串中塊的數(shù)目，保證Hash 函數(shù)的值域足夠使用.

②根據(jù)估算的數(shù)目來(lái)決定Hash 函數(shù)值域的空間大小，S=log(b +1).

③依次將模式串和目標(biāo)串中的每一個(gè)塊進(jìn)行Hash 操作.對(duì)于較小的值域空間，可以依次賦值.例如，對(duì)于一個(gè)S=4 bit 的空間，可將第1 塊轉(zhuǎn)化為0001 B，第2 塊轉(zhuǎn)化為0010 B，以此類推.在尾部需要定義結(jié)尾字符，如采用0000 B 來(lái)標(biāo)注模式串和目標(biāo)串的結(jié)尾.

④轉(zhuǎn)換完成后對(duì)模式串和目標(biāo)串進(jìn)行拼接，以塊為單位進(jìn)行模式匹配.

3 系統(tǒng)實(shí)現(xiàn)與性能分析

采用本文提出的測(cè)試方法對(duì)網(wǎng)絡(luò)傳輸中常用的IPSec 和HTTP 協(xié)議進(jìn)行內(nèi)容符合性分析和測(cè)試.

3.1 協(xié)議內(nèi)容符合性分析

協(xié)議內(nèi)容符合性測(cè)試的流程如圖5所示.IPSec 協(xié)議簇中起最主要作用的是IKE，AH 協(xié)議和ESP 協(xié)議，其中IKE 是實(shí)現(xiàn)安全功能的核心，對(duì)其進(jìn)行內(nèi)容符合性檢測(cè)尤為重要.首先，對(duì)IKE 協(xié)議頭進(jìn)行分段.根據(jù)RFC4306 中的IPSec 協(xié)議規(guī)范，IKE 協(xié)議頭包含4 種內(nèi)容類型，其值域空間大小S=「log(4 +1)?=3 bit;然后，對(duì)模式串和目標(biāo)串分塊進(jìn)行Hash 操作，生成新的模式串及目標(biāo)串;最后，對(duì)轉(zhuǎn)換后的數(shù)據(jù)進(jìn)行模式匹配.

圖5 內(nèi)容符合性分析流程圖

對(duì)HTTP 進(jìn)行內(nèi)容符合性檢測(cè)，首先參考RFC2616 標(biāo)準(zhǔn)規(guī)范對(duì)HTTP 頭進(jìn)行分段處理;例如request-line 中的Method 字段，標(biāo)準(zhǔn)規(guī)范定義了OPTIONS，GET，HEAD，POST，PUT，DELETE，TRACE，CONNECT 共8 種類型，因此其值域空間大小S=「log(8 +1)?=4 bit.然后，分別對(duì)模式串和目標(biāo)串進(jìn)行Hash 操作，生成新的模式串和目標(biāo)串.最后，利用BB-BM 算法進(jìn)行模式匹配.

3.2 性能分析

采用本文所提方法，對(duì)由{aa}，{bbbb}，{ccc}，g0gggggg組成的目標(biāo)串{aa，bbbb，ccc，d}以及由{ccc}，g0gggggg組成的模式串{ccc，d}進(jìn)行測(cè)試.首先，分析得到目標(biāo)串中塊的數(shù)量為4，計(jì)算得值域空間大小S=「log(4 +1)?=3 bit.然后，對(duì)每一塊進(jìn)行Hash 操作.為方便描述，將每一塊的轉(zhuǎn)換結(jié)果使用符號(hào)記錄，轉(zhuǎn)換關(guān)系如表1所示.經(jīng)過(guò)Hash 操作轉(zhuǎn)換后，模式串為{CD}，目標(biāo)串為{ABCD}.最后，進(jìn)行模式匹配，僅需右移1 次，即可得到預(yù)期結(jié)果.

表1 Hash 轉(zhuǎn)換對(duì)應(yīng)關(guān)系

下面對(duì)BF 算法、KMP 算法、BM 算法以及BB-BM 算法進(jìn)行性能比較.利用100 ～500 KB 的目標(biāo)串和5 KB 的模式串進(jìn)行測(cè)試.在使用BB-BM算法進(jìn)行塊轉(zhuǎn)換操作時(shí)，將模式串和目標(biāo)串的塊大小統(tǒng)一為8 B.為了消除誤差影響，采用對(duì)100 次測(cè)量結(jié)果取均值的方法.

圖6描述了4 種算法的時(shí)間消耗.由于模式串和目標(biāo)串的內(nèi)容對(duì)模式匹配算法的效率影響較大，因此對(duì)于不同目標(biāo)串和模式串的選擇，時(shí)間消耗可能存在差別.

圖6 4 種算法的效率比較

由圖6可知，由于BF 算法消耗時(shí)間過(guò)長(zhǎng)，當(dāng)處理時(shí)間大于500 ms 時(shí)不再顯示.BM 算法的最優(yōu)情況在匹配對(duì)象擁有特定格式時(shí)才會(huì)出現(xiàn)，故在小文件處理過(guò)程中，其效率可能低于KMP 算法.但KMP 算法在處理大文件時(shí)，時(shí)間消耗增長(zhǎng)較快;相反，BM 算法處理大文件的時(shí)間增長(zhǎng)則不明顯.BB-BM 算法繼承了BM 算法的優(yōu)點(diǎn)，性能相對(duì)于BM 算法有所提高，但由于需要進(jìn)行Hash 操作，其時(shí)間消耗并未達(dá)到理想的理論值.

4 種算法的性能比較結(jié)果見(jiàn)表2.由表可知，BB-BM 算法的匹配效率與模式串和目標(biāo)串塊的數(shù)量相關(guān).假設(shè)Hash 操作后模式串的塊數(shù)為M，目標(biāo)串的塊數(shù)為N，則最優(yōu)時(shí)間復(fù)雜度為O(N/M)，最差時(shí)間復(fù)雜度為O(MN).而B(niǎo)M 算法的最優(yōu)時(shí)間復(fù)雜度為O(n/m)，最差退化到O(mn);基于BM 算法改進(jìn)的BMH 算法和BMHS 算法在時(shí)間復(fù)雜度上相對(duì)于BM 算法并未有較大改善.對(duì)于本文中的檢測(cè)示例，Hash 轉(zhuǎn)換之前的目標(biāo)串和模式串大小分別為10 和4，使用BM 算法的最優(yōu)和最差時(shí)間復(fù)雜度分別為O(2.5)和O(40).使用BBBM 算法時(shí)，經(jīng)過(guò)Hash 轉(zhuǎn)換后目標(biāo)塊串和模式塊串大小分別為4 和2，最好和最差時(shí)間復(fù)雜度分別為O(2)和O(8)，檢測(cè)性能相對(duì)于使用BM 算法分別提高了20%和80%.雖然最好時(shí)間復(fù)雜度對(duì)于BM 算法沒(méi)有明顯降低，但最壞情況的時(shí)間復(fù)雜度明顯降低，其平均效率明顯提升.

傳統(tǒng)的BF 算法、KMP 算法和BM 算法適用于任何需要進(jìn)行模式匹配的場(chǎng)景，適用范圍更加廣泛.BB-BM 算法是針對(duì)本文的網(wǎng)絡(luò)協(xié)議內(nèi)容符合性檢測(cè)提出的，要求匹配對(duì)象擁有固定的字段格式以進(jìn)行分塊處理，因此其通用性較差.但在網(wǎng)絡(luò)協(xié)議內(nèi)容符合性檢測(cè)的場(chǎng)景下，BB-BM 算法具有較高的檢測(cè)效率.對(duì)于其他場(chǎng)景，如果模式串和目標(biāo)串可以基于特定格式進(jìn)行劃分，并且可通過(guò)分塊的方式進(jìn)行處理，使用BB-BM 算法也可對(duì)其進(jìn)行模式匹配操作.

表2 4種算法的性能比較

4 結(jié)語(yǔ)

本文針對(duì)網(wǎng)絡(luò)協(xié)議內(nèi)容的符合性測(cè)試提出了一種測(cè)試方法，分析了已有的模式匹配算法應(yīng)用在協(xié)議內(nèi)容符合性測(cè)試中的問(wèn)題，對(duì)BM 算法進(jìn)行了改進(jìn)，提出了BB-BM 算法.理論分析和性能測(cè)試的結(jié)果表明，BB-BM 算法在繼承了BM 算法的優(yōu)點(diǎn)的同時(shí)，檢測(cè)效率得到了提高.

本文的測(cè)試方法適用于構(gòu)建協(xié)議安全測(cè)試系統(tǒng)，基于該方法進(jìn)行協(xié)議內(nèi)容符合性測(cè)試能顯著提高測(cè)試效率.但對(duì)于未知協(xié)議的檢測(cè)，由于無(wú)法通過(guò)服務(wù)器端進(jìn)行控制，故不建議采用本文方法，可以通過(guò)旁路監(jiān)聽(tīng)客戶端和服務(wù)器端的通信數(shù)據(jù)，采用模式識(shí)別和模糊測(cè)試結(jié)合的方法，將被測(cè)實(shí)現(xiàn)與協(xié)議標(biāo)準(zhǔn)進(jìn)行匹配，達(dá)到檢測(cè)的目的.

References)

［1］ Heckel R，Mariani L.Automatic conformance testing of web services［J］.FASE，2005，3442:34-48.

［2］ 馮登國(guó)，范紅.安全協(xié)議形式化分析理論與方法研究綜述［J］.中國(guó)科學(xué)院研究生院學(xué)報(bào)，2003，20(4):389-406.Feng Dengguo，F(xiàn)an Hong.Survey on theories and methods of formal analyses for security protocols［J］.Journal of the Graduate School of the Chinese Academy of Sciences，2003，20(4):389-406.(in Chinese)

［3］ Chen L，Wang W.An improved NSSK protocol and its security analysis based on logic approach［C］//International Conference on Communications，Circuits and Systems.Xiamen，China，2008:772-775.

［4］ Lecroq T.Fast exact string matching algorithms ［J］.Information Processing Letters，2007，102(6):229-235.

［5］ Cook S A.The complexity of theorem-proving procedures［C］//Third Annual ACM Symposium on Theory of Computing.New York，USA，1971:151-158.

［6］ Sunday D M.A very fast substring search algorithm［J］.Communications of the ACM，1990，33(8):132-142.

［7］ Cho S，Na J C，Park K，et al.Fast order-preserving pattern matching ［J］.Combinatorial Optimization and Applications，2013，8287:295-305.

［8］ Rytter W.On maximal suffixes and constant-space linear-time versions of KMP algorithm ［J］.Theoretical Computer Science，2003，299(1/2/3):763-774.

［9］ 畢智超.字符串模式匹配算法的研究及改進(jìn)［J］.電子測(cè)試，2013(20):64-65.Bi Zhichao.The research of improved matching algorithm of string pattern［J］.Electronic Test，2013(20):64-65.(in Chinese)

［10］ Fu Y，Kone O.Security and robustness by protocol testing［J］.IEEE Systems Journal，2014，8(3):699-707.