Issue 23364: integer overflow in itertools.product (original) (raw)
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 ,
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 , line 1, in (), 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='', globals=, locals=, flags=0xbf85fbc0, arena=0x9e64220)
at Python/pythonrun.c:2180
#9 0x080637fd in PyRun_InteractiveOneObject (fp=0x40231ac0 <_IO_2_1_stdin_>, filename='', flags=0xbf85fbc0)
at Python/pythonrun.c:1445
#10 0x08063243 in PyRun_InteractiveLoopFlags (fp=0x40231ac0 <_IO_2_1_stdin_>, filename_str=0x826bc06 "", flags=0xbf85fbc0)
at Python/pythonrun.c:1324
#11 0x0806305f in PyRun_AnyFileExFlags (fp=0x40231ac0 <_IO_2_1_stdin_>, filename=0x826bc06 "", 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)