2

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]+(\[([^]]*(]"")?)+])?$";

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 を使用することは非常に危険である可能性があることを示しているようです。

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

4

4 に答える 4

7

では、これを分解してみましょう。

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

(C# でエスケープされた文字列の \" を意味していると思いますが、""... VB.NET からの翻訳ではありませんか?)

まず、/[a-zA-Z0-9]+は最初の角括弧を飲み込み、次のようにします。

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

(\[([^]]*(]"")?)+])?$" の外側のグループは、EOL の前に 0 または 1 つのインスタンスがある場合に一致するはずです。

「[」はすぐに飲み込まれ、次のものが残ります。

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

パターンの分解: 0 個以上の]以外の文字に一致し、次に"]に 0 回または 1 回一致し、できなくなるまでこれを続けます。その後、]を見つけてガブリングしてみてください。

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

]と"の間にスペースがあるため、これらの文字のいずれかを飲み込むことはできませんが、(]")の後の?により、とにかく true を返すことができます。

これで、 ([^]]*(]")?)のマッチングに成功しましたが、+は、可能な限り何度でもマッチングを試行する必要があることを示しています。

これにより、次のことがわかります。

Input: ] "]

ここでの問題は、この入力が([^]]*(]")?)に飲み込まれることなく無限に一致する可能性があることです。

基本的に、何かの「0または1」に続いて何かの「0または1」に一致する「1以上」の状況に一致しています。残りの入力には 2 つのサブパターンのどちらも存在しないため、[^]]\*の 0 と(]")?の 0 を無限ループで一致させ続けます。

入力が飲み込まれることはなく、「+」の後の残りのパターンは評価されません。

（うまくいけば、私はすぐ上にSO-escape-of-regex-escapeを取得しました。）

于 2009-07-29T21:37:57.823 に答える
4

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

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

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

詳細については、MSDNを参照してください。

于 2014-10-16T20:11:29.543 に答える
2

ここでの問題は、この入力が ([^]]*(]")?) に飲み込まれることなく無限に一致する可能性があることです。

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

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

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

于 2016-10-25T09:42:50.157 に答える
1

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

特定のエッジケースでこれが心配な場合は、RegExのスレッドを生成し、妥当な実行時間の後にそれを強制終了することができます。

于 2009-07-29T14:32:42.017 に答える