Use-after-free in several `OrderedDict` operations via re-entrant `__eq__`

[jackfromeast]

What happened?

OrderedDict.__delitem__ (PyObject_DelItem) locates key using hash/equality. A re-entrant __eq__ that calls od.clear() during lookup frees/reshapes the table (ma_keys/od_fast_nodes) while _odict_clear_node() continues using stale pointers, causing a heap-use-after-free in _odict_get_index_raw.

The same bug also is also shown in other OrderedDict operations, like pop and move_to_end.

Proof of Concept:

from collections import OrderedDict

class Original:
    def __hash__(self):
        return 1

class Trigger:
    def __hash__(self):
        return 1
    def __eq__(self, other):
        od.clear()
        return True

od = OrderedDict()
od[Original()] = None
del od[Trigger()]

from collections import OrderedDict

class Original:
    def __init__(self):
        pass

    def __hash__(self):
        return 1

class Trigger:
    def __hash__(self):
        return 1

    def __eq__(self, other):
        # re-entrant mutation while move_to_end() is searching for the key
        od.clear()
        return True

od = OrderedDict()
od[Original()] = None
od.move_to_end(Trigger())

from collections import OrderedDict

class Original():
    def __hash__(self):
        return 1

class Trigger:
    def __hash__(self):
        return 1
    def __eq__(self, other):
        global od
        od.clear()
        return True

od = OrderedDict()
od[Original()] = None
od.pop(Trigger())

Affected Versions:

Python Version	Status	Exit Code
Python 3.9.24+ (heads/3.9:9c4638d, Oct 17 2025, 11:19:30)	Assert	-6
Python 3.10.19+ (heads/3.10:0142619, Oct 17 2025, 11:20:05) [GCC 13.3.0]	Assert	-6
Python 3.11.14+ (heads/3.11:88f3f5b, Oct 17 2025, 11:20:44) [GCC 13.3.0]	ASAN	1
Python 3.12.12+ (heads/3.12:8cb2092, Oct 17 2025, 11:21:35) [GCC 13.3.0]	ASAN	1
Python 3.13.9+ (heads/3.13:0760a57, Oct 17 2025, 11:22:25) [GCC 13.3.0]	ASAN	1
Python 3.14.0+ (heads/3.14:889e918, Oct 17 2025, 11:23:02) [GCC 13.3.0]	ASAN	1
Python 3.15.0a1+ (heads/main:fbf0843, Oct 17 2025, 11:23:37) [GCC 13.3.0]	ASAN	1

Sanitizer Output:

=================================================================
==977233==ERROR: AddressSanitizer: heap-use-after-free on address 0x510000058d68 at pc 0x5957660a36fa bp 0x7fffafd9d500 sp 0x7fffafd9d4f0
READ of size 8 at 0x510000058d68 thread T0
    #0 0x5957660a36f9 in _odict_get_index_raw Objects/odictobject.c:550
    #1 0x5957660a39a6 in _odict_get_index Objects/odictobject.c:615
    #2 0x5957660a456a in _odict_clear_node Objects/odictobject.c:775
    #3 0x5957660a72d5 in PyODict_DelItem_LockHeld Objects/odictobject.c:1669
    #4 0x5957660a730d in PyODict_DelItem Objects/odictobject.c:1680
    #5 0x5957660a7328 in odict_mp_ass_sub Objects/odictobject.c:877
    #6 0x595765fd5046 in PyObject_DelItem Objects/abstract.c:271
    #7 0x5957662992d7 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:5281
    #8 0x5957662c6e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #9 0x5957662c7148 in _PyEval_Vector Python/ceval.c:2001
    #10 0x5957662c73f8 in PyEval_EvalCode Python/ceval.c:884
    #11 0x5957663be507 in run_eval_code_obj Python/pythonrun.c:1365
    #12 0x5957663be723 in run_mod Python/pythonrun.c:1459
    #13 0x5957663bf57a in pyrun_file Python/pythonrun.c:1293
    #14 0x5957663c2220 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #15 0x5957663c24f6 in _PyRun_AnyFileObject Python/pythonrun.c:81
    #16 0x59576641374d in pymain_run_file_obj Modules/main.c:410
    #17 0x5957664139b4 in pymain_run_file Modules/main.c:429
    #18 0x5957664151b2 in pymain_run_python Modules/main.c:691
    #19 0x595766415842 in Py_RunMain Modules/main.c:772
    #20 0x595766415a2e in pymain_main Modules/main.c:802
    #21 0x595766415db3 in Py_BytesMain Modules/main.c:826
    #22 0x595765e99645 in main Programs/python.c:15
    #23 0x71bb5942a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #24 0x71bb5942a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #25 0x595765e99574 in _start (/home/jackfromeast/Desktop/entropy/tasks/grammar-afl++-latest/targets/cpython/python+0x2dd574) (BuildId: ff3dc40ea460bd4beb2c3a72283cca525b319bf0)

0x510000058d68 is located 40 bytes inside of 184-byte region [0x510000058d40,0x510000058df8)
freed by thread T0 here:
    #0 0x71bb598fc4d8 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0x5957660cb96d in _PyMem_RawFree Objects/obmalloc.c:91
    #2 0x5957660cdcd9 in _PyMem_DebugRawFree Objects/obmalloc.c:2955
    #3 0x5957660cdd1a in _PyMem_DebugFree Objects/obmalloc.c:3100
    #4 0x5957660f5348 in PyMem_Free Objects/obmalloc.c:1070
    #5 0x59576608dd52 in free_keys_object Objects/dictobject.c:823
    #6 0x59576608dfba in dictkeys_decref Objects/dictobject.c:473
    #7 0x59576609e4e9 in clear_lock_held Objects/dictobject.c:2947
    #8 0x59576609e680 in _PyDict_Clear_LockHeld Objects/dictobject.c:2969
    #9 0x5957660a4f71 in OrderedDict_clear_impl Objects/odictobject.c:1226
    #10 0x5957660a4f93 in OrderedDict_clear Objects/clinic/odictobject.c.h:353
    #11 0x595766024571 in method_vectorcall_NOARGS Objects/descrobject.c:448
    #12 0x595766004e7f in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #13 0x595766004f72 in PyObject_Vectorcall Objects/call.c:327
    #14 0x595766283056 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620
    #15 0x5957662c6e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #16 0x5957662c7148 in _PyEval_Vector Python/ceval.c:2001
    #17 0x5957660049b8 in _PyFunction_Vectorcall Objects/call.c:413
    #18 0x59576611756b in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #19 0x5957661339a6 in vectorcall_unbound Objects/typeobject.c:3033
    #20 0x5957661339a6 in maybe_call_special_one_arg Objects/typeobject.c:3175
    #21 0x595766133ad3 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190
    #22 0x595766133b19 in slot_tp_richcompare Objects/typeobject.c:10729
    #23 0x5957660c4762 in do_richcompare Objects/object.c:1065
    #24 0x5957660c493d in PyObject_RichCompare Objects/object.c:1108
    #25 0x5957660c49ad in PyObject_RichCompareBool Objects/object.c:1130
    #26 0x59576608e589 in compare_generic Objects/dictobject.c:1110
    #27 0x59576608b340 in do_lookup Objects/dictobject.c:1010
    #28 0x59576608b3db in dictkeys_generic_lookup Objects/dictobject.c:1129
    #29 0x595766094833 in _Py_dict_lookup Objects/dictobject.c:1295
    #30 0x5957660a3678 in _odict_get_index_raw Objects/odictobject.c:547

previously allocated by thread T0 here:
    #0 0x71bb598fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x5957660cc284 in _PyMem_RawMalloc Objects/obmalloc.c:63
    #2 0x5957660cb655 in _PyMem_DebugRawAlloc Objects/obmalloc.c:2887
    #3 0x5957660cb6bd in _PyMem_DebugRawMalloc Objects/obmalloc.c:2920
    #4 0x5957660ccf3b in _PyMem_DebugMalloc Objects/obmalloc.c:3085
    #5 0x5957660f5204 in PyMem_Malloc Objects/obmalloc.c:1041
    #6 0x59576608ebde in new_keys_object Objects/dictobject.c:784
    #7 0x59576609ab28 in insert_to_emptydict Objects/dictobject.c:1948
    #8 0x59576609d1c7 in _PyDict_SetItem_KnownHash_LockHeld Objects/dictobject.c:2723
    #9 0x5957660a4ece in _PyODict_SetItem_KnownHash_LockHeld Objects/odictobject.c:1626
    #10 0x5957660a4f4e in PyODict_SetItem_LockHeld Objects/odictobject.c:1648
    #11 0x5957660a7298 in PyODict_SetItem Objects/odictobject.c:1656
    #12 0x5957660a7321 in odict_mp_ass_sub Objects/odictobject.c:879
    #13 0x595765fd4be7 in PyObject_SetItem Objects/abstract.c:237
    #14 0x5957662c02f6 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:11245
    #15 0x5957662c6e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #16 0x5957662c7148 in _PyEval_Vector Python/ceval.c:2001
    #17 0x5957662c73f8 in PyEval_EvalCode Python/ceval.c:884
    #18 0x5957663be507 in run_eval_code_obj Python/pythonrun.c:1365
    #19 0x5957663be723 in run_mod Python/pythonrun.c:1459
    #20 0x5957663bf57a in pyrun_file Python/pythonrun.c:1293
    #21 0x5957663c2220 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #22 0x5957663c24f6 in _PyRun_AnyFileObject Python/pythonrun.c:81
    #23 0x59576641374d in pymain_run_file_obj Modules/main.c:410
    #24 0x5957664139b4 in pymain_run_file Modules/main.c:429
    #25 0x5957664151b2 in pymain_run_python Modules/main.c:691
    #26 0x595766415842 in Py_RunMain Modules/main.c:772
    #27 0x595766415a2e in pymain_main Modules/main.c:802
    #28 0x595766415db3 in Py_BytesMain Modules/main.c:826
    #29 0x595765e99645 in main Programs/python.c:15

SUMMARY: AddressSanitizer: heap-use-after-free Objects/odictobject.c:550 in _odict_get_index_raw
Shadow bytes around the buggy address:
  0x510000058a80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x510000058b00: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x510000058b80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x510000058c00: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x510000058c80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x510000058d00: fa fa fa fa fa fa fa fa fd fd fd fd fd[fd]fd fd
  0x510000058d80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa
  0x510000058e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x510000058e80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x510000058f00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x510000058f80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
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
==977233==ABORTING

[picnixz]

We have two ways of fixing this:

• Fix it so that the behavior aligns with dict.
• Raise a RuntimeError because the state changed. That's what I did in gh-119004: fix a crash in equality testing between OrderedDict #121329.

@rhettinger what do you want to do for OrderedDict? On one's hand it makes sense to make it behave like a dict but on the other hand, __eq__ already behaves differently in those weird situations (after #121329). So I'd be already willing to try the "easy" solution (I don't know which one it will be).