ReDoS-veilige patronen schrijven

ReDoS (Regular expression Denial of Service) is een klasse aanvallen waarbij een zorgvuldig vervaardigde invoer zorgt ervoor dat de matchingtijd van een regex explodeert. De JS-engine gebruikt backtracking: als een patroon "dubbelzinnig" is, op een ongelukkige invoer kan het een exponentieel aantal pogingen uitvoeren.

Het klassieke catastrofale patroon

Pattern: ^(a+)+$
Input:   "aaaaaaaaaaaaaaaaaaaaab"

Om dit te matchen probeert de engine elke mogelijke partitie van "a" ertussen de twee + kwantoren. Op 20 "a"s zijn dat 2^20 = ~1 miljoen pogingen. Op 30 "a"s, een miljard.

Andere gevaarlijke voorbeelden:

• (a*)*b -- "geneste sterren".
• (a|a)* -- overlappende alternatieven.
• (\w+)+@ -- hebzuchtige groepen met een uiterlijke kwantor.

Hoe het gevaar te herkennen

Zoek naar deze structuren:

1. Kwantificeerder binnen een kwantificator: (...+)+, (...*)*, (...{n,})+.
2. Overlappende alternatieven onder een kwantor: (a|ab)*, (\w|\d)+.
3. Lookahead/lookbehind met complexe alternatieven herhaald.

Defensieve herschrijving

Dangerous:  ^(\w+\s+)+$
Safe:       ^(?:\w+\s+)*\w+$

De veilige versie scheidt het basisgeval van het herhaalde geval en verwijdert het de dubbelzinnigheid. Andere technieken:

• Bezittelijke kwantoren (a++) -- niet ondersteund in JS, maar beschikbaar in andere zoekmachines.
• Atomische patronen ((?>...)) -- niet in JS.
• Beperk de lengte van de invoer voordat deze wordt gekoppeld.
• Time-out bij matching (de editor van deze cursus gebruikt een worker met een time-out van 500 ms).

Aanbevelingen voor ReDoS-veilige patronen

1. Zorg ervoor dat afwisselende opties elkaar uitsluiten (gebruik bijvoorbeeld niet (a|a+)).
2. Vermijd het toepassen van geneste kwantoren op overlappende uitdrukkingen (bijvoorbeeld (\\s*)*).
3. Geef altijd de voorkeur aan specifieke genegeerde tekenklassen ([^\\n]*) boven de algemene jokertekens (.*).

Probeer het

Oefening beoordelen

Extra uitdaging