Pisanie wzorców bezpiecznych przed ReDoS

ReDoS (Regular expression Denial of Service) to klasa ataków, w których specjalnie przygotowany ciąg wejściowy powoduje drastyczny wzrost czasu dopasowywania wyrażenia regularnego. Silnik JS używa backtracking (cofania): jeśli wzorzec jest "niejednoznaczny", na pechowym ciągu wejściowym może wykonać wykładniczą liczbę prób.

Klasyczny wzorzec katastrofalny

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

Aby znaleźć dopasowanie, silnik próbuje każdego możliwego podziału liter "a" pomiędzy dwa kwantyfikatory +. Dla 20 liter "a" daje to 2^20 = ~1 milion prób. Dla 30 liter "a" -- miliard.

Inne niebezpieczne przykłady:

• (a*)*b -- "zagnieżdżone gwiazdki".
• (a|a)* -- nakładające się alternatywy.
• (\\w+)+@ -- zachłanne grupy z zewnętrznym kwantyfikatorem.

Jak dostrzec niebezpieczeństwo

Szukaj następujących struktur:

1. Kwantyfikator wewnątrz kwantyfikatora: (...+)+, (...*)*, (...{n,})+.
2. Nakładające się alternatywy pod kwantyfikatorem: (a|ab)*, (\\w|\\d)+.
3. Lookahead/lookbehind z powtarzającymi się złożonymi alternatywami.

Zapis obronny (bezpieczny)

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

Bezpieczna wersja oddziela przypadek bazowy od powtarzanego, eliminując niejednoznaczność. Inne techniki:

• Kwantyfikatory dzierżawcze (a++) -- nieobsługiwane w JS, ale dostępne w innych silnikach.
• Wzorce atomowe ((?>...)) -- brak w JS.
• Ograniczenie długości ciągu wejściowego przed dopasowaniem.
• Limit czasu (timeout) dopasowania (edytor w tym kursie używa workera z limitem 500 ms).

Zalecenia dotyczące tworzenia bezpiecznych wzorców pod kątem ReDoS

1. Upewnij się, że opcje w alternatywie wykluczają się wzajemnie (np. nie używaj (a|a+)).
2. Unikaj stosowania zagnieżdżonych kwantyfikatorów do nakładających się wyrażeń (np. (\\s*)*).
3. Zawsze preferuj specyficzne, zanegowane klasy znaków ([^\\n]*) zamiast ogólnej kropki (.*).

Spróbuj sam

Ćwiczenie powtórzeniowe

Dodatkowe wyzwanie