Traceback

IP Traceback

• Basic Idea
  • 方法：修改路由器 Router，在 packet 中记录数据
  • 限制：需要在 packet 中挪出足够空间记录路径
• Edge Sampling
  • 使用 (s|e|d) 记录路线中的起点、终点以及从记录开始到终点的条数
  • 方法：修改路由器 Router，在 packet 中记录 (s|e|d)
  • 为了构建发送路径，还需要知道总的跳数。可以通过数据报的 TTL 获得

ICMP Traceback

• 核心算法
  • Each router samples one of packets it is forwarding and copies the contents and adjacent routers' info into an ICMP traceback message
  • Router uses HMAC and X.509 digital certificate for authenticaing traceback messages
  • Router sends ICMP traceback messages to the destination
• 算法缺陷
  • Require all the routers transmitting attack traffic be enabled with iTrace to construct an entire attack path
  • yet ICMP packets are usually filtered because of ICMP Ping Flood Attack

Link Testing

• 核心算法
  • 追踪离受害者最近的路由器
  • 确定发起攻击流量的上行链路
  • 递归地应用前面的技术，直到达到攻击源
• Link Testing 基于的假设
  • 攻击会持续进行
• Link Testing 的具体实现方式
  • Traceback#Input Debugging
  • Traceback#Controlled Flooding

Input Debugging

• 原理
  • 计算所有攻击报文所包含的共同特征，获取「攻击签名」
  • 将「攻击签名」发送给上游路由器，由上游路由器对攻击包进行过滤，并确定进入端口
  • 在上游路由器上递归地应用上述技术，直到到达攻击源
• 缺点
  • 在 ISP 级别上进行通信和协调追溯需要相当大的管理开销

Controlled Flooding

• 原理
  • 需要协作的主机
  • 强制主机将 Link 泛洪到上游路由器，因为受害链路的缓冲区被所有入站链路共享，攻击链路泛洪时，攻击报文会被丢弃
  • 在上游路由器递归使用上述技术，直到达到攻击源
• 缺点
  • 需要一张精确的拓扑图
  • 如果有多个攻击源，如 DDoS，会产生高开销

Logging-Based Traceback

• 核心算法
  • 假设路由器存储「包日志」
  • 受害者会向最近的路由器查询攻击报文的报文外观
  • 含有攻击报文的路由器会递归地查询上游路由器，直至到达攻击源
• 缺点
  • 如果完整记录包的内容，会产生极大的存储开销；即便是使用哈希，也需要很大的存储开销 → 解决方案 Traceback#Bloom Filter

Bloom Filter

• 核心算法
  • 每个采样包使用多个哈希值，对采样包中的不变内容进行多次哈希，使用一个 bitmap 保存哈希结果
  • 需要检验时，检查是否采样包的所有哈希值都在 bitmap 里
• 缺点
  • 有概率发生「false positive」，即错误认为某采样包是由某路由器发来的
  • 如果 bitmap 的大小是 $m$，对 $n$ 个成员使用 $k$ 个哈希函数，则发生「false positive」的概率是 $(1-(1-1/m{)}^{kn}{)}^k\approx (1-e^{kn/m}{)}^k$