research-article
Authors: Arish Sateesan, Jo Vliegen, Joan Daemen, Nele Mentens
Volume 93, Issue C
Published: 01 September 2022 Publication History
Metrics
Total Citations4Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
Abstract
This paper optimizes Bloom filter algorithms and hardware architectures for high-speed implementation on FPGAs. A Bloom filter is a data structure that is used to check whether input search data are present in a table of stored data. Bloom filters are extensively used for monitoring network traffic. Improving the speed of Bloom filters can therefore have a significant impact on the speed of many network applications. The most important components determining the speed of Bloom filters are hash functions. While hash functions in Bloom filters do not require strong cryptographic properties, they do need a minimized computational delay. In this work, we evaluate and compare the performance and resource utilization of different Bloom filter algorithms and architectures as well as non-cryptographic hash functions on an FPGA. We also propose a new non-cryptographic hash function, called Xoodoo-NC, derived from the cryptographic permutation Xoodoo. Xoodoo-NC is a reduced-round, reduced-state version of Xoodoo, inheriting Xoodoo’s desired avalanche properties and low logical depth, resulting in an ultra-low-latency non-cryptographic hash function. We evaluate the performance of Bloom filter architectures based on Xoodoo-NC on a Xilinx UltraScale+ FPGA and we compare the performance and resource occupation to existing Bloom filter implementations. We additionally compare our results to memories that use the built-in CAM cores in Xilinx UltraScale+ FPGAs. Our proposed algorithmic and architectural advances lead to Bloom filters that, to the best of our knowledge, outperform all other FPGA-based solutions.
References
[1]
Varghese G., Network algorithmics: An interdisciplinary approach to designing fast networked devices, 2004.
[2]
Bloom B.H., Space/time trade-offs in hash coding with allowable errors, Commun. ACM 13 (7) (1970) 422–426.
Digital Library
[3]
Dharmapurikar S., Krishnamurthy P., Sproull T.S., Lockwood J.W., Deep packet inspection using parallel bloom filters, IEEE Micro 24 (1) (2004) 52–61.
Digital Library
[4]
S. Dharmapurikar, M. Attig, J. Lockwood, Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters, in: 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM ’04, 2004.
[5]
Broder A.Z., Mitzenmacher M., Network applications of bloom filters: A survey, Internet Math. (2004).
[6]
Luo L., Guo D., Ma RichardT.B., Rottenstreich O., Luo X., Optimizing bloom filter: Challenges, solutions, and comparisons, 2018, arXiv:1804.04777.
[7]
Estan C., Varghese G., New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Trans. Comput. Syst. (2003).
[8]
A. Kumar, J. Xu, J. Wang, O. Spatschek, L. Li, Space-code Bloom filter for efficient per-flow traffic measurement, in: Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement, 2003, pp. 167–172.
[9]
H. Wu, H.C. Hsiao, Y.C. Hu, Efficient large flow detection over arbitrary windows: An algorithm exact outside an ambiguity region, in: Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC, 2014, pp. 209–222.
[10]
Stanley Simon, FPGAS & ASICs for telecom, 2015, Heavy Reading, http://www.heavyreading.com/details.asp?sku_id=3418&skuitem_itemid=1657.
[11]
Menezes A.J., van Oorschot P.C., Vanstone S.A., Handbook of Applied Cryptography, CRC Press, 2001.
[12]
Daemen J., Hoffert S., Assche G.Van, Keer R.Van, The design of xoodoo and xoofff, IACR Trans. Symmetric Cryptol. (2018) 1–38.
[13]
Qiao Y., Li T., Chen S., Fast bloom filters and their generalization, IEEE TPDS 25 (1) (2014) 93–103.
[14]
Fowler G., Noll L.C., Vo K.-P., The FNV non-cryptographic hash algorithm, 2012, https://tools.ietf.org/html/draft-eastlake-fnv-03.
[15]
A. Sateesan, J. Vliegen, J. Daemen, N. Mentens, Novel Bloom filter algorithms and architectures for ultra-high-speed network security applications, in: 2020 23rd Euromicro Conference on Digital System Design, DSD, 2020, pp. 262–269.
[16]
K. Locke, Parameterizable Content-Addressable Memory, https://www.xilinx.com/support/documentation/application_notes/xapp1151_Param_CAM.pdf.
[17]
Reviriego P., Christensen K., Maestro J.A., A comment on fast bloom filters and their generalization, IEEE Trans. Parallel Distrib. Syst. 27 (1) (2016) 303–304.
[18]
Estébanez C., Sáez Y., Recio G., Isasi P., Performance of the most common non-cryptographic hash functions, Softw. - Pract. Exp. 44 (2014).
[19]
J. Lu, T. Yang, Y. Wang, H. Dai, L. Jin, H. Song, B. Liu, One-hashing Bloom filter, in: Proc. IEEE/ACM IWQoS, 2015.
[20]
Kirsch A., Mitzenmacher M., Less hashing, same performance: Building a better bloom filter, Random Struct. Algorithms 33 (2) (2006) 187–218.
[21]
J. Lu, Y. Wan, Y. Li, C. Zhang, H. Dai, Y. Wang, G. Zhang, B. Liu, Ultra-fast Bloom filters using SIMD techniques, in: Proc. IEEE/ACM IWQoS, 2017.
[22]
K. Huang, et al., A Multi-partitioning Approach to Building Fast and Accurate Counting Bloom Filters, in: IEEE 27th International Symposium on Parallel and Distributed Processing, 2013, pp. 1159–1170.
[23]
Mitzenmacher M., Reviriego P., Pontarelli S., OMASS: One memory access set separation, IEEE Trans. Knowl. Data Eng. 28 (7) (2016) 1940–1943.
[24]
T. Wada, N. Matsumura, K. Nakano, Y. Ito, Efficient Byte Stream Pattern Test using Bloom Filter with Rolling Hash Functions on the FPGA, in: 2018 Sixth International Symposium on Computing and Networking, 2018, pp. 66–75.
[25]
I. Kaya, T. Kocak, A low power lookup technique for multi-hashing network applications, in: IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures, 2006.
[26]
M.J. Lyons, D. Brooks, The design of a Bloom filter hardware accelerator for ultra low power systems, in: Proceedings of the 2009 ACM/IEEE International Symposium on Low Power Electronics and Design, 2009, pp. 371–376.
[27]
J. Harwayne-Gidansky, D. Stefan, I. Dalal, FPGA-based SoC for real-time network intrusion detection using counting Bloom filters, in: IEEE Southeastcon 2009, Atlanta, GA, 2009, pp. 452–458.
[28]
[29]
Z. Martinasek, J. Hajny, D. Smekal, L. Malina, D. Matousek, M. Kekely, N. Mentens, 200 Gbps Hardware Accelerated Encryption System for FPGA Network Cards, in: Proceedings of the 2018 Workshop on Attacks and Solutions in Hardware Security, 2018, pp. 11–17.
[30]
Arish Sateesan, Jo Vliegen, Simon Scherrer, Hsu-Chun Hsiao, Adrian Perrig, Nele Mentens, Speed records in network flow measurement on FPGA, in: 2021 31st International Conference on Field-Programmable Logic and Applications, FPL, IEEE, pp. 219–224.
[31]
Claesen Thomas, Sateesan Arish, Vliegen Jo, Mentens Nele, Novel non-cryptographic hash functions for networking and security applications on FPGA, in: 2021 24th Euromicro Conference on Digital System Design, DSD, IEEE, 2021, pp. 347–354.
[32]
Xilinx User Guide, Ternary content addressable memory (TCAM) search IP for SDNet, https://www.xilinx.com/support/documentation/ip_documentation/tcam/pg190-tcam.pdf.
Cited By
View all
- Hassan MVliegen JPicek SMentens NLi XHandl J(2024)A Systematic Exploration of Evolutionary Computation for the Design of Hardware-oriented Non-cryptographic Hash FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654009(1255-1263)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654009
- Zeng ZXiao RLin XLuo TLin J(2023)Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detectionInformation Processing and Management: an International Journal10.1016/j.ipm.2023.10330660:3Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.ipm.2023.103306
- Hassan MSateesan AVliegen JPicek SMentens N(2023)Evolving Non-cryptographic Hash Functions Using Genetic Programming forHigh-speed Lookups inNetwork Security ApplicationsApplications of Evolutionary Computation10.1007/978-3-031-30229-9_20(302-318)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30229-9_20
- Show More Cited By
Index Terms
Hardware-oriented optimization of Bloom filter algorithms and architectures for ultra-high-speed lookups in network applications
Hardware
Integrated circuits
Very large scale integration design
Application-specific VLSI designs
Index terms have been assigned to the content through auto-classification.
Recommendations
- Application and Research on Weighted Bloom Filter and Bloom Filter in Web Cache
WMWA '09: Proceedings of the 2009 Second Pacific-Asia Conference on Web Mining and Web-based Application
A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters and their generalizations, weighted Bloom filters and compressed Bloom filters have been suggested as a ...
Read More
- An Analysis oftheHardware-Friendliness ofAMQ Data Structures forNetwork Security
Security, Privacy, and Applied Cryptography Engineering
Abstract
Field-programmable gate arrays (FPGA) are increasingly used in network security applications for high-throughput measurement solutions and attack detection systems. One class of algorithms that are heavily used for these purposes, are approximate ...
Read More
- The Bloom paradox: when not to use a Bloom filter
In this paper, we uncover the Bloom paradox in Bloom Filters: Sometimes, the Bloom Filter is harmful and should not be queried. We first analyze conditions under which the Bloom paradox occurs in a Bloom Filter and demonstrate that it depends on the a ...
Read More
Comments
Information & Contributors
Information
Published In
Microprocessors & Microsystems Volume 93, Issue C
Sep 2022
396 pages
ISSN:0141-9331
Issue’s Table of Contents
Elsevier B.V.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 September 2022
Author Tags
- Bloom filter
- FPGA
- Network security
- Approximate membership query
- Non-cryptographic hash
Qualifiers
- Research-article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
4
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Nov 2024
Other Metrics
View Author Metrics
Citations
Cited By
View all
- Hassan MVliegen JPicek SMentens NLi XHandl J(2024)A Systematic Exploration of Evolutionary Computation for the Design of Hardware-oriented Non-cryptographic Hash FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654009(1255-1263)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654009
- Zeng ZXiao RLin XLuo TLin J(2023)Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detectionInformation Processing and Management: an International Journal10.1016/j.ipm.2023.10330660:3Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.ipm.2023.103306
- Hassan MSateesan AVliegen JPicek SMentens N(2023)Evolving Non-cryptographic Hash Functions Using Genetic Programming forHigh-speed Lookups inNetwork Security ApplicationsApplications of Evolutionary Computation10.1007/978-3-031-30229-9_20(302-318)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30229-9_20
- Sateesan AVliegen JMentens N(2022)An Analysis oftheHardware-Friendliness ofAMQ Data Structures forNetwork SecuritySecurity, Privacy, and Applied Cryptography Engineering10.1007/978-3-031-22829-2_16(287-313)Online publication date: 9-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22829-2_16
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables