Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation

Mechanisms to trace attack packets towards the source is an important step to counter denial-of-service (DoS) attack. There are two types of techniques. One is based on marking packets with path information probabilistically which is referred to as Probabilistic Packet Marking (PPM) schemes. The other is to store packet information inside each router which is termed as storage-based schemes. Due to the limited space in the IP packet header that can be used for packet marking, to trace attackers not very close to the victim, PPM schemes require either an extremely large number of packets or infeasible computation overhead. And it is difficult to deal with distributed DoS attack. Storage-based schemes currently require per-packet processing. This requires large and expensive memory space even if only digest information is stored. In this paper, we propose a much more scalable solution. The basic idea is to store information of sampled packets. A novel {it space-coding} Bloom filter is used to store information of sampled packets. The Bloom filter at each router is tested with two different sets of pack ets. One includes all the attack packets received by the victim. The other includes the attack packets stored at the downstream neighbor. If during one of these two tests enough number of positives is found, then the router is identified as bad node. We do this process iteratively to construct the attack tree. Some heuristic techniques are used to improve the performance. We show that scalability is greatly improved using simulations on real network topologies.