2015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日

バックトラックによる正規表現マッチングの時間計算量解析○中川 みなみ1,a)

南出 靖彦2,b)

概要：正規表現マッチングは文字列を操作するウェブプログラムなど，様々な場面で用いられており，その実装の多くはバックトラックに基づいている．そのため，正規表現マッチングにかかる時間が文字列の長さに関して線形でないことがあり，最悪の場合指数関数時間となる．
本発表では正規表現マッチングの時間計算量を判定する手法を提案する．対象の正規表現から先読み付き木トランスデューサを構成する．その先読み付き木トランスデューサから準同型写像や有限遷移系を構成し，それらを用いた遷移過程の中に反復補題が成り立つ遷移過程が存在しているか調べることで計算量を判定することができる．この判定には，Aho と Ullman による木トランスデューサの増加率の判定法を先読み付き木トランスデューサに拡張したものを利用する．
先行研究では，Engelfriet と Maneth のマクロ木トランスデューサの増加率の判定法を用い，正規表現
マッチングの計算時間が入力文字列に対して線形であるかどうかを判定する手法が提案された．本発表で提案する手法は，時間計算量が線形であるかどうかの判定だけでなく O(n2 ), O(n3 ), . . . になるこ
とも判定できる．
この提案手法を OCaml によって実装し，既存の PHP プログラムで使用されている正規表現を対象に実験を行った．実験の結果，393 個中入力文字列の長さに対して 338 個が線形，44 個が 2 乗，6 個が 3乗の計算量であると判定された．
キーワード：正規表現，木トランスデューサ

Analyzing Time Complexity of Regular Expression Matching Basedon Backtracking
Minami Nakagawa1,a)Yasuhiko Minamide2,b)Abstract: Regular expression matching is used in various situations such as web programming. Most of
its implementations are based on backtracking. Thus, its execution time may not be linear with respect
to the length of an input string. In the worst case, it takes exponential time. In previous research, they
proposed a method checking whether the matching of a given regular expression runs in linear time.
They translated a regular expression to a tree transducer with regular lookahead and applied the resultof Engelfriet and Maneth on proliferation rate of macro tree transducers.
In this presentation, we propose a new method of analyzing time complexity of regular matching. Thismethod can check a regular expression matching runs in O(n), O(n2 ), O(n3 ), . . . with respect to thelength of input. Instead of the result of Engelfriet and Maneth, we extend the result of Aho and Ullman
about proliferation rate of a tree transducer to a tree transducer with lookahead. We obtain a set ofhomomorphisms from a transducer and then construct a transition system to check whether or not there
exist a transition satisfying the condition of the pumping lemma.
We implemented this method by OCaml and conducted experiments analyzing execution time of regularexpression matching. We applied out method to regular expressions used on existing PHP programs.
Our experiments showed that the time complexity of 338 regular expressions are linear, 44 ones arequadratic, and 6 ones are cubic.
Keywords: regular expression, tree transducer

1

2015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日

Or

1. はじめにOr

Fail

正規表現マッチングは文字列を操作するウェブプログ
ラムなど，様々な場面で用いられており，その実装の多

Or

Fail

くはバックトラックに基づいている．そのため，正規表
現マッチングにかかる時間が文字列の長さに関して線形でないことがあり，最悪の場合指数関数時間となる．こ

Fail
図 1

Successa|b∗ a に対する ba のマッチングの過程を表す木

れは DoS 攻撃の足がかりになると指摘されている [8]．
これは時間の問題だけではない．Perl 互換の正規表現の実装である PCRE では，正規表現の計算回数にリミットが設けられており，計算回数がリミットを超えると本来マッチするはずの文字列もマッチ失敗と判断されてしまう．そのため，計算回数が容易にリミットに達してしまう正規表現はプログラムの正当性に影響を及ぼす可能性がある．
このような状況をふまえて，Sugiyama と Minamideの先行研究 [1] では木トランスデューサを用いて正規表
現マッチングの計算時間が入力文字列に対して線形であるかどうかを判定する手法が提案された．木トランス
デューサとは，入力して与えられた木を別の木に変換する変換機である．この先行研究は，対象の正規表現から先読み付きトップダウン木トランスデューサを構成する
ことにより，線形であるか判定を行うものである．構成

本研究で提案する手法は，正規表現から先読み付き木
トランスデューサを構成し，そのサイズ増加率を決定するものである．サイズ増加率を決定するために，先読み付き木トランスデューサの遷移規則から状態列を生成する準同型写像を構成する．次に，準同型写像から有限遷移系を構成し，その有限遷移系を用いて初期状態から遷移を行ったとき，特定の遷移過程が存在するかどうかの探索を行うことで計算量の判定を行う．
この提案手法を OCaml によって実装し，既存の PHP
プログラムで使用されている正規表現を対象に実験を行った．実験の結果，393 個中入力文字列の長さに対して 338 個が線形，44 個が 2 乗，6 個が 3 乗の計算量であると判定された．

2. 先行研究する木トランスデューサは，入力文字列を正規表現マッ
チングの計算過程を表す木に変換する．このため，構成
した木トランスデューサが入力の大きさに対して，定数倍の大きさに収まる木しか出力しないという性質を持つかどうかを検査することによって，計算量が文字列の長さに対して線形であることを判定することができる．

Sugiyama と Minamide による木トランスデューサを用いた正規表現マッチングの線形性判定の手法を説明する．先行研究で扱う正規表現は，以下の構文のもので
ある．

r ::=

ϵ

（空列）

|

c

（文字）

|

r1 r2 （連接）|r1 |r2 （選択）|r1∗

この先行研究では，計算量が線形であるかどうかの判定しか行うことができず，計算量が入力文字列の長さに対して 2 乗や 3 乗になることを判定できるようにアルゴ
リズムを拡張することが課題であった．また，先行研究
は Engelfriet と Maneth のマクロ木トランスデューサの線形増加性判定 [6] を利用して判定を行っているため，（繰り返し）

正規表現マッチングの過程を模倣する木とは次のような木構造である．

プログラムが複雑であった．そのような状況をふまえ，本研究では計算量が線形であるかどうかの判定だけでな

ctree ::=く O(n2 ) や O(n3 ) になることも判定できる新たなアルゴリズムを構成する．なお，本研究では Aho と Ullman
によって与えられている木トランスデューサの計算量判
定 [5] を先読み付き木トランスデューサに拡張したものを用いて計算量の判定を行う．
1

2

a)
b)

筑波大学 システム情報工学研究科 コンピュータサイエンス専
攻Department of Computer Science, University of Tsukuba
東京工業大学 数理・計算科学専攻
Department of Mathematical and Computing Sciences,
Tokyo Institute of Technology
nakagawa@score.cs.tsukuba.ac.jp
minamide@is.titech.ac.jp

Success

|

Fail

|

Or ctree × ctree

例えば，文字列 ba の a|b∗ a に対するマッチングの過程を表す木は図 1 のようになる．
図 1 の木は正規表現 a|b∗ a のマッチを全探索したものであるが，実際のバックトラックに基づく実装ではマッ
チングが一つ成功するとそこで計算は終了する．そのため，全探索を行う木を一つ目のマッチ成功までの木に構成し直す必要がある．そこで，上記の木構造を以下の木構造に変換する．

2

2015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日

ctree

Successq(a) → ua ∈ Σ, u ∈ T∆,Q

|

Fail

q(ϵ) → uu ∈ T∆|

Or1 ctree|

Or2 ctree × ctree::=

文字列から木への変換であるため，遷移規則には一つの変数しか現れない．そのため，遷移規則には変数を省略した記法を用いている．
例 3.1 (トップダウン木トランスデューサ). 入力木が正規

また，全探索する計算を模倣した木から一つ目のマッチ

表現 a|b∗ a にマッチするかどうかを判定する木を出力するまでの計算を模倣した木に変換する関数や，部分木が成木トランスデューサ M = (Q, Σ, ∆, [[a|b∗ a]], R) を考える．

功するマッチを含むか検査する関数を使用する．

ここで，Q = {[[a|b∗ a]], [[b∗ a]], [[ϵ]]}，Σ = {b(1) , a(1) , ϵ(0) }，そのような木を出力する先読み付き木トランスデュー
サを構成する．構成した木トランスデューサが入力の大∆ = {Or(2) , Success(0) , Fail(0) } とする．遷移規則 R は
以下の通りに与えられる．

きさに対して線形な木しか出力しないならば，正規表現
マッチングの計算時間が線形であるといえる．木トラ
ンスデューサによって変換された木 t′ が入力木 t に対して線形サイズ増加 (linear size increase) であるとは，size(t′ ) ≤ c · size(t) という関係が成り立つときである．
この判定は，Engelfriet と Maneth のマクロ木トラン
木トランスデューサに構成し直して行っている．
この先行研究の手法では，線形サイズ増加であること

Success[[ϵ]](a)→Fail[[ϵ]](b)

→

Fail

∗

[[b a]](ϵ)→

Or(Fail, Fail)[[b∗ a]](a)→Or(Fail, [[ϵ]])[[b a]](b)→Or([[b∗ a]], Fail)[[a|b∗ a]](ϵ)→

Or(Fail, Or(Fail, Fail))[[a|b∗ a]](a)→Or([[ϵ]], Or(Fail, [[ϵ]]))∗→Or(Fail, Or([[b∗ a]], Fail))[[a|b a]](b)の判定しか行えず，入力文字列に対して計算量が O(n2 )た，マクロ木トランスデューサの線形サイズ増加の判定→∗

スデューサの線形サイズ増加の判定手法を，先読み付きや O(n3 ) であるかの判定を行うことができなかった．ま[[ϵ]](ϵ)

この M に文字列 ba を表す木 b(a(ϵ)) を入力として与えたときの変換を以下に示す．

手法を用いていたことがプログラムを複雑にしていた．

[[a|b∗ a]](b(a(ϵ)))

3. 先読み付き木トランスデューサ
3.1 木
集合 Σ と，Σ から自然数を返す関数である Arity で表される組 (Σ, Arity) をランク付きアルファベットとする．Σ(k) は集合 {σ ∈ Σ | Arity(σ) = k} を表し，→Or(Fail, Or([[b∗ a]](a(ϵ)), Fail))→Or(Fail, Or(Or(Fail,[[ϵ]](ϵ)), Fail))→Or(Fail, Or(Or(Fail, Success), Fail))

3.3 先読み付き木トランスデューサ
先読み付きトップダウン木トランスデューサ M の定

Arity(σ) = k のとき σ (k) と表記する．Σ から成る木の義は M = (Q, Σ, ∆, q0 , R, P, p0 , δ) で与えられる．ここ集合を TΣ と表し，木 t 内における記号 σ の出現回数をで，Q は状態の集合を，Σ と ∆ はそれぞれ入力記号と出#σ (t) と表す．また，木 t に対して |t| は木の大きさを

力記号の集合を表している．q0 ∈ Q は初期状態を表し，表す．

R は次の形式の遷移規則の集合を表している．
q(a) → u

3.2 木トランスデューサ

q(ϵ) → u木トランスデューサとは，木から木への変換を行う機⟨p⟩a ∈ Σ, u ∈ T∆,Qu ∈ T∆

械である．本研究で扱う木トランスデューサは，文字列

ここで，⟨p⟩ は入力の残りの文字列を先読みオートマを木で表したものを入力とし，木を出力するトップダウトンで検査した結果が p であることを表している．

ン木トランスデューサである．ここで，文字列を木で表

また，(P, p0 , δ) は先読みオートマトンを表しており，したものとは，σ ∈ Σ のランクを 1 とし，文字列の終わP は 状 態 の 集 合 を ，p0 ∈ P は 初 期 状 態 を 表 し て いりを表す ϵ のランクを 0 として表したものである．例える．δ は P × Σ → P である遷移規則で δ(p, ϵ) = p，ば文字列 ba の場合，b(a(ϵ)) と表す．

δ(p, wa) = δ(δ(p, a), w) となり，文字列の最後の文字か

木トランスデューサ M の定義は M = (Q, Σ, ∆, q0 , R)で与えられる．ここで，Q は状態の集合を，Σ と ∆ はそら適用していく．δ(p0 , w) = p となるとき，w ∈ L(p) と表す．

れぞれ入力記号と出力記号の集合を表している．q0 ∈ Q

全ての遷移規則において右辺に一つ以上の ∆ 内の記

は初期状態を表し，R は次の形式の遷移規則の集合を表号を含む木トランスデューサを非消去 (non-erasing) でしている．

あるという．本研究では，非消去な先読み付き木トラン

3

2015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日

スデューサを扱う．

O(g(n)) = {f (n) | ∃k.∀n.f (n) ≤ kg(n)}∗u ∈ T∆ において q(s) −→ u となるとき，Mq (s) と表記Ω(g(n)) = {f (n) | ∃k.∀n.∃n′ > n.f (n′ ) ≥ kg(n′ )}する．ここで，Mq (s) の増加率を次のように定める．

gM (n) = max|s|=n |Mq (s)|Θ′ (g(n)) = O(g(n)) ∩ Ω(g(n))
本研究で構成するアルゴリズムは [5] の定義や定理を例 3.2 (先読み付きトップダウン木トランスデューサ). 例

基礎としている．まず，正規表現から木トランスデュー

3.1 を先読み付きトップダウン木トランスデューサにしたサを構成し，その木トランスデューサの遷移規則から状M ′ = (Q, Σ, ∆′ , [[a|b∗ a]], R, P, p0 , δ) を考える．ここで，

態列を生成する準同型写像を構成する．次に準同型写像(2)(1)∆′ = {Or2 , Or1 , Success(0) , Fail(0) }，P = {p∅ , p0 , p1 }とする．なお，p∅ = ∅，p0 = {[[ϵ]]}，p1 = {[[a|b∗ a]], [[b∗ a]]}から有限遷移系を構成し，その有限遷移系を用いて初期である．先読みオートマトンの遷移規則 δ は以下のよう状態から遷移を行う．そのとき，特定の遷移過程が存在するかどうかの探索を行うことでオーダの判定を行う．

になる．

4.1 準同型写像
δ(p∅ , a)=p∅ ,δ(p∅ , b)=p∅∆ と Q 上の木から状態列を生成する関数 π : T∆,Q →∗δ(p0 , a)=p1 ,δ(p0 , b)=p∅δ(p1 , a)=p∅ ,δ(p1 , b)=p1

Q を次のように定める．
π(f (t1 , ..., tn )) = π(t1 ) . . . π(tn )遷移規則 R′ は，例 3.1 の遷移規則において状態 [[b∗ a]]と [[a|b∗ a]] からの遷移が以下のように変わったものである．

π(q(x)) = q
準同型写像 ha,p : Q → Q∗ は，q(a) → u ⟨p⟩ ∈ R のと
き ha,p (q) = π(u) とする．また，状態 q ′ が ha,p (q) に含∗→Or2 (Fail, Fail)∗[[b a]](a)→Or2 (Fail, [[ϵ]])[[b∗ a]](b)→Or1 ([[b∗ a]])⟨p1 ⟩[[b∗ a]](b)→Or2 ([[b∗ a]], Fail)⟨p∅ ⟩, ⟨p0 ⟩[[a|b∗ a]](ϵ)→

Or2 (Fail, Or2 (Fail, Fail))∗[[a|b a]](a)→Or1 ([[ϵ]])⟨p0 ⟩[[a|b∗ a]](a)→Or2 ([[ϵ]], Or2 (Fail, [[ϵ]]))⟨p∅ ⟩, ⟨p1 ⟩[[a|b∗ a]](b)→Or2 (Fail, Or1 ([[b∗ a]]))⟨p1 ⟩[[a|b∗ a]](b)→Or2 (Fail, Or2 ([[b∗ a]], Fail))⟨p∅ ⟩, ⟨p0 ⟩[[b a]](ϵ)

まれることを q ′ ∈ ha,p (q) と表記し，集合 Hp,p′ を次のように定義する．

この M ′ に文字列 ba を表す木 b(a(ϵ)) を入力として与えたときの変換を以下に示す．
∗[[a|b a]](b(a(ϵ)))→

Or2 (Fail, Or1 ([[b∗ a]](a(ϵ))))→Or2 (Fail, Or1 (Or2 (Fail, [[ϵ]](ϵ))))→Or2 (Fail, Or1 (Or2 (Fail, Success)))

Hp,p′ = {ha,p′ | δ(p′ , a) = p}p′1 = p2 である場合のみ，2 つの準同型写像 h1 ∈ Hp1 ,p′1 ，n∗h2 ∈ Hp2 ,p′2 は合成される．このとき，Hp,p′ と Hp,p′ を

次のように定義する．
0
Hp,p

=

{id}

0
Hp,p
′

=

n+1
Hp,p
′

=

∅
∪

∗
Hp,p
′

=

if p ̸= p′p′′ ∈P

∪

n≥0

n
Hp,p
′′ ◦ Hp′′ ,p′

n
Hp,p
′

次の定理は，[5] で与えられている定理を [6] における議論をもとに詳細化したものである．
定理 4.1 (反復補題). Hp,p′ を Q 上の準同型写像とす

例 3.1 では Success の右側にも部分木が存在していたが，る．Q′ ⊆ Q，q ∈ Q，α ∈ Hp∗1 ,p3 であり，#Q′ (α(q)) に

先読み付き木トランスデューサの例では Success の右側

上限がないとき，次のような β1 ∈ Hp∗1 ,p2 ，β2 ∈ Hp∗2 ,p2 ，に部分木を構成していない．

β3 ∈ Hp∗2 ,p3 と q1 , q2 ∈ Q が存在する．

4. 時間計算量解析与えられた正規表現から正規表現マッチングの時間計
算量を判定するアルゴリズムを構成する．木トランス• q1 ∈ β3 (q)• q1 と q2 は β2 (q1 ) 内の別々の場所に出現する• q2 ∈ β2 (q2 )• β1 (q1 ) ∩ Q′ ̸= ∅，β1 (q2 ) ∩ Q′ ̸= ∅デューサ M が与えられたとき，サイズ増加率の計算量を決定する．すなわち，自然数 i に対して gM (n) ∈ Θ′ (ni )が成り立つか判定を行う．ここで，関数 g(n) に対して′のオーダ Θ (g(n)) の定義を以下に示す．

4.2 状態の増加率とそのオーダ
先読みの状態 p での状態 q の増加率 fq,p (n) を次のように定める．

4

2015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日
nfq,p (n) = max{|α(q)| | ∃p′ .α ∈ Hp,p′}

Ĥp,p′ から有限遷移系を構成する;= {q | q ∈ Q′ ∧ 有限遷移系の遷移過程より

(i+1)

Qp

(i)

i ≥ 0，j ≥ −1 に対して，状態の集合 Qp ⊆ Q と反復補題が成り立たない };[j]

Qp ⊆ Q を次のように定義する．

[i]

[i−1]

then break;(i+1)= ∅ then i := −3; break;else if Qp

(i)
[i−1]
Qp = {q | q ∈ Q − Qp
∧ fq,p (n) ≤ ∃c.cni }Qp = Qp(i+1)

if q0 ∈ Qp[−1]
Qp = ∅

else i := i + 1;
until false;

(i)

∪ Qp

ComputeOrder := i + 2;

定理 4.2. M を非消去な先読み付き木トランスデュー
(i)

end;

サとする．このとき，q ∈ Qp であることと gMq (n) ∈Θ′ (ni+1 ) であることは同値である．

上記のアルゴリズム 2(b) で行われる ĥa,p′ の計算では，(i)

また，以下の定理は Qp の要素を帰納的に判定するも次の q̂ を使用する．


q
q̂ =
ϵ

のである．
[i]
定理 4.3 (Lemma 4.3[5]). q ∈ Q − Qp ，i ≤ −1 のとき，∗全ての p′ と α ∈ Hp,p[i] α(q) が有限で′ において，#
Q−Q
p′

(i+1)

あるならば q ∈ Qp

である．

[i]

if q ̸∈ Qp[i]

if q ∈ Qp

ha,p (q) = q1 q2 . . . qn とすると，ĥa,p (q) = qˆ1 qˆ2 . . . qˆn となる．

4.3 有限遷移系

(i+1)

また，Qp

定理 4.1 と定理 4.3 に基づき状態の増加率を決定する
ために，準同型写像の集合 Hp,p′ から有限遷移系の遷移
規則を次のように生成する．ここで，ha,p′ ∈ Hp,p′ である．

• ⟨q, p⟩ → ⟨(qi , qj ), p′ ⟩•if qi , qj ∈ ha,p′ (q),′′⟨(q1 , q2 ), p⟩ → ⟨(q1 , q2 ), p′ ⟩if q1′ ∈ ha,p′ (q1 ), q2′ ∈ ha,p′ (q2 )⟨(q1 , q2 ), p⟩ → ⟨(qi , qj , qk ), p′ ⟩反復補題が成り立たず #Q (α(q)) は有限となり，定理 4.3
であるといえる．

(i)q0 ∈ Qp だった場合，オーダは Θ′ (ni+1 ) になる．ま(i)
た Qp が空であった場合，オーダは入力文字列に対して

i ̸= j

指数関数的になる．

5. 実装と実験

if qi , qj ∈ ha,p′ (q1 ), qk ∈ ha,p′ (q2 ), i ̸= j

4 章で説明した方法で正規表現マッチングの過程を模• ⟨(q1 , q2 , q3 ), p⟩ → ⟨(q1′ , q2′ , q3′ ), p′ ⟩if q1′ ∈ ha,p′ (q1 ), q2′ ∈ ha,p′ (q2 ), q3′ ∈ ha,p′ (q3 )このとき，初期状態を q0 とすると，有限遷移系を使っ∗∗移過程が存在するか探索を行う．存在しなかった場合，
より q ∈ Qp

if q ′ ∈ ha,p′ (q)の判定では，q ∈ Q′ において有限遷移系から ⟨q, p⟩ −→ ⟨(q1 , q2 ), p1 ⟩ −→ ⟨(q1 , q2 , q2 ), p2 ⟩ となる遷

(i+1)

• ⟨q, p⟩ → ⟨q ′ , p′ ⟩•∗∗倣する先読み付き木トランスデューサを構成し，5 章で表した方法でそのオーダを判定する．実装は OCaml を用いて行った．正規表現の構文解析には Sakuma ら [3]て初期状態から遷移したときに ⟨q0 , p⟩ −→ ⟨(q1 , q2 ), p1 ⟩ −→が作成したライブラリを用いた．Perl 準拠の標準的な正⟨(q1 , q2 , q2 ), p2 ⟩ となる遷移過程がある場合，定理 4.1 よ規表現をサポートし，特に 2 章の構文に以下の構文を加∗り反復補題が成り立つといえる．その場合，α ∈ Hp,p′

えたものを対象としている．

において，#Q (α(q0 )) は有限ではない．

4.4 アルゴリズム
準同型写像 Hp,p′ が与えられたときの増加率を判定するアルゴリズムを以下に示す．

function ComputeOrder (Hp,p′ )

r

::=

...

|

[c1 c2 . . . cn ] （文字クラス）|r?

（0 回または 1 回の r）

|

r

∗?

（貪欲でない繰り返し）

|

r

+

（1 回以上の繰り返し）|

r{n}{m}（n 回以上 m 回以下の繰り返し）

貪欲でない繰り返しとは，より少ない r の繰り返しに

begin
i := −1;マッチする構文で，r∗? = ϵ|rr∗? と展開される．先読み

repeatやアドミックグループ，後方参照といった拡張はサポー′[i]:= Q − Qp ;

Ĥ

= {ĥ

Q

p,p′

a,p′

トしていない．なお，行頭を意味する ^ から始まらない

|h

a,p′

∈H

p,p′

} を構成する;[i]ĥa,p′ = ha,p′ (q) から Qp 内の状態を除去した状態

列 (q ∈ Q′ );正規表現は .∗? から始まるものとし，行末を意味する $で終わらない正規表現は .∗ で終わるものとする．
先行研究 [1] のプログラムは 6000 行を超えるもので52015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日あったが，本研究のプログラムは 1500 行と大幅に簡単マッチする．先行研究では非線形と判定され，本研究になった．

では Θ′ (n3 ) と判定された．また，反例の文字列として>< imag(e >< image)n >>n > /imag が出力された．

6. 実験

PCRE で反例の文字列を実行した結果，n = 100 のとき

先行研究 [1] で使用された正規表現 393 個を対象に実験を行った．これは，PHO-Fusion，phpMyAdmin，

0.079s，n = 200 のとき 0.58s，n = 400 のとき 4.3s とな
り O(n3 ) に近いことが確認できた．

SquirrelMail，TorrentFlux，XOOPS の五つのプログラ

r6 は数字と小文字のアルファベットを 32 回繰り返す

ムで使用されている正規表現である．なお，実験では文字列にマッチする．先行研究では線形と判定された

900s の制限時間を設定し，それを超えた場合はタイムア

が，本研究では時間内に計算が終わらずタイムアウトとウトとした．実験の結果，正規表現マッチングの計算量なった．これは先読み付き木トランスデューサの状態数

が入力文字列の長さに対して線形であると判定された正が 32，先読みオートマトンの状態数が 34 となり，準同′2

規表現は 338 個，Θ (n ) であると判定された正規表現は′

3

44 個，Θ (n ) であると判定された正規表現は 6 個，タ
イムアウトとなった正規表現は 5 個であった．実験結果の一部を表 1 に示す．また，非線形と判定された正規表
現に関しては，出力された反例を先読み付き木トランス
デューサで実行し，計算量を確認した．

型写像の数が 39168 と多くなってしまい，制限時間内に有限遷移系を構成できなかったためである．

7. 関連研究山口は，NFA よって最左優先一致を行う手法を正規表
現の微分とモナドを用いて形式的に表現し，それがバッ

r1 は / で区切られた 6 個の任意の文字列からなる文字

クトラックによる最左優先一致と結果が一致することを列にマッチする．この正規表現は先行研究でも線形であ示した [4]．本研究では，ここで示されている正規表現のるという結果が得られているが，判定にかかった計算時微分に関する考え方を用いて，木トランスデューサの遷間が先行研究では 757s なのに対し，本研究では 3.28s と移規則を構成している．

なり大幅に時間を短縮することができた．

Kirrage らは，正規表現マッチングの計算時間が指数関

r2 は content-transfer-encoding: の後，任意個の数的になるかどうかの判定を行う研究を行っている [2]．

空白が続き，その後 1 つ以下の - を含む任意の長さの英

彼らは正規表現マッチングを模倣する非決定性抽象機械字からなる文字列を含む文字列にマッチする．この正規を用いて判定を行った．この研究では，実際のバックト

表現は先行研究ではタイムアウトであったが，本研究でラックに基づく実装と同じように一つ目のマッチ成功まは線形であるという結果が得られた．

での正規表現マッチングに関しての計算時間を判定する

r3 は BAD か NO が含まれる文字列にマッチする．先行′

2

ことが目的であった．しかし，彼らは全探索をする正規研究では非線形と判定され，本研究では Θ (n ) と判定

表現マッチングに関しての計算時間の判定しか行えていされた．これは BAD も NO も含まれない文字列に対して

ない．

′

′

Θ (n) にならないと考えられ，Θ (n) の反例として文字列

Drewes は，木トランスデューサの出力木の大きさが入DDn DO が出力された．しかし，PCRE で反例の文字列

力木の大きさに対して指数関数的に増えるかどうかを線を実行した結果，n = 10, 000 のとき 0.71ms，n = 20, 000

形時間で判定を行っている [7]．この判定には，定理 4.1のとき 1.26ms，n = 40, 000 のとき 2.4ms となり，線形の反復補題が成り立つかどうかを検査するために導入しに近い結果となった．r3 は行頭の ^ がないため，.∗? (.∗)

た 5.3 節の有限遷移系に近い考え方が用いられている．

から始まることになる．PCRE ではこの部分で最適化が行われているため，このような結果になったと予想さ

8. 結論
本研究では，バックトラックに基づく正規表現マッチ

れる．

r4 は数字，a から h までの文字と記号 : からなる任意

ングの時間計算量を判定する新たな手法を提案した．正の文字列 2 つが :: によって繋がっている文字列にマッ規表現から先読み付き木トランスデューサを構成し，そチする．先行研究では線形と判定されていたが，本研究のサイズ増加率を決定することでオーダの判定を行った．

では Θ′ (n2 ) と判定された．また，Θ′ (n) の反例として

Aho と Ulman が示した定義や定理 [5] を基に，木トラ

n0 :: 0(:: 0) A0 が出力されている．PCRE で反例の文字

ンスデューサから状態列を取り出す準同型写像を用い，列を実行した結果，n = 100 のとき 0.49ms，n = 200 のその準同型写像から有限遷移系を構成した．構成した遷

2

とき 1.55ms，n = 400 のとき 5.8ms となり O(n ) に近移系を用いて初期状態から遷移したとき，反復補題が成いことが確認できた．

り立つ遷移過程が存在しているかどうかを調べることで

r5 は <image の後に任意の文字列が続き > で終わる文字列と </image> の間に任意の文字列を含む文字列にオーダを判定することができる．また，オーダが Θ′ (n2 )以上だった場合はその反例の文字列も出力できる．

6

2015-4-(9): 情報処理学会プログラミング研究会 発表資料 2016 年 1 月 14 日

表 1

実験結果

正規表現

計算量

判定にかかった計算時間

r1 = ^.*\/.*\/.*\/.*\/.*\/.*$

Θ′ (n)

3.28s

r2 = ^.*(content-transfer-encoding:)\s*(\w+-?(\w+)?).*

Θ′ (n)

129s

r3 = (.*)(BAD|NO)(.*)$

Θ′ (n2 )0.990sr4 = ^([0-9a-h\:]+)::([0-9a-h\:]+)$

Θ′ (n2 )0.145sr5 = <image.*?>(.*?)</image>Θ′ (n3 )8.10s

r6 = ^[0-9a-z]{32}$timeout

900s

構成したアルゴリズムを用いて，既存の PHP プロ
グラムで使用されている正規表現を対象にオーダの判定を行った．先行研究では非線形と判定されたものも，

Θ′ (n2 ) や Θ′ (n3 ) であることを判定することができた．
今後の課題として，実際のセキュリティツールを用いてテストを行うことが挙げられる．Kirrage ら [2] は，オープンソースの侵入防止システムである Snort[9] 等をテストに用いている．それらを用いるためには，正規表
現の構文解析のライブラリを構成し直す必要がある．
また，アルゴリズム自体のオーダを検査することも課
題として挙げられる．先読み付き木トランスデューサの構成では，先読みオートマトンを構成する際にサブセッ
ト構成をするため，オーダは指数関数的，その他のアルゴリズムでは多項式になると予想される．全体では指数関数的になると予想しているが，詳細を確認する必要が
ある．
参考文献
[1]

[2]

[3]

[4]
[5]

[6]

[7]

[8]

[9]

Sugiyama, S. and Minamide, Y.: Checking Time Linearity of Regular Expression Matching Based on Backtracking. IPSJ Transactions on Programming, Vol.7,
No.3, pp.1-11, 2014.
Kirrage, J., Rathnayake, A. and Thielecke, H.: Static
Analysis for Regular Expression Denial-of-Service Attacks. International Conference on Network and System Security(NSS 2013), pp.135-148, 2013.
Sakuma, Y., Minamide, Y. and Voronkov, A.: Translating Regular Expression Matching into Transducers, Journal of Applied Logic, Vol.10, No.1, pp.32-41,
2012.
山口 隆成: 正規表現の微分を用いた線形時間マッチン
グアルゴリズム，卒業研究論文, 2015.
Aho, A.V. and Ullman, J.D.: Translations on a context free grammar, Information and Control, Vol.19,
Issue 5, pp.453-456, 1971.
Engelfriet, J. and Maneth, S.: Macro Tree Translations of Linear Size Increase are MSO Definable,
SIAM J.Comput, Vol.32, pp.950-1006, 2003.
Drewes, F.: The complexity of the exponential output
size problem for top-down and bottom-up tree transducers, Information and Computation, 169, pp.264283, 2001.
OWASP.: Regular expression Denial of Service - ReDoS. https://www.owasp.org/index.php/Regular_
expression_Denial_of_Service_-_ReDoS, 2012.
Snort(IDS/IPS).: http://www.snotr.org/, 2012.

7