基于Simhash的協(xié)議數(shù)據(jù)高頻相似序列提取算法

黃學(xué)波，徐正國，燕繼坤

盲信號(hào)處理國家重點(diǎn)實(shí)驗(yàn)室，成都 610041

1 引言

隨著互聯(lián)網(wǎng)應(yīng)用和傳輸?shù)臄?shù)據(jù)類型日趨繁雜，網(wǎng)絡(luò)中出現(xiàn)的協(xié)議種類越來越多且越來越復(fù)雜。出于網(wǎng)絡(luò)安全考慮，網(wǎng)絡(luò)服務(wù)提供商和網(wǎng)絡(luò)管理者更加依賴于網(wǎng)絡(luò)協(xié)議分析技術(shù)。協(xié)議特征提取技術(shù)是相關(guān)研究的基礎(chǔ)之一，而傳統(tǒng)的依賴人工進(jìn)行的協(xié)議特征提取工作已經(jīng)越發(fā)捉襟見肘[1]。在此背景下，自動(dòng)化的網(wǎng)絡(luò)協(xié)議分析技術(shù)成為了研究的熱點(diǎn)。

在協(xié)議逆向工程和深度包檢測等網(wǎng)絡(luò)協(xié)議分析技術(shù)的相關(guān)研究中，高頻相似序列的提取是一種常用的技術(shù)手段，應(yīng)用于協(xié)議特征提取、協(xié)議分類與聚類、格式規(guī)范挖掘等。高頻相似序列是指同一協(xié)議中出現(xiàn)的大量相同或相似的局部序列。在一種協(xié)議中，協(xié)議字段中除了部分取值隨機(jī)性較強(qiáng)的字段之外，大部分字段的取值都在一定范圍內(nèi)，這些取值表示了協(xié)議的不同類別、狀態(tài)、標(biāo)記等信息，可以作為該協(xié)議的一種特征并用于后續(xù)的協(xié)議分析。

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

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

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

針對(duì)上述問題，本文提出了一種用于網(wǎng)絡(luò)協(xié)議分析的高頻相似序列提取算法。該算法針對(duì)協(xié)議序列特點(diǎn)將用于文本處理的Simhash算法做了改進(jìn)，在擁有較高執(zhí)行效率的同時(shí)也能夠達(dá)到較高準(zhǔn)確率。

2 Simhash算法簡介

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

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

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

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

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

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

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

（2）計(jì)算哈希：對(duì)于特征向量集中的每一個(gè)特征，用傳統(tǒng)哈希函數(shù)計(jì)算得到f比特的哈希值H；

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

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

協(xié)議二進(jìn)制序列與文本的主要區(qū)別是二進(jìn)制序列無法進(jìn)行分詞，并且長度可能較短。若要將Simhash算法應(yīng)用于協(xié)議序列，需要根據(jù)文本與二進(jìn)制序列的差異對(duì)算法進(jìn)行修改。

3 高頻相似序列提取算法

3.1 數(shù)據(jù)預(yù)處理

相比協(xié)議載荷部分，協(xié)議頭部包含了協(xié)議數(shù)據(jù)中的主要特征，因此本文研究對(duì)象是協(xié)議報(bào)文序列的頭部。在頭部長度未知的情況下，本研究根據(jù)實(shí)際經(jīng)驗(yàn)截取固定長度的頭部序列作為后續(xù)研究的輸入。

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

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

通過上述方式，完成了對(duì)協(xié)議數(shù)據(jù)報(bào)文序列的預(yù)處理，將每個(gè)序列對(duì)應(yīng)于文本分詞的處理方式進(jìn)行了分割。假設(shè)原始數(shù)據(jù)有m個(gè)報(bào)文序列，預(yù)處理步驟總結(jié)如下：

（1）截取每個(gè)序列的前N個(gè)字節(jié)，得到大小為m×N的原始數(shù)據(jù)矩陣Morigin；

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

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

整個(gè)預(yù)處理流程如圖1所示。

圖1 數(shù)據(jù)預(yù)處理流程圖

3.2 二進(jìn)制序列的Simhash算法

要將Simhash 算法應(yīng)用在二進(jìn)制數(shù)據(jù)處理中，除了文本分詞外，還需解決算法實(shí)現(xiàn)過程中的其他問題。首先在文本去重問題中，Simhash 算法對(duì)于不同的詞可以設(shè)置不同的權(quán)值用以表示詞的重要程度。在二進(jìn)制序列中，各個(gè)字節(jié)之間沒有重要程度之分，即權(quán)值都為1。

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

本文提出的適用于二進(jìn)制協(xié)議報(bào)文序列的改進(jìn)Simhash算法如下：

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

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

該二進(jìn)制序列的Simhash算法與傳統(tǒng)的文本Simhash算法相比，指紋長度更短且指紋間的比較次數(shù)更少，在本文的問題上可以達(dá)到更好的效果。

3.3 評(píng)價(jià)指標(biāo)

Simhash算法的優(yōu)勢(shì)在于處理海量文本數(shù)據(jù)的高效性，并且已經(jīng)在實(shí)際應(yīng)用中得到驗(yàn)證，但該算法在本文的問題上還沒有公認(rèn)的評(píng)價(jià)標(biāo)準(zhǔn)。除了算法的時(shí)間復(fù)雜度外，為了評(píng)價(jià)算法的有效性，本文還提出一種評(píng)價(jià)指標(biāo)來評(píng)估算法的準(zhǔn)確程度。

首先要確定評(píng)價(jià)指標(biāo)的比較基準(zhǔn)。本研究選取已知協(xié)議各字段的實(shí)際取值作為高頻相似序列提取正確與否的參考基準(zhǔn)。這是由于協(xié)議報(bào)文頭部字段中含有的控制信息通常會(huì)重復(fù)出現(xiàn)在協(xié)議通信數(shù)據(jù)中而成為高頻序列。

計(jì)算基準(zhǔn)的高頻序列時(shí)，先將原始的報(bào)文數(shù)據(jù)按真實(shí)的字段劃分切分，對(duì)每一個(gè)字段統(tǒng)計(jì)其取值范圍，若一個(gè)字段的一種取值出現(xiàn)次數(shù)高于指定的閾值，則認(rèn)為是高頻序列，且同一個(gè)字段可能有多個(gè)高頻序列。這樣得到的高頻序列的集合S={s1,s2,…,sq}就可以作為評(píng)價(jià)的基準(zhǔn)。

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

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

4 實(shí)驗(yàn)與分析

4.1 對(duì)比算法

為了更好地對(duì)比算法性能，在實(shí)驗(yàn)中選擇與另外兩種在網(wǎng)絡(luò)協(xié)議分析中較為常見的算法進(jìn)行比較。

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

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

4.2 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文的實(shí)驗(yàn)環(huán)境及其配置如表1 所示。實(shí)驗(yàn)數(shù)據(jù)均為在某校園骨干網(wǎng)和實(shí)驗(yàn)室網(wǎng)絡(luò)環(huán)境下采集的網(wǎng)絡(luò)協(xié)議數(shù)據(jù)。通過wireshark網(wǎng)絡(luò)協(xié)議分析工具提取了常見的四種二進(jìn)制協(xié)議和一種文本協(xié)議，如表2所示。

由于http協(xié)議的報(bào)文數(shù)據(jù)并不一定都有協(xié)議頭，甚至是只包含非文本的載荷，為了在實(shí)驗(yàn)中測試本文算法在二進(jìn)制協(xié)議和文本協(xié)議中的效果，http協(xié)議數(shù)據(jù)選擇了只含有文本協(xié)議頭的數(shù)據(jù)。

表1 實(shí)驗(yàn)環(huán)境及配置

表2 實(shí)驗(yàn)數(shù)據(jù)

4.3 參數(shù)選擇

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

圖2 不同n2 值的覆蓋率

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

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 時(shí)間性能對(duì)比實(shí)驗(yàn)

為驗(yàn)證本文提出的高頻相似序列算法的時(shí)間性能，選取一種二進(jìn)制協(xié)議和一種文本協(xié)議分別統(tǒng)計(jì)在不同的報(bào)文數(shù)量時(shí)算法的運(yùn)行時(shí)間，并與兩種對(duì)比算法進(jìn)行比較。圖3（a）是ip協(xié)議的實(shí)驗(yàn)結(jié)果，協(xié)議數(shù)據(jù)截取長度N=20，圖3（b）是http協(xié)議的結(jié)果，N=200。

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

圖3 運(yùn)行時(shí)間結(jié)果對(duì)比

4.4.2 覆蓋率對(duì)比實(shí)驗(yàn)

為了衡量本文提出算法的有效性，針對(duì)實(shí)驗(yàn)數(shù)據(jù)集中的五種協(xié)議數(shù)據(jù)，分別計(jì)算它們的覆蓋率，同時(shí)與另外兩種對(duì)比實(shí)驗(yàn)的覆蓋率進(jìn)行比較，得到結(jié)果如圖4所示。

圖4 覆蓋率結(jié)果對(duì)比

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

5 結(jié)束語

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