classification
Title: integer overflow in itertools.combinations_with_replacement
Type: crash Stage: resolved
Components: Versions: Python 3.3, Python 3.4, Python 3.5, 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_cwr.py pkt, 2015-02-01 13:55
Messages (5)
msg235173 - (view) Author: paul (pkt) Date: 2015-02-01 13:55
# Bug
# ---
# 
# static PyObject *
# cwr_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
# {
#     ...
# 1   indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
#     ...
#     for (i=0 ; i<r ; i++)
# 2       indices[i] = 0;
# 
# 
# 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, cwr_new (type=0x83392a0 <cwr_type>, args=('AA', 1073741824), kwds=0x0) at ./Modules/itertoolsmodule.c:2684
# 2684        PyObject *pool = NULL;
# ...
# 2703        indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
# (gdb) print r
# $1 = 1073741824
# (gdb) print r*4
# $2 = 0
# (gdb) c
# Continuing.
#  
# Program received signal SIGSEGV, Segmentation fault.
# 0x0822fdcd in cwr_new (type=0x83392a0 <cwr_type>, args=('AA', 1073741824), kwds=0x0) at ./Modules/itertoolsmodule.c:2710
# 2710            indices[i] = 0;
# 
# 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.combinations_with_replacement("AA", 2**30)
msg235217 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-02-02 02:13
New changeset 93d445cd5f70 by Benjamin Peterson in branch '3.3':
check for overflow in combinations_with_replacement (closes #23365)
https://hg.python.org/cpython/rev/93d445cd5f70

New changeset 2e7a02e4cf2c by Benjamin Peterson in branch '3.4':
merge 3.3 (#23365)
https://hg.python.org/cpython/rev/2e7a02e4cf2c

New changeset 4d875a690c01 by Benjamin Peterson in branch 'default':
merge 3.4 (#23365)
https://hg.python.org/cpython/rev/4d875a690c01

New changeset 366018a91457 by Benjamin Peterson in branch '2.7':
check for overflow in combinations_with_replacement (closes #23365)
https://hg.python.org/cpython/rev/366018a91457
msg235223 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-02 06:33
The test needs 4GiB. May be use 2**29?
msg235307 - (view) Author: Roundup Robot (python-dev) (Python triager) 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
msg235376 - (view) Author: Roundup Robot (python-dev) (Python triager) 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: + msg235376
2015-02-04 01:22:10Arfreversetversions: + Python 2.7, Python 3.3, Python 3.5
2015-02-03 07:41:41serhiy.storchakasetstatus: open -> closed
2015-02-03 00:05:22python-devsetmessages: + msg235307
2015-02-02 07:06:27serhiy.storchakasetstatus: closed -> open
2015-02-02 06:33:51serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg235223
2015-02-02 02:13:54python-devsetstatus: open -> closed

nosy: + python-dev
messages: + msg235217

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