鄭天明，王韜，郭世澤，李華，趙新杰

(1. 軍械工程學(xué)院 計(jì)算機(jī)工程系，河北 石家莊 050003；2. 北方電子設(shè)備研究所，北京 100083；3. 中國(guó)人民解放軍第六九零九工廠(chǎng)，江蘇 蘇州 215300)

1 引言

當(dāng)前，各種衛(wèi)星網(wǎng)絡(luò)已被廣泛應(yīng)用到民用、軍事領(lǐng)域的各個(gè)角落，對(duì)衛(wèi)星網(wǎng)絡(luò)安全性進(jìn)行分析十分重要，其中協(xié)議識(shí)別是衛(wèi)星網(wǎng)絡(luò)安全性評(píng)估的研究熱點(diǎn)[1]?？臻g協(xié)議是衛(wèi)星網(wǎng)絡(luò)的骨架和神經(jīng)，是維系網(wǎng)絡(luò)正常通信的紐帶，各層協(xié)議在空間信息結(jié)構(gòu)中占有核心地位，通過(guò)對(duì)衛(wèi)星網(wǎng)絡(luò)協(xié)議進(jìn)行識(shí)別與分析，可確定各層協(xié)議類(lèi)型，獲取網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、路由算法、IP地址分布等信息，探測(cè)協(xié)議漏洞或獲取高層信息，在此基礎(chǔ)上進(jìn)行更高層次的安全評(píng)估。

BM算法(boyer-moore algorithm)[2]是最為經(jīng)典的協(xié)議識(shí)別算法，算法主要根據(jù)常用協(xié)議模式串規(guī)則，通過(guò)對(duì)待識(shí)別數(shù)據(jù)特征進(jìn)行分析，從中查找模式串并確定其所在位置，在此基礎(chǔ)上進(jìn)行協(xié)議識(shí)別。BM算法主要適用于模式串較長(zhǎng)、字符集較大的協(xié)議識(shí)別。然而，在衛(wèi)星網(wǎng)絡(luò)中，由于空間數(shù)據(jù)具有特征位長(zhǎng)度短、數(shù)據(jù)字符集小特點(diǎn)（如典型的SCPS-NP[3]協(xié)議特征僅為3bit），傳統(tǒng)的BM算法很難從中獲取協(xié)議特征，存在執(zhí)行效率和識(shí)別準(zhǔn)確度較低問(wèn)題。

為此，本文提出了一種改進(jìn)的BM算法。提出的算法給出了一種計(jì)算空間數(shù)據(jù)中相同比特距離的數(shù)據(jù)預(yù)處理方法，降低字符串長(zhǎng)度；并引入小數(shù)跳進(jìn)機(jī)制，提高了BM算法分組頭匹配效率；在此基礎(chǔ)上應(yīng)用正則表達(dá)式方法進(jìn)行規(guī)則判斷，然后給出了一種基于層次關(guān)系法的多層協(xié)議識(shí)別方法，提高了多層網(wǎng)絡(luò)協(xié)議的識(shí)別效率；最后以應(yīng)用廣泛的SCPS(space communication protocol specification)協(xié)議識(shí)別為例，應(yīng)用提出的算法進(jìn)行了實(shí)驗(yàn)。

2 空間協(xié)議特征分析

空間數(shù)據(jù)在傳輸過(guò)程中具有傳輸時(shí)延長(zhǎng)、信道誤碼率高、非對(duì)稱(chēng)、適合同地面終端進(jìn)行協(xié)議轉(zhuǎn)換等特點(diǎn)[4]。為適應(yīng)這種特點(diǎn)，CCSDS（consultative committee for space data systems）委員會(huì)制訂了空間傳輸協(xié)議棧SCPS。SCPS協(xié)議棧結(jié)構(gòu)如圖1所示，其自下而上包括：物理層、數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、運(yùn)輸層和應(yīng)用層，以及介于網(wǎng)絡(luò)層與傳輸層之間的安全保護(hù)機(jī)制等多層協(xié)議，其中每層又包括若干個(gè)可供組合的協(xié)議[5～9]。

經(jīng)分析，空間數(shù)據(jù)結(jié)構(gòu)特征可歸納如下。

1) 協(xié)議結(jié)構(gòu)層次化，對(duì)空間數(shù)據(jù)進(jìn)行分析需要首先解調(diào)出比特流數(shù)據(jù)，并逐層開(kāi)展協(xié)議分析；

2) 協(xié)議特征位較短，數(shù)據(jù)中模式串不易被識(shí)別；協(xié)議長(zhǎng)度可變，典型模式串識(shí)別方法不具優(yōu)勢(shì)；

3) 鏈路層協(xié)議兼容各種上層協(xié)議，空間數(shù)據(jù)各層具有緊密相關(guān)性，分析網(wǎng)絡(luò)層協(xié)議可獲取傳輸層協(xié)議類(lèi)型，而分析鏈路層協(xié)議卻無(wú)法降低網(wǎng)絡(luò)層協(xié)議分析難度；

4) 數(shù)據(jù)量大，同一時(shí)段內(nèi)截獲的數(shù)據(jù)類(lèi)型多樣，針對(duì)單一協(xié)議的識(shí)別效果不佳；業(yè)務(wù)需求大、種類(lèi)多，衛(wèi)星通信技術(shù)以及協(xié)議更新速度快。

圖1 SCPS協(xié)議棧結(jié)構(gòu)

綜上，空間協(xié)議識(shí)別應(yīng)根據(jù)協(xié)議棧結(jié)構(gòu)進(jìn)行層次分析，分析可選取協(xié)議特征位作為識(shí)別基準(zhǔn)點(diǎn)，參照協(xié)議結(jié)構(gòu)拆分?jǐn)?shù)據(jù)進(jìn)行分析，并在單層協(xié)議識(shí)別基礎(chǔ)上對(duì)多層協(xié)議開(kāi)展分析。

3 基于BM算法的空間協(xié)議識(shí)別分析

將截獲數(shù)據(jù)存儲(chǔ)到一個(gè)字符數(shù)組，將協(xié)議特征轉(zhuǎn)化為特征模式串，可將協(xié)議識(shí)別歸結(jié)為模式串匹配[10,11]問(wèn)題，通過(guò)對(duì)協(xié)議特征和數(shù)據(jù)進(jìn)行逐位匹配，可分析出協(xié)議類(lèi)型。BM 算法[2]是最具有代表性的模式串匹配算法，識(shí)別速度較快，執(zhí)行時(shí)間復(fù)雜度為O(n+σm)[12]，σ為模式串在數(shù)據(jù)中出現(xiàn)頻率相關(guān)變量，m、n分別為模式串、目標(biāo)串長(zhǎng)度。如果模式串頻繁出現(xiàn)，BM算法在查找階段時(shí)間復(fù)雜度可以表示為O(mn)，最好時(shí)間復(fù)雜度是O(n/m)。

圖2為應(yīng)用BM算法對(duì)基于比特、英文字母字符集的匹配對(duì)比。易見(jiàn)，字符集{0，1}所生成的數(shù)據(jù)，每位出現(xiàn)0、1的概率為50%。應(yīng)用BM算法進(jìn)行模式串匹配時(shí)，在模式串跳進(jìn)過(guò)程中遇到干擾項(xiàng)概率較高、跳進(jìn)距離較短、誤判率較高、任意4bit出現(xiàn)模式串概率為6.25%。相比較而言，由字符集合{a～z}所生成的模式串，每項(xiàng)出現(xiàn)概率僅為3.8%，跳進(jìn)過(guò)程中遇到干擾項(xiàng)概率較小，跳進(jìn)距離也相對(duì)較大，誤判率較低，任意4bit出現(xiàn)模式串的概率約為0.000 207 9%。

圖2 應(yīng)用BM算法對(duì)不同字符集的模式串匹配對(duì)比

為提高模式串匹配效率，現(xiàn)有研究大都著眼于改進(jìn)BM算法的模式串跳進(jìn)方式，研究者相繼提出了 QS[13]、RSPS[14]、Wu Manber和 SBOM[15](set backward Oracle matching)等算法。以SBOM算法為例，算法的預(yù)處理過(guò)程是根據(jù)所有模式串構(gòu)造匹配使用的Oracle結(jié)構(gòu)，以識(shí)別匹配窗口內(nèi)最長(zhǎng)字串，其算法復(fù)雜度為p為命中密度，α為字符集大小。

通過(guò)對(duì)上述幾種算法進(jìn)行對(duì)比分析不難發(fā)現(xiàn)：改進(jìn)的BM算法在命中密度低（模式串較長(zhǎng)、字符集較大[16]）情況下識(shí)別效率極高[17]，應(yīng)用到漢字搜索等領(lǐng)域，可有效提高匹配效率。但隨命中密度的增大，上述算法的識(shí)別效率將急劇降低（在處理0、1數(shù)據(jù)時(shí)，字符集較小所以p極大，SBOM的復(fù)雜度約為O(mn)，接近于BM算法）。

總的來(lái)說(shuō)，應(yīng)用BM算法及其改進(jìn)算法進(jìn)行空間協(xié)議識(shí)別存在以下不足：模式串長(zhǎng)度較短，字符集元素有限（只有0、1組成），模式串跳進(jìn)和識(shí)別效率低下；即使增大模式串長(zhǎng)度，將不可避免增多模式串中通配符數(shù)量，降低BM算法識(shí)別效率。

4 改進(jìn)的空間協(xié)議識(shí)別算法

4.1 主要思想

為解決應(yīng)用BM算法進(jìn)行空間協(xié)議識(shí)別問(wèn)題，我們提出了一種改進(jìn)算法。通過(guò)對(duì)空間數(shù)據(jù)進(jìn)行預(yù)處理，增大模式串字符集；然后改進(jìn)模式串跳進(jìn)規(guī)則，提高數(shù)據(jù)識(shí)別效率，形成數(shù)據(jù)分組；通過(guò)分組標(biāo)識(shí)使用特定DFA匹配引擎，抑制DFA狀態(tài)數(shù)膨脹，實(shí)現(xiàn)單層協(xié)議識(shí)別；在此基礎(chǔ)上結(jié)合多層協(xié)議間關(guān)聯(lián)關(guān)系，縮小多層協(xié)議識(shí)別范圍，并調(diào)整匹配順序，提高多層協(xié)議識(shí)別效率和準(zhǔn)確度。應(yīng)用改進(jìn)算法進(jìn)行空間數(shù)據(jù)分析過(guò)程如圖3所示。

圖3 基于CRB算法的數(shù)據(jù)分析過(guò)程

4.2 基于比特距離的空間數(shù)據(jù)預(yù)處理

在協(xié)議識(shí)別前，常需先將數(shù)據(jù)轉(zhuǎn)換為比特流，基于比特流進(jìn)行協(xié)議分析。由于信道誤碼等原因可造成部分比特?cái)?shù)據(jù)誤碼，主要表現(xiàn)為2個(gè)方面：首先，數(shù)據(jù)內(nèi)容倒置，在這種情況下，如果直接將比特?cái)?shù)據(jù)按照十六進(jìn)制方式進(jìn)行存儲(chǔ)，將1bit誤碼存儲(chǔ)后造成1byte誤碼，即誤碼放大，因此，基于軟件系統(tǒng)的協(xié)議分析，比特流中的每1bit通常按照字符（字節(jié)）進(jìn)行存儲(chǔ)，文中稱(chēng)為字節(jié)流；其次，數(shù)據(jù)首字符難于確定，通常的分析方式無(wú)法判斷數(shù)據(jù)起始位置，將造成大量錯(cuò)誤分析，將BM算法同正則表達(dá)式方法結(jié)合起來(lái)可有效解決該問(wèn)題。

傳統(tǒng)BM算法基于字符進(jìn)行比對(duì)跳進(jìn)，雖然能夠有效解決起始位置難于確定問(wèn)題，但由于空間比特流轉(zhuǎn)換成的“0”和“1”字符較多，且由“0”和“1”組成的字符集數(shù)目較小，導(dǎo)致協(xié)議分析效率低下。為此，文中給出了一種計(jì)算相鄰比特距離的空間數(shù)據(jù)預(yù)處理算法。具體算法如下：選擇字符“1”為特征位，并記錄連續(xù)2個(gè)字符“1”之間的字符“0”的個(gè)數(shù)N，并將N以字節(jié)形式保存。該預(yù)處理算法可增大模式串字符集數(shù)量、提高字符跳進(jìn)距離、降低數(shù)據(jù)分析時(shí)間復(fù)雜度。

圖4為應(yīng)用BM算法對(duì)原始空間數(shù)據(jù)和預(yù)處理后數(shù)據(jù)進(jìn)行識(shí)別的過(guò)程。對(duì)于16byte存儲(chǔ)的“0101000011011011”字節(jié)流，經(jīng)預(yù)處理后可轉(zhuǎn)換為 8byte“11401010”。

根據(jù)第3節(jié)，模式串頻繁出現(xiàn)時(shí)，查找階段時(shí)間復(fù)雜度O(mn)同目標(biāo)串、模式串長(zhǎng)度成正比。文中數(shù)據(jù)預(yù)處理算法可減小模式串長(zhǎng)度m和目標(biāo)串長(zhǎng)度n，降低模式串匹配復(fù)雜度。數(shù)據(jù)查找階段復(fù)雜度可降低到O(mn/4)，預(yù)處理時(shí)間復(fù)雜度為O(n)（在長(zhǎng)度為n數(shù)據(jù)中查找“1”所耗時(shí)間），整體時(shí)間復(fù)雜度為O(n+mn/4)，顯然O(n+mn/4)＜O(mn)，提出算法可加速數(shù)據(jù)分析效率。

由于 BM 算法效率同模式串字符集數(shù)量成反比，在空間數(shù)據(jù)識(shí)別過(guò)程中，傳統(tǒng)模式串字符集僅為“0”、“1”2種，單個(gè)跳進(jìn)距離最多為 1，跳進(jìn)次數(shù)等同于數(shù)據(jù)串長(zhǎng)度。應(yīng)用本節(jié)預(yù)處理算法，模式串字符集可擴(kuò)展至“0到255”256種。當(dāng)數(shù)據(jù)串字符為0時(shí)，跳進(jìn)距離為1，等同于BM算法；而當(dāng)數(shù)據(jù)串字符A大于0時(shí)，單次跳進(jìn)距離為A+1。由圖4可知，應(yīng)用BM算法模式串匹配的平均跳進(jìn)距離為1，跳進(jìn)次數(shù)為16，而應(yīng)用本節(jié)預(yù)處理算法，平均跳進(jìn)距離為 2，跳進(jìn)次數(shù)為 8。易見(jiàn)提出算法增大了BM算法的跳進(jìn)距離，減小了跳進(jìn)次數(shù)，進(jìn)而提高了識(shí)別效率。

4.3 基于小數(shù)跳進(jìn)的模式串查找

在4.2節(jié)對(duì)空間數(shù)據(jù)預(yù)處理的基礎(chǔ)上，本節(jié)給出一種基于小數(shù)跳進(jìn)機(jī)制的數(shù)據(jù)查找算法，可有效改進(jìn)BM算法后綴轉(zhuǎn)移和不良字符轉(zhuǎn)移機(jī)制。

小數(shù)跳進(jìn)機(jī)制基本思想如下：依據(jù)變換后數(shù)據(jù)內(nèi)在意義，即每比特代表變換前數(shù)據(jù)1的前后間隔比特?cái)?shù)，將目標(biāo)串自起始位置起往右一個(gè)模式串長(zhǎng)度的字符與模式串最小值進(jìn)行比較。如果模式串長(zhǎng)度的字符小于模式串最小值，則應(yīng)從目標(biāo)串的下一比特開(kāi)始新一輪匹配，相當(dāng)于把模式串在目標(biāo)串中向右滑過(guò)，即一次跳過(guò)“滑過(guò)距離”個(gè)字符，從而實(shí)現(xiàn)數(shù)據(jù)匹配的快速跳進(jìn)。

算法1給出了基于小數(shù)跳進(jìn)機(jī)制的數(shù)據(jù)查找算法，同BM算法一樣，文中小數(shù)跳進(jìn)機(jī)制也采用從右向左逆向檢索匹配窗口。

算法1 基于小數(shù)跳進(jìn)機(jī)制的數(shù)據(jù)查找算法

圖4 算法對(duì)比

輸入：預(yù)處理后數(shù)據(jù)串T, 模式串P

輸出：模式串匹配位置集合S

小數(shù)跳進(jìn)機(jī)制正確性證明如下。

命題1 已知數(shù)據(jù)T長(zhǎng)度L(T)和模式串P長(zhǎng)度L(P)，在數(shù)據(jù)匹配過(guò)程中，模式串最小值min(P)，若Tx＜min(P)，數(shù)據(jù)T中下一個(gè)大于min(P)位置為T(mén)s，則T從xbit開(kāi)始的子串Tx-1+i（0＜i＜s-x）與模式串P不匹配，即?(Tx-1+i+k=Pk)。

證明 假設(shè)命題不成立，則Tx-1+i+k=Pk，0＜=k＜L(P)，即Tx+i+k-2還原數(shù)據(jù)所得值最后 1bit應(yīng)為“1”，Tx-1+i+k最后1bit也為“1”，即2個(gè)“1”之間“0”的個(gè)數(shù)應(yīng)為T(mén)x-1+i+k個(gè)。

因?yàn)門(mén)x-1+i+k=Pk，所以根據(jù)數(shù)據(jù)變換規(guī)則可知Pk-1之后下一個(gè)“1”所在位置應(yīng)距離Pk-1為T(mén)x-1+i+k位。同樣對(duì)模式串P進(jìn)行逆變換后，可知Pk-1后下一個(gè)“1”所在位置應(yīng)該距Pk-1為Pkbit，與Tx＜min(P)已知條件相矛盾，故假設(shè)不成立，命題結(jié)論成立。

4.4 基于正則表達(dá)式的單層空間協(xié)議識(shí)別

由第2節(jié)可知，空間數(shù)據(jù)串中查找到的標(biāo)識(shí)比特并不一定為模式串特征比特。通過(guò)較短特征比特匹配方式查找數(shù)據(jù)可形成集合SN，而真正特征比特集合為ST，SN中元素?cái)?shù)量應(yīng)大于等于ST中元素?cái)?shù)量，且ST∈SN式恒成立，所以需要通過(guò)規(guī)范限制方式減少SN數(shù)量，即在SN中查找真正特征位集合ST，文中基于正則表達(dá)式[18]DFA方法實(shí)現(xiàn)。

DFA方法卻受限于狀態(tài)數(shù)膨脹[19,20]問(wèn)題，解決方法一般通過(guò)將規(guī)則集分成N組來(lái)實(shí)現(xiàn)[21]，但這樣會(huì)將處理速度降為原來(lái)的 1/N，增加存儲(chǔ)器所需帶寬，限制匹配速度提高。而應(yīng)用文中改進(jìn)算法，在對(duì)數(shù)據(jù)集進(jìn)行整合的前提下，依據(jù)當(dāng)前所處理子集，將相互之間導(dǎo)致?tīng)顟B(tài)膨脹的正則表達(dá)式分在不同分組，在不影響匹配速度前提下可有效抑制DFA狀態(tài)數(shù)膨脹。通過(guò)對(duì)空間協(xié)議結(jié)構(gòu)進(jìn)行分析，將空間數(shù)據(jù)類(lèi)型歸納為4種，并用正則表達(dá)式進(jìn)行規(guī)則判定，具體類(lèi)型及分析方式如表1所示。

表1 數(shù)據(jù)類(lèi)型及分析方式

4.5 基于層次關(guān)聯(lián)關(guān)系的協(xié)議選擇

單層協(xié)議識(shí)別完成后，可分析出單層使用協(xié)議、數(shù)據(jù)長(zhǎng)度、源目的地址等參數(shù)。如果要進(jìn)一步分析下層協(xié)議，一般做法是通過(guò)分析本層數(shù)據(jù)長(zhǎng)度，跳轉(zhuǎn)到下層數(shù)據(jù)起始位置，逐層進(jìn)行協(xié)議識(shí)別。設(shè)當(dāng)前識(shí)別的底層協(xié)議包含m個(gè)協(xié)議，上層包含n個(gè)協(xié)議，在等概率的協(xié)議分析條件下，應(yīng)用一般的協(xié)議分析模型，一共有mn個(gè)協(xié)議組合，需進(jìn)行mn次協(xié)議分析判定。該方法忽略了本層協(xié)議往往規(guī)定、限制上層協(xié)議這一規(guī)則，導(dǎo)致識(shí)別效率低下。

事實(shí)上，協(xié)議上下層協(xié)議之間存在一定的關(guān)聯(lián)關(guān)系，論文通過(guò)分析這種關(guān)聯(lián)關(guān)系，并計(jì)算上層協(xié)議的出現(xiàn)概率，將上層協(xié)議分析次序進(jìn)行了合理調(diào)整，減小了不必要的判定，進(jìn)而降低了協(xié)議識(shí)別復(fù)雜度。如圖1所示，如果在網(wǎng)絡(luò)層使用“空間分組協(xié)議”，那么在傳輸層就不會(huì)使用 SCPS-TP、TCP或 UDP協(xié)議，進(jìn)行傳輸層協(xié)議識(shí)別時(shí)就無(wú)需選取SCPS-TP等協(xié)議特征位，可在一定程度上提高識(shí)別效率。

基于該思想，給出了一種基于層次關(guān)系的協(xié)議選擇機(jī)制，根據(jù)已識(shí)別協(xié)議所兼容上層協(xié)議，縮小上層協(xié)議識(shí)別范圍，提高識(shí)別效率。算法在實(shí)現(xiàn)自底向上分層識(shí)別后，統(tǒng)計(jì)并記錄該層協(xié)議同上層協(xié)議關(guān)系，在大量數(shù)據(jù)樣本基礎(chǔ)上，對(duì)上層協(xié)議出現(xiàn)概率進(jìn)行歸納，后續(xù)識(shí)別可根據(jù)歸納概率確定多層協(xié)議識(shí)別順序，提高識(shí)別效率。基于層次關(guān)系的協(xié)議選擇機(jī)制算法如算法2所示。

算法2 基于層次關(guān)聯(lián)的協(xié)議選擇機(jī)制

輸入：變換后數(shù)據(jù)串T,某層協(xié)議C(Xi)

輸出：整條數(shù)據(jù)所使用的協(xié)議

r1、r2← 權(quán)重值

L← 模式串匹配起始位置

1) 如果現(xiàn)有的協(xié)議特征庫(kù)中有U(Xi+1)協(xié)議符合規(guī)則C(Xi).NextProtocol

2) 則把該協(xié)議視為已知協(xié)議

3) 本算法將提供基于臨近層協(xié)議權(quán)重比較的方式，將數(shù)據(jù)進(jìn)行分類(lèi)

4) 之后重新設(shè)置P(C(Xi-1)|C(Xi))、P(C(Xi+1)|C(Xi))、P(C(Xi+2)|C(Xi))的出現(xiàn)權(quán)重值r1、r2、r3。

5) 給出上層協(xié)議類(lèi)型C(Xi+1).Pattern

6) 回到第1)步，進(jìn)行下一輪比較

7) 如果現(xiàn)有的協(xié)議特征庫(kù)中沒(méi)有協(xié)議符合規(guī)則

8) 本算法將對(duì)臨近層協(xié)議的置信區(qū)間進(jìn)行比較，將數(shù)據(jù)進(jìn)行分類(lèi)

9) 出現(xiàn)概率分別為P(C(Xi-1)|C(Xi))、P(C(Xi+1)|C(Xi))、P(C(Xi+2)|C(Xi))，而權(quán)重值分別為r1、r2、r3。如果對(duì)于未知協(xié)議C1(Xi)，同該未知協(xié)議集合中臨近協(xié)議相對(duì)比

10) 如果待分析的數(shù)據(jù)段∑rtP(C(Xk)| C(Xi)){其中，k∈(i-1、i+1、i+2),t∈(1、2、3)}較大

11) 更新臨近層協(xié)議的置信區(qū)間

12) 返回該未知協(xié)議C(Xk). Protocol的所屬類(lèi)別

13) 將該類(lèi)別進(jìn)行歸納

14) 更新協(xié)議類(lèi)別庫(kù)

15) 返回到第7)步，循環(huán)進(jìn)行之后的識(shí)別

16) 反之

17) 判定該數(shù)據(jù)使用一種新協(xié)議

5 實(shí)驗(yàn)結(jié)果與分析

在Windows 2000環(huán)境下，基于Visual C++6.0語(yǔ)言，設(shè)計(jì)實(shí)現(xiàn)了空間數(shù)據(jù)分析系統(tǒng)，可生成符合SCPS空間協(xié)議標(biāo)準(zhǔn)的數(shù)據(jù)流，并存入數(shù)據(jù)庫(kù)。此外，針對(duì)SCPS協(xié)議族，對(duì)幾種當(dāng)前常用的網(wǎng)絡(luò)層、傳輸層、應(yīng)用層協(xié)議特征進(jìn)行了歸納，建立了相應(yīng)的協(xié)議特征規(guī)則的正則表達(dá)式，并應(yīng)用文中改進(jìn)算法進(jìn)行了大量的數(shù)據(jù)分析實(shí)驗(yàn)。

5.1 單層空間協(xié)議識(shí)別實(shí)驗(yàn)

實(shí)驗(yàn)中，首先讀取待分析數(shù)據(jù)，應(yīng)用 4.2節(jié)算法進(jìn)行數(shù)據(jù)預(yù)處理，然后應(yīng)用 4.3節(jié)小數(shù)跳進(jìn)機(jī)制算法實(shí)現(xiàn)協(xié)議模式串的快速查找，實(shí)現(xiàn)單層協(xié)議識(shí)別。

圖5為應(yīng)用4.3節(jié)方法同傳統(tǒng)BM算法識(shí)別空間數(shù)據(jù)的比較，可以看出，提出算法識(shí)別效率可提高至BM算法的2倍。

圖5 空間數(shù)據(jù)單層協(xié)議識(shí)別比較

由上可知，提出算法在規(guī)則復(fù)雜度較高，數(shù)據(jù)量較大的情況下，通過(guò)變換空間數(shù)據(jù)的方法有效減小了n、m，增大了跳進(jìn)距離，解析單條數(shù)據(jù)復(fù)雜度為O(4y(mn/(4+α)+n) （y表示經(jīng)篩選后某一層可能的協(xié)議個(gè)數(shù)，y＜P，α與m中連續(xù)“1”出現(xiàn)的頻率有關(guān)）。

由式(1)可以得出：

式(2)成立。易見(jiàn)，對(duì)于單層協(xié)議識(shí)別，文中提出算法時(shí)間復(fù)雜度可降低到BM算法的(1+m/4)/m。

5.2 多層空間協(xié)議識(shí)別實(shí)驗(yàn)

在單層空間協(xié)議識(shí)別基礎(chǔ)上，又應(yīng)用4.5節(jié)算法對(duì)多層協(xié)議識(shí)別進(jìn)行了實(shí)驗(yàn)。

以SCPS協(xié)議族為例，傳輸層協(xié)議包括SCPSTP、TCP和UDP 3種典型協(xié)議，應(yīng)用層包括CFDP、SCPS-FP和FTP 3種典型協(xié)議。圖6給出了衛(wèi)星網(wǎng)絡(luò)協(xié)議識(shí)別中，傳輸層和應(yīng)用層協(xié)議的架構(gòu)及出現(xiàn)概率示例。按照單層的協(xié)議分析方法，識(shí)別由“SCPS-TP、CFDP”組成的一組數(shù)據(jù)，在最差的情況下，需要執(zhí)行3×3次協(xié)議分析。而應(yīng)用文中算法，通過(guò)分析協(xié)議結(jié)構(gòu)和出現(xiàn)概率，首先計(jì)算出多層協(xié)議分析組合的優(yōu)先級(jí)。

圖6 空間數(shù)據(jù)多層協(xié)議識(shí)別比較

從表 2可知，應(yīng)用本文方法，最優(yōu)僅需 1次、最差僅需7次協(xié)議分析，復(fù)雜度要低于傳統(tǒng)的9次分析。首先應(yīng)用文中方法按照表2的優(yōu)先級(jí)順序進(jìn)行了多次實(shí)驗(yàn)，并在隨機(jī)的協(xié)議組合順序下進(jìn)行了識(shí)別實(shí)驗(yàn)，二者的結(jié)果比較如圖6所示。

可以看出提出算法根據(jù)相鄰層協(xié)議出現(xiàn)概率進(jìn)行識(shí)別，可將多層空間協(xié)議識(shí)別效率提高2.5倍。

表2 協(xié)議組合優(yōu)先級(jí)

對(duì)于多層協(xié)議，設(shè)傳輸層協(xié)議為L(zhǎng)T、應(yīng)用層協(xié)議為L(zhǎng)A，概率系數(shù)為β，提出算法的時(shí)間復(fù)雜度

6 結(jié)束語(yǔ)

空間協(xié)議分析是一個(gè)倍受關(guān)注的研究領(lǐng)域，本文在對(duì)SCPS協(xié)議族進(jìn)行研究基礎(chǔ)上，提出了一種改進(jìn)的空間協(xié)議算法。提出算法在空間數(shù)據(jù)預(yù)處理、數(shù)據(jù)查找跳進(jìn)、多層協(xié)議識(shí)別方法進(jìn)行了改進(jìn)，在一定程度上解決了特征位難于區(qū)分和查找問(wèn)題，提高了協(xié)議識(shí)別效率。

[1] 李雄偉. 網(wǎng)絡(luò)對(duì)抗系統(tǒng)及其關(guān)鍵技術(shù)研究[D]. 北京: 北京郵電大學(xué),2003.LI X W. Research on Network Operation System and Key Technologies[D]. Beijing: Beijing University of Posts and Telecommunications,2003.

[2] BOYER R S, MOORE J S. A fast string searching algorithm[J]. Communications ACM, 1977, 20(10):762-772.

[3] CCSDS 311.0-M-1 Reference Architecture for Space Data Systems[S].Washington, DC, USA, 2008.

[4] CCSDS 130.0-G-2 Overview of Space Communications Protocols,Report Concerning Space Data System Standards[S]. Washington, DC,USA, 2007.

[5] CCSDS 211.0-B-4 Proximity-1 Space Link Protocol—Data Link Layer, Recommendation for Space Data System Standards[S]. Washington, DC, USA, 2006.

[6] CCSDS 713.0-B-1. Space Communications Protocol Specification(SCPS)-Network Protocol (SCPS-NP)[S]. Washington, DC, USA,1999.

[7] CCSDS 714. O-B-2. Space Communications Protocol Specification(SCPS)-Transport Protocol (SCPS-TP)[S]. Washington, DC, USA,2006.

[8] CCSDS 717.0-B-1 Space Communications Protocol Specification(SCPS)-File Protocol (SCPS-FP)[S]. Newport Beach, California, USA,1999.

[9] 許楓, 尤政. CCSDS空間通信協(xié)議及其與互聯(lián)網(wǎng)通信協(xié)議的比較[J] . 中國(guó)航天, 2007, (5): 26 - 29.XU F, YOU Z. CCSDS space communications protocol and its comparison with Internet protocols[J] . Aerospace China, 2007,(5): 26-29.

[10] HOOKE J .Evolutionary Paths to Internationally-standardized Space Internetworking[R] . AIAA , 2008. 2 - 9.

[11] 譚建龍. 串匹配算法及其在網(wǎng)絡(luò)內(nèi)容分析中的應(yīng)用[D]. 北京：中國(guó)科學(xué)院研究生院, 2003.TAN J L. String Matching Algorithm and Application of Network Content Analysis[D]. Beijing: Graduate School of Chinese Academy of Sciences, 2003.

[12] RICHARD O D, PETER E H, DAVID G S. Pattern Classification[M].America: Library of Congress, 2000.

[13] SUNDAY D M. A very fast substring search algorithm[J]. Communications ACM , 1990, 33(8): 132-142.

[14] KAGHAZIAN L, MCLEOD D, SADRI R. Scalable complex pattern search in sequential data[A]. Proceedings of the 17thACM Conference on Information and Knowledge Management[C]. Napa valley California, 2008. 1467-1468.

[15] 范洪博, 姚念民. 一種高速精確單模式串匹配算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(8): 1341-1348.FAN H B, YAO X M. A fast and exact single pattern matching algorithm[J]. Journal of Computer Research and Development, 2009, 46(8):1341-1348.

[16] CROCHEMORE M, ALLAUZEN C, RAFFINOT M. Factor oracle:a new structure for pattern matching[A]. Proceedings of the 26th Conference on Current Trends in Theory and Practice of Informatics[C].London, UK, 1999.291-306.

[17] 劉萍, 劉燕兵, 郭莉等. 串匹配算法中模式串與文本之間關(guān)系的研究[J]. 軟件學(xué)報(bào), 2010, 21(7):1503-1514.LIU P, LIU Y B, GUO L,et al. Research on relationship between patterns and text in string matching algorithms[J]. Journal of Software,2010, 21(7):1503-1514.

[18] 范慧萍. 基于正則表達(dá)式的協(xié)議識(shí)別研究與實(shí)現(xiàn)[D]. 長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)研究生院, 2007.FAN H P. Research and Realization of High Speed Protocol Identification Based on Regular Expression[D]. Changsha: Graduate School of National University of Defense Technology, 2007.

[19] 陳曙暉, 蘇金樹(shù), 范慧萍等．一種基于深度報(bào)文檢測(cè)的 FSM 狀態(tài)表壓縮技術(shù)[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(8): 1299-1306.CHEN S H, SU J S, FAN H P,et al．An FSM state table compressing method based on deep packet inspection[J]. Journal of Computer Research and Development, 2008, 45(8): 1299-1306．

[20] 楊毅夫, 劉燕兵, 劉萍等. 正則表達(dá)式的 DFA 壓縮算法[J]. 通信學(xué)報(bào), 2009, 30(10A): 36-41.YANG Y F, LIU Y B, LIU P,et al. Effective algorithm of compressing regular expressions' DFA[J]. Journal on Communications, 2009,30(10A): 36-41.

[21] FANG Y, CHEN Z F, DIAO Y L,et al, Fast and memory-efficient regular expression matching for deep packet inspection[A]. ANCS’06:Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems[C]. New York, NY, USA,2006.93-102.