オートマトンの分解に基づく正規表現マッチング回路について

摘要

In this paper, we propose a regular expression matching circuit based on a decomposed automaton. To implement regular expressions on the hardware, first, we convert them to a non-deterministic finite automaton (NFA). Then, to reduce the number of states, we convert the NFA into a modular non-deterministic finite automaton with unbounded multi-character transition (MNFAU). Next, to realize it by a feasible amount of the hardware, we decompose the MNFAU into the deterministic finite automaton (DFA) and the NFA. The DFA part is implemented by an off-chip memory and a simple sequenser, while the NFA part is implemented by a cascade of logic cells. Also, this paper shows that the MNFAU based implementation is superior to the DFA and the NFA based ones, with respect to the area and time complexity.%NFA（Non-deterministic finite automaton）において，p文字までの文字列に対する遷移を許すことにより状態数を削減したNFAをMNFA（p）（Modular NFA with p-character-consuming transition）という.また，文字数pの制約を除いたMNFAをMNFAU（MNFA with unbounded multi-character transition）という.本論文では，MNFAUの分解に基づく正規表現マッチング回路の実現法について述べる.まず，MNFAUを文字列検出回路と状態遷移模擬回路に分解する.次に，文字列検出回路をDFA（Deterministic finite automaton）で実現し，状態遷移模擬回路をNFAで実現する.MNFAUの分解に基づく正規表現マッチング回路は，メモリの使用率とLUTの使用効率が優れており，安価なシステムで実装可能である.本論文では，並列ハードウェアにおける，NFA，DFA，及び分解したMNFAUの回路の面積と時間複雑度の解析を行い，MNFAUを分解することにより計算時間を増やすことなく面積を削減できることを示す.オープンソースの侵入検知ソフトウェアであるSNORTの正規表現の一部をXilinx社のFPGAに実装し，必要なメモリ量とLUT数を求め，提案手法が既存手法よりも優れていることを示す.