2016/12/08 by Yehuda Afek, Anat Bremler-Barr, Afek, Yehuda +7
Computer Science · #Advanced Malware Detection Techniques #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Network Security and Intrusion Detection #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.1612.02636
openalex publication_date 2016/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 pairs, () 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.