classification
Title: product_setstate() Out-of-bounds Read
Type: security Stage: resolved
Components: Versions: Python 3.3, Python 3.4, Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: kristjan.jonsson Nosy List: Arfrever, JohnLeitch, brycedarling, kristjan.jonsson, python-dev, rhettinger
Priority: normal Keywords: needs review, patch

Created on 2015-09-08 03:55 by JohnLeitch, last changed 2015-09-18 18:11 by Arfrever. This issue is now closed.

Files
File name Uploaded Description Edit
product_setstate_Type_Confusion.patch JohnLeitch, 2015-09-08 03:55 patch
product_setstate_Type_Confusion.py JohnLeitch, 2015-09-08 03:55 repro
itertoolsmodule.c.patch kristjan.jonsson, 2015-09-08 11:55
Messages (8)
msg250152 - (view) Author: John Leitch (JohnLeitch) * Date: 2015-09-08 03:55
Python 3.3, 3.4, and 3.5 suffer from a vulnerability caused by the behavior of the product_setstate() function. When called, the function loops over the state tuple provided and clamps each given index to a value within a range from 0 up to the max number of pools. Then, it loops over the pools and gets an item from the pool using the previously clamped index value.

However, for the upper bound, the clamping logic is using the number of pools and not the size of the individual pool, which can result in a call to PyTuple_GET_ITEM that uses an index outside of the bounds of the pool:

    for (i=0; i<n; i++)
    {
        PyObject* indexObject = PyTuple_GET_ITEM(state, i);
        Py_ssize_t index = PyLong_AsSsize_t(indexObject);
        if (index < 0 && PyErr_Occurred())
            return NULL; /* not an integer */
        /* clamp the index */
        if (index < 0)
            index = 0;
        else if (index > n-1)
            index = n-1;
        lz->indices[i] = index;
    }

    result = PyTuple_New(n);
    if (!result)
        return NULL;
    for (i=0; i<n; i++) {
        PyObject *pool = PyTuple_GET_ITEM(lz->pools, i);
        PyObject *element = PyTuple_GET_ITEM(pool, lz->indices[i]);
        Py_INCREF(element);
        PyTuple_SET_ITEM(result, i, element);
    }

The invalid result of the PyTyple_GET_ITEM() expression is then passed to Py_INCREF(), which performs a write operation that corrupts memory.

In some applications, it may be possible to exploit this behavior to corrupt sensitive information, crash, or achieve code execution. The out-of-bounds write can be observed by running the following script:

import itertools

p = itertools.product((0,),(0,))
p.__setstate__((0, 1))

Which, depending on the arrangement of memory, may produce an exception such as this:

0:000> g
(ea4.11a4): Access violation - code c0000005 (first chance)
First chance exceptions are reported before any exception handling.
This exception may be expected and handled.
eax=0000c962 ebx=059e8f80 ecx=00000000 edx=00000000 esi=004af564 edi=05392f78
eip=613211eb esp=004af4d0 ebp=004af4f8 iopl=0         nv up ei pl nz na po nc
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010202
python35_d!product_setstate+0x13b:
613211eb 8b5108          mov     edx,dword ptr [ecx+8] ds:002b:00000008=????????
0:000> k1
ChildEBP RetAddr  
004af4f8 61553a22 python35_d!product_setstate+0x13b [c:\source\python-3.5.0b3\modules\itertoolsmodule.c @ 2266]

In some cases, EIP corruption may occur:

0:000> r
eax=00000000 ebx=03e0f790 ecx=6d2ad658 edx=00000002 esi=03e0f790 edi=6d0dbb20
eip=00000000 esp=004cf6a0 ebp=004cf6ac iopl=0         nv up ei pl nz na po nc
cs=0023  ss=002b  ds=002b  es=002b  fs=0053  gs=002b             efl=00010202
00000000 ??              ???
0:000> k4
ChildEBP RetAddr
WARNING: Frame IP not in any known module. Following frames may be wrong.
004cf69c 6d08a390 0x0
004cf6ac 6d02b688 python35!PyIter_Next+0x10
004cf6c0 6d0dbb6e python35!chain_next+0x58
004cf6d0 6d0a021d python35!wrap_next+0x4e

To fix this issue, it is recommended that product_setstate() be updated to clamp indices within a range from 0 up to the size of the pool in the body of the result tuple building loop. A proposed patch is attached.

Credit: John Leitch (johnleitch@outlook.com), Bryce Darling (darlingbryce@gmail.com)
msg250172 - (view) Author: Kristján Valur Jónsson (kristjan.jonsson) * (Python committer) Date: 2015-09-08 09:04
Interesting.  Let me have a look.
msg250185 - (view) Author: Kristján Valur Jónsson (kristjan.jonsson) * (Python committer) Date: 2015-09-08 11:55
An alternative patch.  Please test this since I don't have a development system.
msg250186 - (view) Author: Kristján Valur Jónsson (kristjan.jonsson) * (Python committer) Date: 2015-09-08 11:56
There are two problems with the previous patch:
1) it can put out of bounds values into lz->indices.  This can cause problems then next time product_next() is called.
2) the case of a pool having zero size is not dealt with (it wasn't before either).
My patch should deal with both cases, but please verify since I don't have access to a python dev system at the moment.
msg250252 - (view) Author: John Leitch (JohnLeitch) * Date: 2015-09-08 18:26
Glancing over the code, I see the issues you describe. Tonight I will verify your revised patch and report back.
msg250286 - (view) Author: John Leitch (JohnLeitch) * Date: 2015-09-09 05:35
All appears well.
msg250367 - (view) Author: Kristján Valur Jónsson (kristjan.jonsson) * (Python committer) Date: 2015-09-10 12:39
Thanks, I'll get this committed and merged asap.
msg250526 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2015-09-12 16:42
New changeset 8cc052c28910 by Kristján Valur Jónsson in branch '3.3':
Issue #25021: Correctly make sure that product.__setstate__ does not access
https://hg.python.org/cpython/rev/8cc052c28910

New changeset 4f85b6228697 by Kristján Valur Jónsson in branch '3.4':
Issue #25021: Merge from 3.3 to 3.4
https://hg.python.org/cpython/rev/4f85b6228697

New changeset ca628ccec846 by Kristján Valur Jónsson in branch '3.5':
Issue #25021: Merge 3.4 to 3.5
https://hg.python.org/cpython/rev/ca628ccec846

New changeset 92e7ac79c681 by Kristján Valur Jónsson in branch 'default':
Issue #25021: Merge 3.5 to default
https://hg.python.org/cpython/rev/92e7ac79c681
History
Date User Action Args
2015-09-18 18:11:31Arfreversetnosy: + Arfrever
2015-09-13 05:36:11rhettingersetstatus: open -> closed
resolution: fixed
2015-09-12 16:43:06kristjan.jonssonsetstage: resolved
2015-09-12 16:42:20python-devsetnosy: + python-dev
messages: + msg250526
2015-09-10 12:39:01kristjan.jonssonsetmessages: + msg250367
2015-09-10 11:21:27rhettingersetassignee: rhettinger -> kristjan.jonsson
2015-09-09 05:35:59JohnLeitchsetmessages: + msg250286
2015-09-08 18:26:19JohnLeitchsetmessages: + msg250252
2015-09-08 11:56:58kristjan.jonssonsetmessages: + msg250186
2015-09-08 11:55:08kristjan.jonssonsetkeywords: + needs review
files: + itertoolsmodule.c.patch
messages: + msg250185
2015-09-08 09:04:25kristjan.jonssonsetmessages: + msg250172
2015-09-08 05:31:23rhettingersetnosy: + kristjan.jonsson
2015-09-08 05:27:40rhettingersetassignee: rhettinger
2015-09-08 03:55:20JohnLeitchsetfiles: + product_setstate_Type_Confusion.py
2015-09-08 03:55:02JohnLeitchcreate