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

摘要

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の分解に基づく正規表現マッチング回路の実現法について述べる．まず，MNTAUを文字列検出回路と状態遷移模擬回路に分解する．次に，文字列検出回路をDFA （Deterministic finite automaton）で実現し，状態遷移模擬回路をNFAで実現する．MNFAUの分解に基づく正規表現マッチング回路は，メモリの使用率とLUTの使用効率が優れており，安価なシステムで実装可能である．本論文では，並列ハードウェアにおける，NFA，DFA，及び分解したMNFAUの回路の面積と時間複雑度の解析を行い，MNFAUを分解することにより計算時間を増やすことなく面積を削減できることを示す．オープンソースの侵入検知ソフトウェアであるSNORTの正規表現の一部をXilinx社のFPGAに実装し，必要なメモリ量とLUT数を求め，提案手法が既存手法よりも優れていることを示す．