bug: Compiler stack overflow crashes on 9 different expression patterns (~420-500 nodes)

[chamitro]

bug: Compiler stack overflow crashes on 9 different expression patterns (~420-500 nodes)

Bug Report

Cairo version: 2.16.1 (scarb 2.16.1)

Current behavior:

The Cairo compiler crashes with stack overflow (thread has overflowed its stack, SIGABRT) on various expression structures with approximately 420-500+ nodes. The crash affects 9 different expression patterns across both addition and multiplication code paths, suggesting the compiler's AST traversal uses recursion without sufficient stack depth or iterative fallback.

All other ZK compilers tested (Circom, Noir, Leo) handle the same patterns without crashing — they either compile successfully or produce clean error messages.

Expected behavior:

The compiler should either:

1. Handle these expression sizes without crashing
2. Produce a clean error: Error: expression complexity exceeds maximum

A compiler should never crash with a stack overflow on any input.

Steps to reproduce:

The following Python script generates test files for each crash pattern. Each can be placed in src/lib.cairo of a Scarb project with cairo_execute = "2.16.1" dependency.

# Pattern 1: Deep negation chain — -(-(-(...(-a)...)))
depth = 500
expr = "a"
for _ in range(depth):
    expr = f"(0 - {expr})"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

# Pattern 2: Left-skewed tree — ((((a + a) + a) + a) + ...)
n = 500
expr = "a"
for _ in range(n):
    expr = f"({expr} + a)"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

# Pattern 3: Right-skewed tree — (a + (a + (a + (a + ...))))
n = 500
expr = "a"
for _ in range(n):
    expr = f"(a + {expr})"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

# Pattern 4: Alternating operators — a + a * a - a * a + a * ...
n = 500
ops = ["+", "*", "-"]
expr = "a"
for i in range(n):
    op = ops[i % 3]
    operand = "a"
    expr = f"({expr} {op} {operand})"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

# Pattern 5: Many intermediates summed — s0 + s1 + s2 + ... + sN
n = 500
lines = ["#[executable]", "fn main(a: felt252) -> felt252 {"]
for i in range(n):
    lines.append(f"    let s{i}: felt252 = a + {i};")
expr = " + ".join(f"s{i}" for i in range(n))
lines.append(f"    {expr}")
lines.append("}")
print("\n".join(lines))

# Pattern 6: Signal aliasing — a * a * a * ... * a
n = 500
expr = "a"
for _ in range(n - 1):
    expr = f"({expr} * a)"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

# Pattern 7: Mixed deep + wide — each level adds 5 terms
depth = 100
expr = "a"
for _ in range(depth):
    for _ in range(5):
        expr = f"({expr} + a)"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

# Pattern 8: Constant folding — (1 + 1 + 1 + ... + 1)
n = 500
expr = "1"
for _ in range(n - 1):
    expr = f"({expr} + 1)"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ a + {expr} }}")

# Pattern 9: Multiplication chain — (((a * a) * a) * a) * ...
# NOTE: Crashes at ~420, even lower threshold than addition patterns
n = 420
expr = "a"
for _ in range(n):
    expr = f"({expr} * a)"
print(f"#[executable]\nfn main(a: felt252) -> felt252 {{ {expr} }}")

For each pattern, run:

scarb build
# CRASH: thread '<unknown>' has overflowed its stack
# fatal runtime error: stack overflow, aborting

Related code:

Each pattern generates a syntactically valid Cairo program with a large expression tree. The simplest reproducer is Pattern 2 (left-skewed tree):

#[executable]
fn main(a: felt252) -> felt252 {
    // 500 nested additions: ((((a + a) + a) + a) + ... + a)
    ((((a + a) + a) + a) + a)  // ... continued to 500 levels
}

Other information:

Cross-compiler comparison across all 9 patterns:

Pattern	Threshold	Circom 2.2.3	Noir beta.19	Cairo 2.16.1	Leo 3.5.0
1. Deep negation chain	~500	✅ OK	Clean error	❌ CRASH	✅ OK
2. Left-skewed tree	~500	✅ OK	Clean error	❌ CRASH	✅ OK
3. Right-skewed tree	~500	✅ OK	Clean error	❌ CRASH	✅ OK
4. Alternating operators	~500	Clean error	Clean error	❌ CRASH	✅ OK
5. Many intermediates	~500	✅ OK	Clean error	❌ CRASH	✅ OK
6. Signal aliasing (aa...)	~500	Clean error	Clean error	❌ CRASH	✅ OK
7. Mixed deep + wide	~100×5	✅ OK	Clean error	❌ CRASH	✅ OK
8. Constant folding (1+1+...)	~500	✅ OK	Clean error	❌ CRASH	✅ OK
9. Multiplication chain	~420	Clean error	Clean error	❌ CRASH	✅ OK

Note: Pattern 9 (multiplication chain) crashes at a lower threshold (~420) than the addition-based patterns (~450-500), suggesting the multiplication processing path has slightly higher stack usage per recursion level.

Cairo is the only compiler that crashes. All others either handle the input or produce clean errors. Leo handles all patterns without any issues.

Suggested fix: Convert recursive AST traversal to iterative (stack-based) traversal in the compiler's expression processing passes.

Found via mutation-guided differential testing tool that generates structurally mutated IR expression trees and tests them across 4 ZK compilers.

[chamitro]

@orizi @mkaput please check

[orizi]

again - seem like just generated attack strings.

[chamitro]

@orizi Same as the other issue — these are synthetically generated by our automated testing tool, not from real-world code. But a compiler crash (SIGABRT) is always a problem regardless of the input. The compiler should produce a clean error instead of crashing.