Use-after-free in `OrderedDict.copy` via re-entrant `__getitem__`

[jackfromeast]

What happened?

OrderedDict.copy() iterates its nodes and calls __getitem__ to fetch values. A re-entrant __getitem__ that calls clear() during iteration frees all _ODictNode structures while _odict_FOREACH continues accessing them, resulting in a heap-use-after-free in OrderedDict_copy_impl.

Proof of Concept:

from collections import OrderedDict

class Evil(OrderedDict):
    def __getitem__(self, key):
        super().clear()
        return None

# Trigger
Evil([(i, i) for i in range(4)]).copy()

Affected Versions:

Details

Python Version	Status	Exit Code
Python 3.9.24+ (heads/3.9:9c4638d, Oct 17 2025, 11:19:30)	ASAN	1
Python 3.10.19+ (heads/3.10:0142619, Oct 17 2025, 11:20:05) [GCC 13.3.0]	ASAN	1
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

Relevent Code Snippets

Details

static PyObject *
OrderedDict_copy_impl(PyObject *od)
/*[clinic end generated code: output=9cdbe7394aecc576 input=e329951ae617ed48]*/
{
    _ODictNode *node;
    PyObject *od_copy;

    if (PyODict_CheckExact(od))
        od_copy = PyODict_New();
    else
        od_copy = _PyObject_CallNoArgs((PyObject *)Py_TYPE(od));
    if (od_copy == NULL)
        return NULL;

    if (PyODict_CheckExact(od)) {
        _odict_FOREACH(od, node) {
            PyObject *key = _odictnode_KEY(node);
            PyObject *value = _odictnode_VALUE(node, od);
            if (value == NULL) {
                if (!PyErr_Occurred())
                    PyErr_SetObject(PyExc_KeyError, key);
                goto fail;
            }
            if (_PyODict_SetItem_KnownHash_LockHeld((PyObject *)od_copy, key, value,
                                                    _odictnode_HASH(node)) != 0)
                goto fail;
        }
    }
    else {
        _odict_FOREACH(od, node) {
            int res;
            // Trigger the __getitem__ and clear the array buffer so that all the node are freed
            PyObject *value = PyObject_GetItem((PyObject *)od,
                                               _odictnode_KEY(node));
            if (value == NULL)
                goto fail;
                
            // Bug: Access the freed node buffer 
            res = PyObject_SetItem((PyObject *)od_copy,
                                   _odictnode_KEY(node), value);
            Py_DECREF(value);
            if (res != 0)
                goto fail;
        }
    }
    return od_copy;

fail:
    Py_DECREF(od_copy);
    return NULL;
}

Sanitizer Output:

Details

=================================================================
==1546618==ERROR: AddressSanitizer: heap-use-after-free on address 0x506000063ff0 at pc 0x5b4c98be21ee bp 0x7fff1abcc980 sp 0x7fff1abcc970
READ of size 8 at 0x506000063ff0 thread T0
    #0 0x5b4c98be21ed in OrderedDict_copy_impl Objects/odictobject.c:1276
    #1 0x5b4c98be2289 in OrderedDict_copy Objects/clinic/odictobject.c.h:377
    #2 0x5b4c98b5f571 in method_vectorcall_NOARGS Objects/descrobject.c:448
    #3 0x5b4c98b3fe7f in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #4 0x5b4c98b3ff72 in PyObject_Vectorcall Objects/call.c:327
    #5 0x5b4c98dbe056 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620
    #6 0x5b4c98e01e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #7 0x5b4c98e02148 in _PyEval_Vector Python/ceval.c:2001
    #8 0x5b4c98e023f8 in PyEval_EvalCode Python/ceval.c:884
    #9 0x5b4c98ef9507 in run_eval_code_obj Python/pythonrun.c:1365
    #10 0x5b4c98ef9723 in run_mod Python/pythonrun.c:1459
    #11 0x5b4c98efa57a in pyrun_file Python/pythonrun.c:1293
    #12 0x5b4c98efd220 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #13 0x5b4c98efd4f6 in _PyRun_AnyFileObject Python/pythonrun.c:81
    #14 0x5b4c98f4e74d in pymain_run_file_obj Modules/main.c:410
    #15 0x5b4c98f4e9b4 in pymain_run_file Modules/main.c:429
    #16 0x5b4c98f501b2 in pymain_run_python Modules/main.c:691
    #17 0x5b4c98f50842 in Py_RunMain Modules/main.c:772
    #18 0x5b4c98f50a2e in pymain_main Modules/main.c:802
    #19 0x5b4c98f50db3 in Py_BytesMain Modules/main.c:826
    #20 0x5b4c989d4645 in main Programs/python.c:15
    #21 0x7eeb96e2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #22 0x7eeb96e2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #23 0x5b4c989d4574 in _start (/home/jackfromeast/Desktop/entropy/tasks/grammar-afl++-latest/targets/cpython/python+0x2dd574) (BuildId: ff3dc40ea460bd4beb2c3a72283cca525b319bf0)

0x506000063ff0 is located 16 bytes inside of 56-byte region [0x506000063fe0,0x506000064018)
freed by thread T0 here:
    #0 0x7eeb972fc4d8 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0x5b4c98c0696d in _PyMem_RawFree Objects/obmalloc.c:91
    #2 0x5b4c98c08cd9 in _PyMem_DebugRawFree Objects/obmalloc.c:2955
    #3 0x5b4c98c08d1a in _PyMem_DebugFree Objects/obmalloc.c:3100
    #4 0x5b4c98c30348 in PyMem_Free Objects/obmalloc.c:1070
    #5 0x5b4c98bde533 in _odict_clear_nodes Objects/odictobject.c:810
    #6 0x5b4c98bdff79 in OrderedDict_clear_impl Objects/odictobject.c:1227
    #7 0x5b4c98bdff93 in OrderedDict_clear Objects/clinic/odictobject.c.h:353
    #8 0x5b4c98bf24f3 in cfunction_vectorcall_NOARGS Objects/methodobject.c:508
    #9 0x5b4c98b3fe7f in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #10 0x5b4c98b3ff72 in PyObject_Vectorcall Objects/call.c:327
    #11 0x5b4c98dbe056 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620
    #12 0x5b4c98e01e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #13 0x5b4c98e02148 in _PyEval_Vector Python/ceval.c:2001
    #14 0x5b4c98b3f9b8 in _PyFunction_Vectorcall Objects/call.c:413
    #15 0x5b4c98c5256b in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #16 0x5b4c98c52680 in vectorcall_unbound Objects/typeobject.c:3033
    #17 0x5b4c98c73976 in vectorcall_method Objects/typeobject.c:3104
    #18 0x5b4c98c740ee in slot_mp_subscript Objects/typeobject.c:10371
    #19 0x5b4c98b0f393 in PyObject_GetItem Objects/abstract.c:163
    #20 0x5b4c98be2215 in OrderedDict_copy_impl Objects/odictobject.c:1272
    #21 0x5b4c98be2289 in OrderedDict_copy Objects/clinic/odictobject.c.h:377
    #22 0x5b4c98b5f571 in method_vectorcall_NOARGS Objects/descrobject.c:448
    #23 0x5b4c98b3fe7f in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #24 0x5b4c98b3ff72 in PyObject_Vectorcall Objects/call.c:327
    #25 0x5b4c98dbe056 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620
    #26 0x5b4c98e01e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #27 0x5b4c98e02148 in _PyEval_Vector Python/ceval.c:2001
    #28 0x5b4c98e023f8 in PyEval_EvalCode Python/ceval.c:884
    #29 0x5b4c98ef9507 in run_eval_code_obj Python/pythonrun.c:1365

previously allocated by thread T0 here:
    #0 0x7eeb972fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x5b4c98c07284 in _PyMem_RawMalloc Objects/obmalloc.c:63
    #2 0x5b4c98c06655 in _PyMem_DebugRawAlloc Objects/obmalloc.c:2887
    #3 0x5b4c98c066bd in _PyMem_DebugRawMalloc Objects/obmalloc.c:2920
    #4 0x5b4c98c07f3b in _PyMem_DebugMalloc Objects/obmalloc.c:3085
    #5 0x5b4c98c30204 in PyMem_Malloc Objects/obmalloc.c:1041
    #6 0x5b4c98bdf3c6 in _odict_add_new_node Objects/odictobject.c:705
    #7 0x5b4c98bdfef3 in _PyODict_SetItem_KnownHash_LockHeld Objects/odictobject.c:1628
    #8 0x5b4c98bdff4e in PyODict_SetItem_LockHeld Objects/odictobject.c:1648
    #9 0x5b4c98be2298 in PyODict_SetItem Objects/odictobject.c:1656
    #10 0x5b4c98be2321 in odict_mp_ass_sub Objects/odictobject.c:879
    #11 0x5b4c98b0fbe7 in PyObject_SetItem Objects/abstract.c:237
    #12 0x5b4c98bddb32 in mutablemapping_add_pairs Objects/odictobject.c:2253
    #13 0x5b4c98bddfd3 in mutablemapping_update_arg Objects/odictobject.c:2330
    #14 0x5b4c98bde17d in mutablemapping_update Objects/odictobject.c:2351
    #15 0x5b4c98bde3ac in odict_init Objects/odictobject.c:1557
    #16 0x5b4c98c663c0 in type_call Objects/typeobject.c:2460
    #17 0x5b4c98b3fc71 in _PyObject_MakeTpCall Objects/call.c:242
    #18 0x5b4c98b3ff19 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:167
    #19 0x5b4c98b3ff72 in PyObject_Vectorcall Objects/call.c:327
    #20 0x5b4c98dbe056 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620
    #21 0x5b4c98e01e54 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #22 0x5b4c98e02148 in _PyEval_Vector Python/ceval.c:2001
    #23 0x5b4c98e023f8 in PyEval_EvalCode Python/ceval.c:884
    #24 0x5b4c98ef9507 in run_eval_code_obj Python/pythonrun.c:1365
    #25 0x5b4c98ef9723 in run_mod Python/pythonrun.c:1459
    #26 0x5b4c98efa57a in pyrun_file Python/pythonrun.c:1293
    #27 0x5b4c98efd220 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #28 0x5b4c98efd4f6 in _PyRun_AnyFileObject Python/pythonrun.c:81
    #29 0x5b4c98f4e74d in pymain_run_file_obj Modules/main.c:410

SUMMARY: AddressSanitizer: heap-use-after-free Objects/odictobject.c:1276 in OrderedDict_copy_impl
Shadow bytes around the buggy address:
  0x506000063d00: 00 00 00 fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x506000063d80: fa fa fa fa fd fd fd fd fd fd fd fd fa fa fa fa
  0x506000063e00: fd fd fd fd fd fd fd fa fa fa fa fa 00 00 00 00
  0x506000063e80: 00 00 00 00 fa fa fa fa fd fd fd fd fd fd fd fd
  0x506000063f00: fa fa fa fa 00 00 00 00 00 00 00 fa fa fa fa fa
=>0x506000063f80: fd fd fd fd fd fd fd fa fa fa fa fa fd fd[fd]fd
  0x506000064000: fd fd fd fa fa fa fa fa fd fd fd fd fd fd fd fa
  0x506000064080: fa fa fa fa fd fd fd fd fd fd fd fa fa fa fa fa
  0x506000064100: fd fd fd fd fd fd fd fa fa fa fa fa fa fa fa fa
  0x506000064180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x506000064200: 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
==1546618==ABORTING

Linked PRs

• gh-142734: fix OrderedDict copy heap-use-after-free security issue #143059

[superboy-zjc]

The OrderedDict.copy() subclass branch iterates over _ODictNode pointers while calling PyObject_GetItem(). Since PyObject_GetItem() invokes the overridden __getitem__, it is possible for a re-entrant call to clear() frees all _ODictNode structs. The loop then continues and dereferences the freed node (via _odictnode_KEY(node)), resulting in a UAF.

A straightforward fix is to snapshot the keys (e.g., into a list) before any call to PyObject_GetItem()/Python. This avoids accessing raw node pointers during the iteration where re-entrancy is possible, and ensures keys remain alive even if clear() is invoked.