Path-quality monitoring in the presence of adversaries

ABSTRACT

Edge networks connected to the Internet need effective monitoring techniques to drive routing decisions and detect violations of Service Level Agreements (SLAs). However, existing measurement tools, like ping, traceroute, and trajectory sampling, are vulnerable to attacks that can make a path look better than it really is. In this paper, we design and analyze path-quality monitoring protocols that reliably raise an alarm when the packet-loss rate and delay exceed a threshold, even when an adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets.

Despite the strong threat model we consider in this paper, our protocols are efficient enough to run at line rate on high-speed routers. We present a secure sketching protocol for identifying when packet loss and delay degrade beyond a threshold. This protocol is extremely lightweight, requiring only 250-600 bytes of storage and periodic transmission of a comparably sized IP packet to monitor billions of packets. We also present secure sampling protocols that provide faster feedback and accurate round-trip delay estimates, at the expense of somewhat higher storage and communication costs. We prove that all our protocols satisfy a precise definition of secure path-quality monitoring and derive analytic expressions for the trade-off between statistical accuracy and system overhead. We also compare how our protocols perform in the client-server setting, when paths are asymmetric, and when packet marking is not permitted.

REFERENCES

• 1: Bad ISPs that cause trouble for BitTorrent clients. http://www.azureuswiki.com/index.php/Bad_ISPs.
• 2: Keynote launches new SLA services, June 2001. http://investor.keynote.com/phoenix.zhtml?c=78522&p=irol-newsArticle_Print&ID=183745.
• 3: Dimitris Achlioptas, Database-friendly random projections, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.274-281, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375608]
• 4: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 5: 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
• 6: Hitesh Ballani , Paul Francis , Xinyang Zhang, A study of prefix hijacking and interception in the internet, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 7: B. Barak, S. Goldberg, and D. Xiao. Protocols and lower bounds for failure localization in the Internet. In IACR EUROCRYPT, 2008.
• 8: J. L. Carter and M. N. Wegman. Universal classes of hash functions. JCSS, 18(2):143--154, 1979.
• 9: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 10: T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.1. RFC 4346 (Proposed Standard), 2006.
• 11: Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
• 12: N. G. Duffield , Matthias Grossglauser, Trajectory sampling for direct traffic observation, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.280-292, June 2001 [doi>10.1109/90.929851]
• 13: S. Goldberg and J. Rexford. Security vulnerabilities and solutions for packet sampling. IEEE Sarnoff Symposium, 2007.
• 14: S. Goldberg, D. Xiao, E. Tromer, B. Barak, and J. Rexford. Path-quality monitoring in the presence of adversaries. Technical report, Princeton University Department of Computer Science, 2008.
• 15: K. J. Houle and G. M. Weaver. Trends in denial of service attack technology. Technical report, CERT Coordination Center, 2001.
• 16: IETF. Packet sampling working group. http://www.ietf.org/html.charters/psamp-charter.html.
• 17: IETF. Working Group on IP Performance Metrics. http://www.ietf.org/html.charters/ippm-charter.html.
• 18: R. Impagliazzo , M. Luby, One-way functions are essential for complexity based cryptography, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.230-235, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63483]
• 19: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 20: W. Johnson and J. Lindenstrauss. Extensions of Lipshitz mapping into Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 21: M. Luckie, K. Cho, and B. Owens. Inferring and debugging path MTU discovery failures. In Internet Measurement Conference, 2005.
• 22: D. Mills, A. Thyagarajan, and B. Huffman. Internet timekeeping around the globe. Proc. PTTI, pages 365--371, 1997.
• 23: Ilya Mironov , Moni Naor , Gil Segev, Sketching in adversarial environments, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374471]
• 24: Alper Tugay Mizrak , Yu-Chung Cheng , Keith Marzullo , Stefan Savage, Detecting and Isolating Malicious Routers, IEEE Transactions on Dependable and Secure Computing, v.3 n.3, p.230-244, July 2006 [doi>10.1109/TDSC.2006.34]
• 25: A. Nucci. Skype detection: Traffic classification in the dark, 2006. http://www.narus.com/_pdf/news/Converge-Skype%20Detection.pdf.
• 26: Adrian Perrig , J. D. Tygar , Dawn Song , Ran Canetti, Efficient Authentication and Signing of Multicast Streams over Lossy Channels, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.56, May 14-17, 2000
• 27: Joel Sommers , Paul Barford , Nick Duffield , Amos Ron, Improving accuracy in end-to-end packet loss measurement, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 28: Joel Sommers , Paul Barford , Nick Duffield , Amos Ron, Accurate and efficient SLA compliance monitoring, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 29: Jonathan Stone , Craig Partridge, When the CRC and TCP checksum disagree, ACM SIGCOMM Computer Communication Review, v.30 n.4, p.309-319, October 2000
• 30: 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
• 31: Mikkel Thorup , Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 32: J. Xu. Tutorial on network data streaming. In ACM SIGMETRICS, 2008.

INDEX TERMS

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

General Terms:
Measurement, Security

Keywords:
cryptography, path-quality monitoring, sampling, sketching