Secure and policy-compliant source routing

ABSTRACT

In today's Internet, inter-domain route control remains elusive; nevertheless, such control could improve the performance, reliability, and utility of the network for end users and ISPs alike. While researchers have proposed a number of source routing techniques to combat this limitation, there has thus far been no way for independent ASes to ensure that such traffic does not circumvent local traffic policies, nor to accurately determine the correct party to charge for forwarding the traffic.

We present Platypus, an authenticated source routing system built around the concept of network capabilities, which allow for accountable, fine-grained path selection by cryptographically attesting to policy compliance at each hop along a source route. Capabilities can be composed to construct routes through multiple ASes and can be delegated to third parties. Platypus caters to the needs of both end users and ISPs: users gain the ability to pool their resources and select routes other than the default, while ISPs maintain control over where, when, and whose packets traverse their networks. We describe the design and implementation of an extensive Platypus policy framework that can be used to address several issues in wide-area routing at both the edge and the core, and evaluate its performance and security. Our results show that incremental deployment of Platypus can achieve immediate gains.

REFERENCES

• 1: S. Agarwal, C.-N. Chuah, and R. H. Katz, "OPCA: Robust interdomain policy routing and traffic control," in Proc. IEEE OPENARCH, Apr. 2003, pp. 55-64.
• 2: Marcos K. Aguilera , Minwen Ji , Mark Lillibridge , John MacCormick , Erwin Oertli , Dave Andersen , Mike Burrows , Timothy Mann , Chandramohan A. Thekkath, Block-Level Security for Network-Attached Disks, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 3: David G. Andersen, Mayday: distributed filtering for internet services, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.3-3, March 26-28, 2003, Seattle, WA
• 4: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 5: R. Atkinson, Security Architecture for the Internet Protocol, RFC Editor, 1995
• 6: Hari Balakrishnan , Venkata N. Padmanabhan , Randy H. Katz, The effects of asymmetry on TCP performance, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.77-89, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262134]
• 7: M. Bellare , R. Canetti , H. Krawczyk, Pseudorandom functions revisited: the cascade construction and its concrete security, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.514, October 14-16, 1996
• 8: John Black , Shai Halevi , Hugo Krawczyk , Ted Krovetz , Phillip Rogaway, UMAC: Fast and Secure Message Authentication, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.216-233, August 15-19, 1999
• 9: John Black , Phillip Rogaway, A Block-Cipher Mode of Operation for Parallelizable Message Authentication, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.384-397, May 02, 2002
• 10: M. Caesar and J. Rexford, "BGP policies in ISP networks," IEEE Network , vol. 19, no. 6, pp. 5-11, Nov. 2005.
• 11: CAIDA Skitter Project. [Online]. Available: http://www.caida.org/ tools/measurement/skitter/
• 12: Martin Casado , Tal Garfinkel , Aditya Akella , Michael J. Freedman , Dan Boneh , Nick McKeown , Scott Shenker, SANE: a protection architecture for enterprise networks, Proceedings of the 15th conference on USENIX Security Symposium, July 31-August 04, 2006, Vancouver, B.C., Canada
• 13: I. Castineyra , N. Chiappa , M. Steenstrup, The Nimrod Routing Architecture, RFC Editor, 1996
• 14: D. D. Clark, Policy routing in Internet protocols, RFC Editor, 1989
• 15: David D. Clark , John Wroclawski , Karen R. Sollins , Robert Braden, Tussle in cyberspace: defining tomorrow's internet, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 16: N. G. Duffield , M. Grossglauser, Trajectory sampling for direct traffic observation, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.271-282, August 28-September 01, 2000, Stockholm, Sweden
• 17: D. Estrin , T. Li , Y. Rekhter , K. Varadhan , D. Zappala, Source Demand Routing: Packet Format and Forwarding Specification (Version 1), RFC Editor, 1996
• 18: D. Estrin, J. C. Mogul, and G. Tsudik, "Visa protocols for controlling interorganizational datagram flow," IEEE J. Sel. Areas Commun., vol. 7, no. 4, pp. 486-498, May 1989.
• 19: D. Estrin and G. Tsudik, "Security issues in policy routing," in Proc. IEEE Symp. Security and Privacy, May 1989, pp. 183-193.
• 20: Nick Feamster , Jay Borkenhagen , Jennifer Rexford, Guidelines for interdomain traffic engineering, ACM SIGCOMM Computer Communication Review, v.33 n.5, October 2003 [doi>10.1145/963985.963988]
• 21: Krishna P. Gummadi , Harsha V. Madhyastha , Steven D. Gribble , Henry M. Levy , David Wetherall, Improving the reliability of internet paths with one-hop source routing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.13-13, December 06-08, 2004, San Francisco, CA
• 22: Krishna P. Gummadi , Stefan Saroiu , Steven D. Gribble, King: estimating latency between arbitrary internet end hosts, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637203]
• 23: G. Huston, Commentary on Inter-Domain Routing in the Internet, RFC Editor, 2001
• 24: H. Krawczyk , M. Bellare , R. Canetti, HMAC: Keyed-Hashing for Message Authentication, RFC Editor, 1997
• 25: A. Kumar, J. Xu, L. Li, J. Wang, and O. Spatschek, "Space-code Bloom filter for efficient per-flow traffic measurement," in Proc. IEEE INFOCOM 2004, Mar. 2004, vol. 3, pp. 1762-1773.
• 26: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.293-306, June 2001 [doi>10.1109/90.929852]
• 27: J. B. MacQueen, "On convergence of k-means and partitions with minimum average variance," Ann. Math. Stat., vol. 36, 1965.
• 28: Ratul Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 29: 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
• 30: David L. Mills, A brief history of NTP time: memoirs of an Internet timekeeper, ACM SIGCOMM Computer Communication Review, v.33 n.2, April 2003 [doi>10.1145/956981.956983]
• 31: Akihiro Nakao , Larry Peterson , Andy Bavier, A routing underlay for overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863958]
• 32: W. B. Norton, "Internet service providers and peering," in Proc. NANOG, Jun. 2000.
• 33: Poslib DNS Library. [Online]. Available: http://www.posadis.org/ poslib/
• 34: Lili Qiu , Yang Richard Yang , Yin Zhang , Scott Shenker, On selfish routing in internet-like environments, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863974]
• 35: Barath Raghavan , Alex C. Snoeren, A system for authenticated policy-compliant routing, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 36: Barath Raghavan , Kashi Vishwanath , Sriram Ramabhadran , Kenneth Yocum , Alex C. Snoeren, Cloud control with distributed rate limiting, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 37: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 38: 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]
• 39: A. C. Snoeren and B. Raghavan, "Decoupling policy from mechanism in Internet routing," in Proc. HotNets, Nov. 2003.
• 40: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 41: R. Srinivasan, "XDR: External data representation standard," in IETF, RFC 1812, Aug. 1995.
• 42: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 43: I. Stoica and H. Zhang, "LIRA: An approach for service differentiation in the Internet," in Proc. NOSSDAV, Jun. 1998.
• 44: H. Tahilramani Kaur , S. Kalyanaraman , A. Weiss , S. Kanwar , A. Gandhi, BANANAS: an evolutionary framework for explicit and multipath routing in the internet, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 45: Xiaowei Yang, NIRA: a new Internet routing architecture, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 25-27, 2003, Karlsruhe, Germany
• 46: Xiaowei Yang , David Wetherall , Thomas Anderson, A DoS-limiting network architecture, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 47: D. Zhu, M. Gritter, and D. R. Cheriton, "Feedback based routing," in Proc. HotNets, Oct. 2002.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Algorithms, Design, Performance, Security

Keywords:
authentication, capabilities, overlay networks, source routing