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

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