python / python/cpython

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

Open
#142,637 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

extension-modules type-crash
Dominant language
Python
Stars
77.2k
Forks
35.9k
PR metrics pending

Description

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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the three re-entrant OrderedDict cases under ASAN, then read Objects/odictobject.c around _odict_get_index_raw and _odict_clear_node. Trace the lookup and cleanup paths used by deletion, pop, and move_to_end; done means these cases no longer access freed table or node storage and have regression coverage.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, python
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.