Skip to main content

Regex-Tester

Deutsch

Reguläre Ausdrücke mit Treffer-Hervorhebung testen.

Alle Berechnungen erfolgen lokal in Ihrem Browser. Es werden keine Daten an einen Server gesendet.

Die Ergebnisse dienen zur Information. Überprüfen Sie sie anhand anderer Quellen.

Eine Zeichenkette aus 26 Zeichen kann 368 ms brauchen, um am falschen Muster zu scheitern

Reguläre Ausdrücke laufen üblicherweise in einer Zeit proportional zur Eingabe. Verschachteln Sie einen Quantifizierer in einer quantifizierten Gruppe, und das gilt nicht mehr: /^(a+)+$/ braucht rund 23 ms, um 22 Zeichen abzulehnen, 95 ms für 24 und 368 ms für 26. Jedes weitere Zeichen verdoppelt die Arbeit ungefähr, eine etwas längere Eingabe verlangsamt den Abgleich also nicht — sie verhindert, dass er endet.

So wird gerechnet

  • Prüft ein Muster an Beispieltext und zeigt jeden Treffer samt seinen Fanggruppen.
  • Erklärt, was jeder Teil des Ausdrucks tut, denn die Syntax ist bewusst dicht.
  • Lässt Sie die scheiternden Fälle ausprobieren — dort sitzen die Leistungsprobleme.
die gefährliche Form: ein Quantifizierer in einer quantifizierten Gruppe
  (a+)+   (a*)*   (a|a)*   (\d+)+

n Zeichen lassen sich auf exponentiell viele Arten auf die Gruppen aufteilen,
und die Maschine muss alle durchprobieren, bevor sie 'kein Treffer' melden kann

sicheres Äquivalent: a+   — ein Quantifizierer, lineare Zeit

Rechenbeispiel

Zeitmessung von /^(a+)+$/ an Ketten von a-s mit einem abschließenden !, das nicht passen kann.

  1. 22 Zeichen → rund 23 ms
  2. 24 Zeichen → rund 95 ms
  3. 26 Zeichen → rund 368 ms
  4. dieselben 26 a-s ohne ! → Treffer in unter 0,01 ms
  5. die sichere Form /^a+$/ an 100.000 Zeichen → 0,12 ms

26 Zeichen abzulehnen kostet dreitausendmal mehr, als 100.000 anzunehmen. Erfolg ist sofort, Scheitern exponentiell — deshalb taucht das im Test nie auf, denn der Gutfall ist immer schnell.

Das Ergebnis lesen

  • Das ist ein Denial-of-Service-Vektor überall dort, wo Benutzereingaben auf ein Muster treffen. Angreifer brauchen keine lange Zeichenkette; dreißig oder vierzig Zeichen genügen, um einen Anfrage-Thread minutenlang zu binden, und eine Handvoll solcher Anfragen legt einen Server lahm.
  • Die Lösung ist fast immer, die Verschachtelung zu entfernen, statt drumherum zu optimieren. (a+)+ und a+ erkennen exakt dieselbe Sprache, die verwundbare Fassung bringt also überhaupt nichts — es ist ein Fehler und kein Kompromiss.
  • Die Messwerte stammen von einer Maschine und schwanken je Engine, die Form des Phänomens nicht. Jede Implementierung mit Backtracking — JavaScript, Python, Java, PCRE — verhält sich so. RE2 und Gos regexp nicht, weil sie die Merkmale verweigern, die es ermöglichen.
  • Testen Sie Ihre Muster mit Eingaben, die scheitern, nicht nur mit solchen, die passen. Der katastrophale Fall erscheint nur, wenn die Maschine jede Möglichkeit erschöpfen muss, bevor sie 'kein Treffer' feststellt.

Häufige Fragen

Woran erkenne ich, ob mein Muster verwundbar ist?
Suchen Sie nach einem Quantifizierer in einer quantifizierten Gruppe — (a+)+, (a*)*, (\d+)* und dergleichen — und nach Alternativen, deren Zweige denselben Text erkennen können. Testen Sie dann mit einer langen Kette, die BEINAHE passt, denn Beinahetreffer lösen den exponentiellen Pfad aus.
Warum ist es bei einem Treffer schnell und ohne Treffer langsam?
Weil die Maschine beim ersten Erfolg aufhören darf, vor einem Misserfolg aber jede Möglichkeit erschöpfen muss. Bei verschachtelten Quantifizierern verdoppelt sich die Zahl der Möglichkeiten je Zeichen, der scheiternde Fall ist also der einzige, der je vollständig durchsucht wird.

Quellen