ABSTRACT

In this paper, a new method of inferring AS relationship by analyzing the temporal and spatial reliability is proposed. Firstly, the method selects the routing tables which originate from different monitored points in different intervals. Based on the routing strategy and the hierarchical structure, the AS relationship of different monitored points is inferred in every time window. Moreover, we define and calculate the value of the temporal and spatial reliability by analyzing the spatial consistency and time stability. Furthermore, we set a threshold and regard any AS relationship with reliability value greater than the threshold as trusted relationship. In the meanwhile, we analyze the number of monitored points and the threshold to infer the influence on AS relationship’s validity. Experiment result shows that the accuracy of AS relationship deduction can be largely improved by selecting appropriate number of routing monitored points and the threshold value through our proposed methods.

Keywords:AS Relationship, Reliability, Method

一种基于时空可信度推断AS商业关系的方法

刘磊，朱培栋，胡照明

国防科学技术大学计算机学院，湖南 长沙

收稿日期：2016年1月29日；录用日期：2016年2月12日；发布日期：2016年2月19日

摘 要

本文提出了一种基于时空可信度的AS商业关系推断方法，该方法选取多个时间点的不同监测点路由表，基于路由策略和层次结构初步推断每个时刻不同监测点的AS商业关系，并基于空间一致性和时间稳定性计算其可信度值，根据给定阈值选取可信的AS商业关系。同时，本文还分析了路由监测点数量与阈值对有效AS商业关系推断的影响。实验结果表明，选取恰当数量的路由监测点与阈值可以有效提高AS商业关系的精准度。

关键词 :AS商业关系，可信度，方法

1. 引言

Internet是由一系列自治系统(Autonomous System, AS)构成的集合，BGP(边界网关协议) [1] 协调着AS间的有效运转，并允许每个AS配置自己的路由策略以选择最合适的路由到达目的网络，路由策略的配置通常由AS间的商业关系和采用的流量工程所决定。随着主机和网络数量的不断增加，互联网规模正在快速膨胀，使得AS的路由策略越来越商业化，直接影响着AS间的商业互联关系，使得AS间的物理连接并不意味着流量的传递。因此，AS间的商业关系越发成为国家、企业、机构等不可或缺的网络资源，并且AS商业关系在掌握网络结构与演化、设计和优化网络、发现网络故障点等方面也具有重要的指导意义。然而，由于AS间商业关系由ISP之间协议决定，属于商业机密，且ISP在IRR (Internet Routing Registry)注册留下的路由策略信息过于陈旧，因此，不能通过公开的数据中直接获得AS间商业关系，又由于ISP间协议的变化会引起AS间商业关系的变化，这种AS间商业关系的变动性以及互联网与生俱来的异构性、自组织性和非集中性，都给AS商业关系的准确推断带来了技术挑战。

2. 相关工作

高立新等人最早提出AS间商业关系推断方法[2] ，她假设一条有效的AS路径应该遵循valley-free原则，即一条路径包含0个或多个客户–提供者(兄弟)边，0个或1个对等边，以及0个或多个提供者–客户(兄弟)边。高立新的valley-free假设真实地反映了互联网中AS间的商业关系。高立新的算法试图找出一条路径中度数最大的AS，并认为具有相近度大小的两个AS是对等关系。

Subramanian等人[3] 正式地将AS关系类型(Tor)推断转化为一个组合优化问题——MaxToR问题：给定一个由BGP路由表产生的无向图，并指定每条边为p2c或p2p类型(忽略s2s类型)，使得valley-free路径最大化。同时猜测MaxToR问题是NP-完全问题，并给出了一个解决算法SARK：利用不断去除AS拓扑图中叶子节点的方式为AS设定不同的等级，并从多个采样点设定的AS等级进行比较来判断两个AS间的商业关系。

Di Battista、Erlebach等人[4] 证明了MaxToR问题确是NP-完全问题且不能有效推断出p2p关系，提出了MaxToR问题的解决算法BPP和EHS。BPP算法在结果的真实性上不如SARK，EHS将MaxToR问题转化为一个可满足问题，利用随机游走的方法推断AS间商业关系。

Dimitropoulos等人[5] 基于MAX-2-SAT提出了一种解决办法。对于兄弟关系的确定是基于对WHOIS数据库的查寻，然后最大化valley-free路径的数量和基于度差异推断的c2p关系，通过解决这最大化2元可满足性问题推断AS关系。

加州大学的互联网研究实验室使用Zhang和Oliveira等人在文献[6] 和文献[7] 所述方法描绘了一张带有商业关系的AS-level拓扑图[8] 。算法首先推断出Tier-1所包含的AS，对于与Tier-1的AS相连的则推断为p2c关系，其余为p2p关系。Zhang在文献[6] 中给出了推断Tier-1中AS的方法，但Oliveira假定Tier-1中AS可以从维基百科获取到。由于将只有地区级提供商AS才能观察到c2p关系数量不断增多，导致此方法错误的将p2c关系推断为p2p关系。Gregori等人[9] 使用了类似的方法，对于每一条路径推断出可能的关系后，再基于路径的生命期确定AS关系。

上述从AS间商业关系推断的准确性来考虑，给出了不同的方法，但在互联网上由于商业利益或流量工程，甚至是路径伪造、路径篡改、路由泄露、路由震荡等攻击引起的路由变化导致AS间商业关系的变化很少被关注，因此，本文提出了一种基于时空可信度推断AS商业关系的方法。

3. AS互联关系及路由策略

路由策略是网络管理员配置的一系列路由规则，在很大程度上反映了AS间的商业关系。主要包括提供者–客户关系(provider-to-customer, p2c)、客户–提供者关系(customer-to-provider, c2p)、对等关系(peer-to-peer, p2p)和同胞关系(sibling-to-sibling, s2s)。在p2c中，提供者可以将自己、它的客户、它的提供者或对等体的路由输出到客户，但不能输出它的提供者和对等体的路由；在c2p中，客户可以将自己和它的客户的路由输出到提供者；在p2p中，对等体间可以相互输出自己和客户的路由，但不能输出它们的提供者和其它对等体的路由；在s2s中，兄弟间可以将自己、客户、提供者和对等体的路由输出到对方。

根据以上路由策略高立新证明了[2] 在一条AS_PATH中提供者–客户或兄弟边后面只能是提供者–客户边或兄弟边，对等边后面只能是提供者–客户边或兄弟边。若将只有p2c边或s2s边的AS_PATH路径序列称为下坡路径、将只有c2p或s2s边的AS_PATH路径序列称为上坡路径，那么，一条有效的AS_PATH路径应符合6种模式，即一条上坡路径、一条下坡路径、一条上坡路径加一条下坡路径、一条上坡路径加一个对等边、一条上坡路径加一个对等边加一条下坡路径、一条对等边加一条下坡路径。

4. AS商业关系推断

AS商业关系的推断首先要尽量整合路径集合，排除无效路由的影响，然后推断核心层AS并依据路由策略的六种模式对每一时刻每个监测点进行AS商业关系初步推断，统计形成时空上的AS商业关系监测表，计算每个AS商业关系的可信度值，根据阈值选取可信的AS商业关系。

4.1. 过滤无效路由

BGP在设计应用之初，并未考虑到路由信息的安全性问题[10] ，因此没有建立一种可靠的机制来证明路由信息的有效性，使得攻击者可以任意产生、宣告、伪造路由信息，进而对网络实施攻击。目前，从Route-Views上采集的单个文件的路由表项就达2200万条之多，而且从历史数据统计分析看，路由表项呈现逐年递增的趋势，这与网络规模的不断扩大密切相关，给路由分析带来了麻烦，也使得路由表处理的速度极为缓慢。通过对路由表项中的AS-PATH属性进行观察发现，许多AS-PATH是一样的，只是转发的源与目标路由器的IP地址不同，这给我们一个启发，因为主要的研究对象是AS-PATH属性，能不能将AS-PATH数量缩小以达到快速处理的目标。通过对所有AS-PATH做集合操作，发现实际AS-PATH路径只有300多万条，其中含有核心层AS的路径就有200多万条，这大大降低了路由项处理的数量。同时还发现在300多万条路径中包含诸多无效路由，包括含私有AS或保留AS、路由环、3个及以上或2个不相邻核心层AS、连续重复AS的路径。针对私有AS或保留AS，AS-PATH中不应出现RFC1930中定义的私有或保留的自治系统号的路径，2015年10月份的路由表中这样的路由平均占比0.07%；针对路由环，在AS-PATH中若出现多个相同AS且至少有两个被不同的AS所分离，这样的路径影响了正常路由的选择，2015年10月份的路由表中这样的路由平均占比0.06%；针对3个及以上或2个不相邻核心层AS的路径，违反了路由选择策略，2015年10月份的路由表中这样的路由平均占比0.06%；针对连续重复AS的路径，进行压缩处理，例如将A B B C型路径压缩成A B C，2015年10月份的路由表中这样的路由平均占比19.64%。总的来看无效路由占比在20%左右，这无疑将会造成AS的商业关系的错误判断[11] [12] ，因此，在推断AS间商业关系前要尽量排除无效路径的影响。

4.2. 推断核心层AS

由于AS间存在着商业关系，使得整个BGP网络具有一定的层次性。一般地，按照AS在流量传递过程中所处位置一般将Internet分为核心层、转发层和边缘层。核心层AS一般被认为是顶级服务提供商的骨干网所形成的Internet的核心，各个顶级服务提供商之间相互建立同级对等(p2p)商业互联关系，且是全互联结构。由于在5万多个AS的拓扑中求出最大全连通子图是相对比较困难的，为了降低计算的复杂度，文献[13] 给出一种核心层AS推断方法，但此方法依赖于阈值D和经验值P，并未考虑阈值D外的其它AS是否与阈值D内的AS是全互连的，可能存在误差。本文针对上述方法进行改进以提高核心层AS推断的准确性。具体方法为：首先，获取边缘层AS集合，由于边缘层AS不为其它任何自治系统转发网络流量，且位于网络的边缘，只能出现在AS_PATH序列的末端且不会出现在其它位置，因此将AS-PATH中末位AS组成的集合与非末位AS组成的集合做差集运算，即得边缘层AS集合。其次，指定P值为1(即全连通)，并按照文献[13] 所述方法得到部分核心层AS。再次，将AS集合中边缘层AS和部分核心层AS去除，因为边缘层AS不能同时为核心层AS，且边缘层的数量占总AS数量的近60%。最后，逐个判断剩余AS与部分核心层是否为全连通，如果为全连通则加入核心层。

以2015年10月1日至30日的路由数据进行分析，按照上述方法提取核心层AS共13个，分别2914、7018、2828、174、209、1299、4436、6453、1239、3320、3257、3356、701，且它们在1日至30日均被推断为核心层AS，说明核心层AS是相对稳定的。

4.3. 基于时空的AS商业关系可信度计算

由于网络的动态变化，诸如ISP间的合作关系的变化、针对BGP路由的路径伪造、路径篡改、路由泄露等等都会影响AS间的商业关系，需要一种有效的方法来辨别AS间商业关系的可靠性。为此，本文提出一种基于时空的AS商业关系可信度的计算方法，在基于时间的统计分析上加以空间上的统计分析，即在某一时刻将路由表按监测点进行分离后单独对AS间商业关系进行推断与监测，形成空间与时间的立体式统计分析计算。其具体计算方法如公式(1)和(2)。

(1)

(2)

空间可信度由公式(1)给出，其中，n1为监测点的数量，V_MPi的值为0或1，V_Mpi = 1表示在监测点MPi推断出了AS商业关系 ，反之，V _MPi = 0表示在监测点MPi没有推断出AS商业关系 ，考虑到监测点的数量较多，这里指定在有m个及以上监测点监测到了某一AS间商业关系对的存在，即认为此AS商业关系对在空间上是真实可信的。

基于时空的AS商业关系可信度S由公式(2)给出，主要利用对空间可信度加权平均来实现，使得在最近频繁出现的AS商业关系的权重变大，说明在时间维度上越稳定可信。给定AS商业关系可信度阀值β，若S > β，则认为对应的AS商业关系在时空上是可信的，反之亦然。

4.4. 基于可信度的AS商业关系推断算法

依据路由策略模式，基于时空可信度的AS间商业关系算法将监测点的数量及路由表采集的时间综合考虑进去进行AS商业关系判断。首先，获取单个监测点的路由表并进行AS商业关系初步推断，具体算法如算法1，其基本过程如下：

(1) 去除as-path中的含私有AS或保留AS、路由环、3个及以上或2个不相邻核心层AS、含环、即在as-path中出现至少2个相同AS的路径，压缩含连续重复AS的as-path。

(2) 得到核心层AS集合，若两个不同AS都是核心层AS，则推断它们为对等关系。

(3) 若AS-PATH中含有核心层AS，则推断第一个核心层AS及其左侧为上坡路径，且按路径顺序从左至右每相邻两个AS的商业关系为客户–提供者关系；最后一个核心层AS及其右侧为下坡路径，且按路径顺序从左至右每相邻两个AS的商业关系为提供者–客户关系。

(4) 若AS-PATH中不含核心层AS，且已知两个不相邻AS的商业关系为提供者-客户(或客户-提供者)关系，则推断二者之间AS的商业关系为提供者–客户(或客户–提供者)关系。

(5) 若在不含核心层AS的AS-PATH中存在提供者–客户关系，且其右侧AS关系还没有被标记，则推断其右侧为提供者–客户关系。

(6) 若在不含核心层AS的AS-PATH中存在客户–提供者关系，且其左侧AS关系还没有被标记，则推断其左侧为客户–提供者关系。

(7) 重复步骤(3)、(4)和(5)，直到没有新的AS商业关系产生。

(8) 遍历上述产生的AS商业关系集，若存在两个AS1与AS2的关系既为提供者–客户关系也为客户–提供者关系，则推断其为兄弟关系。

然后，在单个监测点AS商业关系初步推断的基础上，进行空间和时间上的统计，并计算每一对AS商业的可信度值S，若S大于给定的β，则认为此AS商业关系在时空上是稳定的、可信的。具体算法如算法2，其基本过程如下：

(1) 将路由表按监测点进行分离，对于每个监测点的路由表进行AS商业关系初步推断，得到空间上AS商业关系的统计表如表1。

(2) 按时间获取路由表，针对每张路由表执行(1)操作，得到时空上监测到的AS商业关系统计表如表2。

(3) 按照公式(1)和(2)计算每个AS商业关系的可信度值，舍弃S值小于β的AS商业关系。

5. 实验结果及分析

本实验路由数据来源于开源公共项目Route-Views [14] ，因其路由数据更新的连续性与完整性，且单个路由表快照包含多个地区AS监测点。以2015年10月1日路由数据为例共观察到41个监测点，这41个监测点遍布世界各地，可以较为全面地反映互联网的路由情况，是实验基础数据的最佳选择。Route-Views上提供两种格式[15] 的路由表供下载，一种是从Cisco路由器以“sh ip bgp”命令产生的路由表数据的形式提供，每2个小时提供一次路由数据镜像，但这个过程相对比较慢，而且路由的时间戳可能会受到影响，由于路由器的缓存以及本地网络的维护问题，可能导致路由数据部分丢失；另一种是从软件路Zebra上采集到的路由数据，数据以MRT格式存储，这种格式方便被计算机处理，路由数据每

Algorithm 1. AS relationship inference of single monitored point

算法1. 单监测点AS商业关系推断

Algorithm 2. AS business relationship inference based on temporal and spatial reliability

算法2. 基于时空可信度的AS商业关系推断

表1. 空间上AS商业关系监测统计表

15分钟更新一次，相比第一种路由信息更加丰富、准确，因此实验数据选用MRT格式。采集Route-Views上2015年10月1日至30日每日零点的路由表快照作为实验数据进行AS商业关系推断，并统计m，β取不同值时产生的结果，如图1所示。

从图1可以看出，当m值逐渐增大时推断的AS商业关系数量呈现递减的趋势，且随着β取值的增大，这种递减的趋势也不断增大。这是因为随着m，β取值的增大，对于基于时空可信度的AS商业关系推断越趋严格，即可信度值越大，符合可信度值的AS商业关系数量就越少，这在一定程度上可以减少由于商业利益、流量工程、路径攻击等对AS商业关系引起的变化的影响，防止非正常AS商业关系被推断出来而掩盖非法攻击行为。

为了评估本算法推断的AS商业关系的有效性并分析m、β值的选取对于有效性的影响，本实验产生的结果将与10月1日CAIDA提供的AS商业关系进行核实验证。不同m、β值对应的有效AS商业关系占比如图2所示。

由图2可以看出m、β值的递增对有效AS商业关系占比的影响不是线性变化的，在m值小于10时的曲线中，都有徒增的部分，说明某些AS商业关系只会有限的监测点被观察到，这样的变化有可能是商业利益、流量工程、路径攻击等引起的，需要其他佐证才有进一步确定。此外，当m = 1，β ≥ 0.0时，即41个监测点中只要有一个监测点观察到AS商业关系且可信度为1时所推断出来的AS商业关系，从图1和图2中可以看出，虽然此时推断出来的AS商业关系数量最多，但其可信AS商业关系占比却是最低的，说明其中有很多不稳定或错误的AS商业关系；当m = 14，β ≥ 0.9时，有效AS商业关系占比值最大，由此可确定m、β值可以最大化AS商业关系推断的有效性。

表2. 时间上AS商业关系监测统计表

图1. m、β值对AS商业关系数量的影响

图2. m、β值对应的有效AS商业关系占比的影响

6. 结束语

本文通过对路由表中的无效路由进行简单分析与统计，说明无效路由在网络分析与AS商业关系推断中具有一定的影响，应在AS商业关系推断前尽量排除或重整无效路由。同时本文给出一种基于时空可信度的AS商业关系推断算法，并分析了m、β取值对AS商业关系推断数量及有效AS商业关系占比的影响。实验结果表明，选取适当的m、β值可以有效提高AS商业关系推断的精准度。

基金项目

新一代互联网社会网络感知模型与能力设计科学基金(编号：61170285)；面向国家关键基础设施的大规模人机物融合网络安全可控性模型与机制科学基金(编号：61572514)。

文章引用

刘 磊,朱培栋,胡照明. 一种基于时空可信度推断AS商业关系的方法
Method for Inferring AS Relationship Based on Temporal and Spatial Reliability[J]. 软件工程与应用, 2016, 05(01): 38-46. http://dx.doi.org/10.12677/SEA.2016.51005

参考文献 (References)