利用流挖掘和圖挖掘的內網異常檢測方法*

孫 偉，張 羽

1.北京交通大學 計算機與信息技術學院，北京100044

2.中國科學院大學 網絡空間安全學院，北京100049

3.中國科學院 信息工程研究所，北京100093

1 引言

在情報界，越來越多的共識認為，內網惡意人員可能是大多數組織中信息保障最有力的威脅[1-4]。內網異常檢測問題的一種傳統方法是監督學習，其從訓練數據構建數據分類模型。不幸的是，監督學習方法的訓練過程往往耗時且昂貴，并且通常需要大量的平衡訓練數據才能有效。在本文的實驗中，觀察到該問題的實際數據集中不到3%的數據與內網異常（少數類）相關聯；超過97%的數據與非威脅（大多數類）相關聯。因此，根據這種不平衡數據訓練的模型可能在測試數據集上表現不佳。

另一種方法是無監督學習，它可以有效地應用于未標記的數據，即沒有明確地將點識別為異常或非異常的數據。基于圖形的異常檢測（graph-based anomaly detection，GBAD）是無監督學習的一種重要形式[5-7]，但傳統上僅限于靜態有限長度數據集。這限制了其應用于與內網異常相關的流，這些威脅往往具有無限長度和隨時間演變的威脅模式。因此，將GBAD應用于內網異常問題需要一個足夠自適應和高效的模型，以便可以從大量不斷發展的數據構建有效模型。

本文將內網異常檢測作為流挖掘問題進行影射，并提出了一種有效的解決方案，用于應用無監督學習來檢測流中的異常。本文方法將多個GBAD模型組合在一個分類器集合中。該集合旨在提高相對于任何單個模型的分類準確性。隨著惡意代理和非惡意代理的行為隨時間變化，這種進化能力提高了分類器概念普適性。在實驗中，使用基于Unix 的多用戶系統的大型系統調用數據記錄作為測試數據。

本文工作做出了以下貢獻：首先，展示了如何有效地應用流挖掘來檢測內網異常；其次，提出了一種無監督學習算法，可以應對基于GBAD 的變化；然后，通過有效地將兩者結合起來，利用流挖掘和基于圖的挖掘的力量；最后，將本文方法與傳統的無監督學習方法進行比較，并展示其卓越的有效性。

2 相關工作

內網異常檢測工作應用了入侵檢測和外部威脅檢測的思想[8-11]。在本文中，內網異常主要指當前或曾經雇員、承包商或商業伙伴，他們現在或曾經被授予一定權限，并且以給組織的信息或信息系統的保密性、完整性和可用性帶來負面影響的方式，故意過度地訪問組織的網絡、系統或數據。監督學習方法收集包含正常和異常行為記錄的系統調用跟蹤日志[12-15]，從收集的數據中提取n-gram 特征，并使用提取的特征來訓練分類器。文本分類方法將每個系統調用視為詞袋模型中的一個單詞[16]。系統調用的各種屬性，包括參數、對象路徑、返回值和錯誤狀態，已被用作各種監督學習方法中的特征[17-18]。這些監督方法需要大量標記的訓練數據，并且僅適用于靜態的、非演進的流。

過去的工作也探討了內網異常檢測的無監督學習，但僅針對所知的靜態流[19-21]。靜態GBAD方法[5-7，22]將威脅和非威脅數據表示為圖形，并應用無監督學習來檢測異常。GBAD 的最小描述長度（minimum description length，MDL）方法已應用于電子郵件、手機流量、業務流程和網絡犯罪數據集[23-24]。本文的工作建立在GBAD 和MDL 之上，以支持動態、不斷發展的流數據。

流挖掘[25]是一種相對較新的數據挖掘研究類型，適用于連續數據流。在這樣的設置中，監督和無監督學習必須是自適應的，以便處理其特征隨時間變化的數據。有兩種主要的適應方法：增量學習[26]和基于集成的學習[25，27-28]。過去的工作表明，基于集成的方法在兩者中更有效，激勵了本文的方法。

過去使用集合來增強正/負分類的有效性[28-29]。通過維持共同對最終分類進行投票的K模型的集合，可以減少測試集的假陰性，即漏報（false negative，FN）和假陽性，即誤報（false positive，FP）。隨著更好的模型被創建，較差的模型被丟棄以維持大小恰好為K的整體。這有助于整體隨著流的變化特征而發展并且使分類任務易于處理。表1 總結了上述相關工作的比較。文獻[30]提供了更完整的調查。

Table 1 Comparison of related work表1 相關工作比較

3 基于集成的內網異常檢測

與內網異常相關的數據通常在組織和系統操作的多年中累積，因此最佳地表征為無界數據流。這樣的流可以被劃分為一系列離散的塊。例如，每個塊可能包含一周的數據。

圖1 說明了當這樣的流觀察概念漂移時分類器的決策邊界如何變化。圖中的每個圓圈表示數據點，未填充的圓圈表示真陰性（true negative，TN）（即非異常），實心圓圈表示真陽性（true positive，TP）（即異常）。每個塊中的實線表示該塊的決策邊界，而虛線表示前一個塊的決策邊界。

Fig.1 Concept drift in stream data圖1 流數據中的概念漂移

陰影圓圈是那些體現了相對于前一個塊漂移的新概念的圓圈。為了對這些進行適當分類，必須調整決策邊界以考慮到新概念。存在兩種可能的誤解（錯誤檢測）：（1）塊2 的決策邊界相對于塊1 向上移動。結果，一些異常數據被錯誤地分類為非異常，導致FN（漏報）率上升。（2）塊3 的決策邊界相對于塊2向下移動。結果，一些非異常數據被錯誤地分類為異常，導致FP（誤報）率上升。

通常舊的和新的決策邊界可以相交，導致上述兩種情況同時發生在同一塊上。因此，FP和FN計數都可能增加。

這些觀察結果表明，從單個塊或任何有限的塊前綴構建的模型不足以對流中的所有數據進行適當的分類。這促使采用本文的集成方法，該方法使用不斷發展的K模型對數據進行分類。

集成分類程序如圖2所示。首先使用靜態的、受監督的三種GBAD 方法來訓練來自單個塊的模型。GBAD識別塊中的所有規范子結構，每個子結構表示為子圖，選擇其中最優的N個子結構作為最終的規范子結構。為了識別異常，將測試子結構與整體中的每個模型進行比較。每個模型基于其與模型的規范子結構的差異對測試子結構進行分類。一旦所有模型投票，加權多數表決將做出最終的分類決定。通過集成演化來保持分類器中模型數量恰好為K。當每個新塊到達時，從新塊創建K+1模型，并丟棄這些K+1 模型的一個受害者模型。可以通過多種方式選擇丟棄受害者。一種方法是計算在K+1塊上的每個模型的預測誤差并丟棄最差的預測器。這要求最近的塊可以立即獲得真實值，以便可以準確地測量預測誤差。如果沒有真實值，就會依賴多數投票；與多數決策最不一致的模型被丟棄。從而保證集成中的K模型最符合當前概念。

Fig.2 Ensemble classification圖2 集成分類

算法1 總結了集成分類和更新算法。第1、第2行從最近的塊構建一個新模型并暫時將其添加到集成中。接下來，第3～第9行應用集成中的每個模型來測試圖t以尋找可能的異常。為每個模型使用3 種GBAD（P、MDL 和MPS（maximum partial substructure）），每種都在第4章中討論。最后，第10～第18行通過丟棄加權多數意見中最不一致的模型來更新集成。如果多個模型具有最多的分歧，則丟棄任意性能最差的模型。

算法1集成分類和更新算法

加權多數意見使用公式：

在第11行計算，其中Mi∈E是從塊i訓練的集成E中的模型，是由模型Mi報告的一組異常，λ∈[0,1]是一個恒定的衰落因子[31]，并且? 是最近的一塊的序號。模型Mi的投票接收權重為λ?-i，最近構建的模型的權重則為λ0=1，從前一個塊接收權重λ1訓練的模型（如果它仍然存在于整體中）。當λ＜1時，這具有加權當前模型的投票高于可能過時的模型的投票的效果。然后將加權平均值WA(E,a)四舍五入到第11行中最接近的整數（0或1）以獲得加權多數表決。

例如，在圖2中，模型M1、M3和M7分別對輸入樣本x投正和負。如果?=7 是最近的塊，則這些投票分別加權λ6、λ4和1。因此加權平均值為WA(E,a)=(λ6+λ4)/(λ6+λ4+1)，如果λ≤0.86，則在這種情況下，負多數意見獲勝；但是，如果λ≥0.87，則新模型的投票結果超過了兩個較老的反對意見，結果是正類。因此可以調整參數λ以平衡大量舊信息與較少量新信息的重要性。

本文方法使用以前的GBAD迭代的結果來識別后續數據塊中的異常。也就是說，在先前的GBAD迭代中發現的規范子結構可能在每個模型中持續存在。這允許每個模型引入所有數據，而不僅僅是當前塊的數據。當流觀察到概念漂移時，這可以是顯著的優點，因為模型集合可以識別整個數據流或大量塊而不是當前塊中的規范模式。因此，仍然可以檢測到罕見的內網惡意行為。

重要的是要注意，集成的大小隨著時間的推移保持固定。表現不佳的過時模型將被更適合當前概念的更好的新模型所取代。這使得每輪分類都易于處理，即使流中的數據總量可能無限制。

4 基于圖的異常檢測

算法1 使用3 種GBAD 來推斷使用每種模型的潛在異常。GBAD是一種基于圖的方法，通過搜索3個因素來查找數據中的異常：頂點和邊的修改、插入和刪除。每個獨特因子都運行自己的算法，找到規范的子結構，并嘗試找到與發現的規范子結構相似但不完全相同的子結構。規范子結構是頂點和邊的重復子圖，當合并為單個頂點時，大多數壓縮整個圖。圖3 中的矩形標識了所描繪圖的標準子結構的示例。

Fig.3 Graph with canonical substructures and exceptions圖3 具有規范子結構和異常的圖

使用SUBDUE[32-34]來查找規范的子結構。最佳規范子結構可以表征為具有最小描述長度（MDL）[35-37]的子結構：

其中，G是整個圖；S是被分析的子結構；DL(G|S)是被S壓縮后的G的描述長度；DL(S)是被分析的子結構的描述長度。描述長度DL(G)是描述圖G[38-39]所需的最小位數。

內網異常與規范子結構的差異很小。這是因為內網異常試圖嚴密模仿合法的系統操作。應用3 種不同的方法來識別這種異常[40-41]，如下所述。

4.1 GBAD-MDL

在找到最佳壓縮規范子結構后，GBAD-MDL 在隨后的子結構中搜索與該規范子結構的偏差。通過分析與標準尺寸相同的子結構，識別邊緣和頂點標簽以及邊緣的方向或端點的差異。最異常的是那些子結構，其中需要最少的修改來產生與標準結構同構的子結構。在圖3 中，標記為E的陰影頂點是GBAD-MDL發現的異常。

4.2 GBAD-P

相反，GBAD-P搜索插入操作，如果刪除，則產生標準子結構。對圖形的插入被視為規范子結構的擴展。GBAD-P 基于邊緣和頂點標簽計算每個擴展的概率，因此利用標簽信息來發現異常。概率由下式給出：

其中，A表示邊或頂點屬性，v表示其值。

概率P(A=v|A)可以通過高斯分布生成：

其中，μ是平均值，σ是標準偏差。較高的ρ(x)值對應于更多的異常子結構。

因此，使用GBAD-P 可確保本文算法將圖中實際數據（而不僅僅是其結構）反映的惡意內網行為可靠地識別為異常。圖3中，標記為C的陰影頂點是GBAD-P發現的異常。

4.3 GBAD-MPS

最后，GBAD-MPS 考慮刪除，如果重新插入，則產生規范的子結構。為了發現這些，GBAD-MPS 檢查了父結構。父級中大小和方向的變化表示子圖之間的刪除。最異常的子結構是使父子結構相同所需的轉換成本最小的子結構。在圖3中，由于陰影矩形標記的B和D之間缺少邊緣，因此GBAD-MPS 將A-B-C-D頂點的最后一個子結構識別為異常。

5 實驗

在2018 年林肯實驗室入侵檢測數據集[42-47]上測試了本文算法。此數據集由每日系統日志組成，其中包含所有進程執行的所有系統調用。它是使用基本安全模式（basic security model，BSM）審計程序創建的。每個日志都包含使用圖4 中舉例說明的語法表示系統調用的令牌。

Fig.4 Example of system call record from MIT Lincoln dataset圖4 來自MIT Lincoln數據集的系統調用記錄示例

令牌參數以標題行開頭，以拖車行結束。標題行以字節為單位報告令牌的大小、版本號、系統調用以及執行的日期和時間（以ms為單位）。第二行報告執行進程的完整路徑名。可選屬性行標識所有者、文件系統和節點以及設備的用戶和組。下一行報告系統調用的參數數量，后跟下一行的參數本身。主題行報告審計ID、有效用戶和組ID、真實用戶和組ID、進程ID、會話ID、終端端口和地址。最后，返回行報告系統調用的結果和返回值。

由于許多系統調用是與任何特定用戶無關的自動過程的結果，因此對于內網異常檢測，將注意力限制在用戶附屬系統調用上。這些包括調用exec、execve、utime、login、logout、su、rsh、rexecd、passwd、rexd和ftp。所有這些都對應于用戶執行的登錄/注銷或文件操作，因此與內網異常檢測相關。限制對此類操作的關注有助于減少數據集中的外來噪聲。通過以這些令牌為源點，提取關鍵屬性作為有向邊的標簽，對應屬性的值為頂點，而產生的令牌子圖如圖5所示。

由于不同的原因，圖5 中的每個屬性都很重要。例如，路徑值可以指示正被訪問的信息的重要性或安全級別。文件路徑訪問位置的更改或給定用戶正在執行的系統調用類型可能表示應調查的異常行為。exec 和execve 調用的文件路徑顯示每個用戶執行的各種程序。進程ID允許跟蹤任何給定進程所做的所有系統調用，指示該進程隨時間的行為。終端信息為用戶提供了一種地點數據形式。如果用戶從意外位置登錄或顯示某些位置的異常行為，則可能表示使用了被盜憑據或其他惡意活動。

Fig.5 Token subgraph圖5 一個令牌子圖

表2 顯示了在過濾掉所有不相關的令牌并且已經提取了圖5 中的屬性數據之后數據集的統計數據。預處理提取了跨越500 000 頂點的62 000 令牌。這些反映了9 個星期以來所有用戶的活動。將集成學習算法應用于此數據，其中模型（K）的數量分別設置為1、3、5、7 和9，在令牌子圖中找到規范子結構的集合。在每次集合迭代期間，每個模型選擇最佳的5 個規范子結構用于異常檢測。可以將算法配置為使用5 個以上，但是此默認值產生了良好的結果，因此保持不變。

Table 2 Data set statistics after filtering and attribute extraction表2 過濾和屬性提取后的數據集統計

性能以總誤報（FP）和漏報（FN）來衡量。之所以選擇林肯數據集是因為它的體積很大，并且因為它的異常集是眾所周知的，所以通過計數來促進準確的性能評估。表3總結了結果，以及異常（true positive，TP）的計數。全部模型實現了零漏報。K=1 的線反映了非整體單模型GBAD方法的性能。當集成規模K在3 以上時，誤報均在200 以下，相對于使用單模型，誤報率大大下降。并且，K=9 模型的集成學習可以減少84%的誤報率，雖然系統誤報的異常數相對于真正的異常較大，但合適地選擇集成大小，可以實現一個很好的平衡，既實現低漏報，又可以保證發現的異常規模是可處理的，因為相比于待識別的異常規模，內網異常危害更大。因此，有理由相信利用圖挖掘的無監督優勢同時，融入了對流變化性的考慮，可以有效地識別內網中的異常活動。

Table 3 All integrated TP and FP count表3 全部集成的TP和FP計數

從K=1 到K=3 觀察到增加模型計數的最大影響。這表明即使集成中模型數很小比如K=2，也比單模型方法K=1提供了顯著的改進。它還揭示了當計算時間非常寶貴時，小型集成可以在合理的運行時間內提供高分類精度。在本文實驗中，使用K=3模型比K=9 的情況下實現誤報減少（減少了80%），但運行時間不到10。

圖6 顯示了每個集成隨時間推移而產生的誤報的分布。在此數據集中，所有真正的內網異常活動都發生在第6周，導致該周的誤報率激增。在前5個星期，隨著它們學習合法的行為模式，集成方法逐漸改善，而單一模型的方法激烈振蕩。當惡意內網行為出現在第6 周時，兩種方法的誤報率都在上升，因為它們試圖學習新概念。集成方法在很大程度上取得了成功，在接下來的幾周內產生了低誤報率，但單一模型方法已經被破壞。它無法充分編碼同一模型中與合法行為和非法行為相關的概念，導致第9周誤報率急劇上升。

Fig.6 Distribution of false positives圖6 假陽（誤報）的分布

接下來研究參數K（集成大小）和q（每個模型的規范子結構的數量）對分類精度和運行時間的影響。為了更容易地執行繪制這些關系所需的大量實驗，使用表4中總結的較小數據集進行這些實驗。數據集A 包括在第2～第8 周期間與用戶Donaldh 相關聯的活動，數據集B 在第4～第7 周期間用于用戶William。這些用戶中的每一個在相應的時間段內顯示惡意內網活動。這兩個數據集都表明了今后討論的所有關系的類似趨勢。因此，僅報告數據集A的詳細信息。

Table 4 Summary of data set A and data set B表4 數據集A和數據集B的總結

圖7 顯示了規范子結構數量q與數據集A 中的運行時間之間的關系。由于數據集A 中只有4 個規范結構，因此時間增加近似線性，直到q=5。因此，對第5個結構的搜索失敗（但是會影響運行時間），而較高的q值則沒有進一步的影響。

Fig.7 Effect ofq on running time of fixedK=6 on data set A圖7 K=6 時q 對數據集A上運行時間的影響

圖8 顯示了集成中總體模型數K對數據集A 的運行時間的影響。正如預期的那樣，運行時間隨著模型的數量逐漸增加（在該數據集中平均每個模型2 s）。

增加q和K也有助于提高TP。圖9和圖10分別通過顯示q和K與TP 的正關系來說明。當q和K增加到一定數量時，分類器可靠地檢測數據集A中的所有7個真陽性。因此，q和K的這些值在對內部威脅的覆蓋率和高響應性所需的有效運行時間之間達到了最佳平衡。

Fig.8 Effect ofK on running time of fixedq=4 on data set A圖8 q=4 時K 對數據集A上運行時間的影響

Fig.9 Effect ofq on true positive count of fixedK=6 on data set A圖9 K=6 時q 對數據集A上TP計數的影響

Fig.10 Effect ofK on true positive count of fixedq=4 on data set A圖10 q=4 時K 對數據集A上TP計數的影響

表5 考慮了加權與未加權多數表決對固定q=3的分類精度的影響。未加權列是λ=1 的列，加權列使用衰落因子λ=0.9。數據集包含與用戶donaldh 相關聯的所有令牌。加權多數表決在這些實驗中沒有影響，除非K=4，其中FP率從124（未加權）降低到85（加權）并且將TN 率從51（未加權）增加到90（加權）。然而由于這些結果可以在K=3時沒有加權投票的情況下獲得，得出結論，加權投票僅用于減輕K的不良選擇；當明智地選擇K時，加權投票與否幾乎沒有什么影響。

Table 5 Effect of fading factorλ (weighted voting)表5 衰落因子λ 的影響（加權投票）

實驗證明，本文提出的集成方法在累積的系統日志中可以有效地識別內網異常。在現實世界中，惡意內部人員的活動往往極力模仿正常人員的活動方式，因此本文結合圖挖掘算法，在發揮其無監督優勢的同時，通過規范子結構可以有效地發現偏離正常行為的活動。并且本文所提方法通過集成分類和更新，可以有效識別隨時間變化的內網異常，同時使用投票提高了分類準確率，避免了單一模型的分類準確率低的性質。因此，對于隱藏在大量數據流中的內網異常且無標記的數據時，本文所提出的基于流挖掘和圖挖掘的集成方法是十分有意義的。

6 結論和未來工作

基于集成的內網異常檢測方法成功識別出林肯實驗室入侵檢測數據集中的所有異常，其漏報為零，誤報率低于相關的單模型方法。該方法將基于圖挖掘的異常檢測的非監督優勢與流挖掘的自適應性相結合，以實現內網異常檢測。

未來的工作應該考慮可調參數以及在其他場景中的參數選擇問題，以進一步降低誤報率和提升方法的擴展性，為此仍有很大的改進空間。此外，更復雜的輪詢算法可以對更好模型的投票進行加權，這可能具有顯著的準確性優勢。

減少分類器運行時間對于快速檢測和響應新出現的內網異常也很重要。本文中的實驗是使用純串行實現進行的，但是整體算法包括大量的并行化空間。因此，未來的工作應該研究分布式和云計算技術的應用，以提高效率。

最后，盡管實際的內網異常檢測機制必須現實地假設標記數據點形式的真實值通常是不可用的，但如果這些標簽隨著時間的推移變得可用則利用這些標簽將是有益的。因此，未來的研究應該檢查在集成內用監督學習更新模型的技術，以提高部分標記流的分類準確性。