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

文/陆岳昆 张沛 李丹丹 马严

针对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实现了爬取BGP Stream收集的异常事件，一起异常事件可以用三元组的方式描述：[prefix,time,type]。prefix表示受影响的IP地址前缀，time表示异常的发生时间，type表示异常类型。

图1 系统架构

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域和ASPATH域相同，那么这条宣告被称作重复宣告。如果一条路由替换了当前的路由，即PREFIX域和AS-PATH的源相同，但是AS-PATH发生了变化，那么这条宣告被称为隐式撤回。当BGP路由异常发生时，路由处于不稳定的状态，有时会伴随重复宣告和隐式撤回。重复宣告计算公式如下：

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

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

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

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

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

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

步骤3.2 pre_path用于记录分组路由，implicate_num用于记录分组隐式撤回数量。算法1具体阐述求一个分组隐式撤回数量方法,如下所示。RETURN implicate_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：网络层可达性信息来自ORGIN AS内部。

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

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

不同的值在BGP路由选择算法中有不同的权重，如果AS-PATH相同，优先选择低等级的ORIGIN类型，优先等级IGP＜EGP＜INCOMPLETE。不同的异常发生可能在宣告的类型上也有区分。宣告类型特征计算公式如下：

ATij为事件宣告类型为j的特征值，ATij的含义是j类型宣告的比例。

路径长度

当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的一条路径（记为p1）与长度为j的一条路径（记为p2）的编辑距离。如果P1(i)=P2(j)，则不需要任何操作，状态转移到(i-1,j-1)。

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

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

特征采集结果分析

图2 宣告数量。横轴表示宣告数量的对数值，纵轴表示对应概率分布函数值F

本研究基于系统结构设计，对提出的小范围BGP异常特征，按照所述定义与计算方法进行了实际采集与分析。其中UPDATE更新报文来自RIPE项目中采集，数据规模包括其全部22个rrc数据。本研究异常事件数据来自BGP Stream，一共考察了259起路由劫持事件和523起路由泄露事件。未被BGP Stream通报的IP地址前缀，其相关UPDATE被视为正常。本研究随机抽样了1000起正常事件，用于参照。正常事件同样用三元组（prefix，time，type）表示。大部分小范围BGP异常发生事件不超过一天，同时要考虑到BGP Stream通报异常发生时间和相关UPDATE收集时间，为了保证相关指标能够被有效采集到，本研究选用24小时作为事件的采样时隙。

图2比较了路由泄露、路由劫持和正常情况下宣告数量。

图2结果表明整体宣告数量上正常情况＜路由劫持＜路由泄露。正常情况下前缀的宣告数量集中在数量级以内（75.82%）。路由劫持事件发生时，有一定比例（47.32%）宣告数量在数量级以上。路由泄露事件发生时，前缀的宣告数量集中在至（80.15%）。图2三条曲线形态有较大差异，表明当小范围BGP异常发生时，宣告数量与正常情况有较大区别，同时路由泄露和路由劫持在宣告数量这个特征上有较高区分度。

图3 撤回数量。横轴表示撤回数量的对数值，纵轴表示对应概率分布函数值F

图4 重复宣告。横轴表示重复数量的比例，纵轴表示对应概率分布函数值F

图5 隐式撤回。横轴表示隐式撤回数量的比例，纵轴表示对应概率分布函数值 F

图3比较了路由泄露、路由劫持和正常情况下撤回数量特征值。从图3可以看出，正常情况下，一个前缀不会在短时间内出现大量的撤回，87.19%前缀撤回数量小于101。当路由发生时，撤回的数量这一比例开始下降，只有38.83%的被劫持前缀撤回数量小于101。路由泄露在撤回数量这一特征上与前两者有着更明显的差别，特征值集中在105的数量级上。

图4比较了路由泄露、路由劫持和正常情况下重复宣告比例。从图4可以看出无论是路由劫持还是路由泄露发生时，在重复宣告数量这一特征上不会产生明显变化。

图5比较了路由泄露、路由劫持和正常情况下隐式撤回比例。

当BGP路由异常发生时，隐式撤回的比例要小于正常情况。这表明异常会伴随着连续的重复宣告。根据前文关于重复宣告和隐式撤回的定义，两者的区别在于重复宣告没有对UPDATE按照时间排序，而隐式撤回考虑到了UPDATE的到达先后顺序。比较图4和图5正常情况下的曲线，两条曲线是相似的。这说明正常情况下，相同的宣告产生与时间这一因素无关的。而异常情况下宣告方式与时间因素相关，可以分为两个阶段：第一个阶段产生大量宣告，这些宣告大多互不相同；第二个阶段开始连续产生相同的宣告。

表1 AS源数量

表2 宣告类型

图6 路径长度

图7 最大路径长度

表1比较了路由泄露、路由劫持和正常情况下AS源数量。对于正常情况和路由泄露，几乎所有前缀只会有一个AS源。但是四成的被劫持前缀被观测到在短时间内出现多个AS自治域相互“争夺”一个IP地址前缀的现象。在AS源数量这一特征上，路由劫持异常具有显著性。

表2比较了路由泄露、路由劫持和正常情况下宣告类型比例。研究中没有发现带有EGP标识的UPDATE。同时与正常情况相比，当小范围的BGP路由异常发生时，宣告类型的比例没有发生明显变化。

图6比较了路由泄露、路由劫持和正常情况下路径长度。图6横轴表示路径长度，纵轴表示数量以10为底的数量级。可以看出，三种情况下UPDATE路径长度均集中在5附近（正常情况路径平均长度5.24，路由劫持4.64，路由泄露6.71）,稍有不同的是数量上正常情况＜路由劫持＜路由泄露。但是根据图7显示的结果，路由泄露发生时的最大路径长度显著大于正常情况和路由劫持。综上所述，虽然三种情况下整体路径长度分布相似，但是路由泄露异常更容易产生不合理的超长的路径。

图8路由泄露、路由劫持和正常情况下路径编辑距离。结果显示编辑距离特征和最长路径长度相似，与正常情况相比，路由劫持特征不显著，路由泄露的编辑距离要大于前两者。

图8 编辑距离。横轴表示编辑距离，纵轴表示对应概率分布函数值F

过滤式异常特征分析

北京邮电大学分别采集了BGP路由泄露、路由劫持、正常三类样本，数量一共1782起，特征维度一共个58维度，形成了一个的特征矩阵。BGP异常分析受特征之间的相关性和冗余所影响，同时采集的特征维度过多浪费了计算资源。Fisher算法和mRMR是两种常用的过滤式算法，用于解决特征相关性和冗余的过滤式方法。

1. Fisher过滤法

Fisher方法的关键思路是从特征中找出一些特征，满足这些特征在样本数据中，不同类别的数据点之间的距离尽可能大，而同一类的数据间的分数尽可能小。同一类别的数据的距离用类别方差和来描述，方差和越小说明对于该特征类别内数据越一致。不同类距离用特征均方和描述，均方和越大说明类别间区分度越好。Fisher分数实际就是前者与后者的比值。特征向量F={X1,X2…X58}，对于第r个特征，其Fisher分数公式如下：

其中c代表3种样本类型，nk代表第k类样本数量，μ代表对于特征r第k类的平均值，μr代表特征r整体平均值，σ 代表征r第k类标注差。

2. mRMR

mRMR方法的关键思想是最大化特征相对于目标类的相关性，同时最小化特征之间的冗余。mRMR方法基于互信息公式，对于两个特征Χk和Χl，其概率密度及联合概率密度为 p(Χk)、p(Χl) 和 p(Χk,Χl)。互信息的计算公式如下：

一般使用两种变体mRMR算法：相互信息差异（MID），互信息（MIQ）。MID和

表3 特征过滤

MIQ评分公式如下：

V(I)和W(I)分别为：

Fisher方法和mRMR方法分别计算分数，表3列出了前15名特征。从表中数据可以看出宣告/撤回数量、重复宣告/隐式撤回、AS源数量、路径长度均对异常分类具有帮助，宣告类型则没有帮助。路径长度的维度虽然有50维，然而对分类有帮助的的维度主要集中在长度小于20的维度。

基于本文讨论的小规模BGP网络异常特征的定义、采集方法和特征与异常类型的关联分析，未来的工作重点将是如何进行小范围BGP网络异常检测。

传统的BGP网络异常检测单模型的检测方法，例如De Urbina等人使用SVM方法进行BGP路由异常检测。Huang提出了基于PCA的检测算法。Deshpande提出了基于最大似然估计的检测算法。

单模型方法的缺陷在于很难在检测效率和准确度两者之间做出适当的平衡。本研究计划在未来采用双模型组合的异常检测策略，将本文采集的特征数据滤筛选后通过GBDT方法离线处理生成新的组合特征，然后使用LR逻辑回归的方法进行分类。如何将本研究结果运用到具体的异常检测算法中，将是今后的研究重点。

（责编：陶春）

为北京邮电大学网络技术研究院）