Apriori關聯規則算法在網絡入侵檢測中的研究與應用

楊麗萍

摘要：本文深入研究Apriori關聯規則算法，并將該算法應用于網絡入侵檢測中，通過該算法可以發現網絡環境中對主機端口的訪問規則，從而利用訪問規則可以檢測非法的網絡入侵。

關鍵詞：關聯規則；Apriori算法；網絡入侵

中圖分類號：TP311.13；TP393.08 文獻標識碼：A 文章編號：1007-9416（2018）08-0107-02

關聯規則能夠反映不同事物之間的相互依賴關系，如果一個事物的發生會影響其他事物的發生，那么這些事物之間就可能存在一定的關聯關系，通過挖掘不同事物之間的關聯關系，得到關聯規則，利用關聯規則就可以預測與某些事物相關聯的其他事物的發生。關聯規則挖掘算法可以被應用于市場營銷、銀行業、零售業、保險業、電信業、信息安全管理、網絡入侵檢測及公司經營管理等各個方面。

本文重點研究Apriori算法，深入分析算法的實現原理，并利用java語言實現了該算法，利用該算法發現網絡中對主機端口的訪問規則，可以檢測非法的網絡入侵。

1 Apriori算法分析

1.1 算法思想

Apriori算法多次掃描交易記錄集，產生長度不同的頻繁集。首先產生1-頻繁集F1，在此基礎上經過連接、修剪產生2-頻繁集F2，直到無法產生新的頻繁集則算法終止。在第i次循環中，也就是在產生i-頻繁集Fi的過程中，首先產生i-候選頻繁集的集合Ci，Ci中的每一個項集是對兩個只有一個項不同的屬于Fi-1的頻繁集連接產生。連接后，還要根據Apriori的性質，即頻繁集的子集一定是頻繁的，來對Ci進行修剪，產生對應的Fi。

1.2 算法偽代碼

輸入：事務數據庫T，最小支持度min_sup。

輸出：所有頻繁集Fi。

Ci：i-候選頻繁集。

Fi：i-頻繁集。

（1）F1=find_frequent_1_itemset（T）； //找到1-頻繁集F1

（2）for（i=2；Fi-1≠；i++）{

（3）Ci=apriori_gen（Fi-1，min_sup）； //根據上一步的頻繁集的集合選出候選集

（4）for each t∈T { //判斷候選項集是否是頻繁項集

（5）Ct=subset（Ci，t）；

（6）for each c∈Ct c.count++；

（7）}

（8）Fi={c∈Ci∣c.count> min_sup}；

（9）}

（10）return F=∪Fi；

第（3）步apriori_gen（Fi-1，min_sup）的算法如下：

輸入：i-1頻繁集Fi-1，最小支持度min_sup。

輸出：i-候選頻繁集Ci。

（3.1）for each f1∈Fi-1

（3.2）for each f2∈Fi-1

（3.3）if（（f1[1]=f2[1]）∧…∧（f1[i-2]=f2[i-2]）∧（f1[i-1]

（3.4）c= f1f2；//對兩個只有一個項不同的屬于Fi-1的頻繁集進行連接

（3.5）if has_infrequent_subset（c，Fi-1）

（3.6）delete c；//如果某個候選項中包含非頻繁子集，則將該候選項刪除

（3.7）else Ci=Ci∪{c}；

（3.8）}

（3.9）return Ci；

第（3.5）步has_infrequent_subset（c，Fi-1）的算法如下：

輸入：由Fi-1頻繁集連接產生的Ci的每個子集c

輸出：將包含非Fi-1頻繁集的子集c從Ci中刪除。

（3.5.1）for each（i-1）-subset n of c

//根據算法性質：候選集的子集一定是頻繁的

（3.5.2）if n Fi-1 return TRUE；

else return FALSE；

2 Apriori算法實現

本文采用java語言實現該算法，主要包括以下幾個方法：

//算法主程序

public Map apriori（ArrayList dataList）；

//找到1-頻繁集L1

private Map findFrequentOneSets（ArrayList dataList）；

//根據上一步的頻繁項集的集合選出候選集

private Map aprioriGen（Map setMap）；

//判斷候選集是否是頻繁項集

private boolean hasInfrequentSubset（String candidateSet， Map setMap）；

//由頻繁項集產生關聯規則

public Map getRelationRules（Map frequentSetMap）；

3 實驗測試與分析

在網絡攻擊過程中，通常是首先利用掃描工具探測系統的弱點，而對各個端口的掃描是常用的探測手段。可以將Apriori算法應用于網絡端口掃描，發現異常的掃描行為，提前預防網絡入侵，提高系統的安全性。

通過在一定時間段不斷地獲取網絡數據包，在對網絡數據包進行預處理后，得到客戶端對端口的訪問列表，如表1所示。

對于上表所示的訪問端口記錄集，設定最小支持度閾值supmin=2/10。利用Apriori算法產生頻繁集的過程如下：

由項集I={20，21，23，80，1433，1434}的所有項目直接產生1-候選集C1，計算其支持度。去除支持度小于supmin的項集，形成1-頻繁集F1，如表2所示。

利用F1中的各項目組合連接，來產生2-候選集C2，然后掃描記錄集，以獲得C2中各項集的支持度。去除支持度小于supmin的項集，形成2-頻繁集F2，如表3所示。

利用L2中的各項目組合連接，來產生3-候選集C3，連接時只能將只差最后一個項目不同的項集進行連接。然后掃描記錄集，以獲得C3中各項集的支持度。去除支持度小于supmin的項集，形成3-頻繁集F3，如表4所示。

重復上述步驟，則C4為空，所有頻繁集都被找到，算法到此結束。此后，可以根據需要設定規則的最小可信度confmin，利用頻繁項集產生強關聯規則。

設定最小可信度confmin=0.6，則利用上述算法產生的強關聯規則如下：

21 23 ->80：0.6666666666666666

80 ->21：0.7142857142857143

21 ->80：0.8333333333333334

23 ->80：0.6666666666666666

20 ->80：1.0

通過分析強關聯規則，可以得到結論：如果客戶端訪問主機的20端口或21端口或23端口，卻沒有訪問80端口，就很可能是進行攻擊的掃描；若只訪問80端口，卻沒有訪問21端口，也可能是進行攻擊的掃描；在同時對三個端口的訪問中，除了21，23，80端口，對其余任意三個端口的同時訪問則可能是進行攻擊的掃描。

4 結語

本文深入分析Apriori算法，并將該算法應用于網絡入侵中，利用該算法挖掘出網絡中對主機端口的訪問規則，通過與訪問規則相比較，可以發現非法的網絡入侵，提高系統的安全性。

參考文獻

[1]陳志泊主編.數據倉庫與數據挖掘[M].清華大學出版社，2009.

[2]陳國君主編.Java程序設計基礎（第5版）[M].清華大學出版社，2015.

[3]王培吉，趙玉琳，呂劍峰.基于Apriori算法的關聯規則數據挖掘研究[J].統計與決策，2011.