この記事は DeNA 21 新卒 Advent Calendar 2020 の24日目の記事です．メリークリスマス！
はじめに
今回は，ReDoS (Regular Expressions DoS)と呼ばれる，正規表現 (Regular Expression) のパターン処理の脆弱性を利用した攻撃 について説明します．
普段何気なく使う正規表現ですが，意外なところに落とし穴があります．
この記事を通して，正規表現の扱い方を考えるきっかけになればいいなと思います．
※ もちろん脆弱性を利用した攻撃をしてはダメです．
ReDoS攻撃とは
ReDoS攻撃は，正規表現のパターン評価に時間を要する文字列を入力することで，サーバーの計算リソースを奪う攻撃です．
まずはその攻撃の具体例を紹介します．
いま，/^(([a-zA-Z0-9])+)+$/という正規表現1を考え，その正規表現に対して幾つか文字列をテストさせてみましょう．
以下のスクリプトを用意します．
re = /^(([a-zA-Z0-9])+)+$/
str = ARGV[0] # Command line argument
start_time = Time.now
str.match(re) do |match|
puts match.to_s
end
p "running time: #{Time.now - start_time}[s]"
そして，幾つか文字列をテストさせてみます．
% ruby regex.rb abcde
abcde
"running time: 5.4e-05[s]"
% ruby regex.rb 01234567
01234567
"running time: 4.4e-05[s]"
% ruby regex.rb AbCdEfGh1JkLmN0pQR5Tu
AbCdEfGh1JkLmN0pQR5Tu
"running time: 3.3e-05[s]"
% ruby regex.rb AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
"running time: 0.000325[s]"
上記の例は全てテストはパスしており，とても短い時間でチェックが完了しています．
では次に，テストをあえてパスしないような文字列を入力してみます．
% ruby regex.rb AAAAAAAAAAAAAAAAAAAAAAAAAAAA@
"running time: 10.23256[s]"
比較的短い文字列にも関わらず，約10秒もテストに時間がかかっています．
もう少し長い文字列を入力してみましょう．
% ruby regex.rb AbCdEfGh1JkLmN0pQR5TuAbCdEfGh1Jk@
"running time: 177.567152[s]"
なんと，177秒もかかってしまいました．
このように，脆弱性を有する正規表現に対して文字列チェック(特にパターンにマッチしない文字列に対してのチェック)を行なった場合，パターン評価に時間を要し，計算リソースを奪ってしまいます．
これがReDoS攻撃です．
ReDoS攻撃の原理
パターンマッチの処理動作を可視化する
なぜReDoS攻撃が発生してしまうのでしょうか．
その原理について理解するため，正規表現のパターン処理がどのように行われているか可視化し，確認しましょう．
正規表現のパターン処理を可視化してくれるサイト(regular expressions 101)がありますので，今回はそちらを使って動作を確認してみます．
サイトにアクセスすると，以下のようなページが表示されます．
サイト中央の「REGULAR EXPRESSION」に正規表現を，「TEST STRING」にテストさせたい文字列を入力します．今回は，正規表現を /^(([a-zA-Z0-9])+)+$/とし，テスト文字列をAAAAAAAAAAAA@とします．そして，左下の「Regex Debugger」を押下します．
遷移したページ先で，再生ボタンを押下します．
すると，正規表現がどのように文字列のパターンを評価しているか，1ステップずつ確認することができます．
挙動を確認すると，
- 文字列先頭のAから終端の@に向かってステップが進む
- @までいったら少し戻る (この戻るステップを「バックトラック」といいます)
- また@まで進む
- 少し戻る
- また@まで進む
- ...
ということを繰り返しているのが分かると思います．
脆弱性を有する正規表現では，このバックトラックというステップが非常に多く発生します．しかも文字列の長さに対して，指数関数的にバックトラックが増えていきます．
これがReDoS攻撃の原因となっています．
パターンマッチの処理動作の詳細
なぜこのようにバックトラックが非常に発生するかについては，正規表現が内部的にどのようにして文字列を評価しているのか理解する必要があります．
詳しく理解するためには オートマトン言語理論 について理解する必要があります．ここではその知識がなくても何となく理解できるように，処理のイメージを説明します．しかし少々複雑な説明があるので，興味のない方は，この節を飛ばしてもらっても構いません(ReDoS攻撃は，バックトラックが大量に発生することによって生じるんだなあ，と思っていてください)．
先ほどの正規表現 /^(([a-zA-Z0-9])+)+$/ は少し複雑なので，ここからは /^a*a*b$/という正規表現を考えます2．
まず文字列を評価するために，正規表現/^a*a*b$/を以下のような状態遷移図(これを オートマトン といいます )に変換します3．
オートマトンには幾つかの状態ノードが存在しています．上記では，s, 3, 4, ..., 11, aの11個の状態ノードが存在しています．ノードsは初期状態と呼ばれるノードで，ノードaは受理状態と呼ばれるノードです．
またオートマトンには，ノード同士を結ぶ辺が存在しています．これは，辺の文字が入力されたら状態を移動できる，ということを表しています．例えば，状態4にいるときに文字aが入力された場合は，状態5に遷移することができます．またεという文字がありますが，これは「空列」を表し，文字を何も読まずに遷移できることを表します．例えば，状態3にいるときは，文字を何も読まずに6に移動することができます．
このオートマトンに対して，評価対象の文字列を入力します．
ここで初期状態sから，受理状態aに遷移することができれば，パターンマッチしていると認識します．
例えば，aabという文字を入力します．
すると，以下のように状態を遷移することができ，受理状態まで達します．つまり，aabという文字列は正規表現/^a*a*b$/にマッチしていると認識されます．
$$s \xrightarrow{\epsilon} 3 \xrightarrow{\epsilon} 4 \xrightarrow{a} 5 \xrightarrow{\epsilon} 6 \xrightarrow{\epsilon} 7 \xrightarrow{\epsilon} 8 \xrightarrow{a} 9 \xrightarrow{\epsilon} 10 \xrightarrow{b} 11 \xrightarrow{\epsilon} a$$
あるいは，以下のようにも状態を遷移することができます．
$$s \xrightarrow{\epsilon} 3 \xrightarrow{\epsilon} 6 \xrightarrow{\epsilon} 7 \xrightarrow{\epsilon} 8 \xrightarrow{a} 9 \xrightarrow{\epsilon} 8 \xrightarrow{a} 9 \xrightarrow{\epsilon} 10 \xrightarrow{b} 11 \xrightarrow{\epsilon} a $$
では次に，aaaという文字を入力してみます．
(これはどう頑張っても初期状態sから受理状態aに遷移することができません．つまり，aaaは正規表現/^a*a*b$/にマッチしていないと認識されます．)
この場合，内部的にどのようにパターンマッチの処理動作をしているのか説明します．
まず，とりあえず遷移できるところまで遷移します．例えば，
$$s \xrightarrow{\epsilon} 3 \xrightarrow{\epsilon} 4 \xrightarrow{a} 5 \xrightarrow{\epsilon} 6 \xrightarrow{\epsilon} 7 \xrightarrow{\epsilon} 8 \xrightarrow{a} 9 \xrightarrow{\epsilon} 10 $$
状態10までいくと，どこにも遷移できないことが分かります(3つのaのうち，2つのaは使ってしまったので，残りは1つのaのみです．しかし，状態10は文字bがないとどこにも遷移できません)．この場合，遷移した経路を逆戻りし，別の経路を試します(これがいわゆる「バックトラック」です)．
例えば，状態10から2つ前の状態8まで逆戻りし，次の経路を試します．
$$... 10 \xrightarrow{逆} 9 \xrightarrow{逆} 8 \xrightarrow{a} 9 \xrightarrow{\epsilon} 8 \xrightarrow{a} 9 \xrightarrow{\epsilon} 8 $$
またしても状態8で遷移できなくなってしまいました．なのでまたバックトラックし，別の経路を試します．
このバックトラックが繰り返されることによって，処理時間を膨大に費やしてしまうわけです．
脆弱な正規表現は，バックトラックが大量に発生してしまうようなオートマトンを生成します．これが原因でReDoS攻撃が可能になってしまいます．
ReDoS攻撃を防ぐ方法
では ReDoS攻撃 を防ぐにはどうすれば良いのでしょうか．
色々な文献を参考にしたところ4，以下の対策が有効そうです．
- 独自の正規表現を使用しない
独自で考えた正規表現は，セキュアであることが第三者から確認されていないため，脆弱性の温床となることが多いです．メールアドレスや電話番号，住所，URLなどのパターンチェックは，公式のライブラリを使用するようにしましょう．例えば validator.js などを参照すると良いでしょう．
-
*や+など，繰り返し表現はなるべく使わない
正規表現の脆弱性は，*や+など，非決定性を有する繰り返し表現が原因になっていることが多いです．
少々正規表現が長くなったとしても，繰り返し表現を使わずに済むのならば，なるべく使わないようにしましょう．
- 入力文字数を制限する
{n}という構文を使うことで，繰り返し回数を制限することができます．このようにして入力文字数を制限することで，ReDoS の脅威を軽減させることができます．
- ライブラリを最新にする
普段使っているライブラリでも，ReDoSの脅威を受ける場合があります．
ライブラリは常に最新にしておき，できるだけ脅威を軽減しておくようにしましょう．
- タイムアウトを設定する
脆弱性がある正規表現に対して，パターンマッチしない長い文字列を入力すると，いつまで経っても処理が終わらない場合があります．そうならないように，タイムアウトを設定しておきましょう．
最後に
ReDoS攻撃という，身近な正規表現の脆弱性を突いた攻撃について説明しました．
より詳細に理解したい方は，参考文献[1]を読むと良いです．
またオートマトン言語理論について深く学びたい方は，参考文献[7]を読むと良いです．
大学でオートマトン言語理論について学んでいたとき，「これっていつ使うんだろ・・・」と思ってたのですが，ReDoSの原理を知ったときに「こういうところに活かされてるんだ！」と感動したのを今でも覚えています．
宣伝
この記事を読んで「面白かった」「学びがあった」と思っていただけた方、よろしければ LGTM、Twitter や Facebook、はてなブックマークにてコメントをお願いします！
また DeNA 公式 Twitter アカウント @DeNAxTech では、 Blog 記事だけでなく色々な勉強会での登壇資料も発信しています。ぜひフォローして下さい！
Follow @DeNAxTech
参考文献
[1] Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers
[2] その正規表現の書き方で大丈夫？ ReDoS 攻撃の怖さと対策方法
[3] 正規表現の落とし穴（ReDoS - Regular Expressions DoS）
[4] アプリからファイアウォールにまで使われる正規表現を標的にした「ReDoS攻撃」とは？
[5] GoでシンプルなDFA型正規表現エンジンを実装した
[6] 正規表現（非決定性有限オートマトンの作成） （Pythonによるアルゴリズムとデータ構造）
[7] J. ホップクロフト (著), J. ウルマン (著), R. モトワニ (著), John E. Hopcroft (原著), Jeffrey D. Ullman (原著), Rajeev Motwani (原著), 野崎 昭弘 (翻訳), 町田 元 (翻訳), 高橋 正子 (翻訳), 山崎 秀記 (翻訳)「オートマトン言語理論 計算論I」, 2003年4月1日