嚴(yán)嘉維 張琛 李成蹊

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

關(guān)鍵詞：日志分析； 可信計(jì)算；Hadoop平臺(tái)；數(shù)據(jù)挖掘；Apriori算法

DOIDOI：10.11907/rjdk.173291

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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.

英文關(guān)鍵詞Key Words：log analysis； trusted computing； Hadoop platform； data mining； Apriori

0 引言

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

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

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

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

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

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

2 日志分析模型架構(gòu)

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

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

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

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

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

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

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

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

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

Hadoop平臺(tái)下Apriori垂直化并行挖掘算法流程如下：

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

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

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

（4）頻繁1-項(xiàng)集L1中的項(xiàng)兩兩連接得出候選2-項(xiàng)集C2，C2的支持事務(wù)標(biāo)識(shí)符集合Tidset通過計(jì)算各分塊的頻繁1-項(xiàng)集的交集得到。

（5） k←2。

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

（7） k←k+1。

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

（9）輸出頻繁項(xiàng)集Lk。

Hadoop分布式平臺(tái)下的Apriori垂直化并行算法計(jì)算流程如圖4所示。

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

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

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

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

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

4 結(jié)語

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

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

參考文獻(xiàn)：

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

[2] 吉根林，趙斌.面向大數(shù)據(jù)的時(shí)空數(shù)據(jù)挖掘綜述[J].南京師大學(xué)報(bào)：自然科學(xué)版，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].計(jì)算機(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小文件存儲(chǔ)策略[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，27（1）：97-100.

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

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

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

（責(zé)任編輯：杜能鋼）