基于改進Apriori算法的網絡入侵數據挖掘仿真

王 霞，曹麗娜，楊鳳麗

(石家莊鐵道大學四方學院，河北 石家莊 051132)

1 引言

網絡是信息交流平臺，在給人們帶來方便時也伴隨著一些潛在的危機，因網絡中每天都會產生大量數據信息，人們非常擔憂網絡中數據信息的安全問題，據相關資料表明，網絡入侵事件頻繁出現，在2000年著名國際購物網站慘遭黑客攻擊，導致經濟損失高達12億美元。網絡入侵數據一般以木馬病毒、DDoS攻擊等形式出現，通過網絡植入客戶端，竊取機密數據[1]。因此，網絡安全問題逐步得到人們的重點關注，一些網絡安全產品應運而生，比如網絡安全軟件、防火墻等。雖然這些產品在網絡安全方面起到一定保護效果，但是仍然存在防攻擊能力差的劣勢，面對高級手段的不法黑客的攻擊也無法實現精準防御，導致網絡安全性下降。網絡性能因網絡中存在異常數據導致其性能下降，網絡入侵數據一方面因不法分子惡意攻擊代碼造成，另一方面因個人用戶操作不當，下載一些帶有病毒的軟件或插件導致網絡入侵數據產生[2]。

關于網絡入侵數據挖掘課題是當前最熱門課題之一，入侵檢測技術可檢測網絡入侵數據類型，并依據類型屬性進行相應的安全防御措施或殺毒[3]。該技術中誤用檢測是通過構建入侵規則庫進行網絡入侵數據判斷，但該檢測技術存在局限性，對于不在入侵規則庫內的新入侵數據無法檢測；而異常檢測將網絡采集數據作為正常行為庫，對比網絡入侵行為與正常行為庫的差異實現檢測。通過將入侵檢測技術的優勢融入侵檢測系統內，但僅僅依靠系統檢測是不行的，需要加入先進算法提高檢測效率，在網絡安全中，網絡入侵數據挖掘最為復雜，針對這一難題，我國相關學者在網絡安全課題中加強對網絡入侵數據挖掘方法研究，但以往研究的網絡入侵數據挖掘方法存在一定缺陷，如蔡柳萍等人研究稀疏表示和特征加權的挖掘方法[4]，該方法通過進行數據處理并利用數據加權實現數據挖掘，但是因該方法計算過程過于復雜，導致數據挖掘不佳，無法挖掘出網絡中隱蔽的異常數據的情況時有發生；楊衛等人研究云計算平臺挖掘方法[5]，該方法側重于軟件設計，導致檢測成本上升。

數據挖掘技術可通過發掘數據內隱含規律，找尋有價值數據，Apriori算法作為一種數據挖掘技術，其適應性較廣，但該算法運行時負載較大，冗余性高，可通過可拓理論改進該算法，改進Apriori算法計算效率較高，因此有效利用改進Apriori算法，研究基于改進Apriori算法的網絡入侵數據挖掘仿真方法，提高網絡入侵數據挖掘效率和網絡安全管理水平。

2 基于改進Apriori算法的網絡入侵數據挖掘仿真

2.1 Apriori算法

在Apriori算法內，數據集k+1項集需要通過k項集進行搜索。設置L1、L2為頻繁項集，直至任一r值滿足Lr=?時結束。在第k次循環內，生成候選k項集合用Ck描述，通過對兩個Lk-1頻集經過連接k-2生成Ck內各項集。候選集通過Ck生成，其子集為Lk。Ck各元素在數據庫進行搜索，但該算法負載較大。

Apriori算法基本思路：

Step 1：需找全部項集，項集發生的頻繁性與預定義最小支持度相同。

Step 2：強關聯規則通過項集生成，該規則一定符合最小可信度與支持度。

2.2 改進Apriori算法

通過可拓理論改進Apfiofi算法，將事物名稱用N表示，其特征c的量值用v描述，物元為有序三元組用R=(N，c，v)表示。其中N，c，v為物元三要素，物元受三要素影響較大[6]。

在網絡入侵數據挖掘中，關聯規則的定義為：對于1個征集X和一個概念描述Y，指定支持度閾值s0和置信度閾值c0，若s(XyY)Es0并且c(XyY)Ec0，則規則XyY成立。其內，s(XyY)=card(XHY)/card(N)，c(XyY)=card(XHY)/card(X)。數據記錄對象集中事務數量用運算符card(#)求解。支持度計數用card(XHY)描述。

當s(XyY)Es0時，大征集是征集X。征集X內某一征集Xk，為降低冗余挖掘可拓關聯規則XkyY需滿足置信度大于置信度闞值條件，對Xk進行刪除。

改進Apriori算法的思路為：

1)大征集交運算

將2個大征集分別用X1，X2描述，通過交互運算得出征集X；

2)征集刪除運算

對k元征集集合內各征集Xk的全部k-1元子句進行查看操作，當Xk-1不是大征集時進行刪除。

改進Apriori算法流程如下：

關聯規則集用R描述，作為數據輸出；最小支持度閾值用s0描述，數據庫用D描述，最小置信度閾值用c0作為數據輸入。

Step 1：為求出元素集合A，通過掃描總體數據庫，統計各條記錄內的各元素得出[7-9]。

Step 2：為生成一元候選集H1，通過A內各元素集合生成，將k表示為1個元計數單位設置為k=1。

Step 3：Y表示概念，求解Hk內各征集XkyY的置信度c與支持度s，若Xk的支持度用sEs0描述，進行判斷：

1)當置信度閾值c0既定時，若Xk的置信度用cEc0描述，得出輸出規則用XkyY描述。

2)若Xk的置信度用cFc0描述，在大征集Lk內存進Xk。

Step 4：當Lk內元素數量小于2個時，則結束；反之，當Lk內的各Xk，依據字典順序對X內全部元素進行排列。

Step 5：通過比較Lk內征集Xki，xkj的元素，為生成k+l候選集，需要對Lk內的全部征集進行組合操作；若第k個元素不一樣，k-1個元素一樣時，則Hk+1存全新k+1元征集。

Step 6：令k=k+1，返回到Step 3。

2.3 基于改進Apriori算法的網絡入侵數據挖掘

2.3.1 網絡入侵行為模式

設定一個閾值并通過正常行為模式和在含有網絡入侵的數據集中挖掘出的模式對比后得出閾值距離，進行發生網絡入侵行為模式判定[10]，采用MEOM(Heterogeneous Euclidean—overlap Metric)函數求解兩種模式距離，具體如公式(1)～公式(2)所示

(1)

(2)

向量X和向量Y的距離，如公式(3)所示

(3)

式中：屬性數量用n描述，向量屬性用b描述。用HOEM(X，Y)描述向量間距離，其值越小表示2個向量大致一樣。

因各屬性的重要性存在差異[11]，需要對各屬性設置權值，重要性和權值成正比。在公式(2)內，若2個向量一致，其值是零，無法表示權值，因此需要對公式(2)進行修改，修改后如公式(4)～公式(5)所示

(4)

(5)

向量X和向量Y的距離，如公式(6)所示

(6)

式中：各屬性的權值用?描述，用HOEM(X，Y)描述向量間距離，其值越小表示2個向量間距離越大。

若異常模式內的一個向量用Y表示，閾值用δ描述，正常模式內的一個向量用X表示，通過公式(4)～公式(6)求解HOEM(X，Y)，當該值小于δ時，判定Y模式為入侵模式，其內存在網絡入侵的數據[12]。

2.3.2 挖掘結果的分類處理

在完成網絡入侵模式識別后，通過改進的分類規則生成(Ripper)算法對不同的網絡入侵的數據類型進行分類，并賦予不同標簽。改進的Ripper分類算法，流程如圖1所示。

圖1 改進的Ripper分類算法流程

由圖1可知，該分類算法的基本流程情況，其中在判斷POS主動數據項為空時，將訓練數據分成縮減集與增長集；在規則擴展中，在置空規則后，添加合法條件，重復此次操作直至規則內包含增長數據集內全部數據項；在規則縮減中，為了實現函數值V最大，需要刪除最后條件，重復此次操作直至V最大，通過規則縮減可提高規則適應性和精度。

3 實驗分析

為驗證本文方法的有效性，在MATLAB＿7.0軟件測試平臺上進行仿真實驗測試，選取某網絡中數據作為實驗數據。

從實驗數據中選取4種網絡入侵數據的特征樣本，對比應用Apriori算法和改進Apriori算法對網絡入侵數據挖掘的效果，算法運行時間設置為30分鐘，可行性測試結果如圖2所示。

圖2 可行性測試結果

通過分析圖2可知，采用改進Apriori算法進行網絡入侵數據挖掘的效果較好，比傳統Apriori算法所挖掘4種網絡入侵數據的特征樣本數量分別約高出1700萬條、1800萬條、2000萬條、2500萬條，因此表明應用改進Apriori算法的本文方法的可行性較高。

統計采用Apriori算法和改進Apriori算法在不同支持度的條件下以及不同數據規模條件下進行挖掘的執行效率，如圖3所示。

圖3 執行效率對比

分析圖3可知，應用兩種算法進行數據挖掘的穩定性均較優，在不同數據量耗時方面，本文方法應用的改進Apriori算法明顯優于Apriori算法，平均耗時比Apriori算法的平均耗時節省19ms左右，在最小支持度不同條件下，應用兩種算法進行挖掘的耗時隨最小支持度的升高而降低，但本文方法應用改進Apriori算法進行數據挖掘的耗時較少，由此說明本文方法的入侵數據挖掘執行效率較高。

設定c0表示最小置信度閾值，s0表示最小支持度閾值。對實驗數據進行7次數據挖掘，在第1次數據挖掘時，設置c0=0.15、s0=0.25；第2次數據挖掘時，設置c0=0.15和s0=0.50；第3次數據挖掘時，設置c0=0.25和s0=0.25；第4次數據挖掘時，設置c0=0.45和s0=0.50；第5次數據挖掘時，c0=0.55和s0=0.70；第6次數據挖掘時，設置c0=0.65和s0=0.70；第7次數據挖掘時，設置最c0=0.85和s0=0.70；得出本文方法挖掘入侵數據的關聯規則數量和運行時間結果，如圖4所示。

圖4 不同置信度與支持度下關聯規則數量圖

分析圖4可知，當最小置信度閾值c0設置在0.45～0.85，s0為0.50～0.70時，數據挖掘的運行時間短、關聯規則數量波動較??；c0為0.15～0.25，s0為0.25～0.50時，數據挖掘的運行時間長、關聯規則數量波動較大。由此可知，運行時間和關聯規則數量受c0、s0影響較大。

實驗數據集內網絡入侵數據607條，網絡正常數據2337條。統計不同算法下網絡入侵數據誤檢率和漏檢率，仿真試驗結果見表1。

表1 網絡入侵數據誤檢率和漏檢率

由表1可知，采用改進Apriori算法下入侵檢測的漏檢率與誤檢率分別比傳統Apriori算法下的入侵檢測的漏檢率與誤檢率降低6.24%、6.14%，說明應用改進Apriori算法的本文方法性能更優，可有效提高網絡數據安全性。

4 結論

為提高網絡入侵數據挖掘效率，本文提出基于改進Apriori算法的網絡入侵數據挖掘方法。構建改進Apriori算法的網絡入侵數據挖掘模型，實現網絡入侵數據挖掘。仿真實驗結果表明，采用本文方法可行性強，可解決網絡入侵檢測中的大量數據挖掘問題，使挖掘效率提高。因本人時間與精力有限，研究仍處于起步階段，仍有許多不足，需要在以后社會實踐中逐步完善。本人以后研究方向如下：

1)將本文方法應用在網絡流量數據異常檢測或系統開發內，拓展本文方法應用范圍，需要我們繼續研究進一步提高算法的挖掘能力。

2)為了提高本文方法在網絡數據檢測中的性能，可以引入更多先進技術和方法，并與之結合提高數據檢測精度和適應性。