李 濤 胡愛群 高 尚

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

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

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

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

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

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

1 系統(tǒng)設計

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

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

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

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

2 基于塊的BM 算法

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

2.1 BM 算法

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

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

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

好后綴規(guī)則為

式中，k 為已匹配成功的字符串長度;shift(pm-k)為pm-k匹配失敗時P 右移的長度;r 為對于任意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é)議安全檢測環(huán)境中，匹配對象有其固有的特性:通常協(xié)議幀的格式由不同塊組成，不同塊之間由特定的分割符號來區(qū)分，或者是有固定的塊長度.因此，在進行匹配檢測時以數(shù)據(jù)塊為單位，而非以字符為單位.例如，對于一個由{aa}，{bbbb}，{ccc}，0m0gwwy組成的目標串{aa，bbbb，ccc，d}以及由{ccc}，qomeg8c組成的模式串{ccc，d}，直接應用BM 算法匹配，經(jīng)過第1 次右移后的結(jié)果見圖3.由圖可知，模式串的塊與目標串的塊并未對齊，從而導致效率降低.

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

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

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

2.2 BB-BM 算法

針對2.1 節(jié)中的問題，在協(xié)議安全檢測的應用場景下，本文對BM 算法進行了改進，提出了BBBM 算法.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 性能分析

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

表1 Hash 轉(zhuǎn)換對應關系

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

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

圖6 4 種算法的效率比較

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

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

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

表2 4種算法的性能比較

4 結(jié)語

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

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

References)

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

［2］ 馮登國，范紅.安全協(xié)議形式化分析理論與方法研究綜述［J］.中國科學院研究生院學報，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］.電子測試，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.