A High-Performance Invertible Sketch for Network-Wide Superspreader Detection
IEEE/ACM Transactions on Networking · 2023-04 · 31 (2) · 724-737
DOI: 10.1109/tnet.2022.3198738 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE/ACM Transactions on Networking, 2023-04. Verfasst von Lu Tang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 23-mal zitiert (Crossref) und nennt 64 Literaturangaben. Gefördert von: Key-Area Research and Development Program of Guangdong Province, Joint Funds of the National Natural Science Foundation of China, National Natural Science Foundation of China.
Abstract (Originalsprache)
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 SpreadSketch, an invertible sketch data structure for network-wide superspreader detection with the theoretical guarantees on memory space, performance, and accuracy. SpreadSketch tracks candidate superspreaders and embeds estimated fan-outs in binary hash strings inside small and static memory space, such that multiple SpreadSketch 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 SpreadSketch in terms of space and time complexities as well as error bounds. We further extend SpreadSketch 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 SpreadSketch while maintaining the accuracy guarantees. Trace-driven evaluation shows that SpreadSketch 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 SpreadSketch in P4 and show its feasible deployment in commodity hardware switches.
Förderung
- Key-Area Research and Development Program of Guangdong Province
- Joint Funds of the National Natural Science Foundation of China
- National Natural Science Foundation of China
- Fundamental Research Funds for the Central Universities
- Natural Science Foundation of Fujian Province of China
- Research Grants Council of Hong Kong
Zitieren
APA
Tang, L., Xiao, Y., Huang, Q., & Lee, P. P. C. (2023). A High-Performance Invertible Sketch for Network-Wide Superspreader Detection. IEEE/ACM Transactions on Networking, 31(2), 724-737. https://doi.org/10.1109/tnet.2022.3198738
Vancouver
Tang L, Xiao Y, Huang Q, Lee PPC. A High-Performance Invertible Sketch for Network-Wide Superspreader Detection. IEEE/ACM Transactions on Networking. 2023;31(2):724-737. doi:10.1109/tnet.2022.3198738
BibTeX
@article{Tang2023,
author = {Tang, Lu and Xiao, Yao and Huang, Qun and Lee, Patrick P. C.},
title = {A High-Performance Invertible Sketch for Network-Wide Superspreader Detection},
journal = {IEEE/ACM Transactions on Networking},
year = {2023},
volume = {31},
number = {2},
pages = {724--737},
doi = {10.1109/tnet.2022.3198738}
}
EUVIMED