[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:


New changeset dedb99acdb5bbc179872235f975248133d3fb440 by Serhiy Storchaka 
(Ashley Whetter) in branch '2.7':
bpo-32758: Warn that ast.parse() and ast.literal_eval() can segfault the 
interpreter (GH-5960) (GH-16565)
https://github.com/python/cpython/commit/dedb99acdb5bbc179872235f975248133d3fb440


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:


New changeset 8eb27cc35489848596d9fb4b1c91fac00ae75d21 by Serhiy Storchaka 
(Ashley Whetter) in branch '2.7':
bpo-32758: Warn that compile() can crash when compiling to an AST object 
(GH-6043) (GH-16566)
https://github.com/python/cpython/commit/8eb27cc35489848596d9fb4b1c91fac00ae75d21


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Roundup Robot]

Change by Roundup Robot :


--
pull_requests: +16157
pull_request: https://github.com/python/cpython/pull/16566

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Roundup Robot]

Change by Roundup Robot :


--
keywords: +patch
pull_requests: +16156
pull_request: https://github.com/python/cpython/pull/16565

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Karthikeyan Singaravelan]

Karthikeyan Singaravelan  added the comment:

This seems like an easy issue that the warnings in docs for ast need to be 
manually backported to 2.7 since miss Islington cannot cherry pick two PRs for 
2.7 in https://bugs.python.org/issue32758#msg313511 .

--
nosy: +Mariatta, cheryl.sabella, xtreak

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

- [x] ast module for Python 3
- [x] compile() for Python 3
- [x] dbm.dumb.open()
- [ ] ast module for Python 2 (see https://github.com/python/cpython/pull/5960)
- [ ] compile() for Python 2 (see https://github.com/python/cpython/pull/6043)

At this point there is only Python 2 stuff and I'm not bothered enough to see 
those changed, so I will leave this open for anyone who wants to put in the 
effort to backport the warnings.

--
assignee: brett.cannon -> 
keywords: +easy -patch
versions:  -Python 3.6, Python 3.7, Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[miss-islington]

Change by miss-islington :


--
pull_requests: +5809

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Change by Brett Cannon :


--
pull_requests: +5808

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

@Serhiy: Correct, which is what the warning says: 
https://github.com/python/cpython/pull/6043/files .

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Yury Selivanov]

Change by Yury Selivanov :


--
nosy:  -yselivanov

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

In 3.7 compile() can crash not only when compiling to an AST object (due to 
recursive AST optimization).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

Thanks for the feedback, Serhiy! Based on that, the new TODO list is:

- [x] ast module for Python 3
- [x] compile() for Python 3
- [ ] dbm.dumb.open()
- [ ] ast module for Python 2 (see https://github.com/python/cpython/pull/5960)
- [ ] compile() for Python 2 (see https://github.com/python/cpython/pull/6043)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

I think we can ignore the inspect module. It is unlikely that it will cause a 
crash unintentionally, and it is hard to use this for attacks. The attacker 
needs to create an extension function with malicious __text_signature__, but if 
he is able to execute arbitrary binary code, there is a much larger problem.

And perhaps there is no need to repeat the warning for exec() and eval(). They 
are considered more dangerous than compile().

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[miss-islington]

Change by miss-islington :


--
pull_requests: +5806

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[miss-islington]

Change by miss-islington :


--
pull_requests: +5807

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Change by Brett Cannon :


--
pull_requests: +5804

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

Actually, the TODO list is:

- [x] ast module for Python 3
- [ ] compile()
- [ ] eval() for >= 3.7
- [ ] exec() for >= 3.7
- [ ] dbm.dumb.open()
- [ ] inspect
- [ ] ast module for Python 2 (see https://github.com/python/cpython/pull/5960)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

I have the changes in for Python 3 for the ast module.

Updated TODO list:

- [x] ast module
- [ ] compile()
- [ ] eval() for >= 3.7
- [ ] exec() for >= 3.7
- [ ] dbm.dumb.open()
- [ ] inspect

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:


New changeset f2fffd41b42d88fe36b483852ae33d5a415b7082 by Brett Cannon (Miss 
Islington (bot)) in branch '3.7':
bpo-32758: Warn that ast.parse() and ast.literal_eval() can segfault the 
interpreter (GH-5960) (GH-6041)
https://github.com/python/cpython/commit/f2fffd41b42d88fe36b483852ae33d5a415b7082


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:


New changeset b316c44b0105d11a80ff971636143735f3655bbf by Brett Cannon (Miss 
Islington (bot)) in branch '3.6':
bpo-32758: Warn that ast.parse() and ast.literal_eval() can segfault the 
interpreter (GH-5960) (GH-6042)
https://github.com/python/cpython/commit/b316c44b0105d11a80ff971636143735f3655bbf


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[miss-islington]

Change by miss-islington :


--
pull_requests: +5803

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[miss-islington]

Change by miss-islington :


--
pull_requests: +5802

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:


New changeset 7a7f100eb352d08938ee0f5ba59c18f56dc4a7b5 by Brett Cannon in 
branch 'master':
bpo-32758: Warn that ast.parse() and ast.literal_eval() can segfault the 
interpreter (GH-5960)
https://github.com/python/cpython/commit/7a7f100eb352d08938ee0f5ba59c18f56dc4a7b5


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

You're probably right and it's worth propagating the warning a bit wider.

--
assignee: docs@python -> brett.cannon

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Thank you Brett! The comment LGTM.

Is it worth to add warnings to other functions?

* compile(), exec() and eval(). They are crashed due to recursion in the AST 
optimizer. This is a regression of 3.7. compile(..., PyCF_ONLY_AST) is the same 
as ast.parse() and crashed in older versions.

* dbm.dumb.open(). It calls ast.literal_eval(). The dbm.dumb databases are 
considered slow but portable. Before issue22885 this function was even more 
vulnerable due to using eval(). Since changing it to ast.literal_eval() some 
developers could consider it safe, but this is not true.

* A number of functions in the inspect module which directly or indirectly call 
ast.parse() on the __text_signature__ attribute. The risk of this vulnerability 
is very low.

--
versions: +Python 2.7

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

The PR adds the documentation warnings. Serhiy, can you double-check that I 
have the appropriate functions and the comment is acceptable?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Change by Brett Cannon :


--
keywords: +patch
pull_requests: +5728
stage: needs patch -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

A consequence of this is that ast.literal_eval() can crash.

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

It should be documented that ast.literal_eval() is not safe.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Change by Serhiy Storchaka :


--
assignee:  -> docs@python
components: +Documentation -Interpreter Core
nosy: +docs@python
stage:  -> needs patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  added the comment:

On Sun, Feb 11, 2018, 16:26 Serhiy Storchaka, 
wrote:

>
> Serhiy Storchaka  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 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Terry J. Reedy]

Terry J. Reedy  added the comment:

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."

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Brett Cannon]

Brett Cannon  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. 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, 
wrote:

>
> Serhiy Storchaka  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 
> 
> ___
>

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Terry J. Reedy]

Terry J. Reedy  added the comment:

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 0x01E7920F34A8>

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?

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Terry J. Reedy]

Terry J. Reedy  added the comment:

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.

--
nosy: +terry.reedy

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

There is also a regression in 3.7 when compile a long expression.

In 3.6:

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

In 3.7:

>>> compile('+a'*100, '?', 'eval')
Segmentation fault (core dumped)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue32758] Stack overflow when parse long expression to AST

[Serhiy Storchaka]

New submission from Serhiy Storchaka :

Python 2 can crash when compile long expression. 

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

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

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

But compiling to AST still can crash.

>>> import ast
>>> x = ast.parse('+chr(33)'*100)
Segmentation fault (core dumped)

--
components: Interpreter Core
messages: 311568
nosy: benjamin.peterson, brett.cannon, ncoghlan, serhiy.storchaka, yselivanov
priority: normal
severity: normal
status: open
title: Stack overflow when parse long expression to AST
type: crash
versions: Python 3.6, Python 3.7, Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com