網絡日志數據中條件因果挖掘算法的優化研究*

劉 云，肖 添

(昆明理工大學信息工程與自動化學院，云南 昆明 650500)

1 引言

保持大規模網絡的穩定性和可靠性已成為網絡管理的基本要求，然而，由于實際運營網絡的高度分散、不斷進化和異構的特點，這并不是一項容易的任務[1]。針對此類問題的研究已取得了許多成果，自動系統日志分析有助于解決各種問題，如系統故障[2,3]和安全威脅[4,5]。跟蹤網絡狀態的一種有效方法是在網絡中部署監控代理，并收集與系統狀態改變相對應的日志信息。在運營網絡中，SysLog[6]已被廣泛地應用于此目的。

如何自動分析系統日志以檢索網絡故障診斷中的有用信息，成為一項重要而具有挑戰性的研究任務。Zheng等人[7]提出三維協同分析算法，通過動態跟蹤多個日志信息，并尋找因果關系來確定觸發事件。Nagaraj等人[8]提出基于分布式系統日志的自動診斷算法，通過使用概率的方法來查找條件獨立性，在系統日志中生成與事件相關的依賴網絡。He等人[9]提出依賴挖掘算法DMA(Dependency Mining Algorithm)，通過將不同設備的日志聚合進行依賴關系挖掘。Mahimkar等人[10]提出網絡信息關聯與探索算法NICE(Network-wide Information Correlation and Exploration)，通過使用多個回歸系數，可以從相關性中剔除失效的因果關系。

但是，三維協同分析算法沒有提出一個有效的修剪方式來消除冗余信息，導致得到的日志數據過大。自動診斷算法通過使用所提的關聯規則并不能生成與故障事件高度關聯的依賴網絡，使得系統整體性能較差。DMA算法在很大程度上依賴于日志事件所依賴的啟發式方法，這使得算法很難進一步拓展。而NICE算法由于使用多個回歸系數需要大量的處理時間。本文在已有研究工作的基礎上，綜合考慮以上算法的優缺點，提出基于條件因果的挖掘算法CCMA(Conditional Causality Mining Algorithm)，首先使用基于監督學習的日志模板生成算法產生一組與每個事件相對應的時間序列；其次用傅里葉分析和線性回歸分析刪除大量無關的周期性時間序列；再根據定義的條件獨立性，用因果推理算法輸出有向無環圖；最后檢測無環圖的邊緣分布，消除因果關系中的冗余部分得出最終結果。仿真結果表明，與DMA和NICE算法相比，CCMA算法優化了處理時間和邊緣相關率2個主要性能指標。

2 預處理

使用基于監督學習的日志模板生成算法[11]，從一個網絡設備獲得的原始日志消息中產生一組與每個事件相對應的時間序列。

Figure 1 Example of log template圖1 日志模板示例圖

從所有日志數據中構造一組事件的時間序列，該時間序列由每個設備(路由器或交換機)的每個日志模板生成。每個時間序列包含一個設備在一個不相連的時間段的日志模板中出現的次數。圖1是日志消息和相應日志模板的示例。在這個例子中，進程ID、用戶名、IP地址、端口號和協議名等變量用通配符(*)代替。

分別用傅里葉分析和線性回歸分析刪除大量無關的周期性時間序列。但是，周期性事件通常包含不遵循其周期性的異常值，由于這些異常值可能對于故障排除也很重要，因此在刪除周期性事件之后，將它們留在時間序列中。

首先利用傅里葉分析發現周期性時間，如果具有時間大小為bf且長度為N的一個給定時間序列f(t)是周期性的，其功率譜以等間距峰為特征。時間序列的功率譜A定義為：

(1)

選擇前l個能量峰作為接來下檢查的候選值(設l=100)。設每個峰值P的間隔滿足：

(2)

利用逆傅里葉分析構造周期性事件的殘差。由于f(t)的周期分量出現在功率譜Ak的峰值中，所以剩余分量A′被表示為：

Ak≤thamax(A),tha=0.4

(3)

的那一部分Ak，其余為0。

通過閾值tha來選取峰值部分(即周期分量),得到了A′的逆傅里葉分析g(t)。剩余時間序列h(t)被表示為：

(4)

的f(t)那一部分，其余為0。

(5)

則時間序列h(t)就可視為周期事件。左側是時間序列與其線性回歸之間差異的指標，將該指標與閾值thl比較，以判斷差異是否足夠小。用此方法可找出哪一個時間序列與它的線性回歸充分吻合。這種方法不能發現大區間周期事件，但與傅里葉分析配合良好，相互彌補了它們各自的缺點。

3 條件因果挖掘算法

3.1 條件因果挖掘算法流程圖

圖2是條件因果算法的流程圖，首先是預處理部分，使用基于監督學習的日志模板生成事件序列；再分別用傅里葉分析和線性回歸分析刪除大量無關的周期性時間序列完成預處理；然后根據定義的條件獨立性，用因果推理算法輸出有向無環圖；最后檢測無環圖的邊緣分布，消除因果關系中的冗余部分得出最終結果。

Figure 2 Flow chart of conditional causality algorithm 圖2 條件因果算法流程圖

3.2 定義條件獨立性

條件獨立性是從相關性中揭示因果關系的一個重要方法。假設有3個事件：X、Y和Z。若滿足式(6)，則對于給定的事件Z,X和Y是條件獨立的。

P(X,Y|Z)=P(X|Z)P(Y|Z)

(6)

則只要Z出現，事件X和Y就是獨立的。若X和Y與Z有因果關系，則X和Y是獨立的，因為它們總是與Z同時出現。也可以理解為，通過考慮相關的事件Z，X和Y之間的相關性被消除(Z可以表示多個事件)。如果X和Y對于給定的Z是條件獨立的，則可以認為X和Y沒有因果關系，因為它們的關系在Z上是間接的。

CCMA算法使用G2檢驗[12]測試條件獨立性，即用節點Z測試節點X和Y的條件獨立性。

G2檢驗是一種評估二進制(包括0和1)或多級數據的條件獨立性的方法。這種方法是卡方檢驗的自然延伸，基于信息理論同時使用交叉熵。統計量G2定義為：

G2=2mCE(X,Y|Z)

(7)

其中，m是數據長度，CE(X,Y|Z)是事件時間序列X,Y和Z(即x(t),y(t)和z(t))的條件交叉熵。用閾值(p=0.01)與零假設下的統計量進行比較。對于G2檢驗，通過把x(t)≥1的每個值轉換為x(t)=1，將原始事件時間序列生成二進制事件時間序列。

條件交叉熵是根據輸入數據中每個值的計數來計算的。假設概率為P(i,j|k)，其中x(t)=i，y(t)=j，z(t)=k，且用Sijk表示t。G2統計量可以變換如下：

(8)

此屬性使得G2檢驗能夠更快地計算，但也將輸入數據的格式限制為二進制。

3.3 生成有向無環圖

稀疏因果圖的快速恢復算法[13,14]是一種基于圖的方法，該方法可重建具有條件獨立性節點之間的因果關系。輸出的因果關系圖是與事件的因果關系對應的有向無環圖，并假定節點在圖中不形成邊緣環。因果推理圖如圖3所示，其步驟如下：

Figure 3 Causality reasoning diagram in CCMA algorithm圖3 CCMA算法中的因果推理圖

(1)從節點(事件)構造完整的(即完全連通的)無向圖。

(2)通過檢測條件獨立性來檢測和去除沒有因果關系的邊。

(3)基于V結構確定邊緣方向。

(4)用方向法則確定邊緣方向。

在(1)和(2)中，用因果推理的思想來估計一個骨架圖，它是一個無向因果圖。為了在(2)中測試條件獨立性，首先切割邊緣(例如A-B)，其節點在沒有其他附加節點的情況下是條件獨立的，這是式(6)的一個特殊情況。然后，通過附加節點(C)的條件獨立性檢查邊緣(A-B)。使用式(6)連接到2個節點(A和B)。如果其他節點中至少有一個保持條件獨立性，則刪除該邊。重復這個過程，可以發現哪些邊表示節點之間的因果關系。

(3)和(4)中，用2個規則來確定檢測到邊緣的方向。在(3)中，V結構是決定邊緣方向的條件。設3個節點(事件)A，B，C為圖的一部分，A-C-B，A和C是相關的，B和C是相關的。如果A和B對C不是條件獨立的，則得到一個因果關系A→C←B。在(4)中，定位規則通過有向無環圖的定義防止事件之間的循環。如果沒有足夠的信息來確定邊緣方向，即使應用了該算法，某些邊緣也可能是無向的。

3.4 消除冗余信息

一些檢測的邊緣在許多不同的有向無環圖(即不同天的數據集)中冗余地出現，它們并不包含能幫助管理人員分析故障的重要信息。設置閾值為5%來過濾冗余事件，即可以方便地識別事件中不尋常的重要因果關系。

4 仿真結果與分析

4.1 數據集及仿真環境

為了驗證所提算法，與其他論文相同均選取來自日本教育與研究網絡中的日志數據集[15]，該網絡連接了日本800多個學術組織。每個消息包含基于SysLog協議的時間戳和源設備名(或IP地址)等附加信息。總共分析了456天的連續日志組成的35 MB日志消息。仿真使用帶有Ubuntu 16.04服務器的計算機，該服務器配備了Intel(R)Xeon(R)X5675(3.07 GHz)和48 GB內存。

為了便于理解日志消息，進一步確定事件及其根源，手動將事件類型標記到生成的日志模板，如表1所示。來自網絡設備的系統日志分為6組：System,Network,Interface,Service,Management,Monitor。此外，還有一些與常用協議和服務相關的外部組。

Table 1 Log message classification表1 日志消息分類

表1中，括號中百分比表示預處理后的消息數量占日志信息總數的比例。“日志信息”表示原始日志消息的數量，“預處理后”表示已預處理消息的數量，“模板”表示已識別的日志模板的數量，表中主要的日志消息是系統事件，模板生成算法輸出1 789個日志模板。因為本文目標是短期因果關系，所以分析每一天的日志數據。最后，從整個數據集生成3 648個有向無環圖(456天和8個網絡子集)。

4.2 預處理分析

圖4所示為預處理抑制的事件數和原始事件數的散點圖,每個點代表1天的數據,對角線表示沒有預處理的基線。預處理方法用了173 min來處理456 d的所有數據集。預處理減少了與輸入事件無關的常規事件數。

Figure 4 Preprocessing scatter plot圖4 預處理散點圖

表1顯示了預處理消息的細分。可以發現System類信息主要是通過預處理刪除的，因為該組包含定期工作的cron事件。由于經常出現NTP(Network Time Protocol)同步消息，Network,Management和Monitor的日志信息也在很大程度上被抑制。經預處理過濾后， 作為CCMA算法的輸入的日志信息占日志信息總數的7%。這些已刪除的事件的報告頻率高于其他事件的，并且在較少的情況下有助于系統故障的排除。另一方面，Interface、VPN和Routing類型的事件很少被刪除，它們的消息代表狀態或配置的變化，這些變化沒有周期性，包含故障排除的重要信息。

4.3 算法對比仿真分析

本節將CCMA算法與DMA算法和NICE算法進行實驗，分析3種算法的處理時間和邊緣相關率。算法的邊緣相關率對比是通過比較生成有向無環圖的邊緣質量而非數量。使用2個指標對比不同算法的邊緣相關率：全局聚類系數[16]和完整子圖大小。全局聚類系數被定義為給定圖中三角形存在數量的比率，全局聚類系數大意味著條件獨立性測試不能有效地切割邊緣。

圖5所示為3種算法的處理時間分布，CCMA算法和DMA算法處理數據集的耗時能控制在合理的時間內，且CCMA算法處理時間更短。NICE算法對有些事件的處理在1天之內沒有完成，有7%的數據集超時，且平均處理時間遠大于CCMA算法和DMA算法的。由于事件量過大，當處理未在1天內完成時，某些點被標記為1天(24 h)。

Figure 5 Comparison of processing time of each algorithm圖5 各算法處理時間對比圖

表2所示為檢測到的邊緣數量，NICE算法和DMA算法比CCMA算法檢測到更多的邊緣。然而在手動調查中發現，大多數這樣的邊緣提供的都是冗余信息。

Table 2 Edge number detected by NICE, CCMA and DMA表2 NICE算法、CCMA和DMA檢測邊緣數

圖6所示為3種不同算法生成有向無環圖的全局聚類系數分布。期望聚類系數能足夠小，而NICE算法產生的有向無環圖是CCMA算法的2倍以上，DMA算法比NIEC算法的聚類系數更高。

Figure 6 Distribution of global clustering coefficients of each algorithm圖6 各算法全局聚類系數分布圖

圖7顯示了生成的有向無環圖大小的分布。與NICE算法和DMA算法相比，CCMA算法生成的子圖更少且更小。CCMA算法在有向無環圖中形成的大多數是三角形子圖，DMA算法形成以4個邊緣為主的子圖，而NICE算法形成邊緣數量達到5個或更多的子圖，但這種子圖大多不具有因果性。仿真結果顯示，通過對比全局聚類系數和完整子圖大小，CCMA算法相比NICE算法和DMA算法在邊緣相關率上有明顯改善。

Figure 7 Complete sub graph size distribution圖7 完整的子圖大小分布圖

表3所示為CCMA算法與DMA算法和NICE算法檢測到的事件對比實際故障報告數據。故障事件總數為188個，由于一個故障事件可能是由多個事件造成的，所以事件類型按與每個故障最相關的事件類型劃分。雖然Service和IGP(Interior Gateway Protocols)中出現了與故障相關的重要信息，但是按照最相關事件劃分并未出現這2類事件，這導致了Service和IGP事件類型的缺失。結果表明，CCMA算法相比DMA算法和NICE算法在不同故障事件類型的挖掘精度更高。由于DMA算法和NICE算法邊緣數量遠大于CCMA算法的，而大量冗余邊緣會影響操作人員的判斷，使得實際檢測效率低。

Table 3 Comparison of edge and actual fault data detected by three algorithms表3 3種算法檢測到的故障與實際故障數據對比

表3中，括號內百分比表示檢測出的故障數占總故障數的比例。

4.4 消除冗余分析與檢測邊緣分類

圖8所示為在所有數據集中檢測到的邊緣的累積和。CCMA算法產生16 196條邊(即35.5條邊/天)。邊緣的前5%(843條不同邊緣中的42個)占邊緣外觀的85%。這些邊緣出現在超過35個有向無環圖中，通過手動觀察出現的邊緣，發現輸入命令和它的確認之間大多表現出因果關系。設置閾值為5%，過濾冗余事件。過濾過程需要20 s處理所有數據集。

Figure 8 Edge number and edge frequency圖8 邊緣數與邊緣頻率圖

通過過濾冗余事件得到剩余邊緣，并使用預處理得到的日志消息模板對檢測到的邊緣分類，表4所示為通過檢測邊緣得到的相鄰節點(事件)的不同類型數量。某些邊緣將2種不同類型事件聯系起來，占主要類型的是System 和Management。這2種類型與外部可操作連接有關，導致管理中觸發的登錄事件和系統中觸發的UI進程啟動事件。與網絡功能相關的類型，如Network,Interface和VPN等也很重要。這些事件通常會影響多個接口、路徑或設備，從而為決策提供更多信息。CCMA算法的因果挖掘有助于分析這些網絡功能。

Table 4 Classification of neighboring nodes obtained by edge detection表4 檢測邊緣得到的相鄰節點分類

表4中,百分比表示內部類型或重要節點與所有節點的比值。

表4還顯示出被檢測邊緣的相鄰節點中屬于同一類型的節點數，用內部類型表示。EGP和VPN中的大多數邊緣都包含在它們自己的類型中。Network的進程通常獨立于正常運行中的其他進程，并與其他終端同步。System和Management中的大多數邊緣也包含在它們自己的類型中。這意味著大多數被檢測到的邊緣對應的外部操作連接事件與其他類型的事件相獨立。相反，Network中的大多數邊緣都連接到其他類型。此外，重要節點表示與實際故障報告中相關的重要節點數。監視事件中重要節點相鄰事件占總節點的78%，這意味著由SNMP(Simple Network Management Protocol)消息組成的監視事件比其他類型提供更重要的信息。

5 結束語

為了從大量網絡日志信息中挖掘出與網絡故障相關聯的重要事件，本文提出基于條件因果的挖掘算法(CCMA)。本文從3個方面進行優化：(1)用傅里葉分析和線性回歸分析刪除日志消息中的無關時間序列數據，減少了處理時間；(2)利用因果推理算法輸出與事件的因果關系相關的因果關系圖；(3)根據合適的閾值消除邊緣中的冗余部分，提高了挖掘精度。仿真結果表明，對比DMA算法和NICE算法，CCMA算法在處理時間和邊緣相關率2個主要性能指標方面均有改善。下一步將嘗試使用其他網絡數據進一步評估所提算法。