Tradeoffs in probabilistic packet marking for IP traceback

ABSTRACT

There has been considerable recent interest in probabilistic packet marking schemes for the problem of tracing a sequence of network packets back to an anonymous source. An important consideration for such schemes is the number of packet header bits that need to be allocated to the marking protocol. Let b denote this value. All previous schemes belong to a class of protocols for which b must be at least log n, where n is the number of bits used to represent the path of the packets. In this paper, we introduce a new marking technique for tracing a sequence of packets sent along the same path. This new technique is effective even when b=1. In other words, the sequence of packets can be traced back to their source using only a single bit in the packet header. With this scheme, the number of packets required to reconstruct the path is O(2²ⁿ), but we also show that ω(2ⁿ) packets are required for any protocol where b=1. We also study the tradeoff between b and the number of packets required. We provide a protocol and a lower bound that together demonstrate that for the optimal protocol, the number of packets required (roughly) increases exponentially with n, but decreases doubly exponentially with b. The protocol we introduce is simple enough to be useful in practice. We also study the case where the packets are sent along k different paths. For this case, we demonstrate that any protocol must use at least log(2k—1) header bits. We also provide a protocol that requires ⌈log(2k+1)⌉ header bits in some restricted scenarios. This protocol introduces a new coding technique that may be of independent interest.

REFERENCES

• 1: M. Adler, Tradeoffs in Probabilistic Packet Marking for IP Traceback TITLE2:, University of Massachusetts, Amherst, MA, 2001
• 2: Sigal Ar, Richard Lipton, Ronitt Rubinfeld, and Madhu Sudan, Reconstructing Algebraic Functions from Mixed Data. In Proc. of 33rd Annual Symposium on Foundations of Computer Science, pp. 503--512, October 1992.
• 3: S. M. Bellovin, ICMP Traceback Messages. Internet Draft: draft-bellovin-itrace-00.txt, Mar. 2000.
• 4: Hal Burch, Tracing Anonymous Packets to Their Approximate Source, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 5: Sven Dietrich , Neil Long , David Dittrich, Analyzing Distributed Denial of Service Tools: The Shaft Case, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 6: Drew Dean, Matt Franklin, and Adam Stubblefield, An Algebraic Approach to IP Traceback. In Proc. 2001 Network and Distributed System Security Symposium.
• 7: Thomas W. Doeppner , Philip N. Klein , Andrew Koyfman, Using router stamping to identify the source of IP packets, Proceedings of the 7th ACM conference on Computer and communications security, p.184-189, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352627]
• 8: P. Ferguson and D. Senie, RFC 2267: Network Ingress Filetring: Defeating Denial of Service Attacks which employ IP Source Address Spoofing. The Internet Society, 1998.
• 9: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 10: S. Lee and C. Shields, Tracing the Source of Network Attack: A Technical, Legal and Societal Problem. In Proceedings of the 2001 IEEE Workshop on Information Assurance and Security , June 2001.
• 11: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 12: K. Park and H. Lee. On the effectiveness of probabilistic packet marking for IP traceback under denial of service attack. In Proc. IEEE INFOCOM '01, pp. 338--347, 2001.
• 13: Kihong Park , Heejo Lee, On the effectiveness of route-based packet filtering for distributed DoS attack prevention in power-law internets, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.15-26, August 2001, San Diego, California, United States
• 14: C. Perkins, IP Mobility Support. RFC 2002, Oct. 1996.
• 15: Luigi Rizzo, Effective erasure codes for reliable computer communication protocols, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.24-36, Apr. 1997 [doi>10.1145/263876.263881]
• 16: Stefan Savage , David Wetherall , Anna Karlin , Tom Anderson, Practical network support for IP traceback, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.295-306, August 28-September 01, 2000, Stockholm, Sweden
• 17: Alex C. Snoeren, Hash-based IP traceback, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.3-14, August 2001, San Diego, California, United States
• 18: Dawn X. Song and Adrian Perrig, Advanced and authenticated marking schemes for IP traceback, In Proc. IEEE INFOCOM '01, 2001.

INDEX TERMS

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

          Nouns: IP

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Design, Experimentation, Performance, Theory