贝叶斯预测下的域间路由信任机制

王 伟，杨本朝，吴 涛

(1.信息工程大学数学工程与先进计算国家重点实验室，河南郑州 450002;2.安徽大学数学科学学院，安徽合肥 230039)

BGP［1］协议是不同域之间交换信息的路由协议，是互联网中不同自治系统间的协议标准.与其他网络协议一样，BGP协议在安全问题上也存在设计缺陷［2］，由于这些缺陷，恶意攻击者可以进行前缀劫持、路径缩短、路径填充等攻击［3］，严重威胁网络的安全性.

为了提高BGP的安全性，多位国内外学者提出了各种BGP安全方案，其中有Kent等［4］提出的S－BGP(secure border gateway protocol)，White等［5］提出的 So－BGP(secure origin BGP).这些方案都依赖PKI(public key infrastructure)技术来保证信息的可信性，虽然具有良好的安全性，但计算开销过大，至今这些方案都没有在网络中得到实际规模部署.Wan等［6］提出的psBGP(pretty secure BGP)是在BGP更新消息中添加前缀信息和AS号绑定的方法来实现异常检测.该方案需要集中的机构或设施作为支撑，且检测的时效性和可靠性难以得到保证.部分学者也提出了根据信任机制来提高BGP抵御虚假路由攻击的方案，如胡宁等［7］提出了基于构建各AS的信誉，根据AS信誉值的大小有选择地抑制信誉值小的AS提供的路由，该方法虽然提高了路由的可信性，但AS信誉值是如何具体计算和更新的，没有具体描述;谭晶等［8］提出了基于Chord环的域间路由机制，但Chord环节点是如何选取和退出的也没有具体描述，而且该方案是一个集中式的计算方法，且涉及证据理论中的集合运算，因而计算效率不高.

1 域间路由节点信任度的计算

1.1 节点信任度的定义

在Internet中以自治系统为信任实体，借鉴社会科学领域对信任的描述［9］，并结合域间自治系统自身的特点和安全需求，将不同自治系统间的信任度定义为:自治系统A在t时刻对邻居自治系统B的信任度是指A根据B转发的历史路由通告的统计结果，对B未来通告真实路由的概率预测.

在文中，路由通告的统计结果是指B转发给A的真实路由和虚假路由的历史统计.自治系统对其每个邻居都维护和更新路由的统计情况(为了简便，论文将自治系统也简称为节点).

1.2 节点信任度的计算

根据目前关于路由检测的手段以及对无效路由的分析［10］，通过监测系统可以得到虚假路由的统计情况、论文根据路由统计情况，由贝叶斯预测计算自治系统的信任度.

将节点是否收到真实路由看成是二项事件，则节点在△t时间内收到真实路由的个数服从二项分布，设为b(n，p)，其中p为收到真实路由的概率.若在tn时刻节点A共收到来自B的N个路由，其中r个真实路由，根据贝叶斯预测［11－12］知，节点A在未来接收到B的k个路由中，有z个真实路由的后验预测分布为m(z|r)，若取p的先验分布为均匀分布，则

在tn时刻节点A对节点B的信任度TA，B(tn)定义如下

由(3)式可以看出，A对B的信任度由A对B的历史信任度和A对B下一时刻通告真实路由的预测值两部分组成.TA，B(tn)的定义保证了所有历史数据参与了计算，且使得离当前时刻越远的历史信任度对当前信任度的贡献愈小，即离当前时刻越远的行为，其对当前时刻的信任度的影响越小，即信任具有时间遗忘性.而贝叶斯预测值SA，B(tn)则是对信任度TA，B(tn)的修正.若在tn时刻，A收到了邻居节点B发送过来虚假路由，为了符合“信任失去容易、得到难”的一般原则，采用如下信任度更新方法

其中:β∈(0，1)为惩罚因子.可以看出，β取值大小反映了对发送虚假路由节点的惩罚力度，这样不仅能提高信任更新的计算效率，还能及时抑制虚假路由的扩散.

2 基于节点信任度的域间路由机制

对BGP路由算法进行了扩展，在BGP选路过程中加入对节点和路径的信任度的考虑，构建了一个新的域间路由机制N－BGP.增加一个新的路径属性ASpath Trust，表示节点对一条路径的信任度，路径的信任度包括节点对邻居的信任度和邻居对该路径的信任度两部分组成，并且每个节点计算出路径的信任度后都修改ASpath Trust值，表示节点对该路径的信任度.由于网络中每个AS并不一定都部署N－BGP，因此设定ASpath Trust属性为可选属性.

2.1 路径信任度的计算

(1)若n=0，则A与AS0为邻居，其对路径P的信任度即当前时刻A对AS0的节点信任度，，并将 AS path Trust属性值设定为

(2)若n＞0，此时路径P的AS path Trust属性值为，则节点A对路径P的信任度为

2.2 BGP 选路算法

由于路径的信任度由节点对邻居的信任和邻居对该条路径的信任度两部分组成，因此可设定一个阈值θ.当节点对邻居节点的信任度小于θ时，直接抑制该条路径，不作为备选路由，否则计算路径的信任度，再根据路径信任度的大小选取最优路径.此外当有路由需要向邻居广播时，也根据阈值θ确定广播的对象，当邻居的信任度小于θ时，不向其广播路由.因为节点对邻居节点信任度很小时，则该邻居节点可能在当前时刻受到攻击或变为恶意节点，若此时向其广播新的路径更新，则该邻居节点可能会产生虚假路由，不利于虚假路由的抑制.

当节点A收到邻居ASn发送的路径，BGP的选路流程如下:

步骤1 查看A对ASn的信任度是否大于θ，若是，按(5)式计算路径P的信任度，并将P的AS path Trust属性值改为，转入步骤2;若否，抑制该路由，转入处理下一条路由.

步骤2 若Loc－RIB(local routing information base)中没有路径P所表示的目的前缀，则将P加入Loc－RIB中，若有则转入步骤3.

步骤3 依次比较Loc－RIB中与路径P相同目的前缀的路径，选择最优的加入Loc－RIB中(依次比较LocalPref，AS path Trust等属性值).

步骤4 若在Adj－RIB－Out(adjacent routing information base，incoming)中有路由需要对邻居广播，若对邻居的信任度大于θ，则对其进行路由广播，否则不广播.

3 试验仿真

采用网络仿真工具SSFNET对域间路由机制进行评估，网络测试拓扑由网络拓扑生成器BRITE产生，其中每个节点代表一个 AS.默认信任参数设为:α=0.6，β=0.7，θ=0.6.文中配置了一个38节点的网络拓扑.为了考察N－BGP抑制虚假路由的能力，用抑制率作为协议性能指标，抑制率是指当BGP收敛后，网络中被抑制掉的虚假路由数目与总的虚假路由数目之比，抑制率越大，说明虚假路由抑制效果越好.

在BGP运行之初，将BGP路由总数的10%作为虚假路由注入网络中，并配置3%，5%，8%，11%，13%的节点为恶意节点发布虚假路由，分别考察BGP和N－BGP抑制虚假路由的能力，结果如图1所示.由图1可以看出，随着网恶意节点比例的增加，网络对虚假路由的抑制能力在逐步下降，这说明网络中恶意节点越多就越难以防范，而BGP中的虚假路由会一直存在，因为其没有抑制虚假路由的能力.

为了考察不同信任参数对网络抑制率的影响，分别对α，β，θ进行考察，当考察其中一个参数时，另2个设定为默认值，结果如图2所示.由图2可以看出，α对抑制率的影响不是很大;而随着β的增大，即对恶意节点的惩罚力度减小，网络抑制率迅速减小;对于θ，随着其增大，网络抑制率也增大，因为恶意节点的信任度一旦小于θ，则其宣告的虚假路由就被过滤掉了，因而阈值θ越大，抑制率越高，但过大不利于BGP的收敛.根据试验结果，信任度参数一般在区间(0.5，0.7)中选取较为适宜.

图1 抑制率Fig.1 Inhibition rate

图2 参数对抑制率的影响Fig.2 The influence of parameters on the inhibition rate

4 结束语

根据社会行为中的信任关系设计了一种基于节点信任度的域间路由机制，该机制根据节点历史的交互数据，由贝叶斯统计计算出节点对邻居节点的信任度，从而根据节点信任度计算出路径的信任度，并根据路径信任度的大小选择其中最优的路径.由于节点信任度的计算为分布式计算，因而计算简单，计算代价小，且节点只需要维护邻居节点的信任度，因而可进行增量式部署，具有良好的可扩展性.最后试验结果表明，扩展后的BGP协议能够有效抑制虚假路由的传播.

［1］Rekhter Y，Li T，Hares S.A border gateway protocol 4(BGP－4)［EB/OL］.(2006－03－01)［2013－03－06］https://datatracker.ietf.org/doc/rfc4271/?include_text=1.

［2］Murphy S.BGP security vulnerabilities analysis［EB/OL］.(2006 －03 －03)［2013 －03 －06］https://datatracker.ietf.org/doc/rfc4272/?include_text=1.

［3］AT＆T Labs.A survey of BGPsecurity［R］.San Antonio:AT＆T Labs，2005.

［4］Kent S，Lynn C，Seo K.Secure border gateway protocol(S － BGP)［J］.IEEE Journal on Selected Areas in Commun-ications，2000，18(4):582 －592.

［5］White R.Securing BGP through secure origin BGP［J］.The Internet Protocol Journal，2003，6(3):15 －22.

［6］Wan T，Kranakis E，Oorschot PC.On inter－ domain routing security and pretty secure BGP(psBGP)［J］.ACM Transactions on Information and System Security(TISSEC)，2007，10(3):1 －41.

［7］胡宁，邹鹏，朱培栋.基于域间信誉机制的路由安全协同管理方法［J］.软件学报，2010，21(3):505－515.

［8］谭晶，罗军舟，李伟，于枫.基于可信度的域间路由机制［J］.计算机学报，2010，33(9):1763－1773.

［9］University of Oxford.Can we trust trust［R］.Oxford:University of Oxford，2000.

［10］Siganos G，Faloutsos M.Analyzing BGPpolicies:Methodology and tool［C］∥The 23rdAnnual joint Conference of the IEEE Computer and Communications Societies.Hong Kong:IEEE，2004:1640 －1651.

［11］茆诗松.贝叶斯统计［M］.北京:中国统计出版社，1999:35－71.

［12］Carleton University.Secure routing protocols using consistency checks and S － RIP［R］.Ottawa:Carleton University，2003.