基于海量日志的入侵檢測(cè)并行化算法研究

摘 要： 隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)的迅猛發(fā)展，對(duì)海量日志進(jìn)行分析并進(jìn)行入侵檢測(cè)就成為重要的研究問題。針對(duì)這一現(xiàn)象，提出在Hadoop平臺(tái)下利用并行化的數(shù)據(jù)挖掘算法對(duì)海量的日志信息進(jìn)行分析從而進(jìn)行入侵檢測(cè)，然后利用搭建好的Hadoop集群環(huán)境對(duì)其進(jìn)行驗(yàn)證，對(duì)不同大小的日志文件進(jìn)行處理，并與單機(jī)環(huán)境下對(duì)比，證明在該平臺(tái)下進(jìn)行入侵檢測(cè)的有效性和高效性，同時(shí)實(shí)驗(yàn)證明如果增大集群中的節(jié)點(diǎn)數(shù)目，執(zhí)行效率也會(huì)相應(yīng)的提高。

關(guān)鍵詞： Hadoop； 日志信息分析； 入侵檢測(cè)； 并行化算法

中圖分類號(hào)： TN915.08?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）19?0071?05

Abstract： With the rapid development of computer technology and Internet， how to analyze the massive logs and perform the intrusion detection become the important research contents. To soleve these difficulties， the parallel data mining algorithm is used to analyze the massive logs information on Hadoop platform， so as to perform the intrusion detection. The established Hadoop cluster environment is used to verify the intrusion detection， and process the log files with different sizes. In comparison with the intrusion detection result verified in the stand?alone environment， the effectiveness and efficiency of the intrusion detection on Hadoop platform were verified. And the experiment results verify that if the node quantity in the cluster is increased， the execution efficiency will be improved accordingly.

Keywords： Hadoop； log information analysis； intrusion detection； parallel algorithm

0 引 言

隨著信息技術(shù)的迅猛發(fā)展以及Web應(yīng)用的快速普及，許多企業(yè)都擁有獨(dú)立的Web服務(wù)器，然而其開放的特性也帶來了不可忽視的安全問題。數(shù)量龐大的Web服務(wù)器以及層出不窮的應(yīng)用安全漏洞為黑客和蠕蟲攻擊提供了可乘之機(jī)[1]。

在Web日志中有應(yīng)用是如何被訪問的數(shù)據(jù)記錄，對(duì)這些日志的分析不僅可以發(fā)現(xiàn)入侵的痕跡，而且可以通過對(duì)攻擊方法的分析找出系統(tǒng)中存在的安全漏洞進(jìn)而采取安全措施對(duì)該種類型的攻擊進(jìn)行防范。對(duì)應(yīng)用進(jìn)行攻擊與進(jìn)行合法的操作產(chǎn)生的日志信息相似度是非常高的，如果單純依靠人工進(jìn)行辨別，對(duì)工作人員的知識(shí)豐富程度和工作經(jīng)驗(yàn)都有極高的要求[2]。同時(shí)，Web應(yīng)用產(chǎn)生的日志信息數(shù)量是極其巨大的。因此，采用一定的入侵檢測(cè)技術(shù)來保護(hù)應(yīng)用系統(tǒng)，幫助其對(duì)抗各種類型的入侵攻擊行為是十分重要的。

1 基于Hadoop海量日志的入侵檢測(cè)算法

1.1 改進(jìn)的并行化K?Means算法

K?均值（K?Means Clustering）算法是最著名的劃分聚類算法，因?yàn)樗哂泻?jiǎn)潔和效率高的特性，是所有聚類算法中最頻繁地被使用的。一般情況下，K?Means算法的應(yīng)用會(huì)局限在數(shù)據(jù)量較小的數(shù)據(jù)集中，然而，本文主要針對(duì)的是海量的數(shù)據(jù)集，傳統(tǒng)的K?Means算法并不能滿足研究的要求。為了能夠讓其更好地對(duì)海量數(shù)據(jù)進(jìn)行處理，需要研究在Hadoop平臺(tái)下對(duì)K?Means算法進(jìn)行并行化的改進(jìn)。為了提高整體的效率，對(duì)Hadoop的Mahout項(xiàng)目中已經(jīng)實(shí)現(xiàn)的并行化K?Means算法[3]進(jìn)行了研究，并在其基礎(chǔ)上進(jìn)行了改進(jìn)，提出了一種對(duì)Combiner中的計(jì)算方法進(jìn)行修改的CPK?Means（Combined Parallel K?Means）算法。主要的改進(jìn)是為了提高計(jì)算效率，在Combiner函數(shù)中先對(duì)每個(gè)簇中的本地?cái)?shù)據(jù)進(jìn)行平均值的計(jì)算，然后再到Reduce階段進(jìn)行匯總，避免了Reduce階段需要處理大量數(shù)據(jù)，負(fù)載過重的問題。

1.1.1 CPK?Means算法的整體思路

本文提出的CPK?Means算法主要可以分為四個(gè)階段：初始化階段、Map階段、Combine階段和Reduce階段。

（1） 初始化階段：將數(shù)據(jù)集分割成HDFS文件塊，并且將它們復(fù)制并傳遞到其他機(jī)器。根據(jù)分塊的編號(hào)和集群的配置，它們將被分配和指派必要的任務(wù)。

（2） Map階段：在這個(gè)階段輸入的是HDFS中鍵值對(duì)形式的序列文件。各個(gè)主機(jī)并行執(zhí)行對(duì)樣本與簇的中心距離的計(jì)算，把樣本劃分到與簇的中心距離值最小的簇中。每個(gè)Map任務(wù)都有其對(duì)應(yīng)的數(shù)據(jù)塊對(duì)其進(jìn)行處理。

（3） Combine階段：每個(gè)Map任務(wù)結(jié)束后，應(yīng)用Combiner函數(shù)對(duì)同一個(gè)Map任務(wù)的中間數(shù)據(jù)進(jìn)行操作，由于中間數(shù)據(jù)保存在主機(jī)的本地磁盤中，這個(gè)過程不需要消耗高昂的通信成本。Combiner函數(shù)中，先計(jì)算被劃分到同一個(gè)簇中的所有數(shù)據(jù)的總和，同時(shí)記錄在同一個(gè)Map任務(wù)中同一個(gè)簇中的樣本數(shù)量，然后計(jì)算平均值，將平均值傳遞給Reduce函數(shù)。

（4） Reduce階段：Reduce函數(shù)的輸入是從各個(gè)主機(jī)獲取來自Combine函數(shù)的數(shù)據(jù)，數(shù)據(jù)中包含每一個(gè)分塊中同一個(gè)簇中樣本的平均值。而在Reduce函數(shù)中直接使用獲取到的平均值就可以計(jì)算出每個(gè)簇中所有樣本的總體平均值。因此，可以使用簇中所有點(diǎn)的坐標(biāo)的平均值重新計(jì)算簇的中心。相關(guān)聯(lián)的點(diǎn)都會(huì)用來計(jì)算平均值以得到新的簇的中心坐標(biāo)值。簇的中心信息會(huì)反饋到Mapper中。循環(huán)這個(gè)過程直到聚類中心的值趨近于收斂的水平。

1.1.2 CPK?Means算法的實(shí)現(xiàn)原理

1.2 改進(jìn)的并行化FP?Growth算法

在FP?Growth算法中使用了頻繁模式樹（FrequentPatternTree，F(xiàn)P?tree），通過這棵樹即可生成關(guān)聯(lián)規(guī)則。在FP?Growth算法中可以分為生成FP?tree和從FP?tree得到頻繁模式兩個(gè)階段。為了使各臺(tái)主機(jī)進(jìn)行計(jì)算時(shí)的負(fù)載盡可能相等，以提高整體的效率，本文提出了基于負(fù)載均衡的并行FP?Growth算法LBPFP（Load Balanced Parallel FP?Growth）。主要的改進(jìn)部分是在將待處理的數(shù)據(jù)切分后分組時(shí)的分組方法上，考慮采用負(fù)載均衡的分組方法，首先對(duì)每個(gè)頻繁項(xiàng)在條件模式基上運(yùn)行FP?Growth算法的工作量進(jìn)行預(yù)估，然后盡可能根據(jù)預(yù)估的工作量將這些條目平均地分布到集群中的各個(gè)節(jié)點(diǎn)。

1.2.1 LBPFP算法的整體思路

對(duì)于一個(gè)給定的數(shù)據(jù)庫DB，在對(duì)FP?Growth 算法進(jìn)行MapReduce并行化時(shí)共需要五個(gè)步驟，其中需要三個(gè)MapReduce過程[4]。五個(gè)步驟如下：

（1） 切分。將給定的數(shù)據(jù)庫DB切分成若干個(gè)連續(xù)的部分并且將它們存儲(chǔ)在[P]臺(tái)不同的計(jì)算機(jī)上。對(duì)數(shù)據(jù)進(jìn)行這樣的劃分和分布稱為切分（sharding），其中的每個(gè)部分稱為分片（shard）。

（2） 并行計(jì)算。第一個(gè)MapReduce過程，使用MapReduce方法計(jì)算出現(xiàn)在DB中的所有條目的支持度。在Mapper階段，輸入為步驟中切分出來的一個(gè)分片。在這個(gè)步驟中，間接地發(fā)現(xiàn)了數(shù)據(jù)庫DB中條目的詞匯集[I，]一般情況下這在巨型數(shù)據(jù)庫中是未知的。在這個(gè)步驟中的計(jì)算結(jié)果保存在F?list中。

（3） 負(fù)載均衡的分組。將F?list中的所有條目[I]按照負(fù)載均衡的方法劃分成[Q]組，每個(gè)組稱為G?list，每個(gè)組設(shè)定一個(gè)惟一的ID稱為gid。具體包括采用預(yù)估的方式計(jì)算負(fù)載以及采用貪心算法進(jìn)行分組兩個(gè)步驟。

（4） 并行的FP?Growth算法。這是整個(gè)算法最關(guān)鍵的步驟，也是進(jìn)行第二次MapReduce過程。

① Mapper階段：首先在每個(gè)分組中生成獨(dú)立的事務(wù)，同時(shí)每個(gè)Mapper實(shí)例都與在切分步驟中產(chǎn)生的一個(gè)分片相關(guān)聯(lián)。首先讀入G?list，然后對(duì)分片中的事務(wù)進(jìn)行單獨(dú)地處理，在Mapper算法的計(jì)算下輸出一個(gè)或多個(gè)group?id鍵值為生成的在分組中獨(dú)立的事務(wù)鍵值對(duì)。

② Reducer階段：在分組中獨(dú)立的FP?Growth算法，當(dāng)所有的Mapper實(shí)例運(yùn)行結(jié)束，對(duì)于每個(gè)group?id，MapReduce的架構(gòu)會(huì)自動(dòng)地將所有分組中獨(dú)立的事務(wù)切分成分片，每一個(gè)Reduce實(shí)例被分配給一個(gè)或多個(gè)分組中獨(dú)立的分片，對(duì)于每一個(gè)分片，Reduce實(shí)例建立一個(gè)本地的FP?tree并且遞歸地建立條件FP?tree，一邊遞歸一邊將其發(fā)現(xiàn)的模式組合輸出。

（5） 聚合。將步驟（4）中產(chǎn)生的結(jié)果進(jìn)行聚合，這也是進(jìn)行第三次MapReduce過程。將聚合的結(jié)果作為最終的結(jié)果。

2 基于Hadoop海量日志的入侵檢測(cè)

2.1 整體實(shí)現(xiàn)框架

本文提出的解決方案主要針對(duì)的是需要進(jìn)行頻繁訪問的Web應(yīng)用進(jìn)行入侵檢測(cè)。具體的實(shí)現(xiàn)原理如圖1所示?；谝陨霞軜?gòu)，本方案可以分為三個(gè)模塊：數(shù)據(jù)收集，即利用一定的工具從各個(gè)服務(wù)器中收集日志信息；數(shù)據(jù)預(yù)處理，將收集到的日志信息導(dǎo)入Hadoop平臺(tái)的分布式文件系統(tǒng)HDFS中，去掉其中多余的記錄以及每條記錄中多余的字段；在Hadoop平臺(tái)下挖掘入侵規(guī)則，對(duì)處理后的日志信息使用并行化的算法進(jìn)行分析，然后將入侵IP地址保存在Hive數(shù)據(jù)庫中。

2.2 數(shù)據(jù)收集

在日志收集階段，需要從各個(gè)Web前端服務(wù)器上收集原始的Web日志文件，在收集時(shí)需要選擇服務(wù)器工作壓力較小的階段，從而防止出現(xiàn)網(wǎng)絡(luò)堵塞、耗時(shí)較高的現(xiàn)象[5]。具體的過程是將保存在不同Web服務(wù)器上的日志文件先匯總到一臺(tái)機(jī)器中，然后傳遞給集群中的名稱節(jié)點(diǎn)服務(wù)器，由名稱節(jié)點(diǎn)服務(wù)器對(duì)數(shù)據(jù)進(jìn)行切分并分配到若干個(gè)數(shù)據(jù)節(jié)點(diǎn)服務(wù)器中，同時(shí)各個(gè)數(shù)據(jù)節(jié)點(diǎn)服務(wù)器之間是可以實(shí)現(xiàn)數(shù)據(jù)共享的，同時(shí)可以實(shí)時(shí)地和名稱節(jié)點(diǎn)服務(wù)器進(jìn)行通信；由名稱節(jié)點(diǎn)服務(wù)器將數(shù)據(jù)交給進(jìn)行數(shù)據(jù)預(yù)處理的機(jī)器進(jìn)而保存到HDFS中。在這個(gè)步驟中，可以選擇使用工具Flume從每個(gè)主機(jī)收集日志信息并把它們保存在HDFS中。

2.3 數(shù)據(jù)預(yù)處理

對(duì)數(shù)據(jù)進(jìn)行預(yù)處理經(jīng)歷的過程如下：首先對(duì)源數(shù)據(jù)去除多余的字段并對(duì)多余的記錄進(jìn)行清洗；將清洗后的數(shù)據(jù)轉(zhuǎn)換成在后續(xù)使用并行化算法進(jìn)行分析時(shí)需要的數(shù)據(jù)格式；將轉(zhuǎn)好格式的待處理數(shù)據(jù)保存到HDFS中。本文中對(duì)數(shù)據(jù)進(jìn)行預(yù)處理的整個(gè)過程如圖2所示。

2.3.1 Web日志格式

2.4 Hadoop平臺(tái)下挖掘入侵規(guī)則

2.4.1 挖掘入侵規(guī)則整體思路

在Hadoop平臺(tái)下使用預(yù)處理后的海量日志信息進(jìn)行入侵規(guī)則挖掘的整體思路為：將預(yù)處理后的數(shù)據(jù)在Mahout下分別使用并行化的K?Means和FP?Growth算法進(jìn)行分析，然后將結(jié)果合并，將最終的入侵IP地址保存在Hive數(shù)據(jù)庫中。具體的過程如圖3所示。

2.4.2 聚類分析

在本實(shí)驗(yàn)中，使用在Mahout中實(shí)現(xiàn)的CPK?Means聚類分析方法，對(duì)預(yù)處理后的海量日志信息數(shù)據(jù)進(jìn)行聚類。

在Mahout中處理的文件必須是SequenceFile格式，而CPK?Means聚類算法處理的文件必須是向量格式，因此在Mahout中使用CPK?Means算法需要有以下三個(gè)步驟：使用seqdirectory命令將待處理文件轉(zhuǎn)化為序列文件；使用seq2sparse命令將序列文件轉(zhuǎn)化為向量文件；使用cpkmeans命令執(zhí)行CPK?Means聚類算法[6]。

2.4.3 關(guān)聯(lián)規(guī)則挖掘

以海量的Web日志信息為數(shù)據(jù)源，經(jīng)過預(yù)處理，只保留IP地址和狀態(tài)碼兩個(gè)字段，并且過濾掉訪問成功（即返回狀態(tài)碼為200）的Web日志信息記錄，使用Hadoop架構(gòu)的Mahout項(xiàng)目中對(duì)關(guān)聯(lián)規(guī)則算法FP?Grwoth進(jìn)行并行化的ParallelFP?Growth算法（PFP算法），通過分析狀態(tài)碼與IP地址之間的關(guān)聯(lián)關(guān)系，找出可疑的IP地址并把它們保存在Hadoop架構(gòu)下的數(shù)據(jù)庫中[7]。

3 實(shí)驗(yàn)及數(shù)據(jù)分析

3.1 實(shí)驗(yàn)過程及結(jié)果分析

3.1.1 單機(jī)環(huán)境與集群環(huán)境的對(duì)比

從圖5中可以看出，當(dāng)集群采用的節(jié)點(diǎn)數(shù)目越多時(shí)，Hadoop平臺(tái)下對(duì)海量日志進(jìn)行入侵檢測(cè)分析所需的執(zhí)行時(shí)間越少。這是由于隨著集群中節(jié)點(diǎn)數(shù)目的增長(zhǎng)，處理相同數(shù)據(jù)時(shí)的執(zhí)行效率相應(yīng)地提高，因此處理時(shí)間也會(huì)降低。由于受到實(shí)驗(yàn)條件的限制，在本實(shí)驗(yàn)中集群中的節(jié)點(diǎn)數(shù)目并未設(shè)置過大的數(shù)值，但是可以預(yù)見，當(dāng)集群中節(jié)點(diǎn)數(shù)目增長(zhǎng)到一定規(guī)模時(shí)，在各種外界因素條件的影響下，集群處理效率的增長(zhǎng)速度會(huì)變緩，甚至停止。

3.1.3 PFP算法與LBPFP算法的對(duì)比

為了驗(yàn)證在本文中提出的基于負(fù)載均衡的并行化FP?Growth算法（LBPFP）的有效性，本文選擇在有三個(gè)節(jié)點(diǎn)的Hadoop集群中以海量的日志信息為數(shù)據(jù)源分別執(zhí)行LBPFP和PFP兩個(gè)算法，以驗(yàn)證改進(jìn)算法的有效性，實(shí)驗(yàn)結(jié)果如圖6所示。圖中當(dāng)日志信息文件較小時(shí)，LBPFP算法的性能優(yōu)勢(shì)并不明顯，隨著日志文件逐漸增大，采用負(fù)載均衡的優(yōu)勢(shì)逐漸表現(xiàn)出來。

3.2 與類似工具的比較

本文提出的是一個(gè)以分布式平臺(tái)為基礎(chǔ)用于入侵檢測(cè)的日志分析工具，該檢測(cè)方法是基于并行化的K?Means算法和并行化的FP?Growth算法進(jìn)行異常檢測(cè)。由于采用了Hadoop架構(gòu)，系統(tǒng)能夠支持更大規(guī)模的數(shù)據(jù)。然而，最大的容量是依據(jù)系統(tǒng)的內(nèi)存。對(duì)以上三個(gè)工具的特征進(jìn)行對(duì)比，結(jié)果如表3所示。由表3可知，本文提出的解決方案不但能夠?qū)θ罩具M(jìn)行分析還能夠用于異常檢測(cè)，同時(shí)由于本文采取的是分布式的系統(tǒng)結(jié)構(gòu)，能夠輸入大規(guī)模的日志文件，適用于對(duì)海量日志數(shù)據(jù)的分批處理。

4 結(jié) 論

Web應(yīng)用的安全問題越來越受到人們的關(guān)注，通過分析記錄了用戶行為的服務(wù)器的日志信息，利用數(shù)據(jù)挖掘算法找出其中的有效信息進(jìn)行入侵檢測(cè)更是一種行之有效的方案。然而，隨著業(yè)務(wù)的增長(zhǎng)使得單一節(jié)點(diǎn)的計(jì)算平臺(tái)無法處理日益增加的海量日志信息，亟需利用分布式的計(jì)算平臺(tái)提高計(jì)算效率。本文正是為這樣的問題提供了一種解決方案，利用分布式計(jì)算平臺(tái)Hadoop框架，以海量日志信息為數(shù)據(jù)源，采用并行化的數(shù)據(jù)挖掘算法分析日志信息從而進(jìn)行入侵檢測(cè)。

參考文獻(xiàn)

[1] 賈世國，張昌城.基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2009，44（14）：134?137.

[2] 劉曉亮，李家濱.基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)研究[J].計(jì)算機(jī)應(yīng)用與軟件，2009，26（4）：253?256.

[3] 周勇祿，吳海燕，蔣東興.基于統(tǒng)計(jì)異常的Web應(yīng)用入侵檢測(cè)模型研究[J].計(jì)算機(jī)安全，2012（5）：8?12.

[4] SHVACHKO K， KUANG H， RADIA S， et al. The Hadoop distributed file system [C]// Proceedings of 2010 IEEE 26th Symposium on Mass Storage Systems and Technologies. Incline Village： IEEE， 2010： 1?10.

[5] GARCIA?TEODORO P， DIAZ?VERDEJO J， MACIá?FERNáNDEZ G， et al. Anomaly?based network intrusion detection： techniques， systems and challenges [J]. Computers security， 2009， 28（1/2）： 18?28.

[6] EZEIFE C I， DONG J， AGGARWAL A K. SensorWebIDS： a Web mining intrusion detection system [J]. International journal of Web information systems， 2007， 4（1）： 509?512.

[7] 魏德志，吳旭，林麗娜，等.基于云計(jì)算的模糊規(guī)則挖掘算法在入侵檢測(cè)中的應(yīng)用[J].吉林師范大學(xué)學(xué)報(bào)，2012（2）：115?118.

[8] 謝天宇，曹奇英.基于Hadoop集群的分布式入侵檢測(cè)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].微計(jì)算機(jī)信息，2012（9）：167.