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

摘 要： 隨著計算機技術和互聯網的迅猛發展，對海量日志進行分析并進行入侵檢測就成為重要的研究問題。針對這一現象，提出在Hadoop平臺下利用并行化的數據挖掘算法對海量的日志信息進行分析從而進行入侵檢測，然后利用搭建好的Hadoop集群環境對其進行驗證，對不同大小的日志文件進行處理，并與單機環境下對比，證明在該平臺下進行入侵檢測的有效性和高效性，同時實驗證明如果增大集群中的節點數目，執行效率也會相應的提高。

關鍵詞： Hadoop； 日志信息分析； 入侵檢測； 并行化算法

中圖分類號： TN915.08?34； TM417 文獻標識碼： A 文章編號： 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 引 言

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

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

1 基于Hadoop海量日志的入侵檢測算法

1.1 改進的并行化K?Means算法

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

1.1.1 CPK?Means算法的整體思路

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

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

（2） Map階段：在這個階段輸入的是HDFS中鍵值對形式的序列文件。各個主機并行執行對樣本與簇的中心距離的計算，把樣本劃分到與簇的中心距離值最小的簇中。每個Map任務都有其對應的數據塊對其進行處理。

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

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

1.1.2 CPK?Means算法的實現原理

1.2 改進的并行化FP?Growth算法

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

1.2.1 LBPFP算法的整體思路

對于一個給定的數據庫DB，在對FP?Growth 算法進行MapReduce并行化時共需要五個步驟，其中需要三個MapReduce過程[4]。五個步驟如下：

（1） 切分。將給定的數據庫DB切分成若干個連續的部分并且將它們存儲在[P]臺不同的計算機上。對數據進行這樣的劃分和分布稱為切分（sharding），其中的每個部分稱為分片（shard）。

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

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

（4） 并行的FP?Growth算法。這是整個算法最關鍵的步驟，也是進行第二次MapReduce過程。

① Mapper階段：首先在每個分組中生成獨立的事務，同時每個Mapper實例都與在切分步驟中產生的一個分片相關聯。首先讀入G?list，然后對分片中的事務進行單獨地處理，在Mapper算法的計算下輸出一個或多個group?id鍵值為生成的在分組中獨立的事務鍵值對。

② Reducer階段：在分組中獨立的FP?Growth算法，當所有的Mapper實例運行結束，對于每個group?id，MapReduce的架構會自動地將所有分組中獨立的事務切分成分片，每一個Reduce實例被分配給一個或多個分組中獨立的分片，對于每一個分片，Reduce實例建立一個本地的FP?tree并且遞歸地建立條件FP?tree，一邊遞歸一邊將其發現的模式組合輸出。

（5） 聚合。將步驟（4）中產生的結果進行聚合，這也是進行第三次MapReduce過程。將聚合的結果作為最終的結果。

2 基于Hadoop海量日志的入侵檢測

2.1 整體實現框架

本文提出的解決方案主要針對的是需要進行頻繁訪問的Web應用進行入侵檢測。具體的實現原理如圖1所示。基于以上架構，本方案可以分為三個模塊：數據收集，即利用一定的工具從各個服務器中收集日志信息；數據預處理，將收集到的日志信息導入Hadoop平臺的分布式文件系統HDFS中，去掉其中多余的記錄以及每條記錄中多余的字段；在Hadoop平臺下挖掘入侵規則，對處理后的日志信息使用并行化的算法進行分析，然后將入侵IP地址保存在Hive數據庫中。

2.2 數據收集

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

2.3 數據預處理

對數據進行預處理經歷的過程如下：首先對源數據去除多余的字段并對多余的記錄進行清洗；將清洗后的數據轉換成在后續使用并行化算法進行分析時需要的數據格式；將轉好格式的待處理數據保存到HDFS中。本文中對數據進行預處理的整個過程如圖2所示。

2.3.1 Web日志格式

2.4 Hadoop平臺下挖掘入侵規則

2.4.1 挖掘入侵規則整體思路

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

2.4.2 聚類分析

在本實驗中，使用在Mahout中實現的CPK?Means聚類分析方法，對預處理后的海量日志信息數據進行聚類。

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

2.4.3 關聯規則挖掘

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

3 實驗及數據分析

3.1 實驗過程及結果分析

3.1.1 單機環境與集群環境的對比

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

3.1.3 PFP算法與LBPFP算法的對比

為了驗證在本文中提出的基于負載均衡的并行化FP?Growth算法（LBPFP）的有效性，本文選擇在有三個節點的Hadoop集群中以海量的日志信息為數據源分別執行LBPFP和PFP兩個算法，以驗證改進算法的有效性，實驗結果如圖6所示。圖中當日志信息文件較小時，LBPFP算法的性能優勢并不明顯，隨著日志文件逐漸增大，采用負載均衡的優勢逐漸表現出來。

3.2 與類似工具的比較

本文提出的是一個以分布式平臺為基礎用于入侵檢測的日志分析工具，該檢測方法是基于并行化的K?Means算法和并行化的FP?Growth算法進行異常檢測。由于采用了Hadoop架構，系統能夠支持更大規模的數據。然而，最大的容量是依據系統的內存。對以上三個工具的特征進行對比，結果如表3所示。由表3可知，本文提出的解決方案不但能夠對日志進行分析還能夠用于異常檢測，同時由于本文采取的是分布式的系統結構，能夠輸入大規模的日志文件，適用于對海量日志數據的分批處理。

4 結 論

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

參考文獻

[1] 賈世國，張昌城.基于數據挖掘的網絡入侵檢測系統設計與實現[J].計算機工程與應用，2009，44（14）：134?137.

[2] 劉曉亮，李家濱.基于數據挖掘的網絡入侵檢測系統研究[J].計算機應用與軟件，2009，26（4）：253?256.

[3] 周勇祿，吳海燕，蔣東興.基于統計異常的Web應用入侵檢測模型研究[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].吉林師范大學學報，2012（2）：115?118.

[8] 謝天宇，曹奇英.基于Hadoop集群的分布式入侵檢測系統的設計與實現[J].微計算機信息，2012（9）：167.