正規表現エンジンの話

seccamp'20 アドベントカレンダー 13日目の記事です

2週間ほど遅刻しました。

DFAエンジンとNFAエンジン

正規表現には2つのエンジンがある。DFAエンジンとNFAエンジンである。

このうち、ReDoS脆弱性が起こるのはNFAエンジンであり、DFAエンジンは仕組み上起こりえない。

というのも、DFAエンジンの正規表現はどんな書き方をしても同じ処理になるため、NFAと違って「脆弱性がないように気を付けて書く」という必要がない。

ついでに、DFAエンジンの方がマッチングも高速である。

ここまで行くと、NFAエンジンいらなくね？となるが、現状プログラム言語でメジャーに使われているのはNFAエンジンの方である。

何かプログラムを書いていて正規表現を使う場合、その目的が「特定の文字列にマッチングするか」だけであることはあまりない。

例えばログやメールの抽出、特定の文字列の置換など「マッチングするか確かめた上で文字列を抽出・置換する」ということをよく行うことになる。

ここでDFAの問題が出てくる。DFAはその仕組み上、マッチングした文字列が何かを調べることができないのである。

つまり、その文字列が正規表現にマッチするかしないか以外の結果を何も得られない。

例えばフォーマットが正しいかどうか、を調べるのであればDFAエンジンは高速かつ安全だが、フォーマットに合うように文字列を修正する、となるとそれはDFAエンジンではできない。

そして、昨今のプログラミング言語は言語自体に文字列を扱う関数が充実している場合が多い。つまり、基本的に正規表現を積極的に使う場合は、あまり単純でない処理をしたい場合になりがちである。

そういった観点からも、多くのプログラミング言語でNFAエンジンが採用されているのは自然な流れでもある。

応用性はNFAエンジンに比べ少ないとはいえ、DFAエンジンにできることであればDFAエンジンを使った方が大抵の場合ベターである。

そこで、言語によってはNFAエンジンとDFAエンジンを併用しているものもある。

GNUのgrepやawkはその最たる例で、DFAができることはDFAで、できないことはNFAで行う、という効率的な手法を採用している。

大抵の人はプログラムを書くときにゴリゴリ正規表現を書くことは少ないと思うので、普段知っておく必要はあまりないけど知っているとたまーーーーに役立つ。