Issue 23363: integer overflow in itertools.permutations

Messages (7) msg235170 - (view) Author: paul (pkt) Date: 2015-02-01 13:54

# Bug
# ---
# 
# static PyObject *
# permutations_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
# {
#     ...
# 1   cycles = PyMem_Malloc(r * sizeof(Py_ssize_t));
#     ...
#     for (i=0 ; i<r ; i++)
# 2       cycles[i] = n - i;
# 
# 1. if r=2^30, then r*sizeof(Py_ssize_t)=2^30*2^2=0 (modulo 2^32), so malloc
#    allocates a 0 byte buffer
# 2. r=2^30>0, so we write well beyond the buffer's end
# 
# Crash
# -----
# 
# Breakpoint 1, permutations_new (type=0x83394e0 <permutations_type>, args=('A', 1073741824), kwds=0x0) at ./Modules/itertoolsmodule.c:3012
# ...
# 3044        indices = PyMem_Malloc(n * sizeof(Py_ssize_t));
# (gdb) print r
# $2 = 1073741824
# (gdb) print r*4
# $3 = 0
# (gdb) c
# Continuing.
#  
# Program received signal SIGSEGV, Segmentation fault.
# 0x08230900 in permutations_new (type=0x83394e0 <permutations_type>, args=('A', 1073741824), kwds=0x0) at ./Modules/itertoolsmodule.c:3054
# 3054            cycles[i] = n - i;
# 
# 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
it.permutations("A", 2**30)

msg235221 - (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

msg235225 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * Date: 2015-02-02 06:59

An overflow in n * sizeof(Py_ssize_t) is not possible because n is the length of already allocated array of pointers.

+        with self.assertRaises(OverflowError):
+            permutations("A", 2**30)

The test needs 4GiB. May be use 2**29?

+        with self.assertRaises(OverflowError):
+            permutations("A", 2, 2**30)

permutations() takes at most 2 arguments.

msg235309 - (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

msg235369 - (view) Author: Arfrever Frehtes Taifersar Arahesis (Arfrever) * Date: 2015-02-04 01:19

The last fix should be applied also in 2.7 branch.

msg235377 - (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

msg235379 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * Date: 2015-02-04 06:10

Thanks Arfrever.

History Date User Action Args 2015-02-04 06:10:39serhiy.storchakasetstatus: open -> closed
resolution: fixed
messages: + msg235379

stage: resolved

2015-02-04 06:09:59python-devsetmessages: + msg235377 2015-02-04 01:19:18Arfreversetstatus: closed -> open
versions: + Python 2.7, Python 3.3, Python 3.5
messages: + msg235369

resolution: fixed -> (no value)
stage: resolved -> (no value)

2015-02-03 07:42:28serhiy.storchakasetstatus: open -> closed 2015-02-03 00:05:22python-devsetmessages: + msg235309 2015-02-02 06:59:29serhiy.storchakasetstatus: closed -> open
nosy: + serhiy.storchaka
messages: + msg235225 2015-02-02 02:39:04python-devsetstatus: open -> closed

nosy: + python-dev
messages: + msg235221

resolution: fixed
stage: resolved

2015-02-01 21:17:08Arfreversetnosy: + Arfrever
2015-02-01 13:54:13pktcreate