一、文章信息
作者：Tongqing Qiu, Lusheng Ji, Dan Pei等
单位：佐治亚理工学院、美国电话电报公司实验室、康奈尔大学等
来源：Conference on Usenix Security Symposium
时间：2009年
二、主要内容
本文提出了一种鲁棒性良好且支持增量部署的定位前缀劫持者的轻量级机制——LOCK。LOCK基于两条重要的事实：一是劫持者不能操控未到达自己的AS路径，二是到受害前缀的路径会在劫持者附近形成“收敛”。具体方法是在网络中分布式的部署monitors来监控控制/数据平面的到受害前缀的路径变化情况，结果显示LOCK区分前缀劫持者的准确率高达94.3%。本文贡献有以下四点：
- 截至本文发表前，我们率先研究了劫持者定位问题；
- LOCK使用数据平面和/或控制平面信息，使部署更为灵活；
- 提出了一种算法选择收集控制/数据平面数据的位置，能更有效定位劫持者；
- 在若干PlanetLab点上部署了LOCK，并且实施了三类实验场景用以评估LOCK的性能：一是从互联网收集真实的路径和拓扑信息来模拟综合攻击；二是重造以前发生过的著名攻击；三是在互联网上实施受控的攻击实验。
三、背景
当由于误配置或恶意BGP路由器产生/宣称不属于它自己的IP前缀，我们就说此时发生了IP前缀劫持。AS收到这类错误通告的BGP报文后，或许会接受并进一步传播错误路由，路由器的路由表会受到“污染”，从而将会使原本应该到受害前缀（目标前缀）的流量重定向到攻击者。按惯例我们将前缀劫持分为三类：
- 黑洞：攻击者只是简单地将劫持的包丢弃掉，并不做其它操作。
- 欺骗：攻击者模拟真实的目标前缀的行为，对发送者的报文作出相应的响应。
- 窃听：攻击者将被劫持的流量报文中的信息窃听后，再重新转发到目标前缀。
本文中的前缀劫持包括以上三种攻击类型，除非有特定说明。目前有一系列方法来检测前缀劫持，包括利用从控制平面收集的BGP更新报文中的信息，或利用从数据平面收集的端到端的探测信息，或结合二者的方法。不同的是，LOCK是一种劫持者定位机制而不是劫持检测机制，为了定位劫持者，LOCK仅仅只需要知道特定前缀是否被劫持，因此LOCK也能结合检测方法来进一步定位劫持者，此外，LOCK也能利用数据平面或控制平面信息来定位劫持者。
四、框架
与前缀劫持检测方法类似，定位劫持者也可以从数据或控制平面出发来解决。不管怎样，我们的目标是在monitors利用到受害前缀的AS路径信息来定位劫持者。在控制平面，AS路径信息来自于路由表或更新报文中，在数据平面，AS路径信息来自于AS级的traceroute命令（将IP地址映射为AS号）。正如所有的方法有利有弊一样，获取实时的数据数据平面信息要比实时BGP信息要容易一些，可同时，又容易被劫持者操控AS路径来反制定位算法。
4.1 挑战
目前，最常用的定位劫持者的方法是考虑目标前缀的源AS。如图1(a)所示，分别显示了在劫持者H攻击前，M1、M2、M3三个monitors的AS路径信息,它们都显示源AS是T；在图1(b)中，劫持者H宣称一条路径H能够到达目标前缀p，导致A、B、M1、M2接受了这条新路由，因为新路由要比之前（通过CDT）的要好。在这种情况下，常规的定位方法能很容易的鉴别出新出现的源AS号H是劫持者。但是在图1(c)中，这种常规的定位方法失效了。当劫持者H假装与自治域T之间有一条链路，并且声称AS路径为HT，然后又重新被A、B、M1、M2接受了这条路由，因为源AS依然是T，所以此时不能定位劫持者H。有人试图想除了检查源AS之外还要检查在路径中的其它AS信息，但是劫持者甚至能够不出现在AS路径当中来应对这种追查，例如，在图1(d)中，H伪装自己是拥有前缀p的T，这样H不会出现在路径中。
所有上述在控制平面出现的问题，在数据平面也同样会存在，几乎所有的数据平面探测机制都源于著名的traceroute命令，traceroute程序将不同的初始TTL值的报文发送到相同的目的地，当沿着路径转发至目的地的过程中，每经过一个路由器TTL值就会相应减1，当TTL值为0时，此时经过的路由器需要给探测源一个ICMP超时报文来告知它。当探测报文经过劫持者，并且此时初始TTL值远大于源到劫持者的hop距离时，劫持者有很多方法干扰路径探测，进而来应对这种定位算法。在下图2（a)中，劫持者H的边界路由器在黑洞和欺骗这两类前缀劫持情况下，会真实地响应traceroute命令。在这两种情况下，路由地址都属于H，并且映射也为H，简单的定位方法能够确定H是新出现的源AS，因此H是劫持者。然而，在如图2（b）所示的窃听攻击中，劫持者H通过XYZT路径来进一步传播traceroute探测包，由于此时源AS依然还是T，所以此时方法失效。更进一步地，劫持者也可以简单的丢弃触发报文并不作相应的响应，来进一步干扰traceroute探测。或者，它可以用任意源IP地址发送ICMP超时消息，以欺骗探测源，使其认为这些地址的路由器正在路由到目的地。劫持者甚至可以在TTL值为0之前就向探测源发送ICMP超时消息。在图2（c)中，劫持者H操纵traceroute响应，在IP-AS映射之后，M1的AS路径为ACDT，M2的AS路径为BDT，这都不包含劫持者H，导致定位劫持很困难。
4.2 定位劫持者
LOCK机制基于两条重要的观察，能够适应于数据平面和控制平面，不同种类的劫持，以及劫持者是否参与反制应对的情况。第一条观察是：劫持者不能操纵从被污染的vantage位置到劫持者“上游”（更靠近vantage位置）邻居的部分AS路径。在图1（c）（d）和图2（b）（c）中，对被污染的vantage位置M1和M2而言，劫持者H的上游AS是A和B，并且M1A和M2B是值得信赖的。第二条观察是：从多个vantage位置到受害前缀，可信的部分受污染AS路径会在劫持者附近形成“收敛”。本文重点关注劫持者的上游邻居的鉴别，直觉上，劫持者应该在劫持者邻居的1-hop邻居集合的交叉点位置，并且如果monitors分布得足够均匀的话，交叉点集合的规模应该很小。对于给定AS的邻居集可以从AS级的拓扑信息得来。在图1和图2中，假设我们知道A和B（它们分别位于vantage位置M1和M2的受污染路径上）是劫持者的上游AS，那么我们可以猜测劫持者应该属于A的邻居集合neighborset(A)={M1,B,H}和B的邻居集合neighborset(B)={M2,C,H}的交集，很显然，二者的交集是H。但是，通常我们并不知道劫持者的上游邻居AS是谁，所以，在受污染路径上的每一个AS都有可能是劫持者的上游邻居AS，也就是说劫持者存在可能与任一个AS相邻的可能性。我们依此建立一条路径的邻居集合，这个集合包括此条受污染路径上的每一个AS及其所有的邻居，显然劫持者本身必然包含在这个集合中。LOCK将所有污染路径的邻居集合合并，并假设所有的污染路径都经过了劫持者的邻居AS，那么理论上某个AS出现在集合中的次数越大，它就越有可能是劫持者。接着我们按照集合中出现的次数来进行排序，就会得到最大可能的几个“收敛点”，即可能的劫持者，排序越靠前，是劫持者概率就越大。
五、monitor的选择
LOCK是利用互联网上分布式部署的monitors来工作的，monitors的数量和分布位置都会影响定位劫持者的准确度，通常来说，monitors数量越多，LOCK能够达到的准确度也就越高，但与此同时带来的开销也会更多，这种开销增长与monitors的数量增长呈线性相关，但获得的准确度提升量却很少，所以我们必须选取合适数量的monitors来兼顾准确度与开销这两方面。这一部分我们提出了新颖算法来从候选集中选择一定数量的monitors，我们对monitor的选择问题建模如下：一开始，我们有M个候选monitors，对于每一个目标前缀，从这M个monitors中选择一个包含m个monitors的子集。为了在基于一定数量的monitors情况下能够达到最大的定位准确度，monitors的选择必须有两项要求：第一是能最大可能性地能观察目标前缀的劫持事件，第二是monitor到目标前缀的路径尽量要多样，这样劫持事件就能从不同的路径角度来分析。我们的monitor选择算法由以下三个部分组成：
- 聚类：从M个候选monitors中分成m个类，类内的monitors到目标前缀的路径相似度要更高一些，相反，类间的monitors彼此的路径相似度差异化要大一些。
- 排序：每一个类中的候选monitors按照其受到污染可能性的大小进行排序，受污染可能性越大，观察来目标前缀劫持事件的可能性也就越大。
- 选择：按照上述排序算法，从每一个类中选择排序第一的monitor，这样，有m个类，我们就能得到m个monitor。
5.1 聚类
给定目标前缀，候选monitors聚类标准基于各自到目标前缀的AS级路径的相似度。一对路径的相似度定义为：以其中最短一条路径为标准，它们包含的相同AS数量，如果没有共同的AS，那么相似度为0，如果一条路径是另一条路径的子集或者彼此完全相同，我们就说相似度为1。我们同样定义类间的相似度：分别从两个类中任意取出一条路径，两条路径的相似度的最大值即为这两个类的相似度。我们定义聚类这部分是分层聚类问题，这类问题有著名算法如层次聚类方案（Hierarchical Clustering Schemes)，其具有多项式时间复杂度。本文中，我们采用如下简单的聚类算法：第一步，从M个monitors出发，初始构造M个类，每个类只包含一个monitor；第二步，计算每一个类的类间相似度，将其中相似度最大的两个类合并；第三步，重复第二步方法，直到最后只剩下m个类结束。
5.2 排序
我们在每一个类中，基于能观察对给定目标前缀t发生劫持事件的可能性的大小来对候选monitors进行排序。相关研究指出，对于一个给定的位置s，从s到t的路由是否被劫持者h污染，依赖于原始最优路由和由h宣称的虚假路由。我们假设当今互联网的路由策略都遵循"prefer customer route"和"valley-free routing"，根据s到t的原始最优路由的下一跳AS与s的商业关系分为客户、对等体和提供者，我们将从s到t的原始最优路由分别标记为客户路由，对等体路由和提供者路由。根据域间路由协议，客户路由优先级大于对等体路由大于提供者路由，并且其它路由策略一样时，AS路径更短的优势更大。因此，当劫持者h宣称一条虚假路径时，原始最优路由是提供者路由的monitors最容易被污染，对等体路由次之，客户路由最末。其它策略相同时，AS路径长的比短的更容易被污染。（读者不妨思考一下为什么会这样，哈哈哈，参考下表）。我们的排序算法如算法1所示（个人认为算法格式是真的差，就不能换个行吗？并且算法本身也很粗糙）。注意到建立AS的拓扑关系本身也是一个具有挑战性的问题，我们利用相关技术来推测AS关系，显然这样得到的结果不会很完整，但是后面的评估部分会证明排序算法依然会得到较高的定位准确率。
六、劫持者定位算法
LOCK机制定位劫持者基于从monitors到受害前缀的AS路径，这可以从控制平面来获得，如BGP的AS路径，也可从数据平面来获得，如traceroute路径。在数据平面，LOCK机制需要进行预处理然后计算相应的AS路径。
6.1 预处理
劫持发生后，互联网的一部分到受害前缀的流量将会经过劫持者，部署在被劫持位置的monitors将会知道它们的monitor-to-prefix被改变，这些monitors就是劫持者定位算法的基础。有研究帮助我们区分真实劫持导致的路径改变与非劫持导致的路径改变。如果monitor-to-prefix路径来源于数据平面，LOCK将对路径进行预处理，通常在数据平面上需要IP地址进行转发的是traceroute，有关traceroute的讲解可参考我另一篇博文，在此不再赘述。利用traceroute得到的路由级路径需要转换为AS级路径，在转换过程中，traceroute结果中的空记录将会被简单的丢弃掉，这种简化不会对最终结果有太大影响，因为只有当这个AS内的所有路由器对traceroute命令都失效时，才会对结果有影响，而这种情况是极少发生的。通过这种转换得到的路径我们称之为"reported paths"。通过iPlane服务能将IP地址映射为对应的AS，由于IXPs和sibling AS的存在，要实现很精确的结果几乎是不可能的，我们认为这对我们的算法影响是很小的，原因如下：第一，路由或AS这些节点的分布，能够导致映射错误的情况是很少的，如果我们的路径不包含有问题的节点，我们的结果不会受到映射错误的影响；第二，是由我们算法的鲁棒性决定的，只要这些映射错误的节点不在劫持者附近，同样不会带来影响。另外由于短时间内IP与AS的映射一般不会有改变，所以我们可以预先计算和存储，不需要实时的从控制平面获得。如果traceroute触发消息确实经过劫持者，劫持者也可以伪造traceroute结果。考虑到前缀已经被劫持了，携带足够大的初始TTL值的触发消息，至少大于从monitors到劫持者的跳数，这很显然地将会经过劫持者。劫持者可以利用这点来伪造对触发消息的响应来隐藏它自己的身份，所以，从这类虚假traceroute结果映射而来的AS路径将会包含错误的AS，不妨称之为“噪音”。因此，如果路径中的某个结点被判断为虚假节点，那么我们不必考虑此条路径上超过这个节点的任何节点，因为这个虚假节点的位置必然已经超过了劫持者的位置。在预处理部分，我们也考虑了AS节点的重复出现问题，如果某条路径上至少出现两次相同的AS，那么超过此AS第一次出现位置的所有节点都是虚假的，这是因为真实的traceroute结果不会含有循环。
6.2 基本算法
对于每一个monitor，都存在一个对应的AS级的monitor-to-prefix路径pi，不论是由traceroute路径计算而来还是直接从BGP路由器得来。定义路径pi的邻居集N(pi)为路径上所有节点及其与之相距一跳的所有邻居AS的并集。因为目标受害前缀所属的AS必然不是劫持者，所以我们从N(pi)上将其去掉。注意到在劫持发生前，LOCK是基于从RouteView推测的AS拓扑来计算邻居集，而不是从劫持发生时实时的BGP数据推测而来。尽管劫持者在攻击前能够污染AS拓扑信息，但是也不可能污染所有的路径。
/ *后文都是一大堆公式符号，作者作了改进并评估了效果，在此略去几千字 */