.NET RegExクラスで無限ループを回避する方法は？

StackOverflow https://stackoverflow.com/questions/1200655

  •  05-07-2019
  •  | 
  •  

質問

単純なタスクを実行してXPath式を取得し、選択された（場合によっては）ノードの親に一致するプレフィックスを返します。

例：

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

角括弧内のパターンには引用符内に角括弧が含まれている可能性があるため、正規表現を使用してこれを実現することにしました。コードスニペットを次に示します。

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?<*>quot;;

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

パターンはかなり規則的であるため、「/」に続いて識別子、その後に文字列の最後に一致するオプションのグループ（....）？$

を探しました。

コードは機能しているように見えますが、入力文字列の異なる値で遊んで、スペースを挿入するだけで（コメントに示されている場所に）、. NET IsMatch関数が無限ループに入り、すべての取得するCPU。

現在、この正規表現パターンが最適かどうかに関係なく（より複雑になりましたが、問題を示すために簡略化しています）、これは些細でないものでRegExを使用することは非常に危険なことを示しているようです。

何か不足していますか？正規表現の一致で無限ループを防ぐ方法はありますか？

役に立ちましたか？

解決

OK、これを分解してみましょう：

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

（VB.NETからの＆quot;＆quot; ...翻訳ではなく、C＃エスケープ文字列で\＆quot;を意味していたと思いますか？）

最初に、 / [a-zA-Z0-9] + が最初の角括弧を通り抜け、次のようになります：

Input: [@x='1' and @y="/aaa[name='z'] "]

（\ [（[^]] *（]＆quot;＆quot;）？）+]）？$＆quot;の外側のグループEOLの前に0または1つのインスタンスがある場合に一致する必要があります。それでは、内部に侵入して、それが何かに一致するかどうかを確認しましょう。

＆quot; [＆quot;すぐにむさぼり食い込んでしまい、次のようになります。

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

パターンの内訳：0個以上の] 文字に一致してから＆quot;] に0回または1回一致し、できないまでこれを繰り返します。その後、] を見つけて取得しようとします。

パターンは、 [に基づいて、] に達するまで一致します。

] と＆quot; の間にスペースがあるため、これらの文字のいずれかを取得することはできませんが、の後の？ >（]＆quot;）では、とにかくtrueを返すことができます。

これで（[^]] *（]＆quot;）？）が1回正常に一致しましたが、 + は、できる回数。

これにより、次のことができます。

Input: ] "]

ここでの問題は、この入力が（[^]] *（]＆quot;）？）と一致する可能性があるということです。 ＆quot; +＆quot;試行を続けるよう強制します。

本質的に「1つ以上」と一致しています＆quot; 0または1＆quot;と一致できる状況「0または1」が続く何かの他の何かの。 2つのサブパターンのどちらも残りの入力に存在しないため、無限ループで [^]] \ * の0と（]＆quot;）？の0の一致を維持します。

入力は決してゴブリングされず、「+」の後の残りのパターンは評価されることはありません。

（うまくいけば、SO-escape-of-regex-escapeがすぐ上にあります。）

他のヒント

  

ここでの問題は、この入力が（[^]] *（]＆quot;）？と一致する可能性があることです。試行を続けるよう強制します。

これは、.NETのRegEx実装のバグの1つです。正規表現はそのようには機能しません。それらをオートマトンにすると、空の文字列の無限の繰り返しは依然として空の文字列であるという事実が自動的に得られます。

つまり、バギーでない正規表現エンジンは、この無限ループを即座に実行し、残りの正規表現を続行します。

必要に応じて、正規表現は非常に限られた言語であるため、そのような無限ループを検出して回避することが可能（かつ簡単）です。

それは、些細でないもので code を使用することは危険なことを示しています。無限ループを引き起こす可能性のあるコードを作成し、RegExコンパイラーが義務付けました。 X = 0 THEN GOTO 10の場合、最初の20以降に行われていない新しいことはありません。

特定のエッジケースでこれについて心配している場合は、RegExのスレッドを生成し、ある程度の実行時間の後にスレッドを強制終了できます。

元の質問（つまり、正規表現で無限ループを回避する方法）に答えるために、これは.Net 4.5で簡単になりました。Regexメソッドに単純にタイムアウトを渡すことができるからです。タイムアウトが期限切れになったときに正規表現ループを停止し、RegexMatchTimeoutExceptionを発生させる内部タイマーがあります

たとえば、次のようにします

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?<*>quot;;
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

MSDN をチェックアウトできます。詳細については

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top