Regex-Performance: Backtracking-Explosionen vermeiden

Regex-Leistung: Ein Ausdruck kann den ganzen Server lahmlegen

Katastrophales Backtracking (Catastrophic Backtracking) kann die Übereinstimmungszeit eines regulären Ausdrucks von Millisekunden auf Stunden ansteigen lassen.

Szenario	Regex	Eingabelänge	Dauer
Normale Übereinstimmung	`/^abc$/`	100	<1ms
Lineares Backtracking	`/a*b/`	100	~1ms
Exponentielles Backtracking	`/(a+)+b/`	30	~10s
Exponentielles Backtracking	`/(a)b/`	30	~10s

I. Prinzip des Backtracking-Mechanismus

Funktionsweise der NFA-Engine

JavaScript verwendet eine NFA (Nichtdeterministischer Endlicher Automat)-Engine mit Backtracking-Algorithmus:

Eingabe: "aaaac"
Regex: /(a+)+c/

Übereinstimmungsprozess:
1. (a+) stimmt mit "aaaa" → versucht +c → stimmt nicht mit 'c'
2. Backtracking: (a+) stimmt mit "aaa" → (a+) stimmt mit "a" → versucht +c → stimmt nicht
3. Backtracking: (a+) stimmt mit "aa" → (a+) stimmt mit "aa" → versucht +c → stimmt nicht
4. Backtracking: (a+) stimmt mit "aa" → (a+) stimmt mit "a" → (a+) stimmt mit "a" → ...
5. ... exponentielles Backtracking

Berechnung der Backtracking-Anzahl

Für /(a+)+b/ bei Übereinstimmung mit "aaa..." (n a's):

Backtracking-Anzahl ≈ 2^n

n=10: ~1.024 Mal
n=20: ~1.048.576 Mal
n=30: ~1.073.741.824 Mal

II. Häufige Muster für katastrophales Backtracking

Muster 1: Verschachtelte Quantifizierer

// Katastrophales Backtracking
/(a+)+b/     // Verschachtelter + Quantifizierer
/(a*)*b/     // Verschachtelter * Quantifizierer
/(\w+)+@/    // Verschachteltes \w+

// Korrektur: Verschachtelte Quantifizierer vermeiden
/a+b/        // Einschichtiger Quantifizierer
/(\w+)@/     // Einschichtiger Quantifizierer

Muster 2: Geordnete Alternation

// Katastrophales Backtracking: Alternativoptionen mit gemeinsamem Präfix
/(a|ab)+c/

// Bei Eingabe "abababab..." ohne Übereinstimmung probiert die Engine alle Kombinationen
// Backtracking-Anzahl ≈ O(2^n)

// Korrektur: Gemeinsamen Präfix extrahieren
/a(b?)+c/

Muster 3: Überlappende Quantifizierer

// Katastrophales Backtracking
/.*.*=/

// Beide .* können denselben Inhalt matchen, was viele Backtrackings erzeugt

// Korrektur: Quantifizierer zusammenfassen
/.*=/

Muster 4: Rückverweis-Falle

// Katastrophales Backtracking
/^(b+)(a+)\1$/

// Bei Eingabe "bbbbaaaa" probiert \1 alle Unterteilungen von b+

// Korrektur: Wenn möglich, Rückverweise vermeiden oder Quantifiziererbereich begrenzen
/^(b+)(a+)\1$/.test(input) // Nur für kurze Eingaben

III. Optimierungstechniken

Technik 1: Zeichenklassen spezifizieren

// Langsam: . stimmt mit jedem Zeichen, viel Backtracking
/.*foo/

// Schnell: [^\n]* stimmt nicht mit Zeilenumbrüchen, reduziert Backtracking
/[^\n]*foo/

// Noch schneller: Wenn bekannt, dass vor foo nur Buchstaben stehen
/[a-z]*foo/

Technik 2: Verankerung zur Reduzierung des Suchraums

// Langsam: Versucht Übereinstimmung von jeder Position
/foo/

// Schnell: Wenn foo am Zeilenanfang steht
/^foo/

// Schnell: Wenn foo am Zeilenende steht
/foo$/

// Schnell: Beidseitig verankern
/^foo$/

Technik 3: Korrekte Verwendung nicht-gieriger Quantifizierer

// Szenario: Inhalt von <b>-Tags extrahieren

// Langsam: Gieriger Quantifizierer + Backtracking
/<b>(.*)<\/b>/

// Schnell: Nicht-gieriger Quantifizierer (aber Backtracking möglich)
/<b>(.*?)<\/b>/

// Am schnellsten: Ausschluss-Zeichenklasse (kein Backtracking)
/<b>([^<]*)<\/b>/

Methode	Übereinstimmung `<b>hello</b><b>world</b>`	Backtracking
`(.*)`	`hello</b><b>world`	Mehrfach
`(.*?)`	`hello`	Wenig
`([^<]*)`	`hello`	Keines

Technik 4: Atomare Gruppen (ES2024+)

// Atomare Gruppe (?>...) einmal gematcht, kein Backtracking
const regex = /^(?>a+)+b$/;

// Entspricht: Wenn a+ gematcht hat, kein Backtracking für äußeres + zum Wiederholen
// Matcht "aaab" → Erfolg
// Matcht "aaa" → Sofortiger Fehlschlag (kein exponentielles Backtracking)

Technik 5: Possessive Quantifizierer (einige Engines)

// Possessiver Quantifizierer a++ gibt nach Match nichts für Backtracking frei
// JavaScript nicht unterstützt, aber mit atomaren Gruppen simulierbar
const regex = /^(?>(a+))b$/;

Technik 6: Vorkompilierung + Wiederverwendung

// Langsam: Jedes Mal neues RegExp erstellen
function validate(input) {
  return /^[\w.+-]+@[\w-]+\.[\w.]+$/.test(input);
}

// Schnell: Vorkompilieren
const EMAIL_REGEX = /^[\w.+-]+@[\w-]+\.[\w.]+$/;
function validate(input) {
  return EMAIL_REGEX.test(input);
}

IV. Leistungsanalyse-Tools

ToolsKu Regex-Tool verwenden

Regex-Tool öffnen
Regulären Ausdruck und Testtext eingeben
Übereinstimmungsergebnisse und Dauer anzeigen
Regex anpassen, Leistung vor und nach Optimierung vergleichen

JS-interne Messung

function measureRegex(regex, input, iterations = 1000) {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    regex.test(input);
  }
  const end = performance.now();
  return {
    totalTime: end - start,
    avgTime: (end - start) / iterations,
    iterations,
  };
}

// Vergleich
const slow = measureRegex(/(a+)+b/, 'a'.repeat(25));
const fast = measureRegex(/a+b/, 'a'.repeat(25));
console.log(`Langsam: ${slow.avgTime}ms, Schnell: ${fast.avgTime}ms`);

recheck-Bibliothek zur Erkennung gefährlicher Regex

npm install recheck

import { check } from 'recheck';

const result = check(/(a+)+b/);
// { safe: false, complexity: 'exponential' }

const result2 = check(/a+b/);
// { safe: true, complexity: 'linear' }

V. Leistungsvergleich häufiger regulärer Ausdrücke

Regex	Komplexität	Sicher	Optimierte Version
`/(a+)+b/`	Exponentiell	❌	`/a+b/`
`/(a\|ab)+c/`	Exponentiell	❌	`/a(b?)+c/`
`/..=/`	Exponentiell	❌	`/.*=/`
`/(\d+){1,10}/`	Polynomiell	⚠️	`/\d{1,10}/`
`/^[a-z]+$/`	Linear	✅	—
`/^\d{4}-\d{2}-\d{2}$/`	Konstant	✅	—

VI. Serverseitiger Schutz

Timeout-Schutz

function safeRegexTest(regex, input, timeoutMs = 100) {
  const start = Date.now();
  const result = regex.test(input);
  if (Date.now() - start > timeoutMs) {
    throw new Error('Regex timeout: possible catastrophic backtracking');
  }
  return result;
}

re2-Engine (lineare Zeitgarantie)

import RE2 from 're2';

// RE2 garantiert lineare Zeit, keine Backtracking-Explosion
const regex = new RE2('(a+)+b');
regex.test('a'.repeat(100)); // Sicher, hängt nicht

Eingabelänge begrenzen

function validateWithLimit(regex, input, maxLength = 1000) {
  if (input.length > maxLength) {
    throw new Error(`Input exceeds maximum length: ${maxLength}`);
  }
  return regex.test(input);
}

VII. Best-Practices-Checkliste

Verschachtelte Quantifizierer vermeiden: (a+)+ → a+
Zeichenklassen spezifizieren: . → [^\n] oder spezifischere Klasse
Gemeinsamen Präfix extrahieren: (a|ab) → a(b?)
Ausschlussklassen statt nicht-gierig: (.*?) → ([^<]*)
Verankerung zur Reduzierung des Suchraums: ^ / $
Regex vorkompilieren: Wiederholte Erstellung vermeiden
Mit recheck prüfen: Gefährliche Regex in CI automatisch erkennen
Serverseitiger Timeout-Schutz: Regex-DoS verhindern
Eingabelänge begrenzen: Auswirkungen des Worst Cases reduzieren