PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities
本論文は、3つの形式的に検証された脆弱なパターンに基づいた入力を合成し、それらを構成的コンコリック実行を通じて洗練させることで、現実的な長さの予算内で実用的な攻撃の実現可能性を確保しつつ、実用的かつ効果的なReDoS攻撃文字列を生成する新しいツールであるPUFFERDOSを紹介するものである。
原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。 免責事項の全文を読む
非常に賢いが、少し強迫観念の強い、建物の入り口に立つ警備員を想像してください。彼の仕事は、あなたのIDカード（入力）が特定のパターン（正規表現、または「regex」）と一致するかどうかを確認することです。通常、これは素早く簡単に終わります。
しかし、トリックがあります。もしあなたが非常に特殊で、混乱を招くようなIDカードを渡すと、彼の脳はループに陥ってしまいます。彼は、あなたのIDがどのようにパターンに一致し得るのか、そのあらゆる可能性を何度も何度も確認し始め、エネルギーを使い果たして倒れてしまいます。これはReDoS攻撃（正規表現によるサービス拒否攻撃）と呼ばれます。これは、計算機を騙して無限に計算をさせ続け、フリーズさせるようなものです。
長い間、セキュリティ研究者たちはこれらの罠を見つけ出し、そのガードマンが壊れていることを証明するための「テスト用ID」を作成しようと試みてきました。しかし、従来の方法には2つの大きな問題がありました。
- IDが長すぎた： 以前の手法では、現実のウェブサイトでは決して受け入れられないほど巨大な入力（本一冊分ほどのテキストなど）を必要としていました。
- 建物に適合していなかった： 彼らは、メインのドアに到達する前に他のガードマン（フィルター）があなたのIDを止めてしまう可能性があるという、実際の建物の中での状況を無視して、隔離された状態でガードマンをテストしていました。
そこで登場したのが、PUFFERDOSです。PUFFERDOSを、単に鍵を開けるだけでなく、最短で最も効率的な鍵を使って、建物全体をどのように通り抜けて鍵に到達するかを解明する、熟練の鍵師だと考えてください。
PUFFERDOSの仕組みを、以下のシンプルなステップに分解して説明します。
1. 「ストップポイント」戦略（ガードマンをより疲れさせる）
研究者たちは、ガードマンをフリーズさせるには、単に混乱させるパターンが必要なのではなく、ガードマンが非常に小さく非効率なステップを踏まざるを得ないパターンが必要であることに気づきました。
- 比喩： ガードマンが廊下を歩いていると想像してください。もし、床のチェックのために一インチごとに立ち止まるように仕向けたら、彼はすぐに疲れ果ててしまいます。もし10フィートごとに立ち止まるだけなら、彼はもっと長く持ちます。
- 解決策： PUFFERDOSは、ガードマンがバックトラック（戻って再確認すること）をできる限り多く行うように、特定の文字を慎重に選び、配置することで、「鍵」（攻撃文字列）を作成します。これにより、攻撃は以前の手法よりも数千倍速くなります。なぜなら、同じ「フリーズ」効果を、より短い鍵で達成できるからです。
2. 3つの「罠」のパターン
チームは、ほとんどの壊れた鍵には3つの特定の形状があることを発見しました。PUFFERDOSには、それぞれに対する特別なレシピがあります。
- ワンループの罠： 複数の混乱した方法で読み取ることができる単一のパターン。PUFFERDOSは、繰り返される最も短く混乱を招く文字を選択します。
- ツーループの罠： 隣り合う2つのパターンが、どちらも同じ文字を読み取れる状態。PUFFERDOSは、両方のパターンがその文字を読み取れるようにすることで、どちらのパターンがその文字を処理すべきかを巡って議論（競合）させるようにします。
- マルチループの罠： 長い連鎖状のパターン。PUFFERDOSは、ガードマンがチェーンの各リンクを個別にチェックせざるを得なくなるような鍵を構築します。
3. 「現実世界」のウォークスルー（コンコリック実行）
これが最も重要な部分です。古いツールは、真空状態で鍵をテストしていました。PUFFERDOSは、建物全体をシミュレートします。
- 比喩： あなたが持つ鍵がドアを開けるとしても、そのドアがセキュリティチェックポイントや受付、そして迷路の背後にあると想像してください。古いツールは、その鍵が機能することだけを示しました。PUFFERDOSは、あなたが迷路を通り抜け、受付があなたを通してくれるかを確認し、実際にドアに到達できるかどうかを確認しながら進みます。
- 手法： これは「コンポーザショナル・コンコリック実行（compositional concolic execution）」と呼ばれる手法を使用しています。これはマップの要約と考えてください。すべてのステップを毎回歩き直す代わりに、PUFFERDOSは建物の各部屋（関数）に対する「チートシート（早見表）」を作成します。「もしこの部屋に混乱した鍵を渡したら、それは次の部屋へパススルーされるのか、それともここで破棄されるのか？」と問いかけます。
- これらのチートシートを使用することで、PUFFERDOSは、短く効率的な鍵が、実際のプログラム内で脆弱なロックに実際に到達できるのか、あるいはプロセス内の早い段階にあるフィルターによってブロックされてしまうのかを、迅速に判断することができます。
結果
チームは、PUFFERDOSを数千の現実世界のプログラムと既知のセキュリティホール（CVE）に対してテストしました。
- 速度： 以前の最高ツールよりも、97倍から3,800倍効率的な攻撃文字列を生成しました。巨大な文字列の代わりに、極めて短い文字列でシステムをフリーズさせることができました。
- 成功率： 既知のセキュリティホールの**96.8%**を再現することに成功しました（従来のツールは77.4%でした）。
- 新たな発見： 12の普及している現実世界のソフトウェアプロジェクトに対してテストを行った際、PUFFERDOSは、古いツールが「脆弱性の存在を証明するための現実的かつ短い攻撃」を生成できなかったために見逃していた、59個の新しい、未知のセキュリティホールを発見しました。
要約すると： PUFFERDOSは、混乱したパターンによってコンピュータシステムをフリーズさせられるかどうかを見つけ、証明するための、よりスマートで実用的な方法です。それは単に鍵を見つけるだけでなく、その鍵がジャム（詰まり）を起こすための最短かつ最も現実的な方法を見つけ出し、その危険が現実であることを証明するのです。
自分の分野の論文に埋もれていませんか？
研究キーワードに一致する最新の論文のダイジェストを毎日受け取りましょう——技術要約付き、あなたの言語で。