A practical and robust inter-domain marking scheme for IP traceback

Zhiqiang Gao, Nirwan AnsariComputer Networks 2007 · DOI

TL;DR

This paper introduces ASEM, a novel IP traceback scheme that significantly improves upon existing Probabilistic Packet Marking (PPM) methods. ASEM reduces the computational burden on victims, enhances robustness against spoofed markings, and effectively handles large-scale Distributed Denial of Service (DDoS) attacks by leveraging Autonomous System (AS) level marking and BGP routing information.

What Problem Does This Paper Address?

The internet's increasing reliance on online services makes it vulnerable to Denial of Service (DoS) and Distributed Denial of Service (DDoS) attacks, which can cripple critical infrastructure and services. IP traceback is a crucial defense mechanism, aiming to identify the sources of these attacks. However, existing IP traceback methods, particularly Probabilistic Packet Marking (PPM), suffer from several significant drawbacks:

  • Heavy Computational Load: Victims face overwhelming computational overhead to reconstruct attack paths, especially during large-scale DDoS attacks involving thousands of sources.
  • High False Positives: The limited marking bits and reconstruction algorithms lead to a high rate of incorrect path identifications.
  • Spoofed Marking: Attackers can inject false marking information, either directly or by compromising routers, to mislead traceback efforts.
  • Subverted Routers: Malfunctioning or compromised routers can also introduce incorrect marking information.
  • Unawareness of Path Length: Routers lack knowledge of the total path length, preventing them from using optimal marking probabilities.
  • Ineffectiveness Against Large-Scale DDoS: PPM struggles to handle the complexity and scale of modern DDoS attacks.

These limitations hinder effective and timely identification of attack origins, making it difficult to mitigate ongoing attacks and prevent future ones.

Methods

ASEM (AS-based Edge Marking) is proposed as a practical and robust solution. It builds upon the core idea of probabilistic marking but introduces several key innovations:

  • AS-Level Marking: Instead of hop-by-hop marking, ASEM marks packets at the Autonomous System (AS) level. Only ingress edge routers of each AS are responsible for marking and verification.
  • AS_PATH Marking: The marking information includes the AS path (a sequence of AS numbers) rather than individual router IP addresses. This significantly shortens the "path length" for traceback purposes.
  • "No Re-marking" Policy: Once a packet is marked by an AS, subsequent routers within that AS or downstream ASs are prohibited from re-marking it. This simplifies the marking process and prevents overwriting.
  • Optimal Marking Probability: ASEM derives and utilizes an optimal marking probability based on the AS path length, which is readily available through BGP routing information.
  • Linkage Information (HASHIP): A 12-bit HASHIP field is introduced, storing a hash of the first router's IP address. This acts as a linkage identifier, allowing the victim to efficiently group packets from the same source within an AS, crucial for large-scale DDoS attacks.
  • Marking Verification: Downstream marking routers can verify the correctness of markings from upstream neighbors by comparing the received AS_PATH with their own BGP routing information. This helps detect and discard spoofed markings from subverted routers.
  • Reduced Marking Bits: ASEM uses fewer bits for marking compared to PPM, simplifying reconstruction and reducing overhead.

Datasets

The paper evaluates its performance using two datasets:

  • Skitter project of CAIDA: A well-known source of Internet topology and measurement data.
  • Internet Mapping data from Lumeta: Another dataset providing insights into Internet structure.

The authors averaged data from these sources and selected paths with lengths between 6 and 30 hops (corresponding to AS path lengths of 2-10) for their analysis, totaling 9804 paths.

Key Insights and Ideas

  • AS-level granularity is sufficient and beneficial: Moving from hop-by-hop to AS-level marking significantly simplifies traceback and reduces computational load without sacrificing essential information.
  • BGP's ASPATH is a powerful tool for traceback: The AS path information, readily available through BGP, provides a more stable and shorter representation of network paths, making traceback more efficient.
  • "No re-marking" is a simple yet effective policy: This policy, combined with AS-level marking, prevents the complex overwriting issues seen in PPM and simplifies path reconstruction.
  • Linkage information (HASHIP) is critical for DDoS: For large-scale attacks, distinguishing between multiple sources within the same AS is vital. HASHIP provides this capability, enabling more precise traceback.
  • Verification at the edge is feasible and effective: By leveraging BGP information, ingress edge routers can actively verify markings, mitigating the impact of subverted routers.

Key Results

ASEM demonstrates significant improvements over PPM:

  • Reduced Computational Burden: ASEM reduces the number of marked packets required for path reconstruction by as much as 90.67% on average.
  • Suppressed False Positives: The use of AS-level marking, fewer marking bits, and linkage information drastically reduces false positives.
  • Enhanced Robustness: ASEM effectively handles spoofed markings from attackers and phony markings from subverted routers.
  • Effectiveness Against Large-Scale DDoS: The HASHIP field and AS-level granularity make ASEM well-suited for tackling complex, multi-source DDoS attacks.
  • Partial Deployment Viability: The power-law nature of the Internet suggests that ASEM can be effective even with partial deployment.

Limitations and Future Work

  • Assumption of AS Path Stability: The scheme assumes that AS paths are relatively stable. While generally true, significant routing changes could impact accuracy.
  • Ingress Edge Router Memory: ASEM requires ingress edge routers to store BGP routing tables, which is a minor memory overhead.
  • Attacker Knowledge: The scheme assumes attackers might know the traceback scheme, but it is designed to be robust against such knowledge.
  • Adjacent Compromised Routers: The current design assumes compromised routers are not adjacent. Handling adjacent compromised routers might require further enhancements.

The authors suggest that the power-law nature of the Internet facilitates effective partial deployment of ASEM, implying that future work could explore the dynamics and benefits of such deployments. The paper also implicitly suggests that further research into optimizing the HASHIP function and its interaction with AS_PATH could yield even greater benefits.

Summary updated

BibTeX
@article{gao2007practical,
  author = {Zhiqiang Gao and Nirwan Ansari},
  title = {{A practical and robust inter-domain marking scheme for IP traceback}},
  journal = {Computer Networks},
  year = {2007},
  doi = {10.1016/j.comnet.2006.06.003},
}
Figure