An FPGA-accelerated string-matching engine

Date

2024-11-29

Author

Yalçın, Süleyman Samet

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

33
views

0
downloads

Cite This

A string-matching engine locates predefined pattern strings within an input string. Various applications, such as DNA analysis and intrusion detection systems, depend on high-performance string-matching engines. In this thesis, we propose a hardware architecture for variable-sized exact string matching, FPGA-Accelerated String-Matching Engine (FASTME), that implements a parallelized version of the well-known, automata-based Aho-Corasick algorithm to achieve high throughput. It is a multi-core architecture with multiple hardware thread blocks on each core, exploiting parallelism, determinism, and scalability of FPGAs. FASTME is fully configurable, including the number of cores and threads, and supports different pattern string sets and performance requirements. The suggested design combines content-addressable and random-access memories for efficient state transitions, supported by an optimized thread arbitration mechanism performed by a local interconnect. A comprehensive evaluation study is conducted to study the effects of hardware parameters on the maximum synthesis frequency and resource consumption. Furthermore, pattern string sets and input strings with different characteristics are constructed to evaluate the number of cycles per character and the resulting throughput. Compared to traditional implementations, the FASTME shows notable improvements in string matching. On an AMD Ultrascale+ Virtex-7 FPGA, the system achieves throughput rates of up to 9.87 Gbps with 2,541 SNORT intrusion detection signatures. Also, it achieves a 10.55 Gbps throughput rate with 3,305 SNORT signatures when the maximum pattern length is limited to 100. When the limit is 15, FASTME achieves a throughput of 10.15 Gbps and 181.77 Gbps for 12,115 and 279 SNORT signatures. The deterministic performance of FASTME architecture makes it ideal for real-time string-matching applications like intrusion detection.

Subject Keywords

Variable-sized string matching, Aho-Corasick algorithm, Field programmable gate array, Configurable and parallel hardware architecture

URI

https://hdl.handle.net/11511/112666

Collections

Graduate School of Natural and Applied Sciences, Thesis