基于AS-Path混淆的域间路由隐蔽通信方法

王 禹，高继勋，王旭辉，葛 琳

(1.河南工程学院 计算机学院，河南 郑州451191；2.河南工程学院 工程训练中心，河南 郑州451191； 3.郑州航空工业管理学院 智能工程学院， 河南 郑州 450015)

边界网关协议(border gateway protocol，BGP)作为互联网实际的域间路由协议已运行多年，当前路由前缀劫持攻击(prefix hijacking)、路由泄露(route leak)、分布式拒绝服务攻击(distributed denial of service, DDoS)，以及针对BGP的低速拒绝服务攻击(BGP low-rate denial of service,BGP-LDoS)均成为影响互联网域间路由系统安全的主要威胁。其中，BGP-LDoS攻击针对目标域间路由系统区域，实施关键路由节点的监测和判定，之后利用僵尸网络对关键节点及其周边节点进行低速拒绝服务攻击。为了防范BGP-LDoS攻击者对于域间路由系统中自治系统(autonomous system，也称自治域)通信行为的窥测，学者们已开展了诸多研究[1-3]。

目前，大多数研究关注于如何监测和发现BGP-LDoS攻击迹象，属于被动防御范畴，研究往往受到攻击方案和技术变化的制约。因此，借鉴主动防御的思想，本研究提出了一种基于多域联盟的域间路由隐蔽通信(covert communication)技术，通过构建并维持多自治系统的联盟关系，以协同配合的方式重新配置对外Update数据包的AS-Path属性，达到隐藏联盟内域间路由通信的目标。

1 网络隐蔽通信

网络隐蔽通信技术是指在网络环境中利用信息载体的不同特性或模式完成信息的隐蔽传输，这一概念自诞生起，其相关研究逐步涉及信息安全的多个领域。从最初基于TCP协议的网络隐蔽通道，到基于HTTP报文的隐蔽通道，甚至还有研究者利用第一人称射击网络游戏来承载隐蔽通信[4]，应用非常广泛。

(1)基于动态路由的隐蔽通信技术[5]是指利用随机方式选择通信的下一跳，使得整个通信路径上的节点均是随机抉择，进而规避了受到潜在攻击者监控和预测的风险。

(2)基于多协议的隐蔽通信技术[6]是指事先预备多种通信协议，将数据载荷(payload)经过分片置于多种不同的协议报文中，使得第三方难以截获所有协议下的全部报文，从而提高了通信的隐蔽性。

(3)基于调频通信的隐蔽通信技术[7]是指通过预先设定调频序列与多种协议构成的隐蔽信道，利用伪随机码生成跳转指令，从而使通信双方的频率保持一致，同步在不同协议下的隐蔽通信中予以转换。

(4)基于多连接的隐蔽通信技术[8]是指通信双方事先建立多条活跃的连接，以发送顺序与传输模式的不同来发送数据包，使得该隐蔽通信脱离了固定的信道条件，同时不涉及特定的统计特征。

然而，目前仍缺乏针对域间路由系统中隐蔽通道技术的研究，需要结合域间路由系统通信的特点，在不影响自治系统之间正常通信的情况下，建立隐蔽通信模型，从而减少恶意自治系统发起BGP-LDoS攻击的可能。

2 Update报文的AS-Path属性

BGP即边界网关协议，负责在自治系统之间传递并选择最佳路由。BGP协议包含5种报文类型：Open、Keepalive、Update、Notification、Route-refresh。其中，若BGP报文头中的Type为2，则为Update类型报文可用于通告路由。Update报文中的内容如图1所示。

图1 Update报文结构Fig.1 Structure of Update

路径属性(path attributes)是对BGP路由的特定描述，是每个BGP数据包的一部分，描述了前缀的路径信息。BGP路由表中有可能包含到达同一目的地的多条路由，此时BGP协议需要选择其中一条路由作为最佳路由。

BGP决策进程将属性和所描述的前缀路由结合在一起，根据BGP的路由优选规则，对所有可达目的的网络备选路径属性予以比较，经过判定和筛选得到最佳路由，据此进行数据转发，并在该时间阶段将此路由告知其对等体。

BGP作为一种路径向量协议，以自治系统(autonomous system, AS)为节点，通过记录数据包的转发轨迹，形成一个AS列表。因此，该列表包含了数据包从起始AS至终点AS过程中所经过的所有节点，BGP路由生成的这一列表被称为AS-Path序列。

需要注意的是，数据包在本地AS内传输时，不会对AS-Path属性内容做任何修改。当数据包离开本地AS时，当前自治系统编号(autonomous system number, ASN)会被自动添加到AS-Path序列的最前端位置。任何路由设备在接收Update数据包时，均会检查AS-Path属性内容，倘若该AS-Path序列中含有接收者路由器所在的AS号，则丢弃这一路由从而避免环路。此外，路由设备可以根据AS-Path的长度来制定最佳路由的选取策略。

因此，AS-Path路径属性作为公认必遵属性，主要作用为记录路由沿途所经过的自治系统，BGP对等体之间传递的每条路由都会携带这份AS编号列表继续传递和更新路由。

3 基于AS-Path混淆的路由隐蔽

考虑到互联网中自治系统间的正常通信需求，为了能够抵御BGP-LDoS等攻击对于关键自治系统节点的监听、分析与判别，借鉴移动目标防御技术的主要思想，针对多自治系统联盟的路由行为实施隐蔽。

首先需要构建多自治系统联盟框架，以联盟为整体单元提升其内部路由的隐蔽性，然后依靠联盟内部各自治系统之间的协同配合，通过重新配置联盟对外Update数据包的AS-Path属性，最终达到迷惑外部潜在攻击者的目标。

3.1 基于社团特征的多自治系统联盟

诸多研究已经证明，互联网中的AS级域间路由系统具有显著的社团特性[9-10]，主要表现如下：社团内部各组织联系紧密，社团外部联系松散；社团内AS节点的地理位置靠近；社团内AS节点通常具有较为一致的利益关系。

张国强等[11]从社团分解的角度，利用CNM算法获得互联网中的多个社团。CAIDA对2012年1月至8月每日的域间系统路由数据进行了分析和统计[12]，依照社团特性予以社团划分。其中：这7个月内社团模块度的平均值为0.681，最小值为0.675；在社团数量方面，由于不同时间段内路由的变化，以及AS节点连接信息采集得不完整，故社团数量出现一定的波动，为43～54。综合上述文献发现，60%以上的社团规模小于100个节点。

考虑到域间路由系统在AS级拓扑结构上存在典型的社团特性，为了更好地应对域间路由系统攻击，尤其是BGP-LDoS对于拓扑关系的探测，本研究提出了一种轻量级的方法，结合互联网中实际业务和商业利益的需求，将域间路由系统中已经具备典型社团特性的多个自治系统组建成面向域间路由安全的自治系统联盟(见图2)，通过自治系统节点间的相互配合，对联盟外部路由设备及节点隐藏真实的路由信息，从而提升整个联盟的攻击抵御能力。

图2 自治系统联盟示例Fig.2 Example of AS alliance

以图2为例，将本身具有社团特征的、编号为1～10的自治系统组织为联盟。假设该联盟的边界节点是编号为1、2、8、9的4个自治系统，联盟外部连接的自治系统包括A、B、C、D、E等。

3.2 AS-Path属性重配置

正常情况下，AS-Path属性中包含的序列是有序的，体现了数据包通信的整个过程，不应对该路径实施任何修改或删除行为，以保护AS-Path的完整性与无环性。然而，有时网络运维管理人员为了增加序列的长度，进而影响远端路由设备的路径选择，会刻意添加重复的AS号。

针对域间路由系统中路由行为隐蔽的问题，同样可以参考网络运维管理人员的方法，通过重新配置AS-Path列表，对多自治系统联盟外暴露出虚假AS序列，使得外部自治系统，尤其是恶意者，无法获知联盟内部通信的方向，从而掩盖联盟内自治系统的拓扑关系、关键自治系统的位置、链路权重等重要信息。为了兼顾计算性能和隐蔽效果，本研究提出了基于AS-Path序列混淆的域间路由系统路由隐蔽方法，通过对AS-Path序列的重配置实现欺骗效果。

目前，众多混淆算法的核心思想是将有序数列按照随机化的方式重新进行排序，其优势在于计算复杂度低、反应迅速。结合已有的混淆算法，本研究提出的面向自治系统联盟内AS-Path序列混淆算法如下所示：

输入：原始的真实AS-Path序列AP_Org；输出：经过重配置的AS-Path序列AP_Ult。

步骤如下：

①假定原始序列AP_Org的长度为n，其中AP_Org[0]为首自治系统编号，AP_Org[n-1]为末端AS编号，二者不介入混淆；

②复制AP_Org至AP_Ult，目的是保证之后的操作不改变原始序列；

③将AP_Ult索引为i的AS编号随机覆盖至索引k处；

④将AP_Org索引为k的AS编号拷贝至AP_Ult索引i处；

⑤重复第③～④步骤n-2次，直至所有AS编号完成初始混淆；

⑥对AP_Ult中的AS编号进行随机丢弃，数量控制在[1,n/2]。

该算法能够保持真实AS-Path路径的入口和出口，同时以时间复杂度为O(n)、空间复杂度为O(n)计算获得混淆后的序列。为了防止潜在攻击者对序列进行大量采样和分析，需要在最后一个步骤中随机缺省若干AS编号，进而提高隐蔽效果。

图3 基于序列混淆的AS-Path重配置示例Fig.3 Example of AS-Path reconfiguration based on sequence confusion

基于序列混淆的AS-Path重配置示例见图3。如图3所示，假如以AS编号2为流量入口、以AS编号9为流量出口，该原始AS-Path序列应为[2,10,5,3,4,6,7,9]。由于多自治系统联盟具有相对程度的黑箱特性，所以利用上述混淆算法，外围观测者最终得到的AS-Path结果同真实的序列在ASN顺序和数量上均不相同。并且，由于随机数的变换，具有相同入口和出口的重配置AS-Path也不尽相同，从而实现了对联盟外部的隐蔽功能。

4 仿真实验

4.1 时间耗费测试

利用基于AS-Path混淆的路由隐蔽算法，生成混淆AS-Path序列，对联盟外攻击者实施隐蔽。Avramopoulos等[13]研究表明，多自治域社团具有小规模数量的特征，以此来构建区域性域间路由系统联盟，能够较好地满足通信隐蔽性。

图4 基于序列混淆的AS-Path属性重配置计算时间Fig.4 Duration of AS-Path reconfiguration based on sequence confusion

在AS-Path序列长度分别为20、50、100、200、400、600的情况下，计算100次后的平均混淆计算时长，结果见图4。由图4可知，整体上其耗费的时间呈线性分布，符合预期的计算时间复杂度O(n)。在上述情况下，仅当序列长度为50时，计算时长的增长幅度略微下降，但总体增长趋势非常显著。

4.2 相似度测试

为了验证所提基于序列混淆的AS-Path重配置算法的有效性、判别混淆程度和影响，拟利用Levenshtein算法计算混淆前与混淆后两个AS-Path序列的编辑距离，进而获得前后序列之间的相似度。

原始序列记为APs，长度为m，混淆后序列记为APf，长度为n，令APs[i]表示原始序列中第i个ASN，APf[j]表示混淆后序列中第j个ASN，编辑距离记为Dist(APs,APf)。

利用Levenshtein算法，计算APs与APf序列的相似度，记为similar(APs,APf)，计算公式为

(1)

在AS-Path序列长度分别为20、50、100、200、400、600的情况下，计算100次后的平均相似度，结果见图5。

图5 基于序列混淆的AS-Path序列相似度比较Fig.5 Similarity comparison of AS-Path based on sequence confusion

由图5可知，随着序列长度的增加，混淆前和混淆后AS-Path的相似度在不断降低。例如：当序列长度为20时，混淆100次，得到平均相似度为0.653；当序列长度达到600时，运行100次得到平均相似度为0.317。可以得出，混淆后的AS-Path能够显著区别于原始序列。

4.3 方法比较

由上述内容可知，基于AS-Path混淆的域间路由隐蔽通信方法(简称APR)针对原始序列具有较好的相似度差异特性，拟将该方法同已有方法进行比较，挖掘其优势与劣势。文献[14]提出了一种典型的乱序方法RL，可在不同的序列长度下比较二者的相似度，具体见图6。

图6 两种方法的相似度比较Fig.6 Similarity comparisons between two methods

如图6所示，当AS-Path序列长度分别为100、200、400、600时，给出了实施APR方法和RL方法100次之后的平均相似度值，可以看出：在AS-Path序列较短时，APR方法计算的相似度较大，而RL方法计算的相似度较小；当AS-Path序列长度为100时，APR方法的相似度为0.53，RL方法的相似度为0.34；随着AS-Path序列长度的增加，APR方法的性能优势逐步显著。例如，当AS-Path序列长度为600时，APR方法的相似度为0.317，RL方法的相似度为0.482。

通过对两种方法的比较可知，在AS-Path序列较大的情形下，依据基于AS-Path混淆的域间路由隐蔽通信方法，同原始序列相比，计算出的混淆序列具有较低的相似度，能够满足对于联盟域外恶意者的伪装欺骗。

5 结语

在互联网域间路由系统中实施安全防护具有较大难度，一方面是由于路由系统本身具备的开放特性，攻击者始终躲在暗处，双方掌握的信息极其不对等，另一方面是因为攻击者能够采用的手段和方法愈加多样化，能够利用各种方法不断尝试并实施威胁。由此，以主动防御思想为指导，本研究提出了一种基于AS-Path属性重配置的路由隐蔽方法，在构建多自治系统的基础上，通过对AS-Path属性进行重新配置达到欺骗潜在攻击者的目标，仿真实验和比较结果显示该方案具有较好的效果。