René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"heap overflow in set_dealloc (setobject.c)","articleBody":"# Crash report\n\n### What happened?\nheap overflow by corrupted PySetObject internal data(`used`)\n### Version\nPython 3.13.7 (main, Sep 14 2025, 14:06:10) [GCC 13.3.0]\n\n\n### Root Cause \n\n\n\n1. **CPython PySetObject entry states**: Python sets maintain three types of entries:\n    - active: successfully inserted entries\n    - dummy: entries that were inserted but subsequently deleted\n    - unused(null): uninitialized/empty entries\n\n    https://github.com/python/cpython/blob/3.13/Include/cpython/setobject.h#L7-L9\n\n2. **Hash collision exploitation**: The hash value is used for both table indexing in set_add_entry and entry comparison. Setting hash to 0 causes deterministic traversal starting from index 0, creating intentional hash collisions between entries.\n\n    https://github.com/python/cpython/blob/3.13/Objects/setobject.c#L144\n\n3. **Dummy entry setup**: Two dummy objects that return hash 0 are inserted into the set, then deleted, leaving behind dummy entries.\n\n4. **Recursive eq calls and exception handling**: The __eq__ method is the callback executed when set entries have identical hashes to resolve hash collisions. Adding a corruption object triggers recursive calls that eventually hit Python's maximum recursion depth, causing an error return and raising an exception.\n\n    https://github.com/python/cpython/blob/3.13/Objects/setobject.c#L165\n\n4. **Freeslot handling logic**: When Python set encounters a dummy entry, it stores the location in freeslot. When it subsequently encounters a null entry, it moves to the dummy_or_freeslot location.\n\n    https://github.com/python/cpython/blob/3.13/Objects/setobject.c#L175-L177\n\n    https://github.com/python/cpython/blob/3.13/Objects/setobject.c#L152-L153\n\n5. **Entry overwrite at dummy_or_freeslot**: If an entry's hash matches a dummy's hash, Python writes the key and hash to that dummy entry at the dummy_or_freeslot location.\n\n    https://github.com/python/cpython/blob/3.13/Objects/setobject.c#L185-L191\n\n6. **Exception handling and recursion unwind corruption**: Even though the exception is caught and handled with try-except, as the recursion stack unwinds, each recursive call attempts to complete its add_entry operation. Since freeslot was determined deterministically, all recursive calls reference the same memory address. During the unwind process, each level overwrites the same freeslot location and incorrectly increments used += 1, as the function determines the insertion was successful.\n\n\u003cdetails\u003e\n  \u003csummary\u003e\u003cb\u003erecusively overwrite same freeslot location \u003c/b\u003e\u003c/summary\u003e\n\n```\nBreakpoint 3, set_add_entry (so=so@entry=0x5110001dcd20, key=key@entry=\u003cweakref.ReferenceType at remote 0x50b00015e640\u003e, hash=0) at Objects/setobject.c:191\n191         return 0;\n1: freeslot = (setentry *) 0x5110001dcd60  // same freeslot location\n2: x/2xg freeslot\n0x5110001dcd60: 0x000050b00015e640      0x0000000000000000\n(gdb) py-bt\nTraceback (most recent call first):\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 23, in \u003cmodule\u003e\n    _asyncio._register_task(a[1])\n(gdb) c\nContinuing.\n\nBreakpoint 3, set_add_entry (so=so@entry=0x5110001dcd20, key=key@entry=\u003cweakref.ReferenceType at remote 0x50b00015e590\u003e, hash=0) at Objects/setobject.c:191\n191         return 0;\n1: freeslot = (setentry *) 0x5110001dcd60    // same freeslot location\n2: x/2xg freeslot  \n0x5110001dcd60: 0x000050b00015e590      0x0000000000000000\n(gdb) py-bt // different python stack\nTraceback (most recent call first):\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 23, in \u003cmodule\u003e\n    _asyncio._register_task(a[1])\n(gdb) c\nContinuing.\n\nBreakpoint 3, set_add_entry (so=so@entry=0x5110001dcd20, key=key@entry=\u003cweakref.ReferenceType at remote 0x50b00015e4e0\u003e, hash=0) at Objects/setobject.c:191\n191         return 0;\n1: freeslot = (setentry *) 0x5110001dcd60  // same freeslot location\n2: x/2xg freeslot\n0x5110001dcd60: 0x000050b00015e4e0      0x0000000000000000\n(gdb) py-bt // different python stack\nTraceback (most recent call first):\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 23, in \u003cmodule\u003e\n    _asyncio._register_task(a[1])\n(gdb) c\nContinuing.\n\nBreakpoint 3, set_add_entry (so=so@entry=0x5110001dcd20, key=key@entry=\u003cweakref.ReferenceType at remote 0x50b00015e430\u003e, hash=0) at Objects/setobject.c:191\n191         return 0;\n1: freeslot = (setentry *) 0x5110001dcd60  // same freeslot location\n2: x/2xg freeslot\n0x5110001dcd60: 0x000050b00015e430      0x0000000000000000\n(gdb) py-bt // different python stack\nTraceback (most recent call first):\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 11, in __eq__\n    _asyncio._register_task(self)\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 23, in \u003cmodule\u003e\n    _asyncio._register_task(a[1])\n(gdb) c\nContinuing.\n\nBreakpoint 3, set_add_entry (so=so@entry=0x5110001dcd20, key=key@entry=\u003cweakref.ReferenceType at remote 0x50b00015e380\u003e, hash=0) at Objects/setobject.c:191\n191         return 0;\n1: freeslot = (setentry *) 0x5110001dcd60  // same freeslot location\n2: x/2xg freeslot\n0x5110001dcd60: 0x000050b00015e380      0x0000000000000000\n(gdb) py-bt // different python stack\nTraceback (most recent call first):\n  File \"/home/ubuntu/Python-3.13.7/Lib/_weakrefset.py\", line 88, in add\n    self.data.add(ref(item, self._remove))\n  \u003cbuilt-in method _register_task of module object at remote 0x5080000de5c0\u003e\n  File \"/home/ubuntu/Python-3.13.7/test.py\", line 23, in \u003cmodule\u003e\n    _asyncio._register_task(a[1])\n(gdb) c\n\n```\n\u003c/details\u003e\n\n7. **Entry counter bug**: This results in the set's used counter being incremented multiple times for what is essentially a single memory location, leading to incorrect set size tracking and potential memory corruption.\n\n\u003cdetails\u003e\n        \u003csummary\u003e\u003cb\u003e entry counter(used : 70 ) bug \u003c/b\u003e\u003c/summary\u003e\n\n```\nBreakpoint 4, set_dealloc (so=0x5110001dcd20) at Objects/setobject.c:495\n495     {\n1: *(PySetObject *)so = {ob_base = {{ob_refcnt = 0, ob_refcnt_split = {0, 0}}, ob_type = 0x555556228520 \u003cPySet_Type\u003e}, fill = 2, used = 70 //\u003c-- \n, mask = 7,   table = 0x5110001dcd60, hash = -1, finger = 0, smalltable = {{key = 0x555556228f40 \u003c_dummy_struct\u003e, hash = -1}, {key = 0x555556228f40 \u003c_dummy_struct\u003e,\n      hash = -1}, {key = 0x0, hash = 0}, {key = 0x0, hash = 0}, {key = 0x0, hash = 0}, {key = 0x0, hash = 0}, {key = 0x0, hash = 0}, {key = 0x0,\n      hash = 0}}, weakreflist = 0x0}\n\n(gdb) x/8gx 0x5110001dcd60 \u003c-- PySetObject internal table address\n\n0x5110001dcd60: 0x0000555556228f40      0xffffffffffffffff\n0x5110001dcd70: 0x0000555556228f40      0xffffffffffffffff\n0x5110001dcd80: 0x0000000000000000      0x0000000000000000\n0x5110001dcd90: 0x0000000000000000      0x0000000000000000\n0x5110001dcda0: 0x0000000000000000      0x0000000000000000\n0x5110001dcdb0: 0x0000000000000000      0x0000000000000000\n0x5110001dcdc0: 0x0000000000000000      0x0000000000000000\n0x5110001dcdd0: 0x0000000000000000      0x0000000000000000\n\n```\n\u003c/details\u003e\n\n\n\n8. **Memory corruption during deallocation**: In set_dealloc, the deallocation routine iterates through the table by incrementing addresses sequentially. When it encounters non-dummy entries, it performs cleanup and decrements used--. However, since used is now greater than the actual (fill - dummy) count due to the previous corruption, the deallocation process accesses invalid memory addresses beyond the allocated table bounds, leading to memory corruption or segmentation faults.\n\n    https://github.com/python/cpython/blob/3.13/Objects/setobject.c#L494-L514\n\n### POC\n\n```python\nimport _asyncio\n\nclass dummy(object):\n    def __hash__(self):\n        return 0\nclass CorrupTrigger():\n    def __hash__(self):\n        return 0\n    def __eq__(self,other):\n        try:\n            _asyncio._register_task(self)\n        except:\n            pass\n        return False\na = [dummy(),dummy()]\n_asyncio._register_task(a[0])\n_asyncio._register_task(a[1])\ndel a # make dummy entries in set \nprint (_asyncio._scheduled_tasks)\na = [CorrupTrigger() for i in range(2)]\n_asyncio._register_task(a[0])\n_asyncio._register_task(a[1]) # make recursive comparision\n\n```\n\n\n\n\n\n### ASAN\n\n\u003cdetails\u003e\n  \u003csummary\u003e\u003cb\u003easan\u003c/b\u003e\u003c/summary\u003e\n\n```\n==4613==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x5110001dcdf0 at pc 0x555555a458a5 bp 0x7fffffffdb20 sp 0x7fffffffdb10\nREAD of size 8 at 0x5110001dcdf0 thread T0\n    #0 0x555555a458a4 in set_dealloc Objects/setobject.c:505\n    #1 0x555555a0c1dc in _Py_Dealloc Objects/object.c:2939\n    #2 0x5555559d8d5a in Py_DECREF Include/object.h:934\n    #3 0x5555559d9787 in set_dict_inline_values Objects/dictobject.c:7151\n    #4 0x5555559e55ad in _PyObject_SetManagedDict Objects/dictobject.c:7180\n    #5 0x5555559e5667 in PyObject_ClearManagedDict Objects/dictobject.c:7222\n    #6 0x555555a746da in subtype_dealloc Objects/typeobject.c:2359\n    #7 0x555555a0c1dc in _Py_Dealloc Objects/object.c:2939\n    #8 0x7ffff6ff7dd8 in Py_DECREF Include/object.h:934\n    #9 0x7ffff6ff83a7 in module_clear Modules/_asynciomodule.c:3584\n    #10 0x555555a05030 in module_clear Objects/moduleobject.c:1103\n    #11 0x555555c3a017 in delete_garbage Python/gc.c:1015\n    #12 0x555555c3b4f9 in gc_collect_main Python/gc.c:1421\n    #13 0x555555c3c05f in _PyGC_CollectNoFail Python/gc.c:1657\n    #14 0x555555ca8fdb in finalize_modules Python/pylifecycle.c:1797\n    #15 0x555555cb2079 in _Py_Finalize Python/pylifecycle.c:2134\n    #16 0x555555cb21ad in Py_FinalizeEx Python/pylifecycle.c:2261\n    #17 0x555555d15c05 in Py_RunMain Modules/main.c:777\n    #18 0x555555d15de7 in pymain_main Modules/main.c:805\n    #19 0x555555d1616c in Py_BytesMain Modules/main.c:829\n    #20 0x5555557de445 in main Programs/python.c:15\n    #21 0x7ffff742a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58\n    #22 0x7ffff742a28a in __libc_start_main_impl ../csu/libc-start.c:360\n    #23 0x5555557de374 in _start (/home/ubuntu/Python-3.13.7/python+0x28a374) (BuildId: c1408b7ecd69be204d23a50df1288230bd9ca6bd)\n\n0x5110001dcdf0 is located 0 bytes after 240-byte region [0x5110001dcd00,0x5110001dcdf0)\nallocated by thread T0 here:\n    #0 0x7ffff78fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69\n    #1 0x555555a15097 in _PyMem_RawMalloc Objects/obmalloc.c:62\n    #2 0x555555a14468 in _PyMem_DebugRawAlloc Objects/obmalloc.c:2792\n    #3 0x555555a144d0 in _PyMem_DebugRawMalloc Objects/obmalloc.c:2825\n    #4 0x555555a16a0a in _PyMem_DebugMalloc Objects/obmalloc.c:2982\n    #5 0x555555a3e147 in PyObject_Malloc Objects/obmalloc.c:1400\n    #6 0x555555a6ea6f in _PyObject_MallocWithType Include/internal/pycore_object_alloc.h:46\n    #7 0x555555a6ea6f in _PyType_AllocNoTrack Objects/typeobject.c:2041\n    #8 0x555555a6ebf8 in PyType_GenericAlloc Objects/typeobject.c:2070\n    #9 0x555555a47924 in make_new_set Objects/setobject.c:1086\n    #10 0x555555a4964c in set_vectorcall Objects/setobject.c:2379\n    #11 0x555555bb4e2c in _PyEval_EvalFrameDefault Python/generated_cases.c.h:1123\n    #12 0x555555bdc0ae in _PyEval_EvalFrame Include/internal/pycore_ceval.h:119\n    #13 0x555555bdc28b in _PyEval_Vector Python/ceval.c:1816\n    #14 0x55555595a39b in _PyFunction_Vectorcall Objects/call.c:413\n    #15 0x55555595d4eb in _PyObject_VectorcallDictTstate Objects/call.c:135\n    #16 0x55555595d910 in _PyObject_Call_Prepend Objects/call.c:504\n    #17 0x555555a7debc in slot_tp_init Objects/typeobject.c:9816\n    #18 0x555555a719e0 in type_call Objects/typeobject.c:1997\n    #19 0x55555595a659 in _PyObject_MakeTpCall Objects/call.c:242\n    #20 0x55555595a93a in _PyObject_VectorcallTstate Include/internal/pycore_call.h:166\n    #21 0x55555595a96a in PyObject_CallNoArgs Objects/call.c:106\n    #22 0x7ffff7004bcc in module_init Modules/_asynciomodule.c:3665\n    #23 0x7ffff7004fb8 in module_exec Modules/_asynciomodule.c:3734\n    #24 0x555555a06fa6 in PyModule_ExecDef Objects/moduleobject.c:491\n    #25 0x555555c5d45a in exec_builtin_or_dynamic Python/import.c:815\n    #26 0x555555c5d47d in _imp_exec_dynamic_impl Python/import.c:4770\n    #27 0x555555c5de55 in _imp_exec_dynamic Python/clinic/import.c.h:513\n    #28 0x555555a02aeb in cfunction_vectorcall_O Objects/methodobject.c:511\n    #29 0x55555595db69 in _PyVectorcall_Call Objects/call.c:273\n    #30 0x55555595e1a8 in _PyObject_Call Objects/call.c:348\n\nSUMMARY: AddressSanitizer: heap-buffer-overflow Objects/setobject.c:505 in set_dealloc\nShadow bytes around the buggy address:\n  0x5110001dcb00: fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa fa\n  0x5110001dcb80: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00\n  0x5110001dcc00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x5110001dcc80: 00 00 00 00 00 00 fa fa fa fa fa fa fa fa fa fa\n  0x5110001dcd00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n=\u003e0x5110001dcd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00[fa]fa\n  0x5110001dce00: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00\n  0x5110001dce80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x5110001dcf00: 00 00 00 00 00 00 fa fa fa fa fa fa fa fa fa fa\n  0x5110001dcf80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\n  0x5110001dd000: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 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==4613==ABORTING\n```\n\u003c/details\u003e\n\n\n\n### CPython versions tested on:\n\nCPython main branch\n\n### Operating systems tested on:\n\nLinux\n\n### Output from running 'python -VV' on the command line:\n\nPython 3.13.7 (main, Sep 14 2025, 14:06:10) [GCC 13.3.0]\n","author":{"url":"https://github.com/kcatss","@type":"Person","name":"kcatss"},"datePublished":"2025-09-17T17:24:19.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":10},"url":"https://github.com/139071/cpython/issues/139071"}