René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Heap buffer overflow in `set_clear_internal` via re-entrant `__eq__` during `set_iand`","articleBody":"### What happened?\n\nIn-place set intersection calls `set_lookkey`, which invokes `PyObject_RichCompareBool` on set elements. A crafted `__eq__` mutates the same sets (including `clear`, `update`, and `^=`) while the interpreter still holds pointers into their tables, re-entering set operations mid-probe. The re-entrant clear runs `set_clear_internal` on a table whose `used` count and storage no longer match, so its cleanup loop walks past the freed/shrunk buffer and triggers a heap buffer overflow.\n\n**Proof of Concept:**\n\n```python\nimport random\nrandom.seed(0)\naux = {object()}\ntargets = []\n\nclass Victim:\n    def __hash__(self):\n        return 0\n    def __eq__(self, other):\n        return NotImplemented\n\nclass Trigger:\n    def __hash__(self):\n        return 0\n    def __eq__(self, other):\n        if not targets:\n            return False\n        for s in targets:\n            op = random.randrange(7)\n            if op == 0:\n                s.clear()\n            elif op == 1:\n                s.add(Victim())\n            elif op == 2:\n                s.discard(Victim())\n            else:\n                s ^= aux\n        return False\n\nfor _ in range(119):\n    left = {Victim() for _ in range(6)}\n    right = {Victim() for _ in range(6)}\n    for _ in range(3):\n        right.add(Trigger())\n    targets[:] = [left, right]\n    left \u0026= right\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 */\nPyObject *\nPyNumber_InPlaceAnd(PyObject *v, PyObject *w)\n{\n    return binary_iop(v, w, NB_SLOT(nb_inplace_and), NB_SLOT(nb_and), \"\u0026=\");\n}\n\nstatic PyObject *\nbinary_iop1(PyObject *v, PyObject *w, const int iop_slot, const int op_slot,\n            const char *op_name)\n{\n    PyNumberMethods *mv = Py_TYPE(v)-\u003etp_as_number;\n    if (mv != NULL) {\n        binaryfunc slot = NB_BINOP(mv, iop_slot);\n        if (slot) {\n            return slot(v, w);  /* for sets: set_iand() */\n        }\n    }\n    return NULL;\n}\n\nstatic PyObject *\nset_iand(PyObject *self, PyObject *other)\n{\n    PySetObject *so = _PySet_CAST(self);\n    /* ... */\n    return set_intersection_update(so, other);\n}\n\nstatic setentry *\nset_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)\n{\n    /* ... */\n    Py_INCREF(startkey);\n    cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);  /* Reentrant call site */\n    /* user __eq__ can call set.clear()/add()/discard()/^= on the same sets mid-probe */\n    Py_DECREF(startkey);\n    if (table != so-\u003etable || entry-\u003ekey != startkey)\n        return set_lookkey(so, key, hash);\n    /* ... */\n}\n\nstatic int\nset_clear_internal(PyObject *self)\n{\n    PySetObject *so = _PySet_CAST(self);\n    setentry *entry;\n    setentry *table = so-\u003etable;  /* crashing pointer derived */\n    Py_ssize_t used = so-\u003eused;\n\n    /* ... */\n    for (entry = table; used \u003e 0; entry++) {\n        if (entry-\u003ekey \u0026\u0026 entry-\u003ekey != dummy) {  /* Crash site */\n            used--;\n            Py_DECREF(entry-\u003ekey);\n        }\n    }\n    /* ... */\n    return 0;\n}\n\n/* Clobbering Path */\nstatic int\nset_add_entry_takeref(PySetObject *so, PyObject *key, Py_hash_t hash)\n{\n    /* ... */\n    if ((size_t)so-\u003efill*5 \u003c mask*3)\n        return 0;\n    return set_table_resize(so, so-\u003eused\u003e50000 ? so-\u003eused*2 : so-\u003eused*4);\n}\n\nstatic int\nset_table_resize(PySetObject *so, Py_ssize_t minused)\n{\n    setentry *oldtable = so-\u003etable;\n    /* ... */\n    so-\u003etable = newtable;\n    /* ... */\n    if (is_oldtable_malloced)\n        PyMem_Free(oldtable);  /* state mutate site */\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==409942==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x51500022fb00 at pc 0x62534c9e1c4e bp 0x7ffe14bf1260 sp 0x7ffe14bf1250\nREAD of size 8 at 0x51500022fb00 thread T0\n    #0 0x62534c9e1c4d in set_clear_internal Objects/setobject.c:492\n    #1 0x62534c9e1cdc in set_clear_impl Objects/setobject.c:1336\n    #2 0x62534c9e1cdc in set_clear Objects/clinic/setobject.c.h:126\n    #3 0x62534c721c93 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:3813\n    #4 0x62534cbf12a5 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #5 0x62534cbf12a5 in _PyEval_Vector Python/ceval.c:2001\n    #6 0x62534ca245e2 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #7 0x62534ca245e2 in vectorcall_unbound Objects/typeobject.c:3033\n    #8 0x62534ca245e2 in maybe_call_special_one_arg Objects/typeobject.c:3175\n    #9 0x62534ca245e2 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190\n    #10 0x62534ca245e2 in slot_tp_richcompare Objects/typeobject.c:10729\n    #11 0x62534c9962af in do_richcompare Objects/object.c:1059\n    #12 0x62534c9962af in PyObject_RichCompare Objects/object.c:1108\n    #13 0x62534c9962af in PyObject_RichCompareBool Objects/object.c:1130\n    #14 0x62534c9e200c in set_lookkey Objects/setobject.c:114\n    #15 0x62534c9ec96d in set_discard_entry Objects/setobject.c:396\n    #16 0x62534c9ec96d in set_discard_key Objects/setobject.c:439\n    #17 0x62534c9ec96d in set_discard_impl Objects/setobject.c:2370\n    #18 0x62534c9ec96d in set_discard Objects/clinic/setobject.c.h:504\n    #19 0x62534c713caf in _PyEval_EvalFrameDefault Python/generated_cases.c.h:3907\n    #20 0x62534cbf12a5 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #21 0x62534cbf12a5 in _PyEval_Vector Python/ceval.c:2001\n    #22 0x62534ca245e2 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169\n    #23 0x62534ca245e2 in vectorcall_unbound Objects/typeobject.c:3033\n    #24 0x62534ca245e2 in maybe_call_special_one_arg Objects/typeobject.c:3175\n    #25 0x62534ca245e2 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190\n    #26 0x62534ca245e2 in slot_tp_richcompare Objects/typeobject.c:10729\n    #27 0x62534c9962af in do_richcompare Objects/object.c:1059\n    #28 0x62534c9962af in PyObject_RichCompare Objects/object.c:1108\n    #29 0x62534c9962af in PyObject_RichCompareBool Objects/object.c:1130\n    #30 0x62534c9e200c in set_lookkey Objects/setobject.c:114\n    #31 0x62534c9e6726 in set_contains_entry Objects/setobject.c:381\n    #32 0x62534c9e6726 in set_intersection Objects/setobject.c:1437\n    #33 0x62534c9e744a in set_intersection_update Objects/setobject.c:1531\n    #34 0x62534c9e744a in set_iand Objects/setobject.c:1589\n    #35 0x62534c819c45 in binary_iop1 Objects/abstract.c:1230\n    #36 0x62534c819c45 in binary_iop Objects/abstract.c:1255\n    #37 0x62534c819c45 in PyNumber_InPlaceAnd Objects/abstract.c:1289\n    #38 0x62534c727072 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:62\n    #39 0x62534cbf0ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #40 0x62534cbf0ad6 in _PyEval_Vector Python/ceval.c:2001\n    #41 0x62534cbf0ad6 in PyEval_EvalCode Python/ceval.c:884\n    #42 0x62534cd3616e in run_eval_code_obj Python/pythonrun.c:1365\n    #43 0x62534cd3616e in run_mod Python/pythonrun.c:1459\n    #44 0x62534cd3ae17 in pyrun_file Python/pythonrun.c:1293\n    #45 0x62534cd3ae17 in _PyRun_SimpleFileObject Python/pythonrun.c:521\n    #46 0x62534cd3b93c in _PyRun_AnyFileObject Python/pythonrun.c:81\n    #47 0x62534cdaee3c in pymain_run_file_obj Modules/main.c:410\n    #48 0x62534cdaee3c in pymain_run_file Modules/main.c:429\n    #49 0x62534cdaee3c in pymain_run_python Modules/main.c:691\n    #50 0x62534cdb071e in Py_RunMain Modules/main.c:772\n    #51 0x62534cdb071e in pymain_main Modules/main.c:802\n    #52 0x62534cdb071e in Py_BytesMain Modules/main.c:826\n    #53 0x7e8d41c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n    #54 0x7e8d41c2a28a in __libc_start_main_impl ../csu/libc-start.c:360\n    #55 0x62534c74a634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)\n\n0x51500022fb00 is located 0 bytes after 512-byte region [0x51500022f900,0x51500022fb00)\nallocated by thread T0 here:\n    #0 0x7e8d420fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69\n    #1 0x62534c9e2d9b in set_table_resize Objects/setobject.c:340\n    #2 0x62534c724038 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:10647\n    #3 0x62534cbf0ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121\n    #4 0x62534cbf0ad6 in _PyEval_Vector Python/ceval.c:2001\n    #5 0x62534cbf0ad6 in PyEval_EvalCode Python/ceval.c:884\n    #6 0x62534cd3616e in run_eval_code_obj Python/pythonrun.c:1365\n    #7 0x62534cd3616e in run_mod Python/pythonrun.c:1459\n    #8 0x62534cd3ae17 in pyrun_file Python/pythonrun.c:1293\n    #9 0x62534cd3ae17 in _PyRun_SimpleFileObject Python/pythonrun.c:521\n    #10 0x62534cd3b93c in _PyRun_AnyFileObject Python/pythonrun.c:81\n    #11 0x62534cdaee3c in pymain_run_file_obj Modules/main.c:410\n    #12 0x62534cdaee3c in pymain_run_file Modules/main.c:429\n    #13 0x62534cdaee3c in pymain_run_python Modules/main.c:691\n    #14 0x62534cdb071e in Py_RunMain Modules/main.c:772\n    #15 0x62534cdb071e in pymain_main Modules/main.c:802\n    #16 0x62534cdb071e in Py_BytesMain Modules/main.c:826\n    #17 0x7e8d41c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n    #18 0x7e8d41c2a28a in __libc_start_main_impl ../csu/libc-start.c:360\n    #19 0x62534c74a634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)\n\nSUMMARY: AddressSanitizer: heap-buffer-overflow Objects/setobject.c:492 in set_clear_internal\nShadow bytes around the buggy address:\n  0x51500022f880: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\n  0x51500022f900: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x51500022f980: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x51500022fa00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x51500022fa80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n=\u003e0x51500022fb00:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\n  0x51500022fb80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\n  0x51500022fc00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\n  0x51500022fc80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\n  0x51500022fd00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\n  0x51500022fd80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa\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==409942==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) ` | OK | 0 |\n| `Python 3.10.19+ (heads/3.10:014261980b1, Oct 28 2025, 16:52:08) [Clang 18.1.3 (1ubuntu1)]` | OK | 0 |\n| `Python 3.11.14+ (heads/3.11:88f3f5b5f11, Oct 28 2025, 16:53:08) [Clang 18.1.3 (1ubuntu1)]` | OK | 0 |\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)]` | OK | 0 |\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-143628\n\u003c!-- /gh-linked-prs --\u003e\n","author":{"url":"https://github.com/jackfromeast","@type":"Person","name":"jackfromeast"},"datePublished":"2026-01-08T05:58:02.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":9},"url":"https://github.com/143546/cpython/issues/143546"}