Mitigating DNS random subdomain DDoS attacks by distinct heavy Hitters sketches

Yehuda Afek, Anat Bremler-Barr, Edith Cohen, Michal Sagam, Shir Landau Feibish
HotWeb ,
Conferences & Workshops
DDoS attack, DNS security, Traffic Measurement


Random Subdomain DDoS attacks on the Domain Name System (DNS) infrastructure are becoming a popular vector in recent attacks (e.g., recent Mirai attack on Dyn). In these attacks, many queries are sent for a single or a few victim domains, yet they include highly varying non-existent subdomains generated randomly.
Motivated by these attacks we designed and implemented novel and efficient algorithms for distinct heavy hitters (dHH). A (classic) heavy hitter (HH) in a stream of elements is a key (e.g., the domain of a query) which appears in many elements (e.g., requests).
When stream elements consist of <key, subkey> pairs, (<domain, subdomain>) a distinct heavy hitter (dhh) is a key that is paired with a large number of different subkeys. Our algorithms dominate previous designs in both the asymptotic (theoretical) sense and practicality. Specifically, the new fixed-size algorithms are simple to code and with asymptotically optimal space accuracy tradeoffs.
Based on these algorithms, we build and implement a system for the detection and mitigation of Random Subdomain DDoS attacks. We perform experimental evaluation, demonstrating the effectiveness of our algorithms.

  title={Mitigating DNS random subdomain DDoS attacks by distinct heavy hitters sketches},
  author={Feibish, Shir Landau and Afek, Yehuda and Bremler-Barr, Anat and Cohen, Edith and Shagam, Michal},
  booktitle={Proceedings of the fifth ACM/IEEE Workshop on Hot Topics in Web Systems and Technologies},