Abstract | ||
---|---|---|
The probabilistic packet marking (PPM in short) algorithm is a promising way to discover the Internet map, or an attack graph, that the attack packets traversed during a distributed denial-of-service attack. Yet, the PPM algorithm is not prefect as its termination condition is not well-defined in the literature. More importantly, without a proper termination condition, the attack graph constructed by the PPM algorithm would be wrong with a very high probability. In this work, we provide a precise termination condition for the PPM algorithm and name the new algorithm the rectified probabilistic packet marking (RPPM in short) algorithm. The most significant merit of the RPPM algorithm is that when the algorithm terminates, the algorithm guarantees that the constructed attack graph is correct with a specified level of confidence. We carry out simulations on the RPPM algorithm and show that the RPPM algorithm can guarantee the correctness of the constructed attack graph under 1) different probabilities that a router marks the attack packets, and 2) different structures of the network graph. The RPPM algorithm provides an autonomous way for the original PPM algorithm to determine its termination, and it is a promising mean to enhance the reliability of the PPM algorithm. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1109/TDSC.2007.70229 | IEEE Trans. Dependable Sec. Comput. |
Keywords | Field | DocType |
probabilistic packet,attack packet,ppm algorithm,rppm algorithm,attack graph,denial-of-service attack,original ppm algorithm,new algorithm,probabilistic packet marking algorithm,precise termination condition,algorithm guarantee,algorithm terminates,filtering,internet,distributed denial of service,indexing terms,distributed denial of service attack,encoding,helium | Denial-of-service attack,Computer science,Network packet,Correctness,Algorithm,Filter (signal processing),Theoretical computer science,Suurballe's algorithm,Router,Probabilistic logic,Distributed computing,Encoding (memory) | Journal |
Volume | Issue | ISSN |
5 | 1 | 1545-5971 |
Citations | PageRank | References |
9 | 0.54 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
T. Y. Wong | 1 | 9 | 0.54 |
Man Hon Wong | 2 | 814 | 233.13 |
John C.S. Lui | 3 | 3680 | 279.85 |