classification
Title: integer overflow in itertools.product
Type: crash Stage: resolved
Components: Versions: Python 3.5, Python 3.3, Python 3.4, Python 2.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: Arfrever, pkt, python-dev, serhiy.storchaka
Priority: normal Keywords:

Created on 2015-02-01 13:55 by pkt, last changed 2015-02-04 06:09 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
poc_product.py pkt, 2015-02-01 13:55
Messages (10)
msg235172 - (view) Author: paul (pkt) Date: 2015-02-01 13:55
# 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
# ...
# 2021        nargs = (repeat == 0) ? 0 : PyTuple_GET_SIZE(args);
# (gdb) n
# 2022        npools = nargs * repeat;
# (gdb) print nargs
# $14 = 65536
# (gdb) print repeat
# $15 = 65536
# (gdb) n
# 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)
msg235220 - (view) Author: Roundup Robot (python-dev) Date: 2015-02-02 02:39
New changeset 7133582b6769 by Benjamin Peterson in branch '3.3':
check for overflows in permutations() and product() (closes #23363, closes #23364)
https://hg.python.org/cpython/rev/7133582b6769

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

New changeset 31dc5a40d2ab by Benjamin Peterson in branch 'default':
merge 3.4 (#23364, #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 #23363, closes #23364)
https://hg.python.org/cpython/rev/acc2c3479f2e
msg235226 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-02 07:01
+        with self.assertRaises(OverflowError):
+            product(["a"]*(2**16), repeat=2**16)

The test needs 16GiB. May be use repeat=2**13?
msg235230 - (view) Author: paul (pkt) Date: 2015-02-02 07:33
Why do you think this test needs 16GiB?
msg235231 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-02 07:35
2**16 * 2**16 * sizeof(Py_ssize_t) = 16GiB
msg235233 - (view) Author: paul (pkt) Date: 2015-02-02 08:16
You mean 64bit? On 32 it'll overflow and that's the point.
msg235270 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-02 16:44
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)
msg235271 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-02 16:55
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.
msg235306 - (view) Author: Roundup Robot (python-dev) Date: 2015-02-03 00:05
New changeset 356ed025dbae by Serhiy Storchaka in branch '3.3':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/356ed025dbae

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

New changeset 4cb316fe6bf2 by Serhiy Storchaka in branch 'default':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/4cb316fe6bf2
msg235375 - (view) Author: Roundup Robot (python-dev) Date: 2015-02-04 06:09
New changeset 887526ebb013 by Serhiy Storchaka in branch '2.7':
Issues #23363, #23364, #23365, #23366: Fixed itertools overflow tests.
https://hg.python.org/cpython/rev/887526ebb013
History
Date User Action Args
2015-02-04 06:09:59python-devsetmessages: + msg235375
2015-02-04 01:20:17Arfreversetversions: + Python 2.7, Python 3.3, Python 3.5
2015-02-03 07:41:24serhiy.storchakasetstatus: open -> closed
2015-02-03 00:05:22python-devsetmessages: + msg235306
2015-02-02 16:55:20serhiy.storchakasetmessages: + msg235271
2015-02-02 16:44:56serhiy.storchakasetmessages: + msg235270
2015-02-02 08:16:34pktsetmessages: + msg235233
2015-02-02 07:35:22serhiy.storchakasetmessages: + msg235231
2015-02-02 07:33:20pktsetmessages: + msg235230
2015-02-02 07:01:42serhiy.storchakasetstatus: closed -> open
nosy: + serhiy.storchaka
messages: + msg235226

2015-02-02 02:39:04python-devsetstatus: open -> closed

nosy: + python-dev
messages: + msg235220

resolution: fixed
stage: resolved
2015-02-01 21:17:21Arfreversetnosy: + Arfrever
2015-02-01 13:55:04pktcreate