Відстеження: огляд

Коли жадібний квантор «виходить за межі», механізм виконує зворотне відстеження: він робить крок назад, пробує іншу конфігурацію, повторює спробу. На простих викрійках нім є невидимим; на погано написаних шаблонах він може стати експоненціальним і заморозити браузер на секунди. Це корінь ReDoS (Regular вираз Відмова в обслуговуванні).

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 → шаблон не вдається, але механізм намагається потрапити туди щоразу можливий розділ as. Експоненціальне зростання: з 30 a ви можете чекати годинами.

Небезпека зворотного відстеження та ReDoS

Якщо шаблон містить квантори, що перекриваються, або вкладені квантифікатори (наприклад, (a+)+), система оцінює експоненціальну кількість шляхів, перш ніж дати збій. Заміна загальних символів підстановки на класи символів, що виключають, значно скорочує шляхи зворотного відстеження.

Спробуйте

Повторна вправа

Додатковий виклик