This project addresses fundamental flaws in Internet-routing infrastructure using both theoretical analysis and practical tools. The results not only improve the security of the current Internet, but also advance principles of secure routing design useful for next-generation protocols. The project advocates a different approach than previous work in this area by formally defining comprehensive requirements for protocol security, rather than imposing new technologies to address one or two specific exploits.
The Border Gateway Protocol (BGP) provides best-effort connectivity between the component networks of the Internet, a task called interdomain routing. However, BGP lacks any security mechanism, allowing accidental router misconfiguration or intentional attacks that have far-reaching effects on network stability and traffic flow. Furthermore, simply adding security mechanisms is insufficient because BGP also lacks the guarantee that specification-compliant inputs always produce stable routes across the network.
This project addresses these shortcomings through research on various assumptions that guarantee good routing behavior and on methods to verify or enforce these assumptions to prevent deviation from that behavior. We identify and address attacks that have previously been studied as well as new attacks that have not yet received attention in the literature. We target incremental-deployment benefits and computational efficiency as primary desiderata; thus, our solutions can offer incentives for immediate adoption without system-wide changes. Through its educational component, our project introduces students to cross-disciplinary research. This encourages collaboration in research projects and allows development of coursework integrating security, networking, and theory for a timely application domain.
The guarantee of connectivity -- ensuring that every pair of network participants can exchange messages, possibly through other participants -- is fundamental to any communication network. Establishing connectivity in a dynamic environment is the job of routing protocols. The Border Gateway Protocol (BGP) today provides best-effort connectivity between the component networks (Autonomous Systems or ASes) composing the Internet, a task called interdomain routing. However, BGP lacks any security mechanism, resulting in the possibility of accidental router misconfiguration or intentional attacks that have far-reaching effects on network stability and traffic flow. This motivates the study of methods of detecting and preventing exploits of these weaknesses. Furthermore, even in the absence of misconfiguration and attacks, locally reasonable routing policies can interact in unexpected and complicated ways to produce global routing instability; this motivates the formal modeling and study of BGP, such as finding policy restrictions that guarantee good behavior, and of the incentives that influence routing policy. Project research has focused on weaknesses in the Border Gateway Protocol (BGP) and related protocols . This includes completed and ongoing work on: (1) rationally motivated deviations from BGP; (2) expanding and strengthening BGP-convergence results and models for analyzing BGP convergence; (3) improving network resiliency through modifications to BGP and studying other network algorithms and (4) security and privacy properties of network protocols. Results include those that generalize to many other settings including congestion-control protocols, best-response dynamics in general games, and asynchronous circuits. Intellectual Merit: The project yielded important advances in the analysis of BGP, the Internet's interdomain-routing protocol, and its vulnerabilities. Results include modeling the separation of forwarding actions from signaling actions, both statically and with more-realistic utilities than previously studied in the interdomain-routing game. This work underscores the limitations of existing proposals to secure the routing infrastructure and demonstrate the potential effects of rationally motivated deviations from BGP. Project outcomes also include a taxonomy of communication models for the analysis of routing protocols, with positive and negative results for transferring convergence guarantees and examples of non-convergence between different models. This shows that security results may indeed depend on the choice of communication model and identifies which models are most appropriate for different uses. The project strengthened results on the non-convergence of BGP when there are two stable routing trees; this used a broad approach that applies to numerous other distributed-computing settings. Ongoing work formalizes and explores a space of probing algorithms for network-fault detection. This work suggests inherent tradeoffs involved in monitoring networks for anomalous conditions that, among other actions, might require adjustments to the routing system. Part of the project involved proof of security properties of the Kerberos authentication protocol using the CryptoVerif prover. This demonstrates the applicability of this approach to real-world, industrial protocols and helped refine the prover; this work also introduced a stronger notion of key usability that was amenable to use with the automated prover. Finally, the project also explored a general approach to quantify the partial privacy provided by protocols that are not perfectly private. Broader Impacts: The Internet and other networks are now critical resources for science and technology. Our work contributes to a better understanding of routing security, with the goals of making the Internet more robust and informing the design of future networks. The project has contributed to the training and professional development of undergraduates, graduate students, and early-career researchers. Four graduate students and four undergraduates have been directly involved in project research. The project also contributed to the development of courses at both Rutgers and Colgate. Outreach activities included a number of talks (including to multi-disciplinary audiences) and organization of workshops and event series. Specifically, PI Jaggard co-organized the 2010 DIMACS Workshop on Secure Routing.
