针对BGP网络中频发的小规模路由异常问题，本文研究小规模BGP路由异常的特征规律，并利用Spark和Hadoop的高性能存储与计算能力，设计一套包括UPDATE采集、事件采集、UPDATE存储、特征计算模块的BGP异常特征分析系统。基于此系统，讨论8种BGP异常特征定义以及其计算方法，分析路由劫持和路由泄露这两类异常发生时的特征表现，进而分析各个特征对异常检测与分类的显著性和差异性，对于今后小范围BGP异常的检测与分类具有参考价值。

　　小范围BGP路由异常特征分析

　　BGP域间路由异常事件包括攻击、配置错误、大规模电源故障。这些异常导致错误的或无法控制的路由行为，影响了全局路由基础架构。最常见的两种BGP路由异常是路由劫持和路由泄露。有统计显示，大约20%的路由劫持和路由泄露持续不超过10分钟，但是却能在2分钟内影响到90%的互联网。

　　目前，已经有学者对BGP异常的特征进行了研究，并应用到了模式识别和机器学习方法上，取得了不错的成效。但是这些研究也存在着一些的缺陷：

　　1.目前的BGP异常特征研究集中在描述大范围异常特征表现，但是小规模异常特征研究较少。小规模异常相对不容易被察觉，但是其发生的频率更高。这类小规模的异常事件，除了持续时间短之外，还有只影响某个特定IP地址前缀，受影响的IP数量较少的特点。

　　2.样本之间的相关性过强。若来自同一异常事件的样本具有较强的相关性，可能导致特征中的偶然因素被放大。

　　3.不同异常发生的原因是不相同的，研究过程中应该按照异常类型区别对待。路由劫持是一种攻击方式，由某个AS非法地宣告IP地址前缀造成。而路由泄露往往是由于配置错误，导致路由转发策略违反了商业关系。不同的异常类型可能在特征上有不同的表现。不同类型的异常被简单的归为一类是不合适的。

　　鉴于以上对于BGP异常特征研究的缺陷，本文着重研究了小范围的BGP路由异常事件的特征表现。为了解决样本相关性较强的问题，本文从BGP Stream项目中选取了上百个小规模的路由劫持和路由泄露事件作为样本，保证了样本之间的独立性。这些异常事件有着确定的受影响的IP地址前缀和发生时间，通过RIPE项目的BGP UPDATE报文，可以回溯出这些异常事件的特征值。同时为了突出不同异常的特征表现，在研究过程中对特征的异常类型进行了区分。在此基础上，考察了8个BGP异常特征，使用基于Spark和Hadoop的系统架构完成研究。最终，北京邮电大学得到了若干小范围BGP路由异常的特征规律和结论。这些规律和结论将有助于未来小范围BGP异常的检测和分类。

　　系统架构

　　系统分为RIPE路由器、UPDATE采集、UPDATE存储、BGP Stream事件源、事件采集、特征计算六个功能模块。

　　RIPE路由器：RIPE（Regional Internet Registry for Europe）是欧洲、中东和中亚部分地区互联网注册机构，负责为服务提供商分配和注册互联网号码资源。RIPE组织使用Quagga路由软件收集了BGP路由器的原始数据，包括全量的路由表BVIEW数据（每八个小时更新一次）和差量的UPDATE数据（每五分钟更新一次）。

　　UPDATE采集模块：本模块负责下载RIPE项目22个rrc（Route Reflector Client）的UPDATE数据。原始的UPDATE数据是以二进制的形式存储的，本模块使用RIPE提供的解析工具libBGPdump，把报文解析成可阅读的形式。模块将解析后的文件存入Hadoop。

　　UPDATE存储模块：Hadoop是一个软件框架，它的作用是方便使用简单的程序在大量的计算机上对数据集进行分布式处理。本文分析了RIPE项目一个月的UPDATE数据，数据文件大小为417.6GB。由于要从较大规模数据中发现BGP异常特征规律，所以需要一个可靠的、高效的数据存储模块。

　　BGP Stream异常事件源：BGP Stream收集了BGP网络中有关路由劫持和路由泄露的免费资源。BGP Stream使用自动化方法选择最大和最重要的异常。提供异常信息包括异常类型，涉及的IP地址前缀、AS号、发生时间等。

　　事件采集模块：本模块使用Python实现了爬取BGPStream收集的异常事件，一起异常事件可以用三元组的方式描述：[prefix，time，type]。prefix表示受影响的IP地址前缀，time表示异常的发生时间，type表示异常类型。

　　Spark特征计算模块：Spark是一个基于MapReduce的快速的通用的大规模数据处理引擎。Spark建立在统一抽象的RDD之上。RDD是一个容错的、并行的数据结构。RDD提供了map、filter、reduceByKey等数据操作方式。本模块从Hadoop中读取BGP UPDATE报文，结合从事件采集模块收集的异常事件，分析若干异常特征。本研究将时间区间划定为一天，分析器将统计异常发生当天的特征数据。系统架构如图1所示。

　　特征选择和计算方法

　　当一个BGP路由器发生异常时，其余的BGP路由器会为失败的路由重新进行路由选择算法。在路由重新选择的过程中，BGP路由器会发布路由宣告和撤回消息。这些更新信息可以帮助我们发现BGP异常的特征规律。下文将讨论以下特征以及其计算方法。

　　宣告/撤回数量

　　在过去大规模的BGP路由异常事件中，通常路由的不稳定性会表现在UPDATE报文中的宣告和撤回数量上。所以本研究将宣告和撤回数量作为一个BGP异常事件特征。宣告和撤回数量特征计算公式如下：

　　AVi和WVi表示事件集合中编号为i的事件宣告/撤回数量。RIPE项目22个rrc每五分钟对外发布一次UPDATE报文文件，每个rrc每天生成288个报文文件。Xij和Yij代表着一个报文文件中的宣告/撤回数量序列。ENUM表示事件集合中的事件数量。

　　重复宣告/隐式撤回

　　宣告的类型可以分为三种。如果一条宣告声明了一个原来不可达的IP地址前缀，那么这条宣告被称作新的宣告。如果一条宣告声明了一个可到达的IP地址前缀，并且具有相同的路由，即UPDATE中PREFIX域和AS-PATH域相同，那么这条宣告被称作重复宣告。如果一条路由替换了当前的路由，即PREFIX域和AS-PATH的源相同，但是AS-PATH发生了变化，那么这条宣告被称为隐式撤回。当BGP路由异常发生时，路由处于不稳定的状态，有时会伴随重复宣告和隐式撤回。重复宣告计算公式如下：

　　DAVi表示事件i的重复宣告数量，PATHi是事件i所有UPADTE中所有AS-PATH。上式证明了重复宣告数量等于宣告数量与路径集合大小的差。

　　隐式撤回IWVi的计算，需要基于路由表的状态，可以根据BGPUPDATE来维护路由表状态。隐式撤回的计算方法如下：

　　步骤1 收集PREFIX域为prefix（i），TIME域为time（i）的宣告UPDATE。

　　步骤2 将UPDATE按照（前缀，采集点，源）为键值，（时间，路径）为值分组。

　　步骤3 分组后，对于每一个分组，都产生一个（时间，路径）的序列。对每个序列应用如下算法：

　　步骤3.1 对元组序列按照时间升序排序。

　　步骤3.2 pre_path用于记录分组路由，implicate_num用于记录分组隐式撤回数量。算法1具体阐述求一个分组隐式撤回数量方法，如下所示。

　　算法1：求单个分组隐式撤回数量

　　输入：按照时间排序的（time，as-path）元组序列输出：隐式撤回数量implicate_num

　　pre_path=nullimplicate_num=0

　　FORtupleINlist：

　　IF path==pre_path：

　　CONTINUE

　　ELSE：

　　implicate_num=implicate_num+1pre_path=path

　　RETURNimplicate_num

　　步骤4将所有分组隐式撤回数相加，得到IWVi。

　　AS源数量

　　AS源数量是一个判定BGP路由异常的重要指标。多源自治域系统冲突发生当一个特定的IP地址前缀被超过一个AS自治域宣告为源。IP地址前缀的源可以从UPDATE的AS-PATH域获得，AS-PATH从左往右的最后一个节点为前缀的源。AS源数量指标是计算时间窗口内，事件前缀不重复的源个数。AS源数量计算公式如下：

　　MUASi为事件i的AS源数量，pathi（-1）表示事件iUPDATE中AS-PATH域路径从左往右第一个AS的集合。

　　宣告类型

　　UPDATE宣告中的ORIGIN是一个必须存在的字段，它定义了AS-PATH路径起源的信息。ORIGIN的值有以下三种：

　　IGP：网络层可达性信息来自ORGINAS内部。

　　EGP：网络层可达性信息获得通过EGP协议。

　　INCOMPLETE：网络层可达性信息获得来自其他渠道。

　　路径长度

　　当BGP重新选择路由时，路径长度有很大概率会发生改变。尤其当发生路由劫持或者路由泄露时，路径长度的变化会更加明显。路由劫持发生时，原有的路由线路不再可用，BGP路由器会尝试新的替代线路。路由泄露发生时，虽然IP地址前缀所属的AS没有发生变化，但是由于路径中间AS的转发策略配置不当，违反了Valley-free的商业关系，往往会导致路径长度变得更长。路径长度特征计算公式如下：

　　PLij表示标号为i的异常事件，路径长度为j的数量。同样Xij表示一组报文数量的序列。MPL表示最大路径长度。

　　路径编辑距离

　　当BGP路由异常发生时，路由处于不稳定的状态，采集点会检测到大量来自同一AS源但路径却不相同的宣告。编辑距离是一种反应两条路径差异程度的量化特征指标，量化方法是一条路径经过至少多少次操作可以变成另一条路径。操作方式包括添加一个AS节点、删除一个AS节点，替换一个AS节点。例如路径[1，3，2，5，4]和路径[1，3，6，4]的编辑距离为2，前者通过将2替换成6，删除5，两次操作可以得到后者。两条路径的编辑距离求解有基于动态规划的多项式时间复杂度求解算法，状态转移方程如下：

　　d（i，j）表示长度为i的一条路径（记为p）与长度为j的一条路径（记为p）的编辑距离。如果P（i）=P（j），则不需要任何操作，状态转移到（i-1，j-1）。

　　基于路径编辑距离求解算法，我们定义最大路径编辑距离特征如下：

　　PDLi表示编号为i的事件的最大编辑距离。对于同一IP地址前缀，采集点编号为j，宣告源编号为k。按照（i，j，k）对宣告进行分组，D表示组内最大编辑距离。p，q表示组内两条宣告路径，d表示两条路径的编辑距离。