廖澤容 者明偉 岳建平

昆明醫(yī)科大學(xué)現(xiàn)代教育技術(shù)中心，云南省昆明市 650500

1 介紹

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

2 檢測(cè)算法

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

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

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

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

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

這里的Li是指第i行，α是經(jīng)驗(yàn)確定的乘數(shù)。

3 評(píng)估

我們從大學(xué)校園網(wǎng)絡(luò)的思科網(wǎng)絡(luò)操作系統(tǒng)中獲得20個(gè)IOS路由器配置文件。通過手動(dòng)檢查一組潛在的錯(cuò)誤配置被發(fā)現(xiàn)在配置文件中，算法檢測(cè)我們關(guān)注的這些錯(cuò)誤配置，具體說，這個(gè)不尋常的或孤獨(dú)的命令。

如果一個(gè)命令出現(xiàn)5次或更多,在所有出現(xiàn)中只有一次需要一組屬性，特別發(fā)生的時(shí)間被稱為一個(gè)孤獨(dú)的命令。我們?cè)诳▋?nèi)基梅隆路由器的配置文件中發(fā)現(xiàn)三個(gè)孤獨(dú)的命令。對(duì)于一個(gè)網(wǎng)絡(luò)管理員來說，確認(rèn)這些孤獨(dú)的命令是一件十分有趣的事情，熟悉校園網(wǎng)絡(luò)的專家們正在討論此事。

檢測(cè)“孤獨(dú)”命令算法的敏感性是通過計(jì)算錯(cuò)誤配置中的誤報(bào)數(shù)目決定的。誤報(bào)被定義為“不孤獨(dú)”的命令行。探測(cè)器運(yùn)行在24個(gè)路由器的配置文件中。計(jì)算出探測(cè)器參數(shù)α的最小值，它用于判斷每行是否有異常。對(duì)于每一個(gè)孤獨(dú)的命令,我們計(jì)算出的α值與最小值相同或是更小。

4 結(jié)果

圖1描述了檢測(cè)到的異常數(shù)目，它是由聯(lián)合貝葉斯以閥值函數(shù)乘數(shù) 檢測(cè)的。每條孤獨(dú)命令的最小 值首先應(yīng)當(dāng)計(jì)算出來。聯(lián)合貝葉斯檢測(cè)兩個(gè)孤獨(dú)命令（命令2和命令3）。其他孤獨(dú)的命令1發(fā)現(xiàn)2541次誤報(bào)。

5 討論

我們的結(jié)果表明,聯(lián)合貝葉斯能夠檢測(cè)潛在的錯(cuò)誤配置而沒有檢測(cè)其他異常。孤獨(dú)的命令2和3。

考德威爾等人描繪的這種錯(cuò)誤配置類型要求被重點(diǎn)檢測(cè)。如果命令之間的獨(dú)立性假設(shè)放松，檢測(cè)“孤獨(dú)”命令和其他路由器配置錯(cuò)誤作為異?？梢宰鲞M(jìn)一步的努力。例如,一個(gè)錯(cuò)誤配置中指定的接口定義的訪問列表可能會(huì)發(fā)現(xiàn)如果在訪問組的屬性和訪問列表命令之間被考慮。

6 結(jié)語

這項(xiàng)工作的目的是確定是否可以檢測(cè)到路由器配置錯(cuò)誤。一個(gè)探測(cè)器是設(shè)計(jì)和評(píng)估在這個(gè)任務(wù),并且它能夠成功地檢測(cè)到某些類型的錯(cuò)誤配置在現(xiàn)實(shí)世界的路由器數(shù)據(jù)。

圖1 閾值乘數(shù)a同探測(cè)器檢測(cè)到的異常數(shù)目比較

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

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

[3]陳虹，陶滔，常景超.路由器配置診斷及優(yōu)化系統(tǒng)研究與設(shè)計(jì).計(jì)算機(jī)工程與設(shè)計(jì)，2008，29(23)：5986-5988

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

[5]顧曉鳴，龔平，張衛(wèi)國，等.IP網(wǎng)路由故障的產(chǎn)生與仿真檢測(cè)[J].系統(tǒng)仿真學(xué)報(bào)，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ìn)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27(14)：2683-2685

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

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