Uncontrolled Recursion

Description

Uncontrolled Recursion occurs when a function calls itself recursively without proper termination conditions or depth limits, leading to stack exhaustion. This can happen due to missing base cases, incorrect termination logic, or external input controlling recursion depth. Attackers can exploit this to cause denial of service by triggering deep recursion that exhausts stack memory.

Risk

Stack overflow causes application crashes. Denial of service through resource exhaustion. Memory corruption from stack overflow. Recursive bombs in data formats (XML, JSON). Parser vulnerabilities from nested structures. System instability from uncontrolled resource consumption.

Solution

Implement proper base cases for all recursive functions. Limit recursion depth with counters. Use iterative alternatives where possible. Validate input that controls recursion. Set stack size limits. Implement tail call optimization where supported. Use trampolining for deep recursion.

Common Consequences

Impact	Details
Availability	Scope: Denial of Service Stack exhaustion crashes the application.
Integrity	Scope: Memory Corruption Stack overflow may corrupt adjacent memory.
Security	Scope: Code Execution Stack overflow can enable exploitation.

Example Code + Solution Code

Vulnerable Code

// VULNERABLE: Uncontrolled recursion in C
#include <stdio.h>
#include <stdlib.h>

// VULNERABLE: No base case
void infinite_recursion() {
    infinite_recursion();  // Never terminates
}

// VULNERABLE: User-controlled depth
void process_depth_vulnerable(int depth) {
    // VULNERABLE: No limit on depth
    if (depth > 0) {
        process_depth_vulnerable(depth - 1);
    }
}

// Called with: process_depth_vulnerable(999999999);  // Stack overflow

// VULNERABLE: Recursive file processing
void process_directory_vulnerable(const char* path) {
    DIR* dir = opendir(path);
    struct dirent* entry;

    while ((entry = readdir(dir)) != NULL) {
        if (entry->d_type == DT_DIR) {
            char subpath[PATH_MAX];
            snprintf(subpath, sizeof(subpath), "%s/%s", path, entry->d_name);
            // VULNERABLE: Symbolic link loops cause infinite recursion
            process_directory_vulnerable(subpath);
        }
    }
    closedir(dir);
}

// VULNERABLE: XML/JSON parsing without depth limit
typedef struct Node {
    struct Node* children;
    int child_count;
} Node;

void process_node_vulnerable(Node* node) {
    // VULNERABLE: No depth limit
    for (int i = 0; i < node->child_count; i++) {
        process_node_vulnerable(&node->children[i]);
    }
}

# VULNERABLE: Python uncontrolled recursion
import sys
import json

# VULNERABLE: No termination condition
def infinite_loop():
    return infinite_loop()  # RecursionError

# VULNERABLE: User-controlled recursion depth
def factorial_vulnerable(n):
    # VULNERABLE: No validation of n
    if n <= 1:
        return 1
    return n * factorial_vulnerable(n - 1)

# factorial_vulnerable(10000)  # RecursionError

# VULNERABLE: Recursive JSON parsing
def process_json_vulnerable(data):
    if isinstance(data, dict):
        for value in data.values():
            process_json_vulnerable(value)  # No depth limit
    elif isinstance(data, list):
        for item in data:
            process_json_vulnerable(item)  # No depth limit

# Malicious JSON: {"a": {"a": {"a": {"a": ...}}}}  # 1000+ levels

# VULNERABLE: Recursive regex (ReDoS related)
def match_nested_vulnerable(s):
    # VULNERABLE: Recursive pattern matching
    if len(s) == 0:
        return True
    if s[0] == '(':
        # Find matching close
        depth = 1
        for i in range(1, len(s)):
            if s[i] == '(':
                depth += 1
            elif s[i] == ')':
                depth -= 1
            if depth == 0:
                return match_nested_vulnerable(s[1:i]) and match_nested_vulnerable(s[i+1:])
    return False

# VULNERABLE: File system traversal
def find_files_vulnerable(directory):
    results = []
    for item in os.listdir(directory):
        path = os.path.join(directory, item)
        if os.path.isdir(path):
            # VULNERABLE: Follows symlinks, no depth limit
            results.extend(find_files_vulnerable(path))
        else:
            results.append(path)
    return results

// VULNERABLE: Java uncontrolled recursion
public class VulnerableRecursion {

    // VULNERABLE: No base case protection
    public int fibonacci(int n) {
        // VULNERABLE: Large n causes StackOverflowError
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    // VULNERABLE: User-controlled depth
    public void processTree(TreeNode node) {
        if (node == null) return;

        // VULNERABLE: Deep trees cause stack overflow
        process(node.value);
        processTree(node.left);
        processTree(node.right);
    }

    // VULNERABLE: Recursive XML parsing
    public void parseXML(Element element) {
        // VULNERABLE: No depth limit
        for (Element child : element.getChildren()) {
            parseXML(child);  // Billion laughs attack possible
        }
    }

    // VULNERABLE: Object graph traversal
    public void serialize(Object obj, Set<Object> visited) {
        if (visited.contains(obj)) return;
        visited.add(obj);

        // VULNERABLE: Deep object graphs
        for (Field field : obj.getClass().getDeclaredFields()) {
            Object value = field.get(obj);
            if (value != null && !isPrimitive(value)) {
                serialize(value, visited);  // No depth limit
            }
        }
    }

    // VULNERABLE: Recursive regex matching
    public boolean matchPattern(String input, String pattern) {
        if (pattern.isEmpty()) {
            return input.isEmpty();
        }
        // VULNERABLE: Exponential backtracking possible
        if (pattern.charAt(0) == '*') {
            return matchPattern(input, pattern.substring(1)) ||
                   (!input.isEmpty() && matchPattern(input.substring(1), pattern));
        }
        // ...
    }
}

// VULNERABLE: JavaScript uncontrolled recursion
class VulnerableRecursion {

    // VULNERABLE: No termination
    infiniteRecursion() {
        return this.infiniteRecursion();  // RangeError: Maximum call stack size exceeded
    }

    // VULNERABLE: User-controlled depth
    processDepth(depth) {
        if (depth > 0) {
            // VULNERABLE: No maximum limit
            this.processDepth(depth - 1);
        }
    }

    // VULNERABLE: Recursive JSON parsing
    processJSON(data) {
        if (typeof data === 'object' && data !== null) {
            for (const key in data) {
                // VULNERABLE: No depth limit
                this.processJSON(data[key]);
            }
        }
    }

    // VULNERABLE: DOM traversal
    processDOM(element) {
        // Process element
        this.handle(element);

        // VULNERABLE: Deep DOM trees
        for (const child of element.children) {
            this.processDOM(child);
        }
    }

    // VULNERABLE: Recursive promise chains
    async processChain(items, index = 0) {
        if (index >= items.length) return;

        await this.process(items[index]);
        // VULNERABLE: Deep recursion with many items
        return this.processChain(items, index + 1);
    }
}

// VULNERABLE: Recursive function in eval
function evalVulnerable(expr) {
    // VULNERABLE: Nested expressions cause deep recursion
    if (expr.includes('(')) {
        const inner = extractInner(expr);
        return evalVulnerable(inner);
    }
    return evaluate(expr);
}

Fixed Code

// SAFE: Controlled recursion in C
#include <stdio.h>
#include <stdlib.h>

#define MAX_RECURSION_DEPTH 100

// SAFE: With depth limit
int process_depth_safe(int depth, int current_depth) {
    // SAFE: Enforce maximum depth
    if (current_depth > MAX_RECURSION_DEPTH) {
        return -1;  // Error: too deep
    }

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

    return process_depth_safe(depth - 1, current_depth + 1);
}

// SAFE: Iterative alternative
void process_iterative(int depth) {
    // SAFE: No recursion, no stack overflow
    for (int i = depth; i > 0; i--) {
        do_work(i);
    }
}

// SAFE: Directory traversal with depth limit and symlink check
int process_directory_safe(const char* path, int max_depth, int current_depth) {
    if (current_depth > max_depth) {
        return 0;  // Depth limit reached
    }

    DIR* dir = opendir(path);
    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 subpath[PATH_MAX];
        snprintf(subpath, sizeof(subpath), "%s/%s", path, entry->d_name);

        struct stat st;
        // SAFE: Use lstat to not follow symlinks
        if (lstat(subpath, &st) == 0 && S_ISDIR(st.st_mode) && !S_ISLNK(st.st_mode)) {
            process_directory_safe(subpath, max_depth, current_depth + 1);
        }
    }

    closedir(dir);
    return 0;
}

// SAFE: Node processing with depth limit
int process_node_safe(Node* node, int max_depth, int current_depth) {
    if (node == NULL || current_depth > max_depth) {
        return 0;
    }

    for (int i = 0; i < node->child_count; i++) {
        process_node_safe(&node->children[i], max_depth, current_depth + 1);
    }

    return 0;
}

# SAFE: Python controlled recursion
import sys
from functools import lru_cache

# Set recursion limit (default is ~1000)
sys.setrecursionlimit(500)  # Reduce for safety

MAX_DEPTH = 100

# SAFE: With depth limit
def factorial_safe(n, max_n=1000):
    if n < 0:
        raise ValueError("Negative number")
    if n > max_n:
        raise ValueError(f"Input too large: {n} > {max_n}")
    if n <= 1:
        return 1
    return n * factorial_safe(n - 1, max_n)

# SAFE: Iterative alternative
def factorial_iterative(n):
    if n < 0:
        raise ValueError("Negative number")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# SAFE: JSON processing with depth limit
def process_json_safe(data, max_depth=50, current_depth=0):
    if current_depth > max_depth:
        raise ValueError(f"Maximum nesting depth exceeded: {max_depth}")

    if isinstance(data, dict):
        for value in data.values():
            process_json_safe(value, max_depth, current_depth + 1)
    elif isinstance(data, list):
        for item in data:
            process_json_safe(item, max_depth, current_depth + 1)

# SAFE: File traversal with depth limit
def find_files_safe(directory, max_depth=20, current_depth=0):
    if current_depth > max_depth:
        return []

    results = []
    try:
        for item in os.listdir(directory):
            path = os.path.join(directory, item)
            # SAFE: Don't follow symlinks
            if os.path.islink(path):
                continue
            if os.path.isdir(path):
                results.extend(find_files_safe(path, max_depth, current_depth + 1))
            else:
                results.append(path)
    except PermissionError:
        pass

    return results

# SAFE: Tail recursion with trampoline
def trampoline(fn):
    def trampolined(*args, **kwargs):
        result = fn(*args, **kwargs)
        while callable(result):
            result = result()
        return result
    return trampolined

@trampoline
def factorial_trampoline(n, acc=1):
    if n <= 1:
        return acc
    return lambda: factorial_trampoline(n - 1, n * acc)

// SAFE: Java controlled recursion
public class SafeRecursion {

    private static final int MAX_DEPTH = 100;

    // SAFE: Memoized with depth protection
    private Map<Integer, Long> fibCache = new HashMap<>();

    public long fibonacci(int n) {
        if (n < 0) throw new IllegalArgumentException("Negative input");
        if (n > MAX_DEPTH) throw new IllegalArgumentException("Input too large");

        if (n <= 1) return n;

        if (fibCache.containsKey(n)) {
            return fibCache.get(n);
        }

        long result = fibonacci(n - 1) + fibonacci(n - 2);
        fibCache.put(n, result);
        return result;
    }

    // SAFE: Iterative tree traversal
    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);
        }
    }

    // SAFE: XML parsing with depth limit
    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("Maximum XML depth exceeded");
        }

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

    // SAFE: Object serialization with depth limit
    public void serialize(Object obj, Set<Object> visited, int maxDepth, int currentDepth) {
        if (currentDepth > maxDepth) {
            return;  // Stop at max depth
        }

        if (obj == null || visited.contains(obj)) {
            return;
        }

        visited.add(obj);

        for (Field field : obj.getClass().getDeclaredFields()) {
            field.setAccessible(true);
            try {
                Object value = field.get(obj);
                if (value != null && !isPrimitive(value)) {
                    serialize(value, visited, maxDepth, currentDepth + 1);
                }
            } catch (IllegalAccessException e) {
                // Handle error
            }
        }
    }
}

// SAFE: JavaScript controlled recursion
class SafeRecursion {

    static MAX_DEPTH = 100;

    // SAFE: With depth limit
    processDepth(depth, currentDepth = 0) {
        if (currentDepth > SafeRecursion.MAX_DEPTH) {
            throw new Error('Maximum recursion depth exceeded');
        }

        if (depth <= 0) {
            return;
        }

        this.processDepth(depth - 1, currentDepth + 1);
    }

    // SAFE: Iterative JSON processing
    processJSONIterative(data) {
        const stack = [data];

        while (stack.length > 0) {
            const current = stack.pop();

            if (typeof current === 'object' && current !== null) {
                for (const key in current) {
                    stack.push(current[key]);
                }
            }
        }
    }

    // SAFE: JSON with depth limit
    processJSON(data, maxDepth = 50, currentDepth = 0) {
        if (currentDepth > maxDepth) {
            throw new Error(`Maximum nesting depth exceeded: ${maxDepth}`);
        }

        if (typeof data === 'object' && data !== null) {
            for (const key in data) {
                this.processJSON(data[key], maxDepth, currentDepth + 1);
            }
        }
    }

    // SAFE: Iterative DOM traversal
    processDOMIterative(element) {
        const queue = [element];

        while (queue.length > 0) {
            const current = queue.shift();
            this.handle(current);

            for (const child of current.children) {
                queue.push(child);
            }
        }
    }

    // SAFE: Iterative processing for large arrays
    async processChainIterative(items) {
        for (const item of items) {
            await this.process(item);
        }
    }

    // SAFE: Batch processing to avoid deep recursion
    async processChainBatched(items, batchSize = 100) {
        for (let i = 0; i < items.length; i += batchSize) {
            const batch = items.slice(i, i + batchSize);
            await Promise.all(batch.map(item => this.process(item)));
        }
    }
}

---

Exploited in the Wild

Billion Laughs Attack

XML entity expansion causing exponential recursion.

Recursive Bomb Payloads

Deeply nested JSON/XML causing DoS.

ReDoS Attacks

Recursive regex patterns causing CPU exhaustion.

---

Tools to test/exploit

• Fuzzing tools for recursion depth.

• Static analysis for recursion without limits.

• Performance profilers.

---

CVE Examples

• CVE-2003-1564: XML bomb (Billion Laughs).

• CVE-2019-9512: HTTP/2 Ping Flood via recursion.

---

References

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

2. XML bomb mitigation strategies.