面向比特流的未知短波協(xié)議識(shí)別技術(shù)

面向比特流的未知短波協(xié)議識(shí)別技術(shù)牛歡;盧選民【摘要】協(xié)議識(shí)別技術(shù)在信息對(duì)抗中發(fā)揮著極其重要的作用,它是對(duì)信號(hào)進(jìn)行解碼的前提條件,是通信對(duì)抗由信號(hào)層對(duì)抗,轉(zhuǎn)變?yōu)樾盘?hào)層與信息層對(duì)抗互相結(jié)合,以信息層對(duì)抗為主的關(guān)鍵一步.從海量比特流數(shù)據(jù)中識(shí)別未知協(xié)議的基本方法是對(duì)比特流數(shù)據(jù)進(jìn)行挖掘,尋找其中的特征序列,在沒(méi)有先驗(yàn)知識(shí)的情況下,則需要對(duì)其中的頻繁序列進(jìn)行提取?為適應(yīng)比特流環(huán)境，本文在BNDM算法的基礎(chǔ)上做出改進(jìn)，進(jìn)行前置編碼,極大地提高了二進(jìn)制環(huán)境下搜尋頻繁序列的效率.實(shí)驗(yàn)表明,上述方法能夠?qū)崿F(xiàn)海量比特流數(shù)據(jù)中對(duì)未知短波協(xié)議的識(shí)別以及對(duì)協(xié)議數(shù)據(jù)幀的定界和切分.％Asthefoundationoffurthersignaldecoding,protocolidentificationtechniqueplaysaveryimportantroleintheinformationcountermeasures.Furthermore,itisakeystepforinformationcountermeasurestoevolvefromsignallayertosignallayercombinedwithinformationlayer.Thebasicapproachofunknownprotocolsidentificatedfrommassivebit-streamdataisthebitstreamdatamining,andlookingforinformationwhichcandeterminethetypeofprotocol.Inthecaseoflackingofpriorknowledge,frequentpatternsequenceappearinginthebitstreamdataneedstobeextracted,andsequencethatcanidentifythetypeofprotocolshouldbescreenedout.Inordertoadapttotheenvironmentofthebitstream,thispapermakesanimprovementbasedontheBNDMalgorithm,andimprovestheefficiencyofsearchingthefrequentsequencesinthebinaryenvironment.Theexperimentalresultsshowthatunknownprotocolidentification,protocoldataframealignmentandsegmentationfrommassivebit-streamdataarerealizedthroughtheresearchresultsofthisthesis.期刊名稱】《計(jì)算機(jī)系統(tǒng)應(yīng)用》年(卷),期】2016(025)003【總頁(yè)數(shù)】5頁(yè)(P142-146)【關(guān)鍵詞】比特流;協(xié)議識(shí)別;短波;模式匹配;數(shù)據(jù)挖掘【作者】牛歡;盧選民【作者單位】西北工業(yè)大學(xué)電子信息學(xué)院,西安710129;西北工業(yè)大學(xué)電子信息學(xué)院,西安710129【正文語(yǔ)種】中文按照國(guó)際無(wú)線電咨詢委員會(huì)的劃分，短波是指其波長(zhǎng)在100m~10m,頻率為3MHz~30MHz的電磁波.工作頻段在此范圍之內(nèi)的無(wú)線電通信稱之為短波通信.相較于衛(wèi)星通信、微波通信、光纜等通信方式,短波通信在不建設(shè)中繼站的條件下,就能夠?qū)崿F(xiàn)遠(yuǎn)距離通信.它有著許多較為顯著的優(yōu)點(diǎn),諸如使用時(shí)無(wú)需支付話費(fèi),建設(shè)和維護(hù)費(fèi)用低;設(shè)備簡(jiǎn)單,目標(biāo)小,容易隱蔽,對(duì)自然災(zāi)害或戰(zhàn)爭(zhēng)的抗毀能力強(qiáng),且損毀后易修復(fù);造價(jià)低,可大規(guī)模裝備,系統(tǒng)頑存性強(qiáng);電路調(diào)度較為容易,靈活性較強(qiáng),既可固定通信,又可由人背負(fù)或裝入其他器械,進(jìn)行移動(dòng)通信等[1].因而,短波通信在現(xiàn)代戰(zhàn)爭(zhēng)中發(fā)揮著十分重要的作用.如圖1所示,現(xiàn)代戰(zhàn)場(chǎng)中的短波通信網(wǎng)絡(luò)是由許多自主工作,彼此之間經(jīng)過(guò)通信鏈路相連接的通信節(jié)點(diǎn)構(gòu)成.在對(duì)短波通信信道進(jìn)行偵察后,可以捕獲到相應(yīng)的短波信號(hào),進(jìn)而采用相應(yīng)的技術(shù)手段對(duì)信號(hào)進(jìn)行處理,就可以得到一些比特信息[2-4].正常情況下,通信雙方所采用的短波通信協(xié)議是非公開(kāi)的.因此,對(duì)于信道偵聽(tīng)所得到的比特流數(shù)據(jù),如何對(duì)其進(jìn)行數(shù)據(jù)分析進(jìn)而識(shí)別出其所使用的通信協(xié)議,對(duì)通信偵察的順利完成有著決定性的影響.現(xiàn)有的協(xié)議識(shí)別技術(shù),其絕大部分只是在信號(hào)層面上進(jìn)行檢測(cè),分析所捕獲信號(hào)的一些參數(shù)或者針對(duì)協(xié)議中的某一個(gè)特征來(lái)進(jìn)行處理,如基于二階循環(huán)統(tǒng)計(jì)量的調(diào)制方式識(shí)別、基于端口掃描的協(xié)議識(shí)別方式以及基于觀測(cè)統(tǒng)計(jì)特性的檢測(cè)識(shí)別方法等[4].上述的協(xié)議識(shí)別技術(shù)一方面主要應(yīng)用在有線通信中,另一方面大都是針對(duì)已知的協(xié)議來(lái)實(shí)現(xiàn),并不能在比特流場(chǎng)景中對(duì)非常規(guī)的專用未知協(xié)議進(jìn)行識(shí)別.為解決上述問(wèn)題,本文從比特流層面的數(shù)據(jù)挖掘出發(fā),根據(jù)短波通信協(xié)議的特點(diǎn),在傳統(tǒng)的單模式識(shí)別算法基礎(chǔ)上做出改進(jìn),從而對(duì)短波協(xié)議的識(shí)別提供一定的支持.在同種未知協(xié)議的原始數(shù)據(jù)大量累積的條件下,面向比特流的未知協(xié)議識(shí)別的目標(biāo)是從中尋找代表短波協(xié)議特征的特征序列[5].因此,首先應(yīng)通過(guò)面向比特流的頻繁集挖掘算法,提取其特征序列,然后以該特征序列作為幀定位的標(biāo)志對(duì)比特流數(shù)據(jù)進(jìn)行切割.上述的兩個(gè)場(chǎng)景中,前者主要體現(xiàn)為序列篩選問(wèn)題,可以采用改進(jìn)的多模式匹配算法,將算法中匹配的過(guò)程替換為模式串的統(tǒng)計(jì)過(guò)程.后者則是設(shè)法從比特流中正確的分離出每一個(gè)完整無(wú)誤的幀,進(jìn)而確定其采用的協(xié)議格式.幀提取問(wèn)題也可以被轉(zhuǎn)化為單模式串匹配問(wèn)題:協(xié)議同步碼序列既定,使用單模式匹配算法從比特流中找出同步碼序列所有的位置,則相鄰兩個(gè)特征序列之間就是一數(shù)據(jù)幀[6].針對(duì)所捕獲的比特流數(shù)據(jù),要對(duì)其所采用的協(xié)議進(jìn)行識(shí)別,首先需要在海量的比特流數(shù)據(jù)中提取此種協(xié)議的特征序列.由前述內(nèi)容可知,可以利用同步碼檢測(cè)的方法來(lái)進(jìn)行協(xié)議識(shí)別.考慮到現(xiàn)有的幀同步檢測(cè)技術(shù)大多是對(duì)已知的同步碼進(jìn)行檢測(cè),因此,本文主要研究如何利用頻繁序列挖掘技術(shù)來(lái)進(jìn)行未知同步碼檢測(cè).考慮到比特流數(shù)據(jù)具有單一性、順序性兩個(gè)明顯的特征,不能直接使用經(jīng)典的數(shù)據(jù)挖掘方法處理純比特流數(shù)據(jù),故需要進(jìn)行一定的改進(jìn)[7].進(jìn)一步深入考慮,在沒(méi)有任何協(xié)議特征信息的情況下,必須對(duì)所有的2進(jìn)制序列進(jìn)行匹配.本質(zhì)上來(lái)說(shuō),是對(duì)所有的2進(jìn)制模式序列的出現(xiàn)情況做全統(tǒng)計(jì),以備下一階段的挖掘運(yùn)用.傳統(tǒng)意義上的單模式匹配一次只能尋找一個(gè)特定的模式序列,在匹配目標(biāo)未知的前提條件下,對(duì)源數(shù)據(jù)的掃描次數(shù)取決于候選模式的存在數(shù)目,對(duì)于大量的源數(shù)據(jù),姑且不論匹配算法本身的效率如何，磁盤I/O的代價(jià)已然相當(dāng)可觀，因此，此環(huán)境下使用單模式匹配算法是不明智的[8].而多模式匹配則能夠以一次掃描尋找到多個(gè)模式,這與比特流模式序列的統(tǒng)計(jì)的目標(biāo)是一致的.比較典型的短波協(xié)議有業(yè)余無(wú)線電封包通信的AX.25鏈接協(xié)議、D-STAR數(shù)字通信協(xié)議以及AIS協(xié)議.以D-STAR為例,其數(shù)據(jù)包報(bào)頭部分結(jié)構(gòu)如圖2所示.表1列出了上述三種短波通信協(xié)議的同步碼序列.通過(guò)對(duì)多個(gè)短波協(xié)議進(jìn)行分析研究,能夠發(fā)現(xiàn),充當(dāng)幀同步段的特征序列,其長(zhǎng)度普遍不超過(guò)128比特.因此,可以做出這樣的經(jīng)驗(yàn)假設(shè):同步碼序列長(zhǎng)度范圍為2~128bits.基于以上分析，在捕獲的未知短波協(xié)議比特?cái)?shù)據(jù)流中，同步碼序列出現(xiàn)的概率P有{P|O<P<1)},此同步序列長(zhǎng)度me[2,128],對(duì)于長(zhǎng)度為m的比特序列，對(duì)其進(jìn)行頻繁序列統(tǒng)計(jì)時(shí)的枚舉空間為2m,且空間復(fù)雜度與m存在指數(shù)關(guān)系?如果對(duì)所有的比特序列進(jìn)行一次性遍歷,則其空間復(fù)雜度為,這是無(wú)法接受的.繼續(xù)分析,如果首先對(duì)長(zhǎng)度m=4的比特序列進(jìn)行統(tǒng)計(jì)，然后通過(guò)設(shè)定最小閾值過(guò)濾得到短頻繁序列，再通過(guò)一定的關(guān)聯(lián)規(guī)則,就可以將長(zhǎng)度為4的短頻繁序列拼接為長(zhǎng)度8的頻繁序列,依此規(guī)則進(jìn)行下去,直到獲得最終的同步碼序列為止[9].相對(duì)于一次性遍歷目標(biāo)長(zhǎng)頻繁序列而言,采用這種思路的好處是,拼接獲得的長(zhǎng)頻繁序列是建立在篩選過(guò)濾的短頻繁序列基礎(chǔ)之上的,因此可以極大地提升工作效率.為了驗(yàn)證算法的有效性及正確性，編程利用改進(jìn)的AC算法實(shí)現(xiàn)對(duì)短頻繁序列進(jìn)行統(tǒng)計(jì),然后通過(guò)拼接算法獲得長(zhǎng)頻繁序列這一過(guò)程[10].測(cè)試采用AX.25協(xié)議以及D-STAR協(xié)議分別解調(diào)后的數(shù)據(jù)文件，其結(jié)果具有一致性,這里以AX.25的數(shù)據(jù)文件為例進(jìn)行說(shuō)明.表2為拼接得到的同步碼候選列表,這些長(zhǎng)序列是一系列近似串.顯然,標(biāo)準(zhǔn)同步序列應(yīng)為編號(hào)為1的序列:01111110(0x7E).圖3是進(jìn)行分頻繁序列拼接后的結(jié)果,有六個(gè)子串是標(biāo)準(zhǔn)同步碼的近似串.實(shí)驗(yàn)結(jié)果表明,利用長(zhǎng)字符串拼接技術(shù)對(duì)于同步碼的識(shí)別率可以達(dá)到94.1%,能夠比較準(zhǔn)確地在比特流數(shù)據(jù)中對(duì)同步碼進(jìn)行識(shí)別.2.1單模式匹配算法效能分析與改進(jìn)在上述內(nèi)容的基礎(chǔ)上,利用已經(jīng)提取出的特征序列對(duì)比特流數(shù)據(jù)進(jìn)行幀定界.為此,首先對(duì)應(yīng)用較廣的幾種單模式匹配算法進(jìn)行性能測(cè)試，測(cè)試文本隨機(jī)生成，共10M字節(jié),模式串也使用同樣的方法生成.實(shí)驗(yàn)不斷重復(fù)進(jìn)行,直到在95%的置信度下相對(duì)誤差低于2%.所有算法都采用了最優(yōu)的實(shí)現(xiàn)，但結(jié)果只有Shift-And,Horspool,BNDM和BOM算法在圖上有相應(yīng)的分布區(qū)域,其他算法則因?yàn)樘鴽](méi)有在圖上顯示?圖4是實(shí)驗(yàn)結(jié)果圖，可見(jiàn)序列長(zhǎng)度不超過(guò)128的前提下,BNDM算法是比較合適的.然而，上述測(cè)試文本的字符集為{a,b,......,z},而比特流中所包含的元素非0即1,并且模式串和目標(biāo)串的字符集大小相同,均為{0,1},遠(yuǎn)小于測(cè)試文本字符集.在此環(huán)境下,傳統(tǒng)的單模式匹配算法效率十分低下.依據(jù)比特流序列的特點(diǎn),需要對(duì)傳統(tǒng)單模式匹配算法進(jìn)行優(yōu)化改進(jìn)以提高在比特流環(huán)境下進(jìn)行匹配的效率.為此,考慮從擴(kuò)充字符集的方向?qū)λ惴ㄟM(jìn)行優(yōu)化,采用預(yù)編碼的思想來(lái)進(jìn)行實(shí)現(xiàn).編碼的目標(biāo)是在擴(kuò)充字符集的同時(shí)能夠?qū)Ρ忍亓魑募M(jìn)行壓縮,從而縮短目標(biāo)串的長(zhǎng)度,提升匹配效率[11].由于目標(biāo)串的長(zhǎng)度遠(yuǎn)遠(yuǎn)大于模式串的長(zhǎng)度,因此,編碼后目標(biāo)串的字符集必然大于模式串的字符集,從而解決了模式匹配算法在比特流環(huán)境下效率低下的問(wèn)題.哈夫曼編碼采用構(gòu)造最優(yōu)前綴碼的貪心算法,從而使得編碼后的二進(jìn)制序列能夠達(dá)到最短.考慮到此編碼方法的前綴性質(zhì),就可以使其譯碼方法變得非常簡(jiǎn)單.這是由于任一字符的代碼都不會(huì)是其他字符代碼的前綴,只要從編碼文件中不斷取出代表某一字符的前綴,再轉(zhuǎn)換為原字符,即可逐個(gè)譯出原文件中的所有字符.這樣,一個(gè)任意長(zhǎng)的哈夫曼編碼序列可以被唯一地翻譯為一個(gè)字符序列.基于哈夫曼編碼算法的優(yōu)勢(shì),本文采用逆向的思想,將目標(biāo)串和模式串看作是采用哈夫曼編碼后的最短二進(jìn)制序列,通過(guò)對(duì)目標(biāo)串和模式串的譯碼來(lái)達(dá)到編碼的效果.采用此種“編碼”方法,可以實(shí)現(xiàn)擴(kuò)大字符集和使“編碼”后的序列長(zhǎng)度最短的目標(biāo),避免編碼對(duì)模式匹配算法效率的影響[12].譯碼時(shí)采用線性鏈表存儲(chǔ)字符序列,具體實(shí)現(xiàn)如下:template<classCharType,classweightType>LinkList<CharType>HuffmanTree<CharType,WeightType>::DeCode(StringstrCode)〃對(duì)編碼串strCode進(jìn)行譯碼，返回編碼前的字符序列{LinkList<CharType>charList;for(intpos=0;pos<strCode.Length();pos++){if(strCode[pos]=='0')curPos=nodes[curPos].leftChild;//'0'表示左分支elsecurPos=nodes[curPos].rightChild;//'1'示右分支if(nodes[curPos].leftChild==0&&nodes[curPOS].rightChild==0){ charList.Insert(charList.Length()+1,LeafChars[curPos]);curPos=2*num-1;//curPos回歸根結(jié)點(diǎn)}}returncharList;//返回編碼前的字符序列}2.2前置編碼BNDM算法效率分析圖5為目標(biāo)比特流01010000110110101在編碼前后的對(duì)比圖,為了驗(yàn)證在真實(shí)場(chǎng)景下，編碼BNDM算法同其他模式匹配算法的差異,進(jìn)行了多組實(shí)驗(yàn)測(cè)試.實(shí)驗(yàn)數(shù)據(jù)以AX.25協(xié)議解調(diào)譯碼后比特流數(shù)據(jù)文件為例,并分別在大小為1Kb、10Kb100Kb三種情況下進(jìn)行測(cè)試.其中AX.25協(xié)議特征串為:01111110,對(duì)照組取KMP算法、BM算法和BNDM算法?實(shí)驗(yàn)結(jié)果如表3所示.表3AX.25協(xié)議特征串檢索測(cè)試（單位:ms）文件大小1Kb10Kb100Kb算法耗時(shí)耗時(shí)耗時(shí)KMP803680572330312BM326612616135943BNDM398416504160336前置編碼305812278126878由圖可見(jiàn)，前置編碼BNDM算法相對(duì)KMP、BM和BNDM算法，效率有了很大的提升,并且數(shù)據(jù)文件越大,其表現(xiàn)越明顯?相對(duì)于其它算法，前置編碼BNDM算法在編碼階段需要消耗一定的時(shí)間,但是由于在匹配過(guò)程中節(jié)省了大量時(shí)間,彌補(bǔ)了預(yù)處理階段付出的時(shí)間代價(jià),因此總耗時(shí)仍然小于其它算法.圖5比特流編碼過(guò)程示意圖可以看出,采用哈夫曼譯碼的編碼方法后,解決了模式匹配算法在比特流環(huán)境下效能低下的問(wèn)題?基于此,就可以采用前置編碼BNDM算法進(jìn)行幀定界切分.圖6給出了AX.25協(xié)議比特流數(shù)據(jù)的測(cè)試結(jié)果，表明本文提出的方法是可行的.圖6AX.25協(xié)議比特流幀定位與切分結(jié)語(yǔ)本文所提出的未知短波協(xié)議識(shí)別技術(shù),主要是指在海量比特流數(shù)據(jù)中提取未知協(xié)議的特征序列,并以此對(duì)其進(jìn)行幀定界和切分.考慮到單模式匹配算法在比特流環(huán)境下效能低下的問(wèn)題,本文將哈夫曼譯碼運(yùn)用于二進(jìn)制序列的編碼,彌補(bǔ)了單模式匹配算法在比特流場(chǎng)景中的缺陷.實(shí)驗(yàn)結(jié)果表明,本文提出的面向比特流的未知短波協(xié)議識(shí)別技術(shù)是可行的,對(duì)目前相關(guān)研究較少的比特流數(shù)據(jù)分析有一定借鑒意義,但對(duì)于數(shù)據(jù)幀切割之后的幀內(nèi)結(jié)構(gòu)分析,有待于進(jìn)一步研究.參考文獻(xiàn)王坦.短波通信系統(tǒng).北京:電子工業(yè)出版社,2008.趙琦,劉榮科.編碼理論.北京:北京航空航天大學(xué)出版社,2009.何永君,舒輝,熊小兵.基于動(dòng)態(tài)二進(jìn)制分析的網(wǎng)絡(luò)協(xié)議逆向解析.計(jì)算機(jī)工程,2010,36(9):268-270.夏曉巍,方旭明,黃巍等.幀同步技術(shù)的研究與展望.信息安全與通信保密,2006,1(7):140-143.聶東舉,葉進(jìn),閆坤,等.基于算法的短波通信協(xié)議識(shí)別技術(shù).系統(tǒng)工程與電子技術(shù),2013,35(6):1307-1311.6孑L東林,羅向陽(yáng)，鄧崎皓,等基于AC自動(dòng)機(jī)匹配算法的入侵檢測(cè)系統(tǒng)研究?微電子學(xué)與計(jì)機(jī),2005,22(3):89-95.ZhouX,WuY.SignalmodulationrecognitionbasedonKPCAandLAD.SystemsEngineeringandElectronics,2011,33(7):1611-1616.金凌.面向比特流的未知幀頭識(shí)別技術(shù)研究［碩士學(xué)位論文］.上海:上海交通大學(xué),2011.陳曙暉,蘇金樹(shù).基于內(nèi)容分析的協(xié)議識(shí)別研究.國(guó)防科技大學(xué)學(xué)報(bào),2008,30(4):82-87.林祎,彭華,趙振華.基于小波降噪的短波通信信號(hào)協(xié)議識(shí)別特征提取算法.信息工程大學(xué)學(xué)報(bào),2012,13(4):438-442.賀瑤,王文慶,薛飛.基于云計(jì)算的海量數(shù)據(jù)挖掘研究.計(jì)算機(jī)技術(shù)與發(fā)展,2013,23(2):69-72.陸琳琳,田野.基于確定有限狀態(tài)自動(dòng)機(jī)的改進(jìn)多模式匹配算法研究.計(jì)算機(jī)應(yīng)用與軟件,2013,30(7):321-323.IdentificationTechnologyofUnknownShortwaveProtocolforBitStreamNIUHuan,LUXuan-Min(SchoolofElectronicsandInformation,NorthwesternPolytechnicalUniversity,Xi'an710129,China)Abstract：Asthefoundationoffurthersignaldecoding,protocolidentificationtechniqueplaysaveryimportantroleintheinformationcountermeasures.Furthermore,itisakeystepforinformationcountermeasurestoevolvefromsignallayertosignallayercombinedwithinformationlayer.Thebasicapproachofunknownprotocolsidentificatedfrommassivebit-streamdataisthebitstreamdatamining,andlookingforinformationwhichcandeterminethetypeofprotocol.Inthecaseoflackingofpriorknowledge,frequentpatternsequenceappearinginthebitstreamdataneedstobeextracted,andsequencethatcanidentifythetypeofprotocolshouldbescreenedout.Inordertoadapttotheenvironmentofthebitstream,thispapermakesanimprovementbasedontheBNDMalgorithm,andimprovestheefficiencyofsearchingthefrequentsequencesinthebinaryenvironment.Theexperimentalresultsshowthatunknownprotocolidentification,protocoldataframealignmentandsegmentationfrommassivebit-streamdataarerealizedthroughtheresearchresultsofthisthesis.Keywords：bitstream;protocolidentification;shortwave;patternmatching;datamining①基金項(xiàng)目：2015年西北工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)(論文)重點(diǎn)扶持項(xiàng)目(GDKY9005)收稿時(shí)間：2015-06-02;收到修改稿時(shí)間:2015-09-08由圖可見(jiàn)，前置編碼BNDM算法相對(duì)KMP、BM和BNDM算法，效率有了很大的提升,并且數(shù)據(jù)文件越大,其表現(xiàn)越明顯?相對(duì)于其它算法，前置編碼BNDM算法在編碼階段需要消耗一定的時(shí)間,但是由于在匹配過(guò)程中節(jié)省了大量時(shí)間,彌補(bǔ)了預(yù)處理階段付出的時(shí)間代價(jià)，因此總耗時(shí)仍然小于其它算法.可以看出,采用哈夫曼譯碼的編碼方法后,解決了模式匹配算法在比特流環(huán)境下效能低下的問(wèn)題?基于此,就可以采用前置編碼BND