Czy dla każdego wyrażenia „zła” istnieje nie-zła alternatywa, czy też diabeł w gramatyce?

Najwyraźniej ataki ReDos wykorzystują właściwości niektórych (poza tym użytecznych) wyrażeń regularnych ... zasadniczo powodując eksplozję możliwych ścieżek przez wykres zdefiniowany przez NFA.

Czy można uniknąć takich problemów, pisząc równoważne wyrażenie „non-evil”? Jeśli nie (w związku z tym gramatyka nie może być obsługiwana przez NFA w praktycznej czasoprzestrzeni), jakie metody analizy byłyby lepsze? Dlaczego?

To zależy od tego, czy masz wyrażenie regularne, czy wyrażenie regularne: wyrażenia regularne są złe, ale wyrażenia regularne są pięknem i nigdy nie zwrócą na ciebie zła.

Przez wyrażenie regularne mam na myśli nowoczesne wyrażenie regularne: tj. Wyrażenie regularne z dodatkowymi nowoczesnymi funkcjami, takimi jak odwołania wsteczne - np. Wyrażenie regularne kompatybilne z Perl. Jest to mocniejsze niż klasyczne wyrażenie regularne z oficjalnego podręcznika teorii języków / automatów, ponieważ klasyczne wyrażenia regularne nie pozwalają na odsyłanie wstecz, lookahead, lookbehind itd.

$n$$O(n)$

Zależy to od implementacji dopasowywania wyrażeń regularnych. Jeśli masz naiwną lub słabą implementację mechanizmu dopasowywania, dopasowanie może potrwać wykładniczo; z pewnością istnieją algorytmy z tą właściwością. Ale najlepszą odpowiedzią na to prawdopodobnie nie jest zmiana wyrażenia regularnego; Prawdopodobnie lepiej wybrać lepszy moduł, jeśli obawiasz się ataków typu „odmowa usługi”.

Dla porównania, niektóre współczesne wyrażenia regularne są nieuchronnie złe. Jeśli masz nowoczesne wyrażenie regularne, dopasowanie może wymagać czasu wykładniczego. W szczególności wyrażenia regularne z odniesieniami wstecznymi mogą rozpoznawać języki trudne dla NP. W związku z tym, przy realistycznych założeniach, istnieje klasa wyrażeń regularnych zła, w których testowanie pod kątem dopasowania zajmuje czas wykładniczy. Dlatego niektóre współczesne wyrażenia regularne są nieuchronnie złe: nie ma żadnego możliwego sposobu znalezienia równoważnego wyrażenia regularnego, które nie spowodowałoby wykładniczego powiększenia w czasie wykonywania.

(Taki ekwiwalent może istnieć i może być nawet możliwy do znalezienia w teorii, ale przy prawdopodobnych założeniach znalezienie równoważnego wyrażenia regularnego zajmie wykładniczy czas, co nie jest możliwe w praktyce. Jeśli miałeś systematyczną procedurę znajdowania równoważnego wyrażenia regularnego w czasie wielomianowym , możesz rozwiązać problem NP-trudny w czasie wielomianowym, udowadniając, że P = NP. Nie ma większego sensu, jeśli istnieje równoważne wyrażenie regularne, jeśli nie ma możliwości znalezienia go w ciągu swojego życia.)

Tło i źródła:

• Jakie języki rozpoznają wyrażenia regularne zgodne z Perl? oraz Ekspresyjność współczesnych wyrażeń regularnych zawiera odniesienia uzasadniające, że współczesne wyrażenia regularne mogą rozpoznawać trudne w NP języki.

• Jak symulować odwołania wsteczne, wyprzedzenia i spojrzenia w automatach skończonych? a kiedy wyrażenie regularne nie jest wyrażeniem regularnym? może pomóc zrozumieć różnicę między wyrażeniami regularnymi a wyrażeniami regularnymi.

• W tym artykule z Russ Cox znajduje się ładne wyjaśnienie dwóch różnych sposobów budowania mechanizmu dopasowywania wyrażeń regularnych i wyjaśnia, dlaczego czas działania, jeśli użyjesz właściwego algorytmu, jest liniowy w długości ciągu wejściowego (gdy wyrażenie regularne jest utrzymywane na stałym poziomie i jego długość jest traktowana jako stała). W szczególności algorytm oparty na NFA - znany również jako algorytm Thompsona - ma liniowy czas działania w najgorszym przypadku. Pokazuje także, w jaki sposób niektóre popularne języki mają wyrażenia regularne, które mogą być wykładnicze w niektórych wyrażeniach regularnych, a także omawia, które aspekty współczesnych wyrażeń regularnych mogą wprowadzać wykładnicze czasy działania.

• W tym poście zakładam, że P! = NP. Co więcej, odnosząc się do „prawdopodobnych założeń”, odnoszę się do wykładniczej hipotezy czasowej .

Ta odpowiedź będzie miała bardziej ogólny obraz tej niezwykłej sytuacji przekrojowej, w której teoria złożoności ma zastosowanie do cyberbezpieczeństwa, a przykład zawiera niektóre znaczące niuanse / subtelności, które mogą wystąpić w tym obszarze. Jest to zasadniczo podobne do „ataku iniekcyjnego”, w którym pewne nieoczekiwane dane wejściowe powodują patologiczne zachowanie albo powodujące awarię systemu, albo powodujące jego nienormalnie długi czas.

Wikipedia ma 15 kategorii ataków typu „ odmowa usługi”, które należą do „powodzi na poziomie aplikacji” na tej liście. Innym nieco podobnym przykładem jest atak, który wypełnia dzienniki aplikacji.

Jedną poprawką dla ataków wstrzykiwanych jest „oczyszczenie wejścia”. Projektant aplikacji może dokonać ponownej oceny, jeśli konieczne jest skompilowanie dowolnych wyrażeń regularnych dostarczonych przez potencjalnie złośliwego użytkownika. Po prostu usunięcie zagnieżdżonych wyrażeń w wyrażeniu regularnym lub inne podobne ograniczenie prawdopodobnie wystarczyłoby, aby uniknąć tego ataku. Chociaż są one nieodłączne od wielu współczesnych programów, można zapewnić dużą liczbę funkcji bez oceny wyrażeń regularnych. Kontekst ma znaczenie, niektóre aplikacje nie wymagałyby takiego bezpieczeństwa.

Innym podejściem do poprawy tolerancji / odporności na błędy, które ma tu zastosowanie, są limity czasu określone na różnych poziomach stosu / hierarchii oprogramowania. Pomysł polegałby na określeniu limitu czasu / procesora lub limitu instrukcji dla „przeciętnej” oceny wyrażenia regularnego i zakończyłby się wcześniej, gdyby został przekroczony. Można je wdrożyć za pomocą niestandardowych rozwiązań, ale niewiele oprogramowania lub języków programowania ma wbudowane limity czasu lub ramy do tego celu.

Oto dobry przykład użycia limitów czasu w celu poprawy odporności na uszkodzenia i pokazuje projekt / architekturę / pov wysokiego poziomu w celu złagodzenia takich problemów: Tolerancja błędów w dużych woluminach, System rozproszony / Netflix. Nie ma nic konkretnego związanego z wyrażeniami regularnymi, ale o to tutaj chodzi: praktycznie każda logika na poziomie aplikacji może pasować do tego frameworka lub czegoś podobnego.

W tym artykule wskazano, w jaki sposób cofanie może w szczególności prowadzić do powolnego dopasowywania wyrażeń regularnych. Regeksy mają wiele różnych cech i można próbować ocenić, które z nich prowadzą do najgorszych zachowań.

Oto miła ankieta naukowa na ten temat z proponowanymi rozwiązaniami do analizy statycznej :

• Analiza statyczna dla wykładniczego środowiska wykonawczego wyrażeń regularnych za pomocą logiki strukturalnej / Rathnayake, Thielecke

  Dopasowywanie wyrażeń regularnych przy użyciu śledzenia wstecznego może mieć wykładniczy czas działania, co prowadzi do ataku złożoności algorytmicznej znanego jako REDoS w literaturze dotyczącej bezpieczeństwa systemów. W tym artykule korzystamy z niedawno opublikowanej analizy statycznej, która wykrywa, czy dane wyrażenie regularne może mieć wykładniczy czas wykonywania dla niektórych danych wejściowych. Systematycznie konstruujemy dokładniejszą analizę, tworząc moce i produkty relacji przejściowych, a tym samym redukując problem REDoS do osiągalności. Poprawność analizy wykazano za pomocą rachunku strukturalnego drzew poszukiwawczych, w którym rozgałęzienie drzewa powodujące wykładniczy wybuch charakteryzuje się jako forma nieliniowości.