[解決済み] 不正な正規表現を見分けるには？

質問

最近、私は 正規表現によるサービス拒否 攻撃について知り、自分のコードベースからいわゆる「邪悪な」正規表現パターン、少なくともユーザー入力に使用されているパターンをすべて根絶することにしました。で示された例は OWASP リンク と ウィキペディア は役に立ちますが、問題を簡単に説明するのには向いていません。

邪悪な正規表現についての説明、以下より。 wikipedia :

• は、正規表現が複雑な部分式に繰り返し（"+", "*"）を適用しています。
• 繰り返される部分式に対して、他の有効なマッチのサフィックスでもあるマッチが存在します。

の例で、再び ウィキペディア :

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

これは、より単純な説明がないだけの問題なのでしょうか？私は、正規表現を書いているときにこの問題を回避したり、既存のコードベース内でこの問題を見つけることを容易にする何かを探しています。

どのように解決するのですか？

なぜ不正な正規表現が問題なのか？

コンピュータは、たとえそれがあなたの意図したものでなくても、あるいはまったく理不尽なことであっても、あなたが指示したとおりに動くからです。もし、ある与えられた入力に対して、与えられたパターンに一致するものがあるかないかを証明するように正規表現エンジンに要求した場合、エンジンは、どれだけ多くの異なる組み合わせをテストしなければならないとしても、それを実行しようとします。

OP の投稿の最初の例に触発された簡単なパターンを紹介します。

^((ab)*)+$

入力があると

アバババババババババババババババババババババババババババババババババババババッ

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

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

アバババババババババババババババババババババババババババババババババババババッ a

エンジンはまず (abababababababababababab) を試しますが、これは余分な a . これは破滅的なバックトラックを引き起こします。なぜなら私たちのパターン (ab)* はそのキャプチャの1つを解放し（"backtrack"）、外側のパターンに再試行させるからです。正規表現エンジンでは、これは次のようになります。

(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) - いいえ

可能な組み合わせの数は入力の長さに対して指数関数的に増加し、いつの間にか正規表現エンジンはこの問題を解決しようとして、すべての可能な組み合わせを使い果たし、ついに諦めて "There is no match." と報告するまでになり、その間、サーバーは溶けた金属の山と化しています。

不正な正規表現を見分ける方法

これは実はとても厄介なことです。最近の正規表現エンジンにおける破滅的なバックトラックは、その性質上 停止問題 という問題に似ています。 私自身、問題のある正規表現を書いたことがあります。 が何であるか、そしてそれを回避する方法を一般的に知っているにもかかわらず。できる限りのことを 原子グループ でラップすることで、バックトラックの問題を防ぐことができます。これは基本的に、与えられた式を再試行しないように正規表現エンジンに指示するものです。しかし、アトム式はバックトラックを防止しないことに注意してください。 内の でのバックトラックは防げないので ^(?>((ab)*)+)$ はまだ危険ですが ^(?>(ab)*)+$ は安全です (これは (abababababababababababab) にマッチし、マッチした文字を放棄しないので、致命的なバックトラックを防ぐことができます）。

残念ながら、一度書かれた正規表現は、すぐに、あるいは素早く問題のある正規表現を見つけるのは非常に難しいのです。結局のところ 悪い正規表現を認識することは、他の悪いコードを認識するのと同じです。 - 多くの時間と経験、そして/または1つの壊滅的な出来事が必要なのです。

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

正規表現を用いたプログラムのDoS脆弱性の静的検出 静的なDoS脆弱性の検出

Valentin Wüstholz, Oswaldo Olivo, Marijn J. H. Heule, and Isil Dillig

テキサス大学オースティン校