Schutz der Benutzereingabe regulärer Ausdrücke vor Angriffen

Mir ist der Denial of Service (ReDoS) für reguläre Ausdrücke bekannt. Gibt es eine vernünftige Möglichkeit, Benutzern das Erstellen benutzerdefinierter regulärer Ausdrücke zu ermöglichen und gleichzeitig sicherzustellen, dass sie kein exponentiell langsames Muster senden?

Das Problem mit regulären Ausdrücken ist nicht der Regex selbst, sondern die Regex-Engine, die alle Arten von „praktischen“ Funktionen wie Backtracking bietet. Daher wird die Verwendung einer Regex-Engine ohne diese Funktionen vermieden.

Reguläre Ausdrücke Das Konzept der Informatik kann immer in linearer Zeit angepasst werden, nachdem sie zu einer endlichen Zustandsmaschine kompiliert wurden. Daher kann eine auf Zustandsmaschinen basierende Regex-Engine nicht für ReDoS verwendet werden. Die notwendigen Zustandsmaschinen können jedoch in pathologischen Beispielen ziemlich groß werden. Die Begrenzung des verfügbaren Speichers ist jedoch in der Regel einfacher als die Begrenzung der verfügbaren Rechenzeit.

Die RE2-Engine wurde speziell für den Umgang mit nicht vertrauenswürdigen regulären Ausdrücken entwickelt und für die Ausführung in linearer Zeit konzipiert.

Eine andere Alternative besteht darin, die regulären Ausdrücke selbst aus einer vereinfachten Notation zusammenzusetzen. Beispielsweise können Sie Benutzern erlauben, Glob-Muster (wie *.txt) zu verwenden. Sie können dies dann auf eine Weise analysieren, die ein Zurückverfolgen verhindert, z. B. indem Sie das Verschachteln nicht zulassen und nur gierige Quantifizierer verwenden. Für viele Anwendungsfälle ist eine vereinfachte Musternotation völlig ausreichend.

Die Analyse eines regulären Ausdrucks, um festzustellen, ob er langsam ist oder nicht, ohne dass die Analyse selbst langsam wird , führt zur Lösung des Stoppproblems. Mit anderen Worten, es ist nicht möglich , eine korrekte und vollständige Lösung zu finden.

Sie können, natürlich, eine Lösung finden , die richtigen und ist in vollständig. Sie könnten beispielsweise mit einer restriktiven weißen Liste von Funktionen arbeiten, die sicher verwendet werden können (z. B. Zeichenklassen Ja, Wiederholung Nein ...). Auf diese Weise können Sie viele unkritische reguläre Ausdrücke übergeben, alle kritischen ablehnen und (fälschlicherweise) einige ablehnen, die in Ordnung, aber zu kompliziert sind, um sich automatisch als sicher zu erweisen.

Als Autor des Re-Parsers für das Lazarus-Projekt würde ich sagen, dass es für einen bestimmten regulären Ausdruck keine Möglichkeit gibt, zu verstehen, welche Ressourcen er für einen bestimmten Text verbraucht.

Ohne die gleichen Ressourcen auszugeben, meine ich (zumindest in Big-O-Bedeutung).

Der beste Ansatz: Führen Sie den Parser in einem separaten Thread aus und beenden Sie ihn nach einer Zeitüberschreitung.

Zusätzlich zu den anderen Antworten kann eine Lösung auch darin bestehen, eine eigene Regex-Bibliothek zu erstellen, die eine Leistungsinstrumentierung während der Ausführung ermöglicht und somit die Möglichkeit bietet, die Ausführung zur Hälfte zu beenden, wenn einige Kriterien erfüllt sind.

Ebenso können Sie die regulären Ausdrücke in einem anderen Thread ausführen und die Threads beenden, wenn sie zu lange dauern.