嚴嘉維 張琛 李成蹊

摘要：針對傳統(tǒng)關聯(lián)規(guī)則 Apriori 算法難以適應大數(shù)據(jù)的問題，為提高可信計算平臺日志數(shù)據(jù)分析效率， 提出了一種基于Hadoop的可信計算平臺日志分析模型。構建了日志分析模型總體框架，對非結構化原始日志數(shù)據(jù)進行垂直劃分，采用分布式文件存儲系統(tǒng)，結合MapReduce編程模式給出一種分布式Apriori并行垂直算法。通過日志挖掘建立用戶行為關聯(lián)規(guī)則庫，并采用規(guī)則匹配實現(xiàn)對用戶異常行為的檢測。理論分析和實驗數(shù)據(jù)證明，該模型在大數(shù)據(jù)環(huán)境下能夠有效提高日志分析效率。

關鍵詞：日志分析； 可信計算；Hadoop平臺；數(shù)據(jù)挖掘；Apriori算法

DOIDOI：10.11907/rjdk.173291

中圖分類號：TP301

文獻標識碼：A 文章編號：1672-7800（2018）008-0071-05

英文摘要Abstract：To solve the problem that the Aprioro algorithm can not adapt to mass data，and to improve the efficiency of analyzing log data of Trusted Computing Platform，a trusted computing log analysis model was constructed based on Hadoop platform.The framework of log analysis model was constructed.A parallel vertical algorithm of Apriori was proposed in MapReduce programming model and distributed file storage system by dividing the original non-structured log data into vertical partitioning pattern.Through log mining，the user behavior association rule base is set up.By rule matching，the user's abnormal behaviors are is detected.Mathematic analysis and simulation experiments show that the model can effectively improve the efficiency of log analysis in mass data environment.

英文關鍵詞Key Words：log analysis； trusted computing； Hadoop platform； data mining； Apriori

0 引言

為了保障計算系統(tǒng)平臺安全、可信賴地運行，提出了可信理念?？尚庞嬎阕鳛橐环N新型信息安全技術，已經(jīng)成為信息安全領域的研究熱點[1]。可信平臺日志是安全設備運行過程中產(chǎn)生的記錄數(shù)據(jù)，通過對可信計算平臺產(chǎn)生的日志進行挖掘分析，可有效判斷系統(tǒng)是否安全運行。

數(shù)據(jù)挖掘[2]是日志分析的重要方法之一。Agrawal等[3-4]首先提出了基于頻繁項集的經(jīng)典關聯(lián)規(guī)則Apriori算法。文獻[5]采用哈希函數(shù)，提出了一種基于散列（hash） 技術產(chǎn)生頻繁項集的算法；文獻[6]針對大數(shù)據(jù)量以及數(shù)據(jù)庫重復掃描問題，基于采樣思想提出了一種關聯(lián)規(guī)則算法；文獻[7]基于DIC思想，采用全局剪枝縮小候選2-項集范圍，提出了一種APM并行化算法；文獻[8]將極大序列挖掘和閉序列挖掘相結合，提出了一種壓縮序列模式挖掘算法，通過挖掘少量有代表性的的頻繁序列組合以表示全部序列模式信息；文獻[9]基于前綴等價類技術，提出了一種采用垂直數(shù)據(jù)格式的串行數(shù)據(jù)挖掘算法Eclat。采用混合搜索策略，分析效率較Apriori算法有明顯提高。文獻[10]基于概念格理論，在Eclat算法基礎上通過劃分項集子概念格，獨立生成頻繁項集，縮短了挖掘時間。文獻[11]提出了基于垂直格式的序列模式算法SPADE，將序列數(shù)據(jù)庫轉換為記錄項集位置的垂直格式數(shù)據(jù)庫，然后動態(tài)連接挖掘頻繁序列模式，算法只需掃描3次數(shù)據(jù)庫，減少了 I/O開銷。

在大數(shù)據(jù)環(huán)境下，分布式日志分析系統(tǒng)因其高可擴展性，能夠有效提高日志分析效率?；贖adoop的日志分析系統(tǒng)，通過增加水平擴展，有效解決了待處理數(shù)據(jù)量增加的問題。文獻[12]將MapReduce編程模型應用于大數(shù)據(jù)處理；文獻[13]提出了一種Barierless MapReduce并行編程模型，改善了鍵值對排序不足問題；文獻[14]針對HDFS存儲海量小文件元服務器內(nèi)存開銷過大問題，提出了一種基于混合索引的小文件存儲策略；文獻[15]將MapReduce編程模型應用于Eclat挖掘算法，但存在頻繁項缺失問題；文獻[16]利用MapReduce編程模型對Apriori算法進行改進，給出了在Hadoop分布式架構下實現(xiàn)數(shù)據(jù)挖掘的過程。

本文基于Hadoop大規(guī)模并行計算平臺，在傳統(tǒng)Apriori算法基礎上對日志源數(shù)據(jù)庫進行轉換、垂直化劃分，在MapReduce框架下提出了一種分布式垂直化Apriori算法，在此基礎上構建了一種可信平臺日志分布式分析模型。

1 關聯(lián)規(guī)則相關定義

推論：若其中所有項目P包含元素a，使得（P）

2 日志分析模型架構

可信平臺日志分析模型通過對可信計算終端生成的不同格式日志進行預處理，統(tǒng)一日志格式并生成事務數(shù)據(jù)庫，進而通過挖掘日志數(shù)據(jù)中的關聯(lián)規(guī)則，分析判定用戶行為的合法性。模型主要包括預處理模塊、挖掘模塊和關聯(lián)分析模塊。日志預處理模塊主要負責對可信計算終端生成的文件訪問、程序控制、網(wǎng)絡訪問和策略加載等日志記錄進行格式統(tǒng)一，通過篩選生成事務數(shù)據(jù)庫，并將數(shù)據(jù)轉換為適合后續(xù)挖掘模塊的數(shù)據(jù)格式；日志挖掘模塊采用分布式垂直Apriori算法進行數(shù)據(jù)挖掘，形成關聯(lián)規(guī)則；關聯(lián)分析模塊通過比對關聯(lián)規(guī)則，分析用戶行為的合法性。模型基于Hadoop分布式計算和存儲平臺，模型架構如圖1所示。

2.1 日志數(shù)據(jù)預處理模塊

可信計算終端生成的文件訪問、程序控制、網(wǎng)絡訪問及策略加載等日志記錄格式并不完全相同，為保持后續(xù)數(shù)據(jù)挖掘模塊的穩(wěn)定獨立，不受制于原始日志數(shù)據(jù)格式，需對日志格式進行預處理，實現(xiàn)格式上的統(tǒng)一?？紤]到可信計算終端操作系統(tǒng)依據(jù)的BLP模型是根據(jù)主客體安全級別間匹配關系決定是否授予主體訪問權限，本文將特定事件審計記錄作為獨立實體進行觀察，在5W1H數(shù)據(jù)分析模型基礎上定義了一種基于鍵值存儲的可信計算平臺日志格式模型，見表1。

在日志數(shù)據(jù)預處理過程中，為提高后續(xù)數(shù)據(jù)挖掘模塊工作效率，對于完全重復的日志記錄只保留一條。同時，對其它字段內(nèi)容相同，僅發(fā)生時間不同但又間隔極短的日志記錄設置時間窗口，按時間窗劃分日志記錄集，每個集合中僅保留其對應時間窗內(nèi)的第一條日志記錄?？尚庞嬎闫脚_日志預處理思路見圖2，單個時間窗口內(nèi)日志處理流程見圖3。

2.2 日志數(shù)據(jù)挖掘分析模塊

數(shù)據(jù)挖掘模塊是日志分析模型的核心模塊，其任務是采用關聯(lián)分析技術尋找可信計算平臺日志中所隱含的關聯(lián)規(guī)則。在Hadoop系統(tǒng)中，數(shù)據(jù)被默認劃分為大小約64MB的水平分塊，但水平劃分存在項目分布于不同水平分塊中的問題，因此計算出的頻繁項集會出現(xiàn)漏項。為提高數(shù)據(jù)挖掘效率，本文采用并行系統(tǒng)Hadoop中的HDFS存儲系統(tǒng)存儲原始數(shù)據(jù)，對原始數(shù)據(jù)進行垂直劃分，在MapReduce計算框架下將互不相交的數(shù)據(jù)塊分配至不同計算節(jié)點，進行并行計算，以增大并行粒度，提高計算效率。模塊部署一個主節(jié)點和若干從節(jié)點。NameNode和JobTracker共用一臺計算機作為主節(jié)點，負責日志數(shù)據(jù)的切割、數(shù)據(jù)塊分配以及計算任務分配。DataNode和TaskTracker也使用同一臺機器作為從節(jié)點，主要負責日志切分后數(shù)據(jù)塊的存儲以及負責MapReduce任務的執(zhí)行，即負責執(zhí)行日志分析模型挖掘模塊。

Apriori算法是數(shù)據(jù)挖掘經(jīng)典算法，基于水平數(shù)據(jù)格式進行挖掘，對日志數(shù)據(jù)庫的處理采用水平數(shù)據(jù)結構，如表2所示。

但水平格式需要在迭代過程中多次掃描數(shù)據(jù)庫，并在掃描過程中需要對候選項集與事務進行模式匹配，耗費大量時間。本文借鑒文獻[18]的思想，采用垂直數(shù)據(jù)格式，如表3所示。由定理1可知，若支持項目A的事務集合為TA，支持項目B的事務集合為TB，則同時支持項目A、B的事務為TA和TB的交集，因此只需進行交集運算，無需進行候選項集與事務模式匹配即可得到候選項集支持事務庫。

假設Hadoop平臺能并行處理最大數(shù)據(jù)量為maxmap，數(shù)據(jù)文件大小為N，事務數(shù)為K，HDFS的數(shù)據(jù)塊block的大小為J，則數(shù)據(jù)文件劃分為N/J個數(shù)據(jù)塊。若N/Jmaxmap，則首先將maxmap個數(shù)據(jù)塊分配至各map，任務結束后繼續(xù)分配下一個數(shù)據(jù)塊，計算每個項在事務集中的支持度，記錄支持該項集事務代碼，刪除支持度小于 K×minsup的1-項集，同時進行垂直數(shù)據(jù)格式轉化并計算頻繁2-項集。

Hadoop平臺下Apriori垂直化并行挖掘算法流程如下：

（1）掃描事務數(shù)據(jù)庫，將源數(shù)據(jù)庫平均分割為不相交的數(shù)據(jù)塊m1，m2，…，mn，將數(shù)據(jù)塊分發(fā)至各計算節(jié)點上的Map函數(shù)進行并行處理。如源數(shù)據(jù)塊為Dk：k1，k2，…，kn，經(jīng)Map函數(shù)轉化后數(shù)據(jù)格式為k1，Dk；k2，Dk；…，kn，Dk，記錄每項的支持事務代碼，計算完成后輸出臨時文件< item：Tid>，其中item為項集，Tid為支持該項集事務代碼。

（2）將各節(jié)點Map階段的本地輸出結果合并，輸出，其中Key為k項集，value為支持此項目的事務集合。

（3）用Reduce函數(shù)對各節(jié)點輸出數(shù)據(jù)進行整合并轉換為垂直1-項集，經(jīng)過Reduce函數(shù)處理后的數(shù)據(jù)如下：k1，D1，D2，…，Dn1；k2，D1，D2，…，Dn2；kn，D1，D2，…，Dnn；將支持事務集按范圍平均分割為不相交的數(shù)據(jù)塊，統(tǒng)計支持每個項的事務數(shù)，刪除支持事務數(shù)小于最小支持事務數(shù)的項，進而得出頻繁1-項集L1。

（4）頻繁1-項集L1中的項兩兩連接得出候選2-項集C2，C2的支持事務標識符集合Tidset通過計算各分塊的頻繁1-項集的交集得到。

（5） k←2。

（6）對頻繁（k-1）-項集利用定理2和推論1進行剪枝，去掉不可能成為頻繁k-項集的項集，將各（k-1）-頻繁項集兩兩連接得出候選k-項集。通過計算支持候選k-項集中各（k-1）-頻繁項集的事務交集，得出支持各項集的k-項事務集，將候選k-項集項目的TidSet分塊輸出分發(fā)給map進程。各個進程并行計算候選k-項集支持度，reduce進程負責將各個map進程的輸出結果匯總，得到全局頻繁k-項集。利用步驟（3）中的分塊思想，將全局頻繁k-項集分塊輸出到不同文件中。

（7） k←k+1。

（8）重復執(zhí)行步驟（6）-步驟（7），直到不再有頻繁項集產(chǎn)生。

（9）輸出頻繁項集Lk。

Hadoop分布式平臺下的Apriori垂直化并行算法計算流程如圖4所示。

2.3 關聯(lián)分析模塊

關聯(lián)分析模塊主要通過Apriori垂直化并行算法得到頻繁項集和每個項目支持度并生成強關聯(lián)規(guī)則。通過將得到的置信度與最小置信度進行比較，得到最小強關聯(lián)規(guī)則，這些規(guī)則反映了日志中所存在的不同操作之間的關聯(lián)關系。將日志挖掘得到的最小強關聯(lián)規(guī)則存入規(guī)則庫，在日志檢測過程中，將實時日志與規(guī)則庫進行匹配分析，進而判斷用戶行為的合法性。規(guī)則置信度由公式（1）得到：

日志關聯(lián)分析模塊工作流程如圖5所示。

可見算法時間復雜度屬于多項式時間，滿足大數(shù)據(jù)環(huán)境下的計算需求。

基于Hadoop的分布式垂直劃分Apriori算法與傳統(tǒng)Apriori算法相比，分布式垂直劃分Apriori算法在處理大數(shù)據(jù)過程中，整個數(shù)據(jù)挖掘過程僅掃描一次數(shù)據(jù)庫，采用垂直化的數(shù)據(jù)結構，將源結構大數(shù)據(jù)垂直劃分為互不相交、相互獨立的數(shù)據(jù)塊，在MapReduce計算框架下將各獨立數(shù)據(jù)塊分配至Hadoop平臺不同的計算節(jié)點進行處理，增大了并行粒度，減少了各計算節(jié)點上數(shù)據(jù)交集的運行次數(shù)，提高了可運算數(shù)據(jù)規(guī)模和挖掘效率。算法通過將并行計算過程中產(chǎn)生的中間數(shù)據(jù)進行合并，減少了中間結果的數(shù)據(jù)量，顯著降低了并行挖掘過程中的通信成本。

4 結語

本文針對傳統(tǒng)關聯(lián)規(guī)則 Apriori 算法難以適應大數(shù)據(jù)集的問題，提出了一種基于Hadoop的可信計算平臺日志分析模型。結合MapReduce編程模式給出一種分布式

架構下垂直并行挖掘算法，對源結構數(shù)據(jù)進行垂直劃分，分配給不同計算節(jié)點進行處理，增大了并行粒度，提高了并行挖掘效率。通過實時日志與規(guī)則庫進行匹配，實現(xiàn)對用戶異常行為的檢測，日志分析結果為主動防御提供了決策支持。

參考文獻：

[1] 馮登國，秦宇，汪丹，等.可信計算技術研究[J].計算機研究與發(fā)展，2011，48（8）：1332-1349.

[2] 吉根林，趙斌.面向大數(shù)據(jù)的時空數(shù)據(jù)挖掘綜述[J].南京師大學報：自然科學版，2014，37（1）：1-6.

[3] AGRAWAL R，SRIKANT R. Fast algorithms for mining association rules[C].Proceedings of International Conference on Very Large Databases.1994：487-499.

[4] AGRAWAL R， IMIELINSKI T SWAMI A.Mining association rules between sets of items in large databases[J].ACM SIGMOD Record，1993，22（2） ：207-216.

[5] PARK J S，CHEN M S，YU P S.An effective hash-based algorithm for mining association rules[J].SIGMOD Record，1995，25（2） ：175-186.

[6] TOIVONEN H.Sampling large databases for association rules[C].Proceedings of the 22nd International Conference on Very Large Databases.1996：1-12.

[7] CHEUNG D W，HAN J，NG V，et al.A fast distributed algorithm for mining association rules[C].Proceedings of International Conference on Parallel and Distributed Information Systems.1996：31-44.

[8] 童詠昕，張媛媛，袁玫，等.一種挖掘壓縮序列模式的有效算法[J].計算機研究與發(fā)展，2010，47（1）：72-80.

[9] ZAKI M J，PARTHASARATHY S，OGIHARA M，et al.New algorithms for fast discovery of association rules[C].Proceedings of 3rd intlconf on knowledge discovery and data mining.Palo Alto，California：AAAI Press，1997：283-286.

[10] ZAKI M J.Scalable algorithms for association mining[J].IEEE transactions on knowledge and data engineering，2000，12（3）：372-390.

[11] ZAKI M J.SPADE：an efficient algorithm for mining frequent sequences[J].Machine Learning，2001，42（1）：31-60.

[12] DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters[J]. Communications of the ACM，2008，51（1） ：107-113.

[13] VERMA A，ZEA N，CHO B，et al.Breaking the MapReduce stage barrier[C].Proceedings of 2010 IEEE International Conference Cluster Computing（CLUSTER10），2010：235-244.

[14] 熊安萍，黃容，鄒樣.一種基于混合索引的HDFS小文件存儲策略[J].重慶郵電大學學報：自然科學版，2014，27（1）：97-100.

[15] 李偉衛(wèi)，趙航，張陽，等.基于MapReduce的海量數(shù)據(jù)挖掘技術研究[EB/OL].http：//www.cnk.net/kcms/detail /11.2127.TP.20120601.1457.016.html.

[16] 崔妍，包志強.關聯(lián)規(guī)則挖掘綜述[J].計算機應用研究，2016，33（2）：330-334.

[17] 崔貫勛，李梁，王柯柯，等.關聯(lián)規(guī)則挖掘中Apriori算法的研究與改進[J].計算機應用，2010，30（11）：2952-2955.

（責任編輯：杜能鋼）