Ist es sicher, eine Benutzereingabe für Pythons reguläre Ausdrücke zu benutzen?

Question

Ich möchte meine Benutzer verwenden reguläre Ausdrücke für einige Funktionen lassen. Ich bin gespannt, was die Auswirkungen sind von Benutzereingaben re.compile vorbei (). Ich nehme an, es gibt keine Möglichkeit für einen Benutzer geben Sie mir eine Zeichenfolge, die ihnen einen beliebigen Code ausführen lassen konnte. Die Gefahren, dachte ich haben, sind:

1. Der Benutzer könnte Eingabe übergeben, die eine Ausnahme auslöst.
   • Der Benutzer könnte Eingang passieren, dass die Regex-Engine verursacht eine lange Zeit in Anspruch nehmen, oder viel Speicher zu verwenden.

Die Lösung auf 1 ist einfach: catch Ausnahmen. Ich bin mir nicht sicher, ob es eine gute Lösung Vielleicht bis 2 ist nur die Länge des regex Begrenzung funktionieren würde.

Gibt es etwas, was ich Grund zur Sorge über?

Answer 1

Ich habe an einem Programm gearbeitet, die Benutzer ihre eigenen regex eingeben kann und Sie haben Recht - sie können (und tut) eingeben regex, das eine lange Zeit bis zum Ende nehmen kann - manchmal länger als als die Lebensdauer des Universums. Was noch schlimmer ist, während ein Regex Verarbeitung von Python der GIL hält, so wird es nicht nur den Faden hängen, dass der Regex läuft, aber das gesamte Programm.

die Länge der regex Begrenzung wird nicht funktionieren, da das Problem ist Rückzieher. Zum Beispiel passend zum regex r"(\S+)+x" auf einer Zeichenfolge der Länge N, die nicht eine enthält „x“ wird Rückzieher 2 ** N-mal. Auf meinem System nimmt dies etwa eine Sekunde gegen "a"*21 und die Zeit verdoppelt für jedes weiteres Zeichen zu finden, so dass eine Reihe von 100 Zeichen etwa 19167393131891000 Jahre in Anspruch nehmen würde (dies ist eine Schätzung, ich habe es nicht abgelaufen ist).

Für weitere Informationen lesen Sie das O'Reilly Buch „Reguläre Ausdrücke.“ - dies ein paar Kapitel auf die Leistung

Bearbeiten Um diese Runde schrieben wir eine Funktion regex Analyse, dass zu fangen versucht, und lehnen einige der offensichtlicheren degenerierte Fälle, aber es ist unmöglich, alle von ihnen zu bekommen.

Eine andere Sache, die wir betrachtet wurde, die Wieder Modul Patchen eine Ausnahme zu erhöhen, wenn es zu viele Male Backtracking. Dies ist möglich, erfordert aber die Python C-Quelle und neu kompilieren zu ändern, so nicht tragbar ist. Wir reichen auch einen Patch, um die GIL freizugeben, wenn Abgleich mit Python-Strings, aber ich glaube nicht, dass es in den Kern angenommen wurde (Python hält nur die GIL weil regex gegen wandelbar Puffer ausgeführt werden kann).

Answer 2

Es ist viel einfacher für gelegentliche Nutzer sie eine Teilmenge Sprache zu geben. Die Schale ist Globbing Regeln in fnmatch , zum Beispiel. Die SQL-LIKE-Bedingung Regeln sind ein weiteres Beispiel.

Übersetzen der Sprache des Benutzers in eine richtige regex für die Ausführung zur Laufzeit.

Answer 3

sollten einigermaßen sicher sein, den regulären Ausdruck zusammenstellen. Obwohl das, was in kompiliert es nicht unbedingt ein NFA ist (Rückreferenzierungen bedeutet es nicht ganz so sauber ist) sollte es noch irgendwie einfach sein in zu kompilieren.

Nun zu Leistungsmerkmalen, ist dies ein weiteres Problem vollständig. Selbst ein kleiner regulärer Ausdruck kann exponentielle Zeiteigenschaften haben wegen Rückzieher. Es könnte besser sein, um eine bestimmte Untergruppe von Funktionen zu definieren und nur sehr begrenzt Ausdrücke unterstützen, dass Sie selbst übersetzen.

Wenn Sie wirklich wollen Sie entweder allgemeine reguläre Ausdrücke unterstützen haben die Benutzer vertrauen (manchmal eine Option) oder begrenzen die Menge von Raum und Zeit verwendet. I glauben , dass der Raum nur durch die Länge des regulären Ausdrucks bestimmt verwendet wird.

edit: Wie Dave Notizen, anscheinend der globalen Interpreter Lock während Regex Matching gehalten wird, die machen würde härter, dass Timeout einstellen. Wenn das der Fall ist, ist Ihre einzige Option, um ein Timeout zu setzen, ist das Spiel in einem separaten Prozess ausgeführt werden. Obwohl nicht gerade ideal ist es machbar. Ich habe ganz vergessen zu multiprocessing . In der Umgebung ist dieser Abschnitt auf Sharing Objekte. Wenn Sie wirklich harte Beschränkungen müssen, sind getrennte Prozesse der Weg hier zu gehen.

Answer 4

Es ist nicht notwendig, der Kompilierung () zu verwenden, es sei denn, Sie müssen viele verschiedene reguläre Ausdrücke wiederzuverwenden. Das Modul bereits speichert die letzten Ausdrücke.

Der Punkt 2 (bei der Ausführung) könnte ein sehr schwieriges, wenn Sie den Benutzer zur Eingabe von beliebigen regulären Ausdruck erlauben. Sie können eine komplexe regexp mit wenigen Zeichen, wie der berühmte (x+x+)+y machen. Ich denke, es ist ein Problem, noch in allgemeiner Weise gelöst werden. Eine Abhilfe könnte ein anderer Thread den Markt bringen und überwachen sie, wenn sie die erlaubte Zeit überschreitet, den Faden und Rückkehr mit einem Fehler töten.

Answer 5

Ich glaube wirklich nicht, dass es möglich ist, Code auszuführen, indem sie einfach in eine re.compile vorbei. So wie ich es verstehen, re.compile (oder irgendein regex System in jeder Sprache) wandelt die regex Zeichenfolge in ein endliche Automaten (DFA oder NFA) und trotz des ominösen Namen ‚Kompilierung‘ es hat nichts mit der Ausführung von Code zu tun.

Answer 6

Sie müssen technisch nicht re.compile() verwenden, um einen regulären Ausdruck Operation an einer Schnur auszuführen. In der Tat kann die Kompilierung Methode langsamer oft, wenn Sie den Vorgang nur einmal ausführen sind, da ist es Overhead mit der anfänglichen Compilierung verbunden.

Wenn Sie über das Wort besorgt sind „Kompilierung“ dann vermeiden sie alle zusammen und einfach den rohen Ausdruck match passieren, search, etc. Sie wickeln können etwas sowieso die Leistung Ihres Codes verbessern werden.