ReDoS とは、正規表現が遅くなる仕組みとオートマトン

後戻りは、なぜ爆発するのか

(a+)+$ のように、くり返しの中にくり返しがあると、同じ字の並びを何通りにも分けられます。a が 4 つでも「4」「3 と 1」「2 と 2」「1 と 1 と 2」のように分け方がいくつもあり、最後の b で合わないと分かるまで、後戻り型のエンジンはその分け方を全部試します。

次のコードは、(a+)+$ を後戻り型で試す小さな照合器です。re と同じく先頭から合わせ、字を 1 つ見るたびに steps を 1 足します。出力は左から、a の数、合うか、見た字の数、2 の n+1 乗 − 1 の値です。

4 False 31 31
8 False 511 511
12 False 8191 8191
13 False 16383 16383
16 False 131071 131071
合う (True, 16)

a が 4 つで 31 回、16 個で 131071 回で、どれも 2 の n+1 乗 − 1 と同じでした。12 個から 13 個へ 1 字増やすと 8191 回から 16383 回へ、ほぼ 2 倍です。a だけの 16 字は 16 回で合い、遅いのは合わない入力だけです。

同じ並びを状態の機械で読みます。この入力では、(a+)+$ が受け入れるのは「a が 1 つ以上並んだもの」なので、矢印は S から A、A から A の 2 本で足ります。

4 False 5
8 False 9
12 False 13
13 False 14
16 False 17
合う (True, 16)

状態の機械は、a が 16 個と b を 17 回で読み切り、字が 1 つ増えても回数は 1 増えるだけです。同じ「合わない」という答えに、後戻り型は 131071 回、状態の機械は 17 回かかりました。爆発の原因は正規表現という考え方ではなく、分かれ道を 1 本ずつ試す動き方にあります。

本物の re でも同じことが起きます。次は手元の Python 3.14 で測った秒数で、頁の中では動かしません (ブラウザが固まるため)。

re.match(r"(a+)+$", "a"*n + "b")
n=18  0.008 秒
n=20  0.035 秒
n=22  0.215 秒
n=24  0.742 秒

a が 2 つ増えるごとに時間が数倍に伸びました。yamory のブログも、^(([a-zA-Z0-9])+)+$ で 1 字増えるごとに約 2 倍の時間がかかったと書いています。

危ない形は、次の 2 つにまとめられます。

• くり返しの入れ子 (a+)+、(a+)*、(x\w{1,10})+y。内と外のどちらで字を取るかを選べる
• 重なる選択肢のくり返し (.|\s)*。空白はどちらの枝でも取れる

直し方

直し方の第一は、同じ字を何通りにも分けられない式に書き直すことです。(a+)+$ が言いたいのは「a が 1 つ以上で終わる」なので、a+$ で足ります。

書き直せないときは、後戻りを禁じる書き方を使います。原子グループ (?>...) は、いったん抜けたら中へ戻らない組で、所有の量指定子 a++ は、取った字を返さない + です。Python の re では、どちらも 3.11 から使えます。

aaaa oooo
aaab xxxx
b xxxx
a+$ None
(?>a+)+$ None
(a++)+$ None

短い入力では、元の式と直した 3 つの式の答えがそろいました。直した式は、a が 30 個と b でもすぐに None (合わない) を返します。元の式には、頁が固まるのでこの入力を渡していません。

式の外でも守ります。

RE2 は、信頼できない利用者の式でも危なくないことを目標に作られ、照合の時間が入力の長さに比例することを約束しています。そのために、後戻りでしか作れない後方参照などの機能を持ちません。利用者が式そのものを渡せるサービスでは、式の書き直しを頼めないので、こうした後戻りしないエンジンを選ぶのが根本の守りです。