Issue 23363: integer overflow in itertools.permutations (original) (raw)
Created on 2015-02-01 13:54 by pkt, last changed 2022-04-11 14:58 by admin. This issue is now closed.
Messages (7)
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 rsizeof(Py_ssize_t)=2^302^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 , 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 , 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)
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
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.
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
Author: Arfrever Frehtes Taifersar Arahesis (Arfrever) *
Date: 2015-02-04 01:19
The last fix should be applied also in 2.7 branch.
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
Author: Serhiy Storchaka (serhiy.storchaka) *
Date: 2015-02-04 06:10
Thanks Arfrever.
History
Date
User
Action
Args
2022-04-11 14:58:12
admin
set
github: 67552
2015-02-04 06:10:39
serhiy.storchaka
set
status: open -> closed
resolution: fixed
messages: +
stage: resolved
2015-02-04 06:09:59
python-dev
set
messages: +
2015-02-04 01:19:18
Arfrever
set
status: closed -> open
versions: + Python 2.7, Python 3.3, Python 3.5
messages: +
resolution: fixed -> (no value)
stage: resolved -> (no value)
2015-02-03 07:42:28
serhiy.storchaka
set
status: open -> closed
2015-02-03 00:05:22
python-dev
set
messages: +
2015-02-02 06:59:29
serhiy.storchaka
set
status: closed -> open
nosy: + serhiy.storchaka
messages: +
2015-02-02 02:39:04
python-dev
set
status: open -> closed
nosy: + python-dev
messages: +
resolution: fixed
stage: resolved
2015-02-01 21:17:08
Arfrever
set
nosy: + Arfrever
2015-02-01 13:54:13
pkt
create