Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a new solution to the problem of determining the path a packet traversed over the Internet (called the traceback problem) during a denial-of-service attack. This article reframes the traceback problem as a polynomial reconstruction problem and uses algebraic techniques from coding theory and learning theory to provide robust methods of transmission and reconstruction.

REFERENCES

• 1: Almquist, P. 1992. Type of service in the internet protocol suite. RFC 1349.
• 2: Ar, S., Lipton, R. J., Rubinfeld, R., and Sudan, M. 1992. Reconstructing algebraic functions from mixed data. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (Pittsburgh, Oct. 24--27), IEEE, Los Alamitos, Calif., 503--512.
• 3: Bellovin, S. M. 2000a. Personal communications.
• 4: Bellovin, S. M. 2000b. ICMP traceback messages. Available at http://www.research.att.com/~smb/papers/draft-bellovin-itrace-00.txt.
• 5: Berlekamp, E. and Welch, L. 1986. Error correction of algebraic block codes. US Patent 4,490,811.
• 6: Berlekamp, E. R. 1984. Algebraic Coding Theory. Aegean Park Press.
• 7: Bleichenbacher and Nguyen. 2000. Noisy polynomial interpolation and noisy Chinese remaindering. In Advances in Cryptology---Eurocrypt 2000, Springer-Verlag, New York.
• 8: 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
• 9: Computer Emergency Response Team. 1999. CERT coordination center denial of service attacks. Available at http://www.cert.org/tech_tips/denial_of_service.html.
• 10: Deering, S. and Hinden, R. 1998. Internet protocol, version 6 (IPv6) specification. RFC 2460.
• 11: Dittrich, D. 1999a. The "Stacheldraht" distributed denial of service attack tool. Available at http://staff.washington.edu/dittrich/misc/stacheldraht.analysis.txt.
• 12: Dittrich, D. 1999b. The "Tribe Flood Network" distributed denial of service attack tool. Available at http://staff.washington.edu/dittrich/misc/tfn.analysis.
• 13: 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]
• 14: Ferguson, P. and Senie, D. 1998. Network ingress filtering: Defeating denial of service attacks which employ IP source address spoofing. RFC 2267. Available at http://www.ietf.org/rfc/rfc2267.txt.
• 15: Guruswami, V. and Sudan, M. 1999. Improved decoding of Reed--Solomon and algebraic-geometric codes. IEEE Trans. Inf. Theor. 45, 1757--1767.
• 16: Kent, S. and Atkinson, R. 1998a. IP authentication header. RFC 2402, Available at http://www.ietf.org/rfc/rfc2402.txt.
• 17: Kent, S. and Atkinson, R. 1998b. IP encapsulating security payload (ESP). RFC 2406, Available at http://www.ietf.org/rfc/rfc2406.txt.
• 18: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 19: Lee, H. and Park, K. 2001. On the effectiveness of probabilistic packet marking for IP traceback under denial of service attack. In Proceedings of IEEE INFOCOM 2001 (Anchorage, April), IEEE, Los Alamitos, Calif.
• 20: Nichols, K., Blake, S., Baker, F., and Black, D. 1998. Definition of the differentiated services field (DS field) in the IPv4 and IPv6 headers. RFC 2474.
• 21: Vadim Olshevsky , M. Amin Shokrollahi, A displacement approach to efficient decoding of algebraic-geometric codes, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.235-244, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301311]
• 22: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in FORTRAN (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 23: Ramakrishnan, K. and Floyd, S. 1999. A proposal to add explicit congestion notification (ECN) to IP. RFC 2481.
• 24: 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
• 25: Song, D. and Perrig, A. 2000. Advanced and authenticated marking schemes for IP traceback. Tech. Rep. UCB/CSD-00-1107 (June), University of California, Berkeley.
• 26: Ion Stoica , Hui Zhang, Providing guaranteed services without per flow management, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.81-94, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 27: Madhu Sudan, Algorithmic Issues in Coding Theory, Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, p.184-199, December 18-20, 1997
• 28: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

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

General Terms:
Algorithms, Design, Security

Keywords:
Internet protocol, traceback