| 講演名 | 2011-01-18 オートマトンの分割に基づく正規表現マッチング回路について(FPGA応用,FPGA応用及び一般) 中原 啓貴, 笹尾 勤, 松浦 宗寛, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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数を求め,提案手法が既存手法よりも優れていることを示す. |
| 抄録(英) | 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. |
| キーワード(和) | |
| キーワード(英) | |
| 資料番号 | VLD2010-98,CPSY2010-53,RECONF2010-67 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2011/1/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | オートマトンの分割に基づく正規表現マッチング回路について(FPGA応用,FPGA応用及び一般) |
| サブタイトル（和） | |
| タイトル（英） | A Regular Expression Matching Circuit Based on a Decomposed Automaton |
| サブタイトル（和） | |
| キーワード(1)（和/英） | |
| 第 1 著者 氏名（和/英） | 中原 啓貴 / Hiroki NAKAHARA |
| 第 1 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 第 2 著者 氏名（和/英） | 笹尾 勤 / Tsutomu SASAO |
| 第 2 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 第 3 著者 氏名（和/英） | 松浦 宗寛 / Munehiro MATSUURA |
| 第 3 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 発表年月日 | 2011-01-18 |
| 資料番号 | VLD2010-98,CPSY2010-53,RECONF2010-67 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 360 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |