モジュールのレッスン (4/4)
バックトラッキング: 概要
貪欲な量指定子が「オーバーシュート」すると、エンジンは バックトラッキング を実行します。 ステップバックして別の構成を試み、再試行します。単純なパターンでは、 目に見えない。パターンが適切に書かれていない場合、指数関数的になる可能性があり、 ブラウザを数秒間フリーズします。これは ReDoS のルートです (通常 式サービス拒否)。
Pattern: .*\d
Sample: abc123def
Steps:
1. .* consumes everything: "abc123def"
2. \d fails (end of string).
3. Backtrack: .* drops 'f' -> "abc123de", \d fails on 'f'.
4. Backtrack: .* drops 'ef' -> "abc123d", \d fails on 'e'.
5. ... and so on until \d finds a digit: match = "abc123" + "?"... actually
the pattern matches "abc123" because .* leaves "def" and \d looks at '3'? No: the
backtrack continues and .* ends up being "abc12", \d=3. Final match: "abc123".エンジンは常にそこに到達しますが、貪欲な量指定子に次のものが含まれる場合、
別の 貪欲な数量子 (例: (a+)+)、構成の数
しようとすると爆発する可能性があります。
壊滅的なパターン
Pattern: (a+)+b
Sample: aaaaaaaaaaaaaaaaaaaaa末尾に b がない → パターンは失敗しますが、そこに到達するためにエンジンは毎回試行します。
a の可能なパーティション。 指数関数的な成長: 30 a を使用すると、次のことが可能になります。
何時間も待ちます。
バックトラッキングと ReDoS の危険性
パターンに重複またはネストされた量指定子が含まれている場合 ((a+)+ など)、エンジンは失敗する前に指数関数的な数のパスを評価します。一般的なワイルドカードを除外文字クラスに置き換えると、バックトラッキング パスが大幅に減少します。
試してみてください
テキスト内のすべての出現箇所について、角かっこ内のコンテンツを抽出します。後の終了へのジャンプを避けるために、量指定子の遅延バージョンを使用してください。
ヒントを表示
\\[.*?\\] は最初の終了時に停止します ]: 激しいバックトラックはありません。
3 回の試行後に解決策が利用可能になります
復習演習
オプションの `s` には `?` 数量子を、パスの非スペース文字には `\\S+` を使用して、テキスト内のすべての `http://...` または `https://...` URL を検索します。
ヒントを表示
https?は、「http」の後にオプションの「s」が続くことを意味します。次に //、次に \\S+ (スペース以外)。
3 回の試行後に解決策が利用可能になります
追加の課題
Match strings enclosed in double quotes, avoiding excessive backtracking by using the negated class `[^"]*` instead of `.*`.
ヒントを表示
Replace the dot with the negated class [^"] to restrict the engine's backtracking paths.
3 回の試行後に解決策が利用可能になります