Zabezpieczanie wprowadzania wyrażeń regularnych przez użytkownika przed atakami

9

Mam świadomość odmowy wyrażenia regularnego usługi (ReDoS). Czy jest jakiś rozsądny sposób, aby pozwolić użytkownikom na tworzenie niestandardowych wyrażeń regularnych, gwarantując jednocześnie, że nie przesyłają oni wykładniczo wolnego wzoru?

regular-expressions icirellik
źródło
Brakuje ci szczegółów. Platforma, wykorzystanie itp.
whatsisname
8
Zamiast próbować uniknąć przesyłania przez użytkownika złych wyrażeń regularnych, być może rozwiązaniem, w którym po pewnym czasie anulujesz wykonanie?
Samuel

Odpowiedzi:

8

Problemem z wyrażeniami regularnymi nie jest sam regex, ale silnik regex, który ma wszystkie „wygodne” funkcje, takie jak cofanie. Dlatego unika się używania silnika regex bez tych funkcji.

Wyrażenia regularne koncepcję informatyki można zawsze dopasować w czasie liniowym po skompilowaniu ich do skończonej maszyny stanów. Tak więc silnik Regex oparty na maszynie stanów nie może być używany do ReDoS. Jednak niezbędne maszyny stanów mogą stać się dość duże w przykładach patologicznych. Ale ograniczenie dostępnej pamięci jest zwykle łatwiejsze niż ograniczenie dostępnego czasu obliczeń.

Silnik RE2 został opracowany specjalnie z myślą o niezaufanych wyrażeniach regularnych i został zaprojektowany do wykonywania w czasie liniowym.

Inną alternatywą jest samodzielne składanie wyrażeń regularnych na podstawie uproszczonej notacji. Na przykład możesz zezwolić użytkownikom na stosowanie wzorców globalnych (takich jak *.txt). Następnie można to przeanalizować w sposób, który zapobiega cofaniu się, np. Poprzez wyłączenie zagnieżdżania i stosowanie tylko chciwych kwantyfikatorów. W wielu przypadkach użycia uproszczona notacja wzoru jest całkowicie wystarczająca.

amon
źródło
11

Analiza wyrażenia regularnego w celu sprawdzenia, czy będzie on powolny, czy też nie, bez przeprowadzania samego spowolnienia , sprowadza się do rozwiązania problemu zatrzymania. Innymi słowy, nie jest możliwe znalezienie poprawnego i kompletnego rozwiązania.

Można, oczywiście, znaleźć rozwiązanie, które jest poprawne i w kompletne. Na przykład możesz pracować z restrykcyjną białą listą funkcji, które są bezpieczne w użyciu (np. Klasy postaci tak, powtórzenie nie ...). Pozwoliłoby to przekazać wiele bezkrytycznych wyrażeń regularnych, odrzucić wszystkie krytyczne i (niesłusznie) odrzucić te, które są w porządku, ale są zbyt skomplikowane, aby automatycznie były bezpieczne.

Kilian Foth
źródło
3
Czy masz cytat na swoje pierwsze oświadczenie? Byłbym zainteresowany takim dowodem. Regeksy nie są kompletne w Turinga, więc problem zatrzymania może nie mieć zastosowania.
Sebastian Redl,
3
@SebastianRedl To prawda, że ​​ściśle mówiąc, wyrażenia regularne nie są pełne Turinga, ale wszystkie popularne biblioteki regex mają rozszerzenia, które sprawiają, że nie są one już regularne. Ograniczenie użytkowników do dosłownie wyrażeń regularnych może być dobrym rozwiązaniem w tej sytuacji.
Kilian Foth
2
@KilianFoth: IIRC, nawet prawdziwe wyrażenia regularne (w znaczeniu tego słowa w CompSci) mogą wymagać wykładniczej ilości cofania się. Ale ponieważ nie są one pełne Turinga, dla każdego wyrażenia regularnego teoretycznie możliwe jest ustalenie tej górnej granicy. Jednak pozostawia otwarte dwa problemy: określenia górnej granicy automatycznie jest nietrywialne zadanie, a wynik może dać nieracjonalnie wysokie wyniki (jak w, górną granicę znacznie wyższa niż oczekiwanego czasu).
MSalters
@msalters każde prawdziwe wyrażenie regularne jest mechanicznie przekształcane w deterministyczny automat skończony, tj. zawsze można dopasować wyrażenie bez cofania się. Twój FSA może oczywiście stać się zbyt duży, ale to sugeruje, że ograniczenie liczby stanów w wygenerowanym FSA jest wystarczającym rozwiązaniem, aby zapobiec atakowi.
Jules
1

Jako autor parsera dla projektu Lazarus powiedziałbym, że nie ma sposobu, aby zrozumieć dane wyrażenie regularne, jakie zasoby zużyje na dany tekst.

Mam na myśli to, że nie wydałem tych samych zasobów (przynajmniej w sensie big-O).

Więc najlepsze podejście - uruchom ponownie parser w osobnym wątku i zabij go po upływie limitu czasu.

ANDgineer
źródło
0

Oprócz innych odpowiedzi rozwiązaniem może być również rzutowanie własnej biblioteki wyrażeń regularnych, która umożliwia instrumentowanie wydajności podczas wykonywania, a tym samym zapewnia środki do zabicia wykonania w połowie, jeśli zostaną spełnione pewne kryteria.

Podobnie możesz uruchomić wyrażenia regularne w innym wątku i zabić wątki, jeśli będą one trwały zbyt długo.

Jaka jest nazwa?
źródło