基于Simhash的協議數據高頻相似序列提取算法

黃學波，徐正國，燕繼坤

盲信號處理國家重點實驗室，成都 610041

1 引言

隨著互聯網應用和傳輸的數據類型日趨繁雜，網絡中出現的協議種類越來越多且越來越復雜。出于網絡安全考慮，網絡服務提供商和網絡管理者更加依賴于網絡協議分析技術。協議特征提取技術是相關研究的基礎之一，而傳統的依賴人工進行的協議特征提取工作已經越發捉襟見肘[1]。在此背景下，自動化的網絡協議分析技術成為了研究的熱點。

在協議逆向工程和深度包檢測等網絡協議分析技術的相關研究中，高頻相似序列的提取是一種常用的技術手段，應用于協議特征提取、協議分類與聚類、格式規范挖掘等。高頻相似序列是指同一協議中出現的大量相同或相似的局部序列。在一種協議中，協議字段中除了部分取值隨機性較強的字段之外，大部分字段的取值都在一定范圍內，這些取值表示了協議的不同類別、狀態、標記等信息，可以作為該協議的一種特征并用于后續的協議分析。

在協議特征挖掘的相關研究中，提取協議特征關鍵詞主流方法采用的是高頻相似序列提取。協議特征關鍵詞是指協議報文序列中可以區分協議類型的比特序列[2]，有些研究中也稱為語義關鍵詞[3]、協議token[4]、特征字符串[5]等。高頻相似序列提取通常有兩種不同的實現方式：一是采用基于頻率統計的頻繁集挖掘方法；二是采用序列相似性比對方法。

基于頻率統計或頻繁集挖掘的方法由于其算法的高效性，應用比較廣泛。琚玉建等人[6]提出的基于自適應權值的指紋特征提取算法通過頻繁序列挖掘得到協議的指紋特征，類似的還有蔡樂等人[7]提出的基于關聯規則挖掘的協議特征提取算法。基于頻率統計的方法雖然在一些情況下能夠取得較好的效果且效率較高，但在處理含有變長或位置不定字段時效果較差。

序列對齊是序列相似性比對中常用的方法，通過將協議數據兩兩比對得到高頻相似序列和出現的位置。序列對齊的經典算法是多序列比對算法，最早是由Beddoe[8]將其從生物信息領域應用到了著名的協議逆向項目PI[8]中，該項目使用了Smith-Waterman 算法。除此以外，其他一些協議逆向工具比如netzob、ScriptGen[9]中還用到了Needleman-Wunsch等序列比對方法。該類方法的問題是，對于大量協議報文序列來說，將每一個序列都與其他序列進行比較的計算復雜度是非常高的。例如使用Needleman-Wunsch 算法進行多序列比對，假設有M個序列，平均長度為N，當M=5 000，N=1 000 時需要次比較[10]。

針對上述問題，本文提出了一種用于網絡協議分析的高頻相似序列提取算法。該算法針對協議序列特點將用于文本處理的Simhash算法做了改進，在擁有較高執行效率的同時也能夠達到較高準確率。

2 Simhash算法簡介

傳統的哈希算法將任意長度的輸入變換為固定長度的輸出，內容相近的輸入得到的輸出相差一般較大。但是在某些應用領域中需要將相似的輸入映射為相似的輸出，即滿足：

（1）d(x,y)≤d1時P(H(x)=H(y))≥p1；

（2）d(x,y)≥d2時P(H(x)=H(y))≤p2。

其中d(x,y)表示x與y的距離，P表示概率，H表示哈希函數。符合上述條件的一類哈希算法稱為局部敏感哈希（Local Sensitive Hash，LSH）算法。根據LSH算法的特性，兩個任意長度序列之間的相似度比較被轉換為長度較短的哈希值之間的比較，在數據量較大時可大幅提高比較的效率。

Simhash 是 由 Charikar 等 人[11]提 出 的 一 種 LSH 算法，而后被谷歌的Manku 等人[12]應用到網頁去重中，在處理海量的文本數據時有較好的效果。此外，Simhash還應用于生物測序數據去重[13]、多媒體數據檢索[14]、惡意代碼檢測[15]等領域。

Simhash 算法的主要思想是降維，即將高維的特征向量映射為一定比特長度的指紋，通過比較指紋的海明距離來確定原始序列的相似性。該算法應用在文本處理中的流程可概括為：

（1）分詞：將文本轉換為特征向量，由文本中的詞（即特征）加權后按順序排列組成；

（2）計算哈希：對于特征向量集中的每一個特征，用傳統哈希函數計算得到f比特的哈希值H；

（3）加權：對每一個特征，初始化一個f比特的向量v，若H的第i位為1，則向量v的第i位加上該特征的權值，否則減去該特征的權值；

（4）合并、降維：初始化一個f比特的向量V，將特征向量集中按上述步驟得到的所有向量v累加，若累加后的第i位為正數則向量V的第i位為1，否則為0，向量V即為文本的Simhash指紋。

協議二進制序列與文本的主要區別是二進制序列無法進行分詞，并且長度可能較短。若要將Simhash算法應用于協議序列，需要根據文本與二進制序列的差異對算法進行修改。

3 高頻相似序列提取算法

3.1 數據預處理

相比協議載荷部分，協議頭部包含了協議數據中的主要特征，因此本文研究對象是協議報文序列的頭部。在頭部長度未知的情況下，本研究根據實際經驗截取固定長度的頭部序列作為后續研究的輸入。

協議報文序列在無任何先驗知識的條件下不存在“分詞”的概念，也沒有其他自然的劃分依據，需要自行設計劃分方法。對文本數據來說，計算Simhash的粒度通常是整段話或整個文章，但在一個協議報文的二進制序列中，高頻相似序列的提取是要找出相似性較高的局部序列，而不是比較整個報文序列的相似性。因此需要將協議報文序列分割為許多局部序列，對應“文本”的概念，然后再對它們進行“分詞”。

這里首先采用自然語言處理中的n-gram方法將序列分割，該方法在協議特征提取中也有較多的應用[16]。例如序列0x12345按n=3 可分割為集合{0x123，0x234，0x345}，集合中的每一個元素對應著一個“文本”。然后再對每一個“文本”進行分詞，同樣使用n-gram 的方式以更小的粒度切分。

通過上述方式，完成了對協議數據報文序列的預處理，將每個序列對應于文本分詞的處理方式進行了分割。假設原始數據有m個報文序列，預處理步驟總結如下：

（1）截取每個序列的前N個字節，得到大小為m×N的原始數據矩陣Morigin；

（2）對Morigin的每一行數據按n-gram方式分割（單位為字節），n=n1，得到大小為m×(N-n1+1)的“文本”矩陣Mtext；

（3）對Mtext中的每一行“文本”按n-gram方式分割（單位為比特），n=n2，得到m×(N-n1+1)×(n1×8-n2+1)個“詞”，記為Mword。

整個預處理流程如圖1所示。

圖1 數據預處理流程圖

3.2 二進制序列的Simhash算法

要將Simhash 算法應用在二進制數據處理中，除了文本分詞外，還需解決算法實現過程中的其他問題。首先在文本去重問題中，Simhash 算法對于不同的詞可以設置不同的權值用以表示詞的重要程度。在二進制序列中，各個字節之間沒有重要程度之分，即權值都為1。

通常用Simhash 處理的一條文本數據中包含的詞的數量往往遠遠大于本文算法中的“分詞”數量。Simhash原始算法將文本數據映射為64 比特長度的指紋序列，由于文本維數很高，這樣的映射是合理的。但根據前文的預處理方法，一條“文本”的維數往往小于64，因此為了符合二進制“文本”的特點同時提高計算性能，將指紋長度降低。這里取1 字節即8 比特，即大部分協議字段長度的最小單位。

本文提出的適用于二進制協議報文序列的改進Simhash算法如下：

通過上面的改進Simhash算法，得到了所有“文本”的Simhash值矩陣Msh，其中每一個元素是8維的0-1向量。為了比較相似性，最常用的方法是比較它們的海明距離。本文的序列提取衡量指標除了相似性之外還有高頻特征，可以先根據上述算法的結果確定哪些二進制序列是高頻的，然后再考查高頻序列對應的Simhash值之間的相似性，這樣也可以減少比較次數，提高算法性能。在得到了所有的高頻相似序列之后，再在原始數據中找出對應的二進制序列，并將相鄰的序列拼接即得到最后的結果。整體的算法流程如下：

序列拼接是指將多個在位置上有重疊部分的序列合并成一個序列的過程。拼接可以減少結果序列數量，但待拼接序列的重疊部分的取值不一定相同。為了提高算法效率，這里采用較為簡單的處理方式，即將取值不同的位置用通配符代替，表示該位置的取值不確定。比如有兩個序列開始位置為0與3，取值分別為abcdefg和aefbh，拼接后的序列為abc*ef*h。

該二進制序列的Simhash算法與傳統的文本Simhash算法相比，指紋長度更短且指紋間的比較次數更少，在本文的問題上可以達到更好的效果。

3.3 評價指標

Simhash算法的優勢在于處理海量文本數據的高效性，并且已經在實際應用中得到驗證，但該算法在本文的問題上還沒有公認的評價標準。除了算法的時間復雜度外，為了評價算法的有效性，本文還提出一種評價指標來評估算法的準確程度。

首先要確定評價指標的比較基準。本研究選取已知協議各字段的實際取值作為高頻相似序列提取正確與否的參考基準。這是由于協議報文頭部字段中含有的控制信息通常會重復出現在協議通信數據中而成為高頻序列。

計算基準的高頻序列時，先將原始的報文數據按真實的字段劃分切分，對每一個字段統計其取值范圍，若一個字段的一種取值出現次數高于指定的閾值，則認為是高頻序列，且同一個字段可能有多個高頻序列。這樣得到的高頻序列的集合S={s1,s2,…,sq}就可以作為評價的基準。

本文的高頻相似序列覆蓋率定義為：

其中，|· |表示序列長度，T={t1,t2,…,tp}為Simhash算法得到的高頻相似序列。表示兩個序列的交集長度，即相同位置出現相同值的個數（含有通配符時視為是相同值），一方面反映了兩個序列位置上的準確性，另一方面反映了序列取值的偏差程度。根據定義可知，覆蓋率的取值范圍為[0,1]，S中的所有元素都能被T中的元素完全覆蓋時取1，都不能覆蓋時取0。該指標可以在一定程度上反映高頻相似序列提取結果的準確率。

4 實驗與分析

4.1 對比算法

為了更好地對比算法性能，在實驗中選擇與另外兩種在網絡協議分析中較為常見的算法進行比較。

首先是基于n-gram的頻率統計算法。該算法先將數據按n-gram 方式切分，然后對每個序列片段出現的頻率進行統計，頻率大于閾值則認為是高頻序列，最后將相鄰的高頻序列拼接。這種算法因為實現簡單，所以處理效率很高，但在處理字段長度可變協議和文本協議時效果不好，并且只計算了完全相同而不是相似的序列。

第二種算法是基于Needleman-Wunsch 算法（簡稱NW算法）的序列比對算法。該算法通過計算兩個序列的最長公共子序列，可以實現序列對齊、相似性比較等功能。比如有兩個字符串序列aabcdab和abbccdbaccb，它們通過該算法得到的最長公共子序列為a*b*cd*a**b，*表示不匹配的位置。由于該算法的比對結果長度為兩個序列的最大長度，本文要計算的高頻相似序列為局部序列，故將比對結果切分為若干子序列，分割依據是連續出現*的個數大于閾值時則分割。該算法對于字段位置不敏感，準確率較高，但算法效率較低。

4.2 實驗環境與數據集

本文的實驗環境及其配置如表1 所示。實驗數據均為在某校園骨干網和實驗室網絡環境下采集的網絡協議數據。通過wireshark網絡協議分析工具提取了常見的四種二進制協議和一種文本協議，如表2所示。

由于http協議的報文數據并不一定都有協議頭，甚至是只包含非文本的載荷，為了在實驗中測試本文算法在二進制協議和文本協議中的效果，http協議數據選擇了只含有文本協議頭的數據。

表1 實驗環境及配置

表2 實驗數據

4.3 參數選擇

在數據預處理時，用到了兩次n-gram算法，參數分別是n1和n2。根據上文的分析，高頻序列對應著高頻字段，它們之間的長度是有相關性的。協議數據按內容類型可分為二進制協議和文本協議，這兩類協議的字段劃分方式不同。對于二進制協議，字段劃分位置通常是確定的，長度一般在1～8個字節之間，且短字段較多，這里設n1=3。而對文本協議來說，通常以分隔符來劃分字段，比如空格或換行，字段往往較長，這里設n1=6。對于“詞”長度n2來說，圖2是兩種協議數據在本文算法中取不同的n2得到的覆蓋率。

圖2 不同n2 值的覆蓋率

從圖2 的結果中可以看出，取n2=5 時幾種協議數據的覆蓋率最高。這是由于n2設置過小，則“詞”取值范圍過窄，導致哈希運算效果不明顯，設置過大時，一條“文本”中包含的“詞”較少，導致“文本”特征較少。

4.4 實驗結果

4.4.1 時間性能對比實驗

為驗證本文提出的高頻相似序列算法的時間性能，選取一種二進制協議和一種文本協議分別統計在不同的報文數量時算法的運行時間，并與兩種對比算法進行比較。圖3（a）是ip協議的實驗結果，協議數據截取長度N=20，圖3（b）是http協議的結果，N=200。

從圖3 中可以看到，NW 算法相比另外兩種算法運行效率非常低。除了比對次數多的因素外，該算法是全局序列比對算法，當序列長度N增大時該算法的運行時間呈指數級增長。n-gram 算法不需要序列間的比較，時間主要消耗在統計每個序列片段的出現頻率上。本文提出的二進制序列Simhash 算法由于在提取高頻序列時已經將待比較的序列數量大幅縮減，并且比較的序列長度都是8比特的0-1序列，運行效率較高，已經接近于n-gram算法。

圖3 運行時間結果對比

4.4.2 覆蓋率對比實驗

為了衡量本文提出算法的有效性，針對實驗數據集中的五種協議數據，分別計算它們的覆蓋率，同時與另外兩種對比實驗的覆蓋率進行比較，得到結果如圖4所示。

圖4 覆蓋率結果對比

從整體上看，NW 算法的平均覆蓋率為78.76%，是三種算法中最高的，但這是以犧牲時間來換取的。Simhash 算法的平均覆蓋率為74.28%，n-gram 算法的平均覆蓋率為60.26%。n-gram 算法由于沒有考慮高頻序列的位置變化和取值的相似性，導致覆蓋率較低。結合實驗結果，Simhash 算法兼顧了結果的準確率和運行效率，實用性更強。

5 結束語

本文提出了一種基于Simhash 的高頻相似序列提取算法。Simhash 算法的應用場景一般是文本處理，本文根據二進制序列的特征將Simhash 算法引入到了協議數據處理中。通過實驗證明，該算法在時間效率上大大優于序列比對算法，并且平均覆蓋率達到了74.28%，接近于序列比對算法，能夠為協議分析研究提供支撐。在下一步的研究中，將進一步優化該算法并探索Simhash算法在其他二進制處理和協議分析等問題中的應用。