ReDoS攻撃

指数関数的なバックトラッキング

最も深刻な問題は、正規表現マッチングのバックトラッキングで発生し、一部のパターンでは実行時間が入力文字列の長さに対して指数関数的になる^[8]。${\displaystyle n}$文字の文字列に対する実行時間は${\displaystyle O(2^{n})}$となる。これは、正規表現が以下の3つの特性を持つ場合に発生する。

• 正規表現が部分式に対して繰り返し（+、*）を適用している。
• 部分式が同じ入力に対して複数の方法でマッチングできるか、部分式がより長い可能性のある一致の接頭辞である入力文字列にマッチングできる。
• 繰り返される部分式の後に、その部分式がマッチングしないものにマッチングする式がある。

2つ目の条件は、以下の2つの例で説明するのがわかりやすい。

• (a|a)+$では、繰り返しが部分式a|aに適用されており、これは選択のどちらの側でもaにマッチングできる。
• (a+)*$では、繰り返しが部分式a+に適用されており、これはaやaaなどにマッチングできる。

これら両方の例では、文字列の末尾にマッチさせるために$を使用し、3つ目の条件を満たしたが、この目的のために別の文字を使用することも可能である。例えば、(a|aa)*cも同じ問題のある構造を持っている。

上記の3つの正規表現はすべて、${\displaystyle a...ax}$という形式の文字列に適用された場合に指数関数的な実行時間を示す。例えば、バックトラッキング式の式エンジンでaaaaaaaaaaaaaaaaaaaaaaaaxとマッチングさせようとすると、完了までにかなりの時間がかかり、xの前のaが1つ増えるごとに実行時間は約2倍になる。

指数関数的ではなく、多項式時間${\displaystyle O(n^{x})}$のバックトラッキングが発生することも可能である。これも十分に入力が長ければ問題を引き起こす可能性があるが、悪意のある入力が大きな影響を与えるためにはさらに長くなる必要があるため、この問題への注目度は低い。このようなパターンの例としては、入力が任意の長さの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サーバーに送信することができる^[9]。

線形時間（有限オートマトン）の実装

C++標準ライブラリの<regex>、C POSIXライブラリの<regex.h>^[23]、Boostのboost.regexなど、一部の正規表現ライブラリはReDoS攻撃に対する防御機能を組み込んでいない（バックトラッキングを使用するため、指数関数時間につながる）が、他の正規表現ライブラリは正規表現DoS攻撃を防ぐように設計されている。これは決定性有限オートマトンを使用して行われ、入力サイズに対して線形時間で実行される。

GoogleによるC++用のRE2ライブラリを使用した場合^[24]：

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クレートを使用した場合^[25]：

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プロパティをサポートしている^[26]。以下は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<>関数オブジェクトを提供し、コンパイル時に正規表現の構文解析を実行する^[27]。コンパイル時のパターンによってコンパイルがconstexpr評価のステップ制限を超えた場合、コンパイルに失敗する。この機能はC++標準ライブラリへの追加が提案されているが、現時点では含まれていない^[28]。

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を提供している^[29]。

Rustでは、コンパイル時正規表現は、コンパイル時の正規表現検証のためのさまざまなマクロを提供するlazy_regex、ctreg、regex-automataなどのサードパーティ製クレートによって実現できる^[30]。

C#には、System.Text.RegularExpressions.GeneratedRegexAttribute属性があり、これはpartialメソッドでのソース生成を通じて正規表現の実装を生成する^[31]。

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}");
    }
}

注釈

出典