An Algebraic Approach to IP TracebackDREW DEANSRI InternationalMATT FRANKLINU.C. DavisandADAM STUBBLEFIELDRice UniversityWe present a new solution to the problem of determining the path a packet traversed over theInternet (called the traceback problem) during a denial-of-service attack. This article reframes thetraceback problem as a polynomial reconstruction problem and uses algebraic techniques fromcoding theory and learning theory to provide robust methods of transmission and reconstruction.Categories and Subject Descriptors: C.2.5 [Computer-Communication Networks]: Localand Wide-Area Networks—internet; C.2.0 [Computer-Communication Networks]: General—security and protectionGeneral Terms: Algorithms, Design, SecurityAdditional Key Words and Phrases: Internet protocol, traceback1. INTRODUCTIONA denial-of-service attack is designed to prevent legitimate access to a re-source. In the context of the Internet, an attacker can “flood” a victim’sconnection with random packets to prevent legitimate packets from gettingthrough. These Internet denial-of-service attacks have become more preva-lent recently due to their near untraceability and relative ease of execution[Computer Emergency Response Team 1999]. Also, the availability of tools suchas Stacheldraht [Dittrich 1999a] and TFN [Dittrich 1999b] greatly simplifiesthe task of coordinating hundreds or even thousands of compromised hosts toattack a single target.An earlier version of this paper appeared in Proceedings 2001 Network & Distributed SystemSecurity Symposium, February 8–9, 2001, San Diego, pp. 3–12. This work is partially supported byDARPA under Grant Number N66001-00-1-8921.Authors’ addresses: D. Dean, SRI International, 333 Ravenswood Ave., Mento Park, CA 94025;M. Franklin, University of California at Davis, Dept. of Computer Science, One Shields Ave., Davis,CA 95616; A. Stubblefield, 6330 Main Street, Houston, TX 77005; email: [email protected] to make digital/hard copy of part or all of this work for personal or classroom use isgranted without fee provided that the copies are not made or distributed for profit or commercialadvantage, the copyright notice, the title of the publication, and its date appear, and notice is giventhat copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers,or to redistribute to lists, requires prior specific permission and/or a fee.C°2002 ACM 1094-9224/02/0500–0119 $5.00ACM Transactions on Information and System Security, Vol. 5, No. 2, May 2002, Pages 119–137.120•D. Dean et al.These attacks are so difficult to trace because the only hint a victim has as tothe source of a given packet is the source address, which can be easily forged.Although ingress filtering can help by preventing a packet from leaving a bor-der network without a source address from the border network [Ferguson andSenie 1998], attackers have countered by choosing legitimate border networkaddresses at random. The traceback problem is also difficult because manyattacks are launched from compromised systems, so finding the source of theattacker’s packets may not lead to the attacker. Disregarding the problem offinding the person responsible for the attack, if a victim were able to determinethe path of the attacking packets in near real-time, it would be much easierto quickly stop the attack. Even finding out partial path information would beuseful because attacks could be throttled at distant routers.This article presents a new scheme for providing these traceback data byhaving routers embed information randomly into packets. This is similar to thetechnique used by Savage et al. [2000], with the major difference being that ourschemes are based on algebraic techniques. This has the advantage of providinga scheme that offers more flexibility in design and more powerful techniquesthat can be used to filter out attacker-generated noise and separate multiplepaths. Our schemes share similar backwards compatibility and incrementaldeployment properties with the previous work.More specifically, our scheme encodes path information as points on polyno-mials. We then use algebraic methods from coding theory to reconstruct thesepolynomials at the victim. This appears to be a powerful new approach to theIP traceback problem.We note that although the study of traceback mechanisms was motivated bydenial-of-service attacks, there are other applications as well. These methodsmight be useful for the analysis of legitimate traffic in a network. For example,congestion control, robust routing algorithms, or dynamic network reconfigu-ration might benefit from real-time traceback mechanisms.The rest of the article is organized as follows. Section 2 discusses relatedwork, Section 3 contains an overview of the problem and our assumptions,Section 4 presents our approach for algebraically coding paths, Section 5 givesdetailed specifications for some of our schemes, Section 6 provides a mathemat-ical analysis of the victim’s reconstruction task, Section 7 discusses the issueof encoding marking data in IP packets, and Section 8 gives conclusions andfuture work.2. RELATED WORKThe idea of randomly encoding traceback data in IP packets was first presentedby Savage et al. [2000]. They proposed a scheme in which adjacent routers wouldrandomly insert adjacent edge information into the ID field of packets. Theirkey insight was that traceback data could be spread across multiple packetsbecause a large number of packets were expected. They also include a distancefield which allows a victim to determine the distance that a particular edgeis from the host. This prevents spoofing of edges from closer than the nearestattacker. The biggest disadvantage of this scheme is the combinatorial explosionACM Transactions on Information and System Security, Vol. 5, No. 2, May 2002.An Algebraic Approach to IP Traceback•121during the edge identification step and the few feasible parameterizations. Thework of Song and Perrig [2000] provides a more in-depth analysis of this scheme.There have been many other notable proposals for IP traceback since theoriginal proposal. Bellovin [2000b] has proposed having routers create addi-tional ICMP packets with traceback information at random and a public keyinfrastructure to verify the source of these packets. This scheme can also beused in a nonauthenticated mode, although the attackers can easily forge partsof routes that are farther from the victim than the