【作者】 邓文平；

【导师】 卢锡城；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2011， 博士

【摘要】 基于BGP(Border Gateway Protocol)的域间路由系统作为Internet的核心基础设施,在安全性与健壮性方面还存在诸多问题:一方面,它缺乏安全的协议机制和有效的监管手段,容易遭受各种攻击;另一方面,它的拓扑结构仍然存在脆弱性,端到端的连通性容易遭到路由设备故障、网络攻击以及自然灾害的破坏。研究域间路由系统的安全性与健壮性,对增强整个Internet的可靠性具有重要意义。本文面向域间路由系统安全性与健壮性领域的关键问题展开研究。针对其安全性,提出了基于模糊集理论的前缀宣告可信性评估方法,用于检测前缀劫持网络攻击;针对其健壮性,研究了Internet自治系统级(Autonomous System,AS)拓扑的健壮性测度与增强机制,并对与AS拓扑健壮性紧密相关的AS路径推断问题做了系统全面的分析。主要贡献和创新点包括以下五个方面:(1)对IP前缀宣告的可信性评估方法:多年来,前缀劫持事件时有发生并对Internet产生严重影响,其根源在于Internet对前缀劫持缺乏有效的防范措施与检测方法。本文提出了一种基于模糊集理论的IP前缀宣告可信性评估方法,从连续的历史路由表快照中提取“前缀-源AS”映射,根据它们的稳定性动态构造基本的“前缀-源AS”映射模糊可信集;基于基本的模糊可信集,进一步提出了对任意“前缀-源AS”映射进行可信性评估的方法。实验表明,本文方法的准确率达到99.85%,能有效检测与验证路由宣告中的前缀劫持。(2)域间路由系统的强度攻击和连锁故障模型:随着防火墙技术的发展和主机安全防护能力的提高,从数据平面对Internet实施大规模强度攻击(如蠕虫攻击)的难度大大增加。本文结合复杂网络的耦合共振机制,设计了一种通过控制平面对Internet实施路由强度攻击的方法;提出了路由强度攻击下的连锁故障模型,对域间路由系统在路由强度攻击下的连锁故障反应做了全面的刻画与模拟。实验模拟结果表明,从控制平面对域间路由系统的路由强度攻击可引发大规模的连锁故障并对Internet的连通性造成严重的影响,但在部分节点对强度攻击具有免疫力的情况下,域间路由系统的健壮性将显著增强。(3)全局AS拓扑的k-容错模型:网络的k-容错是指在任意k个节点或者链路发生故障的情况下,剩余网络中的任意节点对之间仍然相互可达。受路由策略的约束,用传统的简单图理论已不再能刻画AS之间的连通性,AS拓扑的k-容错判定问题也因此变得更复杂。本文结合网络拓扑理论与路由策略约束提出了AS拓扑的k-容错模型,该模型定义了AS拓扑k-容错判定的充要条件。基于k-容错模型定义的充要条件,进一步提出了在任何给定的AS拓扑之上实现k-容错的具体方法。研究结果表明,当前互联网的AS拓扑仅为0-容错的;把AS拓扑增补到k-容错(如k=1),其健壮性也得以显著增强;当k=1时,在给定的AS拓扑之上实现k-容错的链路代价是可接受的,仅需要新增加的上游链路数为7,447,占AS拓扑总链路数的4.5%。(4)单个AS的健壮性测度与增强机制:尽管在k-容错模型中任意AS之间的连通性都可承受k个AS级的节点或链路故障,但是,实现k-容错的代价相对高昂,需要所有的AS都满足相应的约束条件。本文结合AS拓扑的层次结构以及蒙哥定理,提出了针对单个AS的健壮性测度指标―“不相交的顶级上坡路径数”,即,单个AS对节点/链路故障的健壮性取决于它所拥有的到达顶级AS的节点不相交/边不相交的上坡路径条数。统计表明,尽管78.1%的非顶级AS拥有2条以上的上游链路,但却只有74.2%(73.6%)的非顶级AS拥有2条以上的边不相交(节点不相交)的顶级上坡路径。基于健壮性测度指标进一步提出了面向单个AS的健壮性增强机制与方法,该方法可以保证增加一条上游链路即能确保该AS所拥有的到达顶级AS的不相交上坡路径数在原来的基础上增加1。(5)对AS路径推断一致性问题的研究:AS路径推断技术被广泛应用于拓扑健壮性分析与网络性能优化等方面。目前,业内尚没有对推断路径与实际路径之间的一致性进行系统全面的分析,对其可用性缺乏充分的论证。本文系统地研究了AS路径推断的一致性问题,采用当今最具代表性的几种路径推断算法,从一致性的角度对推断路径与实际路径做了全面的比较;深入分析了推断路径与实际路径之间不一致性产生的根源:AS的局部路由控制策略(如“选择性宣告”)对路由传播与扩散的影响。实验结果表明推断路径与实际路径之间存在显著差异,揭示了现有AS路径推断技术的局限性。要提高AS路径推断的准确性,还需要确切知道AS的局部路由控制策略。本文的研究成果对于域间路由系统的安全监测和拓扑规划具有重要的支撑作用和实际的指导意义。更多还原

【Abstract】 The inter-domain routing system based on BGP is the core infrastructure of the Internet. However, there are many issues in its security and resilience. On the one hand, it is vulnerable to various attacks due to the lack of security mechanisms and monitoring measures. On the other hand, its topology is fragile to physical malfunctions, malicious attacks and natural disasters. Hence, studying the security and resilience of inter-domain routing system is indeed necessary for the reliability of the whole Internet.This paper focuses on critical issues in inter-domain routing system. As for its security, we propose a method to evaluate the trustworthiness of prefix announcements in order to detect prefix hijacking. As for its resilience, we investigate the characterization and improvement for the resilience of the Internet AS (Autonomous System) topology, and provide an insightful analysis on the consistency issue in AS path inference. The major contributions and innovations are summarized as follows.(1) Trustworthiness evaluation for prefix origins: The Internet has been suffering from prefix hijacking for many years due to the lack of defense and detection mechanisms. In this paper, we propose a method based on fuzzy set theory to evaluate the trustworthiness of prefix-AS mappings from successive BGP routing table snapshots. We construct an up-to-date trustworthy set of prefix-AS mappings with their trustworthiness inferred from the stability of the mappings. Drawing further on this, we extend our method to evaluate the trustworthiness of arbitrary prefix-AS mappings. The experimental results show that the accuracy of our method is as high as 99.85% and the method can be used to detect prefix hijacking effectively.(2) BGP routing stress attack and the cascading failure model: With the development of firewall technology and hosts’security capabilities, conducting stress attacks (such as worm attacks) in the Internet data plane is becoming more and more difficult. In this paper, we present a method availing BGP routing stress to attack the Internet from its control plane, by leveraging coupling and oscillation mechanisms in complex systems. Afterwards we design a cascading failure model to characterize and simulate behaviors of the inter-domain routing system under such attacks. The simulation results show that the proposed attack can cause large-scale cascading failures and Internet connectivity can be severely affected. However, given there are a portion of ASes that have immunity to the routing stress, the resilience will be greatly enhanced.(3) k-fault tolerance for the global AS topology: A network is k-fault tolerant if any pair of nodes can keep their reachability to each other even there are arbitrary k node or link failures. General graph theory is limited in characterizing the connectivity of Internet AS topology due to complex AS relationships. In consequence, k-fault tolerance in the Internet AS topology is more challenging than that in general graphs. Taking into account both topological connectivity and compliance to routing policies, we propose a k-fault tolerant model for AS topology by availing its inherent hierarchical structure. The model consists of necessary and sufficient csonditions for k-fault tolerance. Drawing further on this, we propose a method for the k-fault tolerance augmentation. The results reveal that the real AS topology is only 0-fault tolerant. The k-fault tolerant AS topology exhibits significantly better resilience, yet the edge cost for 1-fault tolerant augmentation is acceptable, i.e., 7,447 extra links (4.5% of the total links) are needed.(4) Resilience characterization and improvement for individual ASes: Although the k-fault tolerant model can already guarantee the resilience by k-fault tolerance, it is expensive to achieve k-fault tolerance on a global scale and requires that all ASes satisfy the conditions for k-fault tolerance. In order to characterize the resilience of individual ASes, we propose the metrics based on AS hierarchy and Menger’s Theorem, i.e., the number of node-/link-disjoint uphill paths to Tier-1 ASes. In our observations, although 78.1% of all non-Tier-1 ASes have at least two upstream links, only 74.2% (73.6%) of all non-Tier-1 ASes have at least two link-disjoint (node-disjoint) uphill paths to Tier-1 ASes. In light of this, we present a scheme to improve the resilience of individual ASes from a global perspective. With our approach, the number of disjoint uphill paths can be definitely increased by one with adding an extra upstream link.(5) Insights in the consistency between inferred paths & observed paths: AS path inference is widely used in topology resilience analysis and network performance optimization. However, little of the literature has performed a systematic and comprehensive study on the availability of such a technique taking into account the consistency between inferred paths and observed paths. In this paper, we provide a comprehensive and systematic study on the consistency between inferred computed by typical path inferring algorithms and real paths observed from routing tables, and investigate the fundamental causes for inconsistencies between inferred and observed paths. The results reveal the big differentce between inferred and observed paths, and expose limitations of current AS path inference algorithms. To achieve high accuracy in AS path inference, there is the need to know ASes’local routing policies.In summary, our work can provide support and guideline for security monitoring and topology design of the inter-domain routing system.更多还原