Use After Free at _heapreplace_max

[kcatss]

Crash report

What happened?

Version

Python 3.13.0a3+ (heads/main:b3f0b698da, Feb 12 2024, 03:56:25) [GCC 11.4.0]
bisect from commit f95a1b3

Root Cause

The improper validation in headq._heapreplace_max allows the list to contain itself.
And headq._heapreplace_max finally call list_richcompare if the elements are both list type.
At that time, the self argument of __lt__ is an element of the other argument.
In the __lt__ function, the other argument can decrease the reference count of the self argument by using functions such as pop or remove. This action could potentially modify the list that self is part of while it is being compared, leading to unexpected behavior or errors such as use after free.

POC

import heapq

class test():
    def __lt__(self, other):
        heapq._heappop_max(other)
        return NotImplemented

a = [0, [test()]] 
heapq._heapreplace_max(a, a)

Asan

asan

==426==ERROR: AddressSanitizer: heap-use-after-free on address 0x60700085b9d8 at pc 0x5619b030873c bp 0x7fff42570720 sp 0x7fff42570710
READ of size 8 at 0x60700085b9d8 thread T0
    #0 0x5619b030873b in Py_TYPE Include/object.h:330
    #1 0x5619b030873b in list_richcompare_impl Objects/listobject.c:2805
    #2 0x5619b030a89a in list_richcompare Objects/listobject.c:2860
    #3 0x5619b04bb27f in do_richcompare Objects/object.c:908
    #4 0x5619b04bbf85 in PyObject_RichCompare Objects/object.c:951
    #5 0x5619b0309ea9 in list_richcompare_impl Objects/listobject.c:2852
    #6 0x5619b030a89a in list_richcompare Objects/listobject.c:2860
    #7 0x5619b04bac89 in do_richcompare Objects/object.c:902
    #8 0x5619b04bbf85 in PyObject_RichCompare Objects/object.c:951
    #9 0x5619b04bc62e in PyObject_RichCompareBool Objects/object.c:973
    #10 0x7facc703cf12 in siftdown_max Modules/_heapqmodule.c:411
    #11 0x7facc70429d0 in siftup_max Modules/_heapqmodule.c:480
    #12 0x7facc7042f51 in heapreplace_internal Modules/_heapqmodule.c:201
    #13 0x7facc70438ce in _heapq__heapreplace_max_impl Modules/_heapqmodule.c:515
    #14 0x7facc7043a55 in _heapq__heapreplace_max Modules/clinic/_heapqmodule.c.h:236
    #15 0x5619b0475d73 in cfunction_vectorcall_FASTCALL Objects/methodobject.c:425
    #16 0x5619b0149de8 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #17 0x5619b014a09d in PyObject_Vectorcall Objects/call.c:327
    #18 0x5619b0bb6714 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:815
    #19 0x5619b0c54342 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #20 0x5619b0c54342 in _PyEval_Vector Python/ceval.c:1770
    #21 0x5619b01476df in _PyFunction_Vectorcall Objects/call.c:413
    #22 0x5619b0686967 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #23 0x5619b0686967 in vectorcall_unbound Objects/typeobject.c:2264
    #24 0x5619b0686967 in slot_tp_richcompare Objects/typeobject.c:8963
    #25 0x5619b04bb27f in do_richcompare Objects/object.c:908
    #26 0x5619b04bbf85 in PyObject_RichCompare Objects/object.c:951
    #27 0x5619b04bc62e in PyObject_RichCompareBool Objects/object.c:973
    #28 0x7facc703cf12 in siftdown_max Modules/_heapqmodule.c:411
    #29 0x7facc70429d0 in siftup_max Modules/_heapqmodule.c:480
    #30 0x7facc7039534 in heapify_internal Modules/_heapqmodule.c:368
    #31 0x7facc703960f in _heapq__heapify_max_impl Modules/_heapqmodule.c:531
    #32 0x7facc70396e7 in _heapq__heapify_max Modules/clinic/_heapqmodule.c.h:265
    #33 0x5619b04774fa in cfunction_vectorcall_O Objects/methodobject.c:512
    #34 0x5619b0149de8 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #35 0x5619b014a09d in PyObject_Vectorcall Objects/call.c:327
    #36 0x5619b0bb6714 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:815
    #37 0x5619b0c54342 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #38 0x5619b0c54342 in _PyEval_Vector Python/ceval.c:1770
    #39 0x5619b0c546ee in PyEval_EvalCode Python/ceval.c:591
    #40 0x5619b0fe6684 in run_eval_code_obj Python/pythonrun.c:1294
    #41 0x5619b0ff619d in run_mod Python/pythonrun.c:1379
    #42 0x5619b0ff7b4f in pyrun_file Python/pythonrun.c:1215
    #43 0x5619b0fffe73 in _PyRun_SimpleFileObject Python/pythonrun.c:464
    #44 0x5619b10011a6 in _PyRun_AnyFileObject Python/pythonrun.c:77
    #45 0x5619b1148f55 in pymain_run_file_obj Modules/main.c:357
    #46 0x5619b114ae83 in pymain_run_file Modules/main.c:376
    #47 0x5619b115677d in pymain_run_python Modules/main.c:628
    #48 0x5619b1156c1a in Py_RunMain Modules/main.c:707
    #49 0x5619b11570ad in pymain_main Modules/main.c:737
    #50 0x5619b115752a in Py_BytesMain Modules/main.c:761
    #51 0x5619afc8de25 in main Programs/python.c:15
    #52 0x7facca4f8d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)
    #53 0x7facca4f8e3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f)
    #54 0x5619afc8dd54 in _start (/cpython/python+0x271d54)

0x60700085b9d8 is located 56 bytes inside of 72-byte region [0x60700085b9a0,0x60700085b9e8)
freed by thread T0 here:
    #0 0x7facca893537 in __interceptor_free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:127
    #1 0x5619b04c8533 in _PyMem_RawFree Objects/obmalloc.c:83
    #2 0x5619b04cfbd3 in _PyMem_DebugRawFree Objects/obmalloc.c:2369
    #3 0x5619b04d13b5 in _PyMem_DebugFree Objects/obmalloc.c:2502
    #4 0x5619b053a8d9 in PyObject_Free Objects/obmalloc.c:994
    #5 0x5619b0e061dd in PyObject_GC_Del Python/gc.c:1900
    #6 0x5619b05c4309 in object_dealloc Objects/typeobject.c:5551
    #7 0x5619b0652ec2 in subtype_dealloc Objects/typeobject.c:2085
    #8 0x5619b04a1a89 in _Py_Dealloc Objects/object.c:2866
    #9 0x5619b05ad4d8 in Py_DECREF Include/object.h:915
    #10 0x5619b05ad4d8 in Py_XDECREF Include/object.h:1023
    #11 0x5619b05ad4d8 in tupledealloc Objects/tupleobject.c:208
    #12 0x5619b04a1a89 in _Py_Dealloc Objects/object.c:2866
    #13 0x5619b0deb1f2 in Py_DECREF Include/object.h:915
    #14 0x5619b0deb1f2 in Py_XDECREF Include/object.h:1023
    #15 0x5619b0deb1f2 in _PyFrame_ClearExceptCode Python/frame.c:140
    #16 0x5619b0b708cc in clear_thread_frame Python/ceval.c:1634
    #17 0x5619b0b97124 in _PyEval_FrameClearAndPop Python/ceval.c:1661
    #18 0x5619b0c10b0e in _PyEval_EvalFrameDefault Python/generated_cases.c.h:4923
    #19 0x5619b0c54342 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #20 0x5619b0c54342 in _PyEval_Vector Python/ceval.c:1770
    #21 0x5619b01476df in _PyFunction_Vectorcall Objects/call.c:413
    #22 0x5619b0686967 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:168
    #23 0x5619b0686967 in vectorcall_unbound Objects/typeobject.c:2264
    #24 0x5619b0686967 in slot_tp_richcompare Objects/typeobject.c:8963
    #25 0x5619b04bac89 in do_richcompare Objects/object.c:902
    #26 0x5619b04bbf85 in PyObject_RichCompare Objects/object.c:951
    #27 0x5619b0309ea9 in list_richcompare_impl Objects/listobject.c:2852
    #28 0x5619b030a89a in list_richcompare Objects/listobject.c:2860
    #29 0x5619b04bac89 in do_richcompare Objects/object.c:902
    #30 0x5619b04bbf85 in PyObject_RichCompare Objects/object.c:951
    #31 0x5619b04bc62e in PyObject_RichCompareBool Objects/object.c:973
    #32 0x7facc703cf12 in siftdown_max Modules/_heapqmodule.c:411
    #33 0x7facc70429d0 in siftup_max Modules/_heapqmodule.c:480
    #34 0x7facc7042f51 in heapreplace_internal Modules/_heapqmodule.c:201
    #35 0x7facc70438ce in _heapq__heapreplace_max_impl Modules/_heapqmodule.c:515
    #36 0x7facc7043a55 in _heapq__heapreplace_max Modules/clinic/_heapqmodule.c.h:236

previously allocated by thread T0 here:
    #0 0x7facca893887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x5619b04cbfa6 in _PyMem_RawMalloc Objects/obmalloc.c:55
    #2 0x5619b04c798b in _PyMem_DebugRawAlloc Objects/obmalloc.c:2302
    #3 0x5619b04c7ad7 in _PyMem_DebugRawMalloc Objects/obmalloc.c:2335
    #4 0x5619b04d1505 in _PyMem_DebugMalloc Objects/obmalloc.c:2487
    #5 0x5619b053a452 in PyObject_Malloc Objects/obmalloc.c:965
    #6 0x5619b062e263 in _PyType_AllocNoTrack Objects/typeobject.c:1732
    #7 0x5619b062e970 in PyType_GenericAlloc Objects/typeobject.c:1756
    #8 0x5619b0616d68 in object_new Objects/typeobject.c:5537
    #9 0x5619b064b1c7 in type_call Objects/typeobject.c:1675
    #10 0x5619b0148545 in _PyObject_MakeTpCall Objects/call.c:242
    #11 0x5619b014a03a in _PyObject_VectorcallTstate Include/internal/pycore_call.h:166
    #12 0x5619b014a09d in PyObject_Vectorcall Objects/call.c:327
    #13 0x5619b0bb6714 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:815
    #14 0x5619b0c54342 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:115
    #15 0x5619b0c54342 in _PyEval_Vector Python/ceval.c:1770
    #16 0x5619b0c546ee in PyEval_EvalCode Python/ceval.c:591
    #17 0x5619b0fe6684 in run_eval_code_obj Python/pythonrun.c:1294
    #18 0x5619b0ff619d in run_mod Python/pythonrun.c:1379
    #19 0x5619b0ff7b4f in pyrun_file Python/pythonrun.c:1215
    #20 0x5619b0fffe73 in _PyRun_SimpleFileObject Python/pythonrun.c:464
    #21 0x5619b10011a6 in _PyRun_AnyFileObject Python/pythonrun.c:77
    #22 0x5619b1148f55 in pymain_run_file_obj Modules/main.c:357
    #23 0x5619b114ae83 in pymain_run_file Modules/main.c:376
    #24 0x5619b115677d in pymain_run_python Modules/main.c:628
    #25 0x5619b1156c1a in Py_RunMain Modules/main.c:707
    #26 0x5619b11570ad in pymain_main Modules/main.c:737
    #27 0x5619b115752a in Py_BytesMain Modules/main.c:761
    #28 0x5619afc8de25 in main Programs/python.c:15
    #29 0x7facca4f8d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)

SUMMARY: AddressSanitizer: heap-use-after-free Include/object.h:330 in Py_TYPE
Shadow bytes around the buggy address:
  0x0c0e801036e0: fd fd fd fd fd fd fd fd fd fd fa fa fa fa fd fd
  0x0c0e801036f0: fd fd fd fd fd fd fd fa fa fa fa fa fd fd fd fd
  0x0c0e80103700: fd fd fd fd fd fd fa fa fa fa fd fd fd fd fd fd
  0x0c0e80103710: fd fd fd fd fa fa fa fa 00 00 00 00 00 00 00 00
  0x0c0e80103720: 00 fa fa fa fa fa 00 00 00 00 00 00 00 00 00 fa
=>0x0c0e80103730: fa fa fa fa fd fd fd fd fd fd fd[fd]fd fa fa fa
  0x0c0e80103740: fa fa 00 00 00 00 00 00 00 00 00 fa fa fa fa fa
  0x0c0e80103750: 00 00 00 00 00 00 00 00 00 00 fa fa fa fa fd fd
  0x0c0e80103760: fd fd fd fd fd fd fd fd fa fa fa fa fd fd fd fd
  0x0c0e80103770: fd fd fd fd fd fa fa fa fa fa fd fd fd fd fd fd
  0x0c0e80103780: fd fd fd fa fa fa fa fa fd fd fd fd fd fd fd fd
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
==426==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]

[Eclips4]

Confirmed on current main.

[kcatss]

Add the asan log of this uaf

[sobolevn]

Looks like this was also fixed by #120303

Python 3.14.0a0 (heads/main:141babad9b4, Jun 11 2024, 10:06:51) [Clang 15.0.0 (clang-1500.3.9.4)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import heapq
... 
... class test():
...     def __lt__(self, other):
...         heapq._heappop_max(other)
...         return NotImplemented
... 
... a = [0, [test()]] 
... heapq._heapreplace_max(a, a)
Traceback (most recent call last):
  File "<python-input-0>", line 9, in <module>
    heapq._heapreplace_max(a, a)
    ~~~~~~~~~~~~~~~~~~~~~~^^^^^^
TypeError: '<' not supported between instances of 'test' and 'list'

Thanks a lot for useful bug reports and reproductions! 👍