基于改進(jìn)Apriori的WiFi入侵檢測(cè)模型研究

劉明峰，侯 路，郭順森，韓 然

(國(guó)網(wǎng)山東省電力公司青島供電公司，山東 青島 266002)

隨著Wi-Fi技術(shù)的普及，基于IEEE802.11協(xié)議的短距離傳輸無(wú)線網(wǎng)絡(luò)成為主流，但其自身安全機(jī)制存在較大的安全隱患[1]，任何未知用戶都可通過無(wú)線接入點(diǎn)訪問局域網(wǎng)，而防火墻策略無(wú)法滿足高安全性的要求。因此，入侵檢測(cè)系統(tǒng)(IDS)成為防火墻的合理補(bǔ)充，實(shí)時(shí)的IDS能最大程度檢測(cè)出網(wǎng)絡(luò)異常行為[2-4]。因此，提出一種實(shí)時(shí)的Wi-Fi網(wǎng)絡(luò)入侵檢測(cè)機(jī)制成為亟待解決的問題[5]。

目前，國(guó)內(nèi)外學(xué)者提出了多種基于數(shù)據(jù)挖掘的入侵檢測(cè)系統(tǒng)，如：文獻(xiàn)[6]提出一種基于關(guān)聯(lián)規(guī)則挖掘Apriori算法的無(wú)線網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)ADAM；文獻(xiàn)[7]將聚類劃分思想融入Apriori中以提高挖掘的效率；為降低檢測(cè)算法的誤報(bào)率，文獻(xiàn)[8]提出一種基于稀疏自編碼的非監(jiān)督式入侵檢測(cè)方法。雖然上述方法取得了良好的檢測(cè)效果，但檢測(cè)過程都是離線的，無(wú)法將網(wǎng)絡(luò)危害風(fēng)險(xiǎn)降至最低。另一方面，基于Apriori算法的檢測(cè)方法只計(jì)算了某個(gè)數(shù)據(jù)包的頻繁模式，而許多入侵行為的數(shù)據(jù)流不存在頻繁模式，若將整個(gè)攻擊流嵌入到單個(gè)數(shù)據(jù)包中，此種方法就很難發(fā)現(xiàn)網(wǎng)絡(luò)異常。文獻(xiàn)[10]通過分析數(shù)據(jù)包包頭結(jié)構(gòu)生成特征數(shù)據(jù)，訓(xùn)練分類器檢測(cè)網(wǎng)絡(luò)流量，但該方法沒有考慮數(shù)據(jù)包載荷問題，因此該系統(tǒng)無(wú)法檢測(cè)出提權(quán)攻擊或越權(quán)訪問攻擊，同時(shí)訓(xùn)練分類器也增加了檢測(cè)過程的時(shí)間開銷。

1 基于關(guān)聯(lián)規(guī)則挖掘的入侵檢測(cè)方法

1.1 關(guān)聯(lián)規(guī)則挖掘原理

文獻(xiàn)[11]首次提出了關(guān)聯(lián)規(guī)則挖掘，定義L={i1,i2,…,in}為項(xiàng)目集合，稱為項(xiàng)集。數(shù)據(jù)庫(kù)(事務(wù)集)D為全體事務(wù)的集合，每個(gè)事務(wù)T是一組集合，有T?L，對(duì)應(yīng)的標(biāo)識(shí)為TID。定義事務(wù)X?L(其中，X為L(zhǎng)某些項(xiàng)目的集合，且有X?L)。關(guān)聯(lián)規(guī)則定義形如：X→Y，其中X?L，Y?L且X∩Y=φ。若D中c%的事務(wù)既包含X又含Y，則規(guī)則X→Y在數(shù)據(jù)庫(kù)D中的置信度為c。若D中s%的事務(wù)包含X∪Y，則規(guī)則X→Y在數(shù)據(jù)庫(kù)D中的支持度為s。表1羅列了TID為1，2，3，4和5的五個(gè)事務(wù)，關(guān)聯(lián)規(guī)則{A}→{C}{A}→{C}的置信度為75%，支持度為60%。

1.2 Apriori算法

Apriori算法在入侵檢測(cè)中表現(xiàn)出了良好的性能[12]。算法的基本思想是使用較短的k項(xiàng)頻繁集集合Lk，推導(dǎo)出長(zhǎng)度為k+1項(xiàng)的頻繁集Lk+1(從k=1開始)，直到找不到更頻繁的項(xiàng)集。使用以下兩個(gè)步驟從頻繁k-1項(xiàng)集的集合Lk-1中找到頻繁k項(xiàng)集的集合Lk，首先，將Lk中的頻繁項(xiàng)集兩兩結(jié)合，生成候選k項(xiàng)集集合Ck，其次，修剪Ck中不滿足Apriori屬性的項(xiàng)集，篩選掉低于預(yù)設(shè)支持度的候選頻繁k項(xiàng)集。要從候選集Ck獲得Lk，必須掃描數(shù)據(jù)庫(kù)以獲得Ck中所有項(xiàng)集的支持度。Apriori算法實(shí)現(xiàn)流程如圖1所示。

表1 數(shù)據(jù)庫(kù)記錄示例

圖1 Apriori算法流程

2 基于關(guān)聯(lián)規(guī)則挖掘的入侵檢測(cè)方法

2.1 相關(guān)定義

為了方便理解所提方法，將網(wǎng)絡(luò)數(shù)據(jù)包看做數(shù)據(jù)庫(kù)D中的記錄，有如下相關(guān)定義和命題。

定義1 若記錄Ri具有的最大頻繁n項(xiàng)集，即包含n個(gè)不同項(xiàng)目，則記錄最大級(jí)別為n。

定義2 最大級(jí)別為n的記錄具有一組頻繁和非頻繁項(xiàng)集：由其所有的1項(xiàng)集至n項(xiàng)集組成。

定義3 頻繁k項(xiàng)集：支持度大于或等于給定最小支持度的k項(xiàng)集。

定義4 非頻繁k項(xiàng)集：支持度小于給定的最小支持度的k項(xiàng)集，且其所有1至k-1級(jí)子集是頻繁項(xiàng)集。

定義5 最大級(jí)別為n的記錄的頻繁項(xiàng)集集合FR：由其所有1項(xiàng)集到n項(xiàng)集的集合組成，其中所有項(xiàng)集的支持度均大于或等于給定最小支持度。

定義6 最大級(jí)別為n的記錄的非頻繁項(xiàng)集集合IFR：由其所有1項(xiàng)集到n項(xiàng)集的集合組成，其中所有項(xiàng)集的支持度均小于給定最小支持度。并且其所有1至k-1級(jí)子集是頻繁項(xiàng)集。

定義7k項(xiàng)集異常得分：如果項(xiàng)集是頻繁項(xiàng)集，則k項(xiàng)集的異常得分為-k；如果項(xiàng)集是非頻繁項(xiàng)集，則k項(xiàng)集的異常得分為+k。

定義8 記錄的異常得分：最大級(jí)別為n的記錄的異常得分是其所有級(jí)別從1到n的頻繁和非頻繁項(xiàng)集異常得分的總和。

命題記錄屬性(正常/異常)：正常記錄中的頻繁項(xiàng)集多于非頻繁項(xiàng)集，記錄異常得分為負(fù)值；異常記錄的非頻繁項(xiàng)集多于頻繁項(xiàng)集，記錄異常得分為0或正值。

2.2 系統(tǒng)架構(gòu)相關(guān)定義

本文提出的Wi-Fi入侵檢測(cè)系統(tǒng)包括三個(gè)模塊：輸入模塊、數(shù)據(jù)預(yù)處理模塊和異常檢測(cè)模塊、結(jié)構(gòu)如圖2所示。為提高檢測(cè)的響應(yīng)時(shí)間，輸入模塊使用Network Chemistry無(wú)線傳感器[13]實(shí)時(shí)捕獲無(wú)線數(shù)據(jù)包。預(yù)處理器模塊使用CommView軟件從傳感器的firebird數(shù)據(jù)庫(kù)中捕獲數(shù)據(jù)并保存為.csv文件。通過該軟件，提取必要的特征并將其存儲(chǔ)為文本文件，還可將記錄存儲(chǔ)到數(shù)據(jù)庫(kù)中，進(jìn)行后續(xù)離線分析或跟蹤。本文所提方法是在線的，可不依賴訓(xùn)練數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后，便可將其發(fā)送給異常檢測(cè)模塊。

2.3 基于非頻繁模式的關(guān)聯(lián)規(guī)則挖掘算法

基于非頻繁模式關(guān)聯(lián)規(guī)則挖掘算法(IF-Apriori)可計(jì)算出每個(gè)級(jí)別對(duì)應(yīng)的頻繁模式和非頻繁模式，并統(tǒng)計(jì)記錄的異常分值。本文對(duì)傳統(tǒng)Apriori的連接過程進(jìn)行改進(jìn)。Li為頻繁i項(xiàng)集，若要連接Li中的項(xiàng)集M和P，需要滿足：M在Li中的排列在P之前；M和P中的前i-1項(xiàng)集相同；M和P均是可連接的，即M和P中的最后一項(xiàng)在Z列表中，其中Z列表為L(zhǎng)i中所有項(xiàng)集中前i-1個(gè)項(xiàng)目的集合，該連接方法避免了與那些不太可能生成頻繁模式的項(xiàng)集的連接，減少了對(duì)非頻繁項(xiàng)集的剪枝操作。IF-Apriori算法偽代碼如算法1所示，其使用的智能連接方法如算法2所示。

圖2 基于IF-Apriori算法的智能連接

算法1 非頻繁模式計(jì)算

Input：候選集C1，最小支持度λ

Output：頻繁項(xiàng)集集合L，每條記錄的異常得分

其它變量：非頻繁項(xiàng)集S

Begin

k=1

步驟1 根據(jù)最小支持度λ，從Ck中計(jì)算頻繁項(xiàng)集集合Lk和非頻繁項(xiàng)集集合Sk

步驟2 While(Lk≠0) do

begin

k=k+1

根據(jù)算法2，從Lk-1計(jì)算候選集Ck

ForCk中每一個(gè)項(xiàng)集 do

計(jì)算所有可能的子集，并進(jìn)行剪枝

IfCk=φ，轉(zhuǎn)到步驟3

根據(jù)最小支持度λ，從Ck中計(jì)算頻繁項(xiàng)集集合Lk和非頻繁項(xiàng)集集合Sk

調(diào)用異常分?jǐn)?shù)計(jì)算函數(shù)，使用Lk和Sk更新記錄的異常得分

步驟3 計(jì)算所有的頻繁模式，L=L1∪L2…∪Lk

算法2 智能連接算法(從Lk-1中生成候選集Ck)

Input：k-1項(xiàng)集集合L

Output：候選k項(xiàng)集集合Ck

Begin

Ck=φ

Z=Lk-1中所有項(xiàng)集中前k-2個(gè)項(xiàng)目的集合

ForM，P∈Lk-1do

Begin

M與P連接生成M∪P

if 滿足如下條件：

(a)M在Lk-1中排列在P前

(b)M和P的前k-2項(xiàng)集相同

(c)M和P均為可連接，二者最后一項(xiàng)目在Z中

then

Ck=Ck∪M∪P

end

End

2.4 異常分?jǐn)?shù)計(jì)算

通過計(jì)算每個(gè)連接數(shù)據(jù)包的異常得分，所提方法避免了頻繁模式生成關(guān)聯(lián)規(guī)則的步驟。異常得分計(jì)算是對(duì)記錄的每個(gè)n項(xiàng)集的非頻繁模式賦予+n的異常分?jǐn)?shù)，對(duì)頻繁模式賦予-n異常分?jǐn)?shù)。計(jì)算過程基于以下前提：異常是偶然事件，若異常嵌入到頻繁或正常的數(shù)據(jù)包(記錄)中。則記錄的得分為該記錄從1到n項(xiàng)集頻繁和非頻繁模式的所有異常得分?jǐn)?shù)總和，其中n是記錄中頻繁模式的最后非空級(jí)別。若記錄的總得分為零或正，則該記錄異常；總得分為負(fù)則該記錄正常。若網(wǎng)絡(luò)記錄產(chǎn)生類似表2中第一列和第二列的數(shù)據(jù)庫(kù)事務(wù)表，其中候選項(xiàng)集為{A,B,C,D,E,F}。在數(shù)據(jù)預(yù)處理階段，A到F可以表示為以下屬性：連接時(shí)間、源和目的MAC、數(shù)據(jù)包大小、接入點(diǎn)MAC(BSSID)、幀類型/子類型、傳輸速率、接入點(diǎn)名稱、源類型(站點(diǎn)或接入點(diǎn))等。

3 基于關(guān)聯(lián)規(guī)則挖掘的入侵檢測(cè)方法

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

本文采用Network Chemistry傳感器捕獲Wi-Fi網(wǎng)絡(luò)內(nèi)的實(shí)時(shí)數(shù)據(jù)。在5分鐘內(nèi)，捕獲了約20500個(gè)數(shù)據(jù)包，含手工生成的攻擊包約600個(gè)，包括被動(dòng)攻擊(用于WEP破解和端口掃描的數(shù)據(jù)包)、主動(dòng)攻擊(SYN Flood和UDP Flood攻擊數(shù)據(jù)包)和中間人攻擊(建立虛假接入點(diǎn)的數(shù)據(jù)包)。以上具體實(shí)現(xiàn)過程可參考文獻(xiàn)[14]和[15]。表3總結(jié)了實(shí)驗(yàn)中攻擊數(shù)據(jù)的攻擊簽名。

表2 數(shù)據(jù)庫(kù)記錄異常得分

表3 攻擊簽名

3.2 異常得分計(jì)算

對(duì)表2中的前兩列進(jìn)行計(jì)算并統(tǒng)計(jì)異常分?jǐn)?shù)并最小支持度為60%。根據(jù)算法2，C1={A:4,B:4,C:4,D:3,E:2,F:2}，L1={A,B,C,D}中每項(xiàng)異常得分為-1，S1={E,F}中每項(xiàng)異常得分+1。對(duì)于TID為1的事務(wù)，ABD的異常得分為：-1(A)-1(B)-1(D)=-3；TID為2的事務(wù)，ACEF的異常得分為：-1(A)-1(C)+1(E)+1(F)=0；以此類推，TID為3，4，5的事務(wù)異常得分為-2，-4，-2。接下來計(jì)算C2，此時(shí)列表Z為空。因此，C2={AB:3,AC:3,AD:2,BC:3,BD:3,CD:2}。L2={AB,AC,BC,BD}，其中每個(gè)項(xiàng)集異常得分-2，而S2={AD,CD}，每個(gè)項(xiàng)集異常得分+2。事務(wù)異常得分更新為：Tid1(ABD)=-3(來自上一步驟的分?jǐn)?shù))-2(AB)+2(AD)-2(BD)=-5。Tid2(ACEF)=0(來自上一步驟的得分)-2(AC)+2(AE)+2(AF)+2(CE)+2(CF)+2(EF)=+8。其余異常得分更新如表2中第4列所示。第三次迭代創(chuàng)建C3列表，首先從L2中創(chuàng)建Z列表，將每個(gè)L2中的項(xiàng)加入Z中得到Z={A,B}。連接L2的項(xiàng)集，若項(xiàng)集的最后一項(xiàng)不在Z中則終止連接。根據(jù)以上規(guī)則，由于AC、AD、BC、BD和CD的最后一個(gè)元素不在Z列表中?？蓪2={AB,AC,AD,BC,BD,CD}中的項(xiàng)減少至{AB}，通過改進(jìn)的關(guān)聯(lián)規(guī)則算法連接{AB}，得到C3={AB}=φ。由于C3和L2均為φ，不計(jì)算此次迭代的異常得分，算法結(jié)束。所有異常得分為負(fù)的記錄可認(rèn)為是正常數(shù)據(jù)，而異常得分為0或正的記錄則會(huì)產(chǎn)生告警。示例中各記錄的最終異常得分如表2中第5列所示。

3.3 結(jié)果分析

與Apriori進(jìn)行比較，以驗(yàn)證所提方法在檢測(cè)率和運(yùn)行時(shí)間方面的優(yōu)勢(shì)。與兩種IDS(ADAM和Snort Wireless)進(jìn)行比較，以驗(yàn)證所提方法在檢測(cè)率和誤報(bào)率方面的優(yōu)勢(shì)。如圖3所示，所提方法IF-Apriori與傳統(tǒng)的Apriori相比，算法執(zhí)行時(shí)間降低了約35%。這是因?yàn)樗崴惴o(wú)需生成與置信度值相關(guān)的關(guān)聯(lián)規(guī)則，同時(shí)所提的智能連接方法降低了連接過程消耗的時(shí)間。實(shí)驗(yàn)表明，在測(cè)試數(shù)據(jù)集相同的情況下，IF-Apriori與Apriori可生成相同的完整頻繁模式和非頻繁模式。

圖3 不同算法運(yùn)行時(shí)間

本文提出的方法與基于Snort的IDS(Snortwireless)[17]和基于Apriori的IDS(ADAM)[6]進(jìn)行了對(duì)比實(shí)驗(yàn)，研究三種IDS的檢測(cè)和誤報(bào)情況。實(shí)驗(yàn)結(jié)果如表4和圖4所示。

表4 檢測(cè)情況

針對(duì)主動(dòng)攻擊、被動(dòng)攻擊以及中間人攻擊這三種特定的攻擊類別，本文提出的IDS與另外兩種IDS相比，能識(shí)別出更多的攻擊包且誤報(bào)率更低。根據(jù)圖5不難看出，針對(duì)不同類型的攻擊本文提出的IDS具有較高的檢測(cè)率，這也說明其具有較強(qiáng)的泛化能力。

圖4 三種IDS檢測(cè)情況和誤報(bào)情況對(duì)比

圖5 三種IDS對(duì)不同攻擊的檢測(cè)率對(duì)比

無(wú)線干擾攻擊在現(xiàn)實(shí)生活中很少出現(xiàn)，所提方法還不具備檢測(cè)該攻擊的能力。此外，若將最小支持度閾值設(shè)置過低，會(huì)產(chǎn)生大量的頻繁項(xiàng)集和較少的非頻繁項(xiàng)集，這會(huì)增加發(fā)現(xiàn)攻擊的難度。經(jīng)過多次實(shí)驗(yàn)，針對(duì)提出的IF-Apriori算法，最小支持度應(yīng)設(shè)置為60%或更高。為了檢驗(yàn)支持度對(duì)入侵檢測(cè)效果的影響，統(tǒng)計(jì)了IF-Apriori算法與Apriori算法在不同支持度檢測(cè)率，如圖6所示。

圖6 不同支持度下的檢測(cè)率

通過與其他方法進(jìn)行比較以驗(yàn)證IF-Apriori分類器的有效性。實(shí)驗(yàn)中，結(jié)果取10次十折交叉驗(yàn)證對(duì)應(yīng)的平均值以確保實(shí)驗(yàn)合理性。此外，本節(jié)所展示的時(shí)間是平均分類時(shí)間。通過與支持向量機(jī)(Support Vector Machine,SVM)算法[16]和隨機(jī)森林(Random Forest，RF)算法[17]進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表5所示。此外，集成了Real AdaBoost算法的SVM和RF分類器[18]的AUC值能得到一定程度的提高，在集成Real AdaBoost算法后，IF-Apriori分類器的AUC未得到改善。

表5 分類器性能對(duì)比

4 結(jié)論

本文提出一種wifi無(wú)線網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)，使用基于非頻繁模式的關(guān)聯(lián)規(guī)則匹配算法來檢測(cè)非頻繁的模式，為每個(gè)數(shù)據(jù)包分配一個(gè)異常分?jǐn)?shù)，通過判斷異常分?jǐn)?shù)的正負(fù)判斷數(shù)據(jù)包是否異常。使用專用的Network Chemistry硬件傳感器來捕獲實(shí)時(shí)流量，改善入侵響應(yīng)時(shí)間。與現(xiàn)有的無(wú)線IDS不同，它不依賴訓(xùn)練數(shù)據(jù)集，實(shí)現(xiàn)了實(shí)時(shí)入侵檢測(cè)。實(shí)驗(yàn)結(jié)果表明，本文方法具有更高的檢測(cè)率和更低的誤報(bào)率，同時(shí)大大降低了系統(tǒng)運(yùn)行時(shí)間。此外，本文還引入了一種智能聯(lián)合方法，改進(jìn)了Apriori中連接和剪枝過程。但所提IDS還不具備檢測(cè)無(wú)線干擾攻擊的功能，這將是下一步研究的工作。