Research On Key Issues Of Inter-Domain Routing Security And Resilience

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.