102

私は最近、正規表現のサービス拒否攻撃に気づき、コードベースで見つけられる場所、または少なくともユーザー入力で使用されるものならどこでも、いわゆる「悪」の正規表現パターンを根絶することにしました。上記のOWASPリンクとウィキペディアにある例は役に立ちますが、問題を簡単な言葉で説明するのに役立ちません。

ウィキペディアからの邪悪な正規表現の説明：

  • 正規表現は、複雑な部分式に繰り返し（ "+"、 "*"）を適用します。
  • 繰り返される部分式の場合、別の有効な一致の接尾辞でもある一致が存在します。

例を挙げて、再びウィキペディアから：

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (.*a){x}x>10の場合

これは、簡単な説明がないだけの問題ですか？正規表現を記述しているときにこの問題を回避したり、既存のコードベース内で正規表現を見つけたりするのが簡単になるものを探しています。

4

8 に答える 8

97

なぜ邪悪な正規表現が問題なのですか？

コンピュータは、たとえそれがあなたの意図したものではなく、まったく不合理であっても、あなたが指示したとおりに実行するからです。正規表現エンジンに、特定の入力について、特定のパターンに一致するものと一致しないものがあることを証明するように依頼すると、エンジンは、テストする必要のあるさまざまな組み合わせの数に関係なく、それを実行しようとします。

これは、OPの投稿の最初の例に触発された単純なパターンです。

^((ab)*)+$

入力が与えられた場合：

abababababababababababab

正規表現エンジンは次のようなこと(abababababababababababab)を試行し、最初の試行で一致が見つかります。

しかし、次にモンキーレンチを投入します。

abababababababababababab a

エンジンは最初に試行(abababababababababababab)しますが、その余分なために失敗しますa。これにより、壊滅的なバックトラックが発生します。これは、パターン(ab)*が誠意を持ってキャプチャの1つを解放し（「バックトラック」）、外側のパターンを再試行できるためです。正規表現エンジンの場合、次のようになります。

(abababababababababababab)-ノープ
(ababababababababababab)(ab)-ノープ
(abababababababababab)(abab)-ノープ
(abababababababababab)(ab)(ab)-ノープ
(ababababababababab)(ababab)-ノープ
(ababababababababab)(abab)(ab)-ノープ
(ababababababababab)(ab)(abab)-ノープ
(ababababababababab)(ab)(ab)(ab)-ノープ
(abababababababab)(abababab)-ノープ
(abababababababab)(ababab)(ab)-ノープ
(abababababababab)(abab)(abab)-ノープ
(abababababababab)(abab)(ab)(ab)-ノープ
(abababababababab)(ab)(ababab)-ノープ-
(abababababababab)(ab)(abab)(ab)ノープ-
(abababababababab)(ab)(ab)(abab)ノープ-
(abababababababab)(ab)(ab)(ab)(ab)ノープ-
(ababababababab)(ababababab)ノープ-
(ababababababab)(abababab)(ab)ノープ
(ababababababab)(ababab)(abab)-ノープ
(ababababababab)(ababab)(ab)(ab)-ノープ
(ababababababab)(abab)(abab)(ab)-ノープ
(ababababababab)(abab)(ab)(abab)-ノープ
(ababababababab)(abab)(ab)(ab)(ab)-ノープ
(ababababababab)(ab)(abababab)-ノープ
(ababababababab)(ab)(ababab)(ab)-ノープ
(ababababababab)(ab)(abab)(abab)-いいえ
(ababababababab)(ab)(abab)(ab)(ab)-いいえ
(ababababababab)(ab)(ab)(ababab)-いいえ-いいえ-いいえ-いいえ-いいえ...-
(ababababababab)(ab)(ab)(abab)(ab)いいえ-いいえ-いいえ-いいえ-いいえ-いいえ-いいえ-いいえ-いいえ
(ababababababab)(ab)(ab)(ab)(abab)
(ababababababab)(ab)(ab)(ab)(ab)(ab)
                              
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)(ab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)

可能な組み合わせの数は、入力の長さに応じて指数関数的に増加します。正規表現エンジンは、考えられるすべての用語の組み合わせを使い果たして、最終的にあきらめるまで、この問題を解決しようとしてすべてのシステムリソースを使い果たします。 「一致するものはありません」と報告します。その間、サーバーは溶けた金属の燃える山に変わりました。

邪悪な正規表現を見つける方法

それは実際には非常にトリッキーです。現代の正規表現エンジンでの壊滅的なバックトラックは、アランチューリングが解決することが不可能であると証明した停止問題と本質的に似ています。問題のある正規表現を自分で作成しましたが、それらが何であるか、一般的にはそれらを回避する方法を知っています。アトミックグループで可能なすべてをラップすると、バックトラックの問題を防ぐのに役立ちます。これは基本的に、正規表現エンジンに、指定された式を再訪しないように指示します。「最初の試行で一致したものはすべてロックします」。ただし、アトミック式は式内のバックトラックを妨げないため、危険^(?>((ab)*)+)$です^(?>(ab)*)+$が安全です（一致します）。(abababababababababababab)次に、一致する文字を放棄することを拒否し、壊滅的なバックトラックを防ぎます）。

残念ながら、一度作成すると、問題の正規表現をすぐにまたはすばやく見つけることは実際には非常に困難です。結局のところ、悪い正規表現を認識することは、他の悪いコードを認識することと同じです。多くの時間と経験、および/または単一の壊滅的なイベントが必要です。

興味深いことに、この回答が最初に書かれて以来、テキサス大学オースティン校のチームは、これらの「邪悪な」パターンを見つけるという明確な目的で正規表現の静的分析を実行できるツールの開発について説明した論文を発表しました。このツールはJavaプログラムを分析するために開発されましたが、特にReDoS攻撃の割合が増え続けるにつれて、JavaScriptやその他の言語で問題のあるパターンを分析および検出することを中心に開発されたツールが今後さらに増えると思います。

正規表現を使用するプログラムでのDoS脆弱性の静的検出
ValentinWüstholz、Oswaldo Olivo、Marijn JH Heule、およびIsilDillig
テキサス大学オースティン校

于 2012-10-11T18:22:14.403 に答える
14

あなたが「邪悪な」正規表現と呼ぶものは、壊滅的なバックトラックを示す正規表現です。リンク先のページ（私が書いた）は、概念を詳細に説明しています。基本的に、壊滅的なバックトラッキングは、正規表現が一致せず、同じ正規表現の異なる順列が部分的な一致を見つけることができる場合に発生します。次に、正規表現エンジンはこれらすべての順列を試行します。コードを調べて正規表現を調べたい場合は、次の3つの重要な問題を確認してください。

  1. 選択肢は相互に排他的でなければなりません。複数の選択肢が同じテキストに一致する可能性がある場合、正規表現の残りの部分が失敗すると、エンジンは両方を試行します。選択肢が繰り返されるグループに含まれている場合は、壊滅的なバックトラックが発生します。典型的な例は(.|\s)*、正規表現フレーバーに「ドットが改行に一致する」モードがない場合に、任意の量のテキストに一致することです。.これがより長い正規表現の一部である場合、スペースの実行が十分に長い（との両方が一致する\s）サブジェクト文字列は正規表現を壊します。修正は、代替を相互に排他的にするために使用するか、ASCII印刷可能文字、タブ、改行(.|\n)*など、実際に許可される文字をより具体的にするために使用します。[\r\n\t\x20-\x7E]

  2. 順番に並んでいる定量化されたトークンは、相互に排他的であるか、それらの間にあるものが相互に排他的である必要があります。それ以外の場合、両方が同じテキストに一致する可能性があり、正規表現の残りの部分が一致しない場合、2つの数量詞のすべての組み合わせが試行されます。典型的な例はa.*?b.*?c、3つのものをそれらの間の「何でも」と一致させることです。c一致できない場合、最初のファイル.*?は行またはファイルの終わりまで文字ごとに展開されます。2番目の展開では、展開ごとに1.*?文字ずつ展開して、行またはファイルの残りの部分と一致させます。修正は、それらの間に「何か」を置くことはできないことを認識することです。最初の実行はで停止する必要がbあり、2番目の実行はで停止する必要がありますc。単文字でa[^b]*+b[^c]*+c簡単な解決策です。区切り文字で停止するので、所有格の数量詞を使用してパフォーマンスをさらに向上させることができます。

  3. 数量詞を含むトークンを含むグループは、グループ内の数量化されたトークンが相互に排他的な他のものとのみ一致する場合を除いて、独自の数量詞を持ってはなりません。これにより、内部数量詞の反復回数が多い外部数量詞の反復回数が少なくなり、内部数量詞の反復回数が少ない外部数量詞の反復回数が多いのと同じテキストに一致する方法がなくなります。これは、JDBの回答に示されている問題です。

私が答えを書いている間、私はこれが私のウェブサイトの完全な記事に値すると決めました。これもオンラインになりました。

于 2017-06-16T09:26:17.107 に答える
11

邪悪な正規表現の検出

  1. NicolaasWeidemanのRegexStaticAnalysisプロジェクトをお試しください。
  2. WeidemanのツールなどのCLIを備えたアンサンブルスタイルのvuln-regex-detectorを試してみてください。

経験則

邪悪な正規表現は常に、対応するNFAのあいまいさによるものであり、regexperなどのツールを使用して視覚化できます。

ここにいくつかの形式のあいまいさがあります。これらを正規表現で使用しないでください。

  1. (a+)+（別名「星の高さ> 1」）のような入れ子の数量詞。これにより、指数関数的な爆発が発生する可能性があります。サブスタックのsafe-regexツールを参照してください。
  2. のような定量化された重複論理和(a|a)+。これにより、指数関数的な爆発が発生する可能性があります。
  3. のような定量化された重複する隣接関係は避けてください\d+\d+。これにより、多項式の爆発が発生する可能性があります。

追加のリソース

この論文は超線形正規表現について書きました。これには、他の正規表現関連の研究への参照が多数含まれています。

于 2017-05-09T14:29:52.393 に答える
10

私はそれを「繰り返しの繰り返し」と要約します。あなたがリストした最初の例は、「文字a、1回以上続けて。これも1回以上続けて起こる可能性がある」と述べているので良い例です。

この場合に探すべきものは、*や+などの数量詞の組み合わせです。

注意すべきもう少し微妙なことは、3番目と4番目のものです。これらの例にはOR演算が含まれており、両側が真になる可能性があります。これを式の数量詞と組み合わせると、入力文字列に応じて、多くの潜在的な一致が生じる可能性があります。

要約すると、TLDRスタイル：

数量詞を他の演算子と組み合わせて使用​​する方法に注意してください。

于 2012-10-11T17:58:28.800 に答える
7

驚くべきことに、ソースコードレビューを実行するReDOSに何度も遭遇しました。私がお勧めすることの1つは、使用している正規表現エンジンでタイムアウトを使用することです。

たとえば、C＃では、TimeSpan属性を使用して正規表現を作成できます。

string pattern = @"^<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)$";
Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0));
try
{
    string noTags = regexTags.Replace(description, "");
    System.Console.WriteLine(noTags);
} 
catch (RegexMatchTimeoutException ex)
{
    System.Console.WriteLine("RegEx match timeout");
}

この正規表現はサービス拒否に対して脆弱であり、タイムアウトがないとスピンしてリソースを消費します。タイムアウトを使用すると、指定されたタイムアウトの後にがスローRegexMatchTimeoutExceptionされ、サービス拒否状態につながるリソース使用量は発生しません。

タイムアウト値を試して、使用方法に合っていることを確認してください。

于 2016-06-09T01:41:09.960 に答える
4

これは、使用中の正規表現エンジンに関連していると思います。これらのタイプの正規表現を常に回避できるとは限りませんが、正規表現エンジンが正しく構築されていれば、それほど問題にはなりません。正規表現エンジンのトピックに関する多くの情報については、このブログシリーズを参照してください。

バックトラックはNP完全問題であるという点で、記事の下部にある警告に注意してください。現在、それらを効率的に処理する方法はありません。入力でそれらを禁止することをお勧めします。

于 2012-10-11T19:08:07.610 に答える
3

少なくともすべてではないか、表現力を制限することなく、そのような正規表現を認識できるとは思いません。あなたが本当にReDoSを気にかけているのなら、私はそれらをサンドボックス化し、タイムアウトでそれらの処理を強制終了しようとします。また、最大バックトラッキング量を制限できるRegEx実装がある可能性もあります。

于 2012-10-11T15:00:17.393 に答える
0

小さなテスト入力で実行したり、正規表現の構造を分析したりすることで、いくつかの単純化ルールを実装できると私が考える方法がいくつかあります。

  • (a+)+冗長な演算子を次のように置き換えるためのある種のルールを使用して減らすことができます(a+)
  • ([a-zA-Z]+)*また、新しい冗長性の組み合わせルールを使用して簡略化することもできます([a-zA-Z]*)

コンピューターは、関連する文字のランダムに生成されたシーケンスまたは文字のシーケンスに対して正規表現の小さな部分式を実行し、それらがすべてどのグループに入るのかを確認することで、テストを実行できます。が欲しいので、で試してみましょう6aaaxaaq。次に、すべてのaと、最初のグループのみが1つのグループに含まれることを確認し、aがいくつ配置されても、すべてがグループに含まれるため、問題ではないと結論付け+ます。2つ目は、正規表現が文字の束を必要としているので、で試してみると-fg0uj=、各束がすべて1つのグループに含まれていることがわかり+、最後にを削除します。

次に、次のルールを処理するための新しいルールが必要です。それは、elimate-irrelevant-optionsルールです。

  • を使用(a|aa)+すると、コンピューターはそれを調べて、2番目の大きなものが好きですが、最初の1つを使用してより多くのギャップを埋め、できるだけ多くのaaを取得して、他に何かを取得できるかどうかを確認できます。終わった後。`eaaa @ a〜aa'などの別のテスト文字列に対して実行できます。それを決定する。

  • (a|a?)+一致する文字列は私たちが探しているドロイドではないことをコンピューターに認識させることで、自分自身を守ることができますa?。これは、いつでもどこでも一致する可能性があるため、のようなものは好きではないと判断して(a?)+破棄するためです。

  • (.*a){x}一致する文字aがすでに。によって取得されていることを認識させることで、保護し.*ます。次に、その部分を破棄し、別のルールを使用して、の冗長な数量詞を置き換えます(.*){x}。

このようなシステムの実装は非常に複雑ですが、これは複雑な問題であり、複雑な解決策が必要になる場合があります。また、他の人が提起した手法を使用する必要があります。たとえば、正規表現が終了しない場合は、正規表現を強制終了する前に、限られた量の実行リソースのみを許可するなどです。

于 2013-05-29T22:14:23.140 に答える