劉治國，蔡文珠，李運琪，潘成勝

（1.大連大學(xué) 信息工程學(xué)院，遼寧 大連 116600；2.大連大學(xué) 通信與網(wǎng)絡(luò)重點實驗室，遼寧 大連 116600；3.南京信息工程大學(xué) 電子與信息工程學(xué)院，南京 211800）

0 概述

隨著網(wǎng)絡(luò)通信規(guī)模迅速擴大和大量新的移動應(yīng)用出現(xiàn)，小眾通信協(xié)議和未公開專有協(xié)議的數(shù)量逐年遞增［1］，無線網(wǎng)絡(luò)［2］在網(wǎng)絡(luò)通信中的使用比重逐年增大［3-4］。對于提高網(wǎng)絡(luò)服務(wù)、檢測流量異常和通信對抗而言，識別協(xié)議是最基本的要求。有研究指出，準確的協(xié)議特征提取是協(xié)議識別的關(guān)鍵［5］，只有在原始數(shù)據(jù)中準確地挖掘出未知協(xié)議的特征，才能以此為依據(jù)對后續(xù)未知協(xié)議數(shù)據(jù)進行有效的對比識別。由于比特流形式的協(xié)議包含的數(shù)據(jù)特征形式較為單一，因此提取關(guān)鍵的比特流序列作為協(xié)議特征是一種有效的方式［6］。通過挖掘特征序列所在幀內(nèi)位置、特征序列幀內(nèi)位置關(guān)系等輔助信息，并將關(guān)鍵序列、序列位置和序列位置關(guān)系作為復(fù)合特征，可提高協(xié)議識別的準確率。

目前，對比特流形式的未知通信協(xié)議進行特征提取已有較多研究。文獻［7］針對零知識環(huán)境下協(xié)議特征提取準確率不高的問題，提出比特流未知協(xié)議的復(fù)合特征提取方法，把協(xié)議中頻繁項和偏移位置2 個屬性作為協(xié)議特征，提高了特征提取的準確率，但該方法獲得的只是單一的字段，提取的特征較為單一。文獻［8］針對AC（Aho-Corasick）算法特征候選集中元素數(shù)量隨時間和頻繁項長度增加呈指數(shù)級增加的問題，提出CFI（Combined Frequency Items）算法。該算法是AC 算法和Apriori 結(jié)合并優(yōu)化的方法，其采用AC 算法生成頻繁字節(jié)項，并由Apriori 算法進行頻繁項匹配得到協(xié)議特征。文獻［9］通過改進基于互信息的特征選擇算法和幀特征選擇算法對比特流未知協(xié)議幀進行特征提取。該方法有效但是特征包含信息較單一，影響了協(xié)議識別準確率。文獻［10-11］先對原始數(shù)據(jù)進行聚類，再對不同的簇進行分析，從中挖掘到地址字段作為協(xié)議特征，但同樣存在特征單一影響協(xié)議識別效率的問題。文獻［12］提出了多模式匹配和關(guān)聯(lián)規(guī)則相結(jié)合的比特流協(xié)議特征提取方法，通過改進AC 算法提取頻繁項，減少了頻繁候選元素和對數(shù)據(jù)的掃描次數(shù)。但該方法需要建立一個深度為切分長度的字典樹，若頻繁項長度過長，則構(gòu)建字典樹就會越復(fù)雜。文獻［13］提出基于特征分析矩陣的特征碼提取方法。該方法無需建立字典樹，而是根據(jù)協(xié)議特征序列前n個比特對應(yīng)的十進制為索引建立特征分析矩陣，數(shù)據(jù)掃描時定位更準確且效率更高，同時也達到了改進AC 算法的效果，但仍未解決特征每增加一個比特就要掃描一次數(shù)據(jù)的操作問題。

為提高未知協(xié)議特征提取的準確率，本文提出一種基于序列統(tǒng)計的特征提取方法FEMSA。統(tǒng)計定長序列出現(xiàn)的位置和頻次，以序列是否固定和交互作為篩選條件來提取頻繁項，從而提高頻繁項提取的效率。同時通過關(guān)聯(lián)規(guī)則連接頻繁序列，去除冗余的序列信息來優(yōu)化頻繁項集，最終得到協(xié)議特征集合。

1 比特流形式協(xié)議

本文主要對比特流形式的未知無線協(xié)議幀集合進行特征提取研究。根據(jù)已知無線協(xié)議（如IEEE 802.11、IEEE 802.3 等）格式分析可知，完整的幀格式由幀頭、控制段、數(shù)據(jù)段、驗證信息等組成，這些部分又可以分為固定域和變化域［14］。固定域包括固定序列和交互序列。固定序列為在同一位置內(nèi)只出現(xiàn)一種序列或者固定出現(xiàn)幾種序列，若2 種序列交替出現(xiàn)，則稱為交互序列。此外，變化域可稱為數(shù)據(jù)域，指各種變化的數(shù)據(jù)序列。協(xié)議數(shù)據(jù)幀示例如圖1所示。

圖1 協(xié)議數(shù)據(jù)幀示例Fig.1 Example of protocol data frame

為在后文中方便描述，做以下定義：

定義1Fi為提取出的頻繁項，Ci為提取出的協(xié)議特征，兩者都由三元組[Si,Li,Pi]表示。其中：Si為統(tǒng)計序列；Li為序列Si在幀內(nèi)出現(xiàn)的位置；Pi為序列Si在位置Li出現(xiàn)頻率，頻率閾值min_sup 可以通過Jaccard 系數(shù)［15］來獲得。

定義2二元組[Lij,Tij]表示某一序列的位置和在當前位置出現(xiàn)的頻次。其中：Lij為序列出現(xiàn)的位置；Tij為序列在位置Lij處出現(xiàn)的頻次。

定義3二元組[Sij,Pij]表示在幀內(nèi)某一位置上出現(xiàn)的序列和序列在當前位置出現(xiàn)頻率。其中：Sij為在某一位置處出現(xiàn)的序列；Pij為Sij序列在當前位置出現(xiàn)的頻率。

2 基于序列統(tǒng)計的特征提取方法

常用的協(xié)議特征提取方法是遍歷統(tǒng)計，即統(tǒng)計可能出現(xiàn)的比特組合各種狀態(tài)出現(xiàn)的頻次，選取出現(xiàn)頻次多的比特組合供后續(xù)研究使用。若未知協(xié)議特征長度不固定，則需要在掃面數(shù)據(jù)幀集時逐次增加比特數(shù)，由此帶來因反復(fù)掃描數(shù)據(jù)幀集而造成分析工作量大的問題。對此，文獻［13］提出了基于特征分析矩陣的協(xié)議特征獲取方法FAMM。該方法無需反復(fù)掃描數(shù)據(jù)幀集，但是需要創(chuàng)建特征分析矩陣存儲每一個備選特征序列的后續(xù)一定長度字符串，且備選特征序列長度增加需掃描特征分析矩陣。當源數(shù)據(jù)量很大時，需要增大空間創(chuàng)建分析矩陣，而當特征長度逐次增加比特時，則需要反復(fù)掃描特征分析矩陣。因此，文獻［13］方法并未從本質(zhì)上改變因長度變化導(dǎo)致的多次掃描數(shù)據(jù)時間消耗的問題。

本文結(jié)合閉包性思想［16］提出一種定長統(tǒng)計序列頻繁度的方法，通過遍歷一次數(shù)據(jù)，建立一個序列長度為lbit 的特征分析矩陣A，記錄統(tǒng)計序列、序列的位置和頻次，同時統(tǒng)計頻次大于min_sup 的序列，得到初始頻繁項集。

對頻繁序列僅通過出現(xiàn)的頻次進行篩選，造成出現(xiàn)錯誤序列的可能性較大，對此，本文增加篩選條件以降低誤識率。如圖1 所示，由于協(xié)議中存在固定和交互序列，因此為提高特征提取準確率和協(xié)議識別效率，挖掘更多的協(xié)議特征信息，本文根據(jù)概率統(tǒng)計［17］和相似性度量［18］思想，在滿足頻繁條件的序列中提取固定和交互序列，得到頻繁項集。由于前序提取結(jié)果中存在序列重疊的問題，因此得到的頻繁項集中存在大量的冗余信息。此外，真實的協(xié)議特征長度是不固定的，采用定長序列統(tǒng)計的方法無法完整表達協(xié)議特征。本文引入關(guān)聯(lián)規(guī)則［19］的思想連接相關(guān)頻繁序列，以得到更長的頻繁序列，并以更長頻繁序列替換原有的頻繁序列更新頻繁項集，將協(xié)議特征集提取分為頻繁項集提取和關(guān)聯(lián)規(guī)則連接頻繁序列兩部分。特征提取過程如圖2 所示。

圖2 特征提取過程Fig.2 Process of feature extraction

2.1 頻繁項集提取

初始頻繁序列提取過程。設(shè)初始序列長度l，將2l種lbit 組合作為初始序列進行統(tǒng)計。掃描數(shù)據(jù)，統(tǒng)計所有2l種長度為l的比特組合出現(xiàn)的位置和頻次以及存儲位置和頻次，構(gòu)成特征分析矩陣A。該矩陣含有2l行，為列可增矩陣，每行元素數(shù)量不定，每個元素表示為[Lij,Tij]。特征分析矩陣A存儲多種序列出現(xiàn)的位置和頻次，矩陣的一行表示同一序列出現(xiàn)的位置和頻次，表示如下：

構(gòu)造特征分析矩陣（Construct the Feature Analysis Matrix，CFAM）算法描述如下：

算法CFAM 算法

輸入n幀比特流形式的數(shù)據(jù)

輸出特征分析矩陣A

步驟1初始化矩陣行數(shù)2l，每行均含0 個元素，初始化匹配位置Li。

步驟2取數(shù)據(jù)幀中Li～Li+l處的比特組合，設(shè)為Si，對應(yīng)的十進制為d，位置是Li。在特征分析矩陣中第d行遍歷元素，查看是否存在位置Li元素。若不存在，將頻次Tdj設(shè)為1，并在這行的尾部添加；若存在，將頻次Tdj加1。

步驟3若一幀數(shù)據(jù)結(jié)束，則初始化位置Li，進行下一幀數(shù)據(jù)遍歷，重復(fù)步驟2，直至遍歷完n幀數(shù)據(jù)，特征分析矩陣建立完成。

遍歷特征分析矩陣，統(tǒng)計每個序列Si頻率值P(Si)：

其中：T(Si)為序列Si出現(xiàn)的頻次；n為數(shù)據(jù)幀數(shù)。當P(Si)>min_sup 時，將序列Si、Si位 置Li和頻率Pi=P(Si)表示為[Si,Li,Pi]，加入到初始頻繁項集。

根據(jù)概率統(tǒng)計和相似度思想提取固定序列和交互序列對初始頻繁項集進行篩選。由于協(xié)議固定序列和交互序列出現(xiàn)的情況與位置和包含內(nèi)容有關(guān)，因此根據(jù)初始頻繁項集構(gòu)建一個索引為位置Li的查詢矩陣B，存儲特征序列和頻率。查詢矩陣B是一個列可增矩陣，由二元組bij組成，存儲在不同位置上出現(xiàn)的序列和序列在當前位置上出現(xiàn)的頻率，矩陣的一行表示在相同位置上出現(xiàn)的所有序列和序列頻率。表示如下：

通過對大量協(xié)議幀集統(tǒng)計得出固定序列和交互序列在協(xié)議中存在的規(guī)律，通過查詢矩陣B對滿足規(guī)律的固定序列和交互序列提取到頻繁項集。

固定序列和交互序列提?。‵ixed and Interactive Sequence Extraction，F(xiàn)ISE）算法描述如下：

算法FISE 算法

輸入查詢矩陣B

輸出頻繁項集F

步驟1按行遍歷查詢矩陣，若在位置Li上出現(xiàn)唯一序列Si且出現(xiàn)的概率P(Si)=1 時，將序列Si視為固定序列，加上位置Li和概率P(Si)構(gòu)成三元組，提取到頻繁項集，否則當概率不為1，跳轉(zhuǎn)步驟4；序列不為1，否則跳轉(zhuǎn)執(zhí)行步驟2。

步驟2若在位置Li有2 個元素，計算2 個元素中序列S1、S2的相似度：

當similar(S1,S2)≥repe_rate 時，將2 個序列加上位置和頻率構(gòu)成三元組作為交互序列提取到頻繁項集；否則跳轉(zhuǎn)執(zhí)行步驟3

步驟3若在位置Li上出現(xiàn)多個初始頻繁序列S1,S2…Sn,且時，則將序列Si視為固定序列，加上位置Li和頻率P(Si)構(gòu)成三元組，提取到頻繁項集；否則跳轉(zhuǎn)步驟4

步驟4若在位置Li上存在多個（>2）元素，且元素中各序列Si的頻率和不為1 時，則Unit(Li)為位置Li上所有序列組成的集合，計算Unit(Li)與其他所有任意一個集合Unit(Lj)的相似度：

當similar(Unit(Li),Unit(Lj))≥repe_rate 時，將2 個位置上所有序列加上位置和頻率構(gòu)成三元組作為交互序列提取到頻繁項集，否則讀取下一行。

步驟5判斷查詢矩陣是否遍歷完成，若完成，則輸出頻繁項集，否則跳轉(zhuǎn)執(zhí)行步驟1。

在位置Li上的序列出現(xiàn)頻率為1，對單協(xié)議而言這樣的序列一定是此協(xié)議的固定序列，在位置Li上出現(xiàn)的序列頻率和為1，說明在當前位置反復(fù)出現(xiàn)幾個序列，這幾個序列亦是此協(xié)議在當前位置上的固定序列。當similar()值超過repe_rate 閾值時，即在Li位置超過repe_rate 的數(shù)據(jù)在Lj位置的集合中也出現(xiàn)了，將位置Li和Lj出現(xiàn)的初始頻繁序列作為交互序列提取出來；若在位置Li上，2 個初始頻繁序列具有repe_rate 的相似度，則作為交互序列提取出來。

上述方法能夠識別提取固定序列和在2 個位置出現(xiàn)或相同位置出現(xiàn)的相似度很高的交互序列。在分析中出現(xiàn)固定序列和交互序列提取沖突時，以交互序列提取為準。但是交互序列的提取存在一定的局限性：提取的數(shù)據(jù)必須是短時間內(nèi)有交互的數(shù)據(jù)，即對于在某些設(shè)備只發(fā)送信息而不接收信息或在另外的設(shè)備只接收信息而不發(fā)送信息的環(huán)境下抓取的數(shù)據(jù)幀，用此方法提取交互序列存在一定困難性。

2.2 關(guān)聯(lián)規(guī)則連接頻繁序列

本文引入關(guān)聯(lián)規(guī)則的思想，通過頻繁序列連接（Frequently Sequence Connected，F(xiàn)SC）算法連接頻繁項集中的序列得到更長頻繁序列，更新頻繁項集。此操作能夠去除冗余信息，得到更為精簡的頻繁序列，最終得到協(xié)議特征集。

頻繁項集F={Fi,Fj,…,Fn},Fi=[Si,Li,Pi]，判斷Fi和Fj中的序列是否在位置上存在Li≤Lj+|Sj|或者Lj≤Li+|Si|的關(guān)系，若2 個序列存在上述位置關(guān)系，記為SiSj或者SjSi，以前者為例計算連接后在幀集中出現(xiàn)的頻率P(SiSj)和兩的置信度。

連接后出現(xiàn)SiSj的頻率如式（4）所示：

其中：T(SiSj)為SiSj出現(xiàn)的頻次；n為數(shù)據(jù)幀數(shù)。置信度如式（5）所示，表示在Si出現(xiàn)的幀數(shù)據(jù)上Sj也出現(xiàn)的概率：

通過FSC 算法對頻繁項集中的頻繁序列根據(jù)關(guān)聯(lián)的思想進行連接，去除頻繁項集中冗余信息，優(yōu)化頻繁項集得到協(xié)議特征集。算法描述如下：

算法FSC 算法

3 仿真驗證與分析

3.1 仿真設(shè)置

對本文算法進行實驗驗證，利用Wireshark 軟件對一小局域網(wǎng)中通信使用的協(xié)議，并將得到的協(xié)議數(shù)據(jù)轉(zhuǎn)換為連續(xù)的比特流形式的數(shù)據(jù)幀，從而生成實驗所用數(shù)據(jù)集。利用已知協(xié)議數(shù)據(jù)而不引進先驗知識模擬未知無線協(xié)議數(shù)據(jù)，驗證本文方法的可行性。仿真數(shù)據(jù)集信息如表1 所示。

表1 仿真數(shù)據(jù)集信息Table 1 Simulation dataset information

3.2 仿真結(jié)果分析

3.2.1 頻繁序列統(tǒng)計方法仿真驗證

采用數(shù)據(jù)集J1 驗證頻繁序列統(tǒng)計時間隨序列長度變化而變化。由圖3 可以看出，頻繁序列的統(tǒng)計時間隨序列長度增加而增加。時間增加的原因包括：改進的AC 方法需要構(gòu)建“字典樹”，且長度越長，構(gòu)建的“字典樹”越大，消耗的時間越多；特征分析矩陣方法雖然不需要構(gòu)建“字典樹”，但是目標序列長度越長，建立的矩陣越大，目標序列增加長度遍歷矩陣的時間會越長。本文方法消耗時間較少，這是因為算法不需要存儲統(tǒng)計序列的后續(xù)一段序列，且只需要遍歷一次分析矩陣，時間只花在創(chuàng)建特征分析矩陣和頻繁項提取上。

圖3 序列統(tǒng)計時間對比Fig.3 Comparison on sequence statistical time

3.2.2 協(xié)議特征提取仿真驗證

本文將F-measure 評價方法［20］運用到特征提取方法的驗證中，分析通過協(xié)議特征集識別協(xié)議消息的結(jié)果，以反映協(xié)議特征提取的效果。本文使用的評價指標為準確率和召回率。在F-measure 評價方法中，以TP表示實際上屬于該類型協(xié)議且被識別為該類型的協(xié)議幀數(shù)，以FP表示實際上不屬于該類型的協(xié)議但被識別為該類型的協(xié)議幀數(shù)。

1）特征提取準確率R定義為通過協(xié)議特征序列識別協(xié)議消息類型的正確率，如式（6）所示：

其中：TP是識別正確的協(xié)議幀數(shù)；FP是誤識別的協(xié)議幀數(shù)。

2）特征提取的召回率r定義為通過協(xié)議特征序列識別協(xié)議類型正確的幀數(shù)與該類型協(xié)議數(shù)據(jù)幀總數(shù)量的比率，衡量的是通過協(xié)議特征序列識別協(xié)議類型的查全率，如式（7）所示：

其中：N是此類消息數(shù)據(jù)幀的數(shù)量。

本文方法和FAMM 方法的特征提取準確率和召回率對比如圖4 和圖5 所示。由圖4 可以看出，本文方法可以對多種未知協(xié)議進行有效的特征提取，且準確率高于90%。但是由于比特流形式的未知協(xié)議數(shù)據(jù)特征單一，假特征出現(xiàn)的可能性較大。從圖5特征提取召回率來看，基本上所有正確特征都被提取出來，存在極小部分個性特征未被提取出。綜上，本文提出的協(xié)議特征提取方法能夠在比特流形式的未知協(xié)議數(shù)據(jù)中成功提取協(xié)議特征集，并且在速度與準確率方面優(yōu)于FAMM 方法。

圖4 J1～J4 數(shù)據(jù)集下的特征提取準確率對比Fig.4 Comparison of feature extraction accuracy under J1～J4 datasets

圖5 特征提取召回率對比Fig.5 Comparison of feature extraction recall rate

4 結(jié)束語

本文根據(jù)比特流形式協(xié)議通信數(shù)據(jù)的特點，提出一種基于序列統(tǒng)計的未知無線協(xié)議特征提取方法。通過統(tǒng)計定長序列出現(xiàn)的頻率和位置并結(jié)合特征分析矩陣提取頻繁序列，以降低頻繁序列統(tǒng)計的時間。根據(jù)固定序列出現(xiàn)概率和交互序列相似性篩選頻繁序列得到初始頻繁項集，提高頻繁序列提取的準確率，同時引入關(guān)聯(lián)規(guī)則的思想連接頻繁序列，去除冗余序列信息得到協(xié)議特征集。仿真結(jié)果表明，本文方法在準確率和效率方面較FAMM 方法取得了較大的性能提升。下一步將在獲取協(xié)議特征的基礎(chǔ)上對大量數(shù)據(jù)幀和協(xié)議特征進行分析，準確提取出協(xié)議所表達的語義，達到識別未知協(xié)議的目的。