正規表現におけるカタストロフィックバックトラッキングを回避する方法

API7.ai

December 17, 2020

Technology

正規表現のカタストロフィックバックトラッキングとは、正規表現がマッチングする際に過剰にバックトラッキングを行い、CPU使用率が100%に達し、通常のサービスをブロックしてしまう現象を指します。

背景

私は、正規表現のバックトラッキングが100% CPUを引き起こす問題の発見と解決プロセスを詳細に説明した記事を読みました。元の記事はかなり長いですが、私は以前にOpenRestyの開発中に同様の問題に2回遭遇しました。

ここでは、背景を理解するために時間をかけなくても済むように簡単にまとめます。

  1. ほとんどの開発言語の正規表現エンジンは、バックトラッキングベースのNFA（ThompsonのNFAベースではない）を使用して実装されています。
  2. バックトラッキングが多すぎると、100% CPUのカタストロフィックバックトラッキングが発生します。
  3. オンライン環境で問題を特定するには、gdbやsystemtapを使用してダンプを分析する必要があります。
  4. このような問題は、コードが公開される前に検出するのが難しく、正規表現を個別にレビューする必要があります。

開発の観点から見ると、問題のある正規表現を修正することが解決策です。最大でも、バックトラッキングの回数を制限する安全メカニズムを追加することができます。例えば、OpenRestyでは以下のように設定します。

lua_regex_match_limit 100000;

これにより、カタストロフィックバックトラッキングが発生しても、制限がかかり、CPUがフル稼働することはありません。

これで完璧に見えますか？開発レベルを超えて、別の次元からこの問題を見てみましょう。

攻撃者

単に1台のマシンを使用してリクエストを送信するだけで、サーバーを攻撃できるのです。これはハッカーにとっての夢の核兵器です。これに比べると、DDoSは弱く、大規模でコストがかかります。

この攻撃には独自の名前があります：ReDoS (RegEx Denial of Service)。

正規表現は非常に広く使用されており、バックエンドサービスのほぼすべての部分に存在するため、その脆弱性を利用する機会があります。

例えば、ハッカーがWAFにReDoSの脆弱性を発見し、リクエストを送信してWAFをダウンさせたとします。あなたは短時間で問題を特定できず、_攻撃であることさえ気づかない_かもしれません。ビジネスを続けるためにWAFを再起動したり一時的に停止したりするかもしれません。WAFが機能していない間に、ハッカーはSQLインジェクションを使用してデータベースを盗むかもしれません。一方、あなたはまだ完全に無知のままかもしれません。

オープンソースソフトウェアとクラウドサービスの広範な使用により、自分が書いた正規表現が脆弱性を持たないようにするだけでは不十分です。これは別のトピックですが、ここでは自分で制御できる正規表現についてのみ議論します。

そのような正規表現をどのように発見するか？

問題を解決するための最初のステップは、それらを見つけ、すべてを見つけようとすることです。これは、安全に見つける能力とも呼ばれます。

手動のコードレビューで問題のある正規表現を見つけることを期待するのは信頼できません。ほとんどの開発者はセキュリティ意識が低く、複雑な正規表現で問題を見つけることは難しいでしょう。

ここで自動化ツールが役立ちます。

以下の2つの自動化方法を使用してこの問題を解決できます。

  • 静的テスト

このようなツールは、コードをスキャンして正規表現を見つけ、特定のアルゴリズムに従ってカタストロフィックバックトラッキングを引き起こす正規表現を見つけ出します。

例えば、RXXR2は、論文に基づいたアルゴリズムを実装しており、正規表現をε-NFAに変換して検索しますが、正規表現の拡張構文をサポートしていないため、見逃しが発生します。

  • 動的ファジング

ファズテストは、ソフトウェアのクラッシュやメモリリークなどの問題を検出するために、大量のランダムデータを長時間入力する一般的なソフトウェアテスト方法です。

同様に、正規表現のテストでもこのアプローチを使用できます。既存の正規表現に基づいてテストデータを生成することも、完全にランダムに生成することもできます。

SlowFuzzはオープンソースツールの1つで、これも論文に基づいたアルゴリズムを実装しています。この論文はこの記事の最後に記載されています。汎用ツールであり、正規表現の構造に対して特別な処理を行わないため、見逃しが発生します。

SDLFuzzerは、数年前にMicrosoftが開発したReDoS検出ツールですが、現在はメンテナンスされていません。

この分野では選択肢が少なく、あまり注目されていません。しかし、情報を探している間に、南京大学のいくつかの教師と博士がReDoSに関する論文を発表し、ツールReScueをオープンソース化していることを発見しました：https://2bdenny.github.io/ReScue/。このツールは、いくつかのオープンソースプロジェクトでReDoSの脆弱性を発見しました。

以下は、論文での比較テストの結果です。

1.jpg

2.jpg

一発で解決できるか？

このようなツールを使用しても、誤検出や見逃しが発生する可能性があります。では、ReDoSを一発で解決する方法はあるのでしょうか？

そのためには、問題の根本に戻って答えを見つける必要があります：正規表現エンジンがバックトラッキングを使用してマッチングを行う。

このアプローチを放棄すれば良いのではないでしょうか？はい、すでに他の多くの正規表現エンジンの実装があり、一発で解決できます。これらはすべてバックトラッキングを放棄し、NFA/DFAオートマトンのアプローチを使用して実装されています。利点は、ストリーミングマッチングに適しており、より安全であることです。欠点は、多くの正規表現の拡張構文をサポートしていないことです。例えば、後方参照などですが、これらは一般的に使用されません。

  • Google RE2

GoogleのRE2は、より完成されたオープンソースプロジェクトの1つです。PCREのほとんどの構文をサポートしており、Go、Python、Perl、Node.jsなどの開発言語のライブラリ実装があります。開始と置換のコストは非常に低いです。

Perlを例に取り、RE2がカタストロフィックバックトラッキングの問題を回避できるかどうかを見てみましょう。

以下の比較結果のチャートを見てみましょう。

3.jpg

コードは以下の通りです。興味があれば自分で試してみてください。

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

この正規表現を実行するのに40.8秒かかり、その間CPUは99%です。

RE2を使用すると、対照が非常に明確です。

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total
  • Intel Hyperscan

Intel HyperscanもRE2と同様の正規表現エンジンで、Perl、Pythonなどの言語のライブラリがあるため、導入はそれほど難しくありません。

ただし、Intelの慣例に従い、プラットフォームに強く依存しており、x86でのみ実行できます。

唯一の利点は、Intelの命令セットとハードウェアと組み合わせて性能を向上させることができることです。例えば、DPDKと組み合わせることができます。

オープンソースのネットワーク侵入検出ツールであるSnortも、以前の正規表現エンジンを置き換えるためにHyperscanを使用しています。Snortに詳しい学生は試してみてください。

拡張

以下は、正規表現に関するいくつかの論文です。興味があれば拡張として読むことができます。

  1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

  2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

  3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

  4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html

Tags:
Regex
Codec