基于園區網絡拓撲的告警關聯規則挖掘算法

文 /楊滟 黃小紅 馬嚴

園區網絡指在有限的地理區域內由多個局域網相互連接組成的網絡，作為用戶接入互聯網的基礎，當園區網絡發生異常時必須快速準確定位故障根源才能有效保證用戶上網體驗。然而隨著園區網絡規模日益增大，網絡復雜化、設備多樣化等因素使得告警間的關系也變得錯綜復雜。同時，由于網絡故障具有傳播性，單一故障會引發與之直接或間接關聯的節點故障，造成大量衍生告警，使得故障根源的定位更加困難。

告警關聯規則挖掘技術由于其貼合網絡告警時間相關性的特點，成為近年來興起的網絡故障根源分析方法之一。但是往往存在不同程度的問題。為了解決以上問題，本文提出基于園區網絡拓撲的告警關聯規則挖掘算法（Topo C-OPT算法）；即增加園區網絡拓撲作為挖掘依據，根據告警實體間的跳數定量分析空間關聯性，計算得到拓撲關聯因子，并基于此進一步建立置信度優化模型，有效挖掘出時間相關性雖弱但正確的告警關聯規則，同時增強對時間相關性雖強但無效的規則的識別，從而提升園區網絡告警分析場景下挖掘結果集的正確率。

原有算法回顧

SDH-AARM算法（以下簡稱原有算法）同時具備了WINEPI的時序相關性以及FP-Growth的挖掘高效性，因此本文選用此算法為基礎算法，在該算法的基礎上進行研究改進。告警關聯規則挖掘算法的目的是在一個給定的時序集合中挖掘出所有強告警關聯規則。強告警關聯規則指支持度和置信度均高于閾值的告警關聯規則。原有算法包括以下步驟：

1.采用滑動窗口方法構建告警事務庫；

2.基于支持度挖掘頻繁告警序列；

3.加入告警時序特征，生成告警關聯規則及置信度；

4.基于置信度篩選強告警關聯規則。

置信度是評價某一事件正確概率的一種度量，表示該事件的可靠程度。告警關聯規則A=＞ B中A稱為前件，B稱為后件；A=＞ B的置信度(con)計算公式表示為

其中s(AB)為AB的支持度，表示A、B同時出現的概率；s(A)表示A出現的概率。支持度計算公式如下：

由于構建告警事務庫后，窗口總數為確定值，所以根據上述置信度及支持度計算公式可知，原有算法中的置信度是單純基于支持數計算得到的，忽略了空間關系的定量影響，導致其準確度與實際情況存在偏差；當應用于園區網絡告警關聯規則挖掘時往往造成漏選正確規則，同時錯選錯誤規則的現象。

綜上可知，置信度的準確性對最終強告警關聯規則結果集的正確率具有決定性作用。因此，本文所提出的Topo C-OPT算法中，關鍵改進點在于引入園區網絡拓撲優化告警關聯規則的置信度，提高規則置信度的準確性從而達到提升強告警關聯規則挖掘結果集正確率的目的。

Topo C-OPT算法

Topo C-OPT算法在網絡拓撲關聯性與告警時間相關性相互獨立的前提下提出，忽略網絡拓撲距離對告警傳輸時延的影響。

Topo C-OPT算法主要包含以下六個步驟。

1.采用滑動時間窗口方法處理告警源數據，得到告警事務庫；由于園區網絡中的關聯告警必定在相近時間發生，所以該方法具有實際意義。

2.采用FP-growth算法挖掘頻繁告警序列；

3.基于頻繁告警序列，加入告警的時序特征生成告警關聯規則及其置信度；時序特征包括順序關系、并列關系及混合關系。

4.構造拓撲關聯因子算法，計算告警實體在園區網絡拓撲中的關聯性。

5.構造置信度優化模型；基于上一步驟獲得的拓撲關聯因子進一步構造置信度優化模型，優化步驟2中原有置信度，提升置信度值的準確性。

6.基于優化后置信度篩選強告警關聯規則。

其中，步驟4和5中提出的拓撲關聯因子算法及置信度優化模型為本研究的關鍵改進點，彌補了單純從時間維度計算置信度造成其偏差較大的不足，增強對正確規則的識別能力，提升強告警關聯規則挖掘結果集的正確率。

拓撲關聯因子算法

本研究所提出的拓撲關聯因子定義為：描述告警關聯規則前后件在網絡拓撲中的關聯性，關聯性越高，則拓撲關聯因子值越大。本算法采用告警實體在網絡拓撲中的距離，即從源實體到目的實體所需經過的最小鏈路數，作為衡量關聯性的參數。

根據告警關聯規則的定義可知，規則前后件均為告警項集合，集合中的告警項為并列關系，前后件間具有因果關系。為了研究拓撲關聯性對因果關系的影響，本算法中將前件和后件分別視為整體，計算兩者的關聯性，即為拓撲關聯因子。

拓撲關聯因子算法包含以下三個步驟：

1.計算前后件中告警實體在網絡拓撲中的距離；

2.將前件、后件分別視為整體，計算前件與后件的告警實體集之間的平均距離。

3.基于告警關聯規則前后件的平均距離，計算拓撲關聯因子。

第一，計算源-目的告警實體對距離

計算源實體(Sv )與目的實體(Dv )距離的算法如下：

輸入：網絡拓撲 ( G( V, E ))，源-目的實體對([vS,vD])

輸出：源-目的實體對的距離(d)算法描述：

(1) 建立隊列sq，d初始賦值為0，將vS從隊尾加入sq；

如圖1 ，給定一個網絡，該網絡中源實體 v1到目的實體 v6的最短路徑為，則 v1v2的距離計為2。

圖1 一個典型的網絡拓撲圖

第二，計算規則前后件的平均距離

輸入：網絡拓撲 (G( V, E))，A′，B′

算法描述：

(1) 取B′中任意未標記實體 vk，計算vk與A′中所有實體的距離，并相加求平均值得到 vk與A′的平均距離；同時標記 vk；平均距離計算公式如公式(3), 其中 nA'表示A′中的實體個數：

③

(2) 重復步驟(1)，直到B′中所有的實體均被標記；

(3) 將B′中所有實體的平均距離值相加求平均值，即可計算出A′與B′的平均距離，計算公式如公式(4)，其中 n B'表示B′中的實體個數：

第三，計算拓撲關聯因子

本研究定義拓撲關聯因子與規則前后件平均距離成負相關關系。告警關聯規則前后件在園區網絡拓撲中的平均距離越小，可推測前后件的告警項集具備因果關系的可能性越大，則定義該規則的拓撲關聯因子值越大。拓撲關聯因子計算公式如下：

由上述公式可得到拓撲關聯因子與前后件平均距離的關系曲線，如圖2所示。隨著平均距離的增大，拓撲關聯因子呈下降趨勢，兩者成負相關關系；拓撲關聯因子取值范圍為(0,1]。

置信度優化模型

圖2 拓撲關聯因子與前后件平均距離關系曲線，表示園區網內最大距離

按上述算法計算得到的拓撲關聯因子，本研究進一步提出置信度優化模型，根據拓撲關聯因子值對告警關聯規則的原有置信度(con)進行修正，從而得到準確度更高的新置信度( 'con)。根據園區網絡中告警的空間相關性可知，告警關聯規則前后件的拓撲關聯性越強，則該規則的可信程度越高；反之，拓撲關聯性越弱，則可信程度越低。設最小置信度閾值為min，置信度優化模型公式如下⑥：

模型中a、b、c均為基于con的變量，后文將詳細描述； k1、 k2、 k3為三個臨界點，且滿足 0＜k1＜k2＜k3＜1；三個臨界點將topo的取值劃分為四個階段，分別為C1、C2、C3、C4，每個階段具有不同的優化模型；本研究中 k1、 k2、 k3值根據實際故障處理經驗手動設置。

為了更直觀地說明置信度優化模型對告警關聯規則置信度的不同優化策略以及優化后的效果，圖3展示了topo分別與 con'、con的函數關系，并對比了 con'與con曲線。

圖3 'con與con對比圖

由圖3可知，原置信度值不受拓撲關聯因子的影響，完全由時間相關性計算得到，未考慮拓撲關聯因素。而新置信度值是在原置信度值基礎上根據拓撲關聯因子優化得到，同時參考了時間相關性及拓撲關聯性，旨在提高準確性。下面將詳細闡述置信度優化模型各階段的優化策略。

C1階段，topo的取值為 (0,k1]，表示告警關聯規則前后件在園區網絡拓撲中的關聯性非常弱，故在原有置信度的基礎上降低其值。但由于規則在時間維度上的相關性仍然具有重要參考意義，故本研究采用控制原置信度下降范圍的方式保證時間相關性和空間相關性的平衡。當con=1時，根據其計算公式可知每一次前件發生時后件均發生，本研究規定，該情況下即使前后件拓撲關聯性非常弱，該規則也為強告警關聯規則；因此本研究中將下降范圍控制為，則C1階段優化后 con'的取值為。

C2階段，topo的取值為 (k1, k2]，表示告警關聯規則前后件拓撲關聯性較弱，但強于C1階段；故降低原置信度值。本模型定義：在 (k1, k2]范圍內topo的值越小，表示前后件的拓撲關聯性越弱，則對置信度的負向影響程度越大，原有置信度下降程度越大。故本階段采用對數模型， con'的值域為。本階段公式中b和c均為基于con的變量，公式如下：

C3階段，topo的取值為 (k2, k3]，表示告警關聯規則前后件的拓撲關聯性既不強也不弱，故保持原有置信度值不變，即為con。

C4階段中，topo的取值為 (k3,1],表示告警關聯規則前后件在園區網絡拓撲中的關聯性非常強，故在原有置信度的基礎上提升其值。本模型定義：在 (k3,1] 范圍內，topo的值越大，表示前后件的拓撲關聯性越強，對置信度的正向影響程度越大，則原置信度提升的程度越大。故本階段采用指數型增長模型， con'值域為(c on, h]，h值為當即拓撲關聯性最高時 con'的取值。根據置信度的定義，置信度描述關聯規則的可信程度，取值范圍為[0,1]；取值為0時表示該規則完全不可信；取值為1時表示該規則完全可信。原有置信度依據告警的時間相關性計算得到，根據其計算公式可知，表示并非每一次規則前件發生時后件均發生；本研究規定：該情況下即使拓撲關聯性達到最高值1，該規則也不可稱為完全可信，故con'的取值為h(h＜1)。

同時，由于時間維度的相關性依然是置信度計算的重要參考因素，故本研究根據實際故障處理經驗將最大提升空間控制為原有置信度的四分之一，由此可得到以下h值計算公式⑨：

以上詳細闡述了置信度優化模型中topo值處于不同階段時的優化策略，下面通過實驗驗證模型的有效性。

實驗結果與分析

為了對所提出方案的有效性進行驗證，本研究選用某高校校園網絡中2016年6月～2017年4月期間經過初步數據處理后的10000條網絡告警數據作為數據源，并將其按照時間順序平均劃分為5個源告警數據庫。

本研究在2核CPU、4G內存的LAMP環境下采用PHP語言開發。實驗過程如下：首先，分別對5組源告警數據采用滑動窗口方法處理生成5組源告警事務庫。其次，編程實現原有算法與Topo C-OPT算法，并使用兩種算法挖掘相同源告警事務庫，分別得到強告警關聯規則結果集R與R'。最后，采用人工標記法標記出R與R'中所有正確規則。對一條規則而言：正確標記為1，錯誤標記為0；分別統計R與R'中正確規則的數量，計算并對比正確率。

實驗中設置時間窗口為10min、滑動步長為5min；由于在時間窗口和滑動步長確定的情況下，告警事務庫的窗口總數為確定值，根據支持度計算公式(2)可知，此處設定最小支持數閾值即可，故設定1-項最小支持數閾值為10，n-項集最小支持數閾值為5(1＞n)；最小置信度閾值為0.80。分別采用原有算法和Topo C-OPT算法挖掘5組源告警事務庫，得到結果數據如表1所示。

表1 結果集數量及正確率

由以上實驗結果可知，在設置參數均相同的情況下，采用Topo C-OPT算法挖掘5組源告警事務庫得到的強告警關聯規則結果集的正確率均明顯高于原有算法。由此可證明，本研究所提出的Topo C-OPT算法在提升強告警關聯規則結果集的正確率方面具有明顯優勢。

對于研究提出的拓撲關聯因子算法中，園區網絡拓撲關聯性的計算目前只選取了距離作為依據，下一步研究可考慮加入網絡設備層級關系等因子，進一步提高拓撲關聯性計算結果的準確度。