Identifying Hierarchical Super Spreaders in a Data Stream by Hot-Separated and Mergeable Sketch

摘要

Traditionally, network devices detect DDoS attacks and network scans in real time by estimating the cardinality (or spread) of each destination or source IP from high-speed packet streams using per-flow cardinality estimators. However, modern attacks, such as carpet-bombing DDoS, distribute traffic across multiple IPs within a subnet, evading detection by reducing perIP spread. To address this challenge, we consider a new problem: identifying hierarchical super spreaders (HSSs) by estimating the spread of hierarchical flows in real time. Existing solutions either lack support for two-dimensional (2D) hierarchies or suffer from suboptimal accuracy. In this paper, we propose H-MOPS, a new sketch that accurately detects both one-dimensional (1D) and 2D HSSs. H-MOPS organizes hierarchical flows into a grid structure based on IP mask lengths, deploying a MOPS sketch at each node to estimate per-flow spread. MOPS improves accuracy by maintaining a prefilter to separate top-k super spreaders and supports mergeability across distributed sketches. To compute the conditional spread of a hierarchical flow, H-MOPS addresses the duplicated-counting problem by merging the virtual estimators of all its descendant HSSs and subtracting the merged result from its own spread. Experiments on CAIDA traces demonstrate that MOPS achieves lower estimation error and higher detection accuracy than existing methods, and that H-MOPS significantly outperforms prior approaches in both 1D and 2D HSS detection.