Optimalizace architektury NFA-Split

Optimization of the NFA-Split architecture

article in a collection out of WoS and Scopus

Czech

Počet signatur systémů pro detekci nebezpečného provozu se v  souvislosti s rozvojem počítačových sítí stále zvyšuje. To s sebou přináší nutnost redukovat počet zabraných zdrojů FPGA potřebných pro reprezentaci nedeterministických konečných automatů používaných pro akceleraci vyhledávání řetězců popsaných regulárními výrazy. Článek pojednává o možnostech optimalizace architektury NFA-Split. Dvě optimalizace jsou detailněji popsány. První je nahrazení determinizace algoritmem s kvadratickou časovou složitostí. Dosažené zrychlení je 4 až 39 násobné.  Druhou optimalizací je zavedení k vnitřních abeced v deterministické části architektury NFA-Split. Dosažená redukce potřebného počtu pamětí BRAM je v závislosti na množině regulárních výrazů až 98%.

Number of signatures used in intrusion detection systems is steadily growing in connection with the development of computer networks. This entails the necessity of reduction of utilized FPGA resources for implementation of non-deterministic finite automata used to accelerate regular expressions matching. The article discusses  possibilities of optimizing the NFA-Split architecture. Two optimization are described in detail. The first optimization is a replacement of determinization algorithm with an algorithm with quadratic time complexity. The achieved acceleration is 4-39 fold. The second optimization is the introduction of inner alphabets in deterministic part of the NFA-Split architecture. Reached reduction of the utilized BRAM memories is up to 98%.

NKA, FPGA, vyhledávání vzorů

NFA, FPGA, regular expression matching

KOŠAŘ, V.

2013

9. 9. 2013

Západočeská univerzita v Plzni

Plzeň

978-80-261-0270-0

Počítačové architektury a diagnostika PAD 2013

81

86

6