正規表現での壊滅的なバックトラッキング

単純で一見無害な通常のルーチンでシステムを強制終了することは可能ですか？ はい、できます。



例：

>>> r = '(a+)*b'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はい。 無実-ある種のはい。 もちろん、括弧とアスタリスクは不要なので、賢明ではありませんが、機能するはずです。 試してみましょう：

 >>> re.findall('(a+)*b', 'aaaaaab') ['aaaaaa']
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クールで働き、ビールを飲みましょう。



しかし、いや...



探している行に目的のパターンが含まれていない場合、たとえば'aaaaaa'だけの場合、コンパイラは次のアルゴリズムでそれを見つけようとします。



1.すべての流出は「a +」を満たしますが、 「b」 、つまり後退は見当たりません。

2. 「a +」は「aaaaa」 （最後の1つを除くすべて）のみを満たし、後者は繰り返し「*」を満たしますが、 「b」はまだ見つかりません。

3.最初の「a +」は「aaaa」のみを満たし、最後の2個の「aa」は繰り返し「*」 、 「b」を満たします。

4.最初の「a +」は「aaaa 」を満たし、最後から2番目の「a」は1つの繰り返し「*」を満たし、次の「a」は別の繰り返し「*」 、 「b」は存在しません...



さて、あなたは理解しています-などなど。 行の完全検索まで。



いくつかの統計：

 >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*20)", number=1) 0.24741506576538086 >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*22)", number=1) 0.99283289909362793 >>> timeit.timeit("import re; re.findall('(a+)*n', 'a'*24)", number=1) 3.9849259853363037
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、実行時間は指数関数的に増加しています。 大きな文字列の場合、FreeBSD上のPython 2.6はタイムリーにRuntimeErrorをスローしますが、Windowsでは同じPythonがすべての組み合わせを快く検索します。 30文字以上の行はテストすることを敢えてしませんでした:)



この投稿は、今日のstackoverflowの質問と、長く読み忘れていた忘れられていたRunaway Regular Expressions：Catastrophic Backtrackingに触発されました。



PSHabréには、バックトラッキングとアトミックグループに関する記事が既にあり、説明されている問題はより深く、より深刻であると考えられています。 :)