Recursive Parsers and Stack Exhaustion in C

Recursive descent parsers implemented in the C programming language are inherently susceptible to Denial of Service (DoS) attacks caused by stack exhaustion when handling deeply nested data structures like JSON, XML, or nested arithmetic expressions. Because these parsers map grammar nesting directly to native C function call stacks, an attacker can craft an input with excessive nesting levels that outgrows the operating system's allocated call stack space. This article examines the mechanics of the C call stack, how recursive parsing logic interacts with memory, and why unbounded nesting inevitably causes fatal process termination.

The Mechanics of Recursive Descent Parsing in C

A recursive descent parser breaks down structured text by dedicating distinct C functions to specific grammar rules. When the parser encounters an opening delimiter or an inner expression—such as an opening bracket [ in JSON or a parenthesized sub-expression in math—it calls another function or recursively invokes itself to process the nested content.

In C, each function invocation creates a new stack frame on the thread's call stack. This frame stores:

  • The function's return address.
  • Passed arguments.
  • Local variables used for tracking tokens, flags, or intermediate parse trees.
  • Saved CPU registers.

Under normal workloads, recursion unwinds cleanly as closing tokens (e.g., ], }) are parsed, returning memory to the stack.

Fixed Stack Limits in the C Execution Model

Unlike modern managed environments that support resizable segmented stacks or throw catchable exceptions on stack overflows, the C runtime model relies directly on the operating system's memory layout.

Operating systems allocate a fixed, finite stack size for each process or thread. On Linux, this is typically 8 MB for the main thread and often much less (e.g., 512 KB to 2 MB) for worker threads in high-concurrency network servers. Embedded systems may restrict stack space to tens of kilobytes.

The stack grows downward toward a designated guard page—an unmapped memory page placed directly beneath the stack boundary. When a program attempts to write beyond its allocated stack space, it attempts to write to this protected memory address.

The Attack Vector: Adversarial Nesting

An attacker exploiting a recursive parser does not need to send a massive payload in terms of file size; the vulnerability depends on depth rather than length.

Consider an input such as:

[[[[[[[[[[[[... (repeated tens of thousands of times) ...]]]]]]]]]]]]

When processing this input:

  1. The parser reads an opening delimiter and calls the parsing function recursively.
  2. Each step deeper adds a new stack frame without completing prior calls.
  3. If each recursive call consumes 128 bytes of stack memory, an input nested 70,000 levels deep requires approximately 9 MB of stack space.
  4. Once the cumulative frame size exceeds the stack allocation, the stack pointer crosses into the guard page.

The Impact: Uncontrolled Crashes and Denial of Service

C provides no native language mechanism to catch, handle, or recover from a stack overflow. When a thread accesses a guard page, the operating system kernel immediately raises a memory protection fault (such as SIGSEGV on Unix-like systems or an access violation STATUS_STACK_OVERFLOW on Windows).

Because recursive parsers typically lack the ability to validate stack boundaries dynamically, the process terminates immediately. In multi-threaded network daemons, this can crash the entire service, dropping active connections for all users and preventing future requests until a supervisor restarts the daemon. If the parser operates inside an embedded or kernel context, stack exhaustion can lead to complete system halts or reboots.

Preventing Stack Exhaustion

Securing C parsers against this vulnerability requires decoupling the input's nesting depth from the C execution stack:

  • Explicit Recursion Limits: Introduce a depth counter passed through the parsing functions. If the nesting level exceeds a predefined safety threshold (e.g., 500 levels), the parser halts gracefully and returns an error code.
  • Iterative Parsing: Replace recursive function calls with an iterative loop driven by a state machine.
  • Heap-Allocated Stacks: Store parsing state in dynamically allocated heap memory. The heap is significantly larger than the call stack, and memory allocation failures (NULL returned from malloc) can be caught and handled safely without terminating the process.