Constructing Bloom filters by reconfigurable means for solving information security tasks
DOI:
https://doi.org/10.18372/2225-5036.25.13594Keywords:
information security, reconfigurable accelerator, FPGA, Bloom filter, hash-function, signature, multi-pattern string matching, DPIAbstract
Recently, the string matching task became a performance bottleneck in network intrusion detection, anti-virus, anti-worms and other signature-based information security systems. Unlike the firewall, NIDS examines not only packet headers, but also the packet bodies, that is, performs the deep packet inspection (DPI). The multi-pattern string matching task is a specific type of string matching functionality performed in DPI systems to search an input stream for a set of patterns rather than a single pattern. Due to rising traffic rates, increasing number and sophistication of attacks and the collapse of Moore's law for sequential processing, traditional software solutions can no longer meet the high requirements of today’s security challenges. Therefore, hardware approaches are proposed to accelerate pattern matching. Combining the flexibility of software and the near-ASIC performance, reconfigurable hardware devices based on Field Programmable Gate Arrays (FPGA) have become increasingly popular for this purpose. There are three main approaches to fulfill the computation-intensive multi-pattern string matching task using FPGA. The techniques (and underlying technologies) of these approaches are: content addressable memory (based on digital comparators), Bloom filter (based on hash-functions) and Aho-Corasick Algorithm (based on finite automata). This article is devoted to the investigation of the second approach - Bloom filter. The features (advantages and disadvantages) of this approach in terms of resource costs, speed/throughput parameters, as well as scaling parameters are explored. The basic scheme and its modifications are considered. The performance characteristics, problems and challenges of implementing this approach on reconfigurable accelerators as well as ways to overcome them are analyzed. The obtained results allow improving the technical parameters when designing pattern matching modules, which are speed-critical components of the signature-based information protection systems hardware. The knowledge obtained in this study allows developers to create more effective reconfigurable means for information security.
References
С. Казмірчук, А. Корченко, Т. Паращук, "Аналіз систем виявлення вторгнень", Захист інфор-мації, Т. 20, № 4, С. 259-276, 2018.
Б. Смит, Методы и алгоритмы вычислений на строках. Теоретические основы регулярных вычисле-ний. Пер. с англ. М.: Вильямс, 2006, 496 с.
С. Гільгурт, "Множинне розпізнавання рядків у системах виявлення вторгнення на базі ре-конфігуровних обчислювачів", Сучасні комп’ютерні системи та мережі: розробка та використання: матері-али 5-ої Міжнар. наук.-техн. конф. ACSN-2011, 29 вере-сня – 01 жовтня 2011, Львів, Україна. Л.: Вид-во Нац. ун-ту «Львів. політехніка», С. 54–56, 2011.
С. Гильгурт, "Реконфигурируемые вычи-слители. Аналитический обзор", Электронное модели-рование, Т. 35, № 4, С.49-72, 2013.
С. Гильгурт, "Применение реконфигури-руемых вычислителей для аппаратного ускорения сигнатурных систем защиты информации" // Тез. доп. Мiжнар. наук.-техн. конф. «Моделювання-2018». – Київ: Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, С. 107-110, 2018.
B. Bloom, "Space/time trade-offs in hash coding with allowable errors", Communications of the ACM, Vol. 13, No. 7, pp. 422-426, 1970.
D. Pryor, M. Thistle, N. Shirazi, "Text searching on Splash 2", IEEE Workshop on FPGAs for Custom Computing Machines, pp. 172-177, 1993.
A. Broder, M. Mitzenmacher, "Network applications of bloom filters: A survey", Internet Mathe-matics. Vol. 1, No. 4, pp. 485-509, 2004.
S. Dharmapurikar, P. Krishnamurthy, T. Sproull, J. Lockwood, "Deep packet inspection using parallel bloom filters", IEEE Micro, Vol. 24, No. 1, pp. 52-61, 2004.
S. Dharmapurikar, M. Attig, J. Lockwood, "Design and Implementation of a String Matching Sys-tem for Network Intrusion Detection using FPGA-based Bloom Filters", Washington University in St. Louis Engi-neering D. o. C. S.: Scholarship W. U. O., 2004.
T. Kocak, I. Kaya, "Low-power bloom filter architecture for deep packet inspection", IEEE Communi-cations Letters, Vol. 10, No. 3, pp. 210-212, 2006.
N. Artan, K. Sinkar, J. Patel, H. Chao, "Ag-gregated Bloom Filters For Intrusion Detection and Pre-vention Hardware", IEEE Global Telecommunications Conference (GlobeCOM), pp. 349–354, 2007.
Y. Chen, A. Kumar, J. Xu, "A New Design of Bloom Filter for Packet Inspection Speedup", IEEE Global Telecommunications Conference (GlobeCOM), pp. 1-5, 2007.
J. Harwayne-Gidansky, D. Stefan, I. Dalal, "FPGA-based SoC for real-time network intrusion detec-tion using counting bloom filters", Conference Proceedings - IEEE Southeastcon-2009, Article number 5174096, pp. 452-458, 2009.
S. Geravand, M. Ahmadi, "Bloom filter ap-plications in network security: A state-of-the-art sur-vey", Computer Networks, Vol. 57, No. 18, pp. 4047-4064, 2013.
В. Евдокимов, А. Давиденко, С. Гильгурт, "Централизованный синтез реконфигурируемых аппаратных средств информационной безопасности на высокопроизводительных платформах", Захист інформації, Т. 20, № 4, С. 247-258, 2018.
L. Carter, M. Wegman, "Universal classes of hashing functions Bloom filter applications in network security: A state-of-the-art survey", Computer Networks, Vol. 57, No. 18, pp. 4047-4064, 2013.
M. Ramakrishna, E. Fu, E. Bahcekapili, "Ef-ficient hardware hashing functions for high perfor-mance computers", IEEE Transactions on Computers, Vol. 46, No. 12, pp. 1378-1381, 1997.
L. Fan, P. Cao, J. Almeida, A. Broder, "Summary cache: A scalable wide-area Web cache shar-ing protocol", IEEE/ACM Transactions on Networking, Vol. 8, No. 3, pp. 281-293, 2000.
