Zurück zur Schwachstellen-Datenbank

Ineffiziente Reguläre-Ausdruck-Komplexität

Beschreibung

Ineffiziente Reguläre-Ausdruck-Komplexität tritt auf, wenn das Produkt einen regulären Ausdruck mit einer ineffizienten, potenziell exponentiellen Worst-Case-Berechnungskomplexität verwendet, die übermäßige CPU-Ressourcen verbraucht. Bestimmte Regex-Engines unterstützen "Backtracking", bei dem die Engine zu früheren Positionen zurückkehrt, wenn ein Token nicht übereinstimmt, und alternative Übereinstimmungen versucht. Dies wird problematisch, wenn Backtracking-Versuche exponentiell mit der Eingabelänge skalieren, die Eingabe nicht dem Ausdruck entsprechen kann und die Eingabelänge ausreicht, um das Problem auszulösen. Angreifer erstellen Eingaben, die speziell darauf ausgelegt sind, übermäßiges Backtracking auszulösen und CPU-Verbrauch in die Höhe zu treiben.

Risiko

ReDoS hat schwerwiegende Auswirkungen. CPU-Erschöpfung durch bösartige Eingabe. Anwendungs-Denial-of-Service. Server-Unzugänglichkeit. Kaskadierende Request-Timeouts. Dienstverschlechterung für alle Benutzer. Thread-Pool-Erschöpfung. Hohe Wahrscheinlichkeit wenn Regex nicht vertrauenswürdige Eingaben verarbeitet und verwundbare Muster enthält.

Lösung

Entfernen Sie verschachtelte Quantifizierer und verwenden Sie nicht-backtrackende Regex-Engines während der Architektur- und Entwurfsphase (hohe Wirksamkeit). Setzen Sie Backtracking-Limits während der Systemkonfigurationsphase (z.B. PHPs pcre.backtrack_limit) (mäßige Wirksamkeit). Vermeiden Sie Backtracking-Muster und lehnen Sie nicht vertrauenswürdige Regex-Eingaben während der Implementierungsphase ab (hohe Wirksamkeit). Begrenzen Sie die Eingabelänge für Regex-Verarbeitung (mäßige Wirksamkeit).

Häufige Auswirkungen

AuswirkungDetails
VerfügbarkeitBereich: Verfügbarkeit

Denial of Service durch CPU-Ressourcenverbrauch aus exponentiellem Backtracking.

Beispielcode und Lösung

Verwundbarer Code

// VERWUNDBAR: Regex mit katastrophalem Backtracking

// VERWUNDBAR: Verschachtelte Quantifizierer
const vulnerableEmailRegex = /^([a-zA-Z0-9]+)*@example\.com$/;

function vulnerableValidateEmail(input) {
    // VERWUNDBAR: Exponentielles Backtracking bei Eingaben wie
    // "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!"
    return vulnerableEmailRegex.test(input);
}

// VERWUNDBAR: Benutzerkontrolliertes Regex
function vulnerableSearch(userPattern, text) {
    // VERWUNDBAR: Benutzer kann bösartiges Regex bereitstellen
    const regex = new RegExp(userPattern);
    return regex.test(text);
    // Angriff: userPattern = "(a+)+$", text = "aaaaaaaaaaaaaaaaaa!"
}

// VERWUNDBAR: Häufige gefährliche Muster
const dangerousPatterns = [
    /^(a+)+$/,           // Verschachtelte Quantifizierer
    /^([a-zA-Z]+)*$/,    // Gruppe mit Quantifizierer, erneut quantifiziert
    /^(a|aa)+$/,         // Überlappende Alternation
    /^(.*a){20}$/,       // Quantifizierte Gruppe mit gierigem Platzhalter
];

# VERWUNDBAR: Python-Regex mit Backtracking-Problemen

import re

# VERWUNDBAR: Verschachtelte Quantifizierer
vulnerable_pattern = r'^([a-z]+)+$'

def vulnerable_validate(text):
    # VERWUNDBAR: Exponentielle Zeit bei "aaaa...a!"
    return re.match(vulnerable_pattern, text) is not None

Sichere Lösung

// SICHER: Sichere Regex-Muster und Validierung

// SICHER: Vereinfachtes, nicht-backtrackendes Muster
const safeEmailRegex = /^[a-zA-Z0-9._%+-]+@example\.com$/;

function safeValidateEmail(input) {
    // SICHER: Eingabelänge begrenzen
    if (input.length > 254) {  // RFC 5321 maximale E-Mail-Länge
        return false;
    }
    return safeEmailRegex.test(input);
}

// SICHER: Niemals benutzerkontrolliertes Regex zulassen
function safeSearch(userQuery, text) {
    // SICHER: Benutzereingabe escapen statt als Regex verwenden
    const escaped = userQuery.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
    const regex = new RegExp(escaped, 'gi');
    return regex.test(text);
}

// SICHER: RE2 verwenden (nicht-backtrackende Engine)
const RE2 = require('re2');

function safeRegexMatch(pattern, text) {
    // RE2 garantiert lineare Zeitkomplexität
    const regex = new RE2(pattern);
    return regex.test(text);
}

# SICHER: Sichere Python-Regex-Behandlung

import re
import re2  # Googles RE2-Bibliothek
from typing import Optional

# SICHER: Einfache, effiziente Muster
SAFE_EMAIL_PATTERN = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'

def safe_validate_email(text: str) -> bool:
    # SICHER: Längenbegrenzung
    if len(text) > 254:
        return False
    # SICHER: Einfaches Muster ohne verschachtelte Quantifizierer
    return re.match(SAFE_EMAIL_PATTERN, text) is not None

# SICHER: RE2 für Benutzereingaben verwenden
def safe_search_re2(pattern: str, text: str) -> Optional[re2.Match]:
    """RE2 verwenden, das lineare Zeitkomplexität garantiert."""
    try:
        regex = re2.compile(pattern)
        return regex.search(text)
    except re2.error:
        return None

# SICHER: Eingabevalidierung vor Regex
def safe_validate_input(text: str, max_length: int = 10000) -> bool:
    """Eingabe vor Regex-Anwendung validieren."""
    if len(text) > max_length:
        return False
    return True

# SICHER: Dedizierten Parser für komplexe Formate verwenden
from email.utils import parseaddr

def safe_parse_email(email: str) -> tuple:
    """Stdlib-Parser statt Regex verwenden."""
    return parseaddr(email)

// SICHER: Sichere Java-Regex-Behandlung

import java.util.regex.*;
import java.util.concurrent.*;

public class SafeRegex {

    // SICHER: Einfaches, effizientes Muster
    private static final Pattern SAFE_EMAIL_PATTERN =
        Pattern.compile("^[\\w.%+-]+@[\\w.-]+\\.[a-zA-Z]{2,}$");

    private static final int MAX_INPUT_LENGTH = 10000;

    public boolean safeValidateEmail(String input) {
        // SICHER: Längenprüfung zuerst
        if (input == null || input.length() > 254) return false;
        return SAFE_EMAIL_PATTERN.matcher(input).matches();
    }

    // SICHER: Regex mit Timeout
    public boolean safeMatchWithTimeout(String pattern, String input, long timeoutMs)
            throws InterruptedException, ExecutionException, TimeoutException {
        if (input.length() > MAX_INPUT_LENGTH) return false;

        ExecutorService executor = Executors.newSingleThreadExecutor();
        Future<Boolean> future = executor.submit(() -> {
            Pattern p = Pattern.compile(pattern);
            return p.matcher(input).matches();
        });

        try {
            // SICHER: Timeout verhindert unbegrenztes Hängen
            return future.get(timeoutMs, TimeUnit.MILLISECONDS);
        } finally {
            executor.shutdownNow();
        }
    }

    // SICHER: Benutzereingabe für wortwörtliche Suche escapen
    public boolean safeLiteralSearch(String userQuery, String text) {
        String escaped = Pattern.quote(userQuery);
        Pattern pattern = Pattern.compile(escaped, Pattern.CASE_INSENSITIVE);
        return pattern.matcher(text).find();
    }
}

CVE-Beispiele

  • CVE-2020-5243: User-Agent-Parsing mit überlappenden Erfassungsgruppen, das ReDoS verursachte.
  • CVE-2021-21317: npm User-Agent-Parser ReDoS-Schwachstelle.
  • CVE-2019-16215: Markdown-Parser CPU-Erschöpfung durch Regex-Backtracking.
  • CVE-2017-16021: URL-Validierungs-ReDoS in node-url-parse.

Verwandte CWEs

  • CWE-407: Inefficient Algorithmic Complexity (Eltern)
  • CWE-1226: Complexity Issues (Kategorie)
  • CAPEC-492: Regular Expression Exponential Blowup

Referenzen

  1. MITRE Corporation. "CWE-1333: Inefficient Regular Expression Complexity." https://cwe.mitre.org/data/definitions/1333.html
  2. OWASP. "Regular Expression Denial of Service - ReDoS"
  3. Davis, J. et al. "The Impact of Regular Expression Denial of Service (ReDoS)"