Stack Overflow Prevention¶

Overview¶

Implementations MUST prevent stack overflow from deeply nested or recursive input.

The Problem¶

Recursive descent parsers use the call stack for nesting:

; Each level of nesting = one stack frame
2024-01-01 * "Transaction"
  Assets:A  1 USD {1 USD, 2024-01-01, "label"} @ 1 USD
    metadata: "deeply"
      nested: "value"

Malicious input with excessive nesting can exhaust the stack.

Attack Vectors¶

1. Deep Include Chains¶

file1.beancount includes file2.beancount
file2.beancount includes file3.beancount
...
file1000.beancount includes file1001.beancount

2. Nested Expressions¶

If arithmetic expressions are supported:

((((((((((((((((((((1+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)+1)

3. Deep Metadata¶

2024-01-01 open Assets:Test
  meta1: "value"
  ; Parser stores metadata stack

Requirements¶

Depth Limits¶

Structure	Minimum Limit	Recommended
Include depth	10	100
Expression nesting	50	200
Parser call depth	100	1000

Implementation¶

Implementations MUST either:

Use iterative parsing with explicit stack
Track recursion depth and reject at limit
Increase stack size with hard upper bound

Iterative Parsing¶

Convert recursive algorithms to iterative:

# Recursive (vulnerable)
def parse_expr(tokens):
    left = parse_term(tokens)
    if tokens.peek() == '+':
        tokens.consume()
        right = parse_expr(tokens)  # Recursive call
        return Add(left, right)
    return left

# Iterative (safe)
def parse_expr(tokens):
    stack = []
    while True:
        term = parse_term(tokens)
        if not stack or tokens.peek() != '+':
            break
        tokens.consume()
        stack.append(term)
    result = term
    while stack:
        result = Add(stack.pop(), result)
    return result

Depth Tracking¶

fn parse_expr(&mut self, depth: usize) -> Result<Expr, Error> {
    if depth > MAX_DEPTH {
        return Err(Error::MaxDepthExceeded);
    }
    // ... parsing logic
    self.parse_expr(depth + 1)?  // Pass depth
}

Stack Size Considerations¶

Platform	Default Stack	Configurable
Linux	8 MB	`ulimit -s`
macOS	8 MB	`ulimit -s`
Windows	1 MB	Linker flag
WASM	1 MB	Compile option

Error Messages¶

error: Maximum nesting depth exceeded
  --> malicious.beancount:1000:1
  |
  = depth: 101
  = limit: 100
  = hint: simplify expression or increase --max-depth

Testing¶

Create test files with:

Include depth at exactly limit → accept
Include depth at limit + 1 → reject
Expression nesting at limit → accept
Expression nesting at limit + 1 → reject

Verify no crash, only clean error.