Packet-dropping adversary identification for data plane security

ABSTRACT

Until recently, the design of packet dropping adversary identification protocols that are robust to both benign packet loss and malicious behavior has proven to be surprisingly elusive. In this paper, we propose a secure and practical packet-dropping adversary localization scheme that is robust and achieves a high detection rate and low communication and storage overhead -- the three key performance metrics for such protocols in realistic settings. Other recent work just optimizes either the detection rate or the communication overhead.

In this paper, we systematically explore the design space of acknowledgment-based protocols to identify a packet dropping adversary on a forwarding path. In particular, we investigate a set of basic protocols, each exemplifying a design dimension, and examine the underlying tradeoff between the performance metrics. For each basic protocol, we present both upper and lower performance bounds via theoretical analysis, and average-case results via simulations. We conclude that the proposed PAAI-1 protocol outperforms other related schemes.

REFERENCES

• 1: K. Argyraki, P. Maniatis, D. Cheriton, and S. Shenker. Providing packet obituaries. In ACM Hotnets-III, 2004.
• 2: K. Argyraki, P. Maniatis, O. Irzak, S. Ashish, and S. Shenker. Loss and delay accountability interface for the internet. In Proceedings of IEEE International Conference on Network Protocols, 2007.
• 3: I. Avramopoulos, H. Kobayashi, R. Wang, and A. Krishnamurthy. Amendment to: Highly secure and efficient routing. Available at http://www.princeton.edu/~iavramop/amendment.pdf.
• 4: I. Avramopoulos, H. Kobayashi, R. Wang, and A. Krishnamurthy. Highly secure and efficient routing. In IEEE Infocom, 2004.
• 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: Baruch Awerbuch , David Holmer , Cristina Nita-Rotaru , Herbert Rubens, An on-demand secure routing protocol resilient to byzantine failures, Proceedings of the 1st ACM workshop on Wireless security, p.21-30, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570684]
• 7: B. Barak, S. Goldberg, and D. Xiao. Protocols and lower bounds for failure localization in the internet. In Proceedings of EUROCRYPT, 2008.
• 8: K. A. Bradley, S. Cheung, N. Puketza, B. Mukherjee, and R. A. Olsson. Detecting disruptive routers: A distributed network monitoring approach. In Proceedings of the IEEE Symposium on Research in Security and Privacy, pages 115--124, Oakland, CA, May 1998.
• 9: Sharon Goldberg , David Xiao , Eran Tromer , Boaz Barak , Jennifer Rexford, Path-quality monitoring in the presence of adversaries, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 10: John R. Hughes , Tuomas Aura , Matt Bishop, Using Conservation of Flow as a Security Mechanism in Network Protocols, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.132, May 14-17, 2000
• 11: M. Just, E. Kranakis, and W. Tao. Resisting malicious packet dropping in wireless ad hoc networks. In Proceedings of ADHOC-NOW, Oct. 2003.
• 12: Kejun Liu , Jing Deng , Pramod K. Varshney , Kashyap Balakrishnan, An Acknowledgment-Based Approach for the Detection of Routing Misbehavior in MANETs, IEEE Transactions on Mobile Computing, v.6 n.5, p.536-550, May 2007 [doi>10.1109/TMC.2007.1036]
• 13: Jonathan M. McCune , Elaine Shi , Adrian Perrig , Michael K. Reiter, Detection of Denial-of-Message Attacks on Sensor Network Broadcasts, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.64-78, May 08-11, 2005 [doi>10.1109/SP.2005.7]
• 14: 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]
• 15: 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]
• 16: R. Perlman. Network Layer Protocol with Byzantine Agreement. PhD thesis, The MIT Press, Oct. 1988. LCS TR-429.
• 17: X. Zhang, A. Jain, and A. Perrig. Full version: Packet-dropping adversary identification for data plane security. Available at http://www.cs.cmu.edu/~xzhang1/doc/conext08_full.pdf.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Security