Stack overflow in Drop of ruff's AST on large left-associative chains

Open

ajanonopened 16d ago

Sandboxed code can cause monty to SIGABRT with a stack overflow on long left-associative binary operator chains.

Simplest MWE (works with *, |, ^...):

eval('1+' * 1_000_000 + '1')

In action, tested against latest main:

$ ./target/release/monty -c "eval('1+' * 1_000_000 + '1')"

thread 'main' (233626) has overflowed its stack
fatal runtime error: stack overflow, aborting
Aborted                    (core dumped) ./target/release/monty -c "eval('1+' * 1_000_000 + '1')"

This also works by creating very long chains manually:

$ python -c "print('x=' + '1+' * 1_000_000 + '1')" > test.py
$ ./target/release/monty test.py

thread 'main' (275519) has overflowed its stack
fatal runtime error: stack overflow, aborting

CPython, for comparison, raises:

$ python -c "eval('1+' * 1_000_000 + '1')"
Traceback (most recent call last):
  File "<string>", line 1, in <module>
    eval('1+' * 1_000_000 + '1')
    ~~~~^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: Stack overflow (used 8148 kB) during compilation

This looks similar in nature to #362, but slightly different here. These chains are built iteratively, so their depth is bounded only by input length and the recursion guard never fires. The overflow is in the recursive Drop of the resulting tree:

#0  0x0000555559c54c15 in core::ptr::drop_glue<ruff_python_ast::generated::ExprBinOp> () at /rustc/b940084d7eb6a299eb4bfeb8e34901bc051e7ac4/library/core/src/ptr/mod.rs:847
#1  0x0000555559c54437 in core::ptr::drop_glue<ruff_python_ast::generated::Expr> () at /rustc/b940084d7eb6a299eb4bfeb8e34901bc051e7ac4/library/core/src/ptr/mod.rs:847
#2  0x0000555559c5130a in core::ptr::drop_glue<alloc::boxed::Box<ruff_python_ast::generated::Expr, alloc::alloc::Global>> ()

This might be fixed by changing the pre-scan so that each left-associative operator also adds to the nesting estimate. This needs to be done there, before ruff builds the tree.

As far as I understand, astral-sh/ruff#25480 would have fixed this problem, but it was closed unmerged.

Happy to work on a PR, I think I have a fix locally by extending the pre-scan.

Activity

samuelcolvin16d ago

this is a known issue, and basically unfixable in monty, it's one of the reasons we run the interpreter in a subprocess.

https://github.com/astral-sh/ruff/pull/29181 should help.

samuelcolvin16d ago

If you have a potential fix, happy to hear it?

ajanon16d ago

Thanks for the answer!

I think astral-sh/ruff#29181 as-is won't catch this, because the binary ops chains are built in a loop, see parse_binary_expression_or_higher_recursive

So, there, the recursion depth stays mostly falt, but the tree can grow a million deep (bounded by input length?).

We have the same issue with postfix operators also:

./target/release/monty -c "eval('a' + '.x' * 1_000_000)"

thread 'main' (348922) has overflowed its stack
fatal runtime error: stack overflow, aborting

And there, the loop is in parse_postfix_expression.

This is covered in crates/monty/tests/security.rs at depth 200, but at depth 1M, dropping the rest of the tree still overflows.

Same SIGABRT with f()()... and x[0][0]....

To fix this, I see two ways:

Pre-scan counts binary operators and postfix chains, and this becomes a SyntaxError: Source is too deeply nested rather than an abort. That also covers ruff's own error path ('1+' * 1_000_000 + '1 +' overflows in Parsed::into_errors, before Monty sees the tree). I have this working locally for operators, I would need to look a bit more for postfix chains. It does extend the pre-scan, which I understand astral-sh/ruff#29181 is supposed to replace.
Or, in your ruff PR, you can count each link in these loops against the same recursion limit, which I believe should work.

Happy to go either way.