integer overflow in itertools.combinations

[pkt]

BPO	23366
Nosy	@benjaminp, @serhiy-storchaka
Files	poc_combinations.py itertools_overflows.patch itertools_overflows_2.patch

^{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:42:09.035>
created_at = <Date 2015-02-01.13:56:22.664>
labels = ['type-crash']
title = 'integer overflow in itertools.combinations'
updated_at = <Date 2015-02-04.06:09:59.695>
user = 'https://bugs.python.org/pkt'

bugs.python.org fields:

activity = <Date 2015-02-04.06:09:59.695>
actor = 'python-dev'
assignee = 'none'
closed = True
closed_date = <Date 2015-02-03.07:42:09.035>
closer = 'serhiy.storchaka'
components = []
creation = <Date 2015-02-01.13:56:22.664>
creator = 'pkt'
dependencies = []
files = ['37965', '37974', '37982']
hgrepos = []
issue_num = 23366
keywords = ['patch']
message_count = 7.0
messages = ['235174', '235216', '235227', '235272', '235299', '235308', '235378']
nosy_count = 5.0
nosy_names = ['benjamin.peterson', '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/issue23366'
versions = ['Python 2.7', 'Python 3.3', 'Python 3.4', 'Python 3.5']

[pkt]

# Bug
# ---
#
# static PyObject *
# combinations_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] = 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, combinations_new (type=0x83390c0 <combinations_type>, args=('AA', 1073741824), kwds=0x0)
# at ./Modules/itertoolsmodule.c:2343
\bpo-2343 PyObject *pool = NULL;
# ...
# (gdb) n
\bpo-2362 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.
# 0x0822f359 in combinations_new (type=0x83390c0 <combinations_type>, args=('AA', 1073741824), kwds=0x0)
# at ./Modules/itertoolsmodule.c:2369
\bpo-2369 indices[i] = 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.combinations("AA", 2**30)

[python-dev]

New changeset 014886dae5c4 by Benjamin Peterson in branch '3.3':
detect overflow in combinations (closes bpo-23366)
https://hg.python.org/cpython/rev/014886dae5c4

New changeset 2f73de7ffcf5 by Benjamin Peterson in branch '3.4':
merge 3.3 (bpo-23366)
https://hg.python.org/cpython/rev/2f73de7ffcf5

New changeset 886559229911 by Benjamin Peterson in branch 'default':
merge 3.4 (bpo-23366)
https://hg.python.org/cpython/rev/886559229911

New changeset fe203370c049 by Benjamin Peterson in branch '2.7':
detect overflow in combinations (closes bpo-23366)
https://hg.python.org/cpython/rev/fe203370c049

[serhiy-storchaka]

This commit (and three other) causes compiler warnings:

./Modules/itertoolsmodule.c: In function ‘product_new’:
./Modules/itertoolsmodule.c:2025:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (repeat > PY_SSIZE_T_MAX/sizeof(Py_ssize_t) ||
                    ^
./Modules/itertoolsmodule.c:2026:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             nargs > PY_SSIZE_T_MAX/(repeat * sizeof(Py_ssize_t))) {
                   ^
./Modules/itertoolsmodule.c: In function ‘combinations_new’:
./Modules/itertoolsmodule.c:2371:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (r > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)) {
           ^
./Modules/itertoolsmodule.c: In function ‘cwr_new’:
./Modules/itertoolsmodule.c:2716:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (r > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)) {
           ^
./Modules/itertoolsmodule.c: In function ‘permutations_new’:
./Modules/itertoolsmodule.c:3061:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (n > PY_SSIZE_T_MAX/sizeof(Py_ssize_t) ||
           ^
./Modules/itertoolsmodule.c:3062:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         r > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)) {
           ^

May be use PyMem_New instead of PyMem_Malloc?

[serhiy-storchaka]

And with this patch an OverflowError in tests should be replaced with (OverflowError, MemoryError). Updated patch also fixes other bugs in itertools tests.

[benjaminp]

lgtm

[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