An algebraic approach to IP traceback.
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.
Introduction
A denial of service attack is designed to prevent legitimate access to a resource. In
the context of the Internet, an attacker can "flood" a victim's connection with random
packets to prevent legitimate packets from getting through. These Internet denial of service
attacks have become more prevalent recently due to their near untraceability and
relative ease of execution [9]. Also, the availability of tools such as Stacheldraht [11]
and TFN [12] greatly simplify the task of coordinating hundreds or even thousands of
compromised hosts to attack a single target.
These attacks are so difficult to trace because the only hint a victim has as to the
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 border network without
a source address from the border network [14], attackers have countered by choosing
legitimate border network addresses at random. The traceback problem is also difficult
because many attacks are launched from compromised systems, so finding the source
of the attacker's packets may not lead to the attacker. Disregarding the problem of
finding the person responsible for the attack, if a victim was able to determine the path
of the attacking packets in near real-time, it would be much easier to quickly stop the
attack. Even finding out partial path information would be useful because attacks could
be throttled at far routers.
This paper presents a new scheme for providing this traceback data by having
routers embed information randomly into packets. This is similar to the technique
used by Savage, et al [24], with the major difference being that our schemes are based
on algebraic techniques. This has the advantage of providing a scheme that offers more
flexibility in design and more powerful techniques that can be used to filter out attacker
generated noise and separate multiple paths. Our schemes share similar backwards
compatibility and incremental deployment properties to the previous work.
More specifically, our scheme encodes path information as points on polynomials.
We then use algebraic methods from coding theory to reconstruct these polynomials at
the victim. This appears to be a powerful new approach to the IP traceback problem.
We note that although the study of traceback mechanisms was motivated by denial
of service attacks, there are other applications as well. These methods might be useful
for the analysis of legitimate traffic in a network. For example, congestion control,
robust routing algorithms, or dynamic network reconfiguration might benefit from real-time
traceback mechanisms.
The rest of the paper is organized as follows: Section 2 discusses related work,
Section 3 contains an overview of the problem and our assumptions, Section 4 presents
our approach for algebraically coding paths, Section 5 gives detailed specifications for
some of our schemes, Section 6 provides a mathematical analysis of the victim's re-construction
task, Section 7 discusses the issue of encoding marking data in IP packets,
and 8 gives conclusions and future work.
Related Work
The idea of randomly encoding traceback data in IP packets was first presented by
Savage, et al [24]. They proposed a scheme in which adjacent routers would randomly
insert adjacent edge information into the ID field of packets. Their key insight was
that traceback data could be spread across multiple packets because a large number
of packets was expected. They also include a distance field which allows a victim to
determine the distance that a particular edge is from the host. This prevents spoofing
of edges from closer than the nearest attacker. The biggest disadvantage of this scheme
is the combinatorial explosion during the edge identification step and the few feasible
parameterizations. The work of Song and Perrig provides a more in depth analysis of
this scheme [25].
There have been many other notable proposals for IP traceback since the original
proposal. Bellovin has proposed having routers create additional ICMP packets with
traceback information at random and a public key infrastructure to verify the source of
these packets [4]. This scheme can also be used in a non-authenticated mode, although
the attackers can easily forge parts of routes that are farther from the victim than the
closest of the attackers.
Song and Perrig have an improved packet marking scheme that copes with multiple
attackers [25]. Unfortunately, this scheme requires that all victims have a current map
of all upstream routers to all attackers (although Song and Perrig describe how such
maps can be maintained). Additionally, it is not incrementally deployable as it requires
all routers on the attack path to participate (although Song and Perrig note that it also
suffices for the upstream map to indicate which routers are participating).
Doeppner, Klein, and Koyfman proposed adding traceback information to an IP option
[13]. Besides the large space overhead, this solution would cause serious problems
with current routers, as they are unable to process IP packets with options in hardware.
R 4 R 5 R 6 R 7
A 3
A 4

Figure

1: Our example network.
It also causes others issues, for example, adding the option may require the packet to
be fragmented.
Burch and Cheswick have a scheme that uses UDP packets and does not require the
participation of intermediate ISPs [8]. This scheme, however, assumes that the denial
of service attack is coming from a single source network. This differs from us as we
aim to distinguish multiple attacking hosts.
Lee and Park have analyzed packet marking schemes in general [19]. Their paper
contains general tradeoffs between marking probability, recovered path length, and
packets received, that can be applied to any of the probabilistic marking schemes, including
the one in this paper.
We refer the reader to Savage's paper for a discussion of other methods to detect
and prevent IP spoofing and denial of service attacks.
The algebraic techniques we apply were originally developed for the fields of coding
theory [15] and machine learning [2]. For an overview of algebraic coding theory,
we refer the reader to the survey by Sudan [27] or the book by Berlekamp [6].

Overview

This paper addresses what Savage, et al call the approximate traceback problem. That
is, we would like to recover all paths from attacker to victim, but we will allow for
paths to have invalid prefixes. For example, for the network shown in Figure 1, the
true path from the attacker A 1 to the victim V is R 4 R 2 R 1 . We will allow our technique
to also produce paths of the form R 2 R 6 R 4 R 2 R 1 because the true path is a suffix of the
recovered path.
Our family of algebraic schemes was motivated by the same assumptions as used
in previous work:
1. Attackers are able to send any packet
2. Multiple attackers can act together
3. Attackers are aware of the traceback scheme
4. Attackers must send at least thousands of packets
5. Routes between hosts are in general stable, but packets can be reordered or lost
6. Routers can not do much per-packet computation
7. Routers are not compromised, but not all routers have to participate
Algebraic Coding of Paths
We will now present a series of schemes that use an algebraic approach for encoding
traceback information. All of these schemes are based on the principal of reconstructing
a polynomial in a prime field. The basic idea is that for any polynomial f (x) of
degree d in the prime field GF(p), we can recover f (x) given f (x) evaluated at (d +1)
unique points. Let A 1 ; A be the 32-bit IP addresses of the routers on path P.
We associate a packet id x j with the
jth packet. We then somehow evaluate f P as the packet travels along the path,
accumulating the result of the computation in a running total along the way. When
enough packets from the same path reach the destination, then f P can be reconstructed
by interpolation. The interpolation calculation might be a simple set of linear equa-
tions, if all of the packets received at the destination traveled the same path. Otherwise,
we will need to employ more sophisticated interpolation strategies that succeed even in
the presence of incorrect data or data from multiple paths [5, 28, 15, 7]. These methods
were developed originally for use in coding theory and learning theory.
A naive way to evaluate f P (w) would be to have the jth router add A j w n j into
an accumulator that kept the running total. Unfortunately, this would require that each
router know its position in the path and the total length of the path. We could eliminate
the need for each router to know the total length of the path (while still requiring each
router to know its position in the path) by reordering the coefficients of f
However, we can do even better by sticking with our original
ordering, and using an alternative means of computing the polynomial. Specifically,
to compute f P (w), each router R j multiplies the amount in the accumulator by w, adds
returns the result to the accumulator, and passes the packet on to the next router
in the path (Horner's rule [18]). For example, ((((0  w)+R 1 )w+R 2 )w+R 3 )w+R
Notice that the router doesn't need to know the total length
of the path or its position in the path for this computation of f P .
4.1 Deterministic Path Encoding
The simplest scheme that uses this algebraic technique encodes an entire path. At
the beginning of a path, let FullPath 0; Each router i on the path calculates
FullPath is a random value passed in each
packet, R i is the router's IP address and p is the smallest prime larger than 2 32 1. The
value FullPath passed in the packet, along with x j , to the next router. At the
packet's destination FullPath will equal (R n x
which can be reconstructed by solving the following matrix equation over GF(p):B B B @
FullPath n;1
FullPath n;2
FullPath n;3C C C A
As long as all of the x i 's are distinct, the matrix is a Vandermonde matrix (and thus has
full rank) and is solvable in O(n 2 ) field operations [22].
Assuming that we get a unique x j in each packet, we can recover a path of length
d with only d packets. The downside, however, is that this scheme would require
log bits per packet (the first term is the encoding of the running
FullPath and the second term is the encoding of the x j and y j values). Even for modest
maximum path lengths of 16, the space required (68 bits, counting 4 bits for recording
the number of routers in the path, and 32 bits each for the x coordinate and y coordinate
of the point on the polynomial) far exceeds the number of bits available to us in an IP
header.
We could split a router's IP address into c chunks and add dlog 2 (c)e bits to indicate
which chunk was represented in a given packet. Another approach would be to have
each router add all of its chunks into each packet. That is, each router would update
FullPath c times, substituting each chunk of their IP address in order. The destination
could then trivially reconstruct the IP addresses by interpolating to recover -
R 1;1 +R 1;2 are the
successive chunks of R j . This would increase the degree of f by a factor of c, which
would impact the performance of the reconstruction algorithm.
4.2 Randomized Path Encoding
In the above schemes, we require FullPath 0; This implies that there is some
way for a router to know that it is the "first" participating router on a particular path.
In the current Internet architecture there is no reliable way for a router to have this
information. We must therefore extend our scheme to mitigate this problem.
In our revised scheme a router first flips a weighted coin. If it came up tails the
router would assume it was not the first router and simply follow the FullPath algorithm
presented above, adding its IP address (or IP address chunk) data. On the other
hand, if the coin came up heads, the router would assume it was the first router and
randomly choose a x j to use for the path. We will refer to this state as "marking mode."
This overall approach - which might be called the "reset paradigm" - was also used by
Savage et al. for their traceback solutions.
At the destination, we would receive a number of different polynomials, all representing
suffixes of the full path. In our example network, packets from A 1 could contain
R
We could change our marking strategy slightly. Whenever a router receives a
packet, it still flips a weighted coin. But now, instead of simply going into marking
mode for one packet when the coin comes up heads, the router could stay in marking
mode for the next t packets it receives. More generally, the reset behavior could follow
any Markov Process.
One problem is that attackers can cause more false paths than true paths to be
received at the victim. This is due to the fact the our choice of a small p creates large
number of packets in which no router on the packet's path is in marking mode. The
attacker can thus insert any path information he wishes into such packets. Because the
attacker can generally find out the path to his victim (using traceroute, for example) he
can compute FullPath 0;
This choice
will cause the victim to receive FullPath When trying to reconstruct
paths, the victim will have no indication as to which paths are real and which paths
are faked. Two solutions to this problem are to increase p or to store a hop count
(distance field) in the packet that each participating router would increment. Increasing
the probability makes it even harder to receive long paths. Adding a hop count would
prevent an attacker from forging paths (or suffixes of paths) that are closer than its
actual distance from the victim but would require dlog 2 (d)e more bits in the packet.
Our schemes could also make use of the HMAC techniques discussed by Song
and Perrig to ensure that edges are not faked, but this would require us to either use
additional space in the packets to store the hash or lose our incremental deployment
properties [25]. If we decided to make one of these tradeoffs, our scheme would be
comparably secure against multiple attackers.
4.3 Edge Encoding
We could add another parameter, ', that represents the maximum length of an encoded
path. The value of ' is set by the marking router and decremented by each participating
router who adds in their IP information. When the value reaches 0, no more routers
add in their information. For example, in the full path encoding scheme
encoding of edges between routers. When we call this an
"algebraic edge encoding" scheme.
The benefit of this change would be to decrease the maximum degree d of the
polynomials in order to reduce the number of packets needed out of a given set or
packets to recover a route. The cost of this change is that it would add dlog
bits to the packets.
Of course, if ' is less than the true path length, then reconstruction finds arbitrary
subsequences of the path (not just suffixes as in Full Path encoding). The victim still
has some work to do to combine these subsequences properly (as described in Savage
et al. Thus reconstruction in this scheme has an algebraic step followed by a
combinatorial step.
5 Pseudocode for Sample Algebraic Schemes
In this section, we present pseudocode for some sample algebraic marking schemes
that are based on the principles described in the previous section. Recall that each
router has a unique 32-bit id.
5.1 Algebraic Edge Encoding
Here is the router's pseudocode for Edge1, an algebraic edge encoding scheme. Each
packet is marked with is the number of x values. The
degree of the polynomial is one.
Marking procedure at router R:
for each packet w
with probability p
w.xval := random;
w.yval := R;
w.flag :=
otherwise if w.flag
w.yval := w.yval * w.xval
w.flag := 0
Here is Edge2, algebraic edge encoding with c "chunks" per "hop". Each packet is
marked with d32=ce+ dlogne+1 bits. The degree of the polynomial is 2c 1.
Marking procedure at router R:
for each packet w
with probability p
w.xval := random;
w.yval := R[c] w.xval-{c-1}
w.flag :=
otherwise if w.flag
w.yval := w.yval * w.xval-c
w.flag := 0
Here is Edge3, which is identical to Edge2 except that each packet also has a distance
field ("hop count"). Following Savage et al., we reserve five bits for the distance
field. Each packet is marked with d32=ce+ dlogne+6 bits. The degree of the polynomial
is 2c 1.
Marking procedure at router R:
for each packet w
with probability p
w.xval := random;
w.yval := R[c] w.xval-{c-1}
w.flag :=
w.dist := 0;
otherwise if w.flag
w.yval := w.yval * w.xval-c
w.flag := 0;
w.dist
Here is Edge4, which is identical to Edge3 except that the second router only contributes
half of the bits of its router id. This lowers the degree of the polynomial,
and introduces a little uncertainty into the reconstruction process (if two routers at the
same distance from the victim had router id's that agreed on all of the contributed bits).
Each packet is marked with d32=ce+ dlogne +6 bits. The degree of the polynomial is
1:5c 1.
Marking procedure at router R:
for each packet w
with probability p
w.xval := random;
w.yval := R[c] w.xval-{c-1}
w.flag :=
w.dist := 0;
otherwise if w.flag
w.yval := w.yval * w.xval-{c/2}
w.flag := 0;
w.dist
5.2 Algebraic Full Path Encoding
Here is the router's pseudocode for Full1, the full path encoding scheme. Each packet
is marked with 32+dlogne bits, where n is the number of possible x values. The degree
of the path polynomial is at most L, the length of the path.
Full1 Marking procedure at router R:
for each packet w
with probability p
w.xval := random;
w.yval := 0;
w.yval := w.yval * w.xval
Here is the router's pseudocode for Full2, the full path encoding scheme with a
distance field ("hop count"). Following Savage, we reserve five bits for the distance
field, so each packet is marked with 37+ dlogne bits.
Full2 Marking procedure at router R:
for each packet w
with probability p
w.xval := random;
w.yval := 0;
w.dist := 0;
w.yval := w.yval * w.xval
w.dist
6 Path Reconstruction by the Victim
In this section, we look more closely at the problem of path reconstruction by the
victim. Let k denote the number of attack paths. Let L denote the expected length of
an attack path. For simplicity, we will assume that all attack paths are very close to L
in length.
For the main scheme of Savage et al. (which uses a total of 16 bits), the complexity
of path reconstruction by the victim is O(Lk 8 ). The exponent of eight reflects a
combinatorial task that the victim must try by brute force. Of course, if they had more
room to work with in their marking scheme, then the reconstruction complexity would
go down. For example, if they used 23 bits for their marking scheme (and divided
the "padded" router id into four 16-bit chunks), then the victim's reconstruction task
reduces to O(Lk 4 ).
Our goal is to design algebraic schemes that improve on the reconstruction complexity
of Savage et al. There are two main algebraic reconstruction approaches that
we consider:
Reed-Solomon List Decoding: Given
polynomials of degree at most d that pass through at least m of these points. Guruswami-Sudan
give an algorithm to solve this problem in time O(N 3 ) when N < m 2 =d. An
improvement by Olshevsky and Shokrollahi reduces the time to O(N 2:5 ).
More precisely, the reconstruction algorithm due to Guruswami and Sudan [15]
can be implemented in a number of ways. The most straightforward implementation
would take time O(n 3d ) to recover all edges for which we received at least
dn out of
packets. However, this drops to O(n 3 requiring only slightly more packets:
dn(1+d) out of n, for any d  1. By scaling d appropriately, this allows us to trade
off computation time (and memory) for accuracy. A recent algorithmic breakthrough
by Olshevsky and Shokrollahi would reduce our reconstruction time even further, to
O(n 2:5 ) [21]. Moreover, this new algorithm is highly parallelizable (to up to O(n)
processors), which suggests that distributing the reconstruction task might speed things
up even more.
Noisy Polynomial Interploation: Given
at most m, find all polynomials f of degree at most d such that f
Bleichenbacher-Nguyen give an algorithm to solve this problem whenever m < n=d,
with running time identical to the Reed-Solomon List Decoding problem. They give
other algorithms that work even when the bound m < n=d is not met.
Types of Packets: Let us assume that each packet that the victim receives is one of
three possible types. A "true packet" contains a point on a polynomial that corresponds
to a real attack path. A "bogus packet" contains a point created by an attacker
outside the periphery, and never reset by any honest router along an attack path. A
"stray packet" contains a point on a polynomial that corresponds to normal non-attack
traffic. When a denial of service attack is underway, we assume that the fraction of
stray packets is very small compared to true and bogus packets.
False Positives: A "false positive" is a polynomial that is recovered by the reconstruction
algorithm, but does not correspond to part of an actual attack path. For Reed-Solomon
list decoding, the expected number of false positives in a random sample is
about (N!=(m!(N m)!))  (1=q) m d 1 . For noisy polynomial interpolation, the expected
number of false positives in a random sample is about m n =q n d 1 . For the main
scheme of Savage et al., the expected number of false positives is about m 8 =2
When the marking scheme has no distance field, then we must also be concerned
with "bogus edges" or "bogus paths" that the attacker can cause to appear in our sam-
ple. We will consider this separately from the issue of false positives that arise at
random.
A moderate number of false positives is not a serious problem. Consider our marking
scheme Edge3. The victim reconstructs a set of candidate edges for each distance.
Each set of candidate edges includes true edges and "false positive" (but no "bogus
edges" from the attacker assuming that no attacker is within this distance of the vic-
tim). Now the victim attempts to assemble paths by connecting edges from distance '
with edges from distance ' + 1. There is certainly no problem unless the first endpoint
of a false positive edge from some distance ' matches the second endpoint of a false
positive or true edge from distance ' + 1.
Let f be the expected number of false positives at each distance, and let k be the
number of true edges at each distance. Then there are f expected false positives at
distance expected false positives and true edges at distance ' + 1. Let M
be the number of distinct router id's or partial router id's that are possible (e.g., 2
for Edge3). The probability of an accidental match is less than 1 ((M f )=M) f +k
which is very close to 1 e f ( f +k)=M . (When f is close to
this probability is
unacceptably high.) The probability of an accidental match at any distance is less than
is the length of the longest path.
We now analyze the effectiveness of these approaches to path reconstruction. For
each approach, the best known algorithms impose constraints on the design parameters
for our marking schemes. It will be convenient for us to consider separately marking
schemes that have a distance field and marking schemes that do not.
6.1 Reconstruction With a Distance Field
When the marking scheme has a distance field, the task of the victim is simplified. The
victim can select a sample of packets for which w.dist = ', for any given '. As long as
no attacker is within distance ' of the victim, this sample will contain only true packets
with points on polynomials that were last reset by routers at distance '.
6.1.1 Guruswami-Sudan Reconstruction With a Distance Field
The path reconstruction problem faced by the victim can be viewed as a Reed-Solomon
list decoding problem. The distinct points are chosen from a random sample of the
distinct points in packets that reach the victim.
The victim can filter out packets that were last reset at distance ', for every '. This
simplifies the Reed-Solomon list decoding problem, by creating a smaller problem
instance for each distance. We need nk packets from distance ' to have n distinct
points from each of k polynomials. The victim collects the largest possible sample
of distinct points from packets with w.dist = ' for every '. We need N < n 2 =d to
reconstruct the polynomials using the Guruswami-Sudan algorithm. Lastly, we need
for the efficiency of reconstruction to improve on Savage et al.
This has at least a few solutions, but the improvements are not so compelling. For
example, using Edge3 with three 11-bit chunks can be competitive with Savage et al.
for certain values of k.
6.1.2 Bleichenbacher-Nguyen Reconstruction With a Distance Field
The problem faced by the victim can be viewed as a noisy polynomial interpolation
problem. The values x are all of the possible x values. Each set S i contains
all of the distinct y values such that occurs in some packet within a random
sample of all received packets. The polynomial f could be any of the polynomials that
corresponds to a true attack path or a stray path.
The victim could proceed as follows. He looks at a sample of N packets (for suitably
large N), and for each x i he chooses a set S i of size m from all of the
in the sample. If the number of distinct y values for which occurs in the sample
is greater than m, then the victim chooses which m values to include in S i at random.
The victim can filter out packets that were last reset at distance ', for every '. This
creates a smaller problem instance for each distance. For each problem instance, the
number of S i sets is equal to n, the number of possible x values. The size of each S i
is k, the number of attack paths. The degree of each polynomial is at most d, which
depends on the particular algebraic encoding method we are using.
False Positives: There are k n ways of taking one x value from each set. Each of these
will actually be a polynomial of degree d or less with probability at most 1=q n d 1 .
Here q is the size of the finite field, which is essentially the number of distinct y values.
We need the expected number of false positives k n =q n d 1 to be reasonably small.
For the basic reconstruction algorithm of Bleichenbacher-Nguyen, we need k <
n=d. Three other algorithms by Bleichenbacher-Nguyen work for many k;n;d even if
they do not satisfy k < n=d.
A "meet-in-the-middle" algorithm has running time (n d)m n=2 with precomputation
that uses memory which is O(m n=4 logq). Note that this is independent
of k.
A "Grobner basis reduction" algorithm computes a Grobner basis reduction on a
system of k polynomial equations in d +1 unknowns. The best known Grobner
basis algorithms are super-exponential in d, but reasonably efficient for small d
(e.g., d < 20).
A "lattice basis reduction" algorithm performs a lattice basis reduction on an
1)-dimensional lattice in Z nk over a finite field of size about n. This
method will be ineffective for our application because the size of the finite field
is too small.
For efficiency over Savage et al., we need (nk) 2:5 < k 8 . Here are some interesting
instantiations of our schemes with respect to this method of reconstruction:
Example 1: Edge3 encoding with 12 distinct x values (represented in a 4-bit xval
field) and 8-bit yval field. Then the noisy polynomial problem has 12 S i sets, where
the size of each S i is k, the number of attack paths. The degree of each polynomial is
at most 7. The size of the finite field is 256. The meet-in-the-middle algorithm takes
time 8k 6 , which compares favorably to the k 8 required by Savage et al. The Grobner
basis reduction algorithm should also be reasonably efficient here. The total size of
this marking scheme is bits. However, the number of false positives is unacceptably
high here: k 12 =2
Example 2: Edge4 encoding with 12 distinct x values (in a 4-bit xval field) and 8-
bit yval field. Then the degree of each polynomial is at most 5. The running time
for the meet-in-the-middle algorithm is about 8k 6 . The running time for the Grobner
basis reduction algorithm is faster than in the previous example. The expected number
of false positives is lower than in the previous example: k 12 =2 48 . If
we expect about one false positive at each distance. (Of course, the risk from false
positives is slightly greater than in the previous case, because the number of possible
partial router id's is only 2 22 . Thus there will be slightly more accidental matches of
endpoints involving a bogus edge, but it is not significantly worse.) The total size of
this marking scheme is bits.
Example 3: Edge4 encoding with
Then the degree of each polynomial is at most 4 (using 22 bits of second router id).
Running time for meet-in-the-middle is about 6k 5 , versus k 8 for Savage et al. Number
of false positives is about Savage. For example, this is expected
positives for false positives for are quite
manageable. The total size of this marking scheme is 21 bits.
Example 4: Edge4 encoding with
of each polynomial at most 4. Running time for meet-in-the-middle is about 4k 4 .
Number of false positives is about k 8 =2 33 (e.g., 1=2 when
The total size of this marking scheme is 20 bits.
Example 5: Edge4 encoding with
of each polynomial at most 4. Running time for meet-in-the-middle is about 8k 6 . Number
of false positives is about k 12 =2 77 (e.g., 2 5 when
both of which are quite manageable). The total size of this marking scheme is 21 bits.
6.2 Reconstruction Without a Distance Field
For reconstruction when the marking scheme does not have a distance field, we do not
achieve schemes that are competitive with Savage et al. Our analysis will begin with
some facts and simplifying assumptions about the distribution of received packets by
the victim.
6.2.1 Distribution of Received Packets
be the fraction of packets arriving on the ith attack path that reach the victim
as bogus packets. Let T i be the fraction of packets on the ith attack path that reach the
victim as true packets. Let F i be the fraction of packets on the ith attack path that reach
the victim as true packets that were only reset by the furthest router on that path. By
Assumption
For all of the encoding schemes (unless "marking mode" is used), we have F
Viewed as a function of p over fraction takes on its maximum
value at implies that F
For all of the encoding schemes, we have
When this implies that B . The fact that there can be
such a large fraction of bogus packets arriving on each path has serious consequences
for our marking schemes without a distance field.
Let B;T;F be the fractions of bogus packets, true packets, and furthest packets for
all paths to the victim. If we assume that the arrival rate of packets on all attack paths
is approximately the same, then
When "marking mode" is used, the probability that a router is not in reset mode is
Coupon Collector's Bound: A sample of lC logC elements, drawn with replacement
from according to the uniform distribution, is very likely to contain all C possible
values, for some small constant l.
6.2.2 Guruswami-Sudan Reconstruction Without a Distance Field
The victim can choose a random sample of distinct points in the packets that reach him.
Without a distance field, he cannot partition the packets into smaller samples by last
Assume that the routers are using an edge encoding scheme, and assume that we
succeed if we can reconstruct all of the furthest edge polynomials. Let us also assume
that we will search for polynomials that pass through n distinct points, where n is the
number of distinct x values.
There are actually three distinct levels of reconstruction success that can be con-
sidered: (a) The sample of N points contains at least n points on every furthest edge
polynomial with overwhelming probability; (b) The sample of N points contains at
least n points on some furthest edge polynomial with overwhelming probability; (c)
The sample of N points contains at least n points on some furthest edge polynomial
with non-negligible probability q.
For case (a), the Guruswami-Sudan algorithm needs to be applied only once to a
random sample of N points. For case (b), the algorithm needs to be applied lklogk
times to independent random samples of N points (coupon collector's problem on the
set of k furthest edge polynomials). For case (c), the algorithm needs to be applied
lklogk=q times to independent random samples of N points.
For case (a), it suffices to have N  (lnklog(nk))=(p(1 p) L 1 ). That is because
we are very likely to get a complete set of all n possible x values for all k edge poly-
nomials. This implies that lnklog(nk) "samples" are sufficient. By the analysis of
the preceding subsection, a "sample" from a furthest edge polynomial is expected in
fraction of all of the packets. When combined with the Guruswami-Sudan
bound, we get n 2 =d > (lnklog(nk))=(p(1 p) L 1 ). Assuming that
we have
For case (b), it suffices to have N  M n;k =(p(1 p) L 1 , where M n;k is the answer
to the following "occupancy problem": Throw M n;k balls into k bins, and expect to
find lnlogn balls in the bin with the most balls. By the Pigeonhole Principle, it is
certainly true that M n;k < lnklogn. In fact, the actual value for M n;k is quite close to
this. Combined with the Guruswami-Sudan bound, we get n 2 =d > lnklogn=(p(1
Assuming that
ln=logn > dk(L 1)e:
For case (c), we can reduce the value of M n;k a little, but it doesn't appear to be
significant for our purposes.
Of course, for any of (a), (b), or (c), we can reduce N by eliminating from the
sample any duplicate points. Since as many as 1=e of all packets in the sample could
be bogus packets from the attacker, removing duplicate points will have limited benefit.
We can find no solution that yields a marking scheme that is more efficient than Savage
et al. Moreover, for any plausible instantiation, the number of false positives and bogus
edges (or bogus paths) is unacceptably high.
6.2.3 Bleichenbacher-Nguyen Reconstruction Without a Distance Field
The victim can proceed as described at the start of Section 6.1.2, although without a
distance field the packets cannot be partitioned by last reset distance.
Version H. Length Type of Service (8-bit) Total Length
Fragment ID (16-bit) Flags
Fragment Offset
Time to Live Protocol Header Checksum
Source IP Address
Destination IP Address

Figure

2: The IP Header. Darkened areas represent underutilized bits.
Suppose that N is chosen to be large enough that all of the points on some furthest
polynomial are included with high probability. The probability that a given S i
includes a point from f is at least m=n. The probability that reconstruction succeeds is
at least (m=n) n . The basic algorithm of Bleichenbacher and Nguyen solves the noisy
polynomial interpolation whenever m < n=k.
This approach does not seem too promising when k > 1. In this case, (m=n) n < 2 n .
Thus reconstruction is unlikely to succeed.
the victim can choose positive integer c. The
probability that reconstruction succeeds is at least (1 c=n) n which is about e c . Un-
fortunately, either the number of false positives is unacceptably large, or the success
probability is unacceptably small.
Another approach would be to have the victim bias his sample with respect to how
frequently different points occurred in the packets that reached him. Unfortunately, this
does not appear to work well either. Since the victim will not be able
to recognize the true packets that contain points from the furthest polynomials.
We conclude that when the marking scheme does not have a distance field, we do
not see how to use the Bleichenbacher-Nguyen method of polynomial reconstruction,
at least using their simplest algorithm. It is possible that their other algorithms, e.g.,
based on Grobner basis reduction, might be more effective.
7 Encoding Path Data
We now need a way to store our traceback data in IP packets. We will try to maximize
the number of bits available to us while preserving (for the most part) backwards
compatibility.
7.1 IP options
An IP option seems like the most reasonable alternative for storing our path informa-
tion. Unfortunately, most current routers are unable to handle packets with options in
hardware [3]. Even if future routers had this ability, there are a number of problems associated
with this approach as presented by Savage, et al [24]. For all of these reasons
we have concluded that storing data in an IP option is not feasible.
7.2 Additional Packets
Instead of trying to add our path data to the existing IP packets, we could instead send
the data out of band using a new protocol that would encapsulate our data. While this
may have limited uses for special cases (such as dealing with IP fragments), a general
solution based on inserting additional packets requires a means of authenticating these
packets. This is because, presumably, the number of inserted packets is many orders
of magnitude less than the number of packets inserted by the attacker. Thus, because
we assume that an attacker can insert any packet into the network, the victim can be
deluged with fake traceback packets, preventing any information to be gained from the
legitimate packets.
7.3 The IP Header
Our last source of bits is the IP header. There are several fields in the header that may
be exploited for bits, with varying tradeoffs. As shown in Figure 2, we have found 25
bits that might possibly be used.xs
7.3.1 The TOS Field
The type of service field is an 8 bit field in the IP header that is currently used to allow
hosts a way to give hints to routers as to what kind of route is important for particular
packets (maximized throughput or minimized delay, for example) [1]. This field has
been little used in the past, and, in some limited experiments, we have found that
setting this field arbitrarily makes no measurable difference in packet delivery. There
is a proposed Internet standard [20] that would change the TOS field to a "differentiated
services field." Even the proposed DS field has unused bits, however, there are already
other proposed uses for these bits (e.g. [23]).
7.3.2 The ID Field
The ID field is a field used by IP to permit reconstruction of fragments. Naive
tampering with this field breaks fragment reassembly. Since less than 0:25% of all
Internet traffic is fragments [26], we think that overloading this field is appropriate.
A more in-depth discussion of the issues related to its overloading can be found in
Savage's work [24].
7.3.3 The Unused Fragment Flag
There is an unused bit in the fragment flags field that current Internet standards require
to be zero. We have found that setting this bit to one has no effect on current imple-
mentations, with the exception that when receiving the packet, some systems will think
it is a fragment. The packet is still successfully delivered however, because it looks to
those systems as though it is fragment 1 of 1.
Our Selection
We could choose to use up to 25 bits out of the ID, flag, and TOS fields. This would
suffice for all of the examples given in Section 6.1.2. The implications of using multiple
fields in the IP header simultaneously are modest, since the lost functionality appears to
be the union of what would break due to overwriting each field separately. The impact
on header checksum calculation is modest, as this can be done in hardware using the
standard algorithm.
Of course, the algebraic marking scheme is independent of the choice of bits. The
decision of where to put the marking data must be seen as conditional, subject to change
as new standards arise.
7.4 IPsec
The interoperability of a traceback scheme with IPsec should be considered. The Encapsulated
Payload (ESP) [17], which encrypts a datagram for confidentiality,
provides no problem for a traceback scheme, as it does not assume anything about the
surrounding datagram's headers. The Authentication Header (AH) [16], does present
an issue for IPv4. Using the AH, the contents of the surrounding datagram's headers
are hashed. Certain header fields are considered mutable (e.g., Fragment Offset), and
not included in the hash computation. Unfortunately, the mutable fields in the IPv4
header are unusable for traceback: they either are necessary for basic IP functionality,
or reusing them breaks backward compatibility with current IP implementations.
7.5 IPv6
Since IPv6 does not have nearly as many backwards compatibility issues as IPv4,
the logical place to put traceback information is a hop-by-hop option in the IPv6
header [10]. However, schemes such as those presented here are still valuable because
they use a fixed number of bits per packet thereby avoiding the generation of
fragments. Unlike the case in IPv4, we can set the appropriate bit in the Option Type
field to indicate that the data in the option is mutable, and should be treated as zero for
the purposes of the Authentication Header.
We have not worked out the best way to accommodate IPv6's 128-bit addresses,
but note that due to alignment issues, one is likely to select an option length of 8n+6
bytes, n  0. It would likely be the case that 0
8 Conclusion and Future Work
We have presented a new algebraic approach for providing traceback information in IP
packets. Our approach is based on mathematical techniques that were first developed
for problems related to error correcting codes and machine learning. Though we have
proposed it in the context of a probabilistic packet marking scheme, our algebraic approach
could also be applied to an out-of-packet scheme. The resulting scheme would
have the desirable property of allowing multiple routers to act on the extra packet while
it remains at a small constant size. Our marking schemes have applications for other
network management scenarios besides defense against denial of service.
One important open problem is to find better instantiation of the specific methods
we have proposed. In particular, a successful approach based on full path tracing would
be attractive. More generally, it would be interesting to explore resource and security
tradeoffs for the many parametrizations of our schemata. Lower bounds on the size of
any marking scheme would be most helpful. It would also be interesting to explore the
use of algebraic geometric codes in marking schemes.

Acknowledgments

We would like to thank David Goldberg and Dan Boneh for valuable discussions. We
would also like to thank Dawn Song, Adrian Perrig, Ramarathnam Venketesan, Glenn
Durfee, and the anonymous referees for helpful comments on earlier versions of this
paper.



--R

Type of service in the internet protocol suite.
Reconstructing algebraic functions from mixed data.
Personal Communications
ICMP traceback messages.
correction of algebraic block codes.
Algebraic Coding Theory.
Bleichenbacher and Nguyen.
Tracing anonymous packets to their approximate source.
CERT coordination center denial of service attacks.
Internet protocol
"stacheldraht"
"Tribe Flood Network"
Using router stamping to identify the source of IP packets.
Network ingress filtering: Defeating denial of service attacks which employ IP source address spoofing.
Improved decoding of Reed-Solomon and algebraic-geometric codes
IP authentication header
IP encapsulating security payload (ESP)
The Art of Computer Programming
On the effectiveness of probabilistic packet marking for ip traceback under denial of service attack.
Definition of the Differentiated Services field (DS field) in the IPv4 and IPv6 headers.
A displacement approach to efficient decoding of algebraic-geometric codes
Numerical Recipes in FORTRAN: The Art of Scientific Computing.
A proposal to add Explicit Congestion Notification (ECN) to IP.
Practical network support for IP traceback.
Advanced and authenticated marking schemes for IP traceback.
Providing guaranteed services without per flow management.
Algorithmic issues in coding theory.
Decoding of Reed Solomon codes beyond the error-correction bound
--TR
Numerical recipes in FORTRAN (2nd ed.)
The art of computer programming, volume 2 (3rd ed.)
Decoding of Reed Solomon codes beyond the error-correction bound
A displacement approach to efficient decoding of algebraic-geometric codes
Providing guaranteed services without per flow management
Practical network support for IP traceback
Using router stamping to identify the source of IP packets
Algorithmic Issues in Coding Theory

--CTR
Karthik Lakshminarayanan , Daniel Adkins , Adrian Perrig , Ion Stoica, Taming IP packet flooding attacks, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004
Hikmat Farhat, Protecting TCP services from denial of service attacks, Proceedings of the 2006 SIGCOMM workshop on Large-scale attack defense, p.155-160, September 11-15, 2006, Pisa, Italy
Florian P. Buchholz , Clay Shields, Providing process origin information to aid in computer forensic investigations, Journal of Computer Security, v.12 n.5, p.753-776, September 2004
David G. Andersen, Mayday: distributed filtering for internet services, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.3-3, March 26-28, 2003, Seattle, WA
Katerina Argyraki , David R. Cheriton, Loose source routing as a mechanism for traffic policies, Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, August 30-30, 2004, Portland, Oregon, USA
Haining Wang , Danlu Zhang , Kang G. Shin, Change-Point Monitoring for the Detection of DoS Attacks, IEEE Transactions on Dependable and Secure Computing, v.1 n.4, p.193-208, October 2004
Andrey Belenky , Nirwan Ansari, On deterministic packet marking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.10, p.2677-2700, July, 2007
Sherif Khattab , Rami Melhem , Daniel Moss , Taieb Znati, Honeypot back-propagation for mitigating spoofing distributed Denial-of-Service attacks, Journal of Parallel and Distributed Computing, v.66 n.9, p.1152-1164, September 2006
Brent Waters , Ari Juels , J. Alex Halderman , Edward W. Felten, New client puzzle outsourcing techniques for DoS resistance, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA
Hassan Aljifri, IP Traceback: A New Denial-of-Service Deterrent?, IEEE Security and Privacy, v.1 n.3, p.24-31, May
Zhiqiang Gao , Nirwan Ansari, A practical and robust inter-domain marking scheme for IP traceback, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.3, p.732-750, February, 2007
Christos Siaterlis , Vasilis Maglaris, One step ahead to multisensor data fusion for DDoS detection, Journal of Computer Security, v.13 n.5, p.779-806, October 2005
Christos Douligeris , Aikaterini Mitrokotsa, DDoS attacks and defense mechanisms: classification and state-of-the-art, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.5, p.643-666, 5 April 2004
traceback;internet protocol