[Bug]Deeply nested parentheses exhaust the C stack in parse_parentheses() recursion before PRISM_DEPTH_MAXIMUM is reached (CWE-674, stack-overflow) #4252

Hi,

While fuzzing prism, I found that a source consisting of many nested ( recurses through parse_parentheses() → parse_expression_prefix() → parse_expression() until the native C stack is exhausted, producing an ASan stack-overflow. The recursion guard (PRISM_DEPTH_MAXIMUM, 10000) is never hit first, so the depth limit does not protect the parser from a stack-exhaustion denial of service.

Summary

Each unmatched ( recurses as follows (a 3-frame cycle):

/* src/prism.c */
parse_expression_prefix(parser, binding_power, flags, diag_id, depth) {   /* :19524 */
    ...
    case PM_TOKEN_PARENTHESIS_LEFT:
        return parse_parentheses(parser, depth);                          /* :19639 */
}

static pm_node_t *
parse_parentheses(pm_parser_t *parser, uint16_t depth) {                  /* :19325 */
    ...
    pm_node_t *statement = parse_expression(parser, PM_BINDING_POWER_STATEMENT, ..., (uint16_t)(depth + 1));  /* :19325 */
    ...
}

parse_expression() forwards the incremented depth, and the depth guard lives at src/prism.c:22601:

/* src/prism.c:22601, parse_expression() */
if (PRISM_UNLIKELY(depth >= PRISM_DEPTH_MAXIMUM)) { ... /* too deep */ }
/* src/prism.c:50-51 */
#ifndef PRISM_DEPTH_MAXIMUM
    #define PRISM_DEPTH_MAXIMUM 10000
#endif

Because each nesting level pushes three C frames (parse_parentheses → parse_expression_prefix → parse_expression, plus locals), the native stack overflows long before depth reaches 10000. The threshold is reached at roughly 1600–1800 nested parentheses on the default 8 MB stack with ASan, far below the configured limit.

• Affected versions: prism 1.9.0 (PRISM_VERSION "1.9.0"), commit 0a5f9c956cb62b371ab680868d08c82ae0d49201 (2026-10-09).
• CWE: CWE-674 (Uncontrolled Recursion) → CWE-121 / stack exhaustion (denial of service).

Detail

Affected code

src/prism.c, parse_parentheses() (:19325) and parse_expression_prefix() (:19524). The depth counter is threaded through the recursion, but the check at parse_expression() (:22601) only fires at 10000 — the C stack is already exhausted by then.

Root cause: the recursion-depth limit is expressed in parser-logic units (one per expression), whereas each unit consumes several stack frames. With PRISM_DEPTH_MAXIMUM = 10000 and a multi-frame recursion cycle, the depth budget is larger than the C stack can hold, so a linear input of nested parentheses aborts the process with a stack overflow.

Trigger path

pm_serialize_parse()                                       (src/prism.c:23505)
  -> pm_parse() -> parse_statements() -> parse_expression()
       -> parse_expression_prefix()                        (src/prism.c:19524)
            -> parse_parentheses()                          (src/prism.c:19325)
                 -> parse_expression()                      ([recurse])

Build the reproducer

git clone https://github.com/ruby/prism.git
cd prism
git checkout 0a5f9c956cb62b371ab680868d08c82ae0d49201
ruby templates/template.rb

Use the same driver.c as the companion report (prism-issue-1-file-keyword-null-serialize.md) and build:

clang -g -O1 -std=c99 -fsanitize=address,undefined -fno-sanitize-recover=all \
      -Iinclude -Isrc -I. driver.c src/*.c -lm -o repro

POC (tested on the unmodified source)

A 3201-byte file: 1600 (, then the byte 1, then 1600 ). Rebuild it:

python3 -c 'import sys; sys.stdout.buffer.write(b"("*1600 + b"1" + b")"*1600)' > poc.rb
sha256sum poc.rb
# must print: c8f2d8db37ce6652b4cf7da8af993bb379ba62fd47122d6df633abce3c494988
ls -l poc.rb     # 3201 bytes

(The trailing ) are not required to trigger it; a file of 1800 opening ( alone overflows as well. The 3201-byte file above is the fuzzer's minimised sample.)

Run:

./repro poc.rb

Trigger result

Verified on unmodified prism 1.9.0 (0a5f9c95) built as above:

==...==ERROR: AddressSanitizer: stack-overflow on address 0x...
    #0 parse_expression_prefix   src/prism.c:19524
    #1 parse_expression          src/prism.c:22606
    #2 parse_parentheses         src/prism.c:19325
    #3 parse_expression_prefix   src/prism.c:19639
    #4 parse_expression          src/prism.c:22606
    #5 parse_parentheses         src/prism.c:19325
    ... (repeats until the stack is exhausted)
SUMMARY: AddressSanitizer: stack-overflow src/prism.c:19524 in parse_expression_prefix

• Exit status: non-zero (ASan aborts on stack-overflow).
• Threshold: about 1800 nested ( on the default 8 MB stack under ASan; 1200 does not overflow.
• Deterministic: yes — the same file overflows on every run.

Impact

A small, linear input of nested parentheses crashes the parser via stack exhaustion. Any tool that parses untrusted Ruby (servers, editors, linters, language tooling using pm_serialize_parse()) can be killed by a file on the order of a few kilobytes. Because the read is linear and cheap, this is an effective denial-of-service vector.

Suggested fix

Base the depth budget on the actual stack usage (or lower PRISM_DEPTH_MAXIMUM so the guard fires before the C stack is exhausted), e.g. count recursion in parse_parentheses()/parse_expression_prefix() and reject once a safe bound is reached:

/* src/prism.c, parse_parentheses() */
if (PRISM_UNLIKELY(depth >= PRISM_MAXIMUM_NESTING)) {
    pm_parser_err(parser, ..., PM_ERR_EXPRESSION_NOT_WRITABLE /* or a nesting error */);
    return NULL;
}

with PRISM_MAXIMUM_NESTING chosen so the guard fires with stack headroom for the three-frame-per-level recursion. Adding the 3201-byte input above to the regression corpus would prevent a re-introduction.