Preventing Stack Overflow in C with Iterative Parsing

Recursive parsing techniques in C are inherently susceptible to stack overflow vulnerabilities when processing deeply nested or adversarial data. This article explores how replacing implicit call-stack recursion with an iterative parsing model and an explicitly managed heap stack mitigates these vulnerabilities. By shifting state tracking from the operating system's execution stack to dynamically allocated memory, developers can enforce strict depth constraints, handle allocation failures gracefully, and eliminate runtime crashes caused by thread stack exhaustion.

The Problem: Call Stack Exhaustion in Recursive Parsers

Traditional recursive descent parsers map grammar rules directly to function calls. When parsing nested structures—such as JSON arrays, XML elements, or abstract syntax trees (ASTs)—each nested layer invokes a new C function call, allocating a new stack frame on the call stack.

In C, the call stack size for a thread is fixed and comparatively small, typically ranging from 1 MB to 8 MB depending on the operating system and compiler settings. Malicious actors exploit this architectural constraint by supplying deeply nested inputs (for example, thousands of consecutive opening brackets [[[[...]]]]). When the recursion depth exceeds the allocated thread stack boundaries, it triggers a stack overflow. In best-case scenarios, this causes an immediate segmentation fault (SIGSEGV) and denial-of-service (DoS). In worst-case scenarios, it can lead to stack-clash exploits or arbitrary code execution if stack-guard pages are circumvented.

The Solution: Explicit Stack Allocation

Iterative parsing decouples the grammar traversal from C’s execution call stack. Instead of relying on function calls to maintain parsing state, an iterative parser uses a single loop construct driven by an explicit stack data structure allocated in heap memory or an application-managed buffer.

typedef struct {
    int state;
    void *node_data;
} ParseFrame;

typedef struct {
    ParseFrame *frames;
    size_t capacity;
    size_t top;
} ExplicitStack;

In this architecture, when the parser encounters an opening token or a nested grammar production, it pushes a ParseFrame onto the ExplicitStack rather than making a recursive call. When a production finishes, it pops the frame and updates the parent structure.

How Explicit Stacks Mitigate Vulnerabilities

1. Transition from Call Stack to Heap Space

The thread execution stack is confined to a rigid, narrow memory segment. By allocating the parsing stack dynamically via malloc, realloc, or a memory arena, the parser accesses the much larger virtual memory space of the process. An input depth that immediately crashes a standard call stack can be seamlessly accommodated by the heap.

2. Deterministic Error Handling

A native call stack overflow in C cannot be caught at the language level; the operating system terminates the process via an uncatchable signal or exception. Conversely, an explicit stack uses standard allocation APIs. If the heap memory is exhausted, malloc returns NULL, allowing the parser to catch the condition, free partially parsed resources, and return a clean error code without crashing the host application.

3. Trivial Depth Limiting

Iterative parsers simplify the implementation of hard security limits on nesting depth. Because the explicit stack tracks its own depth via an index (e.g., stack->top), the parser can compare the current depth against a defined security threshold (MAX_PARSE_DEPTH) on every push operation:

if (stack->top >= MAX_PARSE_DEPTH) {
    return PARSER_ERROR_DEPTH_EXCEEDED;
}

Enforcing this boundary in recursive descent requires passing depth counters through every function signature or relying on thread-local storage, both of which are error-prone and introduce maintenance overhead.

4. Memory Isolation via Region-Based Allocation

Explicit stacks are frequently paired with arena (region-based) allocators. An arena pre-allocates a contiguous block of memory dedicated exclusively to the parsing lifecycle of a single payload. This guarantees that parsing operations cannot fragment system memory or exceed a predetermined memory quota, fully insulating the host process against memory-exhaustion vectors.