, 李竹村, 王宏, 高先明国防科学技术大学 计算机学院，湖南 长沙 410073
收稿日期：2015-04-29
基金项目：国家自然科学基金资助项目 (61202486，61472438)。
作者简介：邓文平 (1981-)，男，湖南耒阳人, 国防科学技术大学博士研究生;
王宏 (1964-), 男, 湖南益阳人, 国防科学技术大学研究员。
摘要：基于大量的历史BGP路由表快照，对BGP路由宣告信息进行深度挖掘.提出了前缀宣告稳定性度量方法，验证了绝大多数路由宣告是稳定的，历史上发生的路由劫持事件都是瞬时的 (不具备稳定性)；设计了前缀宣告的相似性测度算法，对大量历史BGP路由宣告进行了分析，结果表明大多数大型AS宣告的路由前缀具有自相似性，即，同一个AS宣告的多个路由前缀有一定的连续性.基于以上两个特征，从历史路由信息中可进一步提取前缀宣告的可信集，构造BGP路由宣告的可信知识库，为后续的路由前缀劫持检测和路由安全监测提供依据.
关键词：前缀宣告AS路由前缀劫持RouteViews特征挖掘
Characteristics Mining and Analysis for Internet Prefix Announcements
DENG Wen-ping
, LI Zhu-cun, WANG Hong, GAO Xian-mingSchool of Computer, National University of Defense Technology, Changsha 410073, China
Corresponding author: DENG Wen-ping, E-mail: wsfdwp@163.com
Abstract: The BGP routing information was dogged deeply on the basis of a large number of the history of BGP routing table snapshot. A method to measure stability of prefix announcements was designed, it was verified that vast majority of routing announcement was stable, and the historical routing hijacking was short lived (without stability). A similarity measuring algorithm of prefix announcement was presented, and a large number of the history BGP routing announcements were analyzed. The results showed that the announced prefixes of most large ASes are in line with the property of self-similarity, i.e., the same AS declaring multiple routing prefixes with certain continuity. A trustworthy set of prefix-AS mapping was extracted on the basis of these two characteristics, and a trustworthy knowledge base of BGP routing announcement was designed to provide the basis for prefix hijacking detection and routing security monitoring.
Key Words: prefix announcementautonomous systemprefix hijackingRouteViewscharacteristics mining
Internet以自治系统 (autonomous system，AS) 为单位进行管理[1]，每个自治系统有全局唯一的AS号标识.AS内部使用域内路由协议交换路由信息，如ISIS[2]等；AS间使用域间路由协议交换路由信息，目前大多数AS是使用边界网关协议 (border gateway protocol，BGP[3]) 交换各自的网络可达信息，最新版本是BGP-4.
BGP存在的设计缺陷主要分为两个方面：
1)? BGP协议无法保证路由前缀宣告的完整性.BGP协议漏洞包括BGP本身的漏洞及其他协议带来的漏洞[4].BGP本身的安全漏洞带来的攻击包括重放攻击、消息注入攻击等；其他协议如TCP安全漏洞带来的攻击及SYN洪泛攻击等.
2)? BGP协议默认接收AS宣告的全部路由宣告，AS默认接收BGP协议通告全部路由宣告.BGP和AS本身都没有额外的安全机制来对路由前缀的合法性进行验证.
这两个方面的问题很容易让一个AS可随意发布其他AS拥有的前缀，形成前缀劫持攻击.多年来，前缀劫持攻击现象经常发生，许多大规模的网络瘫痪事故都与路由前缀劫持有关，如2012年的加拿大路由泄露事件[5].前缀劫持攻击是当前Internet域间路由系统所面临的最严重的安全威胁之一，目前仍缺乏有效的防护手段.
业界防范前缀劫持攻击在控制层大致分为两大类：一类是路由认证技术[6].比如：利用数字签名机制如S-BGP[7]，清华大学的GesBGP[8]等，或者利用路由注册思想的IRV[9]，以及基于反向DNS的ROVER[10]等.另一类是增加额外监测机制的前缀劫持检测技术，如通过统计路由数据在发生异常时给用户发出警报的Cyclops[11].前者在部署上存在一定的难度，并且在密钥的管理上易产生新的漏洞；后者存在冒称前缀所有权的可能.此外，部分研究者提出了信任机制来提高域间路由抵御路由前缀劫持的能力，如国防科大胡宁等提出的基于信任机制的域间路由协同管理方法[12]信任值的产生以及检测准确性方面存在的挑战.文献[13]对现有安全路由机制的部分部署进行了全面分析与评估.
由于域间路由的复杂化，目前针对域间路由的安全措施或多或少存在一系列的问题，并不能完全满足需求.检测和发现路由劫持等异常路由的关键在于构建一个可信的知识库.目前的检测知识库都是基于RIR/IRR数据.Internet对于网络资源的管理和分配是通过RIR (regional Internet registry) 进行的，IRR (Internet routing registry) 允许每个ISP在此注册自己的路由策略和规则.但是，资源一旦分配给具体运营商后，网络运营商可独立对网络资源进行再分配.并不是所有的ISP情愿发布自己的路由策略到IRR上，而Internet对于并没有强制要求ISP网络资源再分配的时候到IRR登记.因此，IRR/RIR数据存在“不新鲜、不完整、不准确”的问题，导致基于RIR/IRR数据的知识库的路由劫持检测的准确性和实时性不高.构造一个可信的路由知识库仍然是异常路由监测系统和路由安全监测系统面临的关键性挑战.
本文通过统计和分析大量的历史BGP路由表快照，对BGP路由前缀宣告信息进行深度挖掘，提取验证路由宣告的特征，进一步用于提取前缀宣告的可信集，构造BGP路由前缀宣告的可信知识库，为后续的异常路由监测和安全监测提供信息支撑.
1 实验方法1.1 BGP路由表由于TCP提供可靠传输机制，BGP使用TCP协议作为承载协议，端口号为179.BGP采用“增量式”的更新机制，通过OPEN报文建立邻居，KEEPALIVE维持邻居，UPDATE更新维护路由信息，NOTIFICATION通知对端检测到错误.AS通过使用BGP协议向它的邻居AS宣告IP地址前缀，并且将它从邻居AS学到的路由信息传播给其他的邻居AS.图 1给出了RouteViews[14]下载的BGP路由表实例.
图 1(Fig. 1)
 | 图 1 BGP路由表Fig.1 BGP routing table |
每个BGP路由器会维护一个与图 1类似的路由表，路由表中包含着到目的网络的路径信息.每条路由条目中包含以下属性：Network表示目的网络前缀；Next Hop表示下一跳的IP地址；Metic表示度量值；LocPrf表示本地优先级；Weight为cisco私有参数；Path表示AS路径信息.在通常情况下，一条路由记录中，Path属性从左到右表示从当前AS出发到达目的AS所要穿越的AS，因此，Path最右边的AS号即为目的网络的源宣告者.图 1的第三条记录中，从当前AS到目的网络1.9.0.0/16，需要穿越AS 3356和AS 1273之后，到达目标网络所在AS 4788，则AS 4788就是目的网络的源宣告者.
1.2 IP-AS映射活跃度的构造方法定义1?活跃度 (ActiveString)：假设样本A中共有n个路由表，若IP-AS映射p在第k个路由表中出现，则该映射活跃度的第k位为1，反之，如果没有出现，则为0.
活跃度可以反映IP-AS映射在样本中的出现规律.根据数据源的路由表构造ActiveString的过程，就是统计IP-AS映射在该样本中的出现时间和次数.例如前缀“1.0.0.0/24”与AS 15169的映射在2014年1月份每天的第一个路由表中均有出现，则该映射的ActiveString为1111111111111111111111111111111.根据路由表快照构造IP-AS的ActiveString过程大概分为以下几个步骤：
1)?遍历所有的路由表，从路由表中提取所有的IP-AS映射；
2)?如果在k路由表中出现该IP-AS映射，则当前第k位置为1，反之，置为0.
1.3 IP-AS映射的稳定性计算方法IP-AS映射的稳定性计算基于ActiveString，主要是通过对ActiveString进行处理，统计从第一次出现到最后一张表映射的出现次数，得到IP-AS在该样本空间的稳定性参数.假设一组给定的IP-AS映射，在ActiveString中，它的出现次数为n，第一次出现位置为l，样本空间大小为c，则该映射的稳定性v为
 | (1) |
1)?读取ActiveString，统计映射出现的次数及第一次出现的位置；
2)?根据公式计算映射稳定性.
1.4 路由前缀宣告的变化性测度方法通过统计路由表之间的差异来测度路由宣告的变化性，检测域间路由的异常.路由表的变化分为两种情况：一种是减少的前缀宣告；一种是新增的前缀宣告.假设定义样本中第k个表中IP-AS映射的集合为A，第k+1个表中IP-AS映射的集合为B，则减少的前缀宣告为A-B，数目为 (|A-B |)，减少的比例为 (|A-B|)/(|A|)，称之为差集；反之，新增的前缀宣告为B-A，数目为 (|B-A|)，新增的比例为 (|B-A|)/(|B|)，称之为反差集.通过统计路由表中前缀宣告的增减，计算差集与反差集，得到路由表的变化规律.显然差集越小，稳定性越高，路由表的变化就越小.该计算的基本过程如下：
1)?读取第k个表得到路由表k中的IP-AS映射A；
2)?读取第k+1个表得到路由表k+1中的IP-AS映射B；
3)?计算差集与反差集.
1.5 路由前缀宣告的相似性测度方法通过统计历史路由表信息，得到路由表中每个AS宣告的地址块.RIR分配多个地址块给运营商，运营商将地址块再次划分为多个小的地址块分配给其他AS.因此，AS宣告的前缀间存在一定的内在联系，即存在一定的相似性.从另一方面可以看出，如果路由表中新出现一个IP-AS映射，而在该AS宣告的地址块中不存在一个相似度极高的前缀路由宣告，且稳定性高，则新出现的IP-AS映射的可信度存在一定的问题.
定义2?前缀路由宣告的相似性：假设AS1宣告两个前缀p和q，长度分别为m和n，而p和q的最长父前缀长度为len，则p和q的相似度s为
 | (2) |
图 2(Fig. 2)
 | 图 2 计算路由前缀相似度流程图Fig.2 Flow chart of computing route prefix similarity |
统计路由表中每个AS的路由前缀宣告的相似度的基本过程如下：
1)?读取路由表中的每个AS宣告的地址块，遍历每个AS的每个地址块；
2)?根据公式计算每个地址块与其他所有地址块的相似性，并记录每个地址块与其他地址块的最大相似度.
该计算的实现过程如图 3所示.
图 3(Fig. 3)
 | 图 3 统计AS路由前缀相似度流程图Fig.3 Flow chart of counting prefix similarity of AS |
2 结果与分析2.1 数据源本文实验数据来自于Oregon大学的RouteViews项目[14].实验所使用的四组数据分别是2005年1月到2014年12月、2014年1月1日到2014年12月31日、2014年12月1日到2014年12月31日、2014年1月1日.其中第一组数据使用每月第一个路由表作为一个月数据的代表；第二组和第三组数据使用每天第一个路由表作为当天的数据代表；第四组数据为全天所有的路由表.
2.2 路由宣告稳定性统计分析通过用统计的分析方法分析样本数据，得到以下结果：①2005年到2014年10年期间的IP-AS映射的稳定性分析结果表明，大概有50万条IP-AS映射在10年时间的样本里是非常稳定的.②2014年365天的路由表统计分析结果表明，45万多条IP-AS映射在1年中每天同一个时间点稳定出现.③2014年12月的路由历史信息统计结果表明，有54万多条IP-AS映射在该月内同一个时间出现，是非常稳定的.④2015年1月1日全天的前缀稳定性分析结果表明，在一天的时间里，99.7%的IP-AS前缀是稳定的，约63万条IP-AS在一天的时间内会在路由表中连续出现.
综上，绝大多数IP-AS映射是非常稳定的，出现的时间段是相对规律的，不稳定的IP-AS映射所占比例相对较小.并且样本时间间隔越短，IP-AS映射相对更加稳定.
2.3 路由宣告变化性测度分析利用自相似的分析方法分析样本的正反差集，得到以下结果.
图 4是2014年的IP-AS映射的差集与反差集统计图.结果表明，2014年路由表整体稳定，在2014年11月5号时，差集和反差集达到最高峰.意味着，在2014年11月6日较11月5日，新增了较大数量的IP-AS映射.
图 4(Fig. 4)
 | 图 4 2014年路由表差集Fig.4 Difference set of routing table during 2014 |
2.4 路由宣告相似性测度分析利用自相似性的分析方法分析2014年11月6日全天的历史路由信息，如图 5所示.分析结果显示，AS宣告的地址块中，大约41万条前缀宣告在宣告该前缀的AS中存在相似度90%以上的前缀宣告，占总前缀宣告的74%；其中29万多条前缀宣告在宣告该前缀的AS中存在相似度95%以上的前缀宣告，占总前缀宣告52%；大约只有0.49万条前缀宣告在宣告该前缀的AS中存在相似度5%以下的前缀宣告，占总前缀宣告的0.89%；大约2.7万个AS在该路由表中只出现一个路由宣告 (大约4%).
图 5(Fig. 5)
 | 图 5 2014年11月6日前缀相似性Fig.5 Prefixes self-similarity analysis during november 6th in 2014 |
实验表明，对于大部分AS宣告的一个地址块，存在它宣告另外一个地址块与当前地址块具有很高的相似性，即，同一个AS宣告的多个路由前缀有一定的连续性.
3 结论相较于RIR/IRR数据，对历史BGP路由表快照进行分析得到的数据更为真实，可信度高；而针对短时间内新的路由前缀，利用路由前缀之间的相似性判断路由前缀宣告的可信、实时性程度高.通过分析历史路由信息，挖掘路由前缀宣告的特征及对路由前缀宣告进行可信性分析，可构建一个高效、实时、准确的知识库，为检测路由劫持提供信息支撑.
参考文献
| [1] | Chen Y, Datta A K, Tixeuil H, et al. Stabilizing inter-domain routing in the Internet[J].Journal of High Speed Networks, 2005, 14(1): 21–37. |
| [2] | Internet Engineering Task Force.RFC 1195:use of OSI IS-IS for routing in TCP/IP and dual environments[S].Los Angeles:IETF, 1990. |
| [3] | Internet Engineering Task Force.RFC 1771:a border gateway protocol 4 (BGP-4)[S].Los Angeles:IETF, 1995. |
| [4] | Internet Engineering Task Force.RFC 4272:BGP security vulnerabilities analysis[S].Los Angeles:IETF, 2006. |
| [5] | Toonk A.A BGP leak made in Canada[EB/OL].(2012-08-02)[2016-11-26].http://www.bgpmon.net/a-bgp-leak-made-in-canada/. |
| [6] | 黎松, 诸葛建伟, 李星. BGP安全研究[J].软件学报, 2013, 24(1): 121–138. ( Li Song, Zhuge Jian-wei, Li Xing. Study on BGP security[J].Journal of Software, 2013, 24(1): 121–138.) |
| [7] | Kent S, Lynn C, Seo K. Secure border gateway protocol (S-BGP)[J].IEEE Journal on Selected Areas in Communications, 2000, 18(4): 582–592.DOI:10.1109/49.839934 |
| [8] | 李琦, 吴建平, 徐明伟, 等. 自治系统间的安全路由协议GesBGP[J].计算机学报, 2009(3): 506–515. ( Li Qi, Wu Jian-ping, Xu Ming-wei, et al. GesBGP:a good-enough-security BGP[J].Journal of Computer, 2009(3): 506–515.) |
| [9] | Subramanian L, Roth V, Stoica I, et al.Listen and whisper:security mechanisms for BGP[C]// Proceedings of First Symposium on Networked Systems Design and Implementation. Los Angeles:ACM Digital Library, 2004:10-14. |
| [10] | Malhotra A, Goldberg S. RPKI vs ROVER:comparing the risks of BGP security solutions[J].ACM Sigcomm Computer Communication Review, 2014, 44(1): 113–114. |
| [11] | Chi Y J, Oliveira R, Zhang L. Cyclops:the AS-level connectivity observatory[J].ACM Sigcomm Computer Communication Review, 2008, 38(1): 5–16.DOI:10.1145/1341431 |
| [12] | 胡宁, 邹鹏, 朱培栋. 基于信誉机制的域间路由安全协同管理方法[J].软件学报, 2010, 21(3): 505–517. ( Hu Ning, Zou Peng, Zhu Pei-dong. Reputation-based collaborative management for inter-domain routing security[J].Journal of Software, 2010, 21(3): 505–517.) |
| [13] | Lychev R, Goldberg S, Schapira M. BGP security in partial deployment:is the juice worth the squeeze?[J].ACM Sigcomm Computer Communication Review, 2013, 43(1): 171–182. |
| [14] | Oregon.RouteViews routing table archive[EB/OL].(2005-1-23)[2016-11-26].http://www.routeviews.org/. |
