Eval with too high string multiplication crashes newer Python versions

[Erik-Lamers1]

BPO	42609
Nosy	@methane, @pmp-p, @ambv, @serhiy-storchaka, @corona10, @hongweipeng, @isidentical, @iritkatriel, @stestagg, @Erik-Lamers1
PRs	bpo-42609: Check recursion depth in the AST validator and optimizer #23744 [3.9] bpo-42609: Check recursion depth in the AST validator and optimizer (GH-23744). #25634

^{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 = None
created_at = <Date 2020-12-09.11:05:07.647>
labels = ['interpreter-core', '3.10', '3.9', 'type-crash']
title = 'Eval with too high string multiplication crashes newer Python versions'
updated_at = <Date 2022-01-14.14:30:39.123>
user = 'https://github.com/Erik-Lamers1'

bugs.python.org fields:

activity = <Date 2022-01-14.14:30:39.123>
actor = 'iritkatriel'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2020-12-09.11:05:07.647>
creator = 'Erik-Lamers1'
dependencies = []
files = []
hgrepos = []
issue_num = 42609
keywords = ['patch']
message_count = 6.0
messages = ['382791', '382844', '382849', '382910', '391850', '410562']
nosy_count = 10.0
nosy_names = ['methane', 'pmpp', 'lukasz.langa', 'serhiy.storchaka', 'corona10', 'hongweipeng', 'BTaskaya', 'iritkatriel', 'stestagg', 'Erik-Lamers1']
pr_nums = ['23744', '25634']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue42609'
versions = ['Python 3.9', 'Python 3.10']

[Erik-Lamers1]

For Python version 3.7 and above the following statement will end up in a segfault.

eval("1 + 100"*1000000)

Whereas Python versions 3.6 and below would tread this as a Recursion error.

[stestagg]

Looks like it was introduced by 7ea143a:

bpo-29469: Move constant folding to AST optimizer (GH-2858)

[stestagg]

In python 3.7/8, It's a stack overflow in the constant folding code.

On master, the overflow seems to come out of validate_expr.c.

• thread Support "bpo-" in Misc/NEWS #1, name = 'python3', stop reason = signal SIGSEGV: invalid address (fault address: 0x7fffff7feff8)
  frame #0: 0x00005555557aadba python3`validate_expr(exp=0x00005555602617c0, ctx=Load) at ast.c:224:16
  221 }
  222 return validate_exprs(exp->v.BoolOp.values, Load, 0);
  223 case BinOp_kind:
  -> 224 return validate_expr(exp->v.BinOp.left, Load) &&
  225 validate_expr(exp->v.BinOp.right, Load);
  226 case UnaryOp_kind:
  227 return validate_expr(exp->v.UnaryOp.operand, Load);

300,000 ish stack frames of this:

frame bpo-70832: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150af40, ctx=Load) at ast.c:224:16
frame bpo-70833: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b050, ctx=Load) at ast.c:224:16
frame bpo-70834: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b160, ctx=Load) at ast.c:224:16
frame bpo-70835: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b270, ctx=Load) at ast.c:224:16
frame bpo-70836: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b380, ctx=Load) at ast.c:224:16
frame bpo-70837: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b490, ctx=Load) at ast.c:224:16
frame bpo-70838: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b5a0, ctx=Load) at ast.c:224:16
frame bpo-70839: 0x00005555557aadbf python3`validate_expr(exp=0x000055556150b6b0, ctx=Load) at ast.c:224:16

On the one hand, pure python code should never segfault, on the other hand, evalling untrusted input has bigger problems than a segfault on carefully crafted input.

[serhiy-storchaka]

This is known issue, but interesting that the cause of the crash is different in 3.7-3.8 and 3.9+.

PR 23744 adds recursion checks in the AST validator and optimizer similar to the checks in the symtable. It should not break any existing code because too deep AST tree did not pass checks in the symtable in any case.

But it does not solve all problems. A compound statement with too many "elif"s is still crashed because the new parser uses recursion in C to parse it (elif_stmt_rule). I think it should be a separate issue.

[serhiy-storchaka]

New changeset face87c by Serhiy Storchaka in branch 'master':
bpo-42609: Check recursion depth in the AST validator and optimizer (GH-23744)
face87c

[iritkatriel]

Apart from the 3.9 backport this is complete.

[kumaraditya303]

Python 3.9 is security fix only now so closing.