Skip to main content

Testuj Regex

Polski

Testuj wyrażenia regularne z podświetlaniem dopasowań.

Wszystkie obliczenia wykonywane są lokalnie w przeglądarce. Dane nie są wysyłane na serwer.

Wyniki mają charakter informacyjny. Potwierdź je w innych źródłach.

Dwudziestosześcioznakowy ciąg potrafi potrzebować 368 ms, żeby nie dopasować się do złego wzorca

Wyrażenia regularne zwykle działają w czasie proporcjonalnym do wejścia. Zagnieźdź kwantyfikator wewnątrz kwantyfikowanej grupy, a przestaje to być prawdą: /^(a+)+$/ potrzebuje około 23 ms na odrzucenie 22 znaków, 95 ms na 24 i 368 ms na 26. Każdy dodatkowy znak mniej więcej podwaja pracę, więc nieco dłuższe wejście nie spowalnia dopasowania — ono sprawia, że dopasowanie się nie kończy.

Jak to działa

  • Sprawdza wzorzec na przykładowym tekście i pokazuje każde dopasowanie wraz z grupami przechwytującymi.
  • Wyjaśnia, co robi każda część wyrażenia, bo składnia jest z założenia gęsta.
  • Pozwala wypróbować przypadki niedopasowane, a to właśnie w nich mieszkają problemy wydajnościowe.
niebezpieczny kształt: kwantyfikator wewnątrz kwantyfikowanej grupy
  (a+)+   (a*)*   (a|a)*   (\d+)+

n znaków da się rozdzielić między grupy na wykładniczo wiele sposobów,
a silnik musi wypróbować wszystkie, zanim zgłosi brak dopasowania

bezpieczny odpowiednik: a+   — jeden kwantyfikator, czas liniowy

Przykład z liczbami

Pomiar /^(a+)+$/ na ciągach liter a zakończonych pojedynczym znakiem !, których dopasować się nie da.

  1. 22 znaki → około 23 ms
  2. 24 znaki → około 95 ms
  3. 26 znaków → około 368 ms
  4. te same 26 liter a bez znaku ! → dopasowanie poniżej 0,01 ms
  5. bezpieczna postać /^a+$/ na 100 000 znaków → 0,12 ms

Odrzucenie 26 znaków kosztuje trzy tysiące razy więcej niż przyjęcie 100 000. Sukces jest natychmiastowy, a porażka wykładnicza, i dlatego to nigdy nie wychodzi w testach — ścieżka pozytywna zawsze jest szybka.

Jak czytać wynik

  • To wektor odmowy usługi wszędzie tam, gdzie dane użytkownika trafiają do wzorca. Atakujący nie potrzebuje długiego ciągu; trzydzieści albo czterdzieści znaków wystarczy, by zająć wątek żądania na minuty, a garść takich żądań kładzie serwer.
  • Naprawą jest niemal zawsze usunięcie zagnieżdżenia, a nie optymalizowanie wokół niego. (a+)+ oraz a+ dopasowują dokładnie ten sam język, więc podatna wersja nie daje absolutnie nic — to pomyłka, a nie kompromis.
  • Pomiary pochodzą z jednej maszyny i różnią się między silnikami, ale kształt zjawiska nie. Każda implementacja z nawrotami — JavaScript, Python, Java, PCRE — zachowuje się tak samo. RE2 i regexp z Go nie, bo odmawiają obsługi funkcji, które to umożliwiają.
  • Testuj wzorce na danych, które się nie dopasowują, a nie tylko na tych, które pasują. Przypadek katastrofalny pojawia się wyłącznie wtedy, gdy silnik musi wyczerpać wszystkie możliwości, zanim stwierdzi brak dopasowania.

Częste pytania

Jak poznać, że mój wzorzec jest podatny?
Szukaj kwantyfikatora wewnątrz kwantyfikowanej grupy — (a+)+, (a*)*, (\d+)* i podobnych — oraz alternatyw, których gałęzie mogą dopasować ten sam tekst. Potem przetestuj długim ciągiem, który PRAWIE pasuje, bo to bliskie chybienia uruchamiają ścieżkę wykładniczą.
Dlaczego jest szybko przy dopasowaniu, a wolno przy jego braku?
Bo silnik może zatrzymać się na pierwszym sukcesie, ale musi wyczerpać wszystkie możliwości, zanim ogłosi porażkę. Przy zagnieżdżonych kwantyfikatorach liczba możliwości podwaja się z każdym znakiem, więc przypadek niedopasowany jest jedynym, który kiedykolwiek zostaje przejrzany do końca.

Źródła