yamory Blog

その正規表現の書き方で大丈夫? ReDoS 攻撃の怖さと対策方法

ReDoS とは、Regular expression Denial of Service の略称で脆弱な正規表現を利用することで起こる DoS のひとつです。

正規表現は利用者からの入力値の検証など色々な場面で利用されていますが、正規表現の記述は難しく、誤った記述をしてしまうと ReDoS の影響を受ける恐れがあります。

本記事では ReDoS の概要から対策方法まで解説していきます。

ReDoS とは

メールアドレスや電話番号の入力が正しい形式になっているかどうかを確認するために正規表現を使うことがあると思います。
複雑な形式をマッチさせる正規表現を正しく書くことは難しく、書き方によっては処理に時間がかかることがあります。

ReDoS は、正規表現が使われている部分において、正規表現エンジンに対して処理時間が多くかかる入力を与えることでサービス停止が起こる脆弱性です。

Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers で書かれているように、人気のある npm のライブラリで多くの ReDoS の脆弱性が指摘され、実際のウェブサイトでも脆弱性が発見されています。

特に、Node.js ではイベントループがシングルスレッドのため ReDoS によってイベントループがブロックされると他の利用者にまで影響が出る恐れがあります。

ReDoS を引き起こす正規表現

具体的に良くない正規表現の記述例を紹介したいと思います。

正規表現を使って大文字 / 小文字 / 数字のみの連続になっているか判定する正規表現を以下のように書いたとします。

/^(([a-zA-Z0-9])+)+$/

この正規表現にいくつか入力を与えて実行時間を確認してみます。
ますは、正規表現にマッチする入力で実行時間を計測します。

input: abcdefghij
実行時間: 0.056s
input: abcdefghijklmnopqrstuvwxyz
実行時間: 0.065s
input: abcdefghijklmnopqrstuvwxyzABC
実行時間: 0.083s

正規表現にマッチする入力では文字数を多くしてもあまり実行時間に影響が出ません。
今度は、正規表現にマッチしない入力で実行時間を計測します。

input: abcdefghij@
実行時間: 0.061s
input: abcdefghijklmnopqrstuvwxyz@
実行時間: 6.388s
input: abcdefghijklmnopqrstuvwxyzA@
実行時間: 12.523s
input: abcdefghijklmnopqrstuvwxyzAB@
実行時間: 23.683s
input: abcdefghijklmnopqrstuvwxyzABC@
実行時間: 48.311s

マッチしない場合では文字数が長くなると実行時間が大幅に増加します。
今回の正規表現の場合は 1 文字増加毎に約 2 倍の時間が掛かっています。

これは、@ 前までマッチしたが @ がマッチしなかったため、再度ひとつ戻って評価するといった再帰的なバックトラックが発生しているために多くの時間が掛かっているためです。

ライブラリに含まれる ReDoSの脆弱性

上記のような独自に正規表現を記述した場合以外にも、利用しているライブラリに ReDoS の脆弱性が含まれていることがあります。

例えば、npm の中でもよく使われるユーティリティライブラリの Lodash に ReDoS の脆弱性が過去に発見され、CVE-2019-1010266 として公開されています。

この脆弱性では、50,000 文字が入力された場合に約 2 秒マッチングに時間がかかると Issue で書かれています。

大量な文字列が lodash で扱われるケースはほぼない、あったとしても特定できるため問題ないと思われるかもしれませんが、lodash は多くの場面で利用され、また別のライブラリからも利用されることが多いため場当たり的な対応では漏れる可能性があります。

このように自分たちが導入したライブラリが利用しているライブラリを推移的(間接)依存ライブラリと呼び、この推移的依存ライブラリに含まれる脆弱性によって影響を受けるリスクがあることも注意しなければいけません。

ReDoS の対策方法

では ReDoS を引き起こさないようにするためにはどうすれば良いのでしょうか。

独自の正規表現を避ける

メールアドレス、電話番号、URL の形式が正しいかどうかなど一般的な入力の確認の場合は validator.js のようなライブラリを利用し、独自の正規表現を避けることをおすすめします。

正規表現をチェックする

独自の正規表現を書かなくてはいけない場合には複雑な正規表現を利用しないように心がけましょう。
特に"+"演算子のような、繰り返しマッチするか確認する正規表現を記述する際には注意が必要です。

正規表現が ReDoS の影響を受けるかどうか safe-regex などのツールを使って簡易的にチェックすることもできます。

先ほどの具体例であげた正規表現も safe-regex を使うことで確認することができます。

$ node safe.js '/^(([a-zA-Z0-9])+)+$/'
false

以下のように書き換えた場合には ReDoS の影響が軽減されたことも確認できます。

$ node safe.js '/^[a-zA-Z0-9]+$/'
true

ツールによる確認はあくまで簡易的なものです。
全ての ReDoS の影響を受ける正規表現の確認ができるわけではないことに注意しましょう。

入力文字数を制限する

上記の対策に加えて正規表現への入力文字数を制限することで ReDoS の脅威を軽減させることができます。
しかし、文字数に応じて指数関数的に処理数が増加する場合には少ない文字数でも影響が出るため、入力文字数の制限はあくまで軽減策として考える必要があります。

最新のライブラリを利用する

自分たちで正規表現を利用していない場合でも ReDoS の影響を受ける可能性があります。

上記でも書きましたが人気のある npm のライブラリでも ReDoS の脆弱性を含んでいることがありますので、常に自分たちが利用している OSS の脆弱性を把握し、ReDoS を含めて対応が必要な場合には適切にアップデートをすることが大切です。

また自分たちが直接利用していない推移的依存ライブラリに含まれる脆弱性も確認する必要があります。

推移的依存ライブラリを含めて脆弱性管理を行う場合には管理するライブラリの数がとても多くなります。
工数削減のためにも脆弱性管理ツールの利用を検討するのもよいでしょう。

さいごに

正規表現は多くの場面で利用され、とても便利な機能ではありますが、正しく記述することはとても難しいものです。
誤った書き方をしてしまうと ReDoS の影響を受けることがありますので独自の正規表現を避ける、入力文字数を制限する、チェックツールを使うなど組み合わせて対策する必要があります。
自分たちが正規表現を記述していない場合でも影響を受けることがあり、利用しているライブラリにReDoSの脆弱性がないか確認することも大切です。

yamory では、ライブラリに含まれるReDoSを含む脆弱性のチェックをすることができます。
セキュアなシステム構築の助けになるかと思いますので、ぜひ一度お試しください。

オープンソース脆弱性管理ツール yamory

  • 利用中のOSSを抽出し
    脆弱性を自動スキャン
  • 脆弱性への対応優先度を自動で分類
  • 組織規模に合わせたプランを選択可能

フリー

¥0

個人向け

1チームまでの開発チーム作成

yamory を使いはじめる

プロ

有料料金はお問い合わせください

中〜大規模組織向け

無制限の開発チーム作成

開発チームを俯瞰できるセキュリティチーム機能

危険な脆弱性の Slack 連携通知機能

Jira Cloud と連携

シングル・サインオン(SSO)連携*

* SSO 連携は無料トライアルではご利用できません。プロプラン契約後からご利用できます。

30日間の無料トライアルを開始