7.2. Traceback

Some of the first proposals for defending against DDoS included means to perform traceback to the agents of a DDoS network. The assumption is based on some DDoS tools spoofing the sources and relatively low numbers of agents (100 2,500). In the 1999 2000 time frame, it seemed inconceivable that larger networks with over 100,000 hosts [CER03] would exist in the near future.

An early proposal, ICMP Traceback by Bellovin, et al. [BLT01], was to send an ICMP packet, probabilistically every n (early proposals included n = 20,000) packets, containing a portion of the captured packet, from the observing router to the destination. The disadvantage is that under heavy attack, a target may miss those packets due to congestion of the network equipment, and some networks do not allow ICMP messages to travel across their border router. Even though the sampling of 1/n occurs, it does create additional traffic in the direction of the victim, which adds to the congestion.

Subsequent proposals used a technique called Probabilistic Packet Marking (PPM). Again, every 20,000 network packets to a destination, a router would mark a packet with a reference to itself.^[1] Such a low sampling frequency was chosen to avoid a heavy burden on the router infrastructure due to marking a high volume of traffic during a flooding attack. By analyzing several marked packets from a given source, the victim of the flood would try to build a path back to the attacker, or at least to the edge closest to the attacker on the marking infrastructure. The initial proposal by Savage et al. [SWKA00] did not have any provisions for authentication for those markings, but a later proposal added authentication and integrity checking [SP01]. Several techniques along these lines have been proposed, including single-bit techniques [Adl02]. One drawback is that a sufficiently spread DDoS attack network could stay below the limits of sampling. Some musings by Waldvogel [Wal02] on how PPM techniques could be fooled outline further problems PPM faces with regard to deception and denial of service techniques. One of the PPM schemes [SWKA00], at least, claims to provide some benefit without contiguous deployment, unlike the Pushback scheme. For an evaluation of Savage et al.'s packet-marking techniques, see Park et al. [PL01].

^[1] The IP identification field in the IP header is proposed to bear this mark. This field is used for assembly of fragmented packets. As only about 0.25% [SWKA00] of Internet traffic is fragmented packets, many packet-marking schemes use this field to put their marks in. It is likely that these schemes are not interoperable.

The hash-based traceback technique [SPS⁺01] asks participating routers to remember each packet they see, but for a limited time. This enables tracing of one-packet attacks such as "Ping of Death," but only if the query is fast. The Source Path Isolation Engine (SPIE) remembers packets by computing hashes over the invariant portions of an IP header (e.g., TTL and checksums removed). For additional space trade-offs, weak hashes, rather than strong cryptographic hashes, are deployed in the form of Bloom filters [SPS⁺02]. This passive recording capability does not have to exist inside the router even though hardware design considerations for inclusion in routers were discussed [SPS⁺02]. The SPIE designers thought of a way to place a passive tap on each interface of the router. Some critics initially thought it would be too expensive to add one device per interface, so the SPIE device was extended to be a SPIEDER with multiple connections to each interface cable on the router. Although the weak hashes allow for false positives, they are quickly disambiguated through multiple hash functions applied at different routers as the distance increases from the victim. The victim initiates a traceback request through an alternate network (real or virtual) connecting the traceback manager, the data-generation agents, and the routers. Due to the high volume of traffic on backbone networks, the time between receipt of an offending packet and the request for a traceback should be on the order of a few minutes, depending on network capacity and traffic [SMS⁺01].

Dean et al. [DFS01] take an algebraic approach to the traceback problem. Similar to Savage et al. [SWKA00], this technique embeds partial tracing information into IP packets at the router level. This new scheme uses algebraic techniques to encode path information into packets and to reconstruct them at the victim site. The authors hope to gain more flexibility in the design and improvements in discarding attacker-generated noise and providing multiple-path traceback.

PPM and algebraic traceback schemes make several assumptions. We quote:

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 generally stable, but packets can be reordered or lost.

6. Routers cannot do much per-packet computation.

7. Routers are not compromised, but not all routers have to participate.

These assumptions clearly differentiate these techniques from a single-packet technique like hash-based traceback [SPS⁺02]. The authors of [DFS01] discuss efficiency compared to Savage et al., as space requirements vary between 18 and 21 bits. In some cases, they achieve slightly better results for path reconstruction, but the number of false positives remains high. Aside from packet marking, an out-of-packet scheme is considered, similar to Bellovin [BLT01]. The authors realize that further algorithm improvement is necessary, and trade-offs need to be explored. This concept needs further refining, but could develop into a promising concept in the long run.

Two serious problems exist for traceback solutions:

1. Traceback solutions often become unacceptably complex and expensive when there are large numbers of sources or when sources are well distributed.

2. Traceback, in and of itself, does nothing to stop an attack. If perfect, it identifies the edge networks containing all DDoS sources. Does one then cut them off? Persuade them to clean up the DDoS agents? Counterattack? There are no good answers, except those that presume that one can characterize the attack well enough to distinguish the attack packets from all other packets. If one can do that, traceback may no longer be needed, as offending packets can be filtered using the characterization. Lacking such a DDoS oracle, one option would be to dynamically deploy filters or rate limiters close to identified sources. This would localize collateral damage and stop the flood of attack traffic. However, this calls for a complex and distributed system with the potential to inflict high damage when wrong, so it is not likely to lead to real-life deployment.