Counting distinct elements over sliding windows
Lists
Only you see this
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...