Probabilistic packet marking for large-scale IP traceback

ABSTRACT

This paper presents an approach to IP traceback based on the probabilistic packet marking paradigm. Our approach, which we call randomize-and-link, uses large checksum cords to "link" message fragments in a way that is highly scalable, for the checksums serve both as associative addresses and data integrity verifiers. The main advantage of these checksum cords is that they spread the addresses of possible router messages across a spectrum that is too large for the attacker to easily create messages that collide with legitimate messages.

REFERENCES

• 1: Aris Anagnostopoulos , Michael T. Goodrich , Roberto Tamassia, Persistent Authenticated Dictionaries and Their Applications, Proceedings of the 4th International Conference on Information Security, p.379-393, October 01-03, 2001
• 2: Tatsuya Baba , Shigeyuki Matsuda, Tracing Network Attacks to Their Sources, IEEE Internet Computing, v.6 n.2, p.20-26, March 2002 [doi>10.1109/4236.991439]
• 3: [3] S. M. Bellovin, "ICMP traceback messages," work in Progress, 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: [5] D. Dean, M. Franklin, and A. Stubblefield, "An algebraic approach to IP traceback," in Proc. Network and Distributed System Security Symp. (NDSS), 2001, pp. 3-12.
• 6: Michael T. Goodrich, Efficient packet marking for large-scale IP traceback, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586128]
• 7: [7] M. T. Goodrich, R. Tamassia, and A. Schwerin, "Implementation of an authenticated dictionary with skip lists and commutative hashing," in Proc. 2001 DARPA Information Survivability Conf. Expo., 2001, vol. 2, pp. 68-82.
• 8: [8] J. Ioannidis and S. M. Bellovin, "Implementing Pushback: Router-based defense against DDOS attacks," in Proc. Network and Distributed System Security Symp., 2002.
• 9: Terence K. T. Law , John C. S. Lui , David K. Y. Yau, You Can Run, But You Can't Hide: An Effective Statistical Methodology to Trace Back DDoS Attackers, IEEE Transactions on Parallel and Distributed Systems, v.16 n.9, p.799-813, September 2005 [doi>10.1109/TPDS.2005.114]
• 10: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 11: 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
• 12: 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
• 13: [13] D. Song and A. Perrig, "Advanced and authenticated marking schemes for IP traceback," in Proc. IEEE INFOCOM, 2001, pp. 878-886.
• 14: Robert Stone, Centertrack: an IP overlay network for tracking DoS floods, Proceedings of the 9th conference on USENIX Security Symposium, p.15-15, August 14-17, 2000, Denver, Colorado

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:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

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

General Terms:
Algorithms, Design, Security

Keywords:
IP, associate addresses, checksum cords, denial of service (DDOS), distributed, probabilistic packet marking, traceback