徐勝超，宋 娟，潘 歡

(1.廣東財經(jīng)大學(xué)華商學(xué)院 數(shù)據(jù)科學(xué)學(xué)院，廣東 廣州 511300；2.寧夏大學(xué) 寧夏沙漠信息智能感知重點實驗室，寧夏 銀川 750021)

0 引 言

隨著計算機網(wǎng)絡(luò)的發(fā)展及新型網(wǎng)絡(luò)協(xié)議的出現(xiàn)，近年來各類網(wǎng)絡(luò)入侵攻擊行為持續(xù)增加，普通的數(shù)據(jù)挖掘算法已經(jīng)不能滿足網(wǎng)絡(luò)入侵檢測的需求。作為數(shù)據(jù)挖掘的重要分支，關(guān)聯(lián)規(guī)則挖掘已經(jīng)成為了研究熱點[1-4]。關(guān)聯(lián)規(guī)則算法中，很多都能夠產(chǎn)生頻繁項集，在這些關(guān)聯(lián)挖掘產(chǎn)生頻繁項集的過程中，連接數(shù)據(jù)庫和產(chǎn)生侯選項集的數(shù)目非常大，這樣將大大增加了關(guān)聯(lián)規(guī)則算法的時間代價,降低了效率。例如經(jīng)典的Apriori算法增強了豐富的顏色到數(shù)據(jù)的分析與處理，其目的是為了發(fā)現(xiàn)不同的數(shù)據(jù)項在歷史交易數(shù)據(jù)庫中的關(guān)系，核心功能是通過重復(fù)掃描數(shù)據(jù)項，獲得頻繁項集和研究項集之間的關(guān)系。目前，Apriori算法和并行化的Apriori算法都得到了很大的改善[5-7]。

關(guān)聯(lián)規(guī)則模型中的Apriori算法主要應(yīng)用在大量的歷史交易數(shù)據(jù)中，用來發(fā)現(xiàn)頻繁模式和數(shù)據(jù)項之間的關(guān)聯(lián)性。盡管如此,考慮到Apriori算法的固有的特點，當數(shù)據(jù)容量十分大的時候，它的缺點和不足體現(xiàn)得更加明顯，此時使用Apriori算法來分析和處理數(shù)據(jù)將變得非常消耗時間與內(nèi)存空間，效率低下[8]。所以為了快速處理大容量數(shù)據(jù)，文獻[9]提出了基于Apriori算法的重要狀態(tài)確定方法來完成網(wǎng)絡(luò)入侵檢測。文獻[10]提出了改進的Apriori算法來完成頻繁模式樹的建立,將其應(yīng)用到數(shù)據(jù)挖掘領(lǐng)域。

針對早期的低效率的傳統(tǒng)Apriori算法而言,要處理網(wǎng)絡(luò)入侵檢測的海量大數(shù)據(jù)，目前比較常見的是Hadoop分布式計算框架。同時改進早期經(jīng)典的Apriori算法，建立新的框架用來處理頻繁項集的挖掘的并行Apriori算法，用來加快計算速度，節(jié)省內(nèi)存空間。該文提出的基于MapReduce云計算的并行關(guān)聯(lián)挖掘的網(wǎng)絡(luò)入侵檢測方法Cloud-Apriori就是基于這個思路。Cloud-Apriori的實驗通過構(gòu)造Hadoop集群來完成。實驗結(jié)果表明改進的并行Apriori算法具有很高的檢測精度和更少的運行時間,提高了網(wǎng)絡(luò)入侵檢測效率。

1 Hadoop框架分析

1.1 分布式框架

文中關(guān)聯(lián)挖掘的網(wǎng)絡(luò)入侵檢測采用了Hadoop云計算平臺，這樣可以并行處理頻繁項集，以進一步提高大數(shù)據(jù)處理的速度與效率[11]。

Hadoop是一種開源并行大數(shù)據(jù)處理的總體支撐平臺，一般基于MapReduce的并行算法中采用了6個步驟來表示任務(wù)流Job stream的流程情況。每個任務(wù)流都表示為一系列的Map任務(wù)或者Reduce任務(wù)，并行關(guān)聯(lián)挖掘的Apriori算法作為一個應(yīng)用程序，其包括的所有子任務(wù)組成了一個有向無環(huán)圖，如圖1所示[12]。在部署Hadoop的時候，主控節(jié)點部署為JobTracker，工作機一般部署為TaskTracker。因特網(wǎng)上有很多關(guān)于Hadoop的文獻，由于篇幅原因這里不再過多累述，這6個具體步驟如下：

圖1 基于MapReduce的并行關(guān)聯(lián)挖掘任務(wù)流

(1)對輸入的大數(shù)據(jù)的樣本數(shù)據(jù)集文件進行設(shè)置與分片；

(2)主節(jié)點(JobTracker)調(diào)度從屬節(jié)點(TaskTracker)執(zhí)行Map子任務(wù)；

(3)從屬節(jié)點讀取輸入源片段；

(4)從屬節(jié)點執(zhí)行Map子任務(wù)，并將臨時結(jié)果文件保存在本地；

(5)主節(jié)點調(diào)度從節(jié)點執(zhí)行Reduce子任務(wù)，Reduce階段的從屬節(jié)點讀取Map子任務(wù)的輸出文件；

(6)執(zhí)行Reduce子任務(wù)，將最后的結(jié)果保存到HDFS分布式文件系統(tǒng)當中。

有了這6個步驟，并行關(guān)聯(lián)挖掘的Apriori算法的編程人員就可以擺脫本身分布式計算的編程細節(jié)，可以使用高級語言在很短的時間內(nèi)，完成分布式計算的編程。

1.2 MapReduce模型分析

Map操作和Reduce操作是MapReduce并行編程模型的關(guān)鍵操作，所有的任務(wù)流必須經(jīng)過這2個階段。MapReduce中的任務(wù)流可以通過下面的公式表示:

DAG=(W,E,DAGinfo)

(1)

W={Wname,{Map},{Reduce},Param,Input,

Output}

(2)

其中，W表示被并行處理后的任務(wù)的集合，Wname表示子任務(wù)的名稱；Map和Reduce分別表示映射和規(guī)約操作；Param表示任務(wù)執(zhí)行所需要的參數(shù)信息；Input和Output分別表示輸入任務(wù)和輸出任務(wù)相關(guān)的數(shù)據(jù)信息；E表示在DAG圖中的兩個任務(wù)之間的邊；DAGinfo表示DAG圖中的特殊鑒別信息。

公式(2)中的Map操作可以更詳細地表達如下:

Map=(Mname,InK,InVal,OutK,OutVal,

Propereties)

(3)

其中，Mname表示Map操作的名稱；InK和InVal分別表示在輸入Map操作過程中Key-value關(guān)鍵字與關(guān)鍵字值之間的映射對；OutK和OutVal分別表示在輸出Map操作過程中Key-value關(guān)鍵字與關(guān)鍵字值之間的映射對；Properties表示在Map操作過程中的屬性參數(shù)。公式(2)中的Reduce操作可以更詳細地表達如下:

Reduce=(Rname,InK,InVal,OutK,OutVal,

Propereties)

(4)

其中，Rname表示Reduce操作的名稱,后面的參數(shù)InK和InVal等的含義都與Map操作中是一致的。E表示在DAG圖中的兩個任務(wù)之間的邊。E的詳細描述如下:

E=(Path,StartTK,EndTK)

(5)

其中，Path顯示了數(shù)據(jù)流的傳輸路徑，StartTK表示當前的任務(wù)，EndTK表示任務(wù)的子任務(wù)。

2 Cloud-Apriori并行關(guān)聯(lián)規(guī)則挖掘模型

2.1 基本?？?/h3>

Cloud-Apriori的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘如圖2所示。

圖2 基于Cloud-Apriori的并行關(guān)聯(lián)挖掘模型

主要包括:

(1)動態(tài)交互層:用來與客戶端通過接口進行交互;

(2)業(yè)務(wù)邏輯層:用來完成針對交互層和數(shù)據(jù)挖掘平臺層的所有業(yè)務(wù)處理操作的命令和控制；

(3)數(shù)據(jù)挖掘平臺層:是該文基于Hadoop的關(guān)聯(lián)規(guī)則算法的核心層,具體完成大數(shù)據(jù)的處理,包括并行數(shù)據(jù)挖掘算法,工作流模塊,數(shù)據(jù)裝載模塊和存儲模塊;

(4)分布式計算的平臺層:它是利用Hadoop框架來獲得HDFS分布式文件的存儲和MapReduce的工作的執(zhí)行。

2.2 關(guān)聯(lián)規(guī)則Apriori算法原理

關(guān)聯(lián)規(guī)則表示兩個實體在某種規(guī)則下的一些隱藏信息，關(guān)聯(lián)挖掘的目的是發(fā)現(xiàn)這些隱藏的關(guān)系[13]。關(guān)聯(lián)規(guī)則可以通過數(shù)據(jù)模型來描述，例如X表示關(guān)聯(lián)規(guī)則的前提假設(shè),Y表示后續(xù)的關(guān)聯(lián)規(guī)則。另外，關(guān)聯(lián)規(guī)則算法有一個關(guān)于支持度(support)和置信度(confidence)的定義，如公式(6)，這里A和B分別表示了不同的事件。

(6)

關(guān)于支持度和置信度的通信關(guān)系可以通過公式(7)來計算:

(7)

關(guān)聯(lián)挖掘的Apriori算法的基本思想是使用頻繁項集的優(yōu)先知識信息來完成迭代計算,該過程是層對層的搜索進行的[14]。

為了實現(xiàn)在Apriori算法下的關(guān)聯(lián)分析,一般的關(guān)聯(lián)挖掘的步驟如下:

步驟1:設(shè)置最小的需求支持度min_Sup和最小的置信度min_Conf;

步驟2:順序地連接和掃描數(shù)據(jù)集,確定每個數(shù)據(jù)項的支持數(shù)量，選擇出在步驟1中的最小支持度min_Sup的頻繁項集1;

步驟3:隨機地結(jié)合2個頻繁項集1來生成侯選的頻繁項集2,然后順序地連接數(shù)據(jù)集和完成對侯選的頻繁項集2的支持度的計算,最后根據(jù)步驟2過濾頻繁項集2;

步驟4:重復(fù)步驟3直到產(chǎn)生了空的最高序號的頻繁項集;

步驟5:輸出關(guān)聯(lián)挖掘的結(jié)果,算法結(jié)束。

2.3 Cloud-Apriori挖掘算法的設(shè)計

前面提到MapReduce編程模型采用了主-從(Master/Slave)模式,即主控節(jié)點上可以部署Job Tracker,在從節(jié)點上可以部署Task Tracker。在DAG的有向無環(huán)圖中，為了更好地分配正確的任務(wù)流到所有的處理節(jié)點，該文采用并行MapReduce的任務(wù)流處理技術(shù)，具體的實現(xiàn)機制如圖3所示。

圖3 MapReduce的并行關(guān)聯(lián)挖掘工作機制

2.4 Cloud-Apriori挖掘算法的實現(xiàn)

(1)產(chǎn)生頻繁項集。

文中算法采用了自頂向下的方式，從概念的第一層開始到最后一層，利用MapReduce產(chǎn)生大量的頻繁項集,包括在不同的概念層之間的層次交互。對于每一層來說，MapReduce操作產(chǎn)生一個頻繁集的數(shù)據(jù)項,包括特殊層的交互，這種操作將一直迭代,直到在本層中不能發(fā)現(xiàn)更多的頻繁項集為止。

在數(shù)據(jù)入口的處理中，主要使用了三個類:輸入格式Input format、輸入分片Input split和記錄閱讀器Record Reader。在這三個類中，輸入格式又被輸入數(shù)據(jù)處理一次，每個輸入的分片在后面的類中處理。記錄閱讀器的功能是對數(shù)據(jù)塊的輸入分片進行分析,并將其信息對接到多個key-value關(guān)鍵字和關(guān)鍵值的映射對中，并發(fā)送到Map函數(shù)。與任務(wù)相關(guān)的關(guān)鍵字和關(guān)鍵值的映射如表1所示。

表1 關(guān)鍵詞和關(guān)鍵值的映射表描述

(2)Map和Reduce的處理。

當使用Hadoop來完成大數(shù)據(jù)處理的時候，在文件中的每行都被作為交易記錄對待，在行中的每個入口都被一個空格符號分離開。在客戶端提交了文件到HDFS后，文件中的數(shù)據(jù)塊的默認尺寸是64 MB,每個迭代的輪次都執(zhí)行一個MapReduce任務(wù)。每個Map節(jié)點同時處理多個數(shù)據(jù)塊,處理完后輸出到候選集及其對應(yīng)的支持度。

Reduce操作持續(xù)地處理Map操作階段的結(jié)果,所有的具有相同的鍵值的關(guān)鍵字-關(guān)鍵值對都將完成規(guī)約操作,最后完整的頻繁項的支持結(jié)果將完成。這些并行的規(guī)約過程都采用MapReduce結(jié)構(gòu)設(shè)計，包括Map()函數(shù)和Reduce()函數(shù),它們都運行在Hapdoop平臺上，加快了關(guān)聯(lián)規(guī)則挖掘的計算速度。下面是Map()函數(shù)和Reduce()函數(shù)的偽代碼,這些代碼經(jīng)過少量的修改即可在Java語言環(huán)境下執(zhí)行。

下面的Map_Class是Map階段的類描述代碼：

Map_Class{

1. map(key,value){

2. Sort=0;

3. Dis=Max_Value;

4.for(int i=1;i

5.Records Dis=dis(i,pointer);

6.if(Records Dis

7. Sort=i;

8.min Dis=Records Dis;

9.}

10. }

11.produce<"Sort" , value>;

12. }

13. }

下面的Reduce_Class是Reduce階段的類描述代碼:

Reduce_Class{

1.reduce(key,value){

2. D1=0;

3. Sort=k;

4. Temps=new int[D1];

5. for(int i=0;i

6 . for(int D1=0; D1

7. D1++){

8. Temps[i]=value[D1][i];

9. }

10. }

11. for(int j=0;j

12.pointer+=Temps[j];

13. }

14.produce;

15. }

16. }

(3)計算復(fù)雜度分析。

如果i是原始數(shù)據(jù)集D的交易數(shù),j表示每個交易記錄的平均長度，采用傳統(tǒng)的Apriori關(guān)聯(lián)挖掘算法,在L1層中計算時間復(fù)雜度為T1=O(i*j),整個算法的時間復(fù)雜度為:

O(|Ck|*|Lk-1|)+O(i*|Ck|)]

(8)

如果采用基于MapReduce的并行關(guān)聯(lián)挖掘的Apriori算法,Hadoop集群有a個節(jié)點，每個節(jié)點都操作1個數(shù)據(jù)塊,則獲取頻繁項集的整個時間復(fù)雜度可以表示為:

O(|Ck|*|Lk-1|)+O(i*|Ck|)]}/a

(9)

從公式(8)和公式(9)比較可以看出，從理論上講，基于MapReduce的并行Apriori關(guān)聯(lián)挖掘算法可以很好地降低執(zhí)行時間。集群的物理節(jié)點個數(shù)越多，則執(zhí)行時間越短，效率越高。

3 系統(tǒng)測試與性能分析

3.1 測試環(huán)境

測試平臺的具體參數(shù)包括:8個計算節(jié)點(Intel i7的3.2 GHz主頻處理器，8 GB內(nèi)存。節(jié)點之間的通訊為Intel 82574L芯片組主板,雙網(wǎng)卡,帶寬為1 GB/S。

Hadoop分布式平臺的版本為2.2,JDK的版本為1.8.0。其中一個節(jié)點上部署JobTracker,另外7個節(jié)點上部署TaskTracker。每個TaskTracker上有1個reduce工作slot和2個map工作slot,每個物理主機的IP地址配置如表2所示。

表2 Hadoop云平臺的物理主機的配置

所有物理主機上都安裝Linux操作系統(tǒng)，Hadoop的主目錄安裝在usr/local/hadoop，同時在profile文件中修改和配置好環(huán)境變量:

# /etc/profile

export JAVA_HOME=/usr/local/jdk

export HADOOP_HOME=/usr/local/hadoop

export PATH=.:$HADOOP_HOME/bin:$JAVA_HOME/bin:$PATH

3.2 實驗數(shù)據(jù)

為了比較普通的關(guān)聯(lián)規(guī)則挖掘Apriori算法和基于MapReduce的并行關(guān)聯(lián)挖掘Apriori算法的性能，文中采用了Kddcup數(shù)據(jù)集。Kddcup數(shù)據(jù)集是在網(wǎng)絡(luò)入侵檢測中采用的最常見的標準Benchmark數(shù)據(jù)集[15],它也是一個在國內(nèi)外最有代表性和影響性的網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集。該數(shù)據(jù)集中的記錄主要被劃分為兩個部分:用于訓(xùn)練的數(shù)據(jù)集和用于測試的數(shù)據(jù)集。訓(xùn)練數(shù)據(jù)集具有一個具體的鑒定符,測試數(shù)據(jù)集沒有鑒定符。測試數(shù)據(jù)集也包括不在訓(xùn)練數(shù)據(jù)集中的一些攻擊類型,這樣就使得系統(tǒng)的網(wǎng)絡(luò)入侵檢測能力更加的真實可信。

3.3 入侵檢測的性能分析

(1)精確度比較。

模擬地攻擊數(shù)據(jù)包，并將其保存到日志文件中，實驗中一個大約有2 000個攻擊數(shù)據(jù)包，用來測試并行關(guān)聯(lián)挖掘算法的有效性。算法的預(yù)檢測引擎可以丟棄那些認為是正常的數(shù)據(jù)包，減少沒有必要的異常檢測。

公式(10)很好地體現(xiàn)了網(wǎng)絡(luò)入侵檢測系統(tǒng)的錯誤檢測率(error detection rate，EDR)[16]：

(10)

其中，MP表示丟棄的攻擊包的數(shù)量，DP表示網(wǎng)絡(luò)入侵中所有攻擊包的數(shù)量。文中關(guān)聯(lián)規(guī)則挖掘Cloud-Apriori算法完成網(wǎng)絡(luò)入侵檢測的結(jié)果見表3和表4(分別表示傳統(tǒng)的Apriori算法和基于Cloud-Apriori算法并行關(guān)聯(lián)挖掘的結(jié)果)。

表3 傳統(tǒng)的關(guān)聯(lián)挖掘的網(wǎng)絡(luò)入侵檢測

表4 基于Cloud-Apriori的關(guān)聯(lián)挖掘的網(wǎng)絡(luò)入侵檢測

通過比較表3和表4可以看出，基于Cloud-Apriori算法的網(wǎng)絡(luò)入侵檢測的性能只有少量的改善，不是很明顯，這是因為文中的并行關(guān)聯(lián)挖掘算法只是在任務(wù)執(zhí)行階段完成了并行處理操作，所以整個算法的檢測精度只有少量提高。

(2)入侵檢測速度和效率的比較。

前面的實驗主要針對檢測精度，這部分完成傳統(tǒng)的Apriori關(guān)聯(lián)規(guī)則挖掘算法和基于MapReduce的Apriori并行關(guān)聯(lián)挖掘的算法的時間比較，如表5所示。

表5 傳統(tǒng)和并行的網(wǎng)絡(luò)入侵檢測速度的比較

從表5可以看出，當需要檢測的數(shù)據(jù)尺寸比較小的時候，MapReduce的Apriori關(guān)聯(lián)挖掘的優(yōu)勢還體現(xiàn)不出來，它的消耗時間有時比傳統(tǒng)的Apriori關(guān)聯(lián)挖掘還要多。盡管如此，隨著數(shù)據(jù)容量的不斷增加，基于Cloud-Apriori算法的關(guān)聯(lián)挖掘逐步體現(xiàn)出它的優(yōu)勢，特別是當遇到海量大數(shù)據(jù)的時候，傳統(tǒng)的Apriori關(guān)聯(lián)挖掘甚至無法完成網(wǎng)絡(luò)入侵檢測,而基于Cloud-Apriori算法的關(guān)聯(lián)挖掘可以充分利用分布式并行計算的優(yōu)點,它的執(zhí)行過程不受數(shù)據(jù)容量的限制,這也是早期很多傳統(tǒng)的軟件都被淘汰的原因,不適應(yīng)近年來的大數(shù)據(jù)、云計算技術(shù)的發(fā)展。

為了進一步驗證和分析基于MapReduce的并行關(guān)聯(lián)挖掘的網(wǎng)絡(luò)入侵檢測方法的執(zhí)行時間，改變了物理主機的數(shù)量，圖4顯示了在相同的數(shù)據(jù)容量條件下,不同的物理主機數(shù)目的執(zhí)行時間比較。

圖4 隨著物理主機個數(shù)變化的執(zhí)行時間比較

從圖4可以看出，當數(shù)據(jù)容量相同的時候，物理主機從2增加到7個，執(zhí)行時間平緩減少，執(zhí)行效率也平穩(wěn)增加。

當物理主機個數(shù)到了6～7個的時候,執(zhí)行時間越來越平穩(wěn)，表明Cloud-Apriori算法并行關(guān)聯(lián)挖掘的算法可以很好地提高網(wǎng)絡(luò)入侵檢測的速度。它也證明Hadoop集群計算雖然可以提高速度，但是加速的比例是緩慢的,因為大數(shù)據(jù)處理是一種數(shù)據(jù)密集型應(yīng)用，不能線性地降低處理時間。

4 結(jié)束語

該文提出了基于MapReduce并行關(guān)聯(lián)挖掘的網(wǎng)絡(luò)入侵檢測算法，利用Benchmark數(shù)據(jù)集和網(wǎng)絡(luò)入侵檢測這種大數(shù)據(jù)應(yīng)用對算法效果進行了仿真。結(jié)果表明，Cloud-Apriori算法比傳統(tǒng)的Apriori算法有更好的分類精度和更少的運行時間。但是，Hadoop是一個比較低版本的開源的云平臺，下一步的工作將關(guān)聯(lián)挖掘Apriori算法移植到更高級別的云計算平臺，以進一步提高關(guān)聯(lián)規(guī)則挖掘算法的速度與效率。