Gibt es für jeden "bösen" Regex eine nicht-böse Alternative, oder ist der Teufel in der Grammatik?

16

Anscheinend nutzen ReDos- Angriffe die Eigenschaften einiger (ansonsten nützlicher) regulärer Ausdrücke aus. Dies führt im Wesentlichen zu einer Explosion möglicher Pfade durch den von der NFA definierten Graphen.

Ist es möglich, solche Probleme zu vermeiden, indem man einen entsprechenden "nicht bösen" Regex schreibt? Wenn nicht (daher kann die Grammatik von einer NFA nicht in praktischer Zeit / Raum behandelt werden), welche Parsing-Ansätze wären besser? Warum?

David Bullock
quelle
Wenn ich es geschafft habe, eine präzise Fachsprache zu verwenden, ist das ein Unfall. Bitte dumm Ihre Antworten für eine nicht-akademische :-)
David Bullock
1
Ich versuche eigentlich nur, einen praktischen Weg zu finden, um ReDos zu vermeiden , und diese Frage tauchte auf.
David Bullock
Umformulieren Sie Ihre Frage (?): Verfügt jede reguläre Sprache über einen regulären Ausdruck, dessen Länge durch ein Polynom in der Anzahl der Zustände der minimalen NFA begrenzt ist?
A.Schulz
1
@ A.Schulz. Ich denke nicht, dass das die Frage ist. So funktionieren ReDos-Angriffe nicht. Bei einem ReDos-Angriff wird der reguläre Ausdruck fest in den Programmquellcode codiert und vom Entwickler bereitgestellt, von dem angenommen wird, dass er ihm vertraut. Dann muss der Gegner eine Eingabezeichenfolge bereitstellen, die das Programm mit dem regulären Ausdruck vergleicht. Wenn der Gegner eine Eingabezeichenfolge findet, durch die der Matcher sehr lange ausgeführt wird, gewinnt der Gegner. Wir sind also besorgt um widersprüchliche Eingaben, nicht um widersprüchliche reguläre Ausdrücke. (Fortsetzung)
DW
Folglich lautet die Frage meines Erachtens stattdessen: Verfügt jede reguläre Sprache über einen regulären Ausdruck, so dass das Vergleichen einer Zeichenfolge mit diesem regulären Ausdruck O ( f ( n ) ) dauert , wobei f ( n ) nicht zu viel ist. schnell wachsende Funktion von n (etwa Polynom oder so ähnlich)? [Diese Neuformulierung macht übrigens deutlich, dass die Antwort von dem Algorithmus abhängt, der für den Abgleich verwendet wird ... wie ich in meiner Antwort erwähne.] Die Größe des regulären Ausdrucks in Abhängigkeit von der Größe der minimalen NFA nicht wirklich wichtig hier. nÖ(f(n))f(n)n
DW

Antworten:

14

Es hängt davon ab, ob Sie einen regulären Ausdruck oder einen regulären Ausdruck haben: reguläre Ausdrücke sind böse, aber reguläre Ausdrücke sind etwas Schönes und werden Sie niemals böse machen.

Mit regulärem Ausdruck meine ich einen modernen regulären Ausdruck: dh einen regulären Ausdruck mit zusätzlichen modernen Funktionen wie Rückverweisen - z. B. einem Perl-kompatiblen regulären Ausdruck. Dies ist leistungsfähiger als ein klassischer regulärer Ausdruck aus einem Lehrbuch für formale Sprachen / Automatentheorie, da klassische reguläre Ausdrücke keine Rückverweise, Lookahead, Lookbehind usw. zulassen.

nÖ(n)

Dies hängt von der Implementierung des Matchers für reguläre Ausdrücke ab. Wenn Sie eine naive oder schlechte Implementierung des Matchers haben, kann das Matching exponentiell lange dauern. Es gibt sicherlich Algorithmen mit dieser Eigenschaft. Aber die beste Antwort darauf ist wahrscheinlich, den regulären Ausdruck nicht zu ändern. Es ist wahrscheinlich besser, einen besseren Matcher auszuwählen, wenn Sie Bedenken wegen Denial-of-Service-Angriffen haben.

Im Vergleich sind einige moderne reguläre Ausdrücke unvermeidlich böse. Wenn Sie einen modernen regulären Ausdruck haben, kann der Abgleich exponentielle Zeit erfordern. Insbesondere reguläre Ausdrücke mit Rückreferenzen können NP-harte Sprachen erkennen. Folglich gibt es unter plausiblen Annahmen eine Klasse von bösen Regexps, bei denen das Testen eines Matches exponentielle Zeit in Anspruch nimmt. Daher sind einige moderne reguläre Ausdrücke unvermeidlich böse: Es gibt keine praktikable Möglichkeit, einen äquivalenten regulären Ausdruck zu finden, der nicht zu einem exponentiellen Anstieg der Laufzeit führt.

(Ein solches Äquivalent könnte theoretisch existieren und sogar auffindbar sein, aber unter plausiblen Annahmen wird das Auffinden des äquivalenten regulären Ausdrucks exponentielle Zeit in Anspruch nehmen, was in der Praxis nicht machbar ist. Wenn Sie ein systematisches Verfahren zum Auffinden des äquivalenten regulären Ausdrucks in polynomialer Zeit gehabt hätten Dann könnten Sie das NP-schwierige Problem in polynomieller Zeit lösen und beweisen, dass P = NP ist. Es nützt nicht viel, wenn es einen äquivalenten regulären Ausdruck gibt, wenn es in Ihrem Leben keine Möglichkeit gibt, ihn tatsächlich zu finden.)


Hintergrund und Quellen:

DW
quelle
Ist es nicht einfacher, eine nicht böse Alternative zu finden, indem man den regulären Ausdruck in mehrere kleinere reguläre Ausdrücke aufteilt und sie in Kombination verwendet?
Inf3rno
1

Diese Antwort wird einen umfassenderen Blick auf diese ungewöhnliche Querschnittssituation werfen, in der die Komplexitätstheorie auf die Cybersicherheit anwendbar ist und das Beispiel einige der signifikanten Nuancen / Feinheiten enthält, die in diesem Bereich auftreten können. Dies ähnelt im Wesentlichen einem "Injektionsangriff", bei dem bestimmte unerwartete Eingaben zu einem pathologischen Verhalten führen, das entweder zum Absturz eines Systems oder zu einer ungewöhnlich langen Zeit führt.

Wikipedia hat 15 Kategorien von Denial-of-Service-Angriffen, und dieser Angriff fällt in die Kategorie "Überschwemmungen auf Anwendungsebene" in dieser Liste. Ein anderes, etwas ähnliches Beispiel ist ein Angriff, der die Anwendungsprotokolle füllt.

Ein Fix für Injektionsangriffe besteht darin, "die Eingabe zu bereinigen". Der Anwendungsentwickler kann eine Neubewertung vornehmen, wenn es erforderlich ist, beliebige reguläre Ausdrücke zu kompilieren, die von einem potenziell böswilligen Benutzer bereitgestellt werden. Nur verschachtelte Ausdrücke im regulären Ausdruck oder einer ähnlichen Einschränkung zu entfernen, würde wahrscheinlich ausreichen, um diesen Angriff zu vermeiden. Während sie für viele moderne Softwareprodukte von grundlegender Bedeutung sind, können große Mengen an Funktionen bereitgestellt werden, ohne reguläre Ausdrücke auszuwerten. Auf den Kontext kommt es an, einige Anwendungen würden eine solche Sicherheit nicht benötigen.

Ein anderer Ansatz zur Verbesserung der Fehlertoleranz / Ausfallsicherheit, der hier anwendbar ist, sind Zeitüberschreitungen, die auf verschiedenen Ebenen des Software-Stacks / der Software-Hierarchie angegeben sind. Die Idee wäre, eine Zeit- / CPU- oder Anweisungsbegrenzung für eine "durchschnittliche" reguläre Ausdrucksbewertung anzugeben und sie vorzeitig zu beenden, wenn sie überschritten wird. Sie können mit benutzerdefinierten Lösungen implementiert werden, aber nicht viele Software- oder Programmiersprachen verfügen über integrierte Timeouts oder Frameworks für diesen Zweck.

Hier ist ein schönes Beispiel für die Verwendung von Zeitüberschreitungen zur Verbesserung der Fehlertoleranz. Außerdem wird eine allgemeine Architektur / Design / POV gezeigt, um solche Probleme zu mindern: Fehlertoleranz in einem verteilten System mit hohem Volumen / Netflix. Es hat nichts spezielles mit regulären Ausdrücken zu tun, aber darum geht es hier: Praktisch jede Logik auf Anwendungsebene kann in dieses Framework oder ähnliches passen.

Dieser Artikel weist darauf hin , wie Rückzieher kann insbesondere zu langsam regexp Matching führen. Regexps haben viele verschiedene Funktionen und man könnte versuchen zu bewerten, welche zu Worst-Case-Verhalten führen.

Hier ist eine schöne wissenschaftliche Übersicht über dieses spezielle Thema mit den vorgeschlagenen statischen Analyselösungen:

  • Statische Analyse für die exponentielle Laufzeit eines regulären Ausdrucks über Substructural Logics / Rathnayake, Thielecke

    Der Abgleich regulärer Ausdrücke mithilfe von Backtracking kann eine exponentielle Laufzeit haben und zu einem algorithmischen Komplexitätsangriff führen, der in der Literatur zur Systemsicherheit als REDoS bezeichnet wird. In diesem Artikel bauen wir auf einer kürzlich veröffentlichten statischen Analyse auf, die ermittelt, ob ein bestimmter regulärer Ausdruck für einige Eingaben eine exponentielle Laufzeit haben kann. Wir konstruieren systematisch eine genauere Analyse, indem wir Potenzen und Produkte von Übergangsbeziehungen bilden und dadurch das REDoS-Problem auf Erreichbarkeit reduzieren. Die Richtigkeit der Analyse wird anhand einer Substrukturberechnung von Suchbäumen bewiesen, wobei die Verzweigung des Baumes, die ein exponentielles Aufblähen verursacht, als eine Form der Nichtlinearität charakterisiert wird.

vzn
quelle
Diese Antwort scheint in Bezug auf einige Aspekte von ReDos verwirrt zu sein. 1. ReDoS hat nichts mit einem Injektionsangriff zu tun. Injection-Attacken (z. B. XSS, SQL-Injection, Command Injection usw.) sind völlig unterschiedlich. 2. Bei ReDos handelt es sich nicht um böswillige reguläre Ausdrücke, die von einem Gegner gesendet werden. In der Regel ist der reguläre Ausdruck im Programm (vom Entwickler bereitgestellt) fest codiert, und die Eingabezeichenfolge wird von einem Benutzer bereitgestellt. Das Problem kann durch die Eingabevalidierung nicht vernünftigerweise gelöst werden, da normalerweise keine eindeutige Eingabevalidierungsrichtlinie vorhanden ist, die ausreichen würde, um das Problem zu beheben.
DW
Ich denke, Ihre Punkte belaufen sich auf technische Details / Haarspalterei basierend auf dem ReDos-Hinweis und vermisst den Wald vor lauter Bäumen. Es ist ähnlich wie "Crafted Injection Attacks". In der Antwort wird darauf hingewiesen, dass es Alternativen zur Verwendung von regulären Ausdrücken im Code gibt. statische Analyse kann die "bösen Regexps" finden. Alle Punkte der Antwort sind gültig. Ein Satz wie "Normalerweise ist die reguläre Ausdrucksweise im Programm fest codiert (vom Entwickler bereitgestellt), und die Eingabezeichenfolge wird von einem Benutzer bereitgestellt" stimmt nicht genau mit der ReDos-Beschreibung überein, die an manchen Stellen vager ist und sich auf einen böswilligen Angreifer usw. bezieht .
VZN