正規表現サービス拒否（ReDoS）に対して脆弱な正規表現を見つけます。
詳細は Doyensec ブログ をご覧ください。
多くのデフォルトの正規表現パーサーは、最悪の場合の複雑さが無制限です。マッチする入力文字列に対しては高速にマッチングを行うかもしれません。しかし、特定のマッチしない入力文字列によって、正規表現マッチャーが異常なバックトラッキングループに陥り、処理に長い時間がかかることがあります。これは、CPU が正規表現のマッチングに固執してしまうため、サービス拒否を引き起こす可能性があります。
このツールは以下のために設計されています：
これは、入力文字列の長さに対する正規表現マッチャーのバックトラッキング手順の複雑さを反映しています。
ここでの3次複雑性とは、文字列の脆弱な部分の長さが2倍になると、実行時間が約8倍（2^3）になることを意味します。
スター付きスター（例：(a*)*$）による指数関数的なReDoSの場合、補正係数が使用され、複雑性は10を超えます。
悪用可能性としては、実際に巨大な文字列が入力として許可されない限り、通常は3次以上の複雑性が必要です。
regexploit を実行し、コマンドラインで正規表現 v\w*_\w*_\w*$ を入力します。
$ regexploit
v\w*_\w*_\w*$
Pattern: v\w*_\w*_\w*$
---
Worst-case complexity: 3 ⭐⭐⭐ (cubic)
Repeated character: [5f:_]
Final character to cause backtracking: [^WORD]
Example: 'v' + '_' * 3456 + '!'
部分 \w*_\w*_\w* には、3つの重複する繰り返しグループが含まれています（\w はアルファベット、数字、およびアンダースコアにマッチします）。Repeated character: [5f:_] という行に示されているように、長い _（0x5f）の文字列は、このセクションにさまざまな方法でマッチします。3つの無限に繰り返すグループがあるため、最悪計算量は3です。ReDoS を引き起こす例は、必要なプレフィックス v、長い _ の文字列、そしてバックトラッキングを引き起こす !（非単語文字）で構成されています。すべての ReDoS が最後に特定の文字を必要とするわけではありませんが、この場合、長い _ の文字列は正規表現に正常にマッチし、バックトラックしません。Final character to cause backtracking: [^WORD] の行は、マッチを防ぎ ReDoS を引き起こすために、最後にマッチしない文字（単語文字以外）が必要であることを示しています。
別の例として、pip install ua-parser==0.9.0 のように ReDoS に対して脆弱なモジュールバージョンをインストールします。
インストールされている Python モジュールをスキャンするには、regexploit-python-env を実行します。
Importing ua_parser.user_agent_parser
Vulnerable regex in /somewhere/.env/lib/python3.9/site-packages/ua_parser/user_agent_parser.py #183
Pattern: \bSmartWatch *\( *([^;]+) *; *([^;]+) *;
Context: self.user_agent_re = re.compile(self.pattern)
---
Worst-case complexity: 3 ⭐⭐⭐
Repeated character: [20]
Example: 'SmartWatch(' + ' ' * 3456
Worst-case complexity: 3 ⭐⭐⭐
Repeated character: [20]
Example: 'SmartWatch(0;' + ' ' * 3456
Vulnerable regex in /somewhere/.env/lib/python3.9/site-packages/ua_parser/user_agent_parser.py #183
Pattern: ; *([^;/]+) Build[/ ]Huawei(MT1-U06|[A-Z]+\d+[^\);]+)[^\);]*\)
Context: self.user_agent_re = re.compile(self.pattern)
---
Worst-case complexity: 3 ⭐⭐⭐
Repeated character: [[0-9]]
Example: ';0 Build/HuaweiA' + '0' * 3456
...
脆弱な正規表現ごとに、ReDoS をトリガーする1つ以上の悪意のある文字列を出力します。ユーザーエージェントを ;0 Build/HuaweiA000000000000000... に設定し、古いバージョンの ua-parser を使用しているウェブサイトを閲覧すると、サーバーがリクエストの処理に長い時間を要し、おそらくステータス 502 で終了する可能性があります。
Python 3.8 以上が必要です。JavaScript / TypeScript コードから正規表現を抽出するには、NodeJS 12 以上も必要です。
必要に応じて仮想環境を作成します。
python3 -m venv .env
source .env/bin/activate
次に、pip で実際にインストールします。
pip install regexploit
stdin から（1行に1つずつ）正規表現を regexploit に入力します。
regexploit
またはファイル経由で
cat myregexes.txt | regexploit
Python、JavaScript、TypeScript、C#、YAML、JSON から正規表現を解析するための組み込みサポートがあります。
AST を介して Python コードを（実行せずに）解析し、正規表現を見つけます。その後、正規表現は ReDoS について分析されます。
regexploit-py my-project/
regexploit-py "my-project/**/*.py" --glob
これは、regexploit/bin/javascript にあるバンドルされた NodeJS パッケージを使用し、eslint を使用して JavaScript を AST として解析し、すべての正規表現を出力します。
それらの正規表現は Python の ReDoS 検出ツールに入力されます。
regexploit-js my-module/my-file.js another/file.js some/folder/
regexploit-js "my-project/node_modules/**/*.js" --glob
注意：JavaScript と Python の正規表現解析には違いがあるため、エラーが発生する可能性があります。JS の正規表現 AST を書くのは あまり気が進みません。
現在のパス/環境にインストールされているすべての Python モジュールから正規表現を検索します。つまり、興味のあるモジュールを pip install すれば、それが分析されます。Cpython コードも含まれます。
regexploit-python-env
注意：これは Python コードを AST に解析せず、モジュールのインポート時に自動的にコンパイルされた正規表現のみを見つけます。モジュールは実際にインポートされるため、モジュール内のコードが実行されます。これは、読み込み時に小さな文字列から構築される正規表現（例：Pillow の CVE-2021-25292）を見つけるのに役立ちます。
YAML のサポートには pyyaml が必要で、pip install regexploit[yaml] でインストールできます。
regexploit-json *.json
regexploit-yaml *.yaml
regexploit-csharp something.cs
このツールは、Doyensec LLC の Ben Caller が研究時間中に作成しました。
