セキュリティに関するブリーフィング

[アーティクル]
06/16/2015

正規表現によるサービス拒否攻撃と防御

Bryan Sullivan

2009 年 11 月号の「XML サービス拒否攻撃と防御」(msdn.microsoft.com/magazine/ee335713) という記事で、XML パーサーに対して特に有効ないくつかのサービス拒否攻撃 (DoS) の手法について説明しました。このコラムについて読者の皆様からさらに詳しい情報を求める多数の電子メールをいただいたことで、DoS 攻撃がどれほど深刻な攻撃になり得るかをお伝えすることについて本当に勇気づけられました。

私は今後 4、5 年間で、データ実行防止 (DEP) や ASLR (Address Space Layout Randomization) などのメモリ保護の採用や、分離手法や特権の制限手法などの採用が広まることで、特権昇格による攻撃の実行が難しくなり、DoS 脅迫攻撃が攻撃の主流になると考えています。開発者は、引き続き常に攻撃の傾向の先を読むことで、現在考えられる DoS の将来的な流れに対応することができます。

現在考えられる DoS の将来的流れの 1 つが正規表現による DoS です。2009 年にイスラエルで開催された Open Web Application Security Project (OWASP) カンファレンスにおいて、Checkmarx のチーフアーキテクトの Alex Roichman 氏とシニアプログラマの Adar Weidman 氏は、正規表現による DoS ("ReDoS") についてすばらしい研究を発表しました。この研究では、適切に記述されていない正規表現は悪用される可能性があり、比較的短い文字列 (50 文字未満) の評価に数時間以上かかる可能性があることが明らかにされました。最悪の場合、処理時間は実に入力文字列の文字数の累乗、つまり、文字列に 1 文字追加するだけで処理時間が 2 倍になります。

今回のコラムでは、正規表現に対してこのような攻撃が可能になる要因について説明します。また、数千件のランダム入力を基に正規表現を評価し、許容できないほど処理に時間がかかる入力がないかを調べてフラグを付けることで、脆弱な正規表現を特定するテストユーティリティとして Regex Fuzzer のコードも紹介します。

(注: 今回のコラムは、正規表現構文の知識があることが前提です。正規表現構文をご存知でない方は、「.NET Framework の正規表現」(msdn.microsoft.com/library/hs600312) をお読みいただくか、さらに詳しい内容を知りたい方は、Jeffrey Friedl 著の優れたリファレンスブック『詳説正規表現第 3 版』(オライリージャパン、2008 年) をお読みください。

バックトラック: 問題の根本原因

正規表現エンジンは、基本的に 2 種類あります。1 つは、決定性有限オートマトン (DFA) エンジン、もう 1 つは非決定性有限オートマトン (NFA) エンジンです。この 2 種類のエンジンの違いを完全に分析すると、このコラムで扱う範囲を超えてしまいますので、ここでは次の 2 点についてのみ説明します。

NFA エンジンはバックトラックエンジンです。入力文字列の各文字を最大で 1 度しか評価しない DFA と異なり、NFA エンジンでは入力文字列の各文字を複数回評価できます (このバックトラックの評価アルゴリズムの動作については、後ほど実例を紹介します)。バックトラック方式では、前方参照を含む正規表現や、かっこをキャプチャする正規表現など、エンジンがより複雑な正規表現を処理できるというメリットがあります。一方、処理時間が DFA よりもはるかに長いという欠点があります。
Microsoft .NET Framework System.Text.RegularExpression クラスでは、NFA エンジンを使用します。

バックトラックの重要な副作用の 1 つは、正規表現エンジンはかなり短時間でポジティブマッチ (つまり、入力文字列に特定の正規表現が含まれていること) を確認できますが、ネガティブマッチ (入力文字列に特定の正規表現が含まれていないこと) の確認にはかなり長い時間がかかる可能性があることです。実際、エンジンは入力文字列全体で可能性のある "パス" がどれも正規表現に一致しないことを確認する、つまりすべてのパスがテストされる必要があります。

グループ化なしの簡単な正規表現の場合、ネガティブマッチの確認にかかる時間は大きな問題ではありません。たとえば、一致するかどうかを確認する正規表現が、次の正規表現だとします。

^\d+$

これは、入力文字列全体が数字のみで構成されるかなり単純な正規表現です。文字 ^ および $ は、それぞれ文字列の先頭と末尾を表し、表現 \d は数字を、+ は 1 つ以上の文字が一致することを表します。入力文字列に 123456X を使用して、この表現をテストしてみましょう。

この入力文字列は、X が数字でないことから、一致しないことは明らかです。しかし、この結論にいたるまで、このサンプルの正規表現には、評価しなければならないパスがいくつあるでしょう。この場合、評価は文字列の先頭から始まり、文字 1 が有効な数字であり、正規表現に一致するかどうかが確認されます。次に、文字 2 の処理に移りますが、これも一致します。したがって、この時点で文字列 12 が正規表現に一致しています。次に、3 を検査する (その結果 123 が一致する) というように続いて、最終的に X に到達しますが、これは一致しません。

しかし、このエンジンはバックトラック NFA エンジンであるため、この時点でも処理は終了しません。現在の一致 (123456) から前回確認された一致 (12345) まで後退し、そこから処理を繰り返します。5 の次の文字は文字列の最後の文字ではないため、この正規表現は一致せず、前回確認されている一致 (1234) に後退して処理を繰り返します。これが、最初の一致文字 (1) まで後退し、1 の後の文字が文字列の最後でないことが確認されるまで延々と続きます。この時点で、正規表現は処理を停止しますが、一致は見つかっていません。

合計すると、エンジンは、123456、12345、1234、123、12、1 の 6 つのパスを評価しました。この入力文字列があと 1 文字長かった場合、エンジンはさらに 1 つパスを評価します。したがって、この正規表現は文字列の長さに比例するアルゴリズムであり、DoS の原因になる危険性はありません。^\d+$ をパターンに使用する System.Text.RegularExpressions.Regex オブジェクトは、巨大な入力文字列 (10,000 文字を超える文字列) であっても、ほぼ直ちに評価できるほど高速です。

では、この正規表現を次のような数字のグループに変更してみましょう。

^(\d+)$

これによって評価の結果が大幅に変わることはありません。単に、キャプチャされたグループの単位で一致を扱えるようにするだけです (この手法は、反復演算子を適用するなど、より複雑な正規表現では有用ですが、ここでの例では価値はありません)。この場合にグループ化のかっこを追加しても、正規表現の実行速度も大幅には変わりません。123456X という入力に対してパターンをテストすると、この場合も、エンジンによって 6 つのパスが評価されます。ただし、この正規表現をさらにほんの少し変更するだけで、状況は大きく変化します。

^(\d+)+$

グループ表現に文字 + を追加する (\d+) ことで、キャプチャできるグループの数だけ一致状態が正規表現エンジンによって評価されるようになります。エンジンは前と同じように処理を進め、123456 を評価してから、12345 に後退します。

事態が (非常に危険であるという意味で) "興味深く" なるのはこの部分です。単に 5 の次の文字は文字列の末尾ではないことを確認するのではなく、次の文字 6 が新たにキャプチャされたグループとして扱われ、そこから再び確認が開始されます。このパスが一致しなかった場合、1234 に後退して、56 を別のキャプチャグループとして評価し、さらに 5 と 6 を別のキャプチャグループとして評価します。結果として、エンジンは実に 32 とおりのパスを評価することになります。

ここで、評価対象の文字列にさらに 1 文字追加すると、この文字列が一致しないことを確認するために、エンジンは 64 とおり (2 倍) のパスを評価しなければなりません。このため、正規表現エンジンによって実行される処理量が累乗的に増加します。攻撃者が、比較的短い (30 文字ほどの) 入力文字列を渡して、エンジンが数億とおりのパスを処理しなければならないようにして、数時間または数日間処理し続けるように仕向けることが可能です。

秘密を暴露する

サーバー側のコードに、DoS 攻撃を許可し得る、累乗的に処理量が増加する正規表現が、アプリケーションに潜んでいることは十分に問題です。また、アプリケーションの脆弱性がクライアント側コードにも波及している場合は、さらに問題です。RegularExpressionValidator も含めて ASP.NET バリデーターコントロールの多くは、System.Web.UI.WebControls.BaseValidator から派生したもので、.NET コードでのサーバー側の検証ロジックと同じロジックを JavaScript でクライアント側でも実行します。

ほとんどの場合、これは有用な処理です。入力フィールドにユーザーが誤った入力を行った場合に、バリデーターがフォームを拒否することで、サーバーへのフォーム送信時のラウンドトリップにかかる時間を節約できます。また、サーバー側の処理時間も節約できます。ただし、アプリケーションがサーバー側コードに不適切な正規表現を使用していて、その不適切な正規表現がクライアントコードでも使用される場合、攻撃者がその正規表現を特定して、それ用の攻撃文字列を開発することは非常に容易です。

たとえば、新しい Web フォームを作成して、このフォームに TextBox と RegularExpressionValidator を追加するとします。バリデーターの ControlToValidate プロパティをテキストボックスの名前に設定し、ValidationExpression を前述の不適切な正規表現の 1 つに設定します。

this.RegularExpressionValidator1.ControlToValidate = "TextBox1";

this.RegularExpressionValidator1.ValidationExpression = @"^(\d+)+$";

次にこのページをブラウザーで開き、ソースを参照すると、ページの一番下の方に次の JavaScript コードを確認できます。

<scripttype="text/javascript">

//< ![CDATA[

var RegularExpressionValidator1 = document.all ? 

  document.all["RegularExpressionValidator1"] : 

  document.getElementById("RegularExpressionValidator1");

RegularExpressionValidator1.controltovalidate = "TextBox1";

RegularExpressionValidator1.validationexpression = "^(\\d+)+$";

//]] >

</script>

スクリプトブロックの最後の行に、累乗的に処理量が増加する正規表現が表示されており、だれでもこれを読み取ることができます。

問題のあるその他のパターン

もちろん、世にある不適切な正規表現は ^(\d+)+$ だけではありません。基本的に、グループ式を含む正規表現で、その正規表現自体の反復がある場合は脆弱になります。これには、次のような正規表現があります。

^(\d+)*$
^(\d*)*$
^(\d+|\s+)*$

また、選択条件を含むグループで、代替のサブ表現が互いに共通部分がある場合も脆弱です。

^(\d|\d\d)+$
^(\d|\d?)+$

上記のような表現が現在コードに含まれている場合、コードを見るだけで、そのコードが脆弱であることがわかるでしょう。ただし、次のような、より長く複雑 (で現実的) な表現では、脆弱性を見逃す可能性があります。

^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+[a-zA-Z]{2,9})$

これは、電子メールアドレスの検証に使用することを目的とした Regular Expression Library Web サイト (regexlib.com、英語) で公開されている正規表現です。ただし、これは攻撃に対して脆弱でもあります。この脆弱性は手動のコード検査で発見できる可能性も、発見できない可能性もあります。このような問題を発見するためのより有効な手法が必要であり、次はこれについて説明します。

コードに潜む不適切な正規表現を発見する

コード内で累乗的に処理量が増加する正規表現を発見して、コンパイル時に警告する手段があるのが理想です。おそらく、特定の正規表現文字列を解析して、脆弱性が潜んでいないかを分析するには、また別の正規表現が必要になります。この時点で、私は正規表現中毒者になったような気分になります。「助けなんかいらない、ただもっと正規表現が必要なんだ」と感じるのです。悲しいことに、私の正規表現のスキルは、正規表現を分析するための正規表現を記述できるほどではありません。実際に使用できるこのようなコードがお手元にあると思われたら、私宛てにお送りください。来月の「セキュリティに関するブリーフィング」で詳細させていただきます。とりあえず、私にはコンパイル時に不適切な正規表現を検出する手段がないため、次善の策を取りたいと思います。次のような Regex Fuzzer を作成しました。

ファジーテストは、形式に誤りがあるランダムデータをアプリケーションの入力に渡して、そのデータによってアプリケーションが失敗するかどうかを確認するテストです。ファジーテストを繰り返し実行すればするほど、バグを発見できる可能性は高くなるため、一般的には 1 入力あたり数千や数百万の繰り返しが実行されます。マイクロソフトのセキュリティチームでは、これがバグの発見に非常に有効な手段であることを確認しているため、セキュリティ開発ライフサイクルチームは、すべての製品とサービスチームに対してファジーテストを必須テストにしています。

このコラムの Fuzzer では、正規表現にランダム入力文字列を渡すファジーテストを実行します。まず、正規表現用の定数文字列、正規表現を確認する testInputValue メソッド、および testInputValue にフィードされるランダムな入力文字列を収集する runTest を定義します。

const string regexToTest = @"^(\d+)+$";



static void testInputValue(string inputToTest)

{

  System.Text.RegularExpressions.Regex.Match(inputToTest, regexToTest);

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  testInputValue(inputToTest);

}

ファジーテスト用に入力値を生成するコードは、この時点では作成されていないことに注意してください。これについては、すぐに説明します。また、このコードでは Regex.Match からの戻り値は確認されないことにも注意してください。ここでは、入力がパターンに一致するかどうかは問題にしていないためです。この場合に確認することは、入力の一致状態を判断するために、正規表現エンジンの処理に時間がかかりすぎないかどうかだけです。

通常、Fuzzer は、悪用できる特権の昇格関連の脆弱性の検出に使用されますが、ここでの目的は DoS の脆弱性を検出することのみです。単純に、テストアプリケーションデータをフィードして、アプリケーションがクラッシュするかどうかを確認することはできず、テストデータによってアプリケーションがフリーズしないかどうかを検出できる必要があります。最も科学的な方法ではないかもしれませんが、個別のワーカースレッドで各正規表現テストを順に実行して、そのスレッドの処理の完了にタイムアウト値を設定することでも、目的の作業を達成できます。スレッドが処理を適当な時間内、たとえば 1 つの入力をテストするのに 5 秒以内に完了しなければ、正規表現は DoS 状態に陥ったと見なします。ここでは ManualResetEvent を追加し、それに合わせて testInputValue メソッドと runTest メソッドを変更します (図 1 参照)。

図 1 個別のワーカースレッドを使用したテスト

static ManualResetEvent threadComplete = new ManualResetEvent(false);



static void testInputValue(object inputToTest)

{

  System.Text.RegularExpressions.Regex.Match((string)inputToTest, 

    regexToTest);

  threadComplete.Set();

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  {

    Thread thread = new Thread(testInputValue);

    thread.Start(inputToTest);



    if (!threadComplete.WaitOne(5000))

    {

      Console.WriteLine("Regex exceeded time limit for input " + 

        inputToTest);

      return;

    }



    threadComplete.Reset();

  }



  Console.WriteLine("All tests succeeded within the time limit.");

}

では、入力値を生成しましょう。実際の作業は思ったよりも困難です。単純にまったくランダムなデータを生成しても、正規表現の脆弱性を発見できるような一致状態になる入力値は得られないでしょう。たとえば、^(\d+)+$ という正規表現を XdO(*iLy@Lm4p$ という入力値を使用してテストすると、正規表現は直ちに不一致となり、問題は発見できないままになります。テストを有効なものにするには、アプリケーションが予期する値にごく近い入力値を生成する必要があります。したがって、特定の正規表現に一致するランダムデータを生成する手段が必要です。

データ生成計画の登場

さいわい、Visual Studio データベースプロジェクトに、まさにこの作業を実行できる機能があります。データ生成計画と呼ばれる機能です。Visual Studio Team Suite を使用されている場合も、この機能を利用できます。データ生成計画は、データベースにテストデータをすばやく設定するために使用されます。データ生成計画では、ランダム文字列のほか、数値や (ここではありがたいことに) 特定の正規表現に一致する文字列をテーブルに設定できます。

まず、テストデータの生成先となるテーブルを SQL Server 2005 または 2008 データベースに作成します。作成できたら、Visual Studio に戻り、新しい SQL Server データベースプロジェクトを作成します。データベースプロジェクトのプロパティを編集して、データベースへの接続文字列を指定します。接続文字列を入力し、接続できることをテストできたら、ソリューションエクスプローラーに戻って、プロジェクトに新しい項目としてデータ生成計画を追加します。この時点で、図 2 のようになります。

Figure 2 A Data Generation Plan Item in Visual Studio
図 2 Visual Studio のデータ生成計画項目

次に、ファジーテスト用の入力データを設定するテーブルと列を選択します。テーブルを選択するときに、生成するテスト値の数を設定します ([挿入行] 列)。前に、ファジーテストでは、問題を検出するために、通常、数十万や数百万の繰り返しがテストされると書きました。通常は、この程度の厳格なテストを承認しますが、ここでの正規表現のファジーテストではやり過ぎです。正規表現がフリーズするのであれば、数百回テストを繰り返せば十分です。[挿入行] は「200」の設定で問題ありませんが、それよりも多くテストしたければそれも可能です。

[列 (データ生成に含める場合はオンにする)] セクションで、[ジェネレーター] を [正規表現] に設定し、列の [プロパティ] タブで "式" プロパティの値として、テストする正規表現パターンを入力します。"式" プロパティでは、有効な正規表現がすべてサポートされているわけではないことに注意してください。行の開始アンカー ^ と終了アンカー $ は入力できません (より正確には、入力はできますが、テスト入力に生成される文字はリテラルの ^ または $ 文字になります)。これらの文字は使用しないでください。正規表現ジェネレーターによってサポートされる演算子の完全な一覧については、msdn.microsoft.com/library/aa833197(VS.80) を参照してください。

さらに大きな問題は、"式" プロパティでは、数値には \d、文字には \w といった一般的な簡易表記法がサポートされないことです。正規表現にこれらの表記法が使用されている場合、対応する文字クラスに置き換える必要があります。たとえば、\d の代わりに [0-9] や、\w の代わりに [a-zA-Z0-9_] を使用します。\s (空白文字) を置き換える必要がある場合は、代わりにリテラルのスペースを入力できます。

データベースプロジェクトでの最後の作業は、実際に指定に従ってデータベースにテストデータを設定することです。それには、[データ] メニューの [データジェネレーター] をクリックし、[データの生成] をクリックするか、F5 キーを押します。

攻撃を追加する

ファジーテストコードに戻り、runTest メソッドを変更して、生成されたテストデータをデータベースから取得できるようにします。これが終わったら作業は完了と思われるかもしれませんが、実際には、もう 1 つ重要な変更を行う必要があります。この時点でファジーテストを実行すると、テスト対象が ^(\d+)+$ のような既知の不適切な正規表現であったとしても、問題は見つからず、すべてのテストに合格したと報告されます。これは、生成したすべてのテストデータ、正規表現に一致する有効な値であるためです。

NFA 正規表現エンジンは、非常に短時間でポジティブマッチを確認でき、実際にはネガティブマッチのときのみ問題が起きると説明したことを思い出してください。さらに、NFA はバックトラック方式であるため、入力の最初のかなりの数の文字は一致し、無効な文字が最後に出現しない限り、問題は発生しないことも説明しました。無効な文字が入力文字の先頭にあると、テストは直ちに終了します。

ファジーテストのコードに必要な最後の変更は、テスト入力の最後に無効な文字を追加することです。数値、英文字、句読点、空白文字を保持する文字列配列を作成します。

string[] attackChars = { "0", "1", "9", "X", "x", "+", 

"-", "@", "!", "(", ")", "[", "]", "\\", "/", 

"?", "<", ">", ".", ",", ":", ";", " ", "" };

次に、コードを変更して、データベースから取得される各入力文字列を、これらの攻撃用文字が末尾に追加された状態でテストされるようにします。したがって、最初の入力文字列は末尾に 0 という文字が追加された状態でテストされ、次は末尾に 1 が追加された状態でテストされるという形になります。各攻撃文字列が追加された状態で 1 つの入力文字列のテストが完了したら、次の入力文字列に各攻撃文字列を追加してテストします。

foreach (string inputToTest in inputsToTest)

{

  foreach (string attackChar in attackChars)

  {

    Threadthread = new Thread(testInputValue);

    thread.Start(inputToTest + attackChar);

...

目下の問題は 2 つ

元 Netscape のエンジニア Jamie Zawinski 氏による正規表現についての有名な言葉があります。

「問題が発生したときに、「わかってる、正規表現を使おう」という人がいます。この場合、2 つの問題があります」

私は Zawinski 氏ほど正規表現についてはシニカルではありませんが、正しい正規表現はもとより、DoS 攻撃に対して安全な正しい正規表現を記述するのは非常に困難になり得ることは認めます。累乗的に処理が複雑になる表現がないかすべての正規表現を検査し、ファジーテストを使用して結果を確認することをお勧めします。

Bryan Sullivan は、マイクロソフトのセキュリティ開発ライフサイクルチームのセキュリティプログラムマネージャーであり、Web アプリケーションと .NET のセキュリティ問題を専門に扱っています。『Ajax セキュリティ』(毎日コミュニケーションズ、2008 年) の著者でもあります。

この記事のレビューに協力してくれた技術スタッフの Barclay Hill、Michael Howard、Ron Petrusha、および Justin van Patten に心より感謝いたします。

次の方法で共有