Jak rozpoznać zły regex?

Niedawno dowiedziałem się o atakach Denial of Service za pomocą wyrażeń regularnych i zdecydowałem się wykorzenić tak zwane „złe” wzorce regex, gdziekolwiek mogłem je znaleźć w mojej bazie kodu - lub przynajmniej te, które są używane podczas wprowadzania danych przez użytkownika. Przykłady podane pod linkiem OWASP powyżej i Wikipedii są pomocne, ale nie radzą sobie z wyjaśnianiem problemu w prostych słowach.

Opis złych wyrażeń regularnych z wikipedii :

• wyrażenie regularne stosuje powtórzenie („+”, „*”) do złożonego wyrażenia podrzędnego;
• w przypadku powtarzanego wyrażenia podrzędnego istnieje dopasowanie, które jest również sufiksem innego prawidłowego dopasowania.

Z przykładami, ponownie z wikipedii :

• (a+)+
• ([a-zA-Z]+)*
• (a|aa)+
• (a|a?)+
• (.*a){x} dla x> 10

Czy jest to problem, którego po prostu nie ma prostszego wyjaśnienia? Szukam czegoś, co ułatwiłoby ominięcie tego problemu podczas pisania wyrażeń regularnych lub znalezienie ich w istniejącej bazie kodu.

Dlaczego złe reguły są problemem?

Ponieważ komputery robią dokładnie to, co im każesz, nawet jeśli nie o to ci chodziło lub jest to całkowicie nierozsądne. Jeśli poprosisz silnik Regex o udowodnienie, że dla pewnych danych wejściowych istnieje lub nie pasuje do danego wzorca, silnik spróbuje to zrobić bez względu na to, ile różnych kombinacji musi zostać przetestowanych.

Oto prosty wzór inspirowany pierwszym przykładem w poście OP:

^((ab)*)+$

Biorąc pod uwagę dane wejściowe:

abababababababababababab

Silnik wyrażeń regularnych próbuje czegoś podobnego (abababababababababababab)i dopasowanie zostaje znalezione za pierwszym razem.

Ale potem wrzucamy klucz do małpy:

abababababababababababab a

Silnik najpierw spróbuje, (abababababababababababab)ale to się nie powiedzie z powodu tego dodatkowego a. Powoduje to katastrofalne śledzenie nawiasów, ponieważ nasz wzorzec (ab)*, w dobrej wierze, zwolni jedno ze swoich przechwyceń („cofnie się”) i pozwoli zewnętrznemu wzorowi spróbować ponownie. W przypadku naszego silnika wyrażeń regularnych wygląda to mniej więcej tak:

(abababababababababababab)- Nie
(ababababababababababab)(ab)- Nie
(abababababababababab)(abab)- Nie
(abababababababababab)(ab)(ab)- Nie
(ababababababababab)(ababab)- Nie
(ababababababababab)(abab)(ab)- Nie
(ababababababababab)(ab)(abab)- Nie
(ababababababababab)(ab)(ab)(ab)- Nie
(abababababababab)(abababab)- Nie
(abababababababab)(ababab)(ab)- Nie
(abababababababab)(abab)(abab)- Nie
(abababababababab)(abab)(ab)(ab)- Nie
(abababababababab)(ab)(ababab)- Nie
(abababababababab)(ab)(abab)(ab)- Nie
(abababababababab)(ab)(ab)(abab)- Nie
(abababababababab)(ab)(ab)(ab)(ab)- Nie
(ababababababab)(ababababab)- Nie
(ababababababab)(abababab)(ab)- Nie
(ababababababab)(ababab)(abab)- Nie
(ababababababab)(ababab)(ab)(ab)- Nie
(ababababababab)(abab)(abab)(ab)- Nie
(ababababababab)(abab)(ab)(abab)- Nie
(ababababababab)(abab)(ab)(ab)(ab)- Nie
(ababababababab)(ab)(abababab)- Nie
(ababababababab)(ab)(ababab)(ab)- Nie - Nie - Nie
(ababababababab)(ab)(abab)(abab)- Nie
(ababababababab)(ab)(abab)(ab)(ab)- Nie
(ababababababab)(ab)(ab)(ababab)- Nie
(ababababababab)(ab)(ab)(abab)(ab)- Nie
(ababababababab)(ab)(ab)(ab)(abab)- Nie
(ababababababab)(ab)(ab)(ab)(ab)(ab)- Nie
                              ...
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab) - Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)(ab)- Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab)- Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab)- Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)- Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)- Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)- Nie
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)- Nie - Nie

Liczba możliwych kombinacji skaluje się wykładniczo wraz z długością danych wejściowych i zanim się zorientujesz, silnik wyrażeń regularnych pochłania wszystkie zasoby systemowe, próbując rozwiązać ten problem, aż po wyczerpaniu wszystkich możliwych kombinacji terminów w końcu się poddaje i raporty „Brak dopasowania”. W międzyczasie twój serwer zamienił się w płonący stos stopionego metalu.

Jak rozpoznać złe reguły

W rzeczywistości jest to bardzo trudne. Sam napisałem kilka, chociaż wiem, czym one są i ogólnie, jak ich unikać. Zobacz, jak Regex zajmuje zaskakująco dużo czasu . Zawinięcie wszystkiego, co się da, w grupę atomową może pomóc w zapobieganiu problemowi ze śledzeniem. Zasadniczo mówi silnikowi regex, aby nie wracał do danego wyrażenia - „zablokuj wszystko, co dopasowałeś za pierwszym razem”. Należy jednak pamiętać, że wyrażenia atomowe nie zapobiegają cofaniu się w wyrażeniu, więc ^(?>((ab)*)+)$nadal są niebezpieczne, ale ^(?>(ab)*)+$są bezpieczne (dopasują się, (abababababababababababab)a następnie odmówią porzucenia któregokolwiek z dopasowanych znaków, zapobiegając w ten sposób katastrofalnym cofnięciom).

Niestety, po napisaniu bardzo trudno jest od razu lub szybko znaleźć problematyczne wyrażenie regularne. Ostatecznie rozpoznanie złego wyrażenia regularnego jest jak rozpoznanie każdego innego złego kodu - zajmuje dużo czasu i doświadczenia i / lub pojedynczego katastrofalnego zdarzenia.

Co ciekawe, odkąd ta odpowiedź została napisana po raz pierwszy, zespół z University of Texas w Austin opublikował artykuł opisujący rozwój narzędzia zdolnego do przeprowadzania statycznej analizy wyrażeń regularnych w wyraźnym celu znalezienia tych „złych” wzorców. Narzędzie zostało opracowane do analizy programów Java, ale podejrzewam, że w nadchodzących latach zobaczymy więcej narzędzi opracowanych do analizy i wykrywania problematycznych wzorców w JavaScript i innych językach, zwłaszcza w miarę wzrostu liczby ataków ReDoS .

Statyczne wykrywanie luk w zabezpieczeniach DoS w programach używających wyrażeń regularnych
Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule i Isil Dillig
The University of Texas at Austin

To, co nazywasz „złym” wyrażeniem regularnym, jest wyrażeniem regularnym, które wykazuje katastrofalne cofanie się . Podlinkowana strona (którą napisałem) szczegółowo wyjaśnia koncepcję. Zasadniczo katastroficzne cofanie się ma miejsce, gdy wyrażenie regularne nie pasuje i różne permutacje tego samego wyrażenia regularnego mogą znaleźć częściowe dopasowanie. Silnik wyrażeń regularnych następnie wypróbowuje wszystkie te permutacje. Jeśli chcesz przejrzeć swój kod i sprawdzić swoje wyrażenia regularne, oto 3 kluczowe kwestie, którym należy się przyjrzeć:

1. Alternatywy muszą się wzajemnie wykluczać. Jeśli wiele alternatyw może pasować do tego samego tekstu, silnik spróbuje obu, jeśli pozostała część wyrażenia regularnego zawiedzie. Jeśli alternatywy są w grupie, która się powtarza, masz katastrofalne cofanie się. Klasycznym przykładem jest (.|\s)*dopasowanie dowolnej ilości dowolnego tekstu, gdy styl wyrażenia regularnego nie ma trybu „kropka pasuje do podziałów wiersza”. Jeśli jest to część dłuższego wyrażenia regularnego, to ciąg tematu z wystarczająco długim ciągiem spacji (dopasowanym przez oba .i \s) przerwie wyrażenie regularne. Poprawka polega na (.|\n)*tym, że alternatywy wzajemnie się wykluczają, a nawet lepiej, aby były bardziej szczegółowe, które znaki są naprawdę dozwolone, na przykład [\r\n\t\x20-\x7E]dla materiałów do wydrukowania ASCII, zakładek i podziałów wierszy.

2. Skwantyfikowane tokeny, które występują w kolejności, muszą się wzajemnie wykluczać lub wykluczać to, co występuje między nimi. W przeciwnym razie oba mogą dopasować ten sam tekst, a wszystkie kombinacje dwóch kwantyfikatorów zostaną wypróbowane, gdy pozostała część wyrażenia regularnego nie pasuje. Klasycznym przykładem jest a.*?b.*?cdopasowanie 3 rzeczy z „czymkolwiek” między nimi. Kiedy cnie można dopasować, pierwsza .*?będzie rozszerzana znak po znaku do końca linii lub pliku. Przy każdym rozwinięciu druga .*?będzie rozszerzać znak po znaku, aby dopasować pozostałą część wiersza lub pliku. Rozwiązaniem jest uświadomienie sobie, że nie możesz mieć „niczego” między nimi. Pierwszy bieg musi się kończyć, ba drugi bieg musi się kończyć c. Z pojedynczymi znakamia[^b]*+b[^c]*+cto łatwe rozwiązanie. Ponieważ zatrzymujemy się teraz na separatorze, możemy użyć kwantyfikatorów zaborczych, aby jeszcze bardziej zwiększyć wydajność.

3. Grupa, która zawiera token z kwantyfikatorem, nie może mieć własnego kwantyfikatora, chyba że skwantyfikowany token wewnątrz grupy może być dopasowany tylko do czegoś innego, co wzajemnie się z nim wyklucza. Gwarantuje to, że nie ma możliwości, aby mniej iteracji zewnętrznego kwantyfikatora z większą liczbą iteracji kwantyfikatora wewnętrznego mogło dopasować ten sam tekst, co więcej iteracji kwantyfikatora zewnętrznego z mniejszą liczbą iteracji kwantyfikatora wewnętrznego. To jest problem zilustrowany w odpowiedzi JDB.

Podczas pisania odpowiedzi zdecydowałem, że zasługuje na pełny artykuł na mojej stronie . To jest teraz również online.

Podsumowałbym to jako „powtórzenie powtórzenia”. Pierwszy podany przez Ciebie przykład jest dobry, ponieważ stwierdza, że ​​„litera a, raz lub więcej razy z rzędu. Może się to powtórzyć raz lub więcej razy z rzędu”.

W tym przypadku należy szukać kombinacji kwantyfikatorów, takich jak * i +.

Nieco bardziej subtelną rzeczą, na którą należy zwrócić uwagę, jest trzecia i czwarta rzecz. Te przykłady zawierają operację OR, w której obie strony mogą być prawdziwe. To w połączeniu z kwantyfikatorem wyrażenia może spowodować WIELE potencjalnych dopasowań w zależności od ciągu wejściowego.

Podsumowując, w stylu TLDR:

Uważaj, jak używane są kwantyfikatory w połączeniu z innymi operatorami.

Zaskakująco spotkałem się z ReDOSem kilka razy wykonującym recenzje kodu źródłowego. Jedną rzeczą, którą zalecałbym, jest użycie limitu czasu z dowolnym silnikiem wyrażeń regularnych, którego używasz.

Na przykład w C # mogę utworzyć wyrażenie regularne z TimeSpanatrybutem.

string pattern = @"^<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)$";
Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0));
try
{
    string noTags = regexTags.Replace(description, "");
    System.Console.WriteLine(noTags);
} 
catch (RegexMatchTimeoutException ex)
{
    System.Console.WriteLine("RegEx match timeout");
}

To wyrażenie regularne jest podatne na odmowę usługi i bez limitu czasu będzie obracać i zużywać zasoby. Po przekroczeniu limitu czasu wyrzuci on RegexMatchTimeoutExceptionpo określonym czasie i nie spowoduje użycia zasobów, co doprowadzi do stanu Denial of Service.

Będziesz chciał poeksperymentować z wartością limitu czasu, aby upewnić się, że działa ona w Twoim przypadku.

Wykrywanie złych wyrażeń regularnych

1. Wypróbuj RegexStaticAnalysis Nicolaasa Weidemana projekt .
2. Wypróbuj mój detektor vuln-regex -style, który ma CLI dla narzędzia Weideman i innych.

Reguły kciuka

Złe wyrażenia regularne są zawsze spowodowane niejednoznacznością w odpowiednim NFA, które można wizualizować za pomocą narzędzi takich jak regexper .

Oto kilka form niejasności. Nie używaj ich w swoich wyrażeniach regularnych.

1. Zagnieżdżanie kwantyfikatorów, takich jak (a+)+(aka „wysokość gwiazdy> 1”). Może to spowodować wykładniczy wybuch. Zobacz safe-regexnarzędzie substack .
2. Określone ilościowo nakładające się dysjunkcje, takie jak (a|a)+. Może to spowodować wykładniczy wybuch.
3. Unikaj ilościowo nakładających się przyległości, takich jak \d+\d+. Może to spowodować wybuch wielomianu.

Dodatkowe zasoby

Napisałem ten artykuł o superliniowych wyrażeniach regularnych. Zawiera mnóstwo odniesień do innych badań związanych z wyrażeniami regularnymi.

Powiedziałbym, że jest to związane z używanym silnikiem regex. Nie zawsze możesz uniknąć tego typu wyrażeń regularnych, ale jeśli Twój silnik wyrażeń regularnych jest poprawnie zbudowany, jest to mniejszy problem. Zobacz tę serię blogów aby uzyskać wiele informacji na temat silników wyrażeń regularnych.

Zwróć uwagę na zastrzeżenie na dole artykułu, że cofanie jest problemem NP-Complete. Obecnie nie ma sposobu, aby efektywnie je przetworzyć i możesz chcieć zabronić ich wprowadzania.

Nie sądzę, abyś mógł rozpoznać takie wyrażenia regularne, a przynajmniej nie wszystkie z nich lub nie, bez restrykcyjnego ograniczenia ich ekspresji. Jeśli naprawdę zależy ci na ReDoS, spróbuję je sandboxować i zabić ich przetwarzanie z przekroczeniem limitu czasu. Może się również zdarzyć, że istnieją implementacje RegEx, które pozwalają ograniczyć ich maksymalną ilość wycofywania.

Jest kilka sposobów, o których mogę pomyśleć, że można zaimplementować pewne reguły upraszczające, uruchamiając je na małych wejściach testowych lub analizując strukturę wyrażenia regularnego.

• (a+)+ można zredukować za pomocą jakiejś reguły zastępującej redundantne operatory do just (a+)
• ([a-zA-Z]+)* można by również uprościć dzięki naszej nowej zasadzie łączenia nadmiarowości do ([a-zA-Z]*)

Komputer mógłby uruchamiać testy, uruchamiając małe podwyrażenia wyrażenia regularnego względem losowo generowanych sekwencji odpowiednich znaków lub sekwencji znaków i sprawdzając, do jakich grup się one wszystkie kończą. W pierwszym przypadku komputer jest taki, hej wyrażenie regularne chce a, więc spróbujmy 6aaaxaaq. Następnie widzi, że wszystkie „piątki” i tylko pierwsza grupa kończą się w jednej grupie, i dochodzi do wniosku, że bez względu na to, ile zostanie postawionych „piątków”, nie będzie to miało znaczenia, ponieważ +dostaje wszystko w grupie. Drugi jest taki, że hej, wyrażenie regularne chce kilku liter, więc spróbujmy z nimi -fg0uj=, a potem zobaczy, że znowu każda paczka jest w jednej grupie, więc pozbywa się+ na końcu.

Teraz potrzebujemy nowej reguły do ​​obsługi następnych: Reguła eliminacji nieistotnych opcji.

• Ze (a|aa)+komputer spogląda na niego i jest jak lubimy tego wielkiego drugim, ale możemy użyć tego pierwszy wypełnić więcej luk, pozwala uzyskać ans wiele AA jak możemy, i zobaczyć, czy możemy dostać coś innego kiedy skończymy. Mógłby uruchomić go z innym ciągiem testowym, takim jak „eaaa @ a ~ aa”. aby to ustalić.

• Możesz się przed tym uchronić (a|a?)+ , każąc komputerowi zdać sobie sprawę, że ciągi są dopasowane przeza? nie są droidami, których szukamy, ponieważ ponieważ zawsze mogą pasować wszędzie, decydujemy, że nie lubimy rzeczy (a?)+, i wyrzucamy je.

• Chronimy przed (.*a){x}tym, aby zdać sobie sprawę, że postacie pasują doa zostałyby już złapane przez .*. Następnie wyrzucamy tę część i używamy innej reguły, aby zastąpić nadmiarowe kwantyfikatory w(.*){x} .

Chociaż wdrożenie takiego systemu byłoby bardzo skomplikowane, to jest to skomplikowany problem i może być konieczne skomplikowane rozwiązanie. Powinieneś także użyć technik, które inni ludzie przynieśli, na przykład zezwalanie wyrażeniu regularnemu tylko na pewną ograniczoną ilość zasobów wykonawczych przed zabiciem go, jeśli nie zakończy się.