基于TextRank算法的未知網絡協議幀定位方法

劉治國,宋廣躍,蔡文珠,劉慶利

(大連大學 a.通信與網絡重點實驗室; b.信息工程學院,遼寧 大連 116622)

0 概述

隨著計算機網絡技術的不斷發展,越來越多的網絡私有協議被應用于數據傳輸過程中,但此類私有協議通常不公開且具有固定格式[1-3]。如何從截獲的通信數據中識別出網絡私有協議是當前的一個重要研究課題,而在比特流數據中確定幀頭和幀尾以獲得完整的數據幀是該研究中亟需解決的問題。

國內外針對原始比特流形式的未知網絡協議通信數據識別已開展了很多研究,但由于比特流數據具有隨機性和無界性的特點[4-5],因此現有研究仍存在一定的局限性。文獻[6]分析鏈路層協議通用幀格式以及通信數據中各幀之間的相互關聯關系,通過對比特流數據中的序列進行統計和分析識別出同步序列,并以此為依據對比特流數據進行切分從而得到一個個完整的數據幀,但在序列統計過程中存在效率低下的問題。文獻[7]對通信數據進行挖掘,通過挖掘到的頻繁序列間的位置差分析其中的關聯關系,推斷出幀頭位置及幀長并實現幀切分,但該方法僅在幀長不定的情況下性能較好。文獻[8]通過改進傳統模式匹配算法實現比特流中的序列統計,并結合比特流特點提出剪枝算法以提高序列統計效率,同時減少空間占用,利用該方法可提取出通信數據中的頻繁序列,但其不適用于長頻繁序列的統計。文獻[9-10]采用數據挖掘中的關聯分析方法提取多重關聯規則序列并實現比特流切分,但該方法存在頻繁度門限區間難以確定的問題。為實現比特流形式數據幀的有效定界,本文提出一種基于TextRank的未知網絡協議幀定位方法(UPFLM),其能夠在比特流形式的未知網絡協議中準確定位數據幀的起始位置。

1 協議格式分析

無線網絡通信數據的獲取方式決定了預處理數據具有以下特點[11-12]:1)各幀首尾相接形成比特流;2)數據中只有“0”和“1”兩種元素。同時,針對IEEE 802.11、IEEE 802.3、異步傳輸模式(Asynchronous Transfer Mode,ATM)等已知網絡協議進行分析可知,完整的數據幀格式由幀頭、控制段、數據段和檢驗信息等組成,所有組成部分又可分為固定域與可變域[13],因此比特流形式的未知協議數據格式如圖1所示。

圖1 比特流形式的未知協議數據格式

針對比特流形式的未知網絡協議數據,為便于描述進行以下定義:

定義1比特流B的長度m為其所包含的比特個數。

定義2將比特流中長度為目標序列長度、位于不同位置的序列定義為一個節點,每個節點具有兩個鄰居節點。

定義3在長度為m的比特流B中,長度為n的序列的期望出現頻率為Paverage。比特流B中長度為n的序列共有m-n+1個,而長度為n的序列存在2n種可能,因此:

(1)

2 基于TextRank的未知協議幀定位方法

由上文分析可知,在比特流形式的未知協議數據中可以通過挖掘幀頭位置信息實現對幀的定位與切分。未知協議幀定位方法主要包括序列統計、關鍵序列提取以及幀頭序列挖掘3個主要步驟。

2.1 基于FLSS算法的序列統計

序列統計過程可以參考傳統模式匹配算法,其中,單模式匹配算法(如KMP、BM算法)每次遍歷比特流僅能統計一個目標字符串,多模式匹配算法(如AC、Wu-Manber算法)掃描一次比特流便可統計出所有目標序列的出現次數[14-15]。

針對比特流協議的數據特點,為統計出比特流中出現的所有序列,本文通過對傳統AC算法進行改進,提出定長序列統計(Fixed Length Sequence Statistics,FLSS)算法。在FLSS算法中包含目標序列的所有可能情況,采用枚舉所有長度為n序列的方式產生目標序列,并將其通過數組的形式進行存儲以構成字典,從而取代Trie樹減少空間占用[16]。每個目標序列可以定義為一個狀態,通過二元組形式表示為O(station,value),其中,station為狀態描述,在字典數組中表現為數組的下標,value為狀態的值,即序列的出現次數,在字典數組中表現為數組的值。同時,在統計過程中不存在匹配失敗的情況,失敗指針在這一過程中不起作用。為實現不同狀態之間的跳轉,綜合考慮狀態信息與讀入數據之間的關系,設計狀態跳轉函數:

new_station=(station %2n-1)×2+new_bit

(2)

其中,n表示目標序列長度,new_bit表示最新讀入比特位的值,station表示當前狀態,new_station表示將要跳轉的下一狀態。根據狀態跳轉函數可將最新讀入的比特值在狀態間進行轉換,從而統計出每個字符串的出現頻次,最終得到每個狀態station所對應的value值,即字典的數組值。

FLSS算法具體描述如下:

輸入目標序列長度n,比特流B

輸出二元組O(station,value)形式的狀態信息

步驟1根據給定的目標序列長度n,枚舉出所有目標序列,構造字典數組。

步驟2識別比特流B中初始長度為n的序列,更新其對應狀態的station、value信息。

步驟3讀入下一比特new_bit,根據狀態跳轉函數跳轉到下一狀態new_station并更新其value值。

步驟4若比特流B讀取完畢,則跳轉到步驟5;否則重復步驟3直至比特流B全部讀取完畢。

步驟5按照二元組中的value值對各狀態進行排序并輸出其狀態信息。

2.2 基于BitstreamRank的關鍵序列提取

在實際通信過程中,網絡協議的特征字段通常很長,當利用FLSS算法進行序列統計時,需要建立長度為2n的數組,直接對長序列進行統計意味著大量的空間會被占用,并且由于序列具有向下閉包性[17-18],即某一頻繁序列的子序列也是頻繁序列,因此對短序列進行統計并進一步處理得到關鍵序列。

為通過序列統計得到比特流中的關鍵序列,本文引入自然語言處理中的關鍵詞抽取算法TextRank[19],在此基礎上提出BitstreamRank算法,基于投票原理得到每個節點的權重以實現關鍵詞抽取。由于數據為比特流形式,因此算法主要包括狀態初始權重計算、節點權重計算和關鍵序列提取3個步驟。狀態初始權重計算的目的是設置狀態的投票權重,計算公式為:

VW(stationi)=P(stationi)-Paverage=

(3)

其中,stationi表示比特流B中起始為第i位、長度為n的序列對應的狀態,VW(stationi)表示stationi的投票權重,P(stationi)表示狀態i在比特流B中的實際出現頻率,Paverage為長度為n的序列期望出現頻率。通過式(3)可以設置各狀態的投票權重,當狀態的實際出現頻率P(stationi)小于期望出現頻率Paverage時,其投票權重為負;當P(stationi)大于期望出現頻率Paverage時,其投票權重為正。

為便于描述,將比特流中的每個序列定義為節點,狀態權重計算過程即利用某一節點的鄰居節點進行投票,從而獲得該節點在比特流B中的權重WS,計算公式為:

(4)

其中,nodei表示比特流中起始為第i位、長度為n的節點,WS為節點權重,stationt表示節點nodei對應的狀態,VM為狀態的初始權重,d表示阻尼系數,其意義為某一節點指向其他任意節點的概率,通常取經驗值0.85。

經過計算比特流中狀態的權重可知,如果某一序列為比特流中的關鍵序列,則其表現為連續權重較高的狀態。

長關鍵序列提取算法具體描述如下:

輸入比特流B,各節點權重WS

輸出長關鍵序列

步驟1查找各節點權重WS中的最大值max_WS。

步驟2按順序遍歷比特流B中的各節點。

步驟3如果節點權重大于0.75×max_WS,則判定此節點對應的序列為關鍵序列,執行步驟4;否則跳轉到步驟2。

步驟4如果下一個節點的權重也大于0.75×max_WS,則將兩序列按照位置關系合并為一個序列并重復步驟4;否則跳轉到步驟5。

步驟5將得到的關鍵序列進行存儲并記錄起始位置,若遍歷結束,則跳轉到步驟6;否則跳轉到步驟2。

步驟6輸出長關鍵序列信息。

2.3 基于歐氏距離的幀頭序列挖掘

幀定界問題中的關鍵是確定幀頭和幀尾位置。為解決這一問題,本文在提取比特流中的關鍵序列后,根據關鍵序列對比特流進行切分并計算切分后各序列之間的相似度,從而確定幀頭位置。

采用歐氏距離衡量序列間的相似度,兩序列間的相似度計算公式為:

(5)

其中,str1、str2表示兩序列,str1,m、str2,m表示兩序列的第m位的比特值,dist表示兩序列之間的歐氏距離,N為序列需要對比的長度,通常取兩序列中較短序列的長度或根據需要人為設置。

由于比特流切分后會得到多個序列,因此在兩序列相似度的基礎上,以多序列間平均相似度為依據,按照平均相似度由高到低的順序對關鍵序列進行排序。多序列間的平均相似度計算公式為:

(6)

其中,distaverage表示根據關鍵序列切分后得到的多個序列之間的平均相似度,k表示切分后得到的序列個數,ComTime表示需要比較的次數。經過排序后,平均相似度最高的關鍵序列位于幀頭,根據此序列即可完成幀定位與切分。

3 仿真驗證與結果分析

3.1 實驗設置

為對本文算法進行驗證,利用Wireshark軟件對同一主機不同時間的通信數據進行采集,并將采集到的數據包轉換為連續的比特流形式,從而生成實驗所用數據集。數據集詳細信息如表1所示。

表1 數據集信息

3.2 序列統計方法驗證

為驗證FLSS算法的有效性,采用上文構建的數據集進行實驗驗證。首先在J1數據集中對不同長度的序列進行統計,并與文獻[5]中的改進AC算法和傳統AC算法進行對比實驗,序列統計時間對比結果如圖2所示。可以看出,在數據集大小不變的情況下,3種算法的統計時間隨目標序列長度的增加而增加。統計時間增加的主要原因為在序列統計過程中需要根據目標序列長度構建字典數組,目標序列越長,字典數組越大,構建時間也會增加。當數據集及目標序列長度相同時,FLSS算法優于改進AC算法和傳統AC算法,其原因為改進AC算法及傳統AC算法需要構建Trie樹,且需統計長度為0～n的所有序列,而FLSS算法只需構建字典數組并統計指定長度的序列,因此FLSS算法的時間消耗低于其他兩種算法。

圖2 序列統計時間對比

為觀察數據集大小對序列統計過程的影響,分別將J1數據集～J4數據集在不同目標序列長度下進行實驗,實驗結果如圖3所示。可以看出,當目標序列長度不變時,序列統計時間隨數據集大小的增長而增加。序列統計時間主要包含字典數組構建時間與比特流遍歷時間,當數據集變大時,比特流長度增加,因此序列統計時間也隨之增加。當數據集大小不變時,目標序列長度越長,統計時間越長,符合之前實驗結論。綜上所述,FLSS算法能夠在不同大小的數據集中對不同長度的序列進行挖掘,且挖掘效果優于AC算法。

圖3 4個數據集在不同目標序列長度下的統計時間對比

3.3 BitstreamRank算法有效性驗證

為進一步驗證BitstreamRank算法的有效性,對J1數據集進行序列統計后獲取的數據進行處理,得到J1數據集的部分節點權重如圖4所示。可以看出,BitstreamRank算法能夠通過計算節點在數據中的權重有效識別出關鍵序列。

圖4 J1數據集部分節點權重

利用BitstreamRank算法對上述關鍵序列進行提取,并將序列提取結果與Wireshark捕獲到的原始數據進行對比分析,如表2所示。可以看出,BitstreamRank算法能夠對連續比特流中的關鍵序列進行有效提取。

表2 J1數據集關鍵序列提取

3.4 幀定位與切分效果分析

根據上文所得的關鍵序列提取結果對比特流進行初步切分,并對不同序列切分后得到的結果進行相似度分析,按照相似度從高到低進行排序。實驗首先對比本文UPFLM方法與文獻[5]中的比特流切分方法(Bitstream Segmentation Method,BSM)的時間消耗,然后對兩種方法的識別效果進行分析,采用準確率與誤識別率衡量幀定位方法的準確度。

1)幀定位準確率R的計算公式為:

(7)

其中,Frecog表示定位結果中定位正確的幀數量,Ftotal表示數據集中包含的幀數量。

2)誤識別率Regerr的計算公式為:

(8)

其中,Ferr表示幀定位過程中被錯誤判定為幀頭的數量。

本文UPFLM方法與BSM方法在J1數據集～J4數據集上的幀定位時間對比結果如圖5所示。可以看出,在整體幀定位過程中,UPFLM方法的幀定位時間少于BSM方法。其主要原因為BSM方法需對提取到的短序列進行序列拼接,并且要考察所有序列之間的位置關系來判定幀頭位置,而UPFLM方法只需對位于不同位置的同一關鍵序列的后續序列進行分析,因此減少了幀定位時間。

圖5 UPFLM與BSM方法的幀定位時間對比

UPFLM與BSM方法在J1數據集～J4數據集上的幀定位準確率對比結果如圖6所示。可以看出,UPFLM方法能夠有效對未知協議數據進行幀定位,準確率高于90%。但由于通信數據的數據段中可能包含相同的關鍵序列,這些冗余序列對切分結果會造成一定影響,因此通信數據的每一幀所包含的數據段越長,冗余序列出現的可能性越大,則幀定位效果越差。J4數據集的準確率低于其他兩個數據集的主要原因為J4數據集中包含兩種協議,當數據集只含有單一協議時,幀頭序列保持不變,則定位準確率較高,當數據集有多種協議共存時,幀頭序列具有多種可能,因此定位準確率會降低。

圖6 UPFLM與BSM方法的幀定位準確率對比

對幀定位得到的結果進行統計,可以得到UPFLM與BSM方法的誤識別率對比結果,如圖7所示。可以看出,UPFLM方法的誤識別率低于BSM方法。其主要原因為UPFLM方法只需判定后續序列相似度最高的關鍵序列位置為幀頭位置,而BSM方法中多個特征序列之間的關系會對定位準確率產生影響。

圖7 UPFLM與BSM方法的誤識別率對比

綜上所述,本文UPFLM方法能夠在比特流形式的未知協議數據中成功定位出位于幀頭的序列,依此判定幀頭位置,并且在定位速度與準確率方面均優于BSM方法。

4 結束語

本文根據比特流形式的通信數據特點,利用FLSS算法統計出通信數據中目標序列的出現頻率,并基于通信協議格式,在關鍵序列提取過程中引入BitstreamRank算法對關鍵序列進行挖掘,根據關鍵序列對比特流進行切分并計算切分后各序列之間的相似度,從而定位幀頭位置。仿真結果表明,該方法能有效地對比特流形式的未知協議數據進行分析,從而完成幀定位與幀切分,并且在定位速度與準確率方面均優于BSM方法。后續將對通過本文UPFLM方法獲得的幀數據做進一步分析,并在大量同類型未知網絡協議的數據幀及關鍵序列基礎上,準確提取出其格式特征,實現未知網絡協議的有效識別。