Online Detection of 1D and 2D Hierarchical Super-Spreaders in High-Speed Networks
Authors: 
Hao Su, Qingjun XiaoAuthors Info & Claims
Pages 109 - 115
Abstract
Traditionally, a firewall tracks the per-flow spread of each source and destination IP address to detect network scans and DDoS attacks. It is not designed with hierarchical IP addresses in mind. However, cyberattacks nowadays become more stealthy. To evade the detection, they treat a network subnet instead of a single IP as the victim of an attacking campaign. Therefore, we focus on a new problem: online estimation of each hierarchical flow’s cardinality (or spread), in order to detect the hierarchical super-spreaders (HSSs), which correspond to the IP subnet receiving numerous network connections from an extraordinarily large number of source IPs. For detecting such one-dimensional HSSs, the recent work Hierarchical virtual bitmap estimator (HVE) has been proposed. But it fails to handle the two-dimensional HSSs, and it can not be queried online due to its very high query overhead. In this paper, we propose the Hon-vHLL sketch to address these limitations. It is an innovative hierarchical extension of On-vHLL to support the estimation of conditional spreads for either 1D or 2D hierarchical flows. Hon-vHLL allocates an On-vHLL sketch for each hierarchical level bucket and query conditional spread by merging the virtual estimators of hierarchical flows. We evaluate its performance based on CAIDA network traces. The results show that our Hon-vHLL can improve the query throughput by 578 times than HVE, and also achieve 11% higher HSS detection accuracy.
References
[1]
2017. CAIDA UCSD anonymized 2017 internet traces on Jan. 17. http://www.caida.org/data/passive/passive_2017_dataset.xml. (2017).
[2]
Georgi A Ajaeiya, Nareg Adalian, Imad H Elhajj, Ayman Kayssi, and Ali Chehab. 2017. Flow-based intrusion detection system for SDN. In Proc. of IEEE ISCC. IEEE, 787–793.
[3]
Roberto Baldoni, Giuseppe Antonio Di Luna, and Leonardo Querzoni. 2013. Collaborative detection of coordinated port scans. In Proc. of ICDCN. Springer, 102–117.
[4]
Ran Ben Basat, Gil Einziger, Roy Friedman, Marcelo C Luizelli, and Erez Waisbard. 2017. Constant time updates in hierarchical heavy hitters. In Proc. of ACM SIGCOMM. 127–140.
[5]
Theophilus Benson, Ashok Anand, Aditya Akella, and Ming Zhang. 2011. MicroTE: Fine grained traffic engineering for data centers. In Proc. of ACM CoNEXT. 1–12.
[6]
Chee-Yong Chan and Yannis E Ioannidis. 1998. Bitmap index design and evaluation. In Proc. of ACM SIGMOD. 355–366.
[7]
Kenjiro Cho. 2017. Recursive lattice search: Hierarchical heavy hitters revisited. In Proc. of ACM IMC. 283–289.
[8]
Graham Cormode, Flip Korn, Shanmugavelayutham Muthukrishnan, and Divesh Srivastava. 2003. Finding hierarchical heavy hitters in data streams. In Proc. of VLDB. Elsevier, 464–475.
[9]
Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. 2008. Finding Hierarchical Heavy Hitters in Streaming Data. ACM Trans. Knowl. Discov. Data 1, 4, Article 2 (feb 2008), 48 pages. https://doi.org/10.1145/1324172.1324174
[10]
Seyed K Fayaz, Yoshiaki Tobioka, Vyas Sekar, and Michael Bailey. 2015. Bohatei: Flexible and elastic ddos defense. In Proc. of USENIX. 817–832.
[11]
Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In DMTCS. Discrete Mathematics and Theoretical Computer Science, 137–156.
[12]
Weijiang Liu, Wenyu Qu, Jian Gong, and Keqiu Li. 2015. Detection of superpoints using a vector bloom filter. IEEE TITF 11, 3 (2015), 514–527.
[13]
Yang Liu, Wenji Chen, and Yong Guan. 2015. Identifying high-cardinality hosts from network-wide traffic measurements. IEEE TDSC 13, 5 (2015), 547–558.
[14]
Chaoyi Ma, Shigang Chen, Youlin Zhang, Qingjun Xiao, and Olufemi O Odegbile. 2021. Super spreader identification using geometric-min filter. IEEE/ACM TON 30, 1 (2021), 299–312.
[15]
Michael Mitzenmacher, Thomas Steinke, and Justin Thaler. 2012. Hierarchical heavy hitters with the space saving algorithm. In Proc. of ALENEX. SIAM, 160–174.
[16]
Olufemi Odegbile, Chaoyi Ma, Shigang Chen, Dimitrios Melissourgos, and Haibo Wang. 2021. Hierarchical Virtual Bitmaps for Spread Estimation in Traffic Measurement. In Proc. of NCWMC.
[17]
Zubair Shah, Abdun Naser Mahmood, Michael Barlow, Zahir Tari, Xun Yi, and Albert Y Zomaya. 2017. Computing hierarchical summary from two-dimensional big data streams. IEEE TPDS 29, 4 (2017), 803–818.
[18]
Ahren Studer and Adrian Perrig. 2009. The coremelt attack. In Proc. of ESORICS. Springer, 37–52.
[19]
Lu Tang, Qun Huang, and Patrick PC Lee. 2020. SpreadSketch: Toward invertible and network-wide detection of superspreaders. In Proc. of IEEE INFOCOM. IEEE, 1608–1617.
[20]
Lu Tang, Qun Huang, and Patrick PC Lee. 2021. MVPipe: Enabling Lightweight Updates and Fast Convergence in Hierarchical Heavy Hitter Detection. arXiv preprint arXiv:2107.05954 (2021).
[21]
Da Tong and Viktor Prasanna. 2015. High throughput hierarchical heavy hitter detection in data streams. In Proc. of IEEE HiPC. IEEE, 224–233.
[22]
Pinghui Wang, Xiaohong Guan, Tao Qin, and Qiuzhen Huang. 2011. A data streaming method for monitoring host connection degrees of high-speed links. IEEE TITF 6, 3 (2011), 1086–1098.
[23]
Martin Wischenbart, Stefan Mitsch, Elisabeth Kapsammer, Angelika Kusel, Birgit Pröll, Werner Retschitzegger, Wieland Schwinger, Johannes Schönböck, Manuel Wimmer, and Stephan Lechner. 2012. User profile integration made easy: model-driven extraction and transformation of social network schemas. In Proc. of ACM WWW. 939–948.
[24]
Qingjun Xiao, Shigang Chen, You Zhou, Min Chen, Junzhou Luo, Tengli Li, and Yibei Ling. 2017. Cardinality estimation for elephant flows: A compact solution based on virtual register sharing. IEEE/ACM TON 25, 6 (2017), 3738–3752.
[25]
Qingjun Xiao, Xiongqin Hu, and Shigang Chen. 2021. Supporting Flow-Cardinality Queries with O (1) Time Complexity in High-speed Networks. In Proc.of IEEE/ACM IWQOS. IEEE, 1–10.
[26]
MyungKeun Yoon, Tao Li, Shigang Chen, and Jih-Kwon Peir. 2010. Fit a compact spread estimator in small high-speed memory. IEEE/ACM TON 19, 5 (2010), 1253–1264.
Index Terms
- Online Detection of 1D and 2D Hierarchical Super-Spreaders in High-Speed Networks
Recommendations
Unreliable transport protocol using congestion control for high-speed networks
Currently there is no control for the real-time traffic of multimedia applications using UDP (User Datagram Protocol) in high-speed networks. Therefore, although a number of high-speed TCP (Transmission Control Protocol) protocols have been developed ...
Can high-speed networks survive with DropTail queues management?
It has been observed that TCP connections that go through multiple congested links (MCL) have a smaller transmission rate than the other connections. Such TCP behavior is a result of two components (i) the cumulative packet losses that a flow ...
Performance evaluation of TCP-BIAD in high-speed, long-distance networks
In this paper, the performance of Binary Increase Adaptive Decrease (TCP-BIAD) congestion control algorithm in high-speed long-distance networks is evaluated. As its name implies, this TCP variant is a combination of an enhanced binary increase ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2023
229 pages
ISBN:9798400707827
DOI:10.1145/3600061
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 September 2023
Check for updates
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- National Key Research and Development Plan of China
- Science Foundation of Jiangsu Province of China
Conference
APNET 2023
Acceptance Rates
Overall Acceptance Rate 50 of 118 submissions, 42%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 63Total Downloads
- Downloads (Last 12 months)52
- Downloads (Last 6 weeks)4
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format