正規表現が固まるのには理由があります。エンジンを100行で自作して、遅くなる仕組みを実測します。
前回: HTTPはただのテキストだった — サーバー自作 これは【番外編】です。 このサイトの本筋は roadmap.sh に沿った第0〜第8段階で、正規表現エンジンの自作はそこに載っていません。 読まなくても順路は繋がります。飛ばして構いません。 それでも書いているのは、grep・sed・awk・vimの使い方|サーバー上でログを調べるからずっと正規表現を使ってきたのに、中で何が起きているかを一度も見ていないからです。 この記事のコマンドは、すべて Ubuntu の中で打ちます。 Windows の PowerShell ではありません。
正規表現は、たぶんこのサイトで一番よく出てきた道具です。
grep の回でログを絞り込み、ESLint の設定で無視するファイルを指定し、フォームの検証でメールアドレスの形を確かめました。
それでも、正規表現は「呪文」のままだったはずです。
^[a-z]+@ を書いて、動いたら次へ行く。動かなかったら記号を足したり消したりする。中で何が起きているかは、一度も考えていません。
ここには実害があります。
中身を知らないまま書いた正規表現は、サーバーを止めます。
「止まる」は比喩ではありません。たった30文字の文字列で、CPUを100%使い切って十数秒返ってこなくなる正規表現が、ごく普通の書き方の中にあります。しかも構文エラーではないので、誰にも指摘されません。
この記事では、先にそれを実際に固めて見せます。 そのあと、正規表現エンジンを自分で作ります。
100行そこそこで作れます。 扱うのを 連結・|・* の3つに絞れば、必要なのは2つの部品だけです。
- 正規表現の文字列を、木にする(パーサ)
- 木を、状態と矢印の図にして動かす(オートマトン)
そして、作り終わった瞬間に、なぜ固まるのかが分かります。 理由を先に読んでも「ふーん」で終わります。自分で書いた100行と比べたときに、初めて意味が出ます。
対象レベル: 中級 / 区分: 必要に応じて読む
この記事でわかること
- 正規表現は呪文ではないこと。連結・選択・繰り返しの3つしか本質が無く、残りは全部その省略記法だということ
/(a+)+$/のような普通の見た目の正規表現が、30文字の入力で十数秒固まること(ReDoS)。そしてそれが構文エラーでも書き間違いでもないこと- 多くの言語の正規表現は「1本の道を試して、ダメなら戻る」(バックトラック) で動いていて、戻る回数が入力の長さに対して倍々に増えることがあるということ
- 状態を1つに決めずに、ありうる状態を全部同時に持って進めると、同じ入力が一瞬で終わること。速さの正体は最適化ではなくアルゴリズムの違いだということ
- それでも実務でバックトラック方式が使われている理由。後方参照と先読みは、状態集合方式では原理的に書けないこと
grepが巨大なログに対して速い理由が、道具の出来ではなく同じアルゴリズムの違いだということ
この記事でやること
/(a+)+$/に文字を1つずつ足しながら時間を測り、倍々に増えていくところを見る(自分のVMの中だけ)- 再帰下降パーサを書いて、
a*bを木にする - 木からNFA(状態と矢印)を作り、状態集合を同時に進める
matchを書いてmatch("a*b", "aaab")を動かす - 同じ木を使ってバックトラック版も書き、同じ入力で速度を並べて測る
- 入力長の制限・タイムアウト・
RegExpを使わない選択の3つを、実際に手を動かして確かめる
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| ReDoS | Regular expression Denial of Service。正規表現をわざと固まらせて、サーバーを止める攻撃のこと。特別な道具は要らず、長めの文字列を1本送るだけで成立します |
| パーサ | 文字列を読んで、意味のあるかたまりの木に組み立てるプログラム。「a*b は『aの0回以上の繰り返し』と『b』が繋がったもの」という形に直します |
| 再帰下降パーサ | パーサの作り方の1つ。文法の規則1つにつき関数を1つ書いて、お互いを呼び合わせる。今回はこれです |
| AST(抽象構文木) | パーサが作る木のこと。concat(連結)や star(繰り返し)といった箱が入れ子になったもの |
| オートマトン | 状態(丸)と、文字で進む矢印だけでできた図。正規表現の実行モデルそのものです |
| NFA | 非決定性有限オートマトン。「同じ文字で、行き先が2つ以上ある」ことを許すオートマトン。ここが今回の心臓です |
| バックトラック | 1つの道を選んで進み、行き止まりだったら分かれ道まで戻って別の道を試すやり方。JavaScript の RegExp はこれです |
| 状態集合 | 「いま、ありうる状態」を全部まとめて持つやり方。道を1つに決めないので、戻る必要がありません |
正規表現そのものの書き方は説明しません。
^$[a-z]+を「読んだことはある」程度で十分です。この記事は、書き方ではなく動き方の話です。
先に、固まるところを見る
理屈より先に、壊れるところを見ます。
作業場所を作ります。Node.js は入っている前提です。
v22.14.0
バージョンの数字は違って構いません。 v18 以降なら、この記事のコードはそのまま動きます。
ファイルを作ります。
const re = /(a+)+$/;
for (const n of [10, 20, 24, 26, 28, 30]) {
const input = "a".repeat(n) + "!";
const t0 = Date.now();
const result = re.test(input);
console.log("a を " + n + " 個 → " + result + " / " + (Date.now() - t0) + " ミリ秒");
}
やっていることは1行です。 a を並べた文字列の最後に ! を1つ付けて、/(a+)+$/ に当てているだけです。
(a+)は「aが1回以上」(a+)+は「それが1回以上」$は「ここが文字列の終わり」
! が最後にあるので、答えは必ず false です。読めば5秒で分かります。問題は、答えが出るまでの時間です。
a を 10 個 → false / 0 ミリ秒
a を 20 個 → false / 11 ミリ秒
a を 24 個 → false / 174 ミリ秒
a を 26 個 → false / 699 ミリ秒
a を 28 個 → false / 2915 ミリ秒
a を 30 個 → false / 14359 ミリ秒
数字を縦に見てください。
a の数 | 時間 | 前の行の何倍か |
|---|---|---|
| 24 | 174 ミリ秒 | — |
| 26 | 699 ミリ秒 | 約4倍 |
| 28 | 2915 ミリ秒 | 約4倍 |
| 30 | 14359 ミリ秒 | 約5倍 |
入力が2文字伸びるたびに、時間が4倍になっています。 a を2つ足すだけで4倍です。
この先を計算してみてください。
a の数 | かかる時間(この機械での見積もり) |
|---|---|
| 30 | 14秒 |
| 40 | 約4時間 |
| 50 | 約半年 |
| 60 | 人間の寿命より長い |
60文字の文字列です。 ツイート1つより短い。それを1本送りつけるだけで、サーバーのCPUを1つ、永久に占有できます。
これは自分のVMの中だけでやってください。 他人のサイトの入力欄に長い
aを打ち込むのは攻撃です。 相手のサーバーを止める行為で、日本では電子計算機損壊等業務妨害罪に当たりうるものです。「試したかっただけ」は通りません。 この記事の目的は逆側です。 「自分のサーバーが、これで止まる側かもしれない」を知るために測っています。
なぜ「Webサーバーが止まる」話になるのか
14秒 CPU を使う、だけなら「遅い」で済みます。 済まないのは、その間ほかのリクエストが1つも処理されないからです。
Node.js は1本のスレッドでイベントループを回しています。正規表現の実行中は、そのループが止まります。
見せます。
const re = /(a+)+$/;
for (const n of [10, 15, 20]) {
re.test("a".repeat(n) + "!");
}
let tick = 0;
const timer = setInterval(() => {
tick++;
console.log("生きています: " + tick);
}, 200);
setTimeout(() => {
console.log("--- ここから正規表現 ---");
const t0 = Date.now();
re.test("a".repeat(28) + "!");
console.log("--- 終わった: " + (Date.now() - t0) + " ミリ秒 ---");
clearInterval(timer);
}, 600);
0.2秒ごとに「生きています」と出すタイマーを回しながら、途中で正規表現を1回実行します。
生きています: 1
生きています: 2
--- ここから正規表現 ---
--- 終わった: 3370 ミリ秒 ---
3.37秒の間、タイマーが1回も動いていません。 本来なら16回出るはずの「生きています」が、0回です。
これが「サーバーが止まる」の中身です。 止まっているのは正規表現を実行しているリクエストだけではありません。同じプロセスが受けている全リクエストが止まります。ヘルスチェックも返せないので、ロードバランサから見ると「そのサーバーは死んでいる」ことになります。 実例があります。 2019年7月2日、Cloudflare が世界規模で27分間ダウンしました。原因は、WAFに追加されたたった1つの正規表現です。攻撃ですらなく、自分たちで書いたルールを自分たちのトラフィックに当てただけでした。
[スクリーンショット: 01_ReDoSで固まる.png] node redos.js の実行結果を撮ってください。a の数と、ミリ秒が倍々に増えている表全体が1画面に入るようにお願いします。
「なぜ止まるのか」は、いまは説明しません
ここで理由を書くこともできます。 でも、書いても身に付きません。
この記事の残りで正規表現エンジンを作ります。 作り終わったとき、上の表が「そりゃそうなるよね」に変わります。 そのときに戻ってきてください。
正規表現エンジンは、2つの部品でできている
先に全体像を渡します。
"a*b" ← 人が書いた文字列
│
│ ① パーサ(再帰下降)
↓
concat ← 木(AST)
├ star
│ └ char 'a'
└ char 'b'
│
│ ② Thompson構成
↓
(2)─a→(3) ← NFA(状態と矢印)
│ ↑___│
└─b→(1)→[受理]
│
│ ③ 状態集合を進める
↓
"aaab" → true
やることは3段階です。
| 段階 | 入力 | 出力 | やること |
|---|---|---|---|
| ① パース | 文字列 "a*b" | 木 | * がどこに掛かっているかを確定させる |
| ② 変換 | 木 | 状態と矢印 | 木を、機械が辿れる形に平らにする |
| ③ 実行 | 状態と矢印 + 入力文字列 | true / false | 1文字ずつ、状態を進める |
シェルを自作した回と、形はまったく同じです。 あちらは「読む → 分ける → 実行して待つ」でした。今回は「読む → 木にする → 状態を進める」です。 入力をそのまま実行しようとしない。必ず一度、構造に直してから動かす。 これは自作シェルでも、ビルドツールでも、データベースのクエリ実行計画でも同じ形です。
扱うものを、先に3つに絞る
正規表現には記号がたくさんあります。 + ? {2,5} [a-z] . \d ^ $ (?=...)。
このうち、本質は3つだけです。
- 連結 …
abと書く。aのあとにb - 選択 …
a|bと書く。aかb - 繰り返し …
a*と書く。aが0回以上
残りは全部、この3つの省略記法です。
a+(1回以上) →aa*a?(0回か1回) →(a|)(選択の右側を空にする)a{2,3}→aa(a|)[abc]→(a|b|c)
だから3つだけ作れば、正規表現エンジンとして完成しています。 残りは便利のための飾りです。
これに リテラル文字 と 括弧 を足して、今回作るのはこれだけです。
a b c ... 1文字そのまま
ab 連結
a|b 選択
a* 0回以上の繰り返し
(ab)* 括弧でまとめる
正規表現を木にする
最初の仕事は「* がどこに掛かっているか」を確定させることです。
ab* を見てください。これは (ab) の繰り返しではありません。 b だけの繰り返しです。
ab* → a のあとに、b が0回以上 ← 正しい
(ab) が0回以上 ← 間違い
文字列のままでは、この違いを表現できません。 だから木にします。
文法を先に書く
再帰下降パーサは、文法を書いてから、その規則1つにつき関数を1つ書きます。 順番はこれです。
alt := concat ( "|" concat )* ← 一番弱く結びつく
concat := star*
star := atom "*"*
atom := 文字 | "(" alt ")" ← 一番強く結びつく
「弱い順に外側」がすべてです。
ab|c*d を上から読むと、こうなります。
| 段階 | 見え方 |
|---|---|
alt | ab と c*d の選択 |
concat | ab は a と b の連結 / c*d は c* と d の連結 |
star | c* は c の繰り返し |
atom | a b c d は、ただの文字 |
| を一番外側に置いたから、ab|c*d が (ab)|(c*d) になります。 ここが逆だと a(b|c)*d みたいに読んでしまいます。
「掛かる強さ」を関数の呼び出し順で表す、というのが再帰下降パーサの発明です。 弱い演算子の関数が、強い演算子の関数を呼ぶ。 これだけで優先順位が決まります。計算式の
1 + 2 * 3を1 + (2 * 3)と読むのも、まったく同じ仕組みです。
書く
function parse(pattern) {
let pos = 0;
function peek() {
return pattern[pos];
}
function parseAlt() {
let node = parseConcat();
while (peek() === "|") {
pos++;
node = { type: "alt", left: node, right: parseConcat() };
}
return node;
}
function parseConcat() {
let node = null;
while (pos < pattern.length && peek() !== "|" && peek() !== ")") {
const right = parseStar();
node = node === null ? right : { type: "concat", left: node, right };
}
return node === null ? { type: "empty" } : node;
}
function parseStar() {
let node = parseAtom();
while (peek() === "*") {
pos++;
node = { type: "star", node };
}
return node;
}
function parseAtom() {
const ch = peek();
if (ch === "(") {
pos++;
const node = parseAlt();
if (peek() !== ")") throw new Error("閉じ括弧がありません");
pos++;
return node;
}
if (ch === "*") throw new Error("* の前に文字がありません");
pos++;
return { type: "char", value: ch };
}
const node = parseAlt();
if (pos !== pattern.length) throw new Error(pos + " 文字目の ) が余っています");
return node;
}
module.exports = { parse };
48行です。 1つずつ読みます。
| 部分 | 意味 |
|---|---|
let pos = 0; | いま何文字目を読んでいるか。 パーサの状態はこれ1つだけです |
peek() | いまの文字を、読み進めずに覗く。 末尾を越えたら undefined が返るので、比較が全部安全に外れます |
parseAlt() | concat を1つ読んで、そのあと縦棒(選択の記号)が続く限り読み足す |
parseConcat() | 縦棒か ) か末尾に当たるまで、star を読み続けて左から繋ぐ |
parseStar() | atom を1つ読んで、* が続く限り star で包む(a** も一応通ります) |
parseAtom() | ( なら中身を parseAlt で読み直して(=再帰)) を食べる。それ以外は1文字 |
node === null ? { type: "empty" } | 空を許す。 選択の右側が空のとき(a? を展開した形)や、空の正規表現 "" がここに来ます |
最後の if (pos !== pattern.length) | 全部読み切れなかったら、) が余っている |
parseAtomがparseAltを呼び返しているところが「再帰」下降です。(a|b)*cを読むと、parseAlt→parseConcat→parseStar→parseAtom→parseAltと、一周して戻ってきます。括弧の入れ子が何重になっても、コードは1行も増えません。
木を目で見る
木を印刷する道具を作ります。
const { parse } = require("./parse.js");
function show(node, indent) {
const pad = " ".repeat(indent);
if (node.type === "char") return pad + "char '" + node.value + "'\n";
if (node.type === "empty") return pad + "empty\n";
if (node.type === "star") return pad + "star\n" + show(node.node, indent + 2);
return pad + node.type + "\n" + show(node.left, indent + 2) + show(node.right, indent + 2);
}
process.stdout.write(show(parse(process.argv[2]), 0));
concat
star
char 'a'
char 'b'
star が a だけに掛かっていて、その隣に b が並んでいます。 さっきの「ab* は (ab) の繰り返しではない」が、目に見える形になりました。
もう1つ。
concat
star
alt
char 'a'
char 'b'
char 'c'
括弧は木の中に残っていません。 括弧は「まとまりを指定する記号」であって、まとまりが木で表現できた瞬間に役目を終えます。
確かめてください。
alt
concat
char 'a'
char 'b'
char 'c'
concat
char 'a'
alt
char 'b'
char 'c'
同じ4文字なのに、木の形が違います。 これが「| は弱い」の正体です。
壊れる入力も試します。
Error: 閉じ括弧がありません
Error: 1 文字目の ) が余っています
Error: * の前に文字がありません
エラーで落ちるのが正解です。 ブラウザの new RegExp("(a") も SyntaxError を投げます。同じことを自分で書いただけです。
[スクリーンショット: 02_木になる.png] node tree.js "a*b" と node tree.js "(a|b)*c" を続けて実行し、2つの木が並んでいる画面を撮ってください。
木をオートマトンに変えて、動かす
木ができました。次は、これを機械が辿れる形にします。
状態と矢印だけの世界
正規表現の実行は、こういう図の上を歩くことです。
a
┌───┐
↓ │
→(2)──────┘
│
│ b
↓
(1) ──→ [受理]
これが a*b です。丸が「状態」、矢印が「1文字読んで進む」を表します。
- 開始は
(2) aを読むと(2)に戻ってこられる(=何回でもaを読める)bを読むと(1)に進み、受理に着く- 文字を読み終わったときに受理にいれば
true
「行き先が2つある」を許す
ここが肝です。 (2) にいるとき、次に来る文字が a なら a の矢印へ、b なら b の矢印へ進めばいい。それは簡単です。
問題は、(a|b)* のような場合です。 同じ場所から、文字を読まずに2つの道に分かれる必要があります。
これを表すのが「分岐状態」です。 文字を消費せず、両方の行き先を持つだけの状態を置きます。
| 状態の種類 | 持つもの | やること |
|---|---|---|
char | 文字1つと、次の状態 | その文字が来たら、次に進む |
split | 次の状態を2つ | 文字を読まずに、両方に分かれる |
match | なし | ここに着いていたら成功 |
この3種類だけです。 正規表現がどれだけ複雑でも、この3つの組み合わせで表せます。
これを「NFA」と呼びます。 非決定性有限オートマトン。名前は怖いですが、中身は「行き先が2つあってもいい矢印の図」でしかありません。 「非決定性」は「どっちに行くか決まっていない」という意味です。決まっていないなら、両方行けばいい。それが後半でやることです。
木からNFAを作る(Thompson構成)
木の各ノードを、上の3種類に機械的に置き換えます。 1971年に Ken Thompson が示した方法で、Thompson構成と呼ばれます。
書き方のコツが1つあります。 「このノードが終わったあとに、どこへ行くか」を引数で渡すことです。
build(ノード, 次に行く状態) → このノードの入口の状態
この形にすると、繋ぎ合わせが自動になります。
| ノード | 作るもの |
|---|---|
char 'a' | a を読んだら next へ進む状態を1つ作って返す |
concat(左, 右) | 右を先に作る。その入口を、左の next にして左を作る |
alt(左, 右) | 左と右を両方作って、両方に分かれる split を1つ被せる |
star(中身) | split を1つ置く。 片方は中身へ、中身の出口はその split に戻す。もう片方は next |
empty | 何も作らず、next をそのまま返す |
star の「出口を自分に戻す」がループです。 図の a の矢印が (2) に戻っていたのは、これです。
const { parse } = require("./parse.js");
function compile(pattern) {
const states = [];
function add(state) {
states.push(state);
return states.length - 1;
}
function build(node, next) {
if (node.type === "empty") return next;
if (node.type === "char") return add({ type: "char", char: node.value, next });
if (node.type === "concat") return build(node.left, build(node.right, next));
if (node.type === "alt") {
return add({ type: "split", next1: build(node.left, next), next2: build(node.right, next) });
}
if (node.type === "star") {
const s = add({ type: "split", next1: -1, next2: next });
states[s].next1 = build(node.node, s);
return s;
}
throw new Error("不明なノード: " + node.type);
}
const matchState = add({ type: "match" });
const start = build(parse(pattern), matchState);
return { states, start, matchState };
}
module.exports = { compile };
30行です。 見どころは2つだけです。
| 行 | 意味 |
|---|---|
build(node.left, build(node.right, next)) | 連結。 右を先に作って、その入口を左の行き先にする。内側から外へ組み立てるので、この1行で済みます |
const s = add({ ... next1: -1 ... }); states[s].next1 = build(node.node, s); | 繰り返し。 先に split を置いてから、中身を作る。中身の行き先に自分自身の番号 s を渡すので、ループが閉じます。-1 は「まだ決まっていない」の仮置きです |
starだけ2行に分かれているのは、循環を作るからです。 「中身を作る」ためには「中身の行き先」が要り、「中身の行き先」は「まだ作っていないsplit自身」です。鶏と卵なので、先に箱だけ確保して、あとから中身を書き込みます。
できたものを見ます。
start = 2
0 {"type":"match"}
1 {"type":"char","char":"b","next":0}
2 {"type":"split","next1":3,"next2":1}
3 {"type":"char","char":"a","next":2}
4つの状態で a*b の全部です。
2から始まる。splitなので、文字を読まずに3と1に分かれる3は「aを読んだら2へ戻る」 ← これがループ1は「bを読んだら0へ」0は受理
さっきの図と同じものが、配列4つになりました。
状態集合を、同時に進める
残りは実行です。 ここがこの記事で一番大事な30行です。
普通に考えると、こう書きたくなります。
splitに来た。左に行こう。ダメだったら戻ってきて右に行こう。
それがバックトラックで、ReDoS の原因そのものです。 今回はやりません。
やるのはこれです。
splitに来た。左にも右にも行く。「いま自分がいるかもしれない状態」を全部リストに入れておく。 1文字読むたびに、リストの全員を1歩ずつ進める。
"aaab" を a*b に食わせる
読む前: いる場所 = { 3, 1 } ← 2 は split なので、その先の 3 と 1 に散る
'a' → : いる場所 = { 3, 1 } ← 3 だけが a で進める。行き先 2 がまた散る
'a' → : いる場所 = { 3, 1 }
'a' → : いる場所 = { 3, 1 }
'b' → : いる場所 = { 0 } ← 1 だけが b で進める
終わり: 0(受理)が入っている → true
「戻る」が1回も出てきません。 前に進むだけです。
nfa.js に追記します。
function addState(states, list, seen, i) {
if (seen.has(i)) return;
seen.add(i);
const st = states[i];
if (st.type === "split") {
addState(states, list, seen, st.next1);
addState(states, list, seen, st.next2);
return;
}
list.push(i);
}
function match(pattern, input) {
const { states, start, matchState } = compile(pattern);
let current = [];
addState(states, current, new Set(), start);
for (const ch of input) {
const next = [];
const seen = new Set();
for (const i of current) {
const st = states[i];
if (st.type === "char" && st.char === ch) {
addState(states, next, seen, st.next);
}
}
current = next;
}
return current.includes(matchState);
}
module.exports = { compile, match, addState };
module.exports の行は、さっき書いたものを上書きしてください。
| 部分 | 意味 |
|---|---|
addState | split を辿り尽くして、char と match だけをリストに入れる。 「文字を読まずに行ける場所」を全部展開する係 |
if (seen.has(i)) return; | これが無いと無限ループします。 (a*)* のように「1文字も読まずにループに戻れる」形があるので、同じ状態は1回しか展開しないと決めます |
for (const ch of input) | 入力を1文字ずつ、1回だけ舐める。 ここが戻らない証拠です |
if (st.char === ch) | その文字で進める状態だけを次のリストに入れる |
current.includes(matchState) | 読み終わったときに受理がリストにいれば成功 |
seenの Set が、この記事の全部と言ってもいい行です。 「同じ状態を2回展開しない」=「同じ探索を2回やらない」。バックトラック方式が持っていないのが、まさにこれです。
動かす
nfa.js の末尾にテストを足します。
if (require.main === module) {
const tests = [
["a*b", "aaab", true],
["a*b", "b", true],
["a*b", "aaa", false],
["a*b", "aabb", false],
["ab|c", "ab", true],
["ab|c", "c", true],
["ab|c", "a", false],
["(a|b)*c", "abbac", true],
["(a|b)*c", "abbad", false],
["(ab)*", "ababab", true],
["(ab)*", "aba", false],
["", "", true],
["a", "", false],
["(a*)*b", "aaab", true],
["(a*)*b", "aaa", false],
];
for (const [p, s, want] of tests) {
const got = match(p, s);
console.log((got === want ? "ok " : "NG ") + JSON.stringify(p) + " vs " + JSON.stringify(s) + " -> " + got);
}
}
ok "a*b" vs "aaab" -> true
ok "a*b" vs "b" -> true
ok "a*b" vs "aaa" -> false
ok "a*b" vs "aabb" -> false
ok "ab|c" vs "ab" -> true
ok "ab|c" vs "c" -> true
ok "ab|c" vs "a" -> false
ok "(a|b)*c" vs "abbac" -> true
ok "(a|b)*c" vs "abbad" -> false
ok "(ab)*" vs "ababab" -> true
ok "(ab)*" vs "aba" -> false
ok "" vs "" -> true
ok "a" vs "" -> false
ok "(a*)*b" vs "aaab" -> true
ok "(a*)*b" vs "aaa" -> false
match("a*b", "aaab") が動きました。 正規表現エンジンです。
パーサ48行 + NFA 30行 + 実行30行 = 108行。これで正規表現エンジンの本体は完成しています。
""と""がtrueで、"a"と""がfalseになっているところを見てください。 空の正規表現も、空の入力も、特別扱いを1行も書いていないのに正しく動きます。emptyが「nextをそのまま返す」だけで済んでいるからです。構造が正しいと、端の場合が勝手に合う、というのはこの手のプログラムでよく起きます。
[スクリーンショット: 03_自作エンジンが動く.png] node nfa.js の実行結果を撮ってください。15行すべてが ok になっているところが写るようにお願いします。
今回作ったのは「完全一致」です。
match("a*b", "xaaab")はfalseになります。grepのような部分一致にしたければ、パターンの前後に.*を付けるのと同じことを、開始状態を毎文字リストに入れ直すだけで実現できます。今回はやりません。
ここで、なぜ ReDoS が起きるのかが分かる
準備が整いました。冒頭の14秒に戻ります。
同じ木で、バックトラック版も書く
比較するには、両方が要ります。 パーサは共通で使えるので、実行方法だけを差し替えます。
const { parse } = require("./parse.js");
function walk(node, s, i, k) {
if (node.type === "empty") return k(i);
if (node.type === "char") return i < s.length && s[i] === node.value && k(i + 1);
if (node.type === "concat") return walk(node.left, s, i, (j) => walk(node.right, s, j, k));
if (node.type === "alt") return walk(node.left, s, i, k) || walk(node.right, s, i, k);
if (node.type === "star") {
const more = (j) => walk(node.node, s, j, (j2) => (j2 > j ? more(j2) : false)) || k(j);
return more(i);
}
throw new Error("不明なノード");
}
function matchBacktrack(pattern, input) {
const tree = parse(pattern);
return walk(tree, input, 0, (i) => i === input.length);
}
module.exports = { matchBacktrack };
19行です。 k は「このノードが終わったあとにやること」を持った関数です。
注目するのはこの2行です。
if (node.type === "alt") return walk(node.left, s, i, k) || walk(node.right, s, i, k);
|| です。 左を最後まで試して、false が返ってきたら右を試す。 これが「戻る」の正体です。
const more = (j) => walk(node.node, s, j, (j2) => (j2 > j ? more(j2) : false)) || k(j);
繰り返しも同じ || です。 できるだけ多く繰り返してみて、ダメだったら1回減らして試し直す。 これが「貪欲マッチ」と呼ばれるものの中身です。
動くことを確かめます。
true false true
答えは自作NFA版とまったく同じです。 正しさは変わりません。変わるのは時間だけです。
並べて測る
冒頭の /(a+)+$/ を、今回の3つの記号だけで書き直します。
a+はaa*(a+)+は(aa*)(aa*)*- 今回のエンジンは完全一致なので、
$は要りません(最後まで読み切ることが条件)
手を抜いて (aa*)* で十分です。 これでも「入れ子になった繰り返し」という性質は同じです。
const { match } = require("./nfa.js");
const { matchBacktrack } = require("./backtrack.js");
console.log("=== バックトラック版 ===");
for (const n of [16, 20, 22, 24, 26]) {
const input = "a".repeat(n) + "!";
const t0 = Date.now();
const r = matchBacktrack("(aa*)*", input);
console.log("a が " + n + " 個 → " + r + " / " + (Date.now() - t0) + " ミリ秒");
}
console.log("=== 状態集合版(自作NFA) ===");
for (const n of [26, 30, 100, 1000, 100000]) {
const input = "a".repeat(n) + "!";
const t0 = Date.now();
const r = match("(aa*)*", input);
console.log("a が " + n + " 個 → " + r + " / " + (Date.now() - t0) + " ミリ秒");
}
=== バックトラック版 ===
a が 16 個 → false / 16 ミリ秒
a が 20 個 → false / 127 ミリ秒
a が 22 個 → false / 403 ミリ秒
a が 24 個 → false / 1493 ミリ秒
a が 26 個 → false / 6455 ミリ秒
=== 状態集合版(自作NFA) ===
a が 26 個 → false / 0 ミリ秒
a が 30 個 → false / 0 ミリ秒
a が 100 個 → false / 0 ミリ秒
a が 1000 個 → false / 2 ミリ秒
a が 100000 個 → false / 35 ミリ秒
同じ機械、同じ言語、同じパーサ、同じ木、同じ答えです。
a の数 | バックトラック版 | 状態集合版 |
|---|---|---|
| 26 | 6455 ミリ秒 | 0 ミリ秒 |
| 30 | (数十秒) | 0 ミリ秒 |
| 100000 | (宇宙が終わる) | 35 ミリ秒 |
10万文字が35ミリ秒です。 26文字で6.4秒かかっていたものと、同じことをやっています。
[スクリーンショット: 04_速度の差.png] node bench.js の実行結果を撮ってください。上下2つのブロックが1画面に入って、桁が違うことが分かるようにお願いします。
なぜ、こうなるのか
(aa*)* に aaaa! を食わせるところを、手で追ってみてください。
外側の * が何回回るか、内側の a* が何文字取るか。aaaa の分け方は、これだけあります。
(a)(a)(a)(a)
(aa)(a)(a)
(a)(aa)(a)
(a)(a)(aa)
(aa)(aa)
(aaa)(a)
(a)(aaa)
(aaaa)
8通り。 これは 4 個を区切る位置が3箇所あって、それぞれ「切る/切らない」の2通りだからです。
aが n 個なら、分け方は 2 の (n-1) 乗 通りです。
a の数 | 分け方の数 |
|---|---|
| 10 | 512 |
| 20 | 524288 |
| 26 | 3300万 |
| 30 | 5億3千万 |
| 50 | 562兆 |
そして最後に ! があるので、全部が失敗します。 バックトラック方式は「失敗したら次の分け方を試す」ので、false を返すために、全部の分け方を試し切ります。
! が無ければ一瞬で終わります。 最初の分け方で成功して、そこで止まるからです。
ReDoS の入力が必ず「最後に1文字だけ違うものを付ける」形なのは、これが理由です。 成功させないことが攻撃です。「マッチしません」と答えるまでに、全パターンを踏ませます。
状態集合版が0ミリ秒なのは、分け方を1つも数えないからです。
「
aを3文字読んだ状態」は、どういう分け方で来たかに関係なく、同じ1つの状態です。 バックトラック版は、その3300万通りの道を別々のものとして辿り直します。状態集合版は、同じ場所に着いた道をまとめて1つにします。seenの Set がやっていたのは、これです。
だから状態集合版の計算量は、こうなります。
入力の長さ × 状態の数
掛け算です。 倍々ではありません。状態の数はパターンの長さで決まる固定値なので、入力が10倍になれば10倍、それだけです。
確かめられます。
状態の総数: 5
同時に生きた状態の最大数: 3
1000文字を食わせても、同時に持っている状態は最大3個です。 バックトラック版が数えていた「分け方」は、この3個に全部畳み込まれています。
表にまとめる
| バックトラック方式 | 状態集合方式 | |
|---|---|---|
| 進み方 | 1本の道を最後まで試し、行き止まりなら分かれ道まで戻る | ありうる状態を全部同時に持ち、1文字で全員を進める |
| 「戻る」 | ある | 無い。入力を1回舐めるだけ |
| 最悪の計算量 | 入力の長さに対して指数関数的 | 入力の長さ × 状態数(線形) |
26文字の (aa*)* | 6.4秒 | 0ミリ秒 |
後方参照 (a)\1 | 書ける | 原理的に書けない |
先読み (?=...) | 書ける | 素直には書けない |
| キャプチャの位置 | 自然に取れる | 別の仕組みが要る |
| 採用例 | JavaScript, Python, Java, Ruby, PCRE(PHP・nginx など) | RE2, Go の regexp, Rust の regex, GNU grep |
それでも、実務ではバックトラック方式が使われている
「じゃあ全部 RE2 にすればいい」とはなりません。 正直に書きます。
状態集合方式には、書けないものがあります。
① 後方参照が書けません。
(\w+) \1 ← 「同じ単語が2回続く」
\1 は「1番目の括弧が実際にマッチした文字列と、同じもの」という意味です。
これは有限オートマトンでは表現できません。 「さっき何にマッチしたか」を覚えるには、状態の数が入力の長さに応じて無限に増える必要があるからです。性能の問題ではなく、この計算モデルの外側にあるということです。
後方参照を持った正規表現は、もはや「正規」表現ではありません。 数学でいう正規表現(regular expression)は、有限オートマトンで表せるものの別名です。後方参照はそこから出ています。名前だけが残って、中身が広がったというのが実情です。
② 先読み・後読みが書けません。
foo(?=bar) ← 後ろが bar である foo にだけマッチ
「進むけど、消費しない」という動きは、素直な状態集合方式には入りません。
③ キャプチャの位置を取るのが難しくなります。
String.replace で $1 を使えるのは、どこからどこまでが1番目の括弧だったかを覚えているからです。状態集合方式では、全部の道をまとめてしまっているので、どの道で来たかが消えます。 取ろうとすると、実装が急に複雑になります。
この3つは、実務でよく使われます。 だから JavaScript も Python も Java も、便利さを取ってバックトラック方式を選んでいます。 そして、その代償として ReDoS を抱えています。
「間違った選択をしている」わけではありません。 トレードオフです。 知らずに使うと事故になる、というだけです。だから次の節があります。
どう守るか — セキュリティの回の回収
セキュリティの回で「安全にはできない、被害を小さくする」と書きました。 ReDoS もまったく同じです。
「安全な正規表現の書き方」を暗記するのは筋が悪いです。人間の目視で見抜くのは難しく、(a|a)* のような分かりやすい形以外にも、いくらでもあります。
効く順に4つです。
① 入力の長さを制限する(一番効く)
指数関数は、指数が小さければ怖くありません。
if (typeof s !== "string" || s.length > 200) {
return res.status(400).json({ error: "長すぎます" });
}
26文字で6秒かかるものも、上限が200文字なら… と思うかもしれませんが、それでも足りません。 200文字だと 2^199 です。
現実的にはこうします。
| 入力 | 妥当な上限 |
|---|---|
| メールアドレス | 254文字(RFC の上限) |
| ユーザー名 | 32文字 |
| 検索キーワード | 100文字 |
| URL | 2048文字 |
そのうえで、上限の長さで実際に測ってください。 「上限を決めた」だけでは不十分で、上限いっぱいの最悪ケースが何ミリ秒かを知っている必要があります。
これはレートリミットや WAF では防げません。 1リクエストで成立するので、「たくさん来たら止める」タイプの防御をすり抜けます。正規表現を実行する直前で、長さを見るのが唯一確実です。
② 危険な形を書かない
危ないのは、ほぼ1つの形です。
繰り返しの中に、繰り返しが入っている。 そして同じ文字を2つの経路が食い合える。
(a+)+— 内も外も繰り返し。直すならa+(a*)*— 同上。直すならa*(a|a)*— どちらの枝も同じaを食える。 直すならa*(\w+\s*)+—\wと\sは重ならないが、+の入れ子。直すなら[\w\s]+.*.*=.*—.*同士が同じ文字を取り合う。直すなら分割してindexOf
最後の .*.*=.* が、Cloudflare を止めた形です。
機械にも見つけさせられます。ただし、過信はできません。
/(a+)+$/ → false
/^[a-z]+@[a-z]+$/ → true
/(a|a)*/ → true
/.*.*=.*/ → true
false が「危ない」です。 (a+)+ は拾えました。
でも (a|a)* と .*.*=.* は「安全」と言われています。 どちらも危ない形で、.*.*=.* は Cloudflare を止めた本人です。
これは道具の不出来ではありません。 「この正規表現は最悪どれだけ時間がかかるか」を完全に判定するのは非常に難しく、どの検査ツールも見逃しと誤検知を持ちます。 だから、①の入力長制限が一番効くのです。検査は「明らかな地雷を早めに拾う」ためのもので、通ったから安全、にはなりません。
npm auditで ReDoS の警告が出るのも、これです。 セキュリティの回でnpm auditを流したとき、"Inefficient Regular Expression Complexity" という種類の警告があったはずです。あれは全部この話です。自分のコードだけでなく、依存パッケージの中の正規表現も同じリスクを持ちます。
③ タイムアウトを掛ける
JavaScript の RegExp には、タイムアウトの引数がありません。 そして実行中は誰も止められません。
だから、別のスレッドに追い出します。
const { Worker, isMainThread, workerData, parentPort } = require("worker_threads");
if (!isMainThread) {
parentPort.postMessage(/(a+)+$/.test(workerData));
} else {
const worker = new Worker(__filename, { workerData: "a".repeat(30) + "!" });
const timer = setTimeout(() => {
console.log("時間切れ。打ち切りました");
worker.terminate();
}, 1000);
worker.on("message", (r) => {
clearTimeout(timer);
console.log("結果: " + r);
});
}
時間切れ。打ち切りました
1秒で諦めて、メインは生きています。 さっきの freeze.js と違い、タイマーが動き続けているのが違いです。
これは最後の手段です。 ワーカーを立てる分だけ重くなりますし、攻撃者はワーカーを次々枯渇させられます。 ①と②をやったうえでの保険と考えてください。
④ そもそも RegExp を使わない
「正規表現で書くべき」と思い込んでいるだけ、という場合がかなりあります。
| やりたいこと | 正規表現 | 正規表現なしで |
|---|---|---|
| 前方一致 | /^abc/ | s.startsWith("abc") |
| 含む | /abc/ | s.includes("abc") |
| 後方一致 | /abc$/ | s.endsWith("abc") |
| カンマで分ける | /,/ で split | s.split(",") |
| 数字だけか | /^\d+$/ | [...s].every((c) => c >= "0" && c <= "9") |
どれもバックトラックしません。 そして読みやすいです。
メールアドレスの検証も、ほとんどの場合はこれで足ります。
const at = s.indexOf("@");
const ok = at > 0 && at === s.lastIndexOf("@") && at < s.length - 1;
「正しいメールアドレスかどうか」を正規表現で完全に判定することはできません。 RFC に準拠した正規表現は6000文字を超えます。そして書けたところで、存在しないアドレスは弾けません。 確認メールを送るのが唯一の検証です。形の検証は「打ち間違いに気づかせる」ためのもので、厳しくする意味がありません。
どうしても複雑な正規表現が必要で、しかも外部入力に当てるなら、バックトラックしない実装を使います。
| 言語 | 選択肢 |
|---|---|
| Node.js | re2 パッケージ(RE2 のバインディング) |
| Go | 標準の regexp が最初から RE2 |
| Rust | regex クレートが最初から線形時間保証 |
| .NET | RegexOptions.NonBacktracking |
| Java | タイムアウト無し。自前で切るしかない |
Go と Rust で「後方参照が使えない」と言われるのは、これが理由です。 機能が足りないのではなく、「最悪でも線形時間」を守るために意図的に外しているという設計判断です。
grep が速い理由 — テキスト処理の回の回収
grep・sed・awk の回で、巨大なログファイルを grep で絞り込みました。 あのとき、速さを疑わなかったはずです。
GNU grep は、基本的にバックトラックしません。
確かめます。
100002 big.txt
real 0m0.040s
user 0m0.000s
sys 0m0.031s
10万文字です。 JavaScript の RegExp なら、30文字で14秒でした。grep は一瞬で「無い」と答えます。
理由は、いま自分で書いたものと同じです。
GNU grep は、パターンを DFA(決定性有限オートマトン)に変換して、入力を1回舐めるだけで判定します。
DFA は、今回作った「状態集合」を先に全部計算しておいたものです。「{3, 1} という集合」を1つの新しい状態として名前を付けてしまえば、実行時には集合の計算すら要らなくなります。
| 今回作ったもの | GNU grep | |
|---|---|---|
| 状態集合 | 実行しながら毎回作る(NFAシミュレーション) | 先に全部作っておく(DFA) |
| 速さ | 入力長 × 状態数 | 入力長のみ |
| メモリ | 少ない | 状態の組み合わせ分だけ増える(必要になった分だけ作る工夫がある) |
grepが「後方参照を使うと急に遅くなる」のは、この話の裏返しです。grep -E "(a)\1"のように DFA で扱えないものを書くと、バックトラックする実装に切り替わります。 速さは道具の出来ではなく、どの計算モデルで動いているかで決まります。
同じ道具が、書き方によって別のエンジンで動く。 これを知っているかどうかが、「なんとなく速い/遅い」と「どこが効いているか分かる」の差です。パフォーマンスの回でやった「速くする前に測る」も、測ったあとに何を読むかが要るという意味では、まったく同じ話です。
作らなかったもの
108行で作れたのは、あくまで骨です。 実物との差を、正直に数えます。
| 作らなかったもの | 例 | どのくらいの仕事か |
|---|---|---|
| 文字クラス | [a-z] [^0-9] \d \w . | 難しくない。 char 状態を「1文字を受け取って true/false を返す関数」に変えるだけ |
| 量指定子 | a+ a? a{2,5} | 難しくない。 パーサで木に展開すれば、NFA側は変更なし |
| アンカー | ^ $ | 今回は完全一致固定。部分一致にするなら、開始状態を毎回入れ直す |
| キャプチャ | (...) の中身を取り出す | 難しい。 状態集合方式では、どの道で来たかが消えている |
| 後方参照 | \1 | 原理的に不可能。 別の仕組みが要る |
| 先読み・後読み | (?=...) (?<=...) | 素直には入らない |
| 最短一致 | *? | キャプチャと同じ問題 |
| Unicode | 絵文字、結合文字、\p{...} | for (const ch of input) はコードポイント単位なので、絵文字はまだましだが、家族絵文字のような結合は1文字にならない |
| 最適化 | DFA化、先頭文字の絞り込み | 速さを詰めるなら、ここから |
上の3つは、この記事の続きとして自然にできます。 下の3つは、設計を変える必要があります。
「100行で作れる」は、「100行で本物になる」ではありません。 V8 の正規表現エンジン(Irregexp)は、正規表現を機械語にコンパイルします。 そこには何万行もの最適化が入っています。それでも、
(a+)+で固まります。 最適化の量ではなく、選んだアルゴリズムが決めているからです。
つまずいたところ
| 症状 | 原因 |
|---|---|
node redos.js が返ってこない | 仕様どおりです。 Ctrl + C で止めてください。n を28以上にすると数十秒〜数分かかります |
redos.js の最初の1〜2行だけ、やたら遅い | JITが温まっていないため。 小さい n から回すと、途中から本来の速さになります。倍々の傾きだけを見てください |
match が無限ループして返ってこない | addState の seen チェックを書き忘れている。 (a*)* のような形で、文字を読まずにループへ戻り続けます |
括弧の中の選択が alt にならず、後ろ半分が消える | parseConcat の peek() !== ")" を書き忘れている。 括弧を閉じられずに読み進んでしまいます |
ab* が (ab) の繰り返しになる | parseStar を parseConcat の外側で呼んでいる。 * は直前の1つに掛かるので、parseConcat の中で1回ずつ呼びます |
star を作ると next1 が -1 のまま | build の戻り値を代入し忘れている。 states[s].next1 = build(node.node, s); の左辺が必要です |
TypeError: Cannot read properties of undefined | peek() が undefined を返している場所で .length などを呼んでいる。 比較(===)だけにしてください |
backtrack.js が RangeError: Maximum call stack size exceeded | 長い入力で再帰が深くなりすぎた。 バックトラック方式の弱点そのものです。入力を短くしてください |
bench.js のバックトラック版で n を28にしたら戻らない | 仕様どおり。 Ctrl + C で止めて、26以下にしてください |
grep の time の数字が記事とかなり違う | 問題ありません。 桁(0.0秒台)が合っていれば十分です。14秒との差を見るのが目的です |
npm install safe-regex が失敗する | ネットワークが必要です。 切り分けの4段階を確認してください。この節は飛ばしても記事は成立します |
node -e の中の $ が消える | シェルが変数として展開しています。 記事のとおり \$ と書くか、nano でファイルに書いて実行してください |
もう一段、目で追いたいときは、状態リストを毎回印刷すると分かります。
開始 : [3,1]
'a' を読む: [3,1]
'a' を読む: [3,1]
'a' を読む: [3,1]
'b' を読む: [0]
受理? : true
リストの中身が、増えも減りもしていません。 これが「戻らない」の見た目です。
後片づけ
常駐したものは何もありません。 ファイルを消すだけです。
npx で入ったものが気になるときは、キャッシュを消します。
nodeそのものは消さないでください。 この先ずっと使います。redos.jsを実行したまま忘れていないかだけ、確認しておきます。
自分の grep 以外に node が出てこなければ大丈夫です。 残っていたら kill します(プロセスの回)。
まとめ
- 正規表現は呪文ではない。 本質は連結・選択・繰り返しの3つだけで、
+?{n,m}[a-z]は全部その省略記法 - エンジンは2つの部品でできている。 ①文字列を木にするパーサ ②木を状態と矢印に変えて動かすオートマトン。合わせて108行
- 再帰下降パーサは「弱い演算子の関数が、強い演算子の関数を呼ぶ」だけ。
|を一番外側に置いたからab|cが(ab)|cになる - 括弧は木の中に残らない。 まとまりが木で表現できた瞬間に、括弧の役目は終わる
- NFAの状態は3種類しかない。
char(文字で進む)・split(文字を読まずに2つに分かれる)・match(受理) splitに来たとき、どちらか選んで進み、ダメなら戻るのがバックトラック。両方に行って、ありうる状態を全部持つのが状態集合方式/(a+)+$/に30文字を食わせると14秒固まった。 文字が2つ増えるたびに4倍。60文字で人間の寿命を超える- 止まるのはそのリクエストだけではない。 Node.js は1本のスレッドなので、プロセス全体が止まる(3.4秒間、タイマーが1回も動かなかった)
- 理由は「分け方を全部試すから」。
aが n 個なら2^(n-1)通り。最後に!を付けるのは、成功させずに全部試させるため - 状態集合方式が速いのは、最適化ではなくアルゴリズム。 同じ場所に着いた道をまとめるので、1000文字食わせても同時に持つ状態は3個だった
- 同じ機械・同じ言語・同じパーサ・同じ木で、26文字が6455ミリ秒と0ミリ秒に分かれた。 違うのは実行方法だけ
- それでもバックトラック方式が使われている。 後方参照は有限オートマトンでは原理的に表せない。先読みとキャプチャも同じ理由で難しい。トレードオフであって、間違いではない
- 守り方は、効く順に「入力長の制限」「入れ子の繰り返しを書かない」「別スレッドでタイムアウト」「
RegExpを使わない」 startsWithincludessplitで足りることがかなり多い。 バックトラックしないうえ、読みやすいgrepが速いのは道具の出来ではない。 DFA に変換して入力を1回舐めているから。後方参照を書くと、grep も遅くなる- V8 は正規表現を機械語にコンパイルする。それでも
(a+)+で固まる。 最適化の量ではなく、選んだアルゴリズムが上限を決めている
参考リンク
- roadmap.sh — Computer Science
- Regular Expression Matching Can Be Simple And Fast — Russ Cox
- OWASP — Regular expression Denial of Service
- Cloudflare の2019年7月2日の障害の詳細
- MDN — 正規表現ガイド
- Node.js — worker_threads
- GNU grep 公式マニュアル
- Ubuntu manpages — grep
- RE2
- Rust の regex クレート
次に読む
この記事は 【番外編】roadmap.sh の外 の 29 / 35 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | HTTPはただのテキストだった — サーバー自作 |
| → 次の記事 | インタプリタを自作する演習 — 字句解析と構文解析から実行まで |
ここは番外編です。 本筋から外れているので、飛ばして構いません。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
【番外編】既にあるものを自作して仕組みを知る回。roadmap.sh の範囲外。

コメント