Ich möchte das Testen von regulären Ausdrücken in meiner Codebasis automatisieren.
Ich möchte mich vor (a+)+ bösen Regexps und ihren Verwandten schützen.
Dafür suche ich nach einem Ansatz oder einer existierenden Bibliothek, die "Worst-Case" -Eingaben für einen bestimmten regulären Ausdruck und eine Engine generiert (sowohl NFA- als auch DFA-basierte Engines sind im Umfang).
Zugegeben, der reguläre Ausdruck ist eine mächtige Sprache, und es ist eindeutig [rechnerisch] schwierig, die schlechteste Eingabe für willkürliche reguläre Ausdrücke zu finden, insb. Wenn Rückverweise verwendet werden, könnte es sogar unentscheidbar sein.
Für meinen Anwendungsfall ist es in Ordnung, Eingaben zu finden, die fürchterlich sind (im Gegensatz zu den schlimmsten möglichen), jedoch ziemlich kurz.
Die schlechteste Eingabe für einen regulären Ausdruck wird von Engine zu Engine variieren. Derselbe Regex und die gleiche Zeichenkette brauchen keine Zeit auf einer Engine, aber nie auf einer anderen.
Bei bestimmten Engines ist die "evilest" Regex immer noch gutartig und läuft in linearer Zeit (oder O(n*m) -Zeit, wenn sowohl die Länge der Regex als auch die Länge der Zeichenfolge variieren können.) Natürlich der Grund dafür ist die Umsetzung. Diese Engines gehen nicht zurück; stattdessen verwenden sie einen endlichen Automaten (FSM).
Beachten Sie, dass einige Backtracking-Implementierungen FSM verwenden, jedoch nur als Zwischenschritt. Lass dich dadurch nicht verwirren. Sie sind nicht FSM.
Die meisten alten Regex-Engines (wie sed) verwenden FSM-Matching. Es gibt einige neue Engines, die diese Implementierung verwenden, z. B. Go. PCRE hat sogar DFA-Funktionen (suchen Sie nach "DFA" hier ), die diese Art der Übereinstimmung verwenden.
Eine andere Antwort von mir behandelt auch den möglichen Geschwindigkeitsunterschied zwischen den beiden Implementierungen.
Es wäre ratsam, eine FSM-Implementierung zu verwenden, wenn Sie sich wirklich Sorgen machen, dass bösartige Eingaben die Geschwindigkeit Ihrer Regex beeinflussen. Leider ist FSM nicht so leistungsfähig wie die andere Implementierung; Es fehlt Unterstützung für einige Funktionen, z. B. Rückverweise.
Das Böse ist eigentlich ein bisschen subjektiv. Etwas Böses an einer Regex-Engine kann für einen anderen Motor nicht böse sein. Eine böse Handlung kann vereitelt werden, wenn der Motor optimiert wird. Optimierungen sind besonders wichtig für Backtracking-Engines angesichts ihrer potenziellen exponentiellen Laufzeit.
Unter bestimmten Bedingungen kann der Motor schnell feststellen, dass eine Übereinstimmung unmöglich ist. Während der Regex a*b?a*x gegen die Zeichenkette aaaaaaaaaaaaaaaaaaaaaaaaaa läuft, sagt Regex101 :
Ihr Spiel ist fehlgeschlagen. Was das bedeutet, ist die Engine, aufgrund ihrer internen Optimierungen, verstanden, dass Ihr Muster nie an irgendeiner Position zusammenpassen würde und somit nicht einmal versucht hat.
Denken Sie daran, dass Wikipedia sagt, dass die Regex-Datei böse ist, besonders wenn sie mit dieser Zeichenfolge gepaart ist.
Natürlich ist die Engine schlau, um nicht zurückzuverfolgen, um zu bestimmen, dass das Spiel nicht funktioniert. Es sah etwas ziemlich offensichtlich: die Regex benötigt ein x , um zu passen, aber keine x war in der Zeichenfolge vorhanden.
Ich erwähne das, weil Sie vielleicht nicht erwarten, dass Modifikatoren ein Faktor für die Regex-Leistung sein werden. Aber sie sind es.
Auch PCRE, eine der optimierten Implementierungen, kann erheblich mehr Schritte mit den beiden aktivierten Modifizierern u und i ausführen. Siehe meine Frage hier für weitere Informationen dazu. Am Ende habe ich herausgefunden, dass nur bestimmte Zeichen dieses Verhalten auslösen.
Im Allgemeinen ist eine lange Zeichenfolge langsamer als eine kurze Zeichenfolge. In der Tat, wenn Sie eine Zeichenfolge der Länge x finden, die katastrophale Rückverfolgung verursacht, können Sie es ein bisschen mehr rückgängig machen, indem Sie die Länge der Zeichenfolge erhöhen.
Vergleichen Sie die Geschwindigkeiten dieser Regexe:
.*b auf aaaaaaaa...aaaaab
.*?b auf aaaaaaaa...aaaaab
.*b auf abaaaaaaa...aaaaa
.*?b auf abaaaaaaa...aaaaa
Im Grunde ist gieriges Matching am besten, wenn Sie denken, dass Sie viel zusammenbringen müssen. Lazy Matching ist am besten, wenn Sie nur ein wenig übereinstimmen müssen.
Wenn Sie die Regex in a*b oder a*?b ändern, kann die Engine die Dinge erheblich optimieren.
Es gibt verschiedene Frameworks, die speziell dafür entwickelt wurden, Schwachstellen in Ihren Regexes zu finden. Es kann sich lohnen, einen auszuprobieren.
Es gibt wirklich eine Sache, die ich vorschlagen werde, wenn Sie versuchen wollten, Ihren eigenen Algorithmus zu erstellen. Es ist nicht praktisch, alle Zeichen im Wörterbuch auszuprobieren, besonders wenn Sie lange Zeichenfolgen testen möchten.
Schauen Sie sich stattdessen Ihre Regex an, um zu bestimmen, welche Zeichen Sie testen sollten. Wenn du (a+)+ als deine Regex hast, gibt es wirklich nur zwei Dinge, die in das Spiel passen: a und nicht a . Sie könnten sich wirklich vorstellen, dass es nur zwei Zeichen gibt: a und b (aka nicht a ), wenn Sie Ihre Strings mit Brute Force generieren.
Es wäre fantastisch, wenn Ihr Regex vor dem Hitzetod des Universums fertig sein könnte, oder? Einige Regex-Engines haben eine Möglichkeit, ein Timeout festzulegen.
%Vor%
%Vor%
bool set_time_limit ( int $seconds )Legen Sie die Anzahl der Sekunden fest, die ein Skript ausgeführt werden darf. Wenn dies erreicht wird, gibt das Skript einen schwerwiegenden Fehler zurück. Das Standardlimit ist 30 Sekunden oder, falls vorhanden, der
max_execution_time-Wert, der inphp.inidefiniert ist.Nach dem Aufruf startet
set_time_limit()den Zeitzähler von Null neu. Mit anderen Worten, wenn das Zeitlimit die Standardzeit von 30 Sekunden ist und 25 Sekunden nach Ausführung des Skripts ein Aufruf wieset_time_limit(20)erfolgt, wird das Skript vor dem Zeitlimit insgesamt 45 Sekunden lang ausgeführt.
Sie können auch den Link besuchen, da er direkt auf Stack Overflow ist.
Tags und Links algorithm regex performance-testing analysis