Regex · Textverarbeitung · Sicherheit

Was ist Regex genau?

Ein regulärer Ausdruck, kurz Regex, ist eine kleine Sprache, die die Form von Text beschreibt statt seines genauen Inhalts. Statt zu fragen „ist diese Zeichenkette gleich abc“, fragen Sie „sieht diese Zeichenkette aus wie drei Buchstaben, ein Bindestrich, vier Ziffern“.

Das ist die ganze Idee. Alles Weitere ist Notation.

Die Notation in einem Durchgang

Das meiste, was Sie lesen werden, besteht aus einer Handvoll Bausteine:

• . ein beliebiges Zeichen, \d eine Ziffer, \w ein Wortzeichen, \s ein Leerraum
• * null oder mehr, + eins oder mehr, ? null oder eins, 5 zwischen zwei und fünf
• [abc] eines davon, [^abc] alles außer diesen, [a-z] ein Bereich
• ^ der Anfang der Zeichenkette, $ ihr Ende
• (...) eine Gruppe, die Sie wiederholen oder erfassen können, | das eine oder das andere

^\d3-\d4$ liest sich also: ab dem Anfang drei Ziffern, ein Bindestrich, vier Ziffern, dann das Ende. Mehr nicht.

Warum sich dasselbe Muster in zwei Sprachen anders verhält

Es gibt nicht die eine Regex. Es gibt eine Familie von Dialekten, die sich in den Grundlagen einig sind und darüber hinaus auseinandergehen: POSIX, PCRE, die in JavaScript eingebaute Variante, die von Python, die von Go. Lookbehind, benannte Gruppen, Unicode-Eigenschafts-Escapes und selbst das, was \d als Ziffer ansieht, sind Stellen, an denen sie sich trennen.

Praktische Folge: Ein Muster, das aus einer für eine andere Sprache geschriebenen Antwort kopiert wurde, kann in Ihrer klammheimlich etwas anderes tun. Testen Sie es dort, wo es laufen wird, nicht dort, wo Sie es gefunden haben. Genau dafür gibt es den Regex-Tester auf dieser Seite.

Der Fehlerfall, den man kennen sollte: katastrophales Backtracking

Hier ist der Punkt, der aus einem Textwerkzeug ein Betriebsproblem macht.

Die meisten Regex-Engines gängiger Sprachen arbeiten mit Backtracking. Kann ein Muster auf mehrere Arten passen, probiert die Engine eine Aufteilung, und wenn der Rest scheitert, kehrt sie zurück und probiert eine andere. Für gewöhnliche Muster ist das billig. Für manche nicht.

Die gefährliche Form ist eine Wiederholung innerhalb einer Wiederholung, bei der beide denselben Text auf viele Arten unter sich aufteilen können. Das Lehrbuchbeispiel ist (a+)+$. Bei einer langen Folge von a, gefolgt von einem Zeichen, das nicht passen kann, muss die Engine jede mögliche Aufteilung dieser a zwischen innerer und äußerer Wiederholung durchprobieren, bevor sie auf Misserfolg schließen kann. Die Zahl der Kombinationen wächst exponentiell mit der Eingabelänge.

Zwanzig Zeichen können sofort fertig sein. Dreißig können eine Sekunde dauern. Vierzig werden womöglich nicht fertig, solange Sie dort noch arbeiten. Und weil das nur bei Eingaben passiert, die fast passen, taucht es in den Tests, die Sie mit passenden Eingaben geschrieben haben, nie auf.

Läuft diese Regex serverseitig über vom Nutzer gelieferte Eingaben, ist der exponentielle Fall für jeden erreichbar, der eine Anfrage senden kann. Das ist die Denial-of-Service-Klasse ReDoS, von der OWASP als Regular-Expression-Denial-of-Service geführt.

Wie Sie sich heraushalten

Seien Sie misstrauisch bei verschachtelten Quantoren. Ein + oder * auf einer Gruppe, die bereits eines enthält, ist die zu suchende Form. Oft lässt sie sich zu etwas mit genau einer eindeutigen Möglichkeit zu passen verflachen.

Verankern und präzise sein. ^, $ und genaue Zeichenklassen verringern die Zahl der Aufteilungen, die die Engine erwägen muss. [^"]* ist meist besser als .*.

Schicken Sie Nutzereingaben nicht leichtfertig durch eine handgeschriebene Regex. Für E-Mails, URLs und Daten schlägt ein Parser oder eine gut geprüfte Bibliothek jedes clevere Muster, und sie scheitert auf lesbare Weise.

Kennen Sie Ihre Engine. Manche, etwa RE2 in Go, beruhen auf einem anderen Algorithmus und backtracken überhaupt nicht. Sie verzichten auf Funktionen wie Rückwärtsreferenzen und garantieren dafür lineare Laufzeit. Muss eine Regex über feindliche Eingaben laufen, ist dieser Tausch oft der richtige.

Kurz gefasst

Eine Regex beschreibt die Form von Text, in einer Notation, die kleiner ist, als sie aussieht, und weniger portabel, als sie scheint. Lernen Sie das Dutzend Symbole, prüfen Sie den Dialekt dort, wo der Code laufen wird, und behandeln Sie einen Quantor in einem Quantor als Defekt, bis das Gegenteil bewiesen ist. Das Muster, das all Ihre Tests besteht, ist nicht das, welches die Seite lahmlegt.