Constructing deterministic finite automata by reconfigurable means for solving information security tasks

Abstract

Computer security requires the implementation of different measures - organizational, technical, cryptographic, etc. Network intrusion detection systems, antiviruses and other similar tools of technical protection based on signatures should solve in real time the computationally complex multi-pattern string matching task, which 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 of these approaches are: content addressable memory, Bloom filter and Aho-Corasick Algorithm. Each approach has its advantages and disadvantages. Effective construction of more and more complex signature-based tools of technical secure protection is impossible without a comprehensive analysis of the properties and specific features of every approach. In this study, in order to improve the efficiency of information security tools created on the basis of the FPGA, the main features of the third of the listed approaches are analyzed. Based on the analysis of the stateof-the-art finite automata realizing Aho-Corasick algorithm, the specialty of their implementation on FPGAs, encountering problems and ways to solve them are also investigated.