Tweet

Pocket

Webシステム開発に限らず、正規表現を業務で利用した事がある人は一定数居ると思う。
比較的よく利用されるのは指定の形式で値が入力されたかチェックするバリデーションなどだろうか。
ただし、その正規表現が脆弱性になりえるという認識をもって利用している人はどの程度いるものだろうか。

今回は ReDoS という正規表現を利用した攻撃手法について ほんの少し だけ掘り下げてみた。
どうしてほんの少しなのかと言うと解釈エンジンの考え方に数学的知識が追い付かなかったためだ。

どのような攻撃手法なのか？

サービス運用妨害と分類される攻撃手法で（正規表現 Re gular Expression）を解釈するクライアントやサーバへの DoS（Denial of Service）攻撃の事だ。
一部の正規表現解釈方式で膨大な量のバックトラック（探索処理の一つ）が発生して処理がオーバーフローした状況を指す。

具体的には

以下の正規表現はJavaScriptで脆弱性があるという事になる。（連続した空白文字のイメージ）

/\s+$/

参考：正規表現の脆弱性 (ReDoS) を JavaScript で学ぶ

攻撃があった例

2016年6月、StackOverflowがReDoSによって34分間ダウン

• 文字列の末尾の空白を取り除く非常に単純な正規表現が原因

2019年7月、CloudflareがReDoSによって27分間ダウン

• WAF（Webアプリケーションファイアウォール）に設定された正規表現が原因

発生する主な条件

以下の2点が発生に大きく起因するので覚えておきたい。

1. 正規表現の解釈方式（概ね開発言語が呼び出すライブラリに依存）
2. 組み合わせ数と入力の長さ

正規表現の解釈方式

解釈の方法について詳細を理解するにはオートマトンという状態遷移の概念から理解する必要があるが語れる自信が無いので割愛する。
主に以下の二つが存在しDFA型ではReDoSは発生しないとのこと。

• DFA型
  • 正規表現を決定性有限オートマトン(DFA)に変換してマッチングを行う
  • バックトラックを行わないため後方参照など複雑な正規表現は利用できない
  • GNU grep、Google/RE2などで採用パターン
• VM型
  • バイトコードに変換（組み合わせが爆発しないようにうまく最適化）してマッチングを行う
  • JavaやRubyやPerlやJavaScriptなどで採用

組み合わせ数と入力の長さ

100文字程度でも組み合わせ数によっては数秒かかる。
組み合わせ数は量指定子（ {n,m} ）の組み方に依存する。

※簡略標記を量指定子と同義で呼ぶ場合もある。

ReDoSの発生を抑制するには

• 正規表現を利用しないように仕様を再検討する
  • 実は正規表現を利用しなくて済む場合も多い
• 入力値が短くなるように仕様を再検討する
  • バリデーション処理の順序などで調整出来る場合も多い
• DFA型のエンジン（Google/RE2など）を利用する
  • 大概はシンプルな条件なのでライブラリが使えるならこちらを選択する
• 正規表現の解釈に関わるライブラリの最新化
  • ReDoSが発生する不具合が入っているバージョンを使わない
• 組み合わせが爆発しないように正規表現を組む
  • 量指定子同士や量指定子とor条件（ | 、 [] ）の組み合わせを少なくする
  • 正規表現デバッガツールなどで正規表現をチェックし修正する
• マッチ処理をタイムアウトする
  • 処理時間を有限にしてリソースが枯渇しないようにする

結局どうするのがよい？

まずは正規表現が本当に必要か仕様を再検討するのが確実だ。
正規表現が必要であれば他にどの対策を取るかをシステム要件にしたがって検討する。

最後に

各言語に当然のように存在する正規表現には複数の解釈方式があり、それが利用の仕方により脆弱性に繋がるという事を覚えておいていただきたい。

参考

• 正規表現の脆弱性「ReDoS」徹底解説
• 20日目: 正規表現が ReDoS 脆弱になる 3 つの経験則

Tweet

Pocket