Use After Free in deque_index_impl

[kcatss]

Crash report

What happened?

Version

Python 3.13.0a3+ (heads/v3.13.0a2:e2c4038924, Feb 10 2024, 12:05:47) [GCC 11.4.0]
bisect from commit 32ea165

Root cause

the deque_index_impl function retrieves an element from the deque using b→data. However, the reference count of the item may decrease due to PyObject_RichCompareBool, leading to a use-after-free

static PyObject *
deque_index_impl(dequeobject *deque, PyObject *v, Py_ssize_t start,
                 Py_ssize_t stop){
...
	while (n--) {
            CHECK_NOT_END(b);
            item = b->data[index]; // <---  don't raise reference count using Py_NewRef
            cmp = PyObject_RichCompareBool(item, v, Py_EQ); //  <---  arbitrary call to __eq__
            if (cmp > 0)
                return PyLong_FromSsize_t(stop - (n + 1));
            else if (cmp < 0)
                return NULL;
            if (start_state != deque->state) {
                PyErr_SetString(PyExc_RuntimeError,
                                "deque mutated during iteration");
                return NULL;
           }
}

POC

import collections

class evil_pre1(object):
    def __eq__(self,o):
        deq.clear()
        return NotImplemented

deq = collections.deque([evil_pre1()])

deq.index(3)

ASAN

asan

=================================================================
==246599==ERROR: AddressSanitizer: heap-use-after-free on address 0xffffb086b3c8 at pc 0xaaaabb857308 bp 0xffffc5757c40 sp 0xffffc5757c50
READ of size 8 at 0xffffb086b3c8 thread T0
    #0 0xaaaabb857304 in Py_TYPE Include/object.h:333
    #1 0xaaaabb857304 in long_richcompare Objects/longobject.c:3265
    #2 0xaaaabb8c1158 in do_richcompare Objects/object.c:922
    #3 0xaaaabb8c1438 in PyObject_RichCompare Objects/object.c:965
    #4 0xaaaabb8c1578 in PyObject_RichCompareBool Objects/object.c:987
    #5 0xaaaabbcc1a5c in deque_index_impl Modules/_collectionsmodule.c:1222
    #6 0xaaaabbcc1c94 in deque_index Modules/clinic/_collectionsmodule.c.h:248
    #7 0xaaaabb7f4ee4 in method_vectorcall_FASTCALL Objects/descrobject.c:401
    #8 0xaaaabb7ccb84 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #9 0xaaaabb7cccc0 in PyObject_Vectorcall Objects/call.c:327
    #10 0xaaaabbab73e4 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:815
    #11 0xaaaabbb008f4 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #12 0xaaaabbb008f4 in _PyEval_Vector Python/ceval.c:1788
    #13 0xaaaabbb00abc in PyEval_EvalCode Python/ceval.c:592
    #14 0xaaaabbc02aec in run_eval_code_obj Python/pythonrun.c:1294
    #15 0xaaaabbc059e0 in run_mod Python/pythonrun.c:1379
    #16 0xaaaabbc0677c in pyrun_file Python/pythonrun.c:1215
    #17 0xaaaabbc08c3c in _PyRun_SimpleFileObject Python/pythonrun.c:464
    #18 0xaaaabbc08ff4 in _PyRun_AnyFileObject Python/pythonrun.c:77
    #19 0xaaaabbc66e68 in pymain_run_file_obj Modules/main.c:357
    #20 0xaaaabbc693d8 in pymain_run_file Modules/main.c:376
    #21 0xaaaabbc69de0 in pymain_run_python Modules/main.c:628
    #22 0xaaaabbc6a084 in Py_RunMain Modules/main.c:707
    #23 0xaaaabbc6a274 in pymain_main Modules/main.c:737
    #24 0xaaaabbc6a5b0 in Py_BytesMain Modules/main.c:761
    #25 0xaaaabb63145c in main Programs/python.c:15
    #26 0xffffb93d73f8 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #27 0xffffb93d74c8 in __libc_start_main_impl ../csu/libc-start.c:392
    #28 0xaaaabb63136c in _start (/home/kk/projects/cpython/python+0x27136c)

0xffffb086b3c8 is located 56 bytes inside of 72-byte region [0xffffb086b390,0xffffb086b3d8)
freed by thread T0 here:
    #0 0xffffb96a9fe8 in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:127
    #1 0xaaaabb8c9744 in _PyMem_RawFree Objects/obmalloc.c:84
    #2 0xaaaabb8cc580 in _PyMem_DebugRawFree Objects/obmalloc.c:2398
    #3 0xaaaabb8ccd74 in _PyMem_DebugFree Objects/obmalloc.c:2531
    #4 0xaaaabb8f0f78 in PyObject_Free Objects/obmalloc.c:995
    #5 0xaaaabbb7087c in PyObject_GC_Del Python/gc.c:1903
    #6 0xaaaabb914e1c in object_dealloc Objects/typeobject.c:5569
    #7 0xaaaabb938da8 in subtype_dealloc Objects/typeobject.c:2092
    #8 0xaaaabb8bf0b8 in _Py_Dealloc Objects/object.c:2889
    #9 0xaaaabbb69bc4 in Py_DECREF Include/object.h:922
    #10 0xaaaabbb69bc4 in Py_XDECREF Include/object.h:1030
    #11 0xaaaabbb69bc4 in _PyFrame_ClearExceptCode Python/frame.c:140
    #12 0xaaaabbaa276c in clear_thread_frame Python/ceval.c:1652
    #13 0xaaaabbaab750 in _PyEval_FrameClearAndPop Python/ceval.c:1679
    #14 0xaaaabbadc91c in _PyEval_EvalFrameDefault Python/generated_cases.c.h:4914
    #15 0xaaaabbb008f4 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #16 0xaaaabbb008f4 in _PyEval_Vector Python/ceval.c:1788
    #17 0xaaaabb7cc2fc in _PyFunction_Vectorcall Objects/call.c:413
    #18 0xaaaabb94bfe0 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #19 0xaaaabb94bfe0 in vectorcall_unbound Objects/typeobject.c:2271
    #20 0xaaaabb94bfe0 in slot_tp_richcompare Objects/typeobject.c:8983
    #21 0xaaaabb8c1058 in do_richcompare Objects/object.c:916
    #22 0xaaaabb8c1438 in PyObject_RichCompare Objects/object.c:965
    #23 0xaaaabb8c1578 in PyObject_RichCompareBool Objects/object.c:987
    #24 0xaaaabbcc1a5c in deque_index_impl Modules/_collectionsmodule.c:1222
    #25 0xaaaabbcc1c94 in deque_index Modules/clinic/_collectionsmodule.c.h:248
    #26 0xaaaabb7f4ee4 in method_vectorcall_FASTCALL Objects/descrobject.c:401
    #27 0xaaaabb7ccb84 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #28 0xaaaabb7cccc0 in PyObject_Vectorcall Objects/call.c:327
    #29 0xaaaabbab73e4 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:815
    #30 0xaaaabbb008f4 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #31 0xaaaabbb008f4 in _PyEval_Vector Python/ceval.c:1788
    #32 0xaaaabbb00abc in PyEval_EvalCode Python/ceval.c:592
    #33 0xaaaabbc02aec in run_eval_code_obj Python/pythonrun.c:1294
    #34 0xaaaabbc059e0 in run_mod Python/pythonrun.c:1379
    #35 0xaaaabbc0677c in pyrun_file Python/pythonrun.c:1215

previously allocated by thread T0 here:
    #0 0xffffb96aa2f4 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0xaaaabb8cb160 in _PyMem_RawMalloc Objects/obmalloc.c:56
    #2 0xaaaabb8c9028 in _PyMem_DebugRawAlloc Objects/obmalloc.c:2331
    #3 0xaaaabb8c9084 in _PyMem_DebugRawMalloc Objects/obmalloc.c:2364
    #4 0xaaaabb8ccdc0 in _PyMem_DebugMalloc Objects/obmalloc.c:2516
    #5 0xaaaabb8f0df0 in PyObject_Malloc Objects/obmalloc.c:966
    #6 0xaaaabb92e22c in _PyObject_MallocWithType Include/internal/pycore_object_alloc.h:46
    #7 0xaaaabb92e22c in _PyType_AllocNoTrack Objects/typeobject.c:1739
    #8 0xaaaabb92e538 in PyType_GenericAlloc Objects/typeobject.c:1763
    #9 0xaaaabb92830c in object_new Objects/typeobject.c:5555
    #10 0xaaaabb92ec48 in type_call Objects/typeobject.c:1682
    #11 0xaaaabb7cc64c in _PyObject_MakeTpCall Objects/call.c:242
    #12 0xaaaabb7ccc90 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:166
    #13 0xaaaabb7cccc0 in PyObject_Vectorcall Objects/call.c:327
    #14 0xaaaabbab73e4 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:815
    #15 0xaaaabbb008f4 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #16 0xaaaabbb008f4 in _PyEval_Vector Python/ceval.c:1788
    #17 0xaaaabbb00abc in PyEval_EvalCode Python/ceval.c:592
    #18 0xaaaabbc02aec in run_eval_code_obj Python/pythonrun.c:1294
    #19 0xaaaabbc059e0 in run_mod Python/pythonrun.c:1379
    #20 0xaaaabbc0677c in pyrun_file Python/pythonrun.c:1215
    #21 0xaaaabbc08c3c in _PyRun_SimpleFileObject Python/pythonrun.c:464
    #22 0xaaaabbc08ff4 in _PyRun_AnyFileObject Python/pythonrun.c:77
    #23 0xaaaabbc66e68 in pymain_run_file_obj Modules/main.c:357
    #24 0xaaaabbc693d8 in pymain_run_file Modules/main.c:376
    #25 0xaaaabbc69de0 in pymain_run_python Modules/main.c:628
    #26 0xaaaabbc6a084 in Py_RunMain Modules/main.c:707
    #27 0xaaaabbc6a274 in pymain_main Modules/main.c:737
    #28 0xaaaabbc6a5b0 in Py_BytesMain Modules/main.c:761
    #29 0xaaaabb63145c in main Programs/python.c:15
    #30 0xffffb93d73f8 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #31 0xffffb93d74c8 in __libc_start_main_impl ../csu/libc-start.c:392

SUMMARY: AddressSanitizer: heap-use-after-free Include/object.h:333 in Py_TYPE
Shadow bytes around the buggy address:
  0x200ff610d620: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x200ff610d630: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x200ff610d640: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x200ff610d650: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x200ff610d660: fa fa fa fa fd fd fd fd fd fd fd fd fd fa fa fa
=>0x200ff610d670: fa fa fd fd fd fd fd fd fd[fd]fd fa fa fa fa fa
  0x200ff610d680: fd fd fd fd fd fd fd fd fd fd fa fa fa fa fd fd
  0x200ff610d690: fd fd fd fd fd fd fd fd fa fa fa fa fd fd fd fd
  0x200ff610d6a0: fd fd fd fd fd fd fa fa fa fa 00 00 00 00 00 00
  0x200ff610d6b0: 00 00 00 00 fa fa fa fa 00 00 00 00 00 00 00 00
  0x200ff610d6c0: 00 00 fa fa fa fa 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==246599==ABORTING

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Output from running 'python -VV' on the command line:

Python 3.13.0a3+ (heads/v3.13.0a2:e2c4038924, Feb 10 2024, 12:05:47) [GCC 11.4.0]

Linked PRs

• gh-115243: Fix crash in deque.index() when the deque is concurrently modified #115247
• [3.12] gh-115243: Fix crash in deque.index() when the deque is concurrently modified (GH-115247) #115465
• [3.11] gh-115243: Fix crash in deque.index() when the deque is concurrently modified (GH-115247) #115466

[Eclips4]

Good catch!
Would you like to send a PR with fix?

[Eclips4]

By the way, on all versions except 3.13 with this PoC we won't get segfault:

 python3.12 example.py
Traceback (most recent call last):
  File "/home/eclips4/CLionProjects/cpython/example.py", line 10, in <module>
    deq.index(3)
RuntimeError: deque mutated during iteration

[kcatss]

yes. me too. However, the ASAN build of Python 3.13 can be crashed.

The build instruction is followed.

  ./configure --with-pydebug --with-address-sanitizer

In my opinion, it will be exploited before RuntimeError is called, due to the use-after-free being triggered already.

[Eclips4]

Yep, we definitely have to fix it. Here's what the fix should look like:

diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index ef77d34b10..4fa76d62bc 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -1218,8 +1218,9 @@ deque_index_impl(dequeobject *deque, PyObject *v, Py_ssize_t start,
     n = stop - i;
     while (--n >= 0) {
         CHECK_NOT_END(b);
-        item = b->data[index];
+        item = Py_NewRef(b->data[index]);
         cmp = PyObject_RichCompareBool(item, v, Py_EQ);
+        Py_DECREF(item);
         if (cmp > 0)
             return PyLong_FromSsize_t(stop - n - 1);
         if (cmp < 0)

Would you like to send a PR with this fix? We also need to add a test for this case.

[Eclips4]

By the way, on all versions except 3.13 with this PoC we won't get segfault:

 python3.12 example.py
Traceback (most recent call last):
  File "/home/eclips4/CLionProjects/cpython/example.py", line 10, in <module>
    deq.index(3)
RuntimeError: deque mutated during iteration

The segfault reproducible on 3.11 & 3.12 debug builds (but not on their release builds)