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

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?

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$$O(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:

• Welche Sprachen erkennen Perl-kompatible reguläre Ausdrücke? Die Ausdruckskraft moderner regulärer Ausdrücke liefert Hinweise, um zu rechtfertigen, dass moderne reguläre Ausdrücke NP-harte Sprachen erkennen können.

• Wie simuliert man Rückreferenzen, Lookaheads und Lookbehinds in Automaten mit endlichen Zuständen? und wenn ein regulärer Ausdruck kein regulärer Ausdruck ist? kann hilfreich sein, um den Unterschied zwischen regulären Ausdrücken und regulären Ausdrücken zu verstehen.

• In diesem Artikel von Russ Cox werden zwei verschiedene Möglichkeiten zum Erstellen eines Matchers für reguläre Ausdrücke erläutert. Außerdem wird erläutert, warum die Laufzeit bei Verwendung des richtigen Algorithmus in der Länge der Eingabezeichenfolge linear ist (wenn der reguläre Ausdruck festgehalten wird und seine Länge wird als Konstante behandelt). Insbesondere der NFA-basierte Algorithmus - auch als Thompson-Algorithmus bekannt - weist eine lineare Worst-Case-Laufzeit auf. Es wird auch gezeigt, wie einige populäre Sprachen reguläre Ausdrücke implementieren, die bei einigen regulären Ausdrücken exponentiell werden können, und es wird erläutert, welche Aspekte moderner regulärer Ausdrücke exponentielle Laufzeiten einführen können.

• In diesem Beitrag gehe ich von P! = NP aus. Genauer gesagt, wenn ich mich auf "plausible Annahmen" beziehe, beziehe ich mich auf die Exponentialzeithypothese .

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.