classification
Title: Stack overflow when parse long expression to AST
Type: crash Stage: needs patch
Components: Documentation Versions: Python 3.8, Python 3.7, Python 3.6
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: docs@python Nosy List: benjamin.peterson, brett.cannon, docs@python, ncoghlan, serhiy.storchaka, terry.reedy, yselivanov
Priority: normal Keywords:

Created on 2018-02-03 18:22 by serhiy.storchaka, last changed 2018-02-24 07:04 by serhiy.storchaka.

Messages (10)
msg311568 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-03 18:22
Python 2 can crash when compile long expression. 

>>> x = eval('""' + '+chr(33)'*100000)
Segmentation fault (core dumped)

This was fixed in Python 3. RecursionError is raised now.

>>> x = eval('""' + '+chr(33)'*100000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded during compilation
>>> x = eval('+chr(33)'*1000000)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded during compilation

But compiling to AST still can crash.

>>> import ast
>>> x = ast.parse('+chr(33)'*1000000)
Segmentation fault (core dumped)
msg311570 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-03 18:29
There is also a regression in 3.7 when compile a long expression.

In 3.6:

>>> compile('+a'*1000000, '?', 'eval')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RecursionError: maximum recursion depth exceeded during compilation

In 3.7:

>>> compile('+a'*1000000, '?', 'eval')
Segmentation fault (core dumped)
msg311920 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2018-02-10 00:22
Experimenting on Windows with IDLE's current 3.7 Shell, where a user process crash restarts Shell, compile('+a'*31365, '?', 'eval') consistently gives RecursionError, values a bit larger sometimes crash, and values much larger (32000, at max) consistently crash.  Perhaps it is not just a coincidence that the regressed lower limit for crashing is near 2**15.
msg311922 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2018-02-10 00:30
Ditto as to the limit for ast.parse.

>>> import ast; ast.parse('+chr(33)'*32000)
	    
============================ RESTART: Shell =========================
>>> import ast; ast.parse('+chr(33)'*31000)
	    
<_ast.Module object at 0x000001E7920F34A8>

I see the same in 3.6 and 3.5, so this is not a 3.7 regression.  Rather, was the ast.parse behavior somehow copied into compile for 3.7, perhaps by 'simplifying' code?
msg311945 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-10 09:00
On Linux the limit is much larger that 2**15. This depends on the stack size, it is smaller on Windows.

The stack is overflowed by recursive call of ast2obj_expr in Python/Python-ast.c. The same problem exists in other recursive AST processing code: optimizing, unparsing. This is why 3.7 can crash in cases when 3.6 was not crashed.

I don't see an easy way of fixing this. The common way is surrounding recursive calls with Py_EnterRecursiveCall()/Py_LeaveRecursiveCall(). But this make the limit too small (1000 by default). In other cases it is enough. The data structures with 1000 levels of nesting are rare. In any case the Python compiler has lower limit on nesting indented blocks. But in this case the linear sequence of binary operators is compiled to deeply nested structure.

I see two hard ways of properly fixing this.

1. Rewrite all AST expression processing code with using an explicit stack instead of function stack. This will complicate a lot of C code too much. Python code should be rewritten too if you don't want to get a RecursionError in corner cases, but for common cases it can be left unmodified.

2. Change binary operations representation, so that a+b+c+d will be represented as ('+', (a, b, c, d)) instead of ('+', ('+', ('+', a, b), c), d). This is backward incompatible change and needs to rewrite any AST processing code (in C and Python). This solution can't be backported. But the resulting code will be simpler than when rewrite them for the first approach.
msg311978 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2018-02-11 03:26
The other option is to simply not worry about it and acknowledge you can
crash the compiler with a crazy-sized expression. Option 1 is too much work
and option 2 takes us from an AST to more of an s-expression format which
is a significant shift in design (now if people want to make that kind of
change that's fine, but it should be consistent across the board).

On Sat, Feb 10, 2018, 14:30 Serhiy Storchaka, <report@bugs.python.org>
wrote:

>
> Serhiy Storchaka <storchaka+cpython@gmail.com> added the comment:
>
> On Linux the limit is much larger that 2**15. This depends on the stack
> size, it is smaller on Windows.
>
> The stack is overflowed by recursive call of ast2obj_expr in
> Python/Python-ast.c. The same problem exists in other recursive AST
> processing code: optimizing, unparsing. This is why 3.7 can crash in cases
> when 3.6 was not crashed.
>
> I don't see an easy way of fixing this. The common way is surrounding
> recursive calls with Py_EnterRecursiveCall()/Py_LeaveRecursiveCall(). But
> this make the limit too small (1000 by default). In other cases it is
> enough. The data structures with 1000 levels of nesting are rare. In any
> case the Python compiler has lower limit on nesting indented blocks. But in
> this case the linear sequence of binary operators is compiled to deeply
> nested structure.
>
> I see two hard ways of properly fixing this.
>
> 1. Rewrite all AST expression processing code with using an explicit stack
> instead of function stack. This will complicate a lot of C code too much.
> Python code should be rewritten too if you don't want to get a
> RecursionError in corner cases, but for common cases it can be left
> unmodified.
>
> 2. Change binary operations representation, so that a+b+c+d will be
> represented as ('+', (a, b, c, d)) instead of ('+', ('+', ('+', a, b), c),
> d). This is backward incompatible change and needs to rewrite any AST
> processing code (in C and Python). This solution can't be backported. But
> the resulting code will be simpler than when rewrite them for the first
> approach.
>
> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <https://bugs.python.org/issue32758>
> _______________________________________
>
msg311993 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-11 10:56
> The other option is to simply not worry about it and acknowledge you can
> crash the compiler with a crazy-sized expression.

Agreed, this is the most practical option. Do you want to write such acknowledgement?
msg312009 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2018-02-11 19:25
If ast_parse returns, a correct tree (A) rather than a buggy tree is a hard requirement.  If ast_parse does not return,  an exception (B) rather than a crash is strongly desired.  We should not risk A to get B.  I presume that Serhiy is suggesting that option 1 either has such a risk or would consume developer resources that might be better spent on other improvements.

For Python, option 2, seems pretty useless for real code because there are much better ways to sum a long sequence: sum(iterable_of_numbers),  seq.append, ''.join(iterable_of_string).

Possible addition to the ast.parse entry.
"Syntactically correct but extremely long or complex source strings may result in a RecursionError or program crash."
msg312030 - (view) Author: Brett Cannon (brett.cannon) * (Python committer) Date: 2018-02-12 05:30
On Sun, Feb 11, 2018, 16:26 Serhiy Storchaka, <report@bugs.python.org>
wrote:

>
> Serhiy Storchaka <storchaka+cpython@gmail.com> added the comment:
>
> > The other option is to simply not worry about it and acknowledge you can
> > crash the compiler with a crazy-sized expression.
>
> Agreed, this is the most practical option. Do you want to write such
> acknowledgement?
>

I think adding a test to test_crashers and an appropriate comment pointing
to this issue is sufficient.

> ----------
>
> _______________________________________
> Python tracker <report@bugs.python.org>
> <https://bugs.python.org/issue32758>
> _______________________________________
>
msg312701 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2018-02-24 07:04
A consequence of this is that ast.literal_eval() can crash.

>>> import ast
>>> ast.literal_eval("+0"*200000)
Segmentation fault (core dumped)

It should be documented that ast.literal_eval() is not safe.
History
Date User Action Args
2018-02-24 07:04:15serhiy.storchakasetmessages: + msg312701
2018-02-12 08:02:43serhiy.storchakasetassignee: docs@python

nosy: + docs@python
components: + Documentation, - Interpreter Core
stage: needs patch
2018-02-12 05:30:45brett.cannonsetmessages: + msg312030
2018-02-11 19:25:22terry.reedysetmessages: + msg312009
2018-02-11 10:56:51serhiy.storchakasetmessages: + msg311993
2018-02-11 03:26:42brett.cannonsetmessages: + msg311978
2018-02-10 09:00:06serhiy.storchakasetmessages: + msg311945
2018-02-10 00:30:44terry.reedysetmessages: + msg311922
2018-02-10 00:22:41terry.reedysetnosy: + terry.reedy
messages: + msg311920
2018-02-03 18:29:47serhiy.storchakasetmessages: + msg311570
2018-02-03 18:22:51serhiy.storchakacreate