甕俊昊

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

隨著網(wǎng)絡(luò)規(guī)模的逐漸擴(kuò)大，互聯(lián)網(wǎng)相關(guān)技術(shù)的日新月異，安全問題也日益突出，屢見不鮮的病毒、漏洞、攻擊層出不窮。網(wǎng)絡(luò)安全問題不僅嚴(yán)重影響了人民的生活，還對一個國家的安全和經(jīng)濟(jì)發(fā)展產(chǎn)生了嚴(yán)重威脅[1]。對于網(wǎng)絡(luò)安全信息分析來說，日志數(shù)據(jù)作為信息挖掘的依據(jù)和基礎(chǔ)在其中占據(jù)著重要的地位，日志描述了設(shè)備的相關(guān)行為，其中存在著大量未知信息，安全日志數(shù)據(jù)分析可以用來監(jiān)測網(wǎng)絡(luò)的入侵行為，在故障或安全事件發(fā)生時，日志就像是黑匣子，維護(hù)人員可以從這些數(shù)據(jù)記錄中進(jìn)行分析，查找故障源、獲取攻擊行為、重建攻擊過程等，通過對安全隱患或事件的分析，執(zhí)法機(jī)關(guān)還可以用來打擊網(wǎng)絡(luò)犯罪[2]。

現(xiàn)如今，隨著日志數(shù)據(jù)的數(shù)量越來越多，類型越來越多樣，數(shù)據(jù)處理的要求也越來越高[3]，日志分析系統(tǒng)的功能就是通過對日志數(shù)據(jù)的分析發(fā)現(xiàn)系統(tǒng)的異常以便提出應(yīng)對策略。網(wǎng)絡(luò)管理人員可以通過對日志進(jìn)行分析來尋找網(wǎng)絡(luò)故障的原因，還可以根據(jù)分析結(jié)果找到攻擊者遺留的痕跡。但是由于日志數(shù)量繁多，而且根據(jù)日志的特點(diǎn)，它在種類上具有多樣性，不同設(shè)備產(chǎn)生的日志差異較大，所以有效地對日志進(jìn)行處理分析才能得到分析人員的預(yù)期結(jié)果[4]。目前為止，針對日志分析已有許多方法，并且也衍生出了許多日志分析工具。目前針對安全日志的關(guān)聯(lián)分析方法大致可分為4類，分別是基于統(tǒng)計(jì)、基于規(guī)則庫、基于狀態(tài)轉(zhuǎn)移以及基于數(shù)據(jù)挖掘的分析方法。本文重心是在研究基于數(shù)據(jù)挖掘的日志分析的基礎(chǔ)上，對基于Apriori算法的關(guān)聯(lián)分析方法進(jìn)行改進(jìn)，從而在日志分析上能夠提供更高的效率。本文主要提出一個基于矩陣Apriori算法增加權(quán)重向量的關(guān)聯(lián)規(guī)則挖掘方法，并根據(jù)測試數(shù)據(jù)集進(jìn)行效率測試，驗(yàn)證了該方法在關(guān)聯(lián)規(guī)則的挖掘上能夠大幅提高運(yùn)行效率。

1 多源安全日志關(guān)聯(lián)分析

多源日志的關(guān)聯(lián)分析是指通過特定的規(guī)則對從多種設(shè)備上收集到的日志進(jìn)行相關(guān)性描述，然后通過使用一些關(guān)聯(lián)分析算法從這些結(jié)果數(shù)據(jù)中提取安全事件[5]。企業(yè)信息系統(tǒng)中包含路由器、防火墻、IDS/IPS、交換機(jī)、服務(wù)器和SQL數(shù)據(jù)庫等多個種類的設(shè)備[6]。各種復(fù)雜的應(yīng)用系統(tǒng)和網(wǎng)絡(luò)設(shè)備每天都產(chǎn)生大量的日志信息，查找如此海量的數(shù)據(jù)并分析出其中的安全事件，對管理員來說意味著海量的工作和拖延的工作效率。在互聯(lián)網(wǎng)中海量異構(gòu)的日志大致分成以下三類：System log（UNIX/LINUX、Windows）、Network de-vice log（硬件設(shè)備、安全設(shè)備）、Application log（Web、軟件等）。

在基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)安全日志分析方法中，Apriori算法的應(yīng)用十分廣泛，通過挖掘數(shù)據(jù)集中的不同規(guī)則，找出滿足給定條件下的多個領(lǐng)域之間的依賴關(guān)系[7]。通過使用頻繁項(xiàng)目集的挖掘算法挖掘出了網(wǎng)絡(luò)中異常事件的IP、端口等屬性間的關(guān)聯(lián)特征，以幫助分析人員對網(wǎng)絡(luò)安全事件進(jìn)行識別[8]。對網(wǎng)絡(luò)安全日志進(jìn)行關(guān)聯(lián)分析時，因?yàn)榫W(wǎng)絡(luò)中的連接信息是多屬性元組，所以在挖掘過程中使用的是多維關(guān)聯(lián)規(guī)則。例如在對IDS日志進(jìn)行挖掘分析時得出的其中一條規(guī)則：{SIP:220.228.136.38,DIP:11.11.79.83,EventType:Attempted information Leak,123}該規(guī)則表示目的IP 11.11.79.83在被監(jiān)控時間內(nèi)被源IP 220.228.136.38使用Attempted Information Leak攻擊共計(jì)123次。通過Apriori算法可以挖掘出各安全事件IP、端口間的關(guān)聯(lián)關(guān)系，從而建立起各安全事件的屬性特征，提高事件的檢測效率。本文提出了一種基于矩陣的Apriori增加權(quán)重向量的改進(jìn)方法來進(jìn)行挖掘，下一節(jié)將進(jìn)行詳細(xì)描述。

2 基于改進(jìn)矩陣Apriori算法的關(guān)聯(lián)規(guī)則挖掘研究

2. 1 傳統(tǒng)Apriori算法的關(guān)聯(lián)規(guī)則挖掘

傳統(tǒng)基于Apriori算法的技術(shù)通常應(yīng)用于查找項(xiàng)集之間的具有可信的和代表性的規(guī)則[9]，類似A?B的表達(dá)式即一條關(guān)聯(lián)規(guī)則，Apriori算法包含兩個常用指標(biāo)，分別是支持度（Support count）和置信度（Confidence），支持度（Support count）表示事務(wù)集T中事件A所發(fā)生的頻率，支持度越高，說明這個事件發(fā)生的越頻繁，用A.count表示計(jì)數(shù)：Sup_count(A?B)=，其中N表示事務(wù)集T中的事務(wù)總數(shù)。置信度（Confidence）表示A的前提下B同時發(fā)生的條件概率，它決定了關(guān)聯(lián)規(guī)則是否足夠準(zhǔn)確，有以下公式計(jì)算：

在Apriori算法中，滿足預(yù)先設(shè)定的最小支持度min_sup的項(xiàng)目集合，稱為頻繁項(xiàng)集，然后從中提取的所有規(guī)則中尋找到滿足預(yù)先設(shè)定的最小置信度min_conf的規(guī)則，稱為強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘算法實(shí)際上就是一個不斷生成頻繁項(xiàng)集并尋找強(qiáng)關(guān)聯(lián)規(guī)則的過程。傳統(tǒng)的Apriori使用廣度優(yōu)先查找方式來找到頻繁1項(xiàng)集，并由（k-1）-itemset自連接生成kitemset，其中 k=2，3，…，m；m 代表最大的項(xiàng)目集合，通過min_sup修剪來獲得最終的頻繁k-itemset。

2. 2 基于矩陣的Apriori算法研究

在傳統(tǒng)的Apriori算法中，當(dāng)我們使用頻繁（k-1）-itemset自連接生成k-itemset時，如果頻繁（k-1）-itemset的數(shù)量非常大，Apriori算法需要進(jìn)行大量的I/O操作從而占用大量的CPU資源，而且會得到很多的候選項(xiàng)集，效率低下[10]；同時，傳統(tǒng)Apriori算法缺少對安全日志自身結(jié)構(gòu)的考慮，所以在進(jìn)行關(guān)聯(lián)挖掘時會產(chǎn)生許多無效規(guī)則。針對Apriori算法存在的缺點(diǎn)，眾多學(xué)者提出了多種改進(jìn)方法，例如將矩陣融入到Apriori算法中產(chǎn)生的基于矩陣的Apriori算法[11]，用0-1矩陣的方式存儲和展示數(shù)據(jù)，只需通過矩陣的運(yùn)算就能得到所需要的頻繁項(xiàng)集，而且全程只搜索一次數(shù)據(jù)庫，就能得到所有符合條件的項(xiàng)集，大幅度提高算法效率，同時減少大量候選項(xiàng)集的產(chǎn)生，節(jié)約了存儲空間[12]。

事務(wù)中的每個屬性及事務(wù)集按照序列排列。矩陣中的行表示事務(wù)中的屬性，列表示事務(wù)。假設(shè)在m事務(wù)中存在編號n的屬性，則對應(yīng)生成的矩陣中第m行的第n列的值記為1，反之為0，矩陣中每列數(shù)字的和為屬性計(jì)數(shù)，即為支持度的計(jì)算結(jié)果。例如對于二項(xiàng)集（Mm,Mn），僅需要查看矩陣的第m、n行上處于相同列中均為1的計(jì)數(shù)，便為它的支持度。以下是基于矩陣的Apriori算法步驟：

（1）首先根據(jù)事務(wù)集T構(gòu)造0-1矩陣MT。其中若屬性n在事務(wù)m中出現(xiàn)，則對應(yīng)矩陣元素Mij=1，反之Mij=0。

（2）對MT每列1的值進(jìn)行計(jì)數(shù)，刪除計(jì)數(shù)結(jié)果低于min_sup的項(xiàng)（行向量），對滿足min_sup的結(jié)果每兩列做向量的交運(yùn)算。

（3）利用上述結(jié)果構(gòu)建新矩陣，重復(fù)此過程，直到不再產(chǎn)生新矩陣，最終矩陣就是我們要求的頻繁項(xiàng)集。

使用基于矩陣Apriori算法的具體計(jì)算流程如圖1。

圖1 基于矩陣Apriori算法計(jì)算流圖

2. 3 基于改進(jìn)的加權(quán)矩陣 Apriori算法研究

2.2小節(jié)描述的算法在計(jì)算過程中會不斷生成新的矩陣，而且根據(jù)事務(wù)量的不同，矩陣也同樣需要發(fā)生變化，本文通過研究Apriori算法生成矩陣中的數(shù)據(jù)關(guān)系，發(fā)現(xiàn)很多行和列可以進(jìn)行優(yōu)化，通過增加一個權(quán)重向量的方式，對矩陣整體進(jìn)行精簡，提高計(jì)算效率。

假設(shè)事務(wù)集T中含有m條事務(wù)和n個屬性，二進(jìn)制布爾矩陣可據(jù)此構(gòu)建如下：

其中Ti代表事務(wù)集合T中第i條記錄，存在一個權(quán)重向量WT，初始時WT={1 ,1,...,1}，當(dāng)連續(xù)掃描Ti時如果發(fā)現(xiàn)相同的事務(wù)，對應(yīng)權(quán)重值加1，同時刪除矩陣中相應(yīng)行，支持度sup_coun（tI）可由WTI表示，I是矩陣中的列向量，具體算法流程圖如圖2。

圖2 基于改進(jìn)的加權(quán)矩陣Apriori算法流程圖

根據(jù)Apriori算法的性質(zhì)，我們有以下兩個推論：

推論1：如果兩個頻繁項(xiàng)集（k-1）-itemset可以進(jìn)行連接生成k-itemset，那么它們必然存在一個相同的（k-2）-itemset。

推論2：如果項(xiàng)目集是頻繁的，那么它的所有子集必然也是頻繁的，相應(yīng)的，非頻繁項(xiàng)集的超集肯定也是非頻繁的。

同樣使用圖一中示例事務(wù)集T，構(gòu)建初始矩陣并進(jìn)行運(yùn)算過程如下：

3 實(shí)驗(yàn)對比分析

為了驗(yàn)證基于矩陣加權(quán)的Apriori算法的性能，本節(jié)將該方法與傳統(tǒng)基于矩陣的Apriori算法進(jìn)行相同環(huán)境下的對比實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境在處理器為Intel Corei7-7700 CPU@3.6GHz、內(nèi)存為16G的64位計(jì)算機(jī)上進(jìn)行，程序在Weka平臺下測試，數(shù)據(jù)集選用在UCIMLRepository中的Retail數(shù)據(jù)集，專門用于數(shù)據(jù)挖掘中的算法測試。

從該數(shù)據(jù)集中分別隨機(jī)選擇1000,5000,10000,30000,50000條記錄作為測試用例，min_sup=20%，兩種算法的運(yùn)行時間比較如圖3。

圖3 不同算法的性能測試比較

從圖3所示結(jié)果中我們可以看出，在相同數(shù)據(jù)集的情況下，選擇不同事務(wù)數(shù)據(jù)量的情況下，改進(jìn)的加權(quán)矩陣Apriori算法的性能比較傳統(tǒng)的Apriori算法有著大幅度的提升，同時相對傳統(tǒng)的基于矩陣的Apriori算法也有一定程度的提高，并且在事務(wù)量逐漸增大的情況下，改進(jìn)的算法運(yùn)行效果的提升越來越明顯。

4 結(jié)語

本文研究了多源安全日志的關(guān)聯(lián)分析方法，首先介紹了多源安全日志的基本概念和常見關(guān)聯(lián)分析方法，研究了基于數(shù)據(jù)挖掘的日志分析方法，針對傳統(tǒng)Apriori算法在運(yùn)行過程中效率低下的缺陷，提出了一種基于Apriori矩陣結(jié)合權(quán)重向量的改進(jìn)方法，并通過與傳統(tǒng)Apriori算法、傳統(tǒng)矩陣Apriori算法的對比實(shí)驗(yàn)分析，結(jié)果證明了本文提出的改進(jìn)算法的有效性，為多源安全日志關(guān)聯(lián)分析方法的進(jìn)一步研究提供了可靠依據(jù)。