CAJ | 학술논문

正则表达式匹配在很多网络安全领域起着非常重要的作用。确定性有限自动机(DFA, deterministic finite automaton)具有线速稳定的匹配性能，因而更适合在高速网络环境下执行正则表达式匹配。但 DFA 可能由于状态膨胀而占用巨大的内存空间。作为状态膨胀问题的一种经典解决方案，i-DFA在大幅降低内存开销的同时，还能保证最差匹配性能。然而，已有方法构造i-DFA时在时间和空间上都是非常低效的。基于状态分组的思想，提出了一种高效的 i-DFA 构造方法。进一步地，对状态分组进行了形式化描述，并证明了获得最优状态分组是 NP困难的，并基于局部搜索的思想提出了一种近优的状态分组算法。实验结果表明，相比经典的i-DFA构造方法，所做的工作在时间和空间上都有极大的改进：i-DFA的状态规模可能只是已有方法的2/3，而构造i-DFA所用时间仅是已有方法的1/16。
정칙표체식필배재흔다망락안전영역기착비상중요적작용。학정성유한자동궤(DFA, deterministic finite automaton)구유선속은정적필배성능，인이경괄합재고속망락배경하집행정칙표체식필배。단 DFA 가능유우상태팽창이점용거대적내존공간。작위상태팽창문제적일충경전해결방안，i-DFA재대폭강저내존개소적동시，환능보증최차필배성능。연이，이유방법구조i-DFA시재시간화공간상도시비상저효적。기우상태분조적사상，제출료일충고효적 i-DFA 구조방법。진일보지，대상태분조진행료형식화묘술，병증명료획득최우상태분조시 NP곤난적，병기우국부수색적사상제출료일충근우적상태분조산법。실험결과표명，상비경전적i-DFA구조방법，소주적공작재시간화공간상도유겁대적개진：i-DFA적상태규모가능지시이유방법적2/3，이구조i-DFA소용시간부시이유방법적1/16。
Regular expression matching plays an important role in many network and security applications. DFA is the preferred representation to perform regular expression matching in high-speed network, because of its high and stable matching efficiency. However, DFA may experience state explosion, and thus consume huge memory space. As a classic-al solution for the problem of state explosion, i-DFA can reduce the memory consumption significantly and guarantee the worst matching performance at the same time. However, prior methods are inefficient in both time and space during the construction of i-DFA. An efficient i-DFA construction algorithm based on the idea of state grouping was proposed. Fur-thermore, a formal description for the problem of state grouping was given, and it was proved that it was NP-hard to get the best state grouping result. Thus, based on local search strategy, a near-optimal algorithm was introduced to divide states into different groups. Compared with the classical construction method, the significant improvement in both time and space is achieved;the i-DFA of the proposed method may have 2/3 states as that of prior method and the proposed i-DFA is constructed with only 1/16 time of it.