various issues due to misuse of PySlice_GetIndicesEx

@terryjreedy

BPO	27867
Nosy	@terryjreedy, @mdickinson, @ncoghlan, @vstinner, @serhiy-storchaka, @cryvate
PRs	bpo-27867: Expand the PySlice_GetIndicesEx macro. #1023 bpo-27867: Expand the PySlice_GetIndicesEx macro. (#1023) #1046 bpo-27867: Expand the PySlice_GetIndicesEx macro. (#1023) #1044 bpo-27867: Expand the PySlice_GetIndicesEx macro. (#1023) #1045 bpo-27867: Add a porting guide for PySlice_GetIndicesEx(). #1973
Files	slice_get_indices.patch slice_get_indices_2.patch slice_get_indices_3.patch PySlice_GetIndicesEx-silence-warnings.patch PySlice_GetIndicesEx.cocci

^{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 = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2017-10-08.09:54:02.176>
created_at = <Date 2016-08-26.15:51:25.089>
labels = ['extension-modules', 'interpreter-core', '3.7', 'type-crash']
title = 'various issues due to misuse of PySlice_GetIndicesEx'
updated_at = <Date 2017-10-08.09:54:02.176>
user = 'https://bugs.python.org/tehybel'

bugs.python.org fields:

activity = <Date 2017-10-08.09:54:02.176>
actor = 'serhiy.storchaka'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2017-10-08.09:54:02.176>
closer = 'serhiy.storchaka'
components = ['Extension Modules', 'Interpreter Core']
creation = <Date 2016-08-26.15:51:25.089>
creator = 'tehybel'
dependencies = []
files = ['44279', '46085', '46388', '46510', '46786']
hgrepos = []
issue_num = 27867
keywords = ['patch']
message_count = 33.0
messages = ['273708', '273720', '273775', '273801', '273806', '273807', '273809', '273943', '273962', '273995', '275179', '275277', '275284', '275602', '284297', '286067', '286241', '286903', '286910', '286932', '286933', '286940', '286941', '286944', '286945', '290814', '291258', '291329', '291330', '295285', '302686', '302694', '303905']
nosy_count = 8.0
nosy_names = ['terry.reedy', 'mark.dickinson', 'ncoghlan', 'vstinner', 'python-dev', 'serhiy.storchaka', 'tehybel', 'cryvate']
pr_nums = ['1023', '1046', '1044', '1045', '1973']
priority = 'high'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'crash'
url = 'https://bugs.python.org/issue27867'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6', 'Python 3.7']

Here I will describe 6 issues with various core objects (bytearray, list) and
the array module.

Common to them all is that they arise due to a misuse of the function
PySlice_GetIndicesEx.

This type of issue results in out-of-bounds array indexing which leads to memory
disclosure, use-after-frees or memory corruption, depending on the
circumstances.

For each issue I've attached a proof-of-concept script which either prints
leaked heap memory or segfaults on my machine (64-bit linux, --with-pydebug,
python 3.5.2).

Issue 1: out-of-bounds indexing when taking a bytearray's subscript

While taking the subscript of a bytearray, the function bytearray_subscript in
/Objects/bytearrayobject.c calls PySlice_GetIndicesEx to validate the given
indices.

Some of these indices might be objects with an __index__ method, and thus
PySlice_GetIndicesEx could call back into python code.

If the evaluation of the indices modifies the bytearray, the indices might no
longer be safe, despite PySlice_GetIndicesEx saying so.

Here is a PoC which lets us read out 64 bytes of uninitialized memory from the
heap:

---

class X:
    def __index__(self):
        b[:] = []
        return 1

b = bytearray(b"A"*0x1000)
print(b[0:64:X()])

Here's the result on my system:

$ ./python poc17.py
bytearray(b'\x00\x00\x00\x00\x00\x00\x00\x00\xb0\xce\x86\x9ff\x7f\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00')

Issue 2: memory corruption in bytearray_ass_subscript

This issue is similar to the one above. The problem exists when assigning to a
bytearray via subscripting. The relevant function is bytearray_ass_subscript.
The relevant line is again the one calling PySlice_GetIndicesEx.

Here's a PoC which leads to memory corruption of the heap:

---

class X:
    def __index__(self):
        del b[0:0x10000]
        return 1
        
b = bytearray(b"A"*0x10000)
b[0:0x8000:X()] = bytearray(b"B"*0x8000)

Here's the result of running it:

(gdb) r poc20.py
Program received signal SIGSEGV, Segmentation fault.
PyCFunction_NewEx (ml=0x8b4140 <textiowrapper_methods+128>, self=self@entry=0x7ffff7f0e898,
module=module@entry=0x0) at Objects/methodobject.c:31
31 free_list = (PyCFunctionObject *)(op->m_self);
(gdb) p op
$13 = (PyCFunctionObject *) 0x4242424242424242

Issue 3: use-after-free when taking the subscript of a list

This issue is similar to the one above, but it occurs when taking the subscript
of a list rather than a bytearray. The relevant code is in list_subscript which
exists in /Objects/listobject.c. Here's a PoC:

---

class X:
    def __index__(self):
        b[:] = [1, 2, 3]
        return 2

b = [123]*0x1000
print(b[0:64:X()])

It results in a segfault here because of a use-after-free:

(gdb) run ./poc18.py
Program received signal SIGSEGV, Segmentation fault.
0x0000000000483553 in list_subscript (self=0x7ffff6d53988, item=<optimized out>) at Objects/listobject.c:2441
2441 Py_INCREF(it);
(gdb) p it
$2 = (PyObject *) 0xfbfbfbfbfbfbfbfb

Issue 4: use-after-free when assigning to a list via subscripting

The same type of issue exists in list_ass_subscript where we assign to the list
using a subscript. Here's a PoC which also results in a use-after-free:

---

class X:
    def __index__(self):
        b[:] = [1, 2, 3]
        return 2

b = [123]*0x1000
b[0:64:X()] = [0]*32

(gdb) r poc19.py
Program received signal SIGSEGV, Segmentation fault.
0x0000000000483393 in list_ass_subscript (self=<optimized out>, item=<optimized out>,
value=<optimized out>) at Objects/listobject.c:2603
2603 Py_DECREF(garbage[i]);
(gdb) p garbage[i]
$4 = (PyObject *) 0xfbfbfbfbfbfbfbfb

Issue 5: out-of-bounds indexing in array_subscr

Same type of issue. The problem is in the function array_subscr in
/Modules/arraymodule.c.

Here's a PoC which leaks and prints uninitialized memory from the heap:

---

import array

class X:
    def __index__(self):
        del a[:]
        a.append(2)
        return 1

a = array.array("b")
for _ in range(0x10):
    a.append(1)

print(a[0:0x10:X()])

---

And the result:

$ ./python poc22.py
array('b', [2, -53, -53, -53, -5, -5, -5, -5, -5, -5, -5, -5, 0, 0, 0, 0])

Issue 6: out-of-bounds indexing in array_ass_subscr

Same type of issue, also in the array module. Here's a PoC which segfaults here:

---

import array

class X:
    def __index__(self):
        del a[:]
        return 1

a = array.array("b")
a.frombytes(b"A"*0x100)
del a[::X()]

How should these be fixed?

I would suggest that in each instance we could add a check after calling
PySlice_GetIndicesEx. The check should validate that the "length" argument
passed to PySlice_GetIndicesEx did not change during the call. But maybe there
is a better way?

(By the way: these issues might also exist in 2.7, I did not check.)

I presume you are suggesting to raise if the length changes. This is similar to raising when a dict is mutated while iterating. Note that we do not do this with mutable sequences. (If the iteration is stopped with out-of-memory error, so be it.)

An alternate approach would be to first fully evaluate start, stop, step , *and then length*, to ints, in that order, before using any of them. In particular, have everything stable before comparing and adjusting start and stop to length. This way, slices would continue to always work, barring other exceptions in __index__ or __length__.

Even list suffers from this bug if slicing step is not 1.

class X:
    def __index__(self):
        del a[:]
        return 1

a = [0]
a[:X():2]

There is really one immediate issue: PySlice_GetIndicesEx in Objects/sliceobject.c takes as inputs a slice object and a sequence length, but not the sequence itself. It starts with "/* this is harder to get right than you might think */" Yep. It assumes both inputs are constants.

However, it thrice calls _PyEval_SliceIndex(intlike) (Python/ceval.c). This call in turn may call PyNunber_AsSsize_t(intlike), which calls intlike.__index__. At least in toy examples, this last can change an underlying mutable sequence and hence its length. Since the calculation of the returned start, stop, step, and slicelength depend on the length, the result is that PySlice_GetIndeces can indirectly invalidate its own results.
---

Side effects in __index__ also affect indexing

class X:
    def __index__(self):
        b[:] = []
        return 1

b = [1,2,3,4]
b[X()]

Traceback (most recent call last):
  File "F:\Python\mypy\tem.py", line 7, in <module>
    print(b[X()])
IndexError: list index out of range

Similarly, "b[X()] = 4" results in "list assignment index ...".

Crashes seem not possible as the conversion to a real int seems to always be done locally in the sequence_subscript method. See for instance list_subscript and list_ass_subscript in Objects/listojbect.c. If the subscript is an index, it is *first* converted to int with PyNumber_AsSsize_t *before* being possibly incremented by PySize(self) and compared to the same.

Side-effects also affect index methods.

class X:
    def __index__(self):
        b[:] = []
        return 1

b = [1]
b.index(1, X())

Traceback (most recent call last):
  File "F:\Python\mypy\tem.py", line 7, in <module>
    print(b.index(1, X()))
ValueError: 1 is not in list

For tuple/list/deque.index(val, start, stop), start and stop are converted to int with _PyEval_SliceIndex, as with slices. However, they make this call as part of an initial PyArg_ParseTuple call, before adjusting them to the length of the sequence. So again, no crash is possible.

I suppose there are other places where PyNumber_AsSsize_t is called, and where a crash *might* be possible, and should be checked, But back to slicing.
---

Action on this issue requires a policy decision among three options.

In general, special methods should be proper functions, without side effects, that return what the doc suggests. Doing otherwise is 'at one own risk'. Close that as "won't fix" because anyone writing an 'intlike' with such an evil __index__ method deserves the result, even it it is a crash. Also, this seems like a toy problem since it require __index__ can know of and access the collection it is being called for. It would otherwise only be written my a malicious attacker, who could do things much worse in the __index__ methods.

Counter arguments: A. Our usual policy is that pure Python code only using the stdlib (minus ctypes) should not crash. B. The writer and user of 'intlike' might be different people.

Question: does 'no crash' apply to arbitrary side-effects in special methods?

Declare and enforce that a length-changing side-effect in __index__ used with slicing is a bug and raise ValueError. A. Change every mutable_collection(_ass)_subscript method to record is length before calling PySlice_GetIndicesEx and check itself afterwards. B. Create PySlice_GetIndicesEx2 to receive *collection instead of length, so *it* can do the before and check in just one place, and change the calls.
As I suggested earlier: 'slicing should always work'. Ensure that the 'length' used to adjust int slice components is the correct value, after all calls to __index__. A. Change all calling sites, as above, to pass a slice object with int components and a length calculated after int conversions. Bl. Create PySlice_GetIndicesEx2 to receive *collection, so *it* can retrieve the length after __index__ conversions.

I will ask on pydev which, if any, of the 4 possible patches would be best.

This is a toy example that exposes the problem, but the problem itself is not a toy problem. The key point is that calculating slice indices cause executing Python code and releases GIL. In multithread program a sequence can be changed not in toy __index__ method, but in other thread, in legitimate code. This is very hardly reproducible bug.

Variants B are not efficient. To determine the size of a sequence we should call its __len__() method. This is less efficient than using macros Py_SIZE() or PyUnicode_GET_LENGTH(). And it is not always possible to pass a sequence. In multidimensional array there is no such sequence (see for example _testbuffer.ndarray).

FWIW. Py_SIZE is used all over listobject.c. Are you saying that this could be improved?

I'm saying that PySlice_GetIndicesEx2 can't just use Py_SIZE.

Actually making slicing always working is easier than I expected. Maybe it is even easier than raise an error.

PySlice_GetIndicesEx() is split on two functions. First convert slice attributes to Py_ssize_t, then scale them to appropriate range depending on the length. Here is a sample patch.

I like this. Very nice. What I understand is that callers that access PySlice_GetIndicesEx via the header file (included with Python.h) will see the function as a macro. When the macro is expanded, the length expression will be evaluated after any __index__ calls.

This approach requires that the length expression calculate the length from the sequence, rather than being a length computer before the call. I checked and all of our users in /Objects pass some form of seq.get_size(). This approach also requires that the function be accessed via .h rather than directly as the function in the .c file. If we go this way, should he PySlice_GetIndicesEx doc say something?

I reviewed the two new functions and am satisfied a) that they correctly separate converting None and non-ints to ints from adjusting start and stop as ints according to length and b) that the effect of the change in logic for the latter is to stop making unnecessary checks that must fail.

Nice! The one thing I would suggest double checking with this change is whether or not we have test cases covering ranges with lengths that don't fit into ssize_t. It's been years since I looked at that code, so I don't remember exactly how it currently works, but it does work (except for __len__, due to the signature of the C level length slot):

>>> bigrange = range(int(-10e30), int(10e30))
>>> len(bigrange)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: Python int too large to convert to C ssize_t
>>> bigrange[:]
range(-9999999999999999635896294965248, 9999999999999999635896294965248)
>>> bigrange[0:-1]
range(-9999999999999999635896294965248, 9999999999999999635896294965247)
>>> bigrange[::2]
range(-9999999999999999635896294965248, 9999999999999999635896294965248, 2)
>>> bigrange[0:-1:2]
range(-9999999999999999635896294965248, 9999999999999999635896294965247, 2)

Yet one possible solution is to make slice constructor converting arguments to exact ints. This allows to leave user code unchanged. But this is 3.6-only solution of course. I would like to know Mark's thoughts on this.

As in, for arguments that have __index__() methods, do the conversion to a true Python integer eagerly when the slice is built rather than lazily when slice.indices() (or the C-level equivalent) is called?

That actually seems like a potentially plausible future approach to me, but isn't a change I'd want to make hastily - those values are visible as the start, stop and step attributes on the slice, and https://docs.python.org/3/reference/datamodel.html#types currently describes those as "These attributes can have any type."

Given that folks do a lot of arcane things with the subscript notation, I wouldn't want to break working code if we have less intrusive alternatives.

New changeset 110ec861e5ea by Serhiy Storchaka in branch '2.7':
Issue bpo-27867: Fixed merging error.
https://hg.python.org/cpython/rev/110ec861e5ea

New changeset faa1891d4d1237d6df0af4622ff520ccd6768e04 by Serhiy Storchaka in branch '3.5':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
faa1891

New changeset 745dda46d2e3e27206bb33188c770e1f6c73766e by Serhiy Storchaka in branch '2.7':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
745dda4

New changeset e9d77e9fce477b5589c7eb5e1b4179b1d8e1fecc by Serhiy Storchaka in branch '2.7':
Issue bpo-27867: Fixed merging error.
e9d77e9

New changeset faa1891d4d1237d6df0af4622ff520ccd6768e04 by Serhiy Storchaka in branch 'master':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
faa1891

New changeset 8bd58e9c725a15854a99d19daf935fb08df77a05 by Serhiy Storchaka in branch 'master':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
8bd58e9

New changeset 65febbec9d09101f76a04efeef6b3dc7f9b06ee8 by Serhiy Storchaka in branch 'master':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
65febbe

New changeset faa1891d4d1237d6df0af4622ff520ccd6768e04 by Serhiy Storchaka in branch '3.6':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
faa1891

New changeset 8bd58e9c725a15854a99d19daf935fb08df77a05 by Serhiy Storchaka in branch '3.6':
Issue bpo-27867: Silenced may-be-used-uninitialized warnings after
8bd58e9

This issue is left open because it needs to add a porting guide in What's New.

See also a problem with breaking ABI in bpo-29943.

If don't make PySlice_GetIndicesEx a macro when Py_LIMITED_API is not defined, it should be expanded to PySlice_Unpack and PySlice_AdjustIndices. PR 1023 does this for master branch. The patch is generated by Coccinelle's semantic patch.

New changeset e41390a by Serhiy Storchaka in branch '2.7':
bpo-27867: Expand the PySlice_GetIndicesEx macro. (bpo-1023) (bpo-1046)
e41390a

New changeset b879fe8 by Serhiy Storchaka in branch 'master':
Expand the PySlice_GetIndicesEx macro. (bpo-1023)
b879fe8

New changeset c26b19d by Serhiy Storchaka in branch '3.6':
Expand the PySlice_GetIndicesEx macro. (bpo-1023) (bpo-1046)
c26b19d

New changeset fa25f16 by Serhiy Storchaka in branch '3.5':
Expand the PySlice_GetIndicesEx macro. (bpo-1023) (bpo-1045)
fa25f16

PR 1973 adds a porting guide. This should be the last commit for this issue. Please make a review and suggest better wording.

Could anyone please make review of the documentation?

@serhiy

@serhiy.storchaka: review done.

New changeset 4d3f084 by Serhiy Storchaka in branch 'master':
bpo-27867: Add a porting guide for PySlice_GetIndicesEx(). (bpo-1973)
4d3f084

Navigation Menu

Repository navigation

various issues due to misuse of PySlice_GetIndicesEx #72054

10 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

various issues due to misuse of PySlice_GetIndicesEx #72054

Description

Activity

tehybel commented on Aug 26, 2016

terryjreedy commented on Aug 26, 2016

serhiy-storchaka commented on Aug 27, 2016

terryjreedy commented on Aug 27, 2016

serhiy-storchaka commented on Aug 28, 2016

terryjreedy commented on Aug 28, 2016

serhiy-storchaka commented on Aug 28, 2016

serhiy-storchaka commented on Aug 30, 2016

terryjreedy commented on Aug 30, 2016

ncoghlan commented on Aug 31, 2016

serhiy-storchaka commented on Sep 8, 2016

ncoghlan commented on Sep 9, 2016

10 remaining items

python-dev commented on Feb 4, 2017

python-dev commented on Feb 4, 2017

python-dev commented on Feb 4, 2017

python-dev commented on Feb 4, 2017

python-dev commented on Feb 4, 2017

serhiy-storchaka commented on Mar 30, 2017

serhiy-storchaka commented on Apr 7, 2017

serhiy-storchaka commented on Apr 8, 2017

serhiy-storchaka commented on Apr 8, 2017

serhiy-storchaka commented on Jun 6, 2017

serhiy-storchaka commented on Sep 21, 2017

Cryvate commented on Sep 21, 2017

serhiy-storchaka commented on Oct 8, 2017

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions