ユーザーが送信した正規表現からの無限の一致を処理する方法

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

  •  03-07-2019
  •  | 
  •  

質問

C＃で次の2行を考えてみましょう（フレームワーク.NET 3.5を使用）

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)<*>quot;, RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'énnerver ");

（フランス語のプログラムでごめんなさい：））

実行されると、プロセスは Match（）メソッドで停止し、終了しません。私は正規表現パターンの空白に何らかの問題があると思いますが、私がやりたいのはパターンを変更することではありません（実際にはプログラムの外部、私のツールのエンドユーザーによって設定されます）が、プロセスを停止することができます（たとえばタイムアウト付き）。

これが.NET正規表現の既知の問題であり、それを回避する簡単な方法があるかどうかを知っているか、必要に応じてこれらの行をスレッド化して中止する必要がありますか（間違いなく私は好きではありませんそれを行うために。）

役に立ちましたか？

解決

単に別のスレッドで正規表現の一致を起動し、特定の最大時間制限に達した場合に中止できるようにする必要があると思います。

他のヒント

Regexbuddyに式を入力すると、次のメッセージが表示されます

  

試合の試みは早期に中止されました   正規表現も   複雑。予定している正規表現エンジン   取り扱いできない場合があります   それとまったくクラッシュします。見上げる   「致命的なバックトラッキング」の中に   これを回避する方法を学ぶためのヘルプファイル   状況。

破局的なバックトラッキングを調べると、次の説明が得られます

  

暴走正規表現：致命的なバックトラッキング
  正規表現（x + x +）+ yを検討してください。   恐怖で叫んで言う前に   この考案された例は   xx + yと書かれて、   ひどく入れ子になっていない同じ   数量詞：各＆quot; x＆quot;   より複雑な何かを表し、   特定の文字列が一致する   両方の「x」。 HTMLのセクションを参照してください   実際の例については、以下のファイルをご覧ください。

     

応募するとどうなるか見てみましょう   xxxxxxxxxxyへのこの正規表現。最初   x +は、10個のx文字すべてに一致します。の   2番目のx +は失敗します。最初のx +その後   9試合までバックトラックし、   2番目は残りのxを取得します。   これでグループが1回一致しました。の   グループは繰り返しますが、最初は失敗します   x +。 1回の繰り返しは   十分な場合、グループは一致します。 y   yに一致し、全体の一致は   見つかりました。正規表現が宣言されています   機能的で、コードは   顧客、および彼のコンピューターが爆発します。   ほぼ。

     

上記の正規表現は、y   件名文字列にありません。   yが失敗すると、正規表現エンジン   バックトラック。グループには1つあります   反復はバックトラックできます。の   2番目のx +は1つのxとのみ一致したため、   バックトラックすることはできません。しかし、最初のx +は   1つのxを放棄します。すぐに2番目のx +   xxに一致します。グループにも1つあります   反復、次の失敗、および   yは失敗します。再びバックトラッキング、   2番目のx +には1つのバックトラックがあります   位置、xに一致するように自身を縮小します。   グループは2回目の反復を試みます。   最初のx +は一致しますが、2番目は   文字列の最後で立ち往生。   バックトラッキング、最初のx +   グループの最初の反復が減少します   7文字まで。 2番目のx +   xxxに一致します。 yの失敗、2番目のx +   xxに、次にxに減少します。今、   グループは2回目の反復に一致する場合があります。   x +ごとに1つのxがあります。でも、これ   （7,1）、（1,1）の組み合わせも失敗します。そう   （6,4）に移動してから（6,2）（1,1）に移動します   そして（6,1）、（2,1）そして   （6,1）、（1,2）そして、あなたが始めると思う   ドリフトを取得します。

     

10x文字列でこの正規表現を試す場合   RegexBuddyのデバッガーでは、   最終的なyを把握するための2558ステップ   不足している。 11xストリングの場合、   5118ステップが必要です。 12のために、それはかかります   10238ステップ。明らかに私たちは   ここでO（2 ^ n）の指数複雑度。   21xでは、デバッガーは2.8でボーアウトします。   百万歩、悪いケースを診断   壊滅的なバックトラッキングの。

     

RegexBuddyはそれを許します   サークルになっていることを検出、および   マッチの試行を中止します。 その他の正規表現   エンジン（.NETなど）は継続します   永遠に、他の人は   スタックオーバーフロー（以前のPerlなど）   バージョン5.10）。スタックオーバーフローは   特にWindowsでは厄介です   彼らはあなたのアプリケーションを作る傾向があります   痕跡や説明なしで消えます。   Webを実行する場合は非常に注意してください   ユーザーが提供できるサービス   独自の正規表現。人   ほとんど正規表現の経験がない   思い付く驚くべきスキル   指数関数的に複雑なレギュラー   式。

コードで処理する必要があると思います。 Regexbuddy の作成者に連絡し、このシナリオを検出するために必要なものを尋ねることをお勧めします。

一般に、正規表現は予想よりも長くかかる場合があります。レギュレーターなどのツールを使用して、正規表現を試す必要があります。

問題は、ネストされた＆quot; loops＆quot;があることです。正規表現では、非常に非効率的になります（そのため、式の複雑さにより基本的には永遠にかかります）。

一致させたいものがあれば、そのためのより効率的な正規表現を見つけることができます。

正規表現の一致が指数関数的に増加する場合のように思えます。 BCLブログをご覧ください。

最善の解決策は、スレッドに手を加えずに、正規表現にタイムアウトを設定することです。

文字列を削除する方法はこちらをご覧くださいタイムアウト。

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