贝叶斯检测路由器配置异常

廖泽容 者明伟 岳建平

昆明医科大学现代教育技术中心，云南省昆明市 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