薛開(kāi)平 柳 彬 王勁松 李 威 薛穎杰

?

面向鏈路比特流的未知幀關(guān)聯(lián)分析

薛開(kāi)平*①柳 彬①王勁松②李 威①薛穎杰①

①(中國(guó)科學(xué)技術(shù)大學(xué)信息科學(xué)技術(shù)學(xué)院 合肥 230027)②(西南電子電信技術(shù)研究所成都 610041)

在電子對(duì)抗中，截獲到對(duì)方的通信比特流序列之后，當(dāng)鏈路協(xié)議類(lèi)型未知時(shí)，現(xiàn)有的協(xié)議解析工具往往無(wú)法分析比特流所承載的有用信息。為了獲取比特流承載信息，首先需要切分比特流得到鏈路幀。該文根據(jù)鏈路幀結(jié)構(gòu)的一般規(guī)律，提出一種基于數(shù)據(jù)挖掘的比特流切分算法。通過(guò)頻繁序列統(tǒng)計(jì)、關(guān)聯(lián)規(guī)則分析以及關(guān)聯(lián)規(guī)則整合，識(shí)別出比特流中標(biāo)識(shí)幀起始的多重關(guān)聯(lián)規(guī)則序列。測(cè)試結(jié)果表明，該算法能夠從未知比特流中提取有效的切分標(biāo)識(shí)，正確實(shí)現(xiàn)比特流切分。與同類(lèi)基于數(shù)據(jù)挖掘的比特流分析方法相比，該算法復(fù)雜度低，輸出結(jié)果唯一且可信度高。

鏈路比特流；未知幀；頻繁統(tǒng)計(jì)；關(guān)聯(lián)分析；切分

1 引言

目前的協(xié)議解析工具，如Wireshark, Tcpdump，能有效完成面向已知協(xié)議的解析工作。但在日益激烈的電子對(duì)抗中，偵聽(tīng)者所截獲的通信比特流往往協(xié)議類(lèi)型完全未知，此時(shí)面向已知協(xié)議的解析工具將不起作用。為了分析截獲的比特流承載信息，關(guān)鍵的一步首先是對(duì)其進(jìn)行切分而獲得鏈路幀，在此基礎(chǔ)上才能進(jìn)行后續(xù)解析工作。面向鏈路比特流的未知幀關(guān)聯(lián)分析旨在尋找一種方法，從完全未知的鏈路比特流中尋找能指示幀起始的序列標(biāo)識(shí)，基于此對(duì)比特流進(jìn)行切分獲得鏈路幀，使后續(xù)對(duì)未知幀的解析成為可能。

由于缺乏關(guān)于鏈路協(xié)議的先驗(yàn)知識(shí)，導(dǎo)致面向鏈路比特流的未知幀識(shí)別和解析困難，目前國(guó)內(nèi)外相關(guān)研究較少。文獻(xiàn)[1]基于隱式馬爾科夫模型，結(jié)合報(bào)文長(zhǎng)度和到達(dá)時(shí)間間隔兩種行為模式對(duì)應(yīng)用協(xié)議進(jìn)行分類(lèi)。文獻(xiàn)[2]提出一種基于多模式匹配的網(wǎng)絡(luò)視頻流分類(lèi)算法。文獻(xiàn)[3]基于載荷部分字節(jié)的編碼，實(shí)現(xiàn)對(duì)混合流量按應(yīng)用類(lèi)型進(jìn)行有效分類(lèi)。然而文獻(xiàn)[1-3]都只適用于對(duì)網(wǎng)絡(luò)層以上的協(xié)議進(jìn)行識(shí)別分類(lèi)。文獻(xiàn)[4-7]著眼于安全協(xié)議。其中，文獻(xiàn)[4]提出了一種深度包檢測(cè)和流檢測(cè)相結(jié)合的針對(duì)加密流量的應(yīng)用識(shí)別算法。文獻(xiàn)[5]基于序列模式挖掘提取協(xié)議關(guān)鍵詞序列，并結(jié)合密文特征解析安全協(xié)議格式。文獻(xiàn)[6]提出了一種基于主體行為特征的安全協(xié)議會(huì)話識(shí)別方法。文獻(xiàn)[7]利用隨機(jī)性檢測(cè)識(shí)別比特流的加密部分和未加密部分，但該方法分類(lèi)粒度較粗，無(wú)法按幀切分比特流。此外，文獻(xiàn)[8]提出了一種基于地址信息將未知幀分離為點(diǎn)對(duì)點(diǎn)數(shù)據(jù)的方法，但前提是已將比特流正確切分成幀。文獻(xiàn)[9]借鑒數(shù)據(jù)挖掘中頻繁集和關(guān)聯(lián)規(guī)則的概念[10]，但結(jié)果中存在冗余序列干擾。文獻(xiàn)[11]可以識(shí)別標(biāo)志幀起始的特征序列，但其輸出中同樣存在冗余序列，且在缺乏先驗(yàn)知識(shí)時(shí)無(wú)法驗(yàn)證輸出是否正確。

本文基于鏈路幀結(jié)構(gòu)的一般規(guī)律，通過(guò)頻繁序列統(tǒng)計(jì)和關(guān)聯(lián)分析獲取二重關(guān)聯(lián)規(guī)則集合，并利用關(guān)聯(lián)規(guī)則有向圖進(jìn)行整合，獲得多重關(guān)聯(lián)規(guī)則序列，基于此進(jìn)行比特流有效切分。本文的創(chuàng)新點(diǎn)包括：(1)利用有向圖整合二重關(guān)聯(lián)規(guī)則，得到唯一的多重關(guān)聯(lián)規(guī)則作為輸出結(jié)果，有效消除了輸出結(jié)果的冗余；(2)提供了一種判斷輸出結(jié)果合理性的方法，為用戶調(diào)整門(mén)限參數(shù)提供參考，確保最終結(jié)果正確可信。本文接下來(lái)的結(jié)構(gòu)安排如下：第2節(jié)介紹未知幀關(guān)聯(lián)分析的基本原理；第3節(jié)給出算法的具體流程；第4節(jié)給出算法的實(shí)際數(shù)據(jù)測(cè)試結(jié)果；最后對(duì)本文進(jìn)行了總結(jié)。

2 未知幀關(guān)聯(lián)分析原理

2.1鏈路幀結(jié)構(gòu)特征

鏈路幀一般由幀頭、數(shù)據(jù)段、校驗(yàn)和幀尾4部分組成，如圖1所示。某些特定類(lèi)型的鏈路幀可能省略其中某些部分，例如WiFi的控制幀不含數(shù)據(jù)段。

圖1 鏈路幀一般格式

幀格式中幀頭包含幀同步序列，以及地址域、控制域等常用域。同步序列是一個(gè)特殊的模式序列，用于使接收方能從接收的比特流中區(qū)分幀的起始與終止，一種鏈路協(xié)議的同步序列在通信過(guò)程中始終不變。地址域、控制域等常用域的長(zhǎng)度以及在特定幀的幀頭中的位置通常是固定的，因此這些常用域之間的相對(duì)位置固定，即存在固定位置差。與同步序列類(lèi)似，它們也能起到輔助界定幀起止的作用。這種幀頭結(jié)構(gòu)的組成規(guī)律可以概括如圖2所示，其中固定域是幀頭中內(nèi)容和位置均固定的比特字段，可變域的內(nèi)容在通信過(guò)程中往往會(huì)發(fā)生改變。這種固定域和可變域間隔出現(xiàn)的幀頭結(jié)構(gòu)在各種鏈路幀中普遍存在，是從比特流中識(shí)別鏈路幀頭結(jié)構(gòu)的基礎(chǔ)，尋找到幀頭結(jié)構(gòu)后就可以基于此將比特流切分成鏈路幀。

圖2 鏈路幀頭結(jié)構(gòu)

2.2 相關(guān)定義和概念

為描述鏈路幀頭部存在的固定序列及其位置關(guān)系，首先對(duì)比特流做一些定義。

頻繁序列用于描述幀頭部的同步序列和常用域。在缺乏關(guān)于比特流的先驗(yàn)知識(shí)時(shí)，以平均出現(xiàn)次數(shù)為基準(zhǔn)，其中為待統(tǒng)計(jì)的序列長(zhǎng)度，取值可變，理論上認(rèn)為出現(xiàn)次數(shù)大于該值的序列是“頻繁”的，但為了不過(guò)早排除幀頭部的有關(guān)序列，實(shí)際操作時(shí)一般取。設(shè)置上限參數(shù)是為了限制參與后續(xù)分析的頻繁序列數(shù)量，有利于提高算法效率。

(2)

3 未知幀切分算法

本文所提出的未知幀切分算法包括4個(gè)步驟：(1)設(shè)定頻繁度門(mén)限區(qū)間，從比特流中篩選出滿足頻繁度要求的序列，然后兩兩考察頻繁序列，尋找序列間的關(guān)聯(lián)規(guī)則；(2)為充分考慮關(guān)聯(lián)規(guī)則間的聯(lián)系，將得到的所有關(guān)聯(lián)規(guī)則按一定方式組織成有向圖；(3)為有向圖的序列節(jié)點(diǎn)分配坐標(biāo)，整合參與形成有向圖的二重關(guān)聯(lián)規(guī)則，獲得多重關(guān)聯(lián)規(guī)則；(4)根據(jù)多重關(guān)聯(lián)規(guī)則在比特流中出現(xiàn)的頻率判斷其合理性，根據(jù)判斷結(jié)果調(diào)整頻繁度門(mén)限區(qū)間，確保獲得的結(jié)果正確可信。

3.1 頻繁統(tǒng)計(jì)與關(guān)聯(lián)分析

頻繁統(tǒng)計(jì)通過(guò)對(duì)比特流中的序列計(jì)數(shù)，篩選出滿足頻繁度區(qū)間要求的序列參與后續(xù)關(guān)聯(lián)分析[12]。傳統(tǒng)單模式匹配算法[13,14]一次只能尋找一個(gè)特定模式序列，由于待統(tǒng)計(jì)的序列長(zhǎng)度不一，每種長(zhǎng)度又對(duì)應(yīng)多個(gè)序列，利用多模式匹配算法[15,16]能夠只掃描一次源數(shù)據(jù)找到多個(gè)模式，更適合比特流中的序列統(tǒng)計(jì)。結(jié)合比特流特征，將多模式匹配AC算法[17]稍作改進(jìn)，可有效面向比特流進(jìn)行頻繁序列統(tǒng)計(jì)，掃描一次源數(shù)據(jù)即可得所有長(zhǎng)度比特序列的計(jì)數(shù)[9]，再?gòu)闹羞x出滿足門(mén)限要求的序列即可。

在鏈路幀承載的上層數(shù)據(jù)未知時(shí)，可假定幀頭之外的幀數(shù)據(jù)段比特流是隨機(jī)的。通常在鏈路幀中數(shù)據(jù)段遠(yuǎn)長(zhǎng)于幀頭，數(shù)據(jù)段大量的隨機(jī)比特會(huì)干擾幀頭固定序列的尋找。通過(guò)頻繁統(tǒng)計(jì)得到的比特序列多數(shù)來(lái)自數(shù)據(jù)段，不能作為幀分界標(biāo)識(shí)。根據(jù)對(duì)幀結(jié)構(gòu)特征的分析可知，幀頭固定序列間存在位置差固定的關(guān)聯(lián)規(guī)則。由于數(shù)據(jù)段比特流具有隨機(jī)性，來(lái)自數(shù)據(jù)段的序列成為頻繁序列存在偶然性，且它們?cè)诒忍亓髦谐霈F(xiàn)的位置具有隨機(jī)性，這種“偽頻繁序列”之間存在關(guān)聯(lián)規(guī)則的概率很低。因此可以認(rèn)為，比特流中序列間位置差固定的關(guān)聯(lián)規(guī)則一般來(lái)自幀頭。

驗(yàn)證序列之間的關(guān)聯(lián)規(guī)則需要首先計(jì)算序列位置差，對(duì)于任意兩個(gè)頻繁序列和，相對(duì)位置差為有和兩種可能的順序，必須對(duì)兩種情況都進(jìn)行驗(yàn)證。驗(yàn)證時(shí)取和中出現(xiàn)次數(shù)較少者作為基準(zhǔn)，假定為，對(duì)每一個(gè)，計(jì)算與其距離最近且在其前面出現(xiàn)的的位置差，并確定是否有常數(shù)滿足關(guān)聯(lián)規(guī)則置信度要求；再計(jì)算與其距離最近且出現(xiàn)在其后面的的位置差，并確定是否有常數(shù)滿足關(guān)聯(lián)規(guī)則置信度要求[9]。驗(yàn)證流程如圖3所示。

圖3 關(guān)聯(lián)規(guī)則驗(yàn)證流程

通過(guò)關(guān)聯(lián)規(guī)則驗(yàn)證所得的是由若干關(guān)聯(lián)規(guī)則組成的集合。在缺乏先驗(yàn)知識(shí)時(shí)，用戶對(duì)集合中的關(guān)聯(lián)規(guī)則依然無(wú)從挑選。為解決此問(wèn)題，需要對(duì)集合中的關(guān)聯(lián)規(guī)則進(jìn)一步處理以獲得唯一可信的輸出。

3.2 關(guān)聯(lián)規(guī)則有向圖的生成

實(shí)驗(yàn)中發(fā)現(xiàn)，通過(guò)3.1節(jié)獲得的集合中的關(guān)聯(lián)規(guī)則之間會(huì)存在3種類(lèi)型的聯(lián)系：

(1)一條關(guān)聯(lián)規(guī)則的后繼是另一條關(guān)聯(lián)規(guī)則的先導(dǎo)；

(2)兩條關(guān)聯(lián)規(guī)則存在公共的先導(dǎo)，此時(shí)兩條關(guān)聯(lián)規(guī)則的后繼可能存在公共子序列；

(3)兩條關(guān)聯(lián)規(guī)則存在公共的后繼，此時(shí)兩條關(guān)聯(lián)規(guī)則的先導(dǎo)可能存在公共子序列。

圖4所示是關(guān)聯(lián)規(guī)則之間3種聯(lián)系的具體示例：圖4(a)中序列既是關(guān)聯(lián)規(guī)則的后繼，又是關(guān)聯(lián)規(guī)則的先導(dǎo)；圖4(b)中關(guān)聯(lián)規(guī)則與存在公共的先導(dǎo)，同時(shí)兩條關(guān)聯(lián)規(guī)則的后繼和與先導(dǎo)間隔距離相差4 bit，的末尾與的開(kāi)頭存在長(zhǎng)度為4 bit公共子序列0111；圖4(c)中關(guān)聯(lián)規(guī)則與存在公共的后繼序列，同時(shí)兩條關(guān)聯(lián)規(guī)則的先導(dǎo)和與后繼間隔距離相差3 bit,的開(kāi)頭與的末尾存在長(zhǎng)度為5 bit公共子序列00001。

圖4 關(guān)聯(lián)規(guī)則之間的3種聯(lián)系

關(guān)聯(lián)規(guī)則之間的這些聯(lián)系提供了通過(guò)生成有向圖對(duì)關(guān)聯(lián)規(guī)則進(jìn)行整合的基礎(chǔ)。

為充分發(fā)現(xiàn)集合中關(guān)聯(lián)規(guī)則之間的聯(lián)系，可將關(guān)聯(lián)規(guī)則按如下方式組織成帶權(quán)重有向圖：(1)兩個(gè)序列充當(dāng)節(jié)點(diǎn)；(2)序列的前后順序決定有向圖邊的方向；(3)兩個(gè)序列位置的間隔比特?cái)?shù)充當(dāng)有向邊的權(quán)重。按照此方式，作為示例，將圖4中4條關(guān)聯(lián)規(guī)則組織成如圖5所示的有向圖。

圖5 關(guān)聯(lián)規(guī)則有向圖

3.3 由有向圖生成多重關(guān)聯(lián)規(guī)則

有向圖生成后，為整合各關(guān)聯(lián)規(guī)則，獲得能作為比特流切分標(biāo)識(shí)的多重關(guān)聯(lián)規(guī)則，需要首先確定有向圖各節(jié)點(diǎn)序列在多重關(guān)聯(lián)規(guī)則中的相對(duì)位置。為了確定各節(jié)點(diǎn)序列的相對(duì)位置，可以將節(jié)點(diǎn)序列的第一個(gè)比特在多重關(guān)聯(lián)規(guī)則中出現(xiàn)的位置作為節(jié)點(diǎn)坐標(biāo)，通過(guò)節(jié)點(diǎn)坐標(biāo)間的差值表示節(jié)點(diǎn)的相對(duì)位置。為了計(jì)算節(jié)點(diǎn)序列坐標(biāo)，首先將有向圖用鄰接矩陣形式表示。設(shè)是有個(gè)頂點(diǎn)的有向圖，其中表示頂點(diǎn)集合，表示邊的集合，則的鄰接矩陣可定義為有如下性質(zhì)的階方陣：

(4)

節(jié)點(diǎn)坐標(biāo)只有相對(duì)意義，在計(jì)算坐標(biāo)前，可任選一節(jié)點(diǎn)，為其坐標(biāo)賦值0，再結(jié)合鄰接矩陣即可計(jì)算出其余節(jié)點(diǎn)序列坐標(biāo)。節(jié)點(diǎn)序列坐標(biāo)計(jì)算過(guò)程如表1所示。

表1 有向圖各節(jié)點(diǎn)坐標(biāo)的計(jì)算

表2 節(jié)點(diǎn)坐標(biāo)計(jì)算結(jié)果

根據(jù)節(jié)點(diǎn)序列坐標(biāo)，可確定各節(jié)點(diǎn)序列在未知幀頭部的順序。實(shí)驗(yàn)中發(fā)現(xiàn)，計(jì)算坐標(biāo)時(shí)會(huì)出現(xiàn)兩序列坐標(biāo)之差小于前一序列長(zhǎng)度的情況。這是由于兩序列存在公共子序列，此時(shí)需將存在公共子序列的兩序列合并。如表2中=10100001,=00001100，坐標(biāo)分別為-31, -28，兩者坐標(biāo)之差為3，小于的長(zhǎng)度，末尾與開(kāi)頭存在公共子序列00001，這時(shí)將二者合并成序列10100001100，并將合并所得序列坐標(biāo)設(shè)為(兩者中坐標(biāo)較小者)坐標(biāo)即可。

合并完成后，根據(jù)合并后序列的長(zhǎng)度和序列坐標(biāo)計(jì)算相鄰序列的位置間隔，即可得多重關(guān)聯(lián)規(guī)則。由表2中的節(jié)點(diǎn)坐標(biāo)計(jì)算結(jié)果，進(jìn)行序列合并后所得多重關(guān)聯(lián)規(guī)則如圖6所示。

3.4 多種關(guān)聯(lián)規(guī)則的合理性判斷

獲得多重關(guān)聯(lián)規(guī)則后，可判斷其合理性：若未知比特流中包含條鏈路幀，則幀頭在比特流中也會(huì)出現(xiàn)次。通過(guò)3.1節(jié)的關(guān)聯(lián)分析所得集合中的關(guān)聯(lián)規(guī)則來(lái)自幀頭，因此它們出現(xiàn)的次數(shù)一般會(huì)與相等，受幀數(shù)據(jù)段偶然出現(xiàn)的關(guān)聯(lián)規(guī)則干擾，部分關(guān)聯(lián)規(guī)則出現(xiàn)次數(shù)可能略大于。通過(guò)對(duì)3.1節(jié)所得集合中各關(guān)聯(lián)規(guī)則出現(xiàn)次數(shù)，即式(1)中的取平均值來(lái)估測(cè)值，設(shè)所得平均值為。再統(tǒng)計(jì)所得多重關(guān)聯(lián)規(guī)則在比特流中出現(xiàn)的次數(shù)，設(shè)為。若，則認(rèn)為結(jié)果合理；若與相差過(guò)大()，則結(jié)果不可信，需調(diào)整重新分析。

圖6 多重關(guān)聯(lián)規(guī)則

經(jīng)過(guò)判斷確定多重關(guān)聯(lián)規(guī)則合理后，即可將其作為界定幀起始的標(biāo)識(shí)切分比特流。

4 實(shí)驗(yàn)

本文采用實(shí)際數(shù)據(jù)對(duì)算法進(jìn)行測(cè)試，使用Qt Creator 3.1.0平臺(tái)實(shí)現(xiàn)所提出的算法，硬件配置為：Intel i5-2450M, 2.5 GHz，雙核CPU, RAM 4 GB。

4.1 算法有效性驗(yàn)證

為驗(yàn)證算法的有效性，實(shí)驗(yàn)采用兩組Wireshark實(shí)際抓獲的數(shù)據(jù)集：Ethernet鏈路層數(shù)據(jù)，共1000個(gè)Ethernet幀，大小為1075 kb; WiFi鏈路層數(shù)據(jù)，共500個(gè)WiFi幀(382個(gè)數(shù)據(jù)幀，118個(gè)管理幀)，大小為458 kb。為方便測(cè)試，測(cè)試中只統(tǒng)計(jì)長(zhǎng)為8 bit的頻繁序列，更長(zhǎng)序列可以在此基礎(chǔ)上通過(guò)序列合并獲得。在1075 kb的Ethernet數(shù)據(jù)和458 kb的WiFi數(shù)據(jù)中，長(zhǎng)8 bit的序列出現(xiàn)的平均次數(shù)分別為4300和1830。分別設(shè)定為(0.50,0.75)和(0.90,1.20)，此時(shí)頻繁度門(mén)限分別為2150-3225和1647-2196，置信度門(mén)限設(shè)為0.3。

實(shí)驗(yàn)結(jié)果如表3所示?？梢钥闯觯跀?shù)據(jù)量較大時(shí)，算法能夠從中尋找到正確的比特流切分標(biāo)識(shí)。

表3 Ethernet和WiFi數(shù)據(jù)測(cè)試結(jié)果

在原數(shù)據(jù)中進(jìn)一步分析輸出序列，以Ethernet數(shù)據(jù)集輸出結(jié)果為例，確定輸出序列在原數(shù)據(jù)幀中的相對(duì)位置及承載的含義，結(jié)果如表4所示：Ethernet數(shù)據(jù)集輸出結(jié)果為6個(gè)長(zhǎng)度不等的序列之間間隔若干比特的多重關(guān)聯(lián)規(guī)則。最前面的序列“10101011”是Ethernet幀的特征序列，用于標(biāo)識(shí)一個(gè)Ethernet幀的開(kāi)始，后面的4個(gè)序列屬于Ethernet幀頭部源和目的MAC地址字段，最后一個(gè)序列屬于Ethernet的IP負(fù)載首部IP版本號(hào)和長(zhǎng)度字段。中間間隔比特位屬于幀頭部MAC地址字段，由于頻繁度門(mén)限設(shè)置的原因被排除在頻繁序列之外?；谶@種來(lái)自Ethernet幀頭的多重關(guān)聯(lián)規(guī)則，方案可正確切分Ethernet比特流。

4.2 上下限比例參數(shù)對(duì)算法的影響

表4 算法輸出結(jié)果承載含義

表5 頻繁度門(mén)限區(qū)間對(duì)算法的影響

從表5可以看出，隨著上下限比例參數(shù)差值增加，算法輸出的多重關(guān)聯(lián)規(guī)則序列長(zhǎng)度增加，方案所耗時(shí)間增長(zhǎng)。這是因?yàn)樵龃髤^(qū)間長(zhǎng)度后，篩選得到的頻繁序列更多，而方案所耗時(shí)間主要來(lái)自兩兩考察序列之間的關(guān)聯(lián)規(guī)則，這部分的時(shí)間復(fù)雜度為(為頻繁序列數(shù)目)。上下限比例參數(shù)差值增大后，結(jié)果可能包含錯(cuò)誤信息。因?yàn)樵谏舷孪薇壤齾?shù)差值增大后，篩選得到的頻繁序列更多，其中某些頻繁序列可能在幀頭不同位置出現(xiàn)多次，為不同位置的同一序列分配一個(gè)坐標(biāo)導(dǎo)致結(jié)果出錯(cuò)。根據(jù)3.4節(jié)的合理性判斷可發(fā)現(xiàn)這種錯(cuò)誤，發(fā)現(xiàn)后適當(dāng)縮小上下限差值即可。

為節(jié)省計(jì)算時(shí)間，在保證結(jié)果正確性的前提下，應(yīng)選取盡可能短的頻繁度門(mén)限區(qū)間。最短門(mén)限區(qū)間的具體取值(起點(diǎn)、終點(diǎn))會(huì)受待分析的鏈路比特流數(shù)據(jù)的影響。在實(shí)際應(yīng)用時(shí)，可結(jié)合3.4節(jié)的合理性判斷，經(jīng)過(guò)多次測(cè)試確定最短門(mén)限區(qū)間取值。根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)，初次設(shè)置可取0.5作為門(mén)限區(qū)間中點(diǎn)，再經(jīng)測(cè)試調(diào)整確定區(qū)間的具體取值。

4.3 與其他算法比較

文獻(xiàn)[11]提出的比特流分割算法，輸出結(jié)果是按出現(xiàn)次數(shù)降序排列的個(gè)關(guān)聯(lián)規(guī)則。采用4.1節(jié)數(shù)據(jù)集，在設(shè)置關(guān)聯(lián)規(guī)則置信度為0.9時(shí)，表6列出了算法輸出中排名前5的關(guān)聯(lián)規(guī)則序列(表中?表示間隔比特)。通過(guò)對(duì)比原數(shù)據(jù)分析，在Ethernet對(duì)應(yīng)的輸出結(jié)果中，第1位即為正確切分標(biāo)志；WiFi數(shù)據(jù)對(duì)應(yīng)輸出的前5位中不含正確切分標(biāo)志，正確標(biāo)志最早出現(xiàn)在輸出結(jié)果的第17位。在較大時(shí)，文獻(xiàn)[11]能保證輸出結(jié)果中包含正確比特流切分標(biāo)志，但正確標(biāo)志在輸出中位置不定，缺乏先驗(yàn)知識(shí)時(shí)，用戶對(duì)輸出結(jié)果無(wú)從選擇；在較小時(shí)，算法輸出的個(gè)關(guān)聯(lián)規(guī)則中可能不包含正確的切分標(biāo)識(shí)，結(jié)果不可信。本文算法能提供唯一輸出結(jié)果，有效消除輸出中的冗余；同時(shí)根據(jù)3.4節(jié)的合理性判斷與參數(shù)調(diào)整，可確保最終結(jié)果正確可信。與文獻(xiàn)[11]相比，本文算法輸出結(jié)果唯一且可信度更高。

表6 文獻(xiàn)[11]算法輸出結(jié)果

在與4.1節(jié)相同的數(shù)據(jù)集上，本文算法和文獻(xiàn)[11]算法進(jìn)行了運(yùn)算時(shí)間的比較測(cè)試，實(shí)驗(yàn)結(jié)果如表7所示。由于算法的復(fù)雜度主要來(lái)自兩兩考察頻繁序列之間的關(guān)聯(lián)規(guī)則，文獻(xiàn)[11]認(rèn)為超過(guò)平均次數(shù)的序列均為頻繁序列，未設(shè)置頻繁度上限，需要考察的頻繁序列數(shù)量超過(guò)本文算法，對(duì)相同的鏈路比特流數(shù)據(jù)，本文算法的處理效率高于文獻(xiàn)[11]算法。

表7 不同算法運(yùn)算時(shí)間比較(s)

以上實(shí)驗(yàn)結(jié)果表明，對(duì)幀頭部存在位置差固定的關(guān)聯(lián)規(guī)則的鏈路比特流，在設(shè)定合理門(mén)限后，算法能在相對(duì)較短的時(shí)間內(nèi)獲得有效的比特流切分標(biāo)識(shí)，實(shí)現(xiàn)比特流切分。

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

對(duì)鏈路層截獲的比特流數(shù)據(jù)，如何在缺乏先驗(yàn)知識(shí)的情況下獲取其中承載的有用信息是一項(xiàng)重要的研究課題，分析有用信息的第1步要求正確切分比特流提取鏈路幀。本文分析了一般鏈路幀的幀格式特征，結(jié)合數(shù)據(jù)挖掘的關(guān)聯(lián)分析方法，從未知比特流中尋找能作為未知幀切分標(biāo)識(shí)的多重關(guān)聯(lián)規(guī)則，基于此對(duì)未知比特流進(jìn)行有效切分。最后結(jié)合實(shí)際數(shù)據(jù)，通過(guò)實(shí)驗(yàn)測(cè)試了方案的有效性，實(shí)驗(yàn)結(jié)果證明方案能有效尋找到比特流中標(biāo)識(shí)幀起始的定界序列，為后續(xù)鏈路層數(shù)據(jù)的解析工作提供了支撐。當(dāng)然方案還有改進(jìn)的地方，例如頻繁門(mén)限區(qū)間目前還需要多次測(cè)試后才能確定，如何自適應(yīng)確定最佳頻繁門(mén)限區(qū)間需要進(jìn)一步研究；在切分比特流之后，如何在缺乏先驗(yàn)知識(shí)的情況下解析鏈路幀承載的信息也是下一步研究的重點(diǎn)。

[1] WRIGHT C, MONROSE F, and MASSON G M. HMM profiles for network traffic classification[C]. Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security. ACM, Washington, D.C., USA, 2004: 9-15. doi: 10.1145/1029208.1029211.

[2] 孫欽東, 郭曉軍, 黃新波. 基于多模式匹配的網(wǎng)絡(luò)視頻流識(shí)別與分類(lèi)算法[J]. 電子與信息學(xué)報(bào), 2009, 31(3): 759-762. doi: 10.3724/SP.J.1146.2008.00301.

SUN Q, GUO X, and HUANG X. Algorithm of network video stream recognition and classification based on multi-pattern matching[J].&, 2009, 31(3): 759-762. doi: 10.3724/SP.J.1146.2008.00301.

[3] 王變琴, 余順爭(zhēng). 未知網(wǎng)絡(luò)應(yīng)用流量的自動(dòng)提取方法[J]. 通信學(xué)報(bào), 2014, 35(7): 164-171. doi: 10.3969/j.issn.1000-436x. 2014.07.020.

WANG B and YU S. Automatic extraction for the traffic of unknown network applications[J]., 2014, 35(7): 164-171. doi: 10.3969/j.issn. 1000-436x.2014.07.020.

[4] 高長(zhǎng)喜, 吳亞飚, 王樅. 基于抽樣分組長(zhǎng)度分布的加密流量應(yīng)用識(shí)別[J]. 通信學(xué)報(bào), 2015, 36(9): 65-75. doi: 10.11959/j.issn. 1000-436x.2015171.

GAO C, WU Y, and WANG C. Encrypted traffic classification based on packet length distribution of sampling sequence[J]., 2015, 36(9): 65-75. doi: 10.11959/j.issn.1000-436x.2015171.

[5] 朱玉娜, 韓繼紅, 袁霖, 等. SPFPA: 一種面向未知安全協(xié)議的格式解析方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2015, 52(10): 2200-2211. doi: 10.7544/issn1000-1239.2015.20150568.

ZHU Y, HAN J, YUAN L,. SPFPA: A format parsing approach for unknown security protocols[J]., 2015, 52(10): 2200-2211. doi: 10.7544/issn1000-1239.2015.20150568.

[6] 朱玉娜, 韓繼紅, 袁霖, 等. 基于主體行為的多方安全協(xié)議會(huì)話識(shí)別方法[J]. 通信學(xué)報(bào), 2015, 36(11): 190-200. doi: 10.11959/j.issn.1000-436x.2015273.

ZHU Y, HAN J, YUAN L,. Towards session identification using principal behavior for multi-party secure protocol[J]., 2015, 36(11): 190-200. doi: 10.11959/j.issn.1000-436x.2015273.

[7] 邢萌, 王韜, 吳楊, 等. 一種提高鏈路層加密比特流識(shí)別率的新方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(11): 3443-3447. doi: 10.3969/j.issn.1001-3695.2015.11.057.

XING M, WANG T, WU Y,. New method to improve identification rate of encrypted bit stream in data link layer[J]., 2015, 32(11): 3443-3447. doi: 10.3969/j.issn.1001-3695.2015.11.057.

[8] 鄭杰, 朱強(qiáng). 未知單協(xié)議數(shù)據(jù)幀的地址分析與研究[J]. 計(jì)算機(jī)科學(xué), 2015, 42(11): 184-187. doi: 10.11896/j.issn.1002-137X. 2015.11.038.

ZHENG J and ZHU Q. Analysis and research on address message of unknown single protocol data frame[J].2015, 42(11): 184-187. doi: 10.11896/j.issn. 1002-137X.2015.11.038.

[9] 金凌. 面向比特流的未知幀頭識(shí)別技術(shù)研究[D]. [碩士論文], 上海交通大學(xué), 2011.

JIN L. Study on bit stream oriented unknown frame head identification[D]. [Master dissertation], Shanghai Jiao Tong University, 2011.

[10] WU X, ZHU X, WU G Q,. Data mining with big data[J]., 2014, 26(1): 97-107. doi: 10.1109/TKDE.2013.109.

[11] 王和洲, 薛開(kāi)平, 洪佩琳, 等. 基于頻繁統(tǒng)計(jì)和關(guān)聯(lián)規(guī)則的未知鏈路協(xié)議比特流切割算法[J]. 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2013, 43(7): 554-560. doi: 10.3969/j.issn.0253-2778.2013.07.006.

WANG H, XUE K, HONG P,An unknown link protocol bit stream segmentation algorithm based on frequent statistics and association rules[J]., 2013, 43(7): 554-560. doi: 10.3969/j.issn.0253-2778.2013.07.006.

[12] AGRAWAL R, IMIELINSKI T, and SWAMI A. Mining association rules between sets of items in large databases[C]. Proceedings of ACM SIGMOD International Conference on Management of Data. Washington, D.C, USA, 1993: 207-216. doi: 10.1145/170036.170072.

[13] KNUTH D E, MORRIS,J J H, and PRATT V RFast pattern matching in strings[J]., 1977, 6(2): 323-350. doi: 10.1137/0206024.

[14] BOYER R S and MOORE J S. A fast string searching algorithm[J]., 1977, 20(10): 762-772. doi: 10.1145/359842.359859.

[15] HONG Y D, KE X, and YONG C. An improved Wu-Manber multiple patterns matching algorithm[C]. IEEE Performance, Computing and Communications Conference, Phoenix, Arizona, USA, 2006: 674-680. doi: 10.1109/.2006.1629469.

[16] FAN J J and SU K Y. An efficient algorithm for matching multiple patterns[J]., 1993, 5(2): 339-351. doi: 10.1109/69.219740.

[17] AHO A V and CORASICK M J. Efficient string matching: an aid to bibliographic search[J]., 1975, 18(6): 333-340. doi: 10.1145/360825.360855.

Data Link Bit Stream Oriented Association Analysis on Unknown Frame

XUE Kaiping①LIU Bin①WANG Jinsong②LI Wei①XUE Yingjie①

①(,,230027,)②(,610041,)

In the electronic countermeasure, the opponent’s bit stream can be captured. However, without any knowledge about the type of data link protocol, the existing protocol analyzing tools can not analyze the useful information from the bit stream. To further get the carried information, the bit stream should be segmented to frames firstly. According to the general rules of frame structure, a bit stream segmentation algorithm is proposed based on data mining, in which, the multi-association rule indicating the beginning of frames can be identified by using frequent sequence statistics, association analysis and association rules integration. The test results show that, this algorithm can extract the valid segmentation flag from unknown bit stream and segment the bit stream correctly. Compared to the similar data mining based bit stream analyzing algorithms, this algorithm can be more efficient and produce a unique result which is of high reliability.

Data link bit stream; Unknown frame; Frequent statistics; Association analysis; Segmentation

TP393

A

1009-5896(2017)02-0374-07

10.11999/JEIT160289

2016-03-28；改回日期：2016-07-25；

2016-10-09

薛開(kāi)平 kpxue@ustc.edu.cn

國(guó)家自然科學(xué)基金(61379129)，中國(guó)科學(xué)院青年創(chuàng)新促進(jìn)會(huì)人才基金(2016394)

The National Natural Science Foundation of China (61379129), Youth Innovation Promotion Association CAS (2016394)

薛開(kāi)平： 男，1980年生，副教授，研究方向?yàn)橄乱淮鶬nternet網(wǎng)絡(luò)、網(wǎng)絡(luò)安全與分布式網(wǎng)絡(luò).

柳 彬： 男，1991年生，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)安全與協(xié)議分析.

王勁松： 男，1980年生，工程師，研究方向?yàn)榇髷?shù)據(jù)挖掘和數(shù)據(jù)可視化.

李 威： 男，1992年生，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)安全協(xié)議設(shè)計(jì)與分析.

薛穎杰： 女，1992年生，碩士生，研究方向?yàn)榫W(wǎng)絡(luò)安全和加密技術(shù).