Project homepage: Mitigating Exploits of the Current Interdomain Routing Infrastructure

Mitigating Exploits of the Current Interdomain Routing Infrastructure

This material is based on collaborative research supported by the NSF Cyber Trust program through grants CNS-0753061 (transferred from CNS-0716511) and CNS-0753492 (transferred from CNS-0716564). (Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.)

Description

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.

People

Senior Personnel

Aaron D. Jaggard (PI, DIMACS, Rutgers University)
Vijay Ramachandran (co-PI, CS, Colgate University)
Rebecca N. Wright (PI, DIMACS and CS, Rutgers University)

Graduate Student

Syeda Arzoo Zehra (CS, Rutgers University)

Undergraduate Students

Leilani Gilpin (UCSD) 2010 REU project page
Jonathan Haber (Tufts) 2010 REU project page
Alan Keith (Colgate)
Swara Kopparty (Harvard) 2010 REU project page

Collaborators

Bruno Blanchet, Alex Fabrikant, Joan Feigenbaum, Sharon Goldberg, Shai Halevi, Jesse Rao, Andre Scedrov, Michael Schapira, Joe-Kai Tsay

Preprints and papers

Alex Fabrikant, Aaron D. Jaggard, and Michael Schapira, "On the Structure of Weakly Acyclic Games"
- To appear in Theory of Computing Systems (special issue of invited papers from SAGT 2010)
- Preliminary version available as arXiv:1108.2092
Aaron D. Jaggard, Swara Kopparty, Vijay Ramachandran, and Rebecca N. Wright, "The Design Space of Probing Algorithms for Network-Performance Measurement"
- To appear in the Proceedings of SIGMETRICS 2013 (June 2013)
Joan Feigenbaum, Vijay Ramachandran, and Michael Schapira, "Incentive-Compatible Interdomain Routing"
- Distributed Computing, 23(5-6): 301--319 (2011) doi:10.1007/s00446-011-0126-8
Aaron D. Jaggard, Michael Schapira, and Rebecca N. Wright, "Distributed Computing with Adaptive Heuristics"
- Proceedings of ICS 2011, pp. 417-443 (January 2011) [28-page pdf].
- Also: "Brief Announcement: Distributed Computing with Rules of Thumb," presented at PODC 2011 (June 2011) [two-page pdf]
Alex Fabrikant, Aaron D. Jaggard, and Michael Schapira, "On the Structure of Weakly Acyclic Games"
- Proceedings of SAGT 2010 (October 2010) [12-page pdf]
Joan Feigenbaum, Aaron D. Jaggard, and Michael Schapira, "Approximate Privacy: Foundations and Quantification (Extended Abstract)"
- Proceedings of ACM EC'10 (June 2010). doi:10.1145/1807342.1807369
- Full version split between:
  - "Approximate Privacy: Foundations and Quantification," DIMACS Technical Report 2009-14 [abstract, 32-page pdf]; also available as arXiv:0910.5714 (33 pages).
  - "Approximate Privacy: PARs for Set Problems," DIMACS Technical Report 2010-01 [abstract, 32-page pdf]; also available as arXiv:1001.3388 (34 pages)
Bruno Blanchet, Aaron D. Jaggard, Jesse Rao, Andre Scedrov, and Joe-Kai Tsay, "Refining Computationally Sound Mechanized Proofs for Kerberos"
- Abstract presented at FCC'09
Aaron D. Jaggard, Vijay Ramachandran, and Rebecca N. Wright, "The Impact of Communication Models on Routing-Algorithm Convergence"
- Proceedings of ICDCS 2009, pp. 58--67 (June 2009). doi:10.1109/ICDCS.2009.61
- DIMACS Technical Report 2008-06 [Version of 2008-11-24: abstract, 29-page pdf]
Sharon Goldberg, Shai Halevi, Aaron D. Jaggard, Vijay Ramachandran, and Rebecca N. Wright, "Rationality and Traffic Attraction: Incentives for Honest Path Announcements in BGP"
- Proceedings of SIGCOMM 2008, pp. 267--278 (2008). [12-page pdf] doi:10.1145/1402946.1402989
- Princeton CS Technical Report TR-823-08.
Aaron D. Jaggard, Vijay Ramachandran, and Rebecca N. Wright, "Towards a Realistic Model of Incentives in Interdomain Routing: Decoupling Forwarding from Signaling"
- DIMACS Technical Report 2008-02 [Version of 2008-04-27: abstract, 37-page pdf]
Bruno Blanchet, Aaron D. Jaggard, Andre Scedrov, and Joe-Kai Tsay, "Computationally Sound Mechanized Proofs for Basic and Public-key Kerberos"
- Proceedings of ASIACCS 2008, pp. 87--99 (2008). doi:10.1145/1368310.1368326

Talks

More is Not Better: The Perils of Multiple Solutions
- Presented at the Colgate University Division of Natural Sciences and Mathematics Colloquium Series, 18 February 2011
- Presented in the DIMACS REU Seminar series, 28 June 2011
Distributed Computing with Adaptive Heuristics
- Presented at Innovations in Computer Science 2011, 09 January 2011 (.pptx slides)
Asynchronous Distributed Computing with Adaptive Heuristics
- Presented at the Decentralized Mechanism Design, Distributed Computing, and Cryptography Workshop, 04 June 2010
Towards a unified approach to (in)decision, with implications for divergence of game dynamics
- Presented at the NYCE Day 2009 rump session, 09 November 2009
Refining Computationally Sound Mechanized Proofs for Kerberos
- Presented at the October 2009 Protocol eXchange meeting, 07 October 2009
- Presented at FCC'09
Rationality and Traffic Attraction: Incentives for Honest Path Announcements in BGP
- Presented at the 2009 Workshop on Cryptographic Protocols and Public-Key Cryptography, Bertinoro, Italy, 24--29 May, 2009
- Presented at the NYCE Day 2008 rump session, 03 October 2008 (pdf slides)
Analyzing Kerberos using CryptoVerif
- Presented at the October 2008 Protocol eXchange meeting, 02 October 2008 (pdf slides)
Towards a Realistic Model of Incentives in Interdomain Routing: Decoupling Forwarding from Signaling
- Presented at the DIMACS/DyDAN Workshop on Secure Internet Routing, 26 March 2008 (pdf slides)

Posters

Approximate Privacy: Foundations and Quantification
- Presented at Security and Privacy Day, 15 May 2009
A more realistic model of incentives for routing (pdf poster)
- Presented at the 2008 NSF Cyber Trust PI Meeting, 16--18 March 2008