Backtracking: een overzicht

Wanneer een hebzuchtige kwantor "doorschiet", voert de engine backtracking uit: het doet een stap terug, probeert een andere configuratie, probeert het opnieuw. Op eenvoudige patronen is onzichtbaar; op slecht geschreven patronen kan het exponentieel worden en bevries de browser gedurende seconden. Het is de root van ReDoS (Regular uitdrukking Denial of Service).

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".

De motor komt er altijd wel, maar als er een hebzuchtige kwantificator in zit nog een hebzuchtige kwantificator (bijv. (a+)+), het aantal configuraties proberen kan ontploffen.

Catastrofale patronen

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Geen trailing b → het patroon mislukt, maar om daar te komen probeert de engine alles mogelijke partitie van de as. Exponentiele groei: met 30 as is dat mogelijk uren wachten.

Gevaren van backtracking en ReDoS

Wanneer een patroon overlappende of geneste kwantoren bevat (bijvoorbeeld (a+)+), evalueert de engine een exponentieel aantal paden voordat deze faalt. Het vervangen van generieke jokertekens door het uitsluiten van tekenklassen vermindert de backtracking-paden dramatisch.

Probeer het

Oefening beoordelen

Extra uitdaging