classification
Title: stack overflow evaluating eval("()" * 30000)
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.2, Python 3.3, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Mark.Shannon, ag6502, amaury.forgeotdarc, benjamin.peterson, francismb, ggenellina, jcea, ncoghlan, pitrou, python-dev, serhiy.storchaka, terry.reedy
Priority: low Keywords: patch

Created on 2009-04-15 23:37 by ggenellina, last changed 2012-11-23 16:10 by jcea. This issue is now closed.

Files
File name Uploaded Description Edit
compiler_recursion_limit_check.patch ag6502, 2012-07-07 13:31 Patch review
compiler_recursion_limit_check-2.patch amaury.forgeotdarc, 2012-08-19 22:35 review
compiler_recursion_limit_check_2.patch ag6502, 2012-08-20 06:54 New version of the patch, considering all VISIT* macros and handling also visit_stmt review
Messages (26)
msg86006 - (view) Author: Gabriel Genellina (ggenellina) Date: 2009-04-15 23:37
Originally reported by Juanjo Conti at PyAr: 
http://blog.gmane.org/gmane.org.user-groups.python.argentina/
day=20090415

Evaluating this expression causes a stack overflow, and the Python 
interpreter exits abnormally:

eval("()" * 30000)

3.0.1, 2.6, 2.5 and current 2.x trunk all fail on Windows; the original 
reporter was likely using Linux. Some versions may require a larger 
constant instead of 30000.

2.4 isn't affected; it raises a "TypeError: 'tuple' object is not 
callable" as expected, even for extremely long sequences.

Alberto Bertogli said: inside eval, symtable_visit_expr() (Python/
symtable.c) is called recursively (thru the VISIT/VISIT_SEQ macros), 
eventually taking all stack space.
msg86008 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2009-04-15 23:51
This is a pathological case. I suppose we have to add a recursion
counter to the compiler struct.
msg99785 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2010-02-22 16:56
Another case from issue7985:
eval('l'+'[0]'*999999)
msg112925 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2010-08-04 23:43
On 3.1.2, WinXP, I immediately get
TypeError: 'tuple' object is not callable
so this seems to have been fixed for 3.x.
If released 2.7 is ok, we can close this.
msg164278 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-06-28 17:10
Terry, try a large constant. I can reproduce it on all versions from 2.6 to 3.3 with eval("()" * 300000).
msg164288 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2012-06-28 18:32
In 3.3.3a4 and b1, with original 30000, I no longer get TypeError, but box "python(w).exe has stopped working". So either Win7, 64 bit, on machine with much more memory makes a diffence, or something in code reverted. Is this really a security issue? (If so, up priority?)
msg164289 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2012-06-28 18:50
I don't think that eval is used in security context.
msg164840 - (view) Author: Andrea Griffini (ag6502) * Date: 2012-07-07 13:31
This is a fix for this issue.

The solution was to add two fields (recursion_depth and
recursion_limit) to the symbol table object and just increment and
check the depth in symtable_visit_expr raising a RuntimeError in case
the limit is exceeded.

The test case added also covers other similar cases (a.b.b.b.b.b...
and a[0][0][0][0]....)

There is no depth check in when visiting statement because I cannot
think to a way to nesting statements too much without getting other
errors before. If there is a way to do it, it would be trivial to also
cover that part.

The patch uses the current depth and current recursion limit but
multiplies them for a factor because I suppose that the amount of C
stack used by the compiler per recursion is smaller than the amount
used by the interpreter; the constant in the patch is 4. Using a
constant of 1 (i.e. just using the normal recursion limit) doesn't
allow a previously existing test about big expressions to pass.
msg168451 - (view) Author: Mark Shannon (Mark.Shannon) * Date: 2012-08-17 17:37
I've re-reviewed Andrea's patch (I was looking over Andrea's shoulder at the EuroPython sprint when he wrote it).

It looks good and applies cleanly. 
Could someone commit it please.
msg168596 - (view) Author: Francis MB (francismb) * Date: 2012-08-19 21:04
Just curiosity: how relate the magic numbers 100000 and 2000 in test_compiler_recursion_limit to recursion_depth and recursion_limit

Thanks!
msg168600 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-08-19 22:27
Indeed I don't like the introduction of COMPILER_STACK_FRAME_SCALE.
Re-using the existing infrastructure would be much easier to maintain.
The default recursion limit is 1000, which should cover any non-pathological code, IMHO.
msg168601 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2012-08-19 22:35
The patch is incomplete: the VISIT macro contains a "return 0;" and in this case st->recursion_depth is not decremented.
OTOH errors are never caught, so it's not necessary to do any cleanup in case of errors.
Here is a simplified patch.
msg168625 - (view) Author: Andrea Griffini (ag6502) * Date: 2012-08-20 06:53
I missed all the macrology present :-( ... the following is a patch that takes it into account (also defines a VISIT_QUIT macro to make more visible the exit points). The handling has been also extended to visit_stmt because the macros are shared.

Of course all this makes sense assuming that a cleanup in case of error is indeed desired...

BTW: shouldn't be all those statement macros of the "do{...}while(0)" form instead of just being wrapped in "{}" ? I see potential problems with if/else...
msg168628 - (view) Author: Andrea Griffini (ag6502) * Date: 2012-08-20 07:00
On Mon, Aug 20, 2012 at 12:27 AM, Antoine Pitrou <report@bugs.python.org> wrote:
> Indeed I don't like the introduction of COMPILER_STACK_FRAME_SCALE.
> Re-using the existing infrastructure would be much easier to maintain.
> The default recursion limit is 1000, which should cover any non-pathological code, IMHO.

I submitted a new version with the scale lowered to 3.

Using a lower value (e.g. 1) however makes "test_extended_args" fail
(the test tries to compile an expression with 2500+ terms).

If it's ok to make that test to throw instead then the whole scaling
could be removed.
msg174766 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-11-04 09:37
We want to minimise the risk of breaking working code. Making it easy to adjust this recursion limit separately from the main recursion limit by using a scaling factor is a good way to do that. It shouldn't increase the maintenance burden in any significant way, since the ratio of the stack depth increase in the compiler vs the main interpreter loop should be relatively constant across platforms.

Autogenerated code could easily hit the 1000 term limit - if anything, I'd be inclined to set it *higher* than 4 rather than lower, as breaking previously working code in a maintenance release is a bad thing, regardless of our opinion of the sanity of that code.
msg174777 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-11-04 10:51
> Autogenerated code could easily hit the 1000 term limit - if anything,
> I'd be inclined to set it *higher* than 4 rather than lower, as
> breaking previously working code in a maintenance release is a bad
> thing, regardless of our opinion of the sanity of that code.

We can simply apply the 1000 limit in Python 3.4 and mark the bug as
won't fix in other versions.

I don't think adding a scaling factor just to cope with hypothetical
silly code is a good thing in the long term.
msg174796 - (view) Author: Roundup Robot (python-dev) Date: 2012-11-04 13:54
New changeset ab02cd145f56 by Nick Coghlan in branch '3.3':
Issue #5765: Apply a hard recursion limit in the compiler
http://hg.python.org/cpython/rev/ab02cd145f56

New changeset bd1db93d76e1 by Nick Coghlan in branch 'default':
Issue #5765: Merge from 3.3
http://hg.python.org/cpython/rev/bd1db93d76e1
msg174797 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-11-04 13:55
You can take the scaling factor out if you really want, but it adds no real maintenance overhead, and better reflects the real stack usage.
msg174798 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-11-04 13:57
However, agreed on the won't fix for 3.2 and 2.7, although I'd consider it at least for 2.7 if someone went through and worked out a patch that applies cleanly.

For 3.2, this really isn't the kind of thing we'd want to do in the final regular maintenance release.
msg174799 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-11-04 13:58
> You can take the scaling factor out if you really want, but it adds no
> real maintenance overhead, and better reflects the real stack usage.

Can you also add a related snippet in
Tools/scripts/find_recursionlimit.py ?
msg174800 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-11-04 14:00
Note: if you do take the scaling factor out, don't forget to track down the reasons behind the original commit that added the test that broke *without* the scaling factor.

For me, "the test suite fails without it" is reason enough for me to say its needed - someone decided at some point to ensure that level of nesting worked, so if we're going to go back on that, we need to know the original reason why the test was added.

I think it's easier just to keep that code working, since we have a solution that *doesn't* break it and really isn't that complicated.
msg174801 - (view) Author: Roundup Robot (python-dev) Date: 2012-11-04 14:20
New changeset cf2515d0328b by Nick Coghlan in branch '3.3':
Issue #5765: Also check the compiler when finding the recursion limit
http://hg.python.org/cpython/rev/cf2515d0328b

New changeset 3712028a0c34 by Nick Coghlan in branch 'default':
Issue #5765: Merge from 3.3
http://hg.python.org/cpython/rev/3712028a0c34
msg174802 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-11-04 14:26
The sanity check in the recursion limit finding script is definitely a good idea, so I added that (as the commits show).

For the record, running that script on the 3.3 branch with my 4 GB RAM Fedora 17 ASUS Zenbook finds a maximum recursion limit around 16800, at which point test_add is the first one to die.
msg174804 - (view) Author: Mark Shannon (Mark.Shannon) * Date: 2012-11-04 14:33
I don't think there is any need for a scaling factor.
Expressions in auto-generated trees will tend to be trees of binary operator rather lists of purely unary operators. A tree of a billion items only has a depth of ~30.

There is no way an expression tree >1000 deep could possibly have any sane behaviour.
msg174805 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-11-04 14:35
> The sanity check in the recursion limit finding script is definitely a
> good idea, so I added that (as the commits show).

Didn't you make a mistake in the recursion factor there? Or is it really
10 rather than 3?
msg174808 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-11-04 14:54
Antoine: The scaling is deliberate higher in the recursion limit finder because we just want to ensure it hits the recursion limit (or blows the stack, if the scaling is wrong). In the tests, I cut it finer because I wanted to ensure we were straddling the allowed/disallowed boundary fairly closely in order to properly test the code that accounts for the *existing* recursion depth when initialising the compiler's internal state.

Mark: same answer I gave Antoine earlier. Without the scaling factor, a test fails. If you want to advocate for removing or changing that test instead, track down why it was added and provide a rationale for why it's no longer applicable. However, before you invest too much time in that, note that the trees generated by binary operators of the same precedence in CPython are *not* balanced (IIRC, the LHS is handled as a leaf expression), thus they also suffer from this recursion problem (if you look at the patch I committed, I added an extra test beyond those Andrea provided: a multiplication expression with a ridiculously large number of terms). I agree that path is the only one generated code is likely to hit, though, which is why I added a specific test for it.
History
Date User Action Args
2015-03-13 21:38:00ned.deilylinkissue23643 superseder
2012-11-23 16:10:12jceasetnosy: + jcea
2012-11-22 16:15:50serhiy.storchakalinkissue16527 superseder
2012-11-04 14:54:25ncoghlansetmessages: + msg174808
2012-11-04 14:35:40pitrousetmessages: + msg174805
2012-11-04 14:33:58Mark.Shannonsetmessages: + msg174804
2012-11-04 14:26:03ncoghlansetmessages: + msg174802
2012-11-04 14:20:01python-devsetmessages: + msg174801
2012-11-04 14:00:52ncoghlansetmessages: + msg174800
2012-11-04 13:58:55pitrousetmessages: + msg174799
2012-11-04 13:57:42ncoghlansetstatus: open -> closed
resolution: fixed
messages: + msg174798

stage: patch review -> resolved
2012-11-04 13:55:59ncoghlansetmessages: + msg174797
2012-11-04 13:54:22python-devsetnosy: + python-dev
messages: + msg174796
2012-11-04 10:51:37pitrousetmessages: + msg174777
2012-11-04 09:37:05ncoghlansetnosy: + ncoghlan
messages: + msg174766
2012-11-04 09:18:31serhiy.storchakalinkissue11383 superseder
2012-08-20 07:00:15ag6502setmessages: + msg168628
2012-08-20 06:54:01ag6502setfiles: + compiler_recursion_limit_check_2.patch

messages: + msg168625
2012-08-19 22:35:55amaury.forgeotdarcsetfiles: + compiler_recursion_limit_check-2.patch
2012-08-19 22:35:10amaury.forgeotdarcsetmessages: + msg168601
2012-08-19 22:27:08pitrousetversions: - Python 2.6, Python 3.1, Python 3.4
nosy: + pitrou

messages: + msg168600

stage: patch review
2012-08-19 21:04:59francismbsetnosy: + francismb
messages: + msg168596
2012-08-17 17:37:54Mark.Shannonsetnosy: + Mark.Shannon
messages: + msg168451
2012-07-25 11:38:44r.david.murraylinkissue15446 superseder
2012-07-07 13:31:14ag6502setfiles: + compiler_recursion_limit_check.patch

nosy: + ag6502
messages: + msg164840

keywords: + patch
2012-06-28 18:50:51serhiy.storchakasetmessages: + msg164289
2012-06-28 18:32:32terry.reedysetmessages: + msg164288
2012-06-28 17:10:22serhiy.storchakasetnosy: + serhiy.storchaka

messages: + msg164278
versions: + Python 2.6, Python 3.1, Python 3.2, Python 3.3, Python 3.4
2010-08-04 23:43:16terry.reedysetnosy: + terry.reedy

messages: + msg112925
versions: - Python 2.6, Python 2.5, Python 3.0
2010-02-22 16:56:42amaury.forgeotdarcsetnosy: + amaury.forgeotdarc
messages: + msg99785
2010-02-22 16:56:38amaury.forgeotdarclinkissue7985 superseder
2009-04-15 23:51:22benjamin.petersonsetpriority: low
nosy: + benjamin.peterson
messages: + msg86008

2009-04-15 23:37:36ggenellinacreate