Issue 24100: Use after free in siftdown (2) (original) (raw)

_siftdown(PyListObject *heap, Py_ssize_t startpos, Py_ssize_t pos)

...

while (pos > startpos){

parentpos = (pos - 1) >> 1;

parent = PyList_GET_ITEM(heap, parentpos);

1 cmp = PyObject_RichCompareBool(newitem, parent, Py_LT);

...

2 if (size != PyList_GET_SIZE(heap)) {

Py_DECREF(newitem);

PyErr_SetString(PyExc_RuntimeError,

"list changed size during iteration");

return -1;

}

if (cmp == 0)

3 break;

...

}

4 Py_DECREF(PyList_GET_ITEM(heap, pos));

5 PyList_SET_ITEM(heap, pos, newitem);

1. custom compare function replaces object at index "pos" with a fresh

instance with refcnt==1

2. check is ineffective, since mutation was done without altering size

3. break out of the loop

4. refcnt drops to 0 and del method is called. Destructed clears the heap

5. SET_ITEM doesn't do any bounds checking and does a wild write.

"pos" is under our control and is restricted only by the amount of free

memory. pos==X requires heap of size X-1.

gX global var is necessary. Without it, python crashes in debug checks inside

Py_ForgetReference. Seems like clearing L puts objects in a bad state.

GDB

---

Program received signal SIGSEGV, Segmentation fault.

0x4002ed73 in _siftdown (heap=0x4058edfc, startpos=0, pos=112233) at /home/p/Python-3.4.1/Modules/_heapqmodule.c:58

58 PyList_SET_ITEM(heap, pos, newitem);

(gdb) print *heap

$1 = {ob_base = {ob_base = {_ob_next = 0x405913f4, _ob_prev = 0x4058ee6c, ob_refcnt = 2, ob_type = 0x830e1c0 },

ob_size = 0}, ob_item = 0x0, allocated = 0}

(gdb) print pos

$2 = 112233

Paul, this was nice work. Thanks.

Attaching a patch to make 3.4 match the Python 3.5 version of the code which rearranges the object pointers without changing their reference counts.

With that patch, your crasher no longer seg-faults, but gives this instead:

len(L): 112234 del del Exception ignored in: <bound method X.__del__ of <__main__.X object at 0x10efc9080>> Traceback (most recent call last): File "heap_crasher.py", line 18, in del IndexError: list index out of range

I should add that the crasher scripts share common features and could perhaps be built into a unified test tool. Also, some care should be taken to make the tool mostly independent of non-guaranteed "del" behavior or CPython specific ref-counting logic to trigger a particular sequence of events. For example, pypy gives a different result than CPython 3.5 for for the various poc_sift* scripts. The reason is that the "del" method isn't reliably triggered in a gc-only environment.