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?

regular-expressions parsers

— David Bullock
źródło

Jeśli udało mi się użyć precyzyjnego języka technicznego, to był wypadek. Prosimy o stępienie odpowiedzi dla osób nieakademickich :-)

— David Bullock,

Właśnie próbuję znaleźć praktyczny sposób na uniknięcie ReDos'd i to pytanie się pojawiło.

— David Bullock,

Przeformułuj swoje pytanie (?): Czy każdy język regularny ma wyrażenie regularne, którego długość jest ograniczona wielomianem w liczbie stanów jego minimalnego NFA?

— A.Schulz

@ A.Schulz. Nie sądzę, że to jest pytanie. Nie tak działają ataki ReDos. W przypadku ataku ReDos wyrażenie regularne jest zakodowane na stałe w kodzie źródłowym programu i jest dostarczane przez programistę, który uważa się za zaufanego. Następnie przeciwnik dostaje ciąg wejściowy, który program dopasowuje do wyrażenia regularnego. Jeśli przeciwnik może znaleźć ciąg wejściowy, który powoduje, że moduł dopasowywania działa przez bardzo długi czas, przeciwnik wygrywa. Dlatego martwimy się o przeciwne dane wejściowe, a nie o przeciwne wyrażenia regularne. (ciąg dalszy)

— DW

W związku z tym myślę, że pytanie brzmi: czy każdy język regularny ma wyrażenie regularne, tak że dopasowanie ciągu -znaków do tego wyrażenia regularnego zajmuje czas , gdzie jest czasem niezbyt- szybko rosnąca funkcja (powiedzmy, wielomian lub coś takiego)? [Nawiasem mówiąc, to ponowne sformułowanie wyjaśnia, że odpowiedź będzie zależeć od algorytmu zastosowanego do dopasowywania ... jak wspomniałem w mojej odpowiedzi.] Rozmiar wyrażenia regularnego jako funkcja wielkości minimalnego NFA nie naprawdę ważne tutaj.

n

$n$

O (f (n))

$O(f(n))$

f (n)

$f(n)$

n

$n$

— DW

Odpowiedzi:

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 .

— DW
źródło

Czy nie jest łatwiej znaleźć nie-złą alternatywę, dzieląc wyrażenie regularne na wiele mniejszych wyrażeń regularnych i łącząc je?

— inf3rno

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.

— vzn
źródło

Ta odpowiedź wydaje się mylona co do niektórych aspektów ReDos. 1. ReDoS nie ma nic wspólnego z atakiem iniekcyjnym. Ataki wstrzykiwania (np. XSS, wstrzykiwanie SQL, wstrzykiwanie poleceń itp.) Są zupełnie inne. 2. ReDos nie dotyczy złośliwych wyrażeń regularnych przesłanych przez przeciwnika. Zazwyczaj wyrażenie regularne jest zakodowane na stałe w programie (dostarczonym przez programistę), a ciąg wejściowy jest dostarczany przez użytkownika. Problemu nie można racjonalnie rozwiązać za pomocą sprawdzania poprawności danych wejściowych, ponieważ zwykle nie ma jasnych zasad sprawdzania poprawności danych wejściowych, które wystarczałyby do wyeliminowania problemu.

— DW

myślę, że twoje punkty są równoznaczne z technicznością / rozczesywaniem włosów na podstawie ReDos i brakuje lasów drzewom. jest podobny do „spreparowanych ataków iniekcyjnych”. odpowiedź wskazuje, że istnieją alternatywy dla używania wyrażeń regularnych w kodzie. analiza statyczna może znaleźć „wyrazy regularne zła”. wszystkie punkty odpowiedzi są prawidłowe. zdanie takie jak „zazwyczaj wyrażenie regularne jest zapisane na stałe w programie (dostarczone przez programistę), a ciąg wejściowy jest dostarczany przez użytkownika” nie pasuje dokładnie do zapisu ReDos, który jest bardziej niejasny i odnosi się do złośliwego atakującego itp. .

— vzn