ReDoS攻撃（ReDos attack）もしくは、正規表現DoS攻撃（せいきひょうげんドスこうげき）とは、評価に時間のかかる正規表現（regex）や入力を与えることでDoS攻撃（サービス拒否攻撃）を引き起こすアルゴリズム的計算量攻撃である。この攻撃は、多くの正規表現の実装が超線形的な最悪計算量を持つという事実を悪用している。特定の正規表現と入力の組み合わせにおいて、実行時間は入力サイズに対して多項式時間または指数関数時間で増加する。したがって、攻撃者は特別に細工した正規表現や入力を提供することで、プログラムに膨大な時間を費やさせることができる。その結果、プログラムは遅延するか応答不能になる。
概要
正規表現のマッチングは、有限オートマトンを構築することで実行できる。正規表現は非決定性有限オートマトン（NFA）へ簡単に変換できる。NFAでは、各状態と入力記号に対して、複数の次の状態が存在しうる。オートマトンを構築した後の処理には、いくつかの可能性が存在する。
エンジンがそれを決定性有限オートマトン（DFA）に変換し、その結果に入力を通す。 一致が見つかるか、すべてのパスを試して失敗するまで、エンジンが可能なすべてのパスを1つずつ試す（バックトラッキング）。 エンジンが非決定性オートマトン上のすべての可能なパスを並列に処理する。 エンジンが非決定性オートマトンをDFAに遅延評価で（つまり、マッチングの実行中にオンザフライで）変換する。
上記アルゴリズムのうち、最初の2つには問題がある。1つ目の方法は、決定性オートマトンが最大で（は非決定性オートマトンの状態数）の状態を持つ可能性があるため、NFAからDFAへの変換に指数関数時間がかかる可能性がある点で問題である。2つ目の方法は、非決定性オートマトンが長さの入力に対して指数関数的な数のパスを持つ可能性があるため、入力の探索にも指数関数時間がかかる点で問題である。一方で、残りの2つのアルゴリズムはこのような病的な挙動を示さない。
病的な挙動を示さない正規表現の場合、問題のあるアルゴリズムは通常高速であり、実際には正規表現をの時間で「コンパイル」し、の時間でマッチングできると期待できる。その代わり、NFAのシミュレーションとDFAの遅延計算は、最悪計算量がとなる。正規表現DoS攻撃は、これらの期待がユーザーから提供された正規表現に適用され、悪意のある正規表現がマッチャーの最悪計算量を引き起こす場合に発生する。
正規表現アルゴリズムは効率的に記述できるが、既存のほとんどの正規表現エンジンは、常に効率的に解決できるとは限らない追加の構文で正規表現言語を拡張している。このような拡張パターンは、ほとんどのプログラミング言語における正規表現の実装において、本質的にバックトラッキングの使用を強制している。
例
指数関数的なバックトラッキング
最も深刻な問題は、正規表現マッチングのバックトラッキングで発生し、一部のパターンでは実行時間が入力文字列の長さに対して指数関数的になる。文字の文字列に対する実行時間はとなる。これは、正規表現が以下の3つの特性を持つ場合に発生する。
正規表現が部分式に対して繰り返し（+、*）を適用している。 部分式が同じ入力に対して複数の方法でマッチングできるか、部分式がより長い可能性のある一致の接頭辞である入力文字列にマッチングできる。 繰り返される部分式の後に、その部分式がマッチングしないものにマッチングする式がある。
2つ目の条件は、以下の2つの例で説明するのがわかりやすい。
(a|a)+$では、繰り返しが部分式a|aに適用されており、これは選択のどちらの側でもaにマッチングできる。 (a+)*$では、繰り返しが部分式a+に適用されており、これはaやaaなどにマッチングできる。
これら両方の例では、文字列の末尾にマッチさせるために$を使用し、3つ目の条件を満たしたが、この目的のために別の文字を使用することも可能である。例えば、(a|aa)*cも同じ問題のある構造を持っている。
上記の3つの正規表現はすべて、という形式の文字列に適用された場合に指数関数的な実行時間を示す。例えば、バックトラッキング式の式エンジンでaaaaaaaaaaaaaaaaaaaaaaaaxとマッチングさせようとすると、完了までにかなりの時間がかかり、xの前のaが1つ増えるごとに実行時間は約2倍になる。
指数関数的ではなく、多項式時間のバックトラッキングが発生することも可能である。これも十分に入力が長ければ問題を引き起こす可能性があるが、悪意のある入力が大きな影響を与えるためにはさらに長くなる必要があるため、この問題への注目度は低い。このようなパターンの例としては、入力が任意の長さのaの連続である場合のa*b?a*cが挙げられる。
オンラインリポジトリの脆弱な正規表現
いわゆる「悪意のある」または脆弱な正規表現が、オンラインの正規表現リポジトリで見つかっている。全体の正規表現を攻撃するには、脆弱な部分式を1つ見つけるだけで十分であることに注意が必要である。
1. RegExLib、id=1757（電子メールの検証） - 下線の部分を参照。 ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$ 2. OWASP Validation Regex Repository、Javaクラス名 - 下線の部分を参照。 ^(([a-z])+.)+[A-Z]([a-z])+$
これら2つの例は、aaaaaaaaaaaaaaaaaaaaaaaa!という入力に対しても影響を受けやすい。
攻撃手法
検索パターンをクライアントに提供させるWebサービスなど、正規表現自体がユーザー入力の影響を受ける場合、攻撃者は悪意のある正規表現を注入してサーバーのリソースを消費させることができる。したがって、ほとんどの場合、ユーザーがサーバー上で任意のパターンを実行できないようにすることで、正規表現DoS攻撃を回避できる。このケースでは、Webアプリケーションやデータベースが主に脆弱なアプリケーションとなる。あるいは、悪意のあるページがユーザーのWebブラウザをフリーズさせたり、任意の量のメモリを消費させたりする可能性もある。
しかし、脆弱な正規表現がすでにサーバー側に存在する場合、攻撃者は最悪の挙動を引き起こす入力を提供できる可能性がある。このケースでは、電子メールスキャナや侵入検知システムも脆弱になる可能性がある。
Webアプリケーションの場合、プログラマはシステムのクライアント側とサーバー側の両方で入力を検証するために同じ正規表現を使用することがある。攻撃者はクライアントのコードを検査して悪意のある正規表現を探し、サーバーをフリーズさせるために細工された入力を直接Webサーバーに送信することができる。
緩和策
ReDoSは、信頼できない入力が関与する場合に正規表現の実行に時間制限（タイムアウト）を設定するだけで、正規表現エンジンを変更することなく緩和できる。
脆弱性のない正規表現の実装を使用することで、ReDoSを完全に回避できる。2019年にCloudflareのWebアプリケーションファイアウォール（WAF）がPCREのReDoSによってダウンした後、同社はWAFを書き直し、RE2に似たアルゴリズムを使用するバックトラッキングを行わないRustの正規表現ライブラリを採用した。
脆弱な正規表現は、Lintによってプログラム的に検出できる。その手法は、純粋な静的解析からファジングまで多岐にわたる。ほとんどの場合、問題のある正規表現は「悪意のない」パターンに書き換えることができる。例えば、(.*a)+は([^a]*a)+に書き換えることができる。式の一部でバックトラッキングを無効にする所有格マッチング（Possessive matching）やアトミックグループ化（Atomic grouping）も、脆弱な部分を無効化するために使用できる。
線形時間（有限オートマトン）の実装
C++標準ライブラリの<regex>、C POSIXライブラリの<regex.h>、Boostのboost.regexなど、一部の正規表現ライブラリはReDoS攻撃に対する防御機能を組み込んでいない（バックトラッキングを使用するため、指数関数時間につながる）が、他の正規表現ライブラリは正規表現DoS攻撃を防ぐように設計されている。これは決定性有限オートマトンを使用して行われ、入力サイズに対して線形時間で実行される。
GoogleによるC++用のRE2ライブラリを使用した場合： import <re2/re2.h>; import std;
using std::string_view; using re2::RE2;
constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"; constexpr string_view PATTERN = "^(a+)+$";
int main(int argc, char* argv[]) { bool isMatch = RE2::FullMatch(TEXT, PATTERN); std::println("Match result: {}", isMatch); } Rust用のregexクレートを使用した場合： use regex::Regex;
const TEXT: &str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"; const PATTERN: &str = r"^(a+)+$";
fn main() { // Regex::new() returns Result<Regex, Error> and must be unwrapped match Regex::new(PATTERN) { Ok(re) => { let is_match: bool = re.is_match(TEXT); println!("Match result: {}", is_match);
Err(err) => { eprintln!("Failed to unwrap regex: {}", err);
正規表現マッチングのタイムアウト
タイムアウトを使用して、時間がかかりすぎる正規表現タスクをキャンセルすることができる。ただし、これを安全に行う唯一の方法は、正規表現自体がタイムアウトのしきい値を超えたかどうかをチェックすることである。そうでない場合、ストップトークン（協調的なスレッド割り込みを使用する）は正規表現によってブロックされ、孤立したFutureとPromiseやスレッドは単にリークし、OSのAPIを通じてスレッドを直接強制終了すると破損やデッドロックを引き起こす可能性がある。しかし、それを子プロセスとして分離し、しきい値を超えた場合にプロセスを終了させることは安全である。
タイムアウトは.NET標準ライブラリに組み込まれており、System.Text.RegularExpressions.RegexクラスはMatchTimeoutプロパティをサポートしている。以下はC#での例である。
namespace Wikipedia.Examples;
using System; using System.Text.RegularExpressions;
public class Example { private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"; private const string Pattern = @"^(a+)+$";
static void Main(string[] args)
try
Regex re = new(Pattern, RegexOptions.None, TimeSpan.FromMilliseconds(100)); bool isMatch = re.IsMatch(Text); Console.WriteLine($"Match result: {isMatch}");
catch (RegexMatchTimeoutException ex)
Console.WriteLine($"Regex operation timed out! {ex.Message}");
コンパイル時正規表現
コンパイル時正規表現とは、構文解析と検証をコンパイル時に移行し、実行時のオーバーヘッドを排除する正規表現のことである。ただし、コンパイル時正規表現は、コンパイル時にパターンを提供できる場合にのみ有用である。
Hana DusíkováによるC++のコンパイル時正規表現（ctre）ライブラリは、ctre::match<>関数オブジェクトを提供し、コンパイル時に正規表現の構文解析を実行する。コンパイル時のパターンによってコンパイルがconstexpr評価のステップ制限を超えた場合、コンパイルに失敗する。この機能はC++標準ライブラリへの追加が提案されているが、現時点では含まれていない。
import std; import ctre;
using std::string_view;
constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
int main(int argc, char* argv[]) { // ctre::match<> is a ctre::regex_results<> type // matching logic is done at compile-time when marked constexpr constexpr bool isMatch = ctre::match<"^(a+)+$">(TEXT); std::println("Match result: {}", isMatch); }
Dプログラミング言語は、コンパイル時正規表現であるstd.regex.ctRegexを提供している。
Rustでは、コンパイル時正規表現は、コンパイル時の正規表現検証のためのさまざまなマクロを提供するlazy_regex、ctreg、regex-automataなどのサードパーティ製クレートによって実現できる。
C#には、System.Text.RegularExpressions.GeneratedRegexAttribute属性があり、これはpartialメソッドでのソース生成を通じて正規表現の実装を生成する。
namespace Wikipedia.Examples;
using System; using System.Text.RegularExpressions;
public partial class Example { [GeneratedRegex(@"^(a+)+$")] private static partial Regex Pattern();
private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!";
static void Main(string[] args)
// IsMatch() logic happens at runtime bool isMatch = Pattern().IsMatch(Text); Console.WriteLine($"Match result: {isMatch}");
脚注
注釈
出典
関連項目 DoS攻撃 Billion laughs - XMLパーサーに対する類似の攻撃 ビジービーバー - 終了するまでに可能な限り最大の出力を生成するプログラム メールボム Fork爆弾 オンラインアルゴリズム - 宣言されるのではなく発見される制限 Zip爆弾 時限爆弾 サイバー戦争 Low Orbit Ion Cannon High Orbit Ion Cannon
外部リンク
オープンソースアプリケーションにおけるReDoSの例: DataVaultのReDoS (CVE-2009-3277) EntLibのReDoS (CVE-2009-3275) NASD CORE.NET TerelikのReDoS (CVE-2009-3276) ReDoSに関するいくつかのベンチマーク Achim Hoffman (2010). "ReDoS - benchmark for regular expression DoS in JavaScript". 取得日: 2010-04-19. Richard M. Smith (2010). "Regular expression denial of service (ReDoS) attack test results". 取得日: 2010-04-19.