Truth in advertising: lightweight verification of route integrity

ABSTRACT

We design and evaluate a lightweight route verification mechanism that enables a router to discover route failures and inconsistencies between advertised Internet routes and actual paths taken by the data packets. Our mechanism is accurate, incrementally deployable, and secure against malicious intermediary routers. By carefully avoiding any cryptographic operations in the data path, our prototype implementation achieves the overhead of less than 1% on a 1 Gbps link, demonstrating that our method is suitable even for high-performance networks.

REFERENCES

• 1: Ioannis Avramopoulos , Jennifer Rexford, Stealth probing: efficient data-plane security for IP routing, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.25-25, May 30-June 03, 2006, Boston, MA
• 2: E. Billauer. Frandom. http://frandom.sourceforge.net, 2007.
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: Cisco Systems. Cisco CRS-1 carrier routing system. http://www.cisco.com/application/pdf/en/us/guest/products/ps5763/c1031/cdccont 0900aecd800f8118.pdf.
• 5: M. H. DeGroot. Probability and Statistics. Addison-Wesley, 1986.
• 6: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 7: Dimitris Fotakis , Rasmus Pagh , Peter Sanders , Paul G. Spirakis, Space Efficient Hash Tables with Worst Case Constant Access Time, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.271-282, February 27-March 01, 2003
• 8: S. Goldberg, D. Xiao, B. Barak, and J. Rexford. Measuring path quality in the presence of adversaries. http://www.princeton.edu/<goldbe/FDFL-sc.pdf, 2007.
• 9: G. Goodell, W. Aiello, T. Griffin, J. Ioannidis, P. McDaniel, and A. Rubin. Working around BGP: An incremental approach to improving security and accuracy of interdomain routing. In Proc. NDSS, 2003.
• 10: Iperf. The TCP/UDP bandwidth measurement tool. http://dast.nlanr.net/Projects/Iperf/, 2005.
• 11: B. Jenkins. Hash functions and block ciphers. http://www.burtleburtle.net/bob/hash, 2006.
• 12: S. Kent, C. Lynn, and K. Seo. Secure Border Gateway protocol (Secure-BGP). IEEE Journal on Selected Areas in Communications, 18(4), 2000.
• 13: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 14: Ratul Mahajan , David Wetherall , Tom Anderson, Understanding BGP misconfiguration, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 15: Zhuoqing Morley Mao , Jennifer Rexford , Jia Wang , Randy H. Katz, Towards an accurate AS-level traceroute tool, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863996]
• 16: Alper Tugay Mizrak, Fatih: Detecting and Isolating Malicious Routers, Proceedings of the 2005 International Conference on Dependable Systems and Networks, p.538-547, June 28-July 01, 2005 [doi>10.1109/DSN.2005.49]
• 17: Venkata N. Padmanabhan , Daniel R. Simon, Secure traceroute to detect faulty or malicious routing, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.77-82, January 2003 [doi>10.1145/774763.774775]
• 18: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 19: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, ACM SIGCOMM Computer Communication Review, v.30 n.4, p.295-306, October 2000
• 20: Alex C. Snoeren , Craig Partridge , Luis A. Sanchez , Christine E. Jones , Fabrice Tchakountio , Beverly Schwartz , Stephen T. Kent , W. Timothy Strayer, Single-packet IP traceback, IEEE/ACM Transactions on Networking (TON), v.10 n.6, p.721-734, December 2002 [doi>10.1109/TNET.2002.804827]
• 21: Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.81-94, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 22: Lakshminarayanan Subramanian , Volker Roth , Ion Stoica , Scott Shenker , Randy H. Katz, Listen and whisper: security mechanisms for BGP, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.10-10, March 29-31, 2004, San Francisco, California
• 23: T. Wan, E. Kranakis, and P. van Oorschot. Pretty secure BGP (psBGP). In Proc. NDSS, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Security

Keywords:
BGP, interdomain routing, security