Nearly all network applications rely on the global Internet routing infrastructure to compute routes and deliver packets. Unfortunately, false Internet routes can be maliciously introduced with relative ease into the routing infrastructure. This is because Border Gateway Protocol (BGP), the Internet's global routing protocol, lacks basic authentication and monitoring functionalities. If false routes are introduced, it can lead to total collapse of packet forwarding leading to denial of service or misdirected traffic. Currently, it is impossible to prevent such malicious injection of false traffic routes. We believe that an ability to identify false paths through efficient validation, proper recording and forensic analysis of routing data, will considerably help in the prosecution of the miscreant and will act as a strong deterrent. In this work we propose such a mechanism. We use ICMP (Internet Control Message Protocol) traceback message with AS-PATH information and link connectivity information for each path. Our path verification technique is proportional to the amount of traffic carried on a path, uses efficient off-line verification technique with which each router independently and dynamically keeps track of local database, and allows a destination to monitor its routes, detect false paths used by remote sites, and record routing data for later forensic analysis in the event of an attack. Last but not the least, our approach does not require modifications to the BGP protocol and hence can be easily deployed.

Barrett, R., Haar, S. and Whitestone, R. (1997). Routing Snafu Causes Internet Outage. Interactive Week. April 1997.

Bates, T., Smith, P. and Huston, G. (2006). CIDR Report Status Summary for 14 September 2006, URL: http://www.cidr-report.org, 14 September 2006.

Bellovin, S. M. et al. (2001). Slowing Routing Table Growth by Filtering Based on Address Allocation Policies, URL: http://www.research.att.com/jrex/, June 2001.

Bellovin, S. M. (2000). ICMP Traceback Messages, IETF Network Working Group Internet Draft, March 2000.

Braun, H. W. (1989). The NSFNET Routing Architecture, IETF Network Working Group Request for Comments RFC 1093, February 1989.

Foster, I. and Kessekman, K. (1997). "Globus: A Metacomputing Infrastructure Toolkit," Journal of Supercomputing Application 11(2): 115-128.

Goodell, G., et al. (2003). "Working around BGP: An Incremental Approach to Improving Security and Accuracy of Interdomain Routing". Proceedings of the 10th ISOC Annual Symposium on Network and Distributed Systems Security, February 2000, San Diego, California.

Grimshaw, A. et al. (1997). "The Legion Vision of a Worldwide Virtual Computer," Communications of the ACM 40(1): 39-45.

Hawkinson, J. and Bates, T. (1996). Guidelines for Creation, Selection and Registration of an Autonomous System (AS), IETF Network Working Group Request for Comments RFC 1930, March 1996.

Hu, Y. C., Perrig, A. and Sirbu, M. (2004). "SPV: Secure Path Vector Routing for Secure BGP". Proceedings of the 2004 ACM SIGCOMM Conference on Applications, Technologies, Architectures and Protocols for Computer

Communications, August-September 2004, Portland, Oregon.

Kent, S., Lynn, C. and Seo, K. (2000). "Secure Border Gateway Protocol (S-BGP)," IEEE Journal on Selected Areas in Communications, Special Issue on Network Security 18(4): 582-592.

Lee, H. C. J. et al. (2003). "ICMP Traceback with Cumulative Path: An Efficient Solution for IP Traceback". Proceedings of the 5th International Conference on Information and Communications Security, October 2003, Huhehaote City, Inner Mongolia.

Lowekamp, B. et al. (1998). "A Resource Query Interface for Network-Aware Applications". Proceedings of the 7th IEEE Symposium on High-Performance Distributed Computing, July 1998, Chicago, Illinois.

Mahajan, R., Wetherall, D. and Anderson, T. (2002). "Understanding BGP Misconfiguration". Proceedings of the 2002 ACM SIGCOMM Conference on Applications, Technologies, Architectures and Protocols for Computer Communications, August 2002, Pittsburgh, Pennsylvania.

Mankin, A. et al. (2001). "On Design and Evaluation of Intention-Driven ICMP Traceback". Proceedings of the 10th IEEE International Conference on Computer Communications and Networks (ICCCN), October 2001, Scottsdale, Arizona.

Murphy, S. (2006). BGP Security Vulnerabilities Analysis, IETF Network Working Group Request for Comments RFC 4272, January 2006.

Ng, J. (2002). Extensions to BGP to Support Secure Origin BGP, IETF Network Working Group Internet Draft, October 2002.

Nordstrom, O. and Dovrolis, C. (2004). "Beware of BGP attacks," ACM SIGCOMM Computer Communications Review 34(2): 1-8.

Padmanabhan, V. N. and Simon, D. R. (2003). "Secure Traceroute to Detect Faulty or Malicious Routing," ACM SIGCOMM ComputerCommunication Review 33(1): 77-82.

Pei, D., Massey, D. and Zhang, L. (2004). "A Framework for Resilient Internet Routing Protocol," IEEE Network 18(2): 5-12.

Pei, D., Massey, D. and Zhang, L. (2003). "Detection of Invalid Routing Announcements in the RIP Protocol". Proceedings of the 2003 IEEE Global Communication Conference (Globecom), December 2003, St. Louis, Missouri.

Perlman, R. (1988). "Network Layer Protocols with Byzantine Robustness". Massachusetts Institute of Technology, Boston, Massachusetts, Unpublished Ph.D. Dissertation.

Rabin, M. (1989). "Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance," Journal of the ACM 36(2): 335--348.

Rekhter, Y. and Li, T. (1995). Border Gateway Protocol 4, IETF Network Working Group Request for Comments RFC 1771, March 1995.

Rexford, J. et al. (2002). "BGP Routing Stability of Popular Destinations". Proceedings of the 2nd ACM SIGCOMM Internet Measurement Workshop, November 2002, Marseille, France.

Shamir, A. (1984). "Identity-Based Cryptosystems and Signature Schemes". Proceedings of CRYPTO 84 on Advances in Cryptology, August 1984, Santa Barbara, CA. Lecture Notes in Computer Science 491, Springer-Verlag.

Stewart, J. (1999). BGP4: Inter-Domain Routing in the Internet. Addison-Wesley, Reading, Massachusetts.

Subhlok, J. et al. (1999). "Automatic Node Selection for High Performance Applications on Networks". Proceedings of the 7th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1998, Atlanta, Georgia.

Traina, P. (1995). BGP-4: Protocol Analysis, IETF Network Working Group Request for Comments RFC 1774, March 1995.

Wang, L. et al. (2003). "Protecting BGP Routes to Top Level DNS Server," IEEE Transactions on Parallel and Distributed Systems 14(9): 851-860.

Zhao, X. et al. (2001). "An Analysis of BGP Multiple Origin AS (MOAS) Conflicts". Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 2001, San Francisco, California.

Zhao, X. et al. (2002). "Detection of Invalid Routing Announcements in the Internet". Proceedings of International Conference on Dependable Systems and Networks (DSN 2002), June 2002, Bethesda, Maryland.