Unkontrollierte Rekursion

Beschreibung

Unkontrollierte Rekursion tritt auf, wenn eine Funktion sich selbst rekursiv aufruft, ohne ordnungsgemäße Abbruchbedingungen oder Tiefenbegrenzungen, was zu Stack-Erschöpfung führt. Dies kann aufgrund fehlender Basisfälle, falscher Abbruchlogik oder externer Eingaben, die die Rekursionstiefe steuern, geschehen. Angreifer können dies ausnutzen, um Denial-of-Service zu verursachen, indem sie tiefe Rekursion auslösen, die den Stack-Speicher erschöpft.

Risiko

Stack-Überlauf verursacht Anwendungsabstürze. Denial-of-Service durch Ressourcenerschöpfung. Speicherkorruption durch Stack-Überlauf. Rekursive Bomben in Datenformaten (XML, JSON). Parser-Schwachstellen durch verschachtelte Strukturen. Systeminstabilität durch unkontrollierten Ressourcenverbrauch.

Lösung

Implementieren Sie ordnungsgemäße Basisfälle für alle rekursiven Funktionen. Begrenzen Sie die Rekursionstiefe mit Zählern. Verwenden Sie iterative Alternativen, wo möglich. Validieren Sie Eingaben, die die Rekursion steuern. Setzen Sie Stack-Größenbegrenzungen. Implementieren Sie Tail-Call-Optimierung, wo unterstützt. Verwenden Sie Trampolining für tiefe Rekursion.

Häufige Auswirkungen

Auswirkung	Details
Verfügbarkeit	Bereich: Denial-of-Service Stack-Erschöpfung bringt die Anwendung zum Absturz.
Integrität	Bereich: Speicherkorruption Stack-Überlauf kann angrenzenden Speicher korrumpieren.
Sicherheit	Bereich: Codeausführung Stack-Überlauf kann Ausnutzung ermöglichen.

Beispielcode und Lösung

Verwundbarer Code

// VERWUNDBAR: Unkontrollierte Rekursion in C
#include <stdio.h>
#include <stdlib.h>

// VERWUNDBAR: Kein Basisfall
void endlose_rekursion() {
    endlose_rekursion();  // Terminiert nie
}

// VERWUNDBAR: Benutzergesteuerte Tiefe
void verarbeite_tiefe_verwundbar(int tiefe) {
    // VERWUNDBAR: Keine Tiefenbegrenzung
    if (tiefe > 0) {
        verarbeite_tiefe_verwundbar(tiefe - 1);
    }
}

// Aufgerufen mit: verarbeite_tiefe_verwundbar(999999999);  // Stack-Überlauf

// VERWUNDBAR: Rekursive Verzeichnisverarbeitung
void verarbeite_verzeichnis_verwundbar(const char* pfad) {
    DIR* dir = opendir(pfad);
    struct dirent* entry;

    while ((entry = readdir(dir)) != NULL) {
        if (entry->d_type == DT_DIR) {
            char unterpfad[PATH_MAX];
            snprintf(unterpfad, sizeof(unterpfad), "%s/%s", pfad, entry->d_name);
            // VERWUNDBAR: Symbolische Link-Schleifen verursachen endlose Rekursion
            verarbeite_verzeichnis_verwundbar(unterpfad);
        }
    }
    closedir(dir);
}

# VERWUNDBAR: Python unkontrollierte Rekursion
import sys
import json

# VERWUNDBAR: Keine Abbruchbedingung
def endlose_schleife():
    return endlose_schleife()  # RecursionError

# VERWUNDBAR: Benutzergesteuerte Rekursionstiefe
def fakultät_verwundbar(n):
    # VERWUNDBAR: Keine Validierung von n
    if n <= 1:
        return 1
    return n * fakultät_verwundbar(n - 1)

# fakultät_verwundbar(10000)  # RecursionError

# VERWUNDBAR: Rekursive JSON-Verarbeitung
def verarbeite_json_verwundbar(data):
    if isinstance(data, dict):
        for value in data.values():
            verarbeite_json_verwundbar(value)  # Keine Tiefenbegrenzung
    elif isinstance(data, list):
        for item in data:
            verarbeite_json_verwundbar(item)  # Keine Tiefenbegrenzung

# Böswilliges JSON: {"a": {"a": {"a": {"a": ...}}}}  # 1000+ Ebenen

// VERWUNDBAR: Java unkontrollierte Rekursion
public class VerwundbareRekursion {

    // VERWUNDBAR: Kein Basisfallschutz
    public int fibonacci(int n) {
        // VERWUNDBAR: Großes n verursacht StackOverflowError
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    // VERWUNDBAR: Rekursive XML-Verarbeitung
    public void parseXML(Element element) {
        // VERWUNDBAR: Keine Tiefenbegrenzung
        for (Element child : element.getChildren()) {
            parseXML(child);  // Billion-Laughs-Angriff möglich
        }
    }
}

Sichere Lösung

// SICHER: Kontrollierte Rekursion in C
#include <stdio.h>
#include <stdlib.h>

#define MAX_RECURSION_DEPTH 100

// SICHER: Mit Tiefenbegrenzung
int verarbeite_tiefe_sicher(int tiefe, int aktuelle_tiefe) {
    // SICHER: Maximale Tiefe erzwingen
    if (aktuelle_tiefe > MAX_RECURSION_DEPTH) {
        return -1;  // Fehler: zu tief
    }

    if (tiefe <= 0) {
        return 0;
    }

    return verarbeite_tiefe_sicher(tiefe - 1, aktuelle_tiefe + 1);
}

// SICHER: Iterative Alternative
void verarbeite_iterativ(int tiefe) {
    // SICHER: Keine Rekursion, kein Stack-Überlauf
    for (int i = tiefe; i > 0; i--) {
        arbeite(i);
    }
}

// SICHER: Verzeichnisdurchlauf mit Tiefenbegrenzung und Symlink-Prüfung
int verarbeite_verzeichnis_sicher(const char* pfad, int max_tiefe, int aktuelle_tiefe) {
    if (aktuelle_tiefe > max_tiefe) {
        return 0;  // Tiefengrenze erreicht
    }

    DIR* dir = opendir(pfad);
    if (!dir) return -1;

    struct dirent* entry;
    while ((entry = readdir(dir)) != NULL) {
        if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0) {
            continue;
        }

        char unterpfad[PATH_MAX];
        snprintf(unterpfad, sizeof(unterpfad), "%s/%s", pfad, entry->d_name);

        struct stat st;
        // SICHER: lstat verwenden, um Symlinks nicht zu folgen
        if (lstat(unterpfad, &st) == 0 && S_ISDIR(st.st_mode) && !S_ISLNK(st.st_mode)) {
            verarbeite_verzeichnis_sicher(unterpfad, max_tiefe, aktuelle_tiefe + 1);
        }
    }

    closedir(dir);
    return 0;
}

# SICHER: Python kontrollierte Rekursion
import sys

# Rekursionslimit setzen (Standard ist ~1000)
sys.setrecursionlimit(500)  # Für Sicherheit reduzieren

MAX_DEPTH = 100

# SICHER: Mit Tiefenbegrenzung
def fakultät_sicher(n, max_n=1000):
    if n < 0:
        raise ValueError("Negative Zahl")
    if n > max_n:
        raise ValueError(f"Eingabe zu groß: {n} > {max_n}")
    if n <= 1:
        return 1
    return n * fakultät_sicher(n - 1, max_n)

# SICHER: Iterative Alternative
def fakultät_iterativ(n):
    if n < 0:
        raise ValueError("Negative Zahl")
    ergebnis = 1
    for i in range(2, n + 1):
        ergebnis *= i
    return ergebnis

# SICHER: JSON-Verarbeitung mit Tiefenbegrenzung
def verarbeite_json_sicher(data, max_tiefe=50, aktuelle_tiefe=0):
    if aktuelle_tiefe > max_tiefe:
        raise ValueError(f"Maximale Verschachtelungstiefe überschritten: {max_tiefe}")

    if isinstance(data, dict):
        for value in data.values():
            verarbeite_json_sicher(value, max_tiefe, aktuelle_tiefe + 1)
    elif isinstance(data, list):
        for item in data:
            verarbeite_json_sicher(item, max_tiefe, aktuelle_tiefe + 1)

// SICHER: Java kontrollierte Rekursion
public class SichereRekursion {

    private static final int MAX_DEPTH = 100;

    // SICHER: Iterativer Baumdurchlauf
    public void processTreeIterative(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            process(node.value);

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    // SICHER: XML-Parsing mit Tiefenbegrenzung
    public void parseXML(Element element, int maxDepth) {
        parseXMLInternal(element, maxDepth, 0);
    }

    private void parseXMLInternal(Element element, int maxDepth, int currentDepth) {
        if (currentDepth > maxDepth) {
            throw new SecurityException("Maximale XML-Tiefe überschritten");
        }

        for (Element child : element.getChildren()) {
            parseXMLInternal(child, maxDepth, currentDepth + 1);
        }
    }
}

---

Ausgenutzt in der Praxis

Billion Laughs Angriff (XML-Parser, 2003-heute)

Der "Billion Laughs"-Angriff nutzt rekursive XML-Entity-Expansion, um exponentiellen Speicherverbrauch zu verursachen. Ein kleines XML-Dokument kann zu Gigabytes an Speicherverbrauch führen und Server zum Absturz bringen. Dies betraf zahlreiche Unternehmen und Dienste.

• https://www.wired.com/2003/02/malware-expands-attack-surface/

ZIP-Bomb-Angriffe (verschiedene Systeme)

Rekursiv komprimierte Archive (ZIP-Bomben) haben wiederholt Antivirus-Software und Dateiverarbeitungssysteme zum Absturz gebracht, indem sie bei der Dekompression exponentiell expandierten.

• https://www.bleepingcomputer.com/news/security/a-new-non-recursive-zip-bomb-that-outputs-a-46-petabyte-file/

ReDoS bei Node.js (npm, 2018)

Eine Regular-Expression-Denial-of-Service-Schwachstelle in einem beliebten npm-Paket ermöglichte es Angreifern, durch speziell gestaltete Eingaben CPU-Erschöpfung zu verursachen.

• https://snyk.io/blog/redos-and-catastrophic-backtracking/

---

Tools zum Testen und Ausnutzen

• OWASP Dependency-Check — Erkennt bekannte Schwachstellen in Abhängigkeiten.

• Static Analysis Tools — Statische Analysewerkzeuge zur Erkennung unbegrenzter Rekursion.

• AFL Fuzzer — Fuzzing-Tool zum Finden von Rekursionsproblemen.

---

CVE-Beispiele

• CVE-2003-1564 — XML-Bombe (Billion Laughs) in libxml2.

• CVE-2019-9512 — HTTP/2 Ping Flood via Rekursion.

• CVE-2018-16487 — Lodash Rekursionsschwachstelle.

---

Referenzen

1. MITRE Corporation. "CWE-674: Uncontrolled Recursion." https://cwe.mitre.org/data/definitions/674.html

2. OWASP. "XML Security Cheat Sheet." https://cheatsheetseries.owasp.org/cheatsheets/XML_Security_Cheat_Sheet.html

3. CERT Secure Coding. "MEM04-C: Beware of zero-length allocations." https://wiki.sei.cmu.edu/confluence/display/c/MEM04-C.+Beware+of+zero-length+allocations