貝葉斯檢測路由器配置異常

廖澤容 者明偉 岳建平

昆明醫科大學現代教育技術中心，云南省昆明市 650500

1 介紹

2001年1月23日，微軟的網站下線了將近23個小時。第二天，微軟發言人亞當·索恩認為失敗的原因是“域名服務器網絡上的路由器配置改變”。這個例子突出了關鍵的問題，路由器配置。自從公司依托可用性的網絡，這種錯誤是昂貴的。每個路由器都單獨配置自己的路由器配置文件，它可以包含幾千行命令。雖然語法正確的每個文件可以被驗證，確定整個網絡中的所有的路由器配置文件語義的正確性和一致性是一個更難的問題。由于這一問題的嚴重性，我們的目標是開發一種方法，自動識別定義每個網絡的路由器配置文件的語義錯誤。關于這個問題以往的方法[2,3]中需要一個先驗期望。但是我們的工作是不同的，我們沒有這樣的假設作出的路由器配置結構。由德威爾等人提出了更好的建議[1]，他們指出，通過路由器配置文件的共性可能推斷出網絡設計選擇，而這些可能會被自動地學習和按照規則編碼。我們的工作不直接用規則學習，但我們的算法檢測這種錯誤統計異常是一樣的。

2 檢測算法

為了測試我們的假設，我們設計和實現了聯合貝葉斯檢測算法。該算法分為訓練和檢測階段。訓練階段檢查每一個配置文件的每一行，并計算一組關鍵頻率，這些頻率是用來描述命令和它們參數的。檢測階段是第二次通過這個文件，并使用這些頻率發現異常。我們的算法做了簡化假設，假設一個配置文件的每行相對于其他行是獨立的。然而，并不是一條命令中的屬性相對另一個屬性是獨立的。考慮在一個配置文件中L行包括一個命令C和屬性（a1,a2,……an）,在這里命令被定義為思科命令集里面的關鍵字，屬性是剩余的空格分隔的單詞。該算法估計命令C出現在L行的概率：P(L|c)，命令中所有屬性出現的聯合概率為：P(L|c)=P(a1,a2,...,an|c)。

在訓練階段，該算法估計概率如下。對于每行L，有命令C和屬性a1,a2……,an,命令出現在每行的概率被估計為C的實例部分，該部分屬性a1到an的整個序列。如果我們使用#（c）表示命令C出現的次數，使用#(a1,a2,...,an|c)表示屬性在命令C中出現的次數，那么概率為：

在檢測階段，我們使用這些估計計算出每行的概率P(Li|c)。通過每行概率和閾值比較，我們可以確定每行中是否存在命令異常。一般的閾值命令在所有配置文件中將無法識別異常。考慮有兩個命令C1和C2命令的實例。每個命令都會有24次出現機會，而且每條命令都有一個參數。命令C1的參數X1出現一次，參數X2出現23次。命令C2中每個參數Yi出現一次，i∈{1,..., 24}.在行中“c1 x1”和“c2 y1”都出現相同的概率（1/24）。盡管如此，“c1 x1”比起“c2 y1”看起來似乎更加異常。為了區分這些情景，我們通常使用熵，它是如何預測分布的一個衡量標準。我們明確地計算每條命令的熵

這里A是命令中屬性的可能的序列集，=(a1,a2,...,an)是特別的序列。在我們的例子中，C1的熵比C2的低，因此通過加權熵得到的閥值來區別兩種不同的情況。

如果行中的條件概率明顯地低于熵的逆，該算法把這行視為異常。具體的來說，該算法作以下比較

這里的Li是指第i行，α是經驗確定的乘數。

3 評估

我們從大學校園網絡的思科網絡操作系統中獲得20個IOS路由器配置文件。通過手動檢查一組潛在的錯誤配置被發現在配置文件中，算法檢測我們關注的這些錯誤配置，具體說，這個不尋常的或孤獨的命令。

如果一個命令出現5次或更多,在所有出現中只有一次需要一組屬性，特別發生的時間被稱為一個孤獨的命令。我們在卡內基梅隆路由器的配置文件中發現三個孤獨的命令。對于一個網絡管理員來說，確認這些孤獨的命令是一件十分有趣的事情，熟悉校園網絡的專家們正在討論此事。

檢測“孤獨”命令算法的敏感性是通過計算錯誤配置中的誤報數目決定的。誤報被定義為“不孤獨”的命令行。探測器運行在24個路由器的配置文件中。計算出探測器參數α的最小值，它用于判斷每行是否有異常。對于每一個孤獨的命令,我們計算出的α值與最小值相同或是更小。

4 結果

圖1描述了檢測到的異常數目，它是由聯合貝葉斯以閥值函數乘數 檢測的。每條孤獨命令的最小 值首先應當計算出來。聯合貝葉斯檢測兩個孤獨命令（命令2和命令3）。其他孤獨的命令1發現2541次誤報。

5 討論

我們的結果表明,聯合貝葉斯能夠檢測潛在的錯誤配置而沒有檢測其他異常。孤獨的命令2和3。

考德威爾等人描繪的這種錯誤配置類型要求被重點檢測。如果命令之間的獨立性假設放松，檢測“孤獨”命令和其他路由器配置錯誤作為異常可以做進一步的努力。例如,一個錯誤配置中指定的接口定義的訪問列表可能會發現如果在訪問組的屬性和訪問列表命令之間被考慮。

6 結語

這項工作的目的是確定是否可以檢測到路由器配置錯誤。一個探測器是設計和評估在這個任務,并且它能夠成功地檢測到某些類型的錯誤配置在現實世界的路由器數據。

圖1 閾值乘數a同探測器檢測到的異常數目比較

[1]唐考德威爾,安娜·吉爾伯特等.最前沿的IP路由器的配置.計算機通訊評審，34(1)：(文獻21-26)，2003

[2]詹妮弗·范頓.IP網絡配置跨網域的交通工程.IEEE網絡雜志，頁46-57，九月/十月2001

[3]陳虹，陶滔，常景超.路由器配置診斷及優化系統研究與設計.計算機工程與設計，2008，29(23)：5986-5988

[4]黃望宗，楊建軍，彭東.IP網絡故障診斷與排除方法探討[J].計算機工程與設計，2007，28(14)：3379-3381

[5]顧曉鳴，龔平，張衛國，等.IP網路由故障的產生與仿真檢測[J].系統仿真學報，2004，16(1)：42-44

[6]Franck Le，Sihyung Lee，Tina Wong，et al.Using data mining to detect router misconfigurations [C].Subhabrata Sen，Sambit Sahu. Proceeding of the ACM Sigcomm Workshop on Mining Network Data.New York：ACM Press，2006：293-298

[7]王艷兵，趙銳，姚青.基于可變精度的ID3改進算法[J].計算機工程與設計，2006，27(14)：2683-2685

[8]Ian HWitten，Eibe Frank.Data mining：Concepts and techniques[M].San Francisco：Morgan Kaufmann Publishers，2005

[9]范潔，常曉航，楊岳湘.基于屬性相關性的決策樹規則生成算法[J].計算機仿真，2007，23(12)：90-92