Compiling recursive Python ASTs crash the interpreter

[benjaminp]

BPO	11105
Nosy	@terryjreedy, @gpshead, @abalkin, @benjaminp, @jkloth, @meadori, @ambv, @ericsnowcurrently, @pablogsal, @miss-islington, @isidentical, @Fidget-Spinner
PRs	bpo-11105: Do not crash when compiling recursive ASTs #20594 [3.10] bpo-11105: Do not crash when compiling recursive ASTs (GH-20594) #26521 [3.9] bpo-11105: Do not crash when compiling recursive ASTs (GH-20594) #26522 bpo-11105: use a lower recursion limit for infinite recursion tests #26550 [TEMP] bpo-11105: use PY_LOCAL()s for AST converter functions #26554 bpo-44336: Prevent hanging on child process handles #26578 bpo-11105: document the new test.support.infinite_recursion context m… #26604 [3.9] bpo-11105: reduce the recursion limit for tests (GH-26550). #26605 [3.10] bpo-11105: reduce the recursion limit for tests (GH-26550). #26607

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2021-06-08.17:42:44.965>
created_at = <Date 2011-02-03.05:02:39.444>
labels = ['interpreter-core', '3.10', '3.9', 'type-crash', '3.11']
title = 'Compiling recursive Python ASTs crash the interpreter'
updated_at = <Date 2021-06-08.17:42:44.964>
user = 'https://github.com/benjaminp'

bugs.python.org fields:

activity = <Date 2021-06-08.17:42:44.964>
actor = 'BTaskaya'
assignee = 'none'
closed = True
closed_date = <Date 2021-06-08.17:42:44.965>
closer = 'BTaskaya'
components = ['Interpreter Core']
creation = <Date 2011-02-03.05:02:39.444>
creator = 'benjamin.peterson'
dependencies = []
files = []
hgrepos = []
issue_num = 11105
keywords = ['patch']
message_count = 27.0
messages = ['127783', '127797', '127798', '127799', '127800', '127801', '127816', '155978', '155986', '358952', '359122', '373078', '373084', '395040', '395046', '395050', '395172', '395173', '395174', '395177', '395189', '395190', '395341', '395342', '395343', '395344', '395345']
nosy_count = 12.0
nosy_names = ['terry.reedy', 'gregory.p.smith', 'belopolsky', 'benjamin.peterson', 'jkloth', 'meador.inge', 'lukasz.langa', 'eric.snow', 'pablogsal', 'miss-islington', 'BTaskaya', 'kj']
pr_nums = ['20594', '26521', '26522', '26550', '26554', '26578', '26604', '26605', '26607']
priority = None
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue11105'
versions = ['Python 3.9', 'Python 3.10', 'Python 3.11']

[benjaminp]

You don't want to know why I was thinking about this...

$ ./python 
Python 3.2rc2+ (py3k:88302, Feb  1 2011, 19:02:10) 
[GCC 4.4.4] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import ast
>>> e = ast.UnaryOp(op=ast.Not(), lineno=0, col_offset=0)
>>> e.operand = e
>>> compile(ast.Expression(e), "<test>", "eval")
Segmentation fault

[abalkin]

Looks like a stack overflow caused by an infinite recursion. I am not sure if it is possible to add cycle detection code without sacrificing performance or setting some arbitrary limits.

I wonder: Why ast nodes need to be mutable?

[benjaminp]

2011/2/3 Alexander Belopolsky <report@bugs.python.org>:

Alexander Belopolsky <belopolsky@users.sourceforge.net> added the comment:

Looks like a stack overflow caused by an infinite recursion.  I am not sure if it is possible to add cycle detection code without sacrificing performance or setting some arbitrary limits.

Yes, it's definitely low priority. It's probably easier to crash the
interpreter by producing differently malformed ast anyway.

I wonder: Why ast nodes need to be mutable?

So people can change them.

[abalkin]

On Thu, Feb 3, 2011 at 12:08 PM, Benjamin Peterson
<report@bugs.python.org> wrote:
..

> I wonder: Why ast nodes need to be mutable?

So people can change them.

Well, they are hashable, so this needs to be done carefully. Is this
necessary for AST-based optimizations? Does Python actually change
AST after it has been created? Note that for some optimizations it
may be more appropriate to build a new tree rather than mutate the old
one. Depending on the algorithm, you may or may not need to change
the nodes after they have been created in the process.

[benjaminp]

2011/2/3 Alexander Belopolsky <report@bugs.python.org>:
>
> Alexander Belopolsky <belopolsky@users.sourceforge.net> added the comment:
>
> On Thu, Feb 3, 2011 at 12:08 PM, Benjamin Peterson
> <report@bugs.python.org> wrote:
> ..
>>> I wonder: Why ast nodes need to be mutable?
>>
>> So people can change them.
>
> Well, they are hashable, so this needs to be done carefully.  Is this
> necessary for AST-based optimizations?  Does Python actually change
> AST after it has been created?  Note that for some optimizations it
> may be more appropriate to build a new tree rather than mutate the old
> one.  Depending on the algorithm, you may or may not need to change
> the nodes after they have been created in the process.

Other people are, though. The hash is by identity anyway.

[benjaminp]

2011/2/3 Alexander Belopolsky <report@bugs.python.org>:
>
> Alexander Belopolsky <belopolsky@users.sourceforge.net> added the comment:
>
> On Thu, Feb 3, 2011 at 12:08 PM, Benjamin Peterson
> <report@bugs.python.org> wrote:
> ..
>>> I wonder: Why ast nodes need to be mutable?
>>
>> So people can change them.
>
> Well, they are hashable, so this needs to be done carefully.  Is this
> necessary for AST-based optimizations?  Does Python actually change
> AST after it has been created?  Note that for some optimizations it
> may be more appropriate to build a new tree rather than mutate the old
> one.  Depending on the algorithm, you may or may not need to change
> the nodes after they have been created in the process.

Other people are, though. The hash is by identity anyway.

[birkenfeld]

Alex: If the node attributes were not mutable, it would be extremely awkward, not to say inefficient, to mutate an already existing AST as returned by ast.parse().

The AST objects in the _ast module aren't what Python works with internally, anyway. When calling ast.parse(), the AST is converted to Python objects (these are defined in Python-ast.c), and compile()ing such an object converts them back to the internal tree representation. This conversion is where recursions would need to be handled.

[gpshead]

i haven't confirmed if it is this exact bug but I believe a coworker just ran into something similar. he wrote code to use the ast to remove docstrings from code before passing it to compile() (as that saves a noticable amount of memory). in the case the ast for code like:

def foo():
  """this is a docstring."""

Removing the docstring and passing such a thing to compile triggers a problem. A workaround was to add a pass in such cases:

if (node.body and isinstance(node.body[0], ast.Expr) and
isinstance(node.body[0].value, ast.Str)):
docstring = node.body.pop(0)
if len(node.body) == 0:
# An empty body will sometimes provoke a segfault when you call
# compile on the code object.
node.body.append(ast.Pass(lineno=docstring.lineno,
col_offset=docstring.col_offset))

regardless, it'd be better if compile() *never* crashed on strange input.

[benjaminp]

Have him try on 3.3. This should be less of an issue there where there is an AST validator. It doesn't fix this bug, but it does fix most accidental AST construction bugs.

[isidentical]

We can probably implement something like this to prevent this happening
diff --git a/Parser/asdl_c.py b/Parser/asdl_c.py
index daac0966f5..f9da52da7f 100755
--- a/Parser/asdl_c.py
+++ b/Parser/asdl_c.py
@@ -559,6 +559,11 @@ class Obj2ModVisitor(PickleVisitor):
             self.emit("asdl_seq_SET(%s, i, val);" % field.name, depth+2)
             self.emit("}", depth+1)
         else:
+            self.emit("if (obj == tmp) {", depth+1)
+            self.emit("PyErr_SetString(PyExc_RuntimeError, \"Recursing fields "
+                      "are not supported for AST nodes.\");", depth+2, reflow=False)
+            self.emit("goto failed;", depth+2)
+            self.emit("}", depth+1)
             self.emit("res = obj2ast_%s(tmp, &%s, arena);" %
                       (field.type, field.name), depth+1)
             self.emit("if (res != 0) goto failed;", depth+1)

[pppery]

What about indirect cycles like below:

>> e = ast.UnaryOp(op=ast.Not(), lineno=0, col_offset=0)
>> f = ast.UnaryOp(op=ast.Not(), lineno=0, col_offset=0)
>> e.operand = f
>> f.operand = e
>> compile(ast.Expression(e), "<test>", "eval")

(I tested, this also crashes)

[terryjreedy]

With 3.9 on Windows, using Benjamin's example, I do not get the Windows equivalent of a seg fault. However, execution stops at compile with no exception, including SystemExit.

These examples amount to limited fuzz testing of compile(). I think it should raise something like "SyntaxError: recursive ast" or even 'bad ast' if malformed non-recursive asts have the same issue.