Probabilistic packet marking (PPM) is a technique designed to identify packet traffic sources with low storage and processing overhead on network routers. In most previous PPM approaches, individual path messages carry only partial path information.These methods are susceptible to ``path falsification'' attacks, which greatly reduce their effectiveness. This work proposes a path-falsification-attack free PPM algorithm called Path Information Caching and Aggregation (PICA) that records paths of packet streams in fix-length path messages, thus eliminating the need of path reconstruction at the receiver end. Besides, by using a router's forwarding table to decompose packet volume, this semi-stateful method is more accurate in traffic volume report. It also supports both a packet rate-based path message generation algorithm and a redundant path message suppression mechanism to further eliminate path messages with the same destination. Finally, PICA protects PICA routers from being attacked by faked path messages.
Distributed Denial of Service (DDoS) attacks take the form of a master coordinating a large number of slaves that each mount a DoS attack on a single victim. Because the number of slaves involved in an attack can be in the range of thousands and more, either the victim's server or the victim's network link to the Internet is easily overwhelmed by such a sudden jump in input loads, thus denying the service that the victim would otherwise provide to legitimate users. But if attack paths could be detected, than proper packet filter could be installed into the most upstream routers of attack packet paths, and thus eliminate the attack packets before they even have a chance to reach the victim. Several schemes have been proposed to solve this packet source identification problem using probabilistic packet marking (PPM). PPM can be classified into an in-band approach, which piggybacks path information on payload packets' IP header fields that are rarely used, and an out-of-band approach, which creates special path packets to deliver path information to the receiver hosts. Given the limited storage space, in-band approaches have no choice but to attach only partial path information to each ``marked'' packet. Out-of-band ones, on the other hand, can choose to accumulate either whole (e.g., PICA) or partial (e.g., iTrace) path information.
Instead of using a stateless method as itrace, savage, song or using a stateful one which requires a router to record information of every network connection passing through it and is too expensive, we propose a semi-stateful approach to tackle the traffic source identification problem and achieve the best of both worlds: the accuracy and the lower additional network traffic of the stateful approach and the smaller performance overhead on network routers of the stateless approach. The key idea of our approach, Path Information Caching and Aggregation} (PICA), is to exploit standard routing table entries as caching points for packet traffic that share the same trajectory path through the network. Because PICA partitions packet traffic through a router according to their destination network address, it can more accurately identify attack streams when they arise. At the same time, because PICA is tightly integrated with the generic routing table look-up process, its performance cost is reduced to the minimum.
PICA makes the following assumptions:
We have performed a trace-driven simulation study on the proposed PICA
algorithm and compared its effectiveness with IETF's iTrace scheme by varying
the sampling probability, the number of attack sources, and attack traffic rate.
Compared to iTrace, the PICA algorithm reduces the total number of
path messages required by a factor of more than 2,while reporting traffic volume more accurately.