前のトピックでは、正規表現を機能させ、自分のPCでパフォーマンスを向上させようとする人の視点から、具体的な例を用いて壊滅的なバックトラックについて説明しました。このトピックを読む前に、これらの例を理解しておく必要があります。

自分のPCで壊滅的なバックトラックが発生すると迷惑です。しかし、複数の同時ユーザーがいるサーバーアプリケーションで発生すると、本当に壊滅的になる可能性があります。壊滅的なバックトラックを引き起こす正規表現を実行するユーザーが多すぎると、サーバー全体がダウンします。そして、「多すぎる」は、サーバーのCPUコア数程度である必要があるだけです。

サーバーがユーザーからの正規表現を受け入れる場合、ユーザーは任意の対象に対して壊滅的なバックトラックを引き起こす正規表現を簡単に提供できます。サーバーがユーザーからの対象データを受け入れる場合、それらの正規表現が壊滅的なバックトラックを起こしやすい場合、ユーザーはサーバーで使用される正規表現で壊滅的なバックトラックをトリガーする対象を提供できる可能性があります。ユーザーがこれらのいずれかを行うことができる場合、サーバーは正規表現サービス拒否（ReDoS）の影響を受けやすくなります。十分なユーザー（または多くのユーザーを装った1人のアクター）が悪意のある正規表現や、照合する対象を提供すると、サーバーはそれらの正規表現を照合しようとして、CPUサイクルのほとんどすべてを費やすことになります。

ユーザーが提供する正規表現の処理

アプリケーションでユーザーが独自の正規表現を提供できるようにする場合、実際的な唯一の防御策は、テキスト指向の正規表現エンジンを使用することです。これらのエンジンはバックトラックを行いません。そのパフォーマンスは、正規表現の複雑さではなく、対象文字列の長さに依存します。しかし、それらは、バックトラックに依存し、多くのユーザーが期待する後方参照のような機能もサポートしていません。

アプリケーションがユーザー提供の正規表現でバックトラックエンジンを使用する場合、壊滅的なバックトラックの結果を軽減することしかできません。そして、本当にそうする必要があります。正規表現のスキルが限られている人が、誤って壊滅的なバックトラックに陥るものを簡単に作成してしまう可能性があります。

スクリプトがクラッシュしたり、OSが強制終了したりするまで実行するのではなく、壊滅的なバックトラックが発生した場合に照合試行を中止する正規表現エンジンを使用する必要があります。これは簡単にテストできます。正規表現(x\w{1,10})+yが、増え続ける文字列xで試行された場合、正規表現エンジンが諦めるまでにかかる時間に合理的な制限があるはずです。理想的には、エンジンでこの制限を目的のために構成できるようにする必要があります。たとえば、.NETエンジンでは、Regex()コンストラクターにタイムアウトを渡すことができます。PCREエンジンでは、再帰制限を設定できます。制限が低いほど、ReDoSに対する保護は優れていますが、わずかな時間を与えられれば有効な一致を見つけることができたであろう正当な正規表現を中断するリスクが高くなります。低い再帰制限は、長い正規表現の一致を妨げる可能性があります。低いタイムアウトは、大きなファイルの検索を早すぎる段階で中断する可能性があります。

正規表現エンジンにそのような機能がない場合は、独自のタイムアウトを実装できます。別のスレッドを生成して、正規表現を実行します。タイムアウト付きでスレッドを待機します。待機がタイムアウトする前にスレッドが終了した場合は、その結果を処理します。それ以外の場合は、スレッドを強制終了し、正規表現が複雑すぎることをユーザーに伝えます。safe_regexpパッケージは、これをRuby用に実装しています。

アプリケーション内の正規表現のレビュー

サーバーがアプリケーションにハードコードされた正規表現のみを使用する場合、正規表現ベースのサービス拒否攻撃を完全に防止できます。正規表現が使用されている対象に関係なく、正規表現が壊滅的なバックトラックを起こさないようにする必要があります。これは、正規表現をしっかりと理解している人にとっては特に難しいことではありません。しかし、注意と配慮が必要です。正規表現が有効な対象と一致することをテストするだけでは十分ではありません。対象データとは無関係に正規表現を調べることで、同じ正規表現の複数の順列が同じものと一致することがないことを確認する必要があります。

順列は、正規表現に選択肢を与えるときに発生します。代替と量指定子を使用してこれを行うことができます。したがって、これらは検査する必要がある正規表現トークンです。所有格量指定子はバックトラックしないため、除外されます。

代替

代替は相互に排他的である必要があります。複数の代替が同じテキストと一致できる場合、正規表現の残りの部分が失敗すると、エンジンは両方を試行します。代替が繰り返されるグループにある場合、壊滅的なバックトラックが発生します。

典型的な例は(.|\s)*正規表現のフレーバーに「ドットは改行に一致する」モードがない場合に、任意の量の任意のテキストを照合することです。これが長い正規表現の一部である場合、十分な長さのスペースが続く対象文字列は、正規表現を壊します。エンジンは、.または\sで一致するスペースの可能なすべての組み合わせを試行します。たとえば、3つのスペースは次のように一致する可能性があります。..., ..\s, .\s., .\s\s, \s.., \s.\s, \s\s.、または\s\s\s。これは2^N順列です。修正は、(.|\n)*を使用して、代替を相互に排他的にすることです。許可されている文字をより具体的に指定する方がさらに良いでしょう。たとえば、[\r\n\t\x20-\x7E]*ASCII印刷可能文字、タブ、改行の場合です。

2つの代替が同じテキストに部分的に一致することは許容されます。[0-9]*\.[0-9]+|[0-9]+オプションの整数部とオプションの小数部を持つ浮動小数点数を一致させるのは完全に問題ありません。ただし、数字のみで構成される対象は、最初に[0-9]*で一致し、\.が失敗すると、多少のバックトラックが発生しますが、このバックトラックは壊滅的になることはありません。これを長い正規表現のグループ内に入れたとしても、グループは最小限のバックトラックのみを行います（ただし、グループに量指定子がない必要があります。そうしないと、ネストされた量指定子のルールに違反します）。

シーケンス内の量指定子

シーケンス内の量指定されたトークンは、相互に排他的であるか、それらの間にあるものと相互に排他的である必要があります。それ以外の場合、両方が同じテキストに一致する可能性があり、正規表現の残りの部分が一致に失敗すると、2つの量指定子のすべての組み合わせが試行されます。代替を持つグループ内のトークンは、グループの前または後のトークンとまだシーケンス内にあります。

典型的な例はa.*?b.*?cを使用して、それらの間に「何か」を挟んで3つのものを照合します。cを照合できない場合、最初の.*?は、行またはファイルの終わりまで文字ごとに展開します。各拡張について、2番目の.*?は、行またはファイルの残りの部分に一致するように文字ごとに展開します。修正は、それらの間に「何か」を挟むことができないことを理解することです。最初の実行はbで停止する必要があり、2番目の実行はcで停止する必要があります。単一の文字を使用する場合a[^b]*b[^c]*cが簡単な解決策です。否定された文字クラスは、繰り返しが区切り文字で停止することを保証します。正規表現フレーバーが所有格量指定子をサポートしている場合は、a[^b]*+b[^c]*+cを使用して、パフォーマンスをさらに向上させることができます。

より複雑な例と解決策については、前のトピックの完全なHTMLファイルの照合を参照してください。これは、より複雑な状況でバックトラッキングを防ぐために、アトミックグループ化をどのように使用できるかを説明しています。

ネストされた量指定子

量指定子を持つトークンを含むグループは、グループ内の量指定されたトークンが、それと相互に排他的な何かとしか一致できない場合を除き、独自の量指定子を持ってはなりません。これにより、内部の量指定子の反復回数を増やした外側の量指定子の反復回数が少ない場合と、内部の量指定子の反復回数を減らした外側の量指定子の反復回数が多い場合とで、同じテキストに一致する方法がないことが保証されます。

正規表現(x\w{1,10})+yは、xで始まり、その後に1〜10個の単語文字が続き、すべてyが続く1つ以上のコードのシーケンスに一致します。 yが一致する限り、すべてうまくいきます。 yがない場合、バックトラッキングが発生します。文字列にxが多すぎない場合は、バックトラッキングは非常に迅速に発生します。主題にxの長いシーケンスが含まれている場合にのみ、事態は破滅的になります。xとxは相互に排他的ではありません。したがって、反復されるグループはxxxxを1回の反復でx\w\w\wと一致させることも、2回の反復でx\wx\w.

と一致させることもできます。これを解決するには、まずxとyを除外すると、ほとんどのバックトラッキングが解消されます。残ったものは破滅的ではありません。文字クラスの減算を使用して、次のように除外できます。xを含めることを許可すべきかどうかを検討する必要があります。(x[\w-[x]]{1,10})+yまたは、文字クラスの積集合を使用して、次のように除外できます。(x[\w&&[^x]]{1,10})+y。これらの機能がない場合は、許可する文字を明示する必要があります。(x[a-wyz0-9_]{1,10})+y.

の場合xを許可する必要がある場合は、yを同じように禁止するしか解決策はありません。その後、バックトラッキングを排除するために、グループをアトミックにするか、量指定子を所有的にすることができます。

両方xとyを1〜10文字のシーケンスで許可する必要がある場合は、正規表現のみの解決策はありません。グループをアトミックにしたり、量指定子を所有的にしたりすることはできません。なぜなら、その場合、\w{1,10}が最後のyに一致し、その結果、yが失敗するためです。

その他の防御テクニック

上記で説明した破滅的なバックトラッキングを防止することに加えて、正規表現をできる限り厳密に記述する必要があります。正規表現が厳密であればあるほど、バックトラッキングが少なくなり、パフォーマンスが向上します。正規表現が短い文字列でまれに使用されるため、パフォーマンスの違いを測定できない場合でも、適切なテクニックは習慣です。また、経験の浅い開発者が後で正規表現を拡張するときに、破滅的なバックトラッキングを導入する可能性も低くなります。

選択肢を含むグループは、できる限りアトミックにしてください。\b(?>one|two|three)\bを使用して、単語のリストに一致させます。

量指定子をできる限り所有的にしてください。反復されるトークンが後続のものと相互に排他的である場合は、所有的な量指定子でそれを強制します。

ドットの代わりに、（否定された）文字クラスを使用します。本当に「何でも」許可したいということはまれです。たとえば、二重引用符で囲まれた文字列には「何でも」を含めることはできません。エスケープされていない二重引用符を含めることはできません。したがって、"[^"\n]*+"を代わりに".*?"使用してください。両方とも単独で使用した場合はまったく同じ一致を見つけますが、後者はより長い正規表現に貼り付けると、破滅的なバックトラッキングにつながる可能性があります。前者は、正規表現が他に一致させる必要のあるものに関係なく、決してバックトラックしません。

なぜ正規表現を使用するのか？

上記は、正規表現が危険であり、使用すべきではないことを示しているだけだと主張する人もいるでしょう。彼らは、開発者に手続き型コードでジョブを実行することを強制するでしょう。自明でないパターンに一致する手続き型コードは、すぐに長くて複雑になり、バグの可能性とコードの開発と保守のコストが増加します。多くのパターンマッチングの問題は、再帰によって自然に解決されます。そして、大きな主題の文字列が一致しない場合、暴走した再帰は、アプリケーションをクラッシュさせるスタックオーバーフローにつながります。

開発者は、ツールを正しく使用することを学ぶ必要があります。これは、正規表現も他のものと変わりません。