On deterministic packet marking

Andrey Belenky, Nirwan AnsariComputer Networks 2007 · DOI

TL;DR

This paper introduces Deterministic Packet Marking (DPM), a novel IP traceback method designed to identify the sources of DDoS attacks. DPM marks packets at ingress routers, allowing victims to reconstruct the attacker's path with minimal impact on network infrastructure and performance, even for fragmented traffic and multiple simultaneous attackers.

What Problem Does This Paper Address?

The internet is increasingly vulnerable to Distributed Denial of Service (DDoS) attacks, which aim to overwhelm a victim's resources and make services unavailable. A significant challenge in combating these attacks is their anonymity, often achieved by spoofing source IP addresses. This makes it difficult for victims to identify the true origin of the attack traffic. Existing traceback methods have limitations, including high overhead, significant ISP involvement, lack of post-mortem analysis capabilities, and ineffectiveness against certain attack types or fragmented traffic. This paper addresses the need for a scalable, efficient, and robust IP traceback mechanism that can handle sophisticated DDoS attacks, including those involving multiple attackers and fragmented packets.

Methods

The core of the proposed solution is Deterministic Packet Marking (DPM). DPM operates by marking incoming packets at the edge ingress routers of a network. This marking is done using a portion of the IP header (specifically, the 16-bit Identification (ID) field and the 1-bit Reserved Flag (RF)). The mark contains partial address information of the ingress interface.

Key aspects of the DPM approach include:

  • Ingress Marking: Packets are marked only when they enter the network, and this mark is not altered as the packet traverses the network. This prevents mark spoofing by intermediate routers.
  • Victim-Side Reconstruction: The bulk of the processing for traceback is performed by the victim. The victim collects marked packets and uses the embedded information to reconstruct the ingress IP address of the attacker.
  • Scalability and Efficiency: DPM introduces minimal bandwidth and processing overhead on network equipment. It is designed to be scalable to handle thousands of simultaneous attackers.
  • Handling Multiple Attackers: Modifications to the basic DPM are introduced to handle multiple simultaneous attackers. This involves using multiple hash functions to generate digests of the ingress address, allowing for better differentiation between attackers.
  • Fragment-Persistent DPM: A significant contribution is the adaptation of DPM to handle IP fragmentation. This involves a mechanism to ensure that fragments of the same original datagram receive consistent marks, preventing reassembly failures and enabling traceback even with fragmented traffic. This is achieved by suspending random marking for a short series of fragments from the same datagram.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic design and theoretical analysis of the DPM method.

Key Insights and Ideas

  • Shifting Traceback Burden: The most significant insight is shifting the heavy lifting of traceback from network routers to the victim. This drastically reduces the operational burden on ISPs and network infrastructure.
  • Deterministic Marking for Robustness: By making the marking deterministic at the ingress point, DPM inherently prevents mark spoofing by intermediate nodes, a common vulnerability in other marking schemes.
  • Post-Mortem Traceback: The design allows for traceback even after an attack has concluded, which is crucial for analyzing attacks that might have been too fast or disruptive to trace in real-time.
  • Fragmentation as a Feature, Not a Bug: DPM's ability to accommodate IP fragmentation is a key differentiator. Instead of being a hindrance, the method is adapted to work with fragmentation, making it more resilient to sophisticated attack techniques.
  • ISP Collaboration Minimal: The proposed DPM deployment strategy requires limited ISP involvement, primarily to disable DPM on upstream interfaces when a downstream ISP enables it, facilitating a more practical deployment.

Key Results

The paper presents theoretical analysis and pseudocode for the DPM algorithm and its variants. While specific quantitative results from real-world deployments are not provided, the analysis demonstrates:

  • Scalability: The DPM approach is designed to handle a large number of simultaneous attackers (NMAX values are presented in tables for different configurations).
  • Efficiency: Minimal per-packet overhead is achieved, with processing limited to generating a small random number and overwriting header bits.
  • Traceback Capability: The method is shown to be capable of reconstructing ingress addresses for various attack scenarios, including multiple attackers and fragmented traffic.
  • False Positive Rate: The analysis aims to keep the false positive rate below 1%, a standard metric for traceback algorithms.

Limitations and Future Work

  • Deployment Dependency: The effectiveness of DPM relies on its widespread deployment across the Internet, particularly by major ISPs. Incomplete deployment can undermine its traceback capabilities.
  • Router Subversion: DPM is sensitive to router subversion, where routers might overwrite the placed marks. The authors plan to investigate the effects of such subversion.
  • Lossy Conditions: The paper acknowledges that DDoS attacks often involve significant packet loss, which can skew the distribution of received marks and affect traceback accuracy. The impact of lossy conditions on DPM's effectiveness is a planned area of future work.
  • Integration with IDS: The authors suggest integrating DPM with Intrusion Detection Systems (IDS) as a future research direction.
  • Practical Deployment Challenges: While the paper outlines deployment guidelines, the practicalities of inter-ISP collaboration and managing storage for traceback data (especially with millions of reflectors and slaves) are noted as considerations.

Summary updated

BibTeX
@article{belenky2007deterministic,
  author = {Andrey Belenky and Nirwan Ansari},
  title = {{On deterministic packet marking}},
  journal = {Computer Networks},
  year = {2007},
  doi = {10.1016/j.comnet.2006.11.020},
}
Figure