  Motivated by a recent new type of randomized Distributed Denial of Service
(DDoS) attacks on the Domain Name Service (DNS), we develop novel and efficient
distinct heavy hitters algorithms and build an attack identification system
that uses our algorithms. Heavy hitter detection in streams is a fundamental
problem with many applications, including detecting certain DDoS attacks and
anomalies. 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 a <key; subkey> pairs, (<domain; subdomain>) a
distinct heavy hitter (dhh) is a key that is paired with a large number of
different subkeys. Our dHH algorithms are considerably more practical than
previous algorithms. Specifically the new fixed-size algorithms are simple to
code and with asymptotically optimal space accuracy tradeoffs. In addition we
introduce a new measure, a combined heavy hitter (cHH), which is a key with a
large combination of distinct and classic weights. Efficient algorithms are
also presented for cHH detection. Finally, we perform extensive experimental
evaluation on real DNS attack traces, demonstrating the effectiveness of both
our algorithms and our DNS malicious queries identification system.
