楊麗萍

摘要：本文深入研究Apriori關(guān)聯(lián)規(guī)則算法，并將該算法應(yīng)用于網(wǎng)絡(luò)入侵檢測中，通過該算法可以發(fā)現(xiàn)網(wǎng)絡(luò)環(huán)境中對主機端口的訪問規(guī)則，從而利用訪問規(guī)則可以檢測非法的網(wǎng)絡(luò)入侵。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；Apriori算法；網(wǎng)絡(luò)入侵

中圖分類號：TP311.13；TP393.08 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2018）08-0107-02

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

本文重點研究Apriori算法，深入分析算法的實現(xiàn)原理，并利用java語言實現(xiàn)了該算法，利用該算法發(fā)現(xiàn)網(wǎng)絡(luò)中對主機端口的訪問規(guī)則，可以檢測非法的網(wǎng)絡(luò)入侵。

1 Apriori算法分析

1.1 算法思想

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

1.2 算法偽代碼

輸入：事務(wù)數(shù)據(jù)庫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）； //根據(jù)上一步的頻繁集的集合選出候選集

（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的頻繁集進(jìn)行連接

（3.5）if has_infrequent_subset（c，F(xiàn)i-1）

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

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

（3.8）}

（3.9）return Ci；

第（3.5）步has_infrequent_subset（c，F(xiàn)i-1）的算法如下：

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

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

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

//根據(jù)算法性質(zhì)：候選集的子集一定是頻繁的

（3.5.2）if n Fi-1 return TRUE；

else return FALSE；

2 Apriori算法實現(xiàn)

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

//算法主程序

public Map apriori（ArrayList dataList）；

//找到1-頻繁集L1

private Map findFrequentOneSets（ArrayList dataList）；

//根據(jù)上一步的頻繁項集的集合選出候選集

private Map aprioriGen（Map setMap）；

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

private boolean hasInfrequentSubset（String candidateSet， Map setMap）；

//由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則

public Map getRelationRules（Map frequentSetMap）；

3 實驗測試與分析

在網(wǎng)絡(luò)攻擊過程中，通常是首先利用掃描工具探測系統(tǒng)的弱點，而對各個端口的掃描是常用的探測手段?？梢詫priori算法應(yīng)用于網(wǎng)絡(luò)端口掃描，發(fā)現(xiàn)異常的掃描行為，提前預(yù)防網(wǎng)絡(luò)入侵，提高系統(tǒng)的安全性。

通過在一定時間段不斷地獲取網(wǎng)絡(luò)數(shù)據(jù)包，在對網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行預(yù)處理后，得到客戶端對端口的訪問列表，如表1所示。

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

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

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

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

重復(fù)上述步驟，則C4為空，所有頻繁集都被找到，算法到此結(jié)束。此后，可以根據(jù)需要設(shè)定規(guī)則的最小可信度confmin，利用頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則。

設(shè)定最小可信度confmin=0.6，則利用上述算法產(chǎn)生的強關(guān)聯(lián)規(guī)則如下：

21 23 ->80：0.6666666666666666

80 ->21：0.7142857142857143

21 ->80：0.8333333333333334

23 ->80：0.6666666666666666

20 ->80：1.0

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

4 結(jié)語

本文深入分析Apriori算法，并將該算法應(yīng)用于網(wǎng)絡(luò)入侵中，利用該算法挖掘出網(wǎng)絡(luò)中對主機端口的訪問規(guī)則，通過與訪問規(guī)則相比較，可以發(fā)現(xiàn)非法的網(wǎng)絡(luò)入侵，提高系統(tǒng)的安全性。

參考文獻(xiàn)

[1]陳志泊主編.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘[M].清華大學(xué)出版社，2009.

[2]陳國君主編.Java程序設(shè)計基礎(chǔ)（第5版）[M].清華大學(xué)出版社，2015.

[3]王培吉，趙玉琳，呂劍峰.基于Apriori算法的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘研究[J].統(tǒng)計與決策，2011.