A High-Performance Invertible Sketch for Network-Wide Superspreader Detection

Authors:
Publisher website
Google Scholar
Abstract
Superspreaders (i.e., hosts with numerous distinct connections) remain severe threats to production networks. How to accurately detect superspreaders in real-time at scale remains a non-trivial yet challenging issue. We present, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. tracks candidate superspreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple instances can be readily merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs. We present formal theoretical analysis on in terms of space and time complexities as well as error bounds. We further extend with a fast and small data structure that filters out the packets of high-frequency connections from sketch processing, so as to improve the update performance of while maintaining the accuracy guarantees. Trace-driven evaluation shows that achieves higher accuracy and performance over state-of-the-art sketches and remains accurate in detecting real-world worms and DDoS attacks. Furthermore, we prototype in P4 and show its feasible deployment in commodity hardware switches.
Funding Information
  • Key-Area Research and Development Program of Guangdong Province (2020B0101390001)
  • Joint Funds of the National Natural Science Foundation of China (U20A20179)
  • National Natural Science Foundation of China (62172007)
  • Fundamental Research Funds for the Central Universities (20720210072)
  • Natural Science Foundation of Fujian Province of China (2021J05002)
  • Research Grants Council of Hong Kong (GRF 14204017)

This publication has 46 references indexed in Scilit: