Gibt es eine Möglichkeit, bösartigen Code in einen regulären Ausdruck einzufügen?

138

Ich möchte meiner öffentlichen Webseite die Suchfunktion für reguläre Ausdrücke hinzufügen. Muss ich außer der HTML- Codierung der Ausgabe etwas tun, um mich vor böswilligen Benutzereingaben zu schützen?

Google - Suchanfragen werden von Menschen überschwemmt die Lösung der Umkehrung problem-- regulären Ausdrücken bösartigen Eingabe zu erkennen -. , Die ich bin nicht interessiert In meinem Szenario der Benutzereingabe ist ein regulärer Ausdruck.

Ich werde die Regex- Bibliothek in .NET (C #) verwenden.

MatthewMartin
quelle
4
Dies kann davon abhängen, welche Sprache und / oder Regex-Bibliothek Sie verwenden.
Aschepler
Noch etwas Lesematerial: ReDoS auf OWASP , ReDoS auf Wikipedia
joeytwiddle

Antworten:

216

Denial-of-Service-Bedenken

Das häufigste Problem bei Regexen ist ein Denial-of-Service-Angriff durch pathologische Muster, die exponentiell oder sogar überexponentiell verlaufen! - und so scheint es ewig zu dauern, bis es gelöst ist. Diese werden möglicherweise nur bei bestimmten Eingabedaten angezeigt, aber im Allgemeinen kann eine erstellt werden, bei der dies keine Rolle spielt.

Welche dies sind, hängt etwas davon ab, wie intelligent der von Ihnen verwendete Regex-Compiler ist, da einige davon während der Kompilierungszeit erkannt werden können. Regex-Compiler, die eine Rekursion implementieren, verfügen normalerweise über einen integrierten Rekursionstiefenzähler zur Überprüfung der Nichtprogression.

Russ Cox 'exzellentes Papier von 2007 über das Abgleichen regulärer Ausdrücke kann einfach und schnell sein (ist aber in Java, Perl, PHP, Python, Ruby usw. langsam) und beschreibt Möglichkeiten, wie die meisten modernen NFAs, die alle von Henry Spencers Code abgeleitet zu sein scheinen leiden unter starken Leistungseinbußen, aber wo ein NFA im Thompson-Stil keine derartigen Probleme hat.

Wenn Sie nur Muster zulassen, die von DFAs gelöst werden können, können Sie sie als solche kompilieren, und sie werden schneller ausgeführt, möglicherweise viel schneller. Es braucht jedoch Zeit , um dies zu tun. Das Cox-Papier erwähnt diesen Ansatz und die damit verbundenen Probleme. Es kommt alles auf einen klassischen Zeit-Raum-Kompromiss an.

Mit einem DFA verbringen Sie mehr Zeit damit, ihn zu erstellen (und mehr Zustände zuzuweisen), während Sie mit einem NFA mehr Zeit damit verbringen, ihn auszuführen, da es sich um mehrere Zustände gleichzeitig handeln kann und das Zurückverfolgen Ihr Mittagessen und Ihre CPU verschlingen kann.

Denial-of-Service-Lösungen

Der wahrscheinlich vernünftigste Weg, um diese Muster anzugehen, die am Ende eines Rennens mit dem Hitzetod des Universums stehen, besteht darin, sie mit einem Timer zu versehen, der effektiv eine maximale Zeitspanne für ihre Ausführung festlegt. Normalerweise ist dies viel, viel weniger als das Standardzeitlimit, das die meisten HTTP-Server bieten.

Es gibt verschiedene Möglichkeiten, diese zu implementieren, angefangen von einer einfachen alarm(N)auf C-Ebene bis hin zu einer Art try {}Blockierung der Ausnahmen vom Typ "Catch-Alarm", bis hin zum Laichen eines neuen Threads, der speziell mit einer integrierten Zeitbeschränkung erstellt wurde.

Code-Beschriftungen

In Regex-Sprachen, die Code-Callouts zulassen, sollte ein Mechanismus bereitgestellt werden, mit dem diese für die zu kompilierende Zeichenfolge zugelassen oder nicht zugelassen werden können. Auch wenn Code-Beschriftungen nur in der von Ihnen verwendeten Sprache codieren sollen, sollten Sie sie einschränken. Sie müssen nicht in der Lage sein, externen Code aufzurufen, obwohl Sie, wenn sie können, viel größere Probleme haben.

In Perl können beispielsweise keine Code-Beschriftungen in regulären Ausdrücken aus Zeichenfolgeninterpolation erstellt werden (wie dies bei der Kompilierung zur Laufzeit der Fall wäre), es sei denn, das spezielle Pragma mit lexikalischem Gültigkeitsbereich ist use re "eval";im aktuellen Bereich aktiv.

Auf diese Weise kann sich niemand in ein Code-Callout einschleichen rm -rf *, um beispielsweise Systemprogramme auszuführen . Da Code-Callouts so sicherheitsrelevant sind, deaktiviert Perl sie standardmäßig für alle interpolierten Zeichenfolgen, und Sie müssen alles tun, um sie wieder zu aktivieren.

Benutzerdefiniert \ P {Eigenschaften}

Es bleibt eine mehr sicherheitsrelevante Fragen im Zusammenhang mit Unicode-Stil Eigenschaften - wie \pM, \p{Pd}, \p{Pattern_Syntax}oder \p{Script=Greek}- das kann in einigen Regex Compiler gibt , die Unterstützung , die Notation.

Das Problem ist, dass in einigen von diesen die möglichen Eigenschaften vom Benutzer erweiterbar sind. Das bedeutet, dass Sie benutzerdefinierte Eigenschaften haben können, die tatsächliche Code-Beschriftungen für benannte Funktionen in einem bestimmten Namespace wie \p{GoodChars}oder sind \p{Class::Good_Characters}. Es könnte sich lohnen, einen Blick darauf zu werfen, wie Ihre Sprache damit umgeht.

Sandboxing

In Perl würde ein Sandkastenfach über das SafeModul die Kontrolle über die Sichtbarkeit von Namespaces ermöglichen. Andere Sprachen bieten ähnliche Sandbox-Technologien an. Wenn solche Geräte verfügbar sind, sollten Sie sie untersuchen, da sie speziell für die eingeschränkte Ausführung von nicht vertrauenswürdigem Code entwickelt wurden.

tchrist
quelle
4
Die NFA-> DFA-Konvertierung kann eine exponentielle Zustandsexplosion erzeugen, die ein Zeit-DoS in ein Raum-DoS verwandelt, sowie die Zeitkosten für die Erzeugung der exponentiellen Anzahl von Zuständen.
Barry Kelly
aber wahrscheinlich wird er nicht die gesamten Funktionen für reguläre Ausdrücke benötigen. Was halten Sie davon, die Leistung regulärer Ausdrücke einzuschränken, wie es Google getan hat: google.com/intl/en/help/faq_codesearch.html#regexp
Systemsfault
1
@ Barry Ganz richtig. Ich hatte an Russ Cox 'Strategie gedacht, die in einem seiner Artikel beschrieben wurde, Teile der NFA schrittweise zu einem äquivalenten DFA zusammenzustellen, sie aber wegzuwerfen, wenn sie zu groß wurde. Aber es gibt keine Silberkugel in einem DFA, selbst wenn Thompson bewiesen hat, dass es einer NFA entspricht, weil Sie den Piper irgendwann bezahlen müssen. Die Zeit, die für das Bitten des Betriebssystems um mehr Speicherplatz aufgewendet wird, und die damit verbundenen Einrichtungskosten für Seitentabellen können manchmal die Ausgleichsskala weiter in die andere Richtung verschieben und die Konvertierung von Zeit zu Speicherplatz weniger attraktiv machen, als dies der Fall wäre.
Tchrist
20

Zur hervorragenden Antwort von tchrist: Der gleiche Russ Cox, der die Seite "Regular Expression" geschrieben hat, hat auch Code veröffentlicht! re2 ist eine C ++ - Bibliothek, die eine Laufzeit von O (length_of_regex) und eine konfigurierbare Speicherbeschränkung garantiert. Es wird in Google verwendet, damit Sie einen regulären Ausdruck in die Google-Codesuche eingeben können. Dies bedeutet, dass es kampferprobt wurde.

Brian Bloniarz
quelle
2
Tatsächlich so. Sie können re2 mit einem Modul in die Regex-Engine von Perl tauschen. Wenn möglich, wird re2 und wenn nicht Perl verwendet. Funktioniert ganz gut.
Tchrist
6

Sie möchten dieses Papier lesen:

Unsicherer Kontextwechsel: Inokulieren regulärer Ausdrücke für die Überlebensfähigkeit In diesem Artikel geht es mehr darum, was mit Engines für reguläre Ausdrücke (z. B. PCRE) schief gehen kann, aber es kann Ihnen helfen, zu verstehen, was Sie erwartet.

Bruce Ediger
quelle
1
Hier ist ein Sicherheitshinweis zum GNU libc regcomp (3) -Code: securityreason.com/achievement_securityalert/93 Wie aktuell! Zumindest unter Linux ist die Sicherheitsanfälligkeit leicht zu demonstrieren: grep -E ". * {10,} {10,} {10,} {10,} {10,}"
Bruce Ediger
5

Sie müssen sich nicht nur um das Matching selbst kümmern, sondern auch darum, wie Sie das Matching durchführen. Wenn Ihre Eingabe beispielsweise auf dem Weg zur Engine für reguläre Ausdrücke eine Auswertungsphase oder eine Befehlsersetzung durchläuft, wird möglicherweise Code innerhalb des Musters ausgeführt. Wenn Ihre Syntax für reguläre Ausdrücke eingebettete Befehle zulässt, müssen Sie auch vorsichtig sein. Da Sie die Sprache in Ihrer Frage nicht angegeben haben, ist es schwierig, sicher zu sagen, welche Auswirkungen die Sicherheit hat.

Bryan Oakley
quelle
1

Eine gute Möglichkeit, Ihre RegEx auf Sicherheitsprobleme zu testen (zumindest für Windows), ist das kürzlich von Microsoft veröffentlichte SDL RegEx-Fuzzing-Tool . Dies kann helfen, eine pathologisch schlechte RegEx-Konstruktion zu vermeiden.

RandomNickName42
quelle