基于序列統(tǒng)計(jì)的未知無線協(xié)議特征提取方法

劉治國，蔡文珠，李運(yùn)琪，潘成勝

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

0 概述

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

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

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

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

本文主要對比特流形式的未知無線協(xié)議幀集合進(jìn)行特征提取研究。根據(jù)已知無線協(xié)議（如IEEE 802.11、IEEE 802.3 等）格式分析可知，完整的幀格式由幀頭、控制段、數(shù)據(jù)段、驗(yàn)證信息等組成，這些部分又可以分為固定域和變化域［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為提取出的頻繁項(xiàng)，Ci為提取出的協(xié)議特征，兩者都由三元組[Si,Li,Pi]表示。其中：Si為統(tǒng)計(jì)序列；Li為序列Si在幀內(nèi)出現(xiàn)的位置；Pi為序列Si在位置Li出現(xiàn)頻率，頻率閾值min_sup 可以通過Jaccard 系數(shù)［15］來獲得。

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

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

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

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

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

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

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

2.1 頻繁項(xiàng)集提取

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

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

算法CFAM 算法

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

輸出特征分析矩陣A

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

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

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

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

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

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

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

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

算法FISE 算法

輸入查詢矩陣B

輸出頻繁項(xiàng)集F

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

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

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

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

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

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

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

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

上述方法能夠識別提取固定序列和在2 個(gè)位置出現(xiàn)或相同位置出現(xiàn)的相似度很高的交互序列。在分析中出現(xiàn)固定序列和交互序列提取沖突時(shí)，以交互序列提取為準(zhǔn)。但是交互序列的提取存在一定的局限性：提取的數(shù)據(jù)必須是短時(shí)間內(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àng)集中的序列得到更長頻繁序列，更新頻繁項(xiàng)集。此操作能夠去除冗余信息，得到更為精簡的頻繁序列，最終得到協(xié)議特征集。

頻繁項(xiàng)集F={Fi,Fj,…,Fn},Fi=[Si,Li,Pi]，判斷Fi和Fj中的序列是否在位置上存在Li≤Lj+|Sj|或者Lj≤Li+|Si|的關(guān)系，若2 個(gè)序列存在上述位置關(guān)系，記為SiSj或者SjSi，以前者為例計(jì)算連接后在幀集中出現(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 算法對頻繁項(xiàng)集中的頻繁序列根據(jù)關(guān)聯(lián)的思想進(jìn)行連接，去除頻繁項(xiàng)集中冗余信息，優(yōu)化頻繁項(xiàng)集得到協(xié)議特征集。算法描述如下：

算法FSC 算法

3 仿真驗(yàn)證與分析

3.1 仿真設(shè)置

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

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

3.2 仿真結(jié)果分析

3.2.1 頻繁序列統(tǒng)計(jì)方法仿真驗(yàn)證

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

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

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

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

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

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