#Iptrace examples series#

Deterministic packet marking īelenky and Ansari, outline a deterministic packet marking scheme. They state that this approach essentially reduces the probability of collision to (1/(211)m). Song and Perrig identify that this is not robust enough against collisions and thus suggest using a set of independent hash functions, randomly selecting one, and then hashing the IP along with a FID or function id and then encoding this. If a router decides not to mark the packet it merely increments the hop count in the overloaded fragment id field. If it finds a non-zero hop count it inserts its IP hash, sets the hop count to zero and forwards the packet on. If this is the case, it generates an 11-bit hash of its own IP address and then XORs it with the previous hop. Next, if any given hop decides to mark it first checks the distance field for a 0, which implies that a previous router has already marked it. Further, they suggest that two different hashing functions be used so that the order of the routers in the markings can be determined. This is based on the observation that a 5-bit hop count (32 max hops) is sufficient for almost all Internet routes. Īccordingly, Song and Perrig propose the following traceback scheme: instead of encoding the IP address interleaved with a hash, they suggest encoding the IP address into an 11 bit hash and maintain a 5 bit hop count, both stored in the 16-bit fragment ID field. As an example, with only 25 attacking hosts in a DDoS attack the reconstruction process takes days to build and results in thousands of false positives. Furthermore, the approach results in a large number of false positives. ĭue to the high number of combinations required to rebuild a fragmented edge id, the reconstruction of such an attack graph is computationally intensive according to research by Song and Perrig.

#Iptrace examples series#

When enough packets are received, the victim can reconstruct all of the edges the series of packets traversed (even in the presence of multiple attackers). Then, randomly select a fragment and encode it, along with the fragment offset so that the correct corresponding fragment is selected from a downstream router for processing. Their next approach is to further take this edge id and fragment it into k smaller fragments. This new data entity is called an edge id and reduces the required state for edge sampling by half.

Upon being detected at b (by detecting a 0 in the distance), b XORs its address with the address of a. Node a inserts its IP address into the packet and sends it to b. The first approach is to XOR each node forming an edge in the path with each other.

They suggest three ways to reduce the state information of these approaches into something more manageable. This approach would require more state information in each packet than simple node marking but would converge much faster.

The second approach, edge marking, requires that the two nodes that make up an edge mark the path with their IP addresses along with the distance between them. They propose that the router mark the packet with either the router’s IP address or the edges of the path that the packet traversed to reach the router.įor the first alternative, marking packets with the router's IP address, analysis shows that in order to gain the correct attack path with 95% accuracy as many as 294,000 packets are required. suggested probabilistically marking packets as they traverse routers through the Internet.