A general model of probabilistic packet marking for IP traceback

Liming Lu, Mun Choon Chan, Ee-Chien Chang

Abstract

In this paper, we model Probabilistic Packet Marking (PPM) schemes for IP traceback as an identification problem of a large number of markers. Each potential marker is associated with a distribution on tags, which are short binary strings. To mark a packet, a marker follows its associated distribution in choosing the tag to write in the IP header. Since there are a large number of (for example, over 4,000) markers, what the victim receives are samples from a mixture of distributions. Essentially, traceback aims to identify individual distribution contributing to the mixture. Guided by this model, we propose Random Packet Marking (RPM), a scheme that uses a simple but effective approach. RPM does not require sophisticated structure/relationship among the tags, and employs a hop-by-hop reconstruction similar to AMS [16]. Simulations show improved scalability and traceback accuracy over prior works. For example, in a large network with over 100K nodes, 4,650 markers induce 63% of false positives in terms of edges identification using the AMS marking scheme; while RPM lowers it to 2%. The effectiveness of RPM demonstrates that with prior knowledge of neighboring nodes, a simple and properly designed marking scheme suffices in identifying large number of markers with high accuracy.
BibTeX
@inproceedings{lu2008general,
  author = {Liming Lu and Mun Choon Chan and Ee-Chien Chang},
  title = {{A general model of probabilistic packet marking for IP traceback}},
  booktitle = {AsiaCCS},
  year = {2008},
  doi = {10.1145/1368310.1368337},
}

Loading related content...

Figure