面向網(wǎng)絡攻擊建模的分布式過程挖掘與圖分割方法

劉貞宇，陳羽中，郭 昆，張毓東

(福州大學 數(shù)學與計算機科學學院，福州 350116)

(福州大學 福建省網(wǎng)絡計算與智能信息處理重點實驗室，福州 350116)E-mail：yzchen@fzu.edu.cn

1 引 言

在現(xiàn)今網(wǎng)絡安全形勢下，政府和企業(yè)組織為應對入侵者，通常需要部署防火墻、入侵檢測與防御系統(tǒng)等多種網(wǎng)絡安全防護設備，以保護信息資產(chǎn)安全.這些網(wǎng)絡安全防護設備在運行過程中會產(chǎn)生大量信息等級較低的網(wǎng)絡安全警報日志[1]，而網(wǎng)絡攻擊建模技術旨在通過對網(wǎng)絡安全警報日志進行融合及關聯(lián)關系分析，生成網(wǎng)絡攻擊圖，發(fā)現(xiàn)網(wǎng)絡攻擊的特點和規(guī)律，提高應對各種突發(fā)網(wǎng)絡攻擊事件的能力.

現(xiàn)有的網(wǎng)絡攻擊建模算法，主要基于警報關聯(lián)或聚類兩類方法.警報關聯(lián)方法的主要思想是將設備的日志記錄聚合，形成信息層級高的元警報，再通過相似度計算等方式將元警報互相關聯(lián)，構建攻擊模型.早期基于警報關聯(lián)的網(wǎng)絡攻擊建模算法依賴人工輸入先驗數(shù)據(jù)，當日志規(guī)模增大時，難以生成攻擊模型.聚類算法則通過聚類規(guī)則，自動關聯(lián)警報并保存在相應的數(shù)據(jù)結構中(如樹結構或圖結構)，無需人工輸入先驗數(shù)據(jù)，但存在生成的網(wǎng)絡攻擊圖完備性不足的問題[2].近年的一些研究工作將過程挖掘方法應用到網(wǎng)絡攻擊建模中.過程挖掘方法依據(jù)日志中記錄的實例執(zhí)行信息構建工作流模型，主要用于過程分析.過程挖掘方法能夠有效挖掘網(wǎng)絡安全警報日志中包含的具有規(guī)律性的攻擊模式.然而現(xiàn)有的研究工作為了保證攻擊模型的完備性，所建立的網(wǎng)絡攻擊圖包含大量結點和邊，雖然能夠覆蓋網(wǎng)絡入侵者的攻擊行為，但是過于復雜的網(wǎng)絡攻擊圖幾乎無法進行人工分析[3，4]，而人工分析是目前抵御網(wǎng)絡攻擊的關鍵步驟.雖然有一些研究工作會進行模型簡化或分割，但是存在效率低下、丟失攻擊圖部分信息的問題.此外，在過程挖掘領域，針對海量數(shù)據(jù)處理的相關研究比較少，現(xiàn)有研究主要對原始數(shù)據(jù)進行合并重復警報、對警報賦予優(yōu)先級等方法減少計算壓力[5，6]，因此有必要引入分布式架構提高對大規(guī)模網(wǎng)絡安全日志的處理能力[7，8].針對現(xiàn)有網(wǎng)絡攻擊建模方法存在的問題，本文提出一種基于啟發(fā)式過程挖掘與圖分割的網(wǎng)絡攻擊建模方法，主要工作如下：

1)提出了一種基于過程挖掘的攻擊圖生成方法(HPMA，Heuristic ProcessMining for AttackModeling)，基于過程挖掘方法對網(wǎng)絡安全警報日志進行融合，分析網(wǎng)絡安全警報日志間的順序依賴關系和短循環(huán)關系，檢測每一個網(wǎng)絡攻擊行為的前驅和后繼行為、各個事件中隱含的XOR/AND關系，從而獲取各個攻擊行為間的邏輯關系，生成網(wǎng)絡攻擊圖.該方法能夠有效挖掘網(wǎng)絡安全警報日志的關聯(lián)關系，反映入侵者的攻擊行為和攻擊策略.

2)提出了一種針對復雜網(wǎng)絡攻擊圖的攻擊圖分割方法(HGSA，Heuristic GraphSegmentation for AttackModeling).該方法首先尋找網(wǎng)絡攻擊圖的分支結點，從分支結點出發(fā)構造網(wǎng)絡攻擊子圖，再根據(jù)所分割的網(wǎng)絡攻擊圖的結構，對生成的網(wǎng)絡攻擊子圖進行補全.該方法在保留網(wǎng)絡攻擊圖的結構信息的同時，降低了網(wǎng)絡攻擊圖的復雜度.

3)在上述方法基礎上，提出了基于MapReduce的分布式攻擊圖生成方法(HPMAoMR，HPMAoverMapReduce)以及基于Spark GraphX圖計算模型的分布式攻擊圖分割方法(HGSAoSG，HGSA over Spark GraphX)，能夠有效解決大規(guī)模網(wǎng)絡安全警報日志的融合分析問題.

2 相關工作

2.1 網(wǎng)絡攻擊圖生成

網(wǎng)絡攻擊建模旨在挖掘網(wǎng)絡安全警報日志間的關聯(lián)關系，并生成網(wǎng)絡攻擊圖.現(xiàn)有的研究工作主要基于警報關聯(lián)、聚類以及過程挖掘等方法[9].

警報關聯(lián)是網(wǎng)絡攻擊建模的核心方法之一，旨在關聯(lián)構成攻擊步驟的低級別網(wǎng)絡安全日志警報，融合生成高級別的網(wǎng)絡安全警報(又稱元警報或超警報).Lee[10]等人提出了一種基于警報特征相似性的警報關聯(lián)算法.該方法過濾并聚合冗余警報，通過警報相似度確定是否將兩個警報關聯(lián)到元警報.Ning[11]提出了一種基于攻擊行為的前因和后果分析的警報關聯(lián)算法.該算法需要人工定義幾種類型攻擊的前因和后果，無法適用于大規(guī)模的網(wǎng)絡場景.上述研究工作僅實現(xiàn)網(wǎng)絡安全警報日志的關聯(lián)，并未對關聯(lián)結果做進一步分析與抽象.

近年來，一些研究工作從關聯(lián)的網(wǎng)絡安全警報日志中提取入侵者的攻擊模式，從而構建網(wǎng)絡攻擊圖.Ahmadinejad等[12]提出一種二級混合模型的網(wǎng)絡攻擊建模算法，首先基于前因和后果的方法關聯(lián)警報，之后使用相似度聚類將未關聯(lián)的剩余警報關聯(lián)起來.Sadoddin等[13]通過FSP-Growth挖掘警報的頻繁模式來關聯(lián)警報.Lagzian等[14，15]則根據(jù)IP和攻擊方式將警報聚合到圖中，然后應用Bit-AssocRule算法挖掘圖中的頻繁模式，實現(xiàn)警報間的關聯(lián).上述方法能夠提取入侵者的攻擊模式，但是融合層級較低，難以抽象出信息層級更高的網(wǎng)絡攻擊模型.

聚類是網(wǎng)絡攻擊建模廣泛采用的另一類方法.Spathoulas等[15]利用攻擊警報特征的相似性對警報進行聚類，建立攻擊模型.Siraj等[16]采用基于PCA和期望最大化聚類算法對警報進行聚類，構建網(wǎng)絡攻擊圖.Alvarenga等[17]采用自頂向下的層次聚類算法對警報進行聚類，得到網(wǎng)絡攻擊圖.上述基于聚類的網(wǎng)絡攻擊建模算法能夠提取入侵者的攻擊模式，但難以全面描述網(wǎng)絡攻擊的全過程，且存在所生成的網(wǎng)絡攻擊圖過于復雜的問題.

過程挖掘方法通過挖掘日志中的實例執(zhí)行記錄以構建工作流模型，能夠在沒有過程模式先驗知識的情況下挖掘工作流.由于入侵者進行網(wǎng)絡攻擊的流程類似工作流，因此一些研究人員將過程挖掘方法應用于網(wǎng)絡攻擊建模.Weijters等[18]提出了一種啟發(fā)式的過程挖掘方法，通過計算各種行為的順序頻次和邏輯規(guī)律，分析攻擊行為之間的依賴關系和邏輯關系.Alvarenga等[9]則將日志按照日期和攻擊目標分組，使用過程挖掘方法從網(wǎng)絡安全警報日志中提取網(wǎng)絡入侵者的攻擊策略信息，建立網(wǎng)絡攻擊圖.上述方法能夠全面描繪網(wǎng)絡攻擊過程，但所生成的網(wǎng)絡攻擊圖仍過于復雜.

2.2 圖分割

為了能夠完備描述安全日志中蘊含的攻擊模式，現(xiàn)有的網(wǎng)絡攻擊建模方法得到的網(wǎng)絡攻擊圖過于復雜.為了提高網(wǎng)絡攻擊圖的可讀性，需要利用圖分割方法對網(wǎng)絡攻擊圖進行處理.現(xiàn)有的圖分割方法主要分為近似解算法和精確解算法兩大類.近似解算法主要基于啟發(fā)式算法，如線性規(guī)劃、模擬退火算法、遺傳算法、蟻群算法、粒子群算法、譜聚類算法、K-L算法等.現(xiàn)有的圖分割算法主要用于復雜網(wǎng)絡分析、VLSI電路設計、并行計算等研究領域.但對于基于有向圖，前后結點聯(lián)系緊密的攻擊圖分割上并不適用.本文則提出一種基于攻擊圖幾何性質的分割算法，對攻擊圖分割有著良好的效果.

3 預備知識

過程挖掘技術能夠在沒有過程模式先驗知識的情況下挖掘工作流.過程挖掘從依賴關系挖掘開始.設T為一次流程執(zhí)行案例(Case)，A和B為該案例過程中的兩個事件(Event)，又稱實例.

定義1.依賴關系.在過程P中，如果每一個從事件Ai到結束事件的有向路徑中都包含Aj，且Ai到Aj的路徑上不存在其他事件，則Aj依賴于Ai.

定義2.依賴值(Dependency Score).依賴值表示A和B之間存在依賴關系的置信度，記為A?wB.設W為案例T上的日志，A,B∈T，事件B的記錄在A之后，記為A>wB，則:

(1)

其中|A>wB|表示A>wB在日志W(wǎng)中的出現(xiàn)次數(shù).A?wB在-1到1之間取值.若出現(xiàn)負值，則表示可能存在相反關系B?wA.A與B之間的依賴關系是否存在可以通過公式(1)計算其置信度.比如，事件A后發(fā)生了事件B在日志中出現(xiàn)了55次，A?wB=55/56=0.982，則基本能確信其A與B存在著依賴關系.若存在某個噪聲數(shù)據(jù)，使得B>wA出現(xiàn)了一次，則根據(jù)公式(1)計算可得A?wB=54/57=0.947.幾乎不影響置信度的計算結果.

在挖掘過程中，有可能出現(xiàn)同一個實例必須重復執(zhí)行多次的情況.這種情況在流程圖中稱為短循環(huán).較長的循環(huán)可以作為依賴關系用公式(1)有效挖掘.但是長度為1(如ABBBBBC)則需要通過公式(2)計算挖掘：

設W為事件T上的日志，A,B∈T，則：

(2)

其中|A>wA|為T中A>wA出現(xiàn)的次數(shù).

除了依賴關系和短循環(huán)關系外，過程挖掘算法還需要挖掘事件中的邏輯關系，如XOR/AND關系.例如，設在日志w中，A之后可能執(zhí)行B，也可能執(zhí)行C，則B和C存在AND關系；若B和C不會同時執(zhí)行，則B和C為XOR關系.挖掘這兩種邏輯關系，需要在流程執(zhí)行的過程中，通過A?wB∧C關系對其進行判斷:

(3)

若B和C為AND關系，則B和C在案例中往往同時出現(xiàn)，以BC的形式存在，A?wB∧C的值會接近1.若其為XOR關系，則B和C幾乎不會同時出現(xiàn)在同一個案例中，A?wB∧C的值接近0.通常，當A?wB∧C<0.1時即判斷B和C為XOR關系[19].

4 網(wǎng)絡攻擊建模

4.1 算法框架

本文提出的網(wǎng)絡攻擊建模方法主要包括網(wǎng)絡安全日志預處理、網(wǎng)絡攻擊圖生成、網(wǎng)絡攻擊圖分割三個步驟.

網(wǎng)絡安全日志預處理：對原始網(wǎng)絡安全日志進行數(shù)據(jù)清洗、格式轉換等操作，去除噪聲與冗余，對日志數(shù)據(jù)進行分組和聚合，轉換為過程挖掘算法所需數(shù)據(jù)格式.

網(wǎng)絡攻擊圖生成：使用啟發(fā)式過程挖掘算法，將日志警報數(shù)據(jù)融合為入侵者的攻擊模式數(shù)據(jù)，建立網(wǎng)絡攻擊圖.

網(wǎng)絡攻擊圖分割：通過圖分割算法，在保留原網(wǎng)絡攻擊圖的攻擊步驟信息的同時，將復雜度高的網(wǎng)絡攻擊圖分割成復雜度低，可讀性強的網(wǎng)絡攻擊子圖.

4.2 網(wǎng)絡攻擊圖生成

使用啟發(fā)式過程挖掘算法從日志中挖掘初始網(wǎng)絡攻擊圖.啟發(fā)式過程挖掘算法[19]通過引入頻率計算解決了傳統(tǒng)過程挖掘算法無法處理噪聲數(shù)據(jù)的問題，在輸入日志數(shù)量較大時有著優(yōu)異的挖掘效果.由于網(wǎng)絡攻擊入侵者的攻擊策略與工作流特征十分相似，因此可以將過程挖掘技術應用在攻擊圖建模方面[9].攻擊圖生成過程分為如下幾個步驟：

首先，對原始IDS報警日志數(shù)據(jù)聚合.將警報日志按照攻擊源IP和時間戳進行分組聚合.然后將其轉換為啟發(fā)式過程挖掘算法所需的XES日志形式作為輸入數(shù)據(jù).

然后，算法讀取輸入數(shù)據(jù)，通過攻擊事件出現(xiàn)順序頻次計算依賴值，依賴值是判斷攻擊事件之間的依賴關系或者邏輯關系是否存在的指標.然后算法會構建一個依賴頻率表，通過短循環(huán)計算公式計算出短循環(huán)關系.

隨后，算法通過計算各個事件和依賴間的頻率關系，計算挖掘出攻擊事件之間的XOR/AND關系，完善攻擊策略圖中各個行為間的邏輯關系.補充相應的信息.最后輸出網(wǎng)絡攻擊圖.

4.3 網(wǎng)絡攻擊圖分割

由網(wǎng)絡安全管理人員對網(wǎng)絡攻擊情況進行人工分析是確保網(wǎng)絡系統(tǒng)安全的重要手段[16].然而由于海量網(wǎng)絡安全日志中包含了不同入侵者的大量行為記錄，網(wǎng)絡攻擊圖中表示入侵者行為的結點數(shù)目十分巨大，入侵行為間的先后依賴關系也十分復雜，使得網(wǎng)絡攻擊圖中邊的數(shù)量也十分龐大，導致網(wǎng)絡攻擊圖過于復雜，不利于網(wǎng)絡管理人員直觀地分析當前的網(wǎng)絡攻擊狀態(tài).針對上述問題，本文提出了一種針對復雜網(wǎng)絡攻擊圖的攻擊圖分割算法，將復雜的網(wǎng)絡攻擊圖劃分為多個能夠直觀反映入侵者攻擊步驟的網(wǎng)絡攻擊子圖，以方便網(wǎng)絡安全管理員進行分析.

4.3.1 問題描述

網(wǎng)絡攻擊圖G=(V,E)表示攻擊行為與攻擊行為之間關系，V表示結點集，代表著入侵者的攻擊行為，E表示攻擊圖中的邊集，代表入侵者攻擊行為之間的邏輯關聯(lián)關系，網(wǎng)絡攻擊圖分割問題定義如下：

定義3.網(wǎng)絡攻擊圖分割.網(wǎng)絡攻擊圖分割.給定網(wǎng)絡攻擊圖G，求G的一個網(wǎng)絡攻擊圖分割P，P={G1,G2,…,Gn},其中Gi表示網(wǎng)絡攻擊圖的某一個子圖.

4.3.2 算法概述

攻擊圖分割的基本思想如下：首先對原始網(wǎng)絡攻擊圖進行遍歷，然后以分支為基準，將各個分支遍歷到的結點和邊保存為新的攻擊圖.因此對攻擊圖的分割不會影響原始攻擊圖結構.算法的主要步驟如下：

步驟1.計算待分割的網(wǎng)絡攻擊圖G的復雜度，若G不是復雜網(wǎng)絡攻擊圖，則輸出G后結束；否則將G放入隊列Qs中；

步驟2.遍歷隊列Qs，對隊列中的每個待分割的網(wǎng)絡攻擊圖，自頂向下尋找分支點Vs；

步驟3.遍歷到分支點Vs，則以Vs作為分割的起始點，去除網(wǎng)絡攻擊圖中的獨立子圖，然后將網(wǎng)絡攻擊圖剩余部分中以Vs為起始點的有向邊加入到隊列Qe中；

步驟4.遍歷隊列Qe，對遍歷到的有向邊e使用深度優(yōu)先算法遍歷并生成e的后繼子圖，并將Vs標記為所生成的后繼子圖的起始點.對每個后繼子圖，計算其復雜度，如果不是復雜子圖，則將后繼子圖加入隊列Qoutput中，Qoutput用于存放分割得到的網(wǎng)絡攻擊子圖；否則將其加入到存放待分割的網(wǎng)絡攻擊圖的隊列Qs中；

步驟5.判斷隊列Qs是否為空，若非空，回到步驟2；

步驟6.遍歷Qoutput中的網(wǎng)絡攻擊子圖，對其進行分支信息補全后輸出，即為網(wǎng)絡攻擊圖G分割所得的網(wǎng)絡攻擊子圖.

4.3.3 網(wǎng)絡攻擊圖復雜度判定

對網(wǎng)絡攻擊圖進行分割的目的是降低其視覺上的復雜度，增加其可讀性，但視覺上的復雜性難以直接衡量，因此需要定義網(wǎng)絡攻擊圖復雜度的評估方法，用于判斷一個網(wǎng)絡攻擊圖是否需要進行分割或分割后的子圖是否已經(jīng)具有可讀性，可以輸出給網(wǎng)絡管理員進行分析.本文攻擊圖分割方法所采用的網(wǎng)絡子圖復雜度判定規(guī)則如下：

(4)

其中|V|為攻擊圖G結點的個數(shù).若網(wǎng)絡攻擊圖的結點數(shù)滿足|V|N2, 則網(wǎng)絡攻擊圖G為復雜網(wǎng)絡攻擊圖，需要進行子圖分割；若網(wǎng)絡攻擊圖的結點數(shù)滿足N1<|V|

(5)

參數(shù)N1和N2根據(jù)文獻[9]確定：N1=15，N2=31.

4.3.4 獨立子圖分割

定義4.后繼子圖.從網(wǎng)絡攻擊圖G中的某個結點v經(jīng)以v為起始結點的某條有向邊e出發(fā)，遍歷到的點與邊所構成的流程圖，為v的一個后繼子圖，記為Gsucc(v,e).

如圖1(a)所示，實線部分為點v的一個后繼子圖.在網(wǎng)絡攻擊圖G中，結點v表示入侵者的某個攻擊行為，其后繼子圖則代表入侵者執(zhí)行某個攻擊行為后可能進行的后續(xù)攻擊行為.

定義5.分支點.給定網(wǎng)絡攻擊圖G中的某個結點v，若結點v的出度大于1，則v為網(wǎng)絡攻擊圖G中某個入侵行為的分支點.

攻擊流程的分支點代表攻擊者在執(zhí)行攻擊計劃的過程中，在執(zhí)行完此攻擊步驟后，存在多種不同的可執(zhí)行攻擊方案.圖分割算法以分支點為基礎分割攻擊圖，可以將不同的攻擊方案分割成獨立子圖，使得管理員對攻擊者的各個攻擊方案有較為清晰的把控.算法自頂向下找到網(wǎng)絡攻擊圖的分支點后，首先將易于分割的部分分離出來.

定義6.獨立子圖.給定v的一個后繼子圖，若該后繼子圖內的全部有向邊e的端點屬于后繼子圖或為v本身，則該后繼子圖是以結點v為起始點的獨立子圖.

如圖1(b)所示，實線部分為結點v的一個獨立子圖，首先從攻擊圖中獲取以v為起始點的有向邊，然后從這些有向邊開始遍歷v的各個后繼子圖，并且判斷遍歷到的每一個子圖是否為v的獨立子圖.如果遍歷到的圖是獨立子圖，則將該子圖從原圖中分割出來，作為一次分割結果入隊待分割隊列中，后續(xù)確認是否需要進一步分割.

圖1 結點v的后繼子圖與獨立子圖

獨立子圖代表著這個子圖內所有的攻擊行為都是且僅是分支點代表的攻擊行為的后續(xù)攻擊方案.當網(wǎng)絡管理員發(fā)現(xiàn)符合獨立子圖內的攻擊順序被執(zhí)行，就可以立即確認入侵者之前的攻擊行為.同時，由于獨立子圖只是分支點V的后繼子圖，因此不需要對分割出的獨立子圖進行補全，能夠提高算法的計算效率.

4.3.5 剩余子圖分割

將獨立子圖分離后，算法需對去除獨立子圖之后剩余的后繼子圖作進一步分割.算法選取從以分支點為起始點的有向邊出發(fā)，依次遍歷分支點的各個后繼子圖，并且生成子圖.具體步驟如下：

步驟1.遍歷隊列Qe，對遍歷到的有向邊e，以有向邊e為起始，使用廣度優(yōu)先遍歷算法遍歷e的后繼結點和對應的有向邊，并且標記遍歷過的結點和邊；

步驟2.對遍歷到的每個結點，判斷是否存在遠距離環(huán)，若存在遠距離環(huán)，則對其進行去除遠距離環(huán)的操作，最后由遍歷到的結點和邊生成后繼子圖Ge.

以圖2(a)的網(wǎng)絡攻擊圖為例，結點v為分支點，對網(wǎng)絡攻擊圖的分割過程如圖2(b)-圖2(d)所示.

圖2 以v為起始點將后繼圖分割成三個子圖

如圖2(b)，首先從v為起始點的有向邊e1出發(fā)以深度優(yōu)先遍歷后繼子圖.將遍歷到的結點和邊連同分支點Vs一起保存為一個新的子圖G1.同理，分別從e2、e3出發(fā)遍歷v的后繼子圖，并將結果保存為新的子圖G2和G3，如圖2(c)、圖2(d)所示.

子圖表示著入侵者某個攻擊階段的攻擊策略.當網(wǎng)絡管理員聚焦在某個攻擊行為時，子圖中的結點表示著在該攻擊行為前后有可能出現(xiàn)的攻擊行為.不屬于相同子圖的結點，其對應的攻擊行為不會相互在前后出現(xiàn)，因此網(wǎng)絡管理員可以集中在這個子圖中研究當前攻擊行為的依賴關系和邏輯關系.

4.3.6 去除遠距離環(huán)

定義7.遠距離環(huán).自結點v出發(fā)，經(jīng)過一個或多個結點可返回結點v.則稱所經(jīng)過結點構成的路徑為v的一個遠距離環(huán).

遠距離環(huán)是過程挖掘算法中由于存在遠距離依賴因而產(chǎn)生的環(huán).圖3(a)顯示了圖2(b)中網(wǎng)絡攻擊子圖G1的部分子圖，從圖中可以看出，算法執(zhí)行到以v為分支點進一步分割圖模型時，遍歷算法通過圖中實線路徑可回到v，即實線部分組成了一個遠距離環(huán).

圖3 遠距離環(huán)

遠距離環(huán)會導致許多不必要的重復計算，增加圖分割算法的復雜度，因此在分割網(wǎng)絡攻擊圖的過程中需要對遠距離環(huán)進行處理.按照構成遠距離環(huán)的結點的不同，對遠距離環(huán)的處理可分為以下兩種情況.

Case1：如圖3，算法從結點v對向下遍歷到的結點v1，若v1?G1，且v1≠v，則認為結點v1為圖外結點(如圖3(a)).遍歷退回前一個結點t，并且v1和遍歷到的指向v1的邊不加入后繼子圖G1中，得到的子圖G1，如圖3(b)中實線部分所示；

Case2：若遍歷到一條指向分支點v的邊e(如圖3(c))，退回前一次訪問的結點t，將以v為終點的有向邊加入后繼子圖G1，則得到的子圖即為圖3(c)所示.

4.3.7 生成子圖補全

當分割隊列的圖全部分割完成后，為了讓網(wǎng)絡安全管理員便于對分割后的網(wǎng)絡攻擊圖進行分析，需要對分割結果進行信息補全.需要補全的是圖內結點的前驅結點的信息，這些前驅結點代表攻擊模型圖中入侵者行為的前驅步驟，但是在遍歷生成子圖的過程中，遍歷算法沿著有向邊的方向前進，部分結點的前驅結點無法遍歷到，未納入到子圖中.為了讓管理員能夠更方便地了解入侵者行為的前后關系，需要將這些結點納入到子圖中.

此外，這些前驅結點同時存在于其他子圖中，補全這些結點的信息可以實現(xiàn)不同的子圖相互關聯(lián).生成子圖補全步驟如下：

步驟1.遍歷待補全的子圖，對遍歷到的結點v，從攻擊圖G中尋找指向v的邊的集合Ev.

步驟2.遍歷Ev，判斷Ev中的有向邊e是否屬于待補全圖.若e不屬于待補全圖，則將e保存到待補全圖中.

如圖4所示，對圖2(b)所示的分割子圖G1進行信息補全，新加入的點和邊在圖4中加粗標出.

圖4 信息補全樣例

4.3.8 算法描述

算法主要流程的偽代碼如下所示：

算法1.Complex Graph Segmentation Algorithm

1.function AttackGraphGenerater(AttackGraphG)

2.ifComplexDegree(G)then

3.Qs.push(G)

4.while(Qs)do

5.G←Qs.pop(G)

6. /* Looking for branch points */

7. VS← SearchSplitVertex(G)

8. /* Judge independent subgraph */

9.ifIsDependentGraph(VS)then

10. /* Independent subgraph segmentation */

11. DependGraphGenerater(VS)

12.endif

13. /* saves the edge to be traversed */

14. Qe.push(getSuccEdge(VS))

15.while(Qe)do

16. /* Looking for successor subgraphs */

17. Ge=getSuccGraph(Qe.pop())

18.ifComplexDegree(Ge)then

19.Qs.push(Ge)

20. /* saves the output graph */

21.else

22.QOutput.push(Ge))

23.endif

24. end while

25. end while

26.while(QOutput)do

27. /* subgraph Completion */

28. G=InfoComplete(QOutput.pop())

29.Output(G)

30. end while

31.else

32.Output(G)

33.endif

4.4 算法復雜度分析

過程挖掘算法的時間復雜度和待挖掘的攻擊步驟數(shù)量k相關，時間復雜度為O(k2)[19].

圖分割算法的時間復雜度如下：

步驟1.判斷攻擊圖的復雜度需計算攻擊圖包含的點和邊的數(shù)量，因此所需時間為O(m).其中m為攻擊圖結點的數(shù)量.

步驟2.尋找出所有分支點的過程相當于遍歷一遍攻擊圖的過程，因此所需時間仍為O(m).

步驟3.在去除獨立子圖和分割圖模型的過程中會多次對分支結點進行遍歷，遍歷的次數(shù)取決于分支點的個數(shù)x和分支的邊數(shù)n.因此一階段所需時間為O(xn).

步驟4.分割剩余子圖的所需的時間仍為O(xn).

步驟5.此步驟每個子圖信息補全所需的時間和所需要補全的結點個數(shù)有關.因此所需總時間為O(nm).

綜上此算法所需時間為O(n(m+x)).運行時間和分割圖的結構有很大關系.

考慮算法的空間復雜度，在計算的過程中，需要額外的內存用于保存分割出的子圖，所需的空間大小取決于圖的結點數(shù)量m和邊的數(shù)量n.故算法的空間復雜度為S(m+n).

5 分布式網(wǎng)絡攻擊建模

5.1 分布式攻擊圖生成

啟發(fā)式過程挖掘算法用于網(wǎng)絡攻擊圖挖掘時，主要步驟是計算安全日志中攻擊事件之間的關聯(lián)關系，然后將各個節(jié)點的計算結果進行聚合和拼接，得到網(wǎng)絡攻擊圖.分布式攻擊圖生成算法包括SecurityCaseRelationCreation、AttackRelationComputation、EventClassification以及EventClassification四個模塊.

SecurityCaseRelationCreation：該模塊的主要目標是創(chuàng)建事件之間的關系.從HDFS讀取原始安全警報后，SecurityXesLogCaseMapper識別出日志記錄的字段信息，如SourseIP流量特征簽名等信息.然后根據(jù)SourseIP字段將原始日志分片為多個子集，將分片后的子集作為挖掘算法中的案例.將SourseIP設置為分片關鍵字，將流量特征Signature設置為挖掘算法中的實例，即攻擊圖中的攻擊行為.同時，設置Timestamp為關鍵字進行二次排序.然后將結果輸入到AttackCaseReducer中，算法循環(huán)遍歷每個案例，依次計算案例中的順序關系、循環(huán)關系和邏輯關系，然后創(chuàng)建并輸出案例中攻擊步驟之間的關系數(shù)據(jù).例如，XES日志會根據(jù)SourceIP字段分成多個SubLog.設A和B是同一案例下的兩個攻擊事件實例，之后在reduce任務中，AttackCaseReducer會通過B在A后出現(xiàn)的頻率，計算兩個事件之間的順序關系頻數(shù)，輸出|A>wB|，即攻擊事件B在攻擊事件A后發(fā)生的次數(shù).

AttackRelationComputation：該模塊僅執(zhí)行Reduce任務RelationReducer.RelationReducer的輸入是上一階段中AttackCaseReducer的輸出.RelationReducer將攻擊行為之間的關聯(lián)關系聚合，同時，通過各種關系數(shù)據(jù)計算事件之間的依賴值和短循環(huán)關系，并計算事件之間的邏輯關系.同時在運算過程中，算法會將案例中存在的每一種關系(包括順序關系、分支關系、短循環(huán)關系等)都聚合起來，然后將聚合后的關系數(shù)據(jù)輸出提供下一個模塊進行計算.假設輸入的關系數(shù)據(jù)中存在a與b，a與c的順序關系(a?b、a?c)，這些關系會按照關系數(shù)據(jù)中的左值(即關系中的前驅結點)進行聚合，然后將結果輸出.

AttackClassification：在該模塊中，ScoredEventMapper會根據(jù)攻擊行為關系對中的左值(例如順序關系中的前驅)將數(shù)據(jù)進行進一步分片.然后通過ScoredEventReducer構建前后結點，輸出事件結點作為key，結點的前驅，后繼和以及他們之間的邊(即關系)三種數(shù)據(jù)作為value輸出.

CausalMatrixGeneration：該模塊主要是拼接匯總挖掘出的關系.在前一模塊輸出的事件結點作為key輸入至CausalMatrixMapper中，Mapper會通過key對應的結點找到關系數(shù)據(jù)中相應的前驅結點和后繼結點，構建對應關系矩陣.最后在CausalMatrixReducer將各個計算節(jié)點的輸出結果匯總到一個實例中，輸出一個完整的攻擊圖.

5.2 分布式攻擊圖分割

使用啟發(fā)式過程挖掘算法挖掘出的攻擊圖，結點和邊的數(shù)量往往很大，所生成的攻擊圖結構十分復雜，需要對攻擊圖進行分割，以便于分析攻擊行為.本文提出的攻擊流程模型使用有向圖來表示入侵者的攻擊策略，而Apache Spark的GraphX組件十分適合處理圖數(shù)據(jù)處理.因此，可將Spark與前一階段的MapReduce攻擊圖發(fā)現(xiàn)相結合，利用Spark GraphX組件進行分布式攻擊圖分割.由于Spark使用RDD作為數(shù)據(jù)抽象，因此需要從HDFS中讀取攻擊圖并且保存在RDD中.讀取出圖的數(shù)據(jù)后，將圖的信息保存在如下三個RDD上：VertexTable、EdgeTable和RoutingTable，其中VertexTable存儲結點信息，EdgeTable存儲邊的信息，RoutingTable存儲結點在集群中的位置.

在對單個復雜圖進行分割時，若圖的復雜度并不是非常高(例如只有數(shù)十結點)，通常將分割任務分配在一個節(jié)點上進行.使得多個節(jié)點可以同時進行多個圖分割任務.若圖的結點數(shù)量巨大，則需要調用Graph.partitionBy對圖重新分片，將復雜圖分片到多個節(jié)點上，再進行分割任務.

6 實驗與分析

6.1 實驗環(huán)境與數(shù)據(jù)集

6.1.1 實驗環(huán)境

本節(jié)通過實驗對本文提出的攻擊圖生成算法與攻擊圖分割算法進行分析.算法實現(xiàn)語言為Java，基于Hadoop和Spark分布式框架，實驗環(huán)境設置如表1所示.

表1 實驗環(huán)境配置

實驗數(shù)據(jù)集為歐洲某國的ISP提供商在2016年3月到8月之間，產(chǎn)生自IDS/IPS設備的網(wǎng)絡攻擊數(shù)據(jù).實驗數(shù)據(jù)集中的每條日志數(shù)據(jù)只記錄行為信息，不描述攻擊者使用的攻擊策略，所包含的主要字段如表2所示.此外，為便于研究者們進行算法模型驗證，6月與7月的網(wǎng)絡攻擊數(shù)據(jù)，按照常見的攻擊模式對攻擊進行了詳細的分類，作為驗證集提供.

表2 字段說明

由于實驗數(shù)據(jù)的大小超過11 GB，因此實驗選擇7月某一周的數(shù)據(jù)作為輸入數(shù)據(jù)，在對數(shù)據(jù)進行預處理后，將數(shù)據(jù)按天分組，以SourseIP字段作為聚類關鍵字段分為若干組作為輸入案例(Case)，并將公式(4)中的γ設為0.3.在單節(jié)點實驗中，過程挖掘工具選用了ProM框架.ProM框架是目前最流行的過程挖掘工具之一.ProM框架提供了可擴展日志流輸入支持，因此對原始數(shù)據(jù)做預處理后，將日志轉換成ProM支持的XES(eXtensible Event Stream)日志格式，以天為單位劃分，分別導入到ProM框架中進行過程挖掘.

6.1.2 對比算法與評估指標

本文采用文獻[20]的Alpha算法與文獻[9]的攻擊模型發(fā)現(xiàn)算法(MDA，Model Discovery Algorithm)作為HPMA的對比算法，并采用Precision、Recall與F1-score作為性能評價指標.

6.2 實驗分析

6.2.1 過程挖掘結果分析

將7月26日-7月30日的攻擊日志分成5組分別進行實驗，計算每日的Precision、Recall以及F1-score，并求出平均值，結果如圖5所示.

圖5 Recall、Precision和F1-score比較

由圖5可知，基于啟發(fā)式過程挖掘算法的召回率、準確率、F1-score分別達到91.3%、85.7%以及88.8%，均優(yōu)于對比算法.所生成的網(wǎng)絡攻擊圖基本涵蓋了發(fā)生的攻擊序列，說明啟發(fā)式過程挖掘算法能夠有效地從安全日志中挖掘出入侵者的攻擊策略以及可能使用的攻擊步驟.這是由于過程挖掘算法在挖掘過程中能夠更好地消除噪聲數(shù)據(jù)的影響.

6.2.2 網(wǎng)絡攻擊圖分割結果分析

由于原始數(shù)據(jù)記錄的規(guī)模十分龐大，因此盡管將數(shù)據(jù)按照天數(shù)分開，挖掘結果仍然十分復雜.以2016年7月31日的結果為例.當天日志一共323120條記錄，以SourseIP作為關鍵字分為了4367個案例，平均實例數(shù)量大約為79個.以當天的日志輸入后，輸出的結果為一個由34個結點，109條邊組成的復雜攻擊圖.本節(jié)對網(wǎng)絡攻擊圖分割結果進行分析.以根據(jù)7月第4周的數(shù)據(jù)生成的網(wǎng)絡攻擊圖為例，攻擊圖分割方法將該初始網(wǎng)絡攻擊圖分割為14個網(wǎng)絡攻擊子圖.網(wǎng)絡攻擊子圖構成的結點和邊數(shù)如表3所示.

表3 分割后的網(wǎng)絡攻擊子圖

從表3可以看出，經(jīng)過分割算法分割，原網(wǎng)絡攻擊圖被分成了13個非復雜網(wǎng)絡攻擊圖和一個序號為11的復雜網(wǎng)絡攻擊圖，對序號為11的復雜網(wǎng)絡攻擊子圖進行回溯可知，該子圖是由于圖分割算法在進行信息補全操作后，從非復雜圖轉換為復雜圖.接下來對實驗結果樣例進行分析，驗證分割結果圖的有效性.

圖6是序號6的網(wǎng)絡攻擊子圖，從圖6可以看出，進行了sshScan掃描攻擊的入侵者，往后一般會選擇四種攻擊行為：Impossible Flags(利用無效tcp頭部字段的標志位濫用，一種DOS攻擊)，Nmap掃描，惡意SMB探針，惡意PHP程序.其中，前三種攻擊行為有可能互為后續(xù)攻擊.使用SMB探針后，利用windows系統(tǒng)漏洞進行MS SQL Hello Buffer Overflow攻擊(利用MS SQL漏洞的一種攻擊)或者引發(fā)windows即插即用異常請求.另一方面，若入侵者在sshScan掃描后，使用了PHP惡意程序，入侵者會使用PHP代碼注入就行進一步攻擊.從上述例子可以看出，所提出的算法輸出的攻擊子圖顯然可以清楚地反映入侵者的攻擊模式.

圖6 序號6的攻擊子圖的攻擊步驟

6.2.3 時間性能分析

A.攻擊圖生成算法時間性能分析

本節(jié)對比Alpha算法、基于Alpha算法的分布式過程挖掘算法(AlphaoMR)、HPMA算法、分布式HPMA算法(HPMAoMR)的時間性能.實驗取7月份兩周的日志數(shù)據(jù)，分別選擇11.4G、8G、4G以及1G的日志數(shù)據(jù)作為輸入，并同時對比單機運行和集群運行的結果.每次實驗重復運行三次，取平均值進行對比.實驗結果如圖7所示.

圖7 數(shù)據(jù)規(guī)模對攻擊圖生成算法運行時間的影響

從圖7可以看出，當日志數(shù)據(jù)規(guī)模僅為1GB時，分布式挖掘算法的運行時間并沒有很明顯的優(yōu)勢，然而隨著日志數(shù)據(jù)的增大，分布式挖掘算法的優(yōu)勢逐漸明顯，其中分布式Alpha算法的運行時間最短，分布式挖掘算法HPMAoMR的運行時間略長于分布式Alpha算法(AlphaoMR)，但是兩者均明顯優(yōu)于單機版本的HPMA算法和Alpha算法.分布式Alpha算法的運行時間優(yōu)于本文提出的HPMAoMR算法的原因在于，Alpha算法基于W-net進行過程挖掘，由于其缺少對重復任務的挖掘，因此計算量小了許多，較基于啟發(fā)式算法的HPMA的核心步驟更為簡單快速，因此Alpha算法的算法復雜度較低，在運行時間上有一定優(yōu)勢，但是HPMA能夠獲得優(yōu)于ALPHA算法的網(wǎng)路攻擊圖挖掘效果.

接下來固定日志數(shù)據(jù)規(guī)模為11G，通過增減集群節(jié)點數(shù)，對比分析不同節(jié)點數(shù)量對網(wǎng)絡攻擊圖挖掘運行時間的影響.實驗結果如圖8所示，HPMAoMR的運行時間單位為min.當集群節(jié)點數(shù)為2個時，HPMAoMR的運行時間相比單機版本算法減少了39%.當集群節(jié)點數(shù)增加為4個時，運行時間減少了62%.但是當節(jié)點數(shù)增加為8個時，運行時間僅減少了67%.算法從單機到2節(jié)點能夠明顯減少運行時間，是因為兩個節(jié)點同時處理原始數(shù)據(jù)，能夠有效緩解IO壓力.在集群數(shù)量從4個增加到8個時，效果并不十分明顯，這主要是因為在4個節(jié)點數(shù)時已經(jīng)能夠有效地解決IO瓶頸問題，同時在Map過程中，由于節(jié)點數(shù)量變多，數(shù)據(jù)分片數(shù)量變多，節(jié)點相互通訊的時間增加，對算法運行時間也有一定的影響，因此性能提升已經(jīng)不大.

圖8 節(jié)點數(shù)對攻擊圖生成算法與分割算法運行時間的影響

將網(wǎng)絡攻擊圖挖掘算法生成的網(wǎng)絡攻擊圖作為Spark GraphX的輸入，Spark GraphX從HDFS讀取到的攻擊圖的結點數(shù)為276，邊的數(shù)量為1053.同時對比單機環(huán)境與Spark集群下網(wǎng)絡攻擊圖分割算法(HGSA)的運行時間，每次實驗重復運行三次，取平均值進行對比.實驗結果如圖8所示，HGSAoSG的運行時間單位為s.從圖8中可以看出，基于Spark的圖分割算法的運行時間顯著優(yōu)于單機狀態(tài)下的圖分割算法，而Spark集群中節(jié)點數(shù)量的挑戰(zhàn)對結果影響不大，并且對數(shù)百個結點的圖進行分割時，Spark可以接近實時地輸出結果，處理效率較高.

7 總 結

本文提出了一種攻擊圖生成方法，將啟發(fā)式過程挖掘技術用于從網(wǎng)絡攻擊策略模型挖掘.這種方法的主要思想是利用網(wǎng)絡攻擊者攻擊行為和工作流特征的相似性，使用過程挖掘對網(wǎng)絡安全日志進行挖掘.為了驗證生成方法的有效性，本文使用一個攻擊數(shù)據(jù)集進行實驗，實驗結果表明過程挖掘算法能夠有效挖掘出入侵者的攻擊策略.同時，為了解決過程挖掘的輸出攻擊圖的結構復雜的問題，本文提出了一種針對復雜攻擊圖的分割方法.該方法在有效地保存攻擊圖的基礎結構前提下，成功將復雜的攻擊圖分割成多個復雜度低的攻擊子圖，大大增加圖的可讀性.

在上述攻擊圖生成方法的基礎上，提出基于Hadoop和Spark的分布式攻擊圖生成方法，該方法使用Spark GraphX對生成的攻擊圖進行分割，提高分割效率.并通過YARN將MapReduce和Spark整合.解決了過程挖掘算法在單機運行狀態(tài)下數(shù)據(jù)處理能力不足的問題，使得攻擊圖的挖掘效率得到極大提高，減少算法運行時長.并且搭建了一個Hadoop集群對提出的方法進行了實驗，驗證了算法的有效性.此算法能夠使網(wǎng)絡管理員能夠監(jiān)控網(wǎng)絡安全，并使網(wǎng)絡安全管理員能夠獲取更詳細的網(wǎng)絡攻擊信息，從而做出適當?shù)臎Q策.