integer overflow in itertools.product

[pkt]

BPO	23364
Nosy	@serhiy-storchaka
Files	poc_product.py

^{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 2015-02-03.07:41:24.007>
created_at = <Date 2015-02-01.13:55:04.096>
labels = ['type-crash']
title = 'integer overflow in itertools.product'
updated_at = <Date 2015-02-04.06:09:59.262>
user = 'https://bugs.python.org/pkt'

bugs.python.org fields:

activity = <Date 2015-02-04.06:09:59.262>
actor = 'python-dev'
assignee = 'none'
closed = True
closed_date = <Date 2015-02-03.07:41:24.007>
closer = 'serhiy.storchaka'
components = []
creation = <Date 2015-02-01.13:55:04.096>
creator = 'pkt'
dependencies = []
files = ['37963']
hgrepos = []
issue_num = 23364
keywords = []
message_count = 10.0
messages = ['235172', '235220', '235226', '235230', '235231', '235233', '235270', '235271', '235306', '235375']
nosy_count = 4.0
nosy_names = ['Arfrever', 'python-dev', 'serhiy.storchaka', 'pkt']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue23364'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4', 'Python 3.5']

[pkt]

# Bug
# ---
#
# static PyObject *
# product_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
# {
# ...
# 1 nargs = (repeat == 0) ? 0 : PyTuple_GET_SIZE(args);
# 2 npools = nargs * repeat;
#
# 3 indices = PyMem_Malloc(npools * sizeof(Py_ssize_t));
# ...
#
# 4 for (i=0; i < nargs ; ++i) {
# ...
# indices[i] = 0;
# }
#
# 1. nargs is the number of functions arguments (not counting the keyword arg).
# We set this value to 2^16 using argument unpacking (*args).
# 2. We set the 'repeat' keyword argument to 2^16, so npools=2^32==0 (modulo 2^32)
# 3. npools*4=0, so malloc allocates a 0 byte buffer
# 4. nargs=2^16, so the loop writes well beyond the buffer's end
#
# Breakpoint 1, product_new (type=0x8338c80 <product_type>,
# args=('a', ...(truncated), kwds={'repeat': 65536})
# at ./Modules/itertoolsmodule.c:1998
# ...
\bpo-2021 nargs = (repeat == 0) ? 0 : PyTuple_GET_SIZE(args);
# (gdb) n
\bpo-2022 npools = nargs * repeat;
# (gdb) print nargs
# $14 = 65536
# (gdb) print repeat
# $15 = 65536
# (gdb) n
\bpo-2024 indices = PyMem_Malloc(npools * sizeof(Py_ssize_t));
# (gdb) print npools
# $16 = 0
# (gdb) c
# Continuing.
#
# Crash
# -----
#
# We crash in a different place, because there was sufficient allocated memory
# after the "indices" buffer.
#
# Program received signal SIGSEGV, Segmentation fault.
# 0x08313940 in PyTuple_Type ()
# (gdb) bt
# #0 0x08313940 in PyTuple_Type ()
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# #1 0x080f27c7 in PyObject_Hash (v=) at Objects/object.c:747
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# #2 0x080e132f in PyDict_GetItem (op=, key=) at Objects/dictobject.c:1070
# #2 0x080e132f in PyDict_GetItem (op=, key=) at Objects/dictobject.c:1070
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# #3 0x080e5261 in _PyDict_GetItemId (dp=, key=0x832bd20 <PyId_displayhook.11614>) at Objects/dictobject.c:2729
# #4 0x0806f0e8 in _PySys_GetObjectId (key=0x832bd20 <PyId_displayhook.11614>) at ./Python/sysmodule.c:57
# #5 0x081bb52a in PyEval_EvalFrameEx (f=Frame 0x404ea1ac, for file <stdin>, line 1, in <module> (), throwflag=0) at Python/ceval.c:1848
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# #6 0x081c8574 in PyEval_EvalCodeEx (_co=<code at remote 0x40531c58>, globals=, locals=, args=0x0, argcount=0, kws=0x0, kwcount=0,
# defs=0x0, defcount=0, kwdefs=0x0, closure=0x0) at Python/ceval.c:3578
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# #7 0x081b51ef in PyEval_EvalCode (co=<code at remote 0x40531c58>, globals=, locals=) at Python/ceval.c:773
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# Python Exception <type 'exceptions.UnicodeDecodeError'> 'utf8' codec can't decode byte 0xc8 in position 1: invalid continuation byte:
# #8 0x08065e89 in run_mod (mod=0x9ea5758, filename='<stdin>', globals=, locals=, flags=0xbf85fbc0, arena=0x9e64220)
# at Python/pythonrun.c:2180
# #9 0x080637fd in PyRun_InteractiveOneObject (fp=0x40231ac0 <IO_2_1_stdin>, filename='<stdin>', flags=0xbf85fbc0)
# at Python/pythonrun.c:1445
# #10 0x08063243 in PyRun_InteractiveLoopFlags (fp=0x40231ac0 <IO_2_1_stdin>, filename_str=0x826bc06 "<stdin>", flags=0xbf85fbc0)
# at Python/pythonrun.c:1324
# #11 0x0806305f in PyRun_AnyFileExFlags (fp=0x40231ac0 <IO_2_1_stdin>, filename=0x826bc06 "<stdin>", closeit=0, flags=0xbf85fbc0)
# at Python/pythonrun.c:1286
# #12 0x08079e8a in run_file (fp=0x40231ac0 <IO_2_1_stdin>, filename=0x0, p_cf=0xbf85fbc0) at Modules/main.c:319
# #13 0x0807a988 in Py_Main (argc=1, argv=0x9e45010) at Modules/main.c:751
# #14 0x0805dc34 in main (argc=1, argv=0xbf85fd04) at ./Modules/python.c:69
#
# OS info
# -------
#
# % ./python -V
# Python 3.4.1
#
# % uname -a
# Linux ubuntu 3.8.0-29-generic #42~precise1-Ubuntu SMP Wed Aug 14 15:31:16 UTC 2013 i686 i686 i386 GNU/Linux
#

import itertools as it
args=["a"]*(2**16)
it.product(*args, repeat=2**16)

[python-dev]

New changeset 7133582b6769 by Benjamin Peterson in branch '3.3':
check for overflows in permutations() and product() (closes bpo-23363, closes bpo-23364)
https://hg.python.org/cpython/rev/7133582b6769

New changeset 9ae055c3db32 by Benjamin Peterson in branch '3.4':
merge 3.3 (bpo-23364, bpo-23363)
https://hg.python.org/cpython/rev/9ae055c3db32

New changeset 31dc5a40d2ab by Benjamin Peterson in branch 'default':
merge 3.4 (bpo-23364, bpo-23363)
https://hg.python.org/cpython/rev/31dc5a40d2ab

New changeset acc2c3479f2e by Benjamin Peterson in branch '2.7':
check for overflows in permutations() and product() (closes bpo-23363, closes bpo-23364)
https://hg.python.org/cpython/rev/acc2c3479f2e

[serhiy-storchaka]

+ with self.assertRaises(OverflowError):
+ product(["a"]*(2**16), repeat=2**16)

The test needs 16GiB. May be use repeat=2**13?

[pkt]

Why do you think this test needs 16GiB?

[serhiy-storchaka]

2**16 * 2**16 * sizeof(Py_ssize_t) = 16GiB

[pkt]

You mean 64bit? On 32 it'll overflow and that's the point.

[serhiy-storchaka]

Oh, and actually the test is wrong. It fails on 32-bit with -M2G. Should be:

-        with self.assertRaises(OverflowError):
-            product(["a"]*(2**16), repeat=2**16)
+        with self.assertRaises((OverflowError, MemoryError)):
+            product(*(['ab']*2**5), repeat=2**25)

[serhiy-storchaka]

And this means that this test (and other tests with the bigaddrspacetest decorator) is not executed on any of our buildbots. It skipped on 64-bit builders and 32-bit builders ran tests without the -M2G option.

[python-dev]

New changeset 356ed025dbae by Serhiy Storchaka in branch '3.3':
Issues bpo-23363, bpo-23364, bpo-23365, bpo-23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/356ed025dbae

New changeset 98c720c3e061 by Serhiy Storchaka in branch '3.4':
Issues bpo-23363, bpo-23364, bpo-23365, bpo-23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/98c720c3e061

New changeset 4cb316fe6bf2 by Serhiy Storchaka in branch 'default':
Issues bpo-23363, bpo-23364, bpo-23365, bpo-23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/4cb316fe6bf2

[python-dev]

New changeset 887526ebb013 by Serhiy Storchaka in branch '2.7':
Issues bpo-23363, bpo-23364, bpo-23365, bpo-23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/887526ebb013