Counting distinct elements over sliding windows

Eran Assaf, Ran Ben-Basat, Gil Einziger, Roy Friedman, Yaron Kassner

Abstract

In Distributed Denial of Service (DDoS) attacks, an attacker tries to disable a service with a flood of seemingly legitimate requests from multiple devices; this is usually accompanied by a sharp spike in the number of distinct IP addresses / flows accessing the system in a short time frame. Hence, the number of distinct elements over sliding windows is a fundamental signal in DDoS identification. Additionally, assessing whether a specific flow has recently accessed the system, known as the Set Membership problem, can help us identify the attacking parties. Here, we show how to extend the functionality of a state of the art algorithm for set membership over a W elements sliding window. We now also support estimation of the distinct flow count, using as little as log2 (W) additional bits.
BibTeX
@inproceedings{assaf2017counting,
  author = {Eran Assaf and Ran Ben-Basat and Gil Einziger and Roy Friedman and Yaron Kassner},
  title = {{Counting distinct elements over sliding windows}},
  booktitle = {SYSTOR},
  year = {2017},
  doi = {10.1145/3078468.3078491},
}

Loading related content...

Figure