基于序列統計的未知無線協議特征提取方法

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

（1.大連大學 信息工程學院，遼寧 大連 116600；2.大連大學 通信與網絡重點實驗室，遼寧 大連 116600；3.南京信息工程大學 電子與信息工程學院，南京 211800）

0 概述

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

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

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

1 比特流形式協議

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

圖1 協議數據幀示例Fig.1 Example of protocol data frame

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

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

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

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

2 基于序列統計的特征提取方法

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

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

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

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

2.1 頻繁項集提取

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

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

算法CFAM 算法

輸入n幀比特流形式的數據

輸出特征分析矩陣A

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

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

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

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

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

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

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

固定序列和交互序列提取（Fixed and Interactive Sequence Extraction，FISE）算法描述如下：

算法FISE 算法

輸入查詢矩陣B

輸出頻繁項集F

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

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

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

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

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

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

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

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

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

2.2 關聯規則連接頻繁序列

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

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

連接后出現SiSj的頻率如式（4）所示：

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

通過FSC 算法對頻繁項集中的頻繁序列根據關聯的思想進行連接，去除頻繁項集中冗余信息，優化頻繁項集得到協議特征集。算法描述如下：

算法FSC 算法

3 仿真驗證與分析

3.1 仿真設置

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

表1 仿真數據集信息Table 1 Simulation dataset information

3.2 仿真結果分析

3.2.1 頻繁序列統計方法仿真驗證

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

圖3 序列統計時間對比Fig.3 Comparison on sequence statistical time

3.2.2 協議特征提取仿真驗證

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

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

其中：TP是識別正確的協議幀數；FP是誤識別的協議幀數。

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

其中：N是此類消息數據幀的數量。

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

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

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

4 結束語

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