Vor kurzem wurde ich auf Denial-of-Service- Angriffe mit regulären Ausdrücken aufmerksam und beschloss, sogenannte "böse" Regex-Muster auszurotten, wo immer ich sie in meiner Codebasis finden konnte - oder zumindest solche, die für Benutzereingaben verwendet werden. Die Beispiele unter dem obigen OWASP-Link und Wikipedia sind hilfreich, aber sie erklären das Problem nicht einfach in einfachen Worten.
Eine Beschreibung der bösen Regexe aus Wikipedia :
- Der reguläre Ausdruck wendet die Wiederholung ("+", "*") auf einen komplexen Unterausdruck an.
- Für den wiederholten Unterausdruck gibt es eine Übereinstimmung, die auch ein Suffix einer anderen gültigen Übereinstimmung ist.
Mit Beispielen, wieder aus Wikipedia :
(a+)+([a-zA-Z]+)*(a|aa)+(a|a?)+(.*a){x}für x> 10
Ist das ein Problem, das einfach nicht einfacher zu erklären ist? Ich suche nach etwas, das es einfacher macht, dieses Problem beim Schreiben von regulären Ausdrücken zu vermeiden oder sie in einer vorhandenen Codebasis zu finden.
Antworten:
Warum sind böse Regexe ein Problem?
Weil Computer genau das tun, was Sie ihnen sagen, auch wenn es nicht das ist, was Sie gemeint haben oder völlig unvernünftig sind. Wenn Sie eine Regex-Engine bitten, zu beweisen, dass für eine bestimmte Eingabe eine Übereinstimmung mit einem bestimmten Muster vorliegt oder nicht, versucht die Engine, dies zu tun, unabhängig davon, wie viele verschiedene Kombinationen getestet werden müssen.
Hier ist ein einfaches Muster, das vom ersten Beispiel im Beitrag des OP inspiriert wurde:
Angesichts der Eingabe:
Die Regex-Engine versucht so etwas wie
(abababababababababababab)und beim ersten Versuch wird eine Übereinstimmung gefunden.Aber dann werfen wir den Schraubenschlüssel hinein:
Der Motor wird es zuerst versuchen,
(abababababababababababab)aber das scheitert an diesem Extraa. Dies führt zu einem katastrophalen Bracktracking, da unser Muster(ab)*in gutem Glauben eine seiner Aufnahmen freigibt (es wird "zurückverfolgen") und das äußere Muster erneut versuchen lässt. Für unsere Regex-Engine sieht das ungefähr so aus:Die Anzahl der möglichen Kombinationen skaliert exponentiell mit der Länge der Eingabe, und bevor Sie es wissen, verbraucht die Regex-Engine alle Ihre Systemressourcen, um dieses Problem zu lösen, bis sie nach Erschöpfung aller möglichen Kombinationen von Begriffen schließlich aufgibt und meldet "Es gibt keine Übereinstimmung." Inzwischen hat sich Ihr Server in einen brennenden Haufen geschmolzenen Metalls verwandelt.
Wie man böse Regexe erkennt
Es ist eigentlich sehr schwierig. Ich habe selbst ein Paar geschrieben, obwohl ich weiß, was sie sind und wie ich sie generell vermeiden kann. Sehen Sie, wie Regex überraschend lange dauert . Wenn Sie alles, was Sie können, in eine Atomgruppe einschließen, können Sie das Backtracking-Problem vermeiden. Grundsätzlich weist es die Regex-Engine an, einen bestimmten Ausdruck nicht erneut aufzurufen - "Sperren Sie alles, was Sie beim ersten Versuch gefunden haben". Beachten Sie jedoch, dass atomare Ausdrücke das Zurückverfolgen innerhalb des Ausdrucks nicht verhindern , also
^(?>((ab)*)+)$immer noch gefährlich, aber^(?>(ab)*)+$sicher sind (es stimmt überein(abababababababababababab)und weigert sich dann, übereinstimmende Zeichen aufzugeben, wodurch ein katastrophales Zurückverfolgen verhindert wird).Leider ist es nach dem Schreiben sehr schwierig, sofort oder schnell einen regulären Regex zu finden. Am Ende ist das Erkennen eines fehlerhaften regulären Ausdrucks wie das Erkennen eines anderen fehlerhaften Codes - es erfordert viel Zeit und Erfahrung und / oder ein einzelnes katastrophales Ereignis.
Interessanterweise veröffentlichte ein Team der University of Texas in Austin seit der ersten Abfassung dieser Antwort einen Artikel, in dem die Entwicklung eines Tools beschrieben wurde, mit dem reguläre Ausdrücke statisch analysiert werden können, um diese "bösen" Muster zu finden. Das Tool wurde entwickelt, um Java-Programme zu analysieren, aber ich vermute, dass in den kommenden Jahren weitere Tools entwickelt werden, die problematische Muster in JavaScript und anderen Sprachen analysieren und erkennen, insbesondere wenn die Rate der ReDoS-Angriffe weiter steigt .
quelle
Was Sie als "böse" Regex bezeichnen, ist eine Regex, die ein katastrophales Backtracking aufweist . Die verlinkte Seite (die ich geschrieben habe) erklärt das Konzept im Detail. Grundsätzlich kommt es zu einem katastrophalen Backtracking, wenn eine Regex nicht übereinstimmt und unterschiedliche Permutationen derselben Regex eine teilweise Übereinstimmung finden können. Die Regex-Engine versucht dann alle diese Permutationen. Wenn Sie Ihren Code überprüfen und Ihre regulären Ausdrücke überprüfen möchten, sind dies die drei wichtigsten Punkte, die Sie berücksichtigen sollten:
Alternativen müssen sich gegenseitig ausschließen. Wenn mehrere Alternativen mit demselben Text übereinstimmen können, versucht die Engine beide, wenn der Rest des regulären Ausdrucks fehlschlägt. Wenn sich die Alternativen in einer Gruppe befinden, die wiederholt wird, liegt ein katastrophales Backtracking vor. Ein klassisches Beispiel ist
(.|\s)*das Abgleichen einer beliebigen Textmenge, wenn die Regex-Variante keinen Modus "Punkt stimmt mit Zeilenumbrüchen überein" hat. Wenn dies Teil eines längeren regulären Ausdrucks ist, wird der reguläre Ausdruck durch eine Betreffzeichenfolge mit einer ausreichend langen Anzahl von Leerzeichen (die mit beiden.und übereinstimmen\s) unterbrochen. Der Fix besteht darin(.|\n)*, die Alternativen gegenseitig auszuschließen oder noch besser zu machen, um genauer zu bestimmen, welche Zeichen wirklich zulässig sind, z. B.[\r\n\t\x20-\x7E]für ASCII-Ausdrucke, Tabulatoren und Zeilenumbrüche.Quantifizierte Token, die nacheinander angeordnet sind, müssen sich entweder gegenseitig ausschließen oder sich gegenseitig ausschließen, was zwischen ihnen liegt. Andernfalls können beide mit demselben Text übereinstimmen, und alle Kombinationen der beiden Quantifizierer werden versucht, wenn der Rest des regulären Ausdrucks nicht übereinstimmt. Ein klassisches Beispiel ist
a.*?b.*?c, 3 Dinge mit "irgendetwas" zwischen ihnen abzugleichen. Wennckeine Übereinstimmung möglich ist, wird die erste.*?Zeichenweise bis zum Ende der Zeile oder Datei erweitert. Bei jeder Erweiterung wird die zweite.*?Zeichenweise erweitert, um dem Rest der Zeile oder Datei zu entsprechen. Die Lösung besteht darin, zu erkennen, dass Sie nichts zwischen sich haben können. Der erste Lauf muss bei anhaltenbund der zweite muss bei anhaltenc. Mit einzelnen Zeichena[^b]*+b[^c]*+cist eine einfache Lösung. Da wir jetzt beim Trennzeichen stehen bleiben, können wir Possessivquantifizierer verwenden, um die Leistung weiter zu steigern.Eine Gruppe, die ein Token mit einem Quantifizierer enthält, darf keinen eigenen Quantifizierer haben, es sei denn, das quantifizierte Token innerhalb der Gruppe kann nur mit etwas anderem abgeglichen werden, das sich gegenseitig ausschließt. Dies stellt sicher, dass weniger Iterationen des äußeren Quantifizierers mit mehr Iterationen des inneren Quantifizierers nicht mit demselben Text übereinstimmen können wie mehr Iterationen des äußeren Quantifizierers mit weniger Iterationen des inneren Quantifizierers. Dies ist das Problem, das in der Antwort von JDB dargestellt ist.
Während ich meine Antwort schrieb, entschied ich, dass dies einen vollständigen Artikel auf meiner Website verdient . Dies ist jetzt auch online.
quelle
Ich würde es als "Wiederholung einer Wiederholung" zusammenfassen. Das erste Beispiel, das Sie aufgelistet haben, ist gut, da es "den Buchstaben a, ein- oder mehrmals hintereinander. Dies kann wieder ein- oder mehrmals hintereinander vorkommen".
In diesem Fall ist auf die Kombination der Quantifizierer wie * und + zu achten.
Etwas subtiler ist die dritte und vierte. Diese Beispiele enthalten eine ODER-Verknüpfung, bei der beide Seiten wahr sein können. Dies kann in Kombination mit einem Quantifizierer des Ausdrucks abhängig von der Eingabezeichenfolge zu einer Menge potenzieller Übereinstimmungen führen.
Um es zusammenzufassen, TLDR-Stil:
Seien Sie vorsichtig, wie Quantifizierer in Kombination mit anderen Operatoren verwendet werden.
quelle
Ich bin überraschenderweise einige Male auf ReDOS gestoßen, als ich Quellcode-Überprüfungen durchgeführt habe. Eine Sache, die ich empfehlen würde, ist die Verwendung eines Timeouts mit der von Ihnen verwendeten Engine für reguläre Ausdrücke.
In C # kann ich beispielsweise den regulären Ausdruck mit einem
TimeSpanAttribut erstellen .string pattern = @"^<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)$"; Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0)); try { string noTags = regexTags.Replace(description, ""); System.Console.WriteLine(noTags); } catch (RegexMatchTimeoutException ex) { System.Console.WriteLine("RegEx match timeout"); }Diese Regex ist anfällig für Denial-of-Service und ohne das Timeout werden Ressourcen gesponnen und verschlungen. Mit dem Timeout wird
RegexMatchTimeoutExceptionnach dem angegebenen Timeout ein Wert ausgelöst, und die Ressourcennutzung führt nicht zu einer Denial-of-Service-Bedingung.Sie sollten mit dem Timeout-Wert experimentieren, um sicherzustellen, dass er für Ihre Verwendung funktioniert.
quelle
Böse Regexe erkennen
Faustregeln
Böse Regexe sind immer auf Mehrdeutigkeiten in der entsprechenden NFA zurückzuführen, die Sie mit Tools wie Regexper visualisieren können .
Hier sind einige Formen der Mehrdeutigkeit. Verwenden Sie diese nicht in Ihren regulären Ausdrücken.
(a+)+(auch bekannt als "Sternhöhe> 1"). Dies kann zu exponentiellem Aufblasen führen. Siehe dassafe-regexWerkzeug des Teilstapels .(a|a)+. Dies kann zu exponentiellem Aufblasen führen.\d+\d+. Dies kann zu einem Aufblasen des Polynoms führen.Zusätzliche Ressourcen
Ich habe dieses Papier über superlineare Regexe geschrieben. Es enthält zahlreiche Verweise auf andere Regex-bezogene Forschungsergebnisse.
quelle
Ich würde sagen, dies hängt mit der verwendeten Regex-Engine zusammen. Möglicherweise können Sie diese Arten von regulären Ausdrücken nicht immer vermeiden. Wenn Ihre Regex-Engine jedoch richtig aufgebaut ist, ist dies weniger problematisch. In dieser Blog-Reihe finden Sie zahlreiche Informationen zum Thema Regex-Engines.
Beachten Sie die Einschränkung am Ende des Artikels, da das Zurückverfolgen ein NP-Complete-Problem ist. Derzeit gibt es keine Möglichkeit, sie effizient zu verarbeiten, und Sie möchten sie möglicherweise in Ihrer Eingabe nicht zulassen.
quelle
a*a*verwendet keine Rückreferenzen. Jetzt verwendet die Regex-Engine Backtracking , was Sie vielleicht gemeint haben? In diesem Fall verwenden alle modernen Motoren Backtracking. Sie können das Backtracking über einfach deaktivieren(?>...), dies ändert jedoch häufig nicht die Bedeutung Ihres Ausdrucks (und kann in einigen Fällen umgangen werden).Ich glaube nicht, dass Sie solche regulären Ausdrücke erkennen können, zumindest nicht alle oder nicht, ohne ihre Ausdruckskraft einzuschränken. Wenn Sie sich wirklich für ReDoSs interessieren, würde ich versuchen, sie zu sandboxen und ihre Verarbeitung mit einem Timeout zu beenden. Möglicherweise gibt es auch RegEx-Implementierungen, mit denen Sie den maximalen Backtracking-Betrag begrenzen können.
quelle
a*oder\*„verletzlich“ zu sein.a*ist überhaupt nicht anfällig. Inzwischena{0,1000}a{0,1000}wartet ein katastrophaler Regex darauf, passiert zu werden. Sogara?a?kann unter den richtigen Bedingungen böse Ergebnisse haben.a*b*c*$ist sicher, abera*b*[ac]*$gefährlich, daa*möglicherweise Zeichen aufgegeben werden können,[ac]*wenn siebfehlen und die anfängliche Übereinstimmung fehlschlägt (zaaaaaaaaaaaccccccccccd. B. ).Ich kann mir einige Möglichkeiten vorstellen, wie Sie einige Vereinfachungsregeln implementieren können, indem Sie sie auf kleinen Testeingaben ausführen oder die Struktur des regulären Ausdrucks analysieren.
(a+)+kann durch eine Art Regel zum Ersetzen redundanter Operatoren auf gerecht reduziert werden(a+)([a-zA-Z]+)*könnte auch mit unserer neuen Redundanz-Kombinationsregel vereinfacht werden([a-zA-Z]*)Der Computer könnte Tests ausführen, indem er die kleinen Unterausdrücke des regulären Ausdrucks gegen zufällig generierte Sequenzen der relevanten Zeichen oder Zeichenfolgen ausführt und sieht, in welchen Gruppen sie alle landen. Für den ersten ist der Computer wie der reguläre Ausdruck will a's, also lass es uns versuchen mit
6aaaxaaq. Es sieht dann, dass alle a's und nur die erste Gruppe in einer Gruppe landen, und kommt zu dem Schluss, dass es egal ist, wie viele a's gesetzt werden, es spielt keine Rolle, da+alle in der Gruppe sind. Der zweite ist wie, hey, der Regex will ein paar Buchstaben, also lass es uns versuchen-fg0uj=, und dann sieht er wieder, dass jeder Haufen alle in einer Gruppe ist, so dass er+am Ende die los wird .Jetzt brauchen wir eine neue Regel, um die nächsten zu behandeln: Die Regel zum Eliminieren irrelevanter Optionen.
Mit
(a|aa)+, der Computer schaut es sich an und meint, wir mögen diesen großen zweiten, aber wir können diesen ersten verwenden, um mehr Lücken zu füllen, lassen Sie uns so viele AAs wie möglich bekommen und sehen, ob wir noch etwas bekommen können nachdem wir fertig sind. Es könnte es gegen eine andere Testzeichenfolge wie "eaaa @ a ~ aa" ausführen. um das festzustellen.Sie können sich davor schützen,
(a|a?)+indem Sie dem Computer klar machen, dass die von ihm übereinstimmenden Zeichenfolgena?nicht die Droiden sind, nach denen wir suchen. Da sie immer überall übereinstimmen können, entscheiden wir, dass wir solche Dinge nicht mögen(a?)+, und werfen sie weg.Wir schützen uns davor, indem wir
(.*a){x}erkennen lassen, dass die Charaktere, mit denen wir übereinstimmena, bereits erfasst worden wären.*. Wir werfen diesen Teil dann weg und verwenden eine andere Regel, um die redundanten Quantifizierer in zu ersetzen(.*){x}.Während die Implementierung eines solchen Systems sehr kompliziert wäre, ist dies ein kompliziertes Problem, und möglicherweise ist eine komplizierte Lösung erforderlich. Sie sollten auch Techniken verwenden, die andere Leute angesprochen haben, z. B. nur dem Regex eine begrenzte Menge an Ausführungsressourcen erlauben, bevor Sie ihn beenden, wenn er nicht fertig ist.
quelle