Constructing optimal reconfigurable pattern matching tools for information security
DOI:
https://doi.org/10.18372/2225-5036.25.13824Keywords:
information security, FPGA, multi-pattern string matching, combination of approaches, efficiency, optimizationAbstract
Signature-based security tools such as network intrusion detection systems, anti-virus scanners, filters against network worms and other similar systems perform in real time computation-intensive task of multi-pattern string matching against tens of thousands or even millions of predefined malicious patterns. 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, designers pay more attention to hardware approaches to accelerate pattern matching. The reconfigurable devices based on Field Programmable Gate Arrays (FPGA) combining the flexibility of software and the near-ASIC performance, have become increasingly popular for this purpose. The state-of-the-art solutions made in this area around the world were analyzed. There are three main approaches to fulfill the pattern matching 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). But none of them shows clear advantages over others. In this article, we propose a set of methods to increase the effectiveness of reconfigurable security tools by synthesizing optimal recognition modules that maximize the benefits of each approach. The Parallel Combination Method divides a set of patterns between several matching blocks that use different approaches to better fit each of them. The Sequential Cascading Method processes patterns in parts: if the first fragment does not match, the rest can be ignored. The Vertical Join Method couples together different approaches or techniques in a single unit to provide higher efficiency of the resulting device. The optimization procedure maximizes efficiency gains for each method.
The methods and methodologies presented in this study will allow developers to create more efficient reconfigurable tools for information security systems.
References
С. Казмірчук, А. Корченко, Т.І. Паращук, "Аналіз систем виявлення вторгнень", Захист інформації, Т. 20, № 4, С. 259-276, 2018.
Б. Смит, Методы и алгоритмы вычислений на строках. Теоретические основы регулярных вычисле-ний. Пер. с англ. М.: Вильямс, 2006, 496 с.
С. Гільгурт, "Множинне розпізнавання рядків у системах виявлення вторгнення на базі ре-конфігуровних обчислювачів", Сучасні комп’ютерні системи та мережі: розробка та використання: матері-али 5-ої Міжнар. наук.-техн. конф. ACSN-2011, 29 ве-ресня – 01 жовтня 2011, Львів, Україна. Л.: Вид-во Нац. ун-ту «Львів. політехніка», С. 54–56, 2011.
V. Paxson, K. Asanovic, S. Dharmapurikar, J. Lockwood, R. Pang, R. Sommer, N. Weaver, "Rethinking Hardware Support for Network Analysis and Intrusion Prevention", Proceedings of the First USENIX Workshop on Hot Topics in Security, pp. 63-68, 2006.
H. Chen, Y. Chen, D.H. Summerville, "A Survey on the Application of FPGAs for Network Infrastructure Security", IEEE Communications Surveys and Tutorials, pp. 541-561, 2011.
С. Гильгурт, "Реконфигурируемые вычи-слители. Аналитический обзор", Электронное модели-рование, Т. 35, № 4, С. 49-72, 2013.
Ю. Коростиль, С. Гильгурт, "Принципы построения сетевых систем обнаружения вторжений на базе ПЛИС", Моделювання та інформаційні техно-логії. Зб. наук. пр. ІПМЕ ім. Г.Є. Пухова НАН України, Вип. 57, С. 87-94, 2010.
А. Лукацкий, Обнаружение атак, СПб.: БХВ-Петербург, 2001, 624 с.
С. Гільгурт, "Побудова асоціативної пам'-яті на цифрових компараторах реконфігуровними засобами для вирішення задач інформаційної безпе-ки", Электронное моделирование, Т. 41, № 3, С. 59-80, 2019.
С. Гільгурт, "Побудова фільтрів Блума реконфігуровними засобами для вирішення задач інформаційної безпеки", Безпека інформації, Т. 35, № 1, С. 53-58, 2019.
С. Гільгурт, "Побудова скінченних авто-матів реконфігуровними засобами для вирішення задач інформаційної безпеки", Захист інформації, Т. 21, № 2, С. 111-120, 2019.
В. Евдокимов, А. Давиденко, С. Гильгурт, "Организация централизованной генерации файлов конфигураций для аппаратных ускорителей задач информационной безопасности", Моделювання та інформаційні технології, № 81, С. 3-11, 2017.
С. Гильгурт, Б. Дурняк, Ю. Коростиль, "Противодействие атакам алгоритмической сложнос-ти на системы обнаружения вторжений", Моделюван-ня та інформаційні технології, № 71, С. 3-12, 2014.
S. Dharmapurikar, J.W. Lockwood, "Fast and scalable pattern matching for network intrusion detection systems", IEEE Journal on Selected Areas in Communications, Article Vol. 24, no. 10, pp. 1781-1792, Oct 2006.
Y.H. Cho, W.H. Mangione-Smith, "A pattern matching co-processor for network security", in 42nd Design Automation Conference, Anaheim, CA, Jun 13-17 2005, LOS ALAMITOS: IEEE Computer Soc, in Design Automation Conference DAC, 2005, pp. 234-239.
I. Sourdis, D. Pnevmatikatos, S. Vassiliadis, "Scalable Multigigabit Pattern Matching for Packet Inspection", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 16, no. 2, pp. 156-166, 2008.
L. Tan, T. Sherwood, "A high throughput string matching architecture for intrusion detection and prevention", in 32nd International Symposium on Computer Architecture, Madison, WI, Jun 04-08 2005, LOS ALAMITOS: IEEE Computer Soc, in Conference Proceedings Annual International Symposium on Computer Architecture, 2005, pp. 112-122
