René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Use-after-free in `itertools.groupby` via re-entrant key comparison through `__eq__`","articleBody":"### What happened?\n\n`groupby_next` compares the current and target keys with `PyObject_RichCompareBool` while holding pointers to the active key/value pair. A user-defined `__eq__` can call back into `next(groupby)` mid-compare, advancing the iterator, replacing `currkey/currvalue`, and dereferencing the objects still in use by the outer compare. The outer compare then dereferences freed memory, crashing in `_Py_IsImmortal`.\n\n**Proof of Concept:**\n\n```python\nfrom itertools import groupby\n\n\nclass Key(bytearray):\n    seen = False\n\n    def __init__(self, is_first):\n        self.is_first = is_first\n\n    def __eq__(self, other):\n        global G\n        if self.is_first and not Key.seen:\n            Key.seen = True\n            next(G)\n            return NotImplemented\n        return False\n\n\ndef keys():\n    yield Key(True)\n    while True:\n        yield Key(False)\n\n\nG = groupby([None, 1], keys().send)\nnext(G)\nnext(G)\n```\n\n**Vulnerable Code Snippet:**\n\n\u003cdetails\u003e\n\u003csummary\u003eClick to expand\u003c/summary\u003e\n\n```c\n/* Buggy Re-entrant Path */\nstatic PyObject *\nbuiltin_next(PyObject *self, PyObject *const *args, Py_ssize_t nargs)\n{\n    PyObject *it, *res;\n    /* ... */\n    it = args[0];\n    res = (*Py_TYPE(it)-\u003etp_iternext)(it);\n    /* ... */\n    return res;\n}\n\nstatic PyObject *\ngroupby_next(PyObject *op)\n{\n    PyObject *r, *grouper;\n    groupbyobject *gbo = groupbyobject_CAST(op);\n\n    gbo-\u003ecurrgrouper = NULL;\n    /* skip to next iteration group */\n    for (;;) {\n        if (gbo-\u003ecurrkey == NULL)\n            /* pass */;\n        else if (gbo-\u003etgtkey == NULL)\n            break;\n        else {\n            int rcmp;\n\n            rcmp = PyObject_RichCompareBool(gbo-\u003etgtkey, gbo-\u003ecurrkey, Py_EQ);  /* crashing pointer derived */\n            if (rcmp == -1)\n                return NULL;\n            else if (rcmp == 0)\n                break;\n        }\n\n        if (groupby_step(gbo) \u003c 0)\n            return NULL;\n    }\n    Py_INCREF(gbo-\u003ecurrkey);\n    Py_XSETREF(gbo-\u003etgtkey, gbo-\u003ecurrkey);\n\n    grouper = _grouper_create(gbo, gbo-\u003etgtkey);\n    if (grouper == NULL)\n        return NULL;\n\n    r = PyTuple_Pack(2, gbo-\u003ecurrkey, grouper);\n    Py_DECREF(grouper);\n    return r;\n}\n\nstatic PyObject *\nslot_tp_richcompare(PyObject *self, PyObject *other, int op)\n{\n    PyObject *res = _PyObject_MaybeCallSpecialOneArg(self, name_op[op], other);  /* Reentrant call site */\n    /* ... */\n    return res;\n}\n\nstatic inline Py_ALWAYS_INLINE int _Py_IsImmortal(PyObject *op)\n{\n#if SIZEOF_VOID_P \u003e 4\n    return _Py_CAST(PY_INT32_T, op-\u003eob_refcnt) \u003c 0;  /* Crash site */\n#else\n    return op-\u003eob_refcnt \u003e= _Py_IMMORTAL_MINIMUM_REFCNT;\n#endif\n}\n\n/* Clobbering Path */\nPy_LOCAL_INLINE(int)\ngroupby_step(groupbyobject *gbo)\n{\n    PyObject *newvalue, *newkey, *oldvalue;\n    /* ... */\n    oldvalue = gbo-\u003ecurrvalue;\n    gbo-\u003ecurrvalue = newvalue;\n    Py_XSETREF(gbo-\u003ecurrkey, newkey);  /* state mutate site */\n    Py_XDECREF(oldvalue);\n    return 0;\n}\n```\n\u003c/details\u003e\n\n**Sanitizer Output:**\n\n\u003cdetails\u003e\n\u003csummary\u003eClick to expand\u003c/summary\u003e\n\n```\n=================================================================\n==252399==ERROR: AddressSanitizer: heap-use-after-free on address 0x51300001d3a0 at pc 0x5a6a780142bb bp 0x7fffd4fe72a0 sp 0x7fffd4fe7290\nREAD of size 4 at 0x51300001d3a0 thread T0\n    #0 0x5a6a780142ba in _Py_IsImmortal Include/refcount.h:127\n    #1 0x5a6a780142ba in _PyStackRef_FromPyObjectNew Include/internal/pycore_stackref.h:632\n    #2 0x5a6a780142ba in _PyEval_Vector Python/ceval.c:1983\n    #3 0x5a6a77e475e2 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #4 0x5a6a77e475e2 in vectorcall_unbound Objects/typeobject.c:3033\n    #5 0x5a6a77e475e2 in maybe_call_special_one_arg Objects/typeobject.c:3175\n    #6 0x5a6a77e475e2 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190\n    #7 0x5a6a77e475e2 in slot_tp_richcompare Objects/typeobject.c:10729\n    #8 0x5a6a77db94df in do_richcompare Objects/object.c:1065\n    #9 0x5a6a77db94df in PyObject_RichCompare Objects/object.c:1108\n    #10 0x5a6a77db94df in PyObject_RichCompareBool Objects/object.c:1130\n    #11 0x5a6a782cb6ad in groupby_next Modules/itertoolsmodule.c:549\n    #12 0x5a6a77ff5d8a in builtin_next Python/bltinmodule.c:1681\n    #13 0x5a6a77c953e7 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #14 0x5a6a77c953e7 in PyObject_Vectorcall Objects/call.c:327\n    #15 0x5a6a77b495a2 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620\n    #16 0x5a6a78013ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #17 0x5a6a78013ad6 in _PyEval_Vector Python/ceval.c:2001\n    #18 0x5a6a78013ad6 in PyEval_EvalCode Python/ceval.c:884\n    #19 0x5a6a7815916e in run_eval_code_obj Python/pythonrun.c:1365\n    #20 0x5a6a7815916e in run_mod Python/pythonrun.c:1459\n    #21 0x5a6a7815de17 in pyrun_file Python/pythonrun.c:1293\n    #22 0x5a6a7815de17 in _PyRun_SimpleFileObject Python/pythonrun.c:521\n    #23 0x5a6a7815e93c in _PyRun_AnyFileObject Python/pythonrun.c:81\n    #24 0x5a6a781d1e3c in pymain_run_file_obj Modules/main.c:410\n    #25 0x5a6a781d1e3c in pymain_run_file Modules/main.c:429\n    #26 0x5a6a781d1e3c in pymain_run_python Modules/main.c:691\n    #27 0x5a6a781d371e in Py_RunMain Modules/main.c:772\n    #28 0x5a6a781d371e in pymain_main Modules/main.c:802\n    #29 0x5a6a781d371e in Py_BytesMain Modules/main.c:826\n    #30 0x7800fd62a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n    #31 0x7800fd62a28a in __libc_start_main_impl ../csu/libc-start.c:360\n    #32 0x5a6a77b6d634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)\n\n0x51300001d3a0 is located 32 bytes inside of 368-byte region [0x51300001d380,0x51300001d4f0)\nfreed by thread T0 here:\n    #0 0x7800fdafc4d8 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52\n    #1 0x5a6a77e268f3 in subtype_dealloc Objects/typeobject.c:2852\n    #2 0x5a6a77db21d8 in _Py_Dealloc Objects/object.c:3200\n    #3 0x5a6a7809da49 in Py_DECREF_MORTAL Include/internal/pycore_object.h:482\n    #4 0x5a6a7809da49 in PyStackRef_XCLOSE Include/internal/pycore_stackref.h:736\n    #5 0x5a6a7809da49 in _PyFrame_ClearLocals Python/frame.c:101\n    #6 0x5a6a7809da49 in _PyFrame_ClearExceptCode Python/frame.c:126\n    #7 0x5a6a78009052 in clear_thread_frame Python/ceval.c:1826\n    #8 0x5a6a78009052 in _PyEval_FrameClearAndPop Python/ceval.c:1850\n    #9 0x5a6a77b4df4c in _PyEval_EvalFrameDefault Python/generated_cases.c.h:10403\n    #10 0x5a6a780142a5 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #11 0x5a6a780142a5 in _PyEval_Vector Python/ceval.c:2001\n    #12 0x5a6a77e475e2 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #13 0x5a6a77e475e2 in vectorcall_unbound Objects/typeobject.c:3033\n    #14 0x5a6a77e475e2 in maybe_call_special_one_arg Objects/typeobject.c:3175\n    #15 0x5a6a77e475e2 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190\n    #16 0x5a6a77e475e2 in slot_tp_richcompare Objects/typeobject.c:10729\n    #17 0x5a6a77db92af in do_richcompare Objects/object.c:1059\n    #18 0x5a6a77db92af in PyObject_RichCompare Objects/object.c:1108\n    #19 0x5a6a77db92af in PyObject_RichCompareBool Objects/object.c:1130\n    #20 0x5a6a782cb6ad in groupby_next Modules/itertoolsmodule.c:549\n    #21 0x5a6a77ff5d8a in builtin_next Python/bltinmodule.c:1681\n    #22 0x5a6a77c953e7 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #23 0x5a6a77c953e7 in PyObject_Vectorcall Objects/call.c:327\n    #24 0x5a6a77b495a2 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620\n    #25 0x5a6a78013ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #26 0x5a6a78013ad6 in _PyEval_Vector Python/ceval.c:2001\n    #27 0x5a6a78013ad6 in PyEval_EvalCode Python/ceval.c:884\n    #28 0x5a6a7815916e in run_eval_code_obj Python/pythonrun.c:1365\n    #29 0x5a6a7815916e in run_mod Python/pythonrun.c:1459\n    #30 0x5a6a7815de17 in pyrun_file Python/pythonrun.c:1293\n    #31 0x5a6a7815de17 in _PyRun_SimpleFileObject Python/pythonrun.c:521\n    #32 0x5a6a7815e93c in _PyRun_AnyFileObject Python/pythonrun.c:81\n    #33 0x5a6a781d1e3c in pymain_run_file_obj Modules/main.c:410\n    #34 0x5a6a781d1e3c in pymain_run_file Modules/main.c:429\n    #35 0x5a6a781d1e3c in pymain_run_python Modules/main.c:691\n    #36 0x5a6a781d371e in Py_RunMain Modules/main.c:772\n    #37 0x5a6a781d371e in pymain_main Modules/main.c:802\n    #38 0x5a6a781d371e in Py_BytesMain Modules/main.c:826\n    #39 0x7800fd62a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n    #40 0x7800fd62a28a in __libc_start_main_impl ../csu/libc-start.c:360\n    #41 0x5a6a77b6d634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)\n\npreviously allocated by thread T0 here:\n    #0 0x7800fdafd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69\n    #1 0x5a6a77e3a88e in _PyObject_MallocWithType Include/internal/pycore_object_alloc.h:46\n    #2 0x5a6a77e3a88e in _PyType_AllocNoTrack Objects/typeobject.c:2504\n    #3 0x5a6a77e3aaf4 in PyType_GenericAlloc Objects/typeobject.c:2535\n    #4 0x5a6a77e32118 in type_call Objects/typeobject.c:2448\n    #5 0x5a6a77c939cd in _PyObject_MakeTpCall Objects/call.c:242\n    #6 0x5a6a77b51f33 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620\n    #7 0x5a6a77ce9bc4 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #8 0x5a6a77ce9bc4 in gen_send_ex2 Objects/genobject.c:259\n    #9 0x5a6a77ce9bc4 in gen_send_ex Objects/genobject.c:301\n    #10 0x5a6a77ce9bc4 in gen_send Objects/genobject.c:324\n    #11 0x5a6a77c9572d in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #12 0x5a6a77c9572d in PyObject_CallOneArg Objects/call.c:395\n    #13 0x5a6a782cb718 in groupby_step Modules/itertoolsmodule.c:519\n    #14 0x5a6a782cb718 in groupby_next Modules/itertoolsmodule.c:556\n    #15 0x5a6a77ff5d8a in builtin_next Python/bltinmodule.c:1681\n    #16 0x5a6a77c953e7 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #17 0x5a6a77c953e7 in PyObject_Vectorcall Objects/call.c:327\n    #18 0x5a6a77b495a2 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1620\n    #19 0x5a6a78013ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #20 0x5a6a78013ad6 in _PyEval_Vector Python/ceval.c:2001\n    #21 0x5a6a78013ad6 in PyEval_EvalCode Python/ceval.c:884\n    #22 0x5a6a7815916e in run_eval_code_obj Python/pythonrun.c:1365\n    #23 0x5a6a7815916e in run_mod Python/pythonrun.c:1459\n    #24 0x5a6a7815de17 in pyrun_file Python/pythonrun.c:1293\n    #25 0x5a6a7815de17 in _PyRun_SimpleFileObject Python/pythonrun.c:521\n    #26 0x5a6a7815e93c in _PyRun_AnyFileObject Python/pythonrun.c:81\n    #27 0x5a6a781d1e3c in pymain_run_file_obj Modules/main.c:410\n    #28 0x5a6a781d1e3c in pymain_run_file Modules/main.c:429\n    #29 0x5a6a781d1e3c in pymain_run_python Modules/main.c:691\n    #30 0x5a6a781d371e in Py_RunMain Modules/main.c:772\n    #31 0x5a6a781d371e in pymain_main Modules/main.c:802\n    #32 0x5a6a781d371e in Py_BytesMain Modules/main.c:826\n    #33 0x7800fd62a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n    #34 0x7800fd62a28a in __libc_start_main_impl ../csu/libc-start.c:360\n    #35 0x5a6a77b6d634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)\n\nSUMMARY: AddressSanitizer: heap-use-after-free Include/refcount.h:127 in _Py_IsImmortal\nShadow bytes around the buggy address:\n  0x51300001d100: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa\n  0x51300001d180: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00\n  0x51300001d200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x51300001d280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x51300001d300: 00 00 00 00 00 04 fa fa fa fa fa fa fa fa fa fa\n=\u003e0x51300001d380: fd fd fd fd[fd]fd fd fd fd fd fd fd fd fd fd fd\n  0x51300001d400: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd\n  0x51300001d480: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa\n  0x51300001d500: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00\n  0x51300001d580: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x51300001d600: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\nShadow byte legend (one shadow byte represents 8 application bytes):\n  Addressable:           00\n  Partially addressable: 01 02 03 04 05 06 07 \n  Heap left redzone:       fa\n  Freed heap region:       fd\n  Stack left redzone:      f1\n  Stack mid redzone:       f2\n  Stack right redzone:     f3\n  Stack after return:      f5\n  Stack use after scope:   f8\n  Global redzone:          f9\n  Global init order:       f6\n  Poisoned by user:        f7\n  Container overflow:      fc\n  Array cookie:            ac\n  Intra object redzone:    bb\n  ASan internal:           fe\n  Left alloca redzone:     ca\n  Right alloca redzone:    cb\n==252399==ABORTING\n```\n\u003c/details\u003e\n\n### CPython versions tested on:\n\n\u003cdetails\u003e\n\n| Python Version | Status | Exit Code |\n|---|---|---|\n| `Python 3.9.24+ (heads/3.9:111bbc15b26, Oct 28 2025, 16:51:20) ` | ASAN | 1 |\n| `Python 3.10.19+ (heads/3.10:014261980b1, Oct 28 2025, 16:52:08) [Clang 18.1.3 (1ubuntu1)]` | ASAN | 1 |\n| `Python 3.11.14+ (heads/3.11:88f3f5b5f11, Oct 28 2025, 16:53:08) [Clang 18.1.3 (1ubuntu1)]` | ASAN | 1 |\n| `Python 3.12.12+ (heads/3.12:8cb2092bd8c, Oct 28 2025, 16:54:14) [Clang 18.1.3 (1ubuntu1)]` | ASAN | 1 |\n| `Python 3.13.9+ (heads/3.13:9c8eade20c6, Oct 28 2025, 16:55:18) [Clang 18.1.3 (1ubuntu1)]` | ASAN | 1 |\n| `Python 3.14.0+ (heads/3.14:2e216728038, Oct 28 2025, 16:56:16) [Clang 18.1.3 (1ubuntu1)]` | ASAN | 1 |\n| `Python 3.15.0a1+ (heads/main:f5394c257ce, Oct 28 2025, 19:29:54) [GCC 13.3.0]` | ASAN | 1 |\n\n\u003c/details\u003e\n\n### Operating systems tested on:\n\nLinux\n\n### Output from running 'python -VV' on the command line:\n\nPython 3.15.0a1+ (heads/main:f5394c257ce, Oct 28 2025, 19:29:54) [GCC 13.3.0]\n\n\n\n\u003c!-- gh-linked-prs --\u003e\n### Linked PRs\n* gh-143738\n* gh-144626\n* gh-144627\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/jackfromeast","@type":"Person","name":"jackfromeast"},"datePublished":"2026-01-08T05:56:27.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":2},"url":"https://github.com/143543/cpython/issues/143543"}