Segfault from `repr()` of a corrupted set

[devdanzin]

Crash report

What happened?

It's possible to segfault the interpreter by corrupting a set, then calling repr() on it.

MRE:

tasks = set()

class Dummy(object):
    def __hash__(self):
        return 0

class CorrupTrigger():
    counter = 0
    def __hash__(self):
        return 0
    def __eq__(self,other):
        if self.counter < 1:
            self.counter += 1
            tasks.add(self)
        return False

tasks.add(Dummy())
tasks.add(Dummy())
tasks.pop()
tasks.add(CorrupTrigger())
repr(tasks)

Backtrace:

Program received signal SIGSEGV, Segmentation fault.
0x0000555555b5b1e7 in Py_INCREF (op=0x0) at ./Include/refcount.h:281
281         PY_UINT32_T cur_refcnt = op->ob_refcnt;
(gdb) bt
#0  0x0000555555b5b1e7 in Py_INCREF (op=0x0) at ./Include/refcount.h:281
#1  _Py_NewRef (obj=0x0) at ./Include/refcount.h:529
#2  list_repr_impl (v=0x7c6ff6e72f60) at Objects/listobject.c:598
#3  list_repr (self=0x7c6ff6e72f60) at Objects/listobject.c:638
#4  0x0000555555bea219 in PyObject_Repr (v=v@entry=0x7c6ff6e72f60) at Objects/object.c:779
#5  0x0000555555c3c4b7 in set_repr_lock_held (so=0x7d0ff6eb17a0) at Objects/setobject.c:594
#6  set_repr (self=0x7d0ff6eb17a0) at Objects/setobject.c:622
#7  0x0000555555bea219 in PyObject_Repr (v=0x7d0ff6eb17a0) at Objects/object.c:779
#8  0x0000555555bd9b13 in cfunction_vectorcall_O (func=func@entry=0x7c7ff6e35d40, args=args@entry=0x7bfff5f70208, nargsf=nargsf@entry=9223372036854775809, kwnames=kwnames@entry=0x0)
    at Objects/methodobject.c:536
#9  0x0000555555aba6a0 in _PyObject_VectorcallTstate (tstate=0x555556aebf00 <_PyRuntime+358560>, callable=0x7c7ff6e35d40, args=0x7bfff5f70208, nargsf=9223372036854775809, kwnames=0x0)
    at ./Include/internal/pycore_call.h:169
#10 0x0000555555e8cf61 in _PyEval_EvalFrameDefault (tstate=<optimized out>, frame=<optimized out>, throwflag=<optimized out>) at Python/generated_cases.c.h:1620
#11 0x0000555555e4a67b in _PyEval_EvalFrame (tstate=0x555556aebf00 <_PyRuntime+358560>, frame=0x7e8ff6de5220, throwflag=0) at ./Include/internal/pycore_ceval.h:121

It's also possible to get set_pop_impl into an infinite loop by changing the last code block to:

tasks.add(Dummy())
tasks.add(Dummy())
tasks.pop()
tasks.add(CorrupTrigger())
tasks.pop()
tasks.pop()
tasks.pop()

Found when trying to simplify the MRE in #139071.

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Output from running 'python -VV' on the command line:

Python 3.15.0a2+ (heads/main-dirty:41b9ad5b38e, Nov 20 2025, 11:03:41) [Clang 21.1.2 (2ubuntu6)]

Linked PRs

• gh-141805: avoid increase the set->used twice when the __eq__ trigger another add #142007
• gh-141805: Fix crash after concurrent addition objects with the same hash to set #143815
• [3.14] gh-141805: Fix crash after concurrent addition objects with the same hash to set (GH-143815) #143849
• [3.13] gh-141805: Fix crash after concurrent addition objects with the same hash to set (GH-143815) #143853

[devdanzin]

I guess all sorts of shenanigans are possible with the corrupted set. Here's a heap-buffer-overflow:

tasks = set()

class Dummy(object):
    def __hash__(self):
        return 0

class CorrupTrigger():
    counter = 0
    def __hash__(self):
        return 0
    def __eq__(self,other):
        if self.counter < 1:
            self.counter += 1
            tasks.add(self)
        return False

tasks.add(Dummy())
tasks.add(Dummy())
tasks.pop()
tasks.add(CorrupTrigger())
tasks | set()

ASan output:

=================================================================
==409426==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x786f9beb0d30 at pc 0x5d5c440a00f3 bp 0x7ffd088428d0 sp 0x7ffd088428c8
READ of size 8 at 0x786f9beb0d30 thread T0
    #0 0x5d5c440a00f2 in set_dealloc /home/danzin/projects/jit_cpython/Objects/setobject.c:552:20
    #1 0x5d5c4405b2c3 in _Py_Dealloc /home/danzin/projects/jit_cpython/Objects/object.c:3200:5
    #2 0x5d5c442b452d in Py_DECREF_MORTAL /home/danzin/projects/jit_cpython/./Include/internal/pycore_object.h:450:9
    #3 0x5d5c442b452d in PyStackRef_XCLOSE /home/danzin/projects/jit_cpython/./Include/internal/pycore_stackref.h:849:9
    #4 0x5d5c442b452d in _PyEval_EvalFrameDefault /home/danzin/projects/jit_cpython/Python/generated_cases.c.h:10099:13
    #5 0x5d5c442ae67a in _PyEval_EvalFrame /home/danzin/projects/jit_cpython/./Include/internal/pycore_ceval.h:121:16
    #6 0x5d5c442ae67a in _PyEval_Vector /home/danzin/projects/jit_cpython/Python/ceval.c:2159:12
    #7 0x5d5c442ae094 in PyEval_EvalCode /home/danzin/projects/jit_cpython/Python/ceval.c:995:21
    #8 0x5d5c4461fc2e in run_eval_code_obj /home/danzin/projects/jit_cpython/Python/pythonrun.c:1372:12
    #9 0x5d5c4461edfb in run_mod /home/danzin/projects/jit_cpython/Python/pythonrun.c:1475:19
    #10 0x5d5c446193fc in pyrun_file /home/danzin/projects/jit_cpython/Python/pythonrun.c:1300:15
    #11 0x5d5c44616f92 in _PyRun_SimpleFileObject /home/danzin/projects/jit_cpython/Python/pythonrun.c:521:13
    #12 0x5d5c4461630d in _PyRun_AnyFileObject /home/danzin/projects/jit_cpython/Python/pythonrun.c:81:15
    #13 0x5d5c446910aa in pymain_run_file_obj /home/danzin/projects/jit_cpython/Modules/main.c:410:15
    #14 0x5d5c446910aa in pymain_run_file /home/danzin/projects/jit_cpython/Modules/main.c:429:15
    #15 0x5d5c4468f173 in pymain_run_python /home/danzin/projects/jit_cpython/Modules/main.c:691:21
    #16 0x5d5c4468f173 in Py_RunMain /home/danzin/projects/jit_cpython/Modules/main.c:772:5
    #17 0x5d5c44690076 in pymain_main /home/danzin/projects/jit_cpython/Modules/main.c:802:12
    #18 0x5d5c446901e7 in Py_BytesMain /home/danzin/projects/jit_cpython/Modules/main.c:826:12
    #19 0x7b5f9ca2a574 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #20 0x7b5f9ca2a627 in __libc_start_main csu/../csu/libc-start.c:360:3
    #21 0x5d5c43c734f4 in _start (/home/danzin/projects/jit_cpython/python+0x2bb4f4) (BuildId: 768911764b07158e8e5e5c253a7b8c560417792d)

0x786f9beb0d30 is located 0 bytes after 240-byte region [0x786f9beb0c40,0x786f9beb0d30)
allocated by thread T0 here:
    #0 0x5d5c43d18a98 in malloc (/home/danzin/projects/jit_cpython/python+0x360a98) (BuildId: 768911764b07158e8e5e5c253a7b8c560417792d)
    #1 0x5d5c4408b581 in _PyMem_DebugRawAlloc /home/danzin/projects/jit_cpython/Objects/obmalloc.c:2887:24
    #2 0x5d5c4408b581 in _PyMem_DebugRawMalloc /home/danzin/projects/jit_cpython/Objects/obmalloc.c:2920:12
    #3 0x5d5c4408b581 in _PyMem_DebugMalloc /home/danzin/projects/jit_cpython/Objects/obmalloc.c:3085:12
    #4 0x5d5c440c96eb in _PyObject_MallocWithType /home/danzin/projects/jit_cpython/./Include/internal/pycore_object_alloc.h:46:17
    #5 0x5d5c440c96eb in _PyType_AllocNoTrack /home/danzin/projects/jit_cpython/Objects/typeobject.c:2515:19
    #6 0x5d5c440c9544 in PyType_GenericAlloc /home/danzin/projects/jit_cpython/Objects/typeobject.c:2546:21
    #7 0x5d5c440a7eb2 in make_new_set /home/danzin/projects/jit_cpython/Objects/setobject.c:1143:25
    #8 0x5d5c440a7eb2 in make_new_set_basetype /home/danzin/projects/jit_cpython/Objects/setobject.c:1174:12
    #9 0x5d5c440a7eb2 in set_copy_impl /home/danzin/projects/jit_cpython/Objects/setobject.c:1295:22
    #10 0x5d5c440a60a9 in set_copy /home/danzin/projects/jit_cpython/Objects/clinic/setobject.c.h:78:20
    #11 0x5d5c440a60a9 in set_or /home/danzin/projects/jit_cpython/Objects/setobject.c:1381:29
    #12 0x5d5c43ec6dc7 in binary_op1 /home/danzin/projects/jit_cpython/Objects/abstract.c:966:13
    #13 0x5d5c43ec66d0 in binary_op /home/danzin/projects/jit_cpython/Objects/abstract.c:1005:24
    #14 0x5d5c442e9cc7 in _PyEval_EvalFrameDefault /home/danzin/projects/jit_cpython/Python/generated_cases.c.h:62:35
    #15 0x5d5c442ae67a in _PyEval_EvalFrame /home/danzin/projects/jit_cpython/./Include/internal/pycore_ceval.h:121:16
    #16 0x5d5c442ae67a in _PyEval_Vector /home/danzin/projects/jit_cpython/Python/ceval.c:2159:12
    #17 0x5d5c442ae094 in PyEval_EvalCode /home/danzin/projects/jit_cpython/Python/ceval.c:995:21
    #18 0x5d5c4461fc2e in run_eval_code_obj /home/danzin/projects/jit_cpython/Python/pythonrun.c:1372:12
    #19 0x5d5c4461edfb in run_mod /home/danzin/projects/jit_cpython/Python/pythonrun.c:1475:19
    #20 0x5d5c446193fc in pyrun_file /home/danzin/projects/jit_cpython/Python/pythonrun.c:1300:15
    #21 0x5d5c44616f92 in _PyRun_SimpleFileObject /home/danzin/projects/jit_cpython/Python/pythonrun.c:521:13
    #22 0x5d5c4461630d in _PyRun_AnyFileObject /home/danzin/projects/jit_cpython/Python/pythonrun.c:81:15
    #23 0x5d5c446910aa in pymain_run_file_obj /home/danzin/projects/jit_cpython/Modules/main.c:410:15
    #24 0x5d5c446910aa in pymain_run_file /home/danzin/projects/jit_cpython/Modules/main.c:429:15
    #25 0x5d5c4468f173 in pymain_run_python /home/danzin/projects/jit_cpython/Modules/main.c:691:21
    #26 0x5d5c4468f173 in Py_RunMain /home/danzin/projects/jit_cpython/Modules/main.c:772:5
    #27 0x5d5c44690076 in pymain_main /home/danzin/projects/jit_cpython/Modules/main.c:802:12
    #28 0x5d5c446901e7 in Py_BytesMain /home/danzin/projects/jit_cpython/Modules/main.c:826:12
    #29 0x7b5f9ca2a574 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
    #30 0x7b5f9ca2a627 in __libc_start_main csu/../csu/libc-start.c:360:3
    #31 0x5d5c43c734f4 in _start (/home/danzin/projects/jit_cpython/python+0x2bb4f4) (BuildId: 768911764b07158e8e5e5c253a7b8c560417792d)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/danzin/projects/jit_cpython/Objects/setobject.c:552:20 in set_dealloc
Shadow bytes around the buggy address:
  0x786f9beb0a80: fd fd fd fd fd fa fa fa fa fa fa fa fa fa fa fa
  0x786f9beb0b00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x786f9beb0b80: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fa fa
  0x786f9beb0c00: fa fa fa fa fa fa fa fa 00 00 00 00 00 00 00 00
  0x786f9beb0c80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x786f9beb0d00: 00 00 00 00 00 00[fa]fa fa fa fa fa fa fa fa fa
  0x786f9beb0d80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x786f9beb0e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x786f9beb0e80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x786f9beb0f00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x786f9beb0f80: 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
==409426==ABORTING

[rhettinger]

Confirmed that this crashes on Py3.13 and later but worked fine on Py3.12 and prior.

[yihong0618]

the first segment fault commit 3de0f55

but its not the root cause

the root cause is we count the so->old wrong in the first 3.13

cat ttt.py

{<__main__.CorrupTrigger object at 0x105956900>, <__main__.Dummy object at 0x105a94b90>, <NULL>}
➜  cpython git:(3a130c1786) ✗ cat ttt.py 
tasks = set()

class Dummy(object):
    def __hash__(self):
        return 0

class CorrupTrigger():
    counter = 0
    def __hash__(self):
        return 0
    def __eq__(self,other):
        if self.counter < 1:
            self.counter += 1
            tasks.add(self)
        return False

tasks.add(Dummy())
tasks.add(Dummy())
tasks.pop()
tasks.add(CorrupTrigger())
print(repr(tasks))

the third one is NULL in the good commit

{<__main__.CorrupTrigger object at 0x105956900>, <__main__.Dummy object at 0x105a94b90>, <NULL>} 

but for 3.12

➜ cpython git:(3a130c1) ✗ python3.12 ttt.py
{<main.CorrupTrigger object at 0x1007336e0>, <main.Dummy object at 0x100733680>}

[yihong0618]

this is the source cause the issue commit 3325699

from

➜  cpython git:(v3.12.9) ✗ ./python.exe ttt.py
{<__main__.CorrupTrigger object at 0x105972e70>, <__main__.Dummy object at 0x105972e10>}

to

➜  cpython git:(3325699ffa) ✗ ./python.exe ttt.py
{<__main__.CorrupTrigger object at 0x105987b60>, <__main__.Dummy object at 0x105987c50>, <NULL>}

some dig

```text
+-----------+           +-----------------+       +-----------------+       +------------+
| User Code |           | set.add (Outer) |       | set.add (Inner) |       | Hash Table |
+-----------+           +-----------------+       +-----------------+       +------------+
      |                          |                         |                      |
      | 1. tasks.add(X)          |                         |                      |
      |------------------------->|                         |                      |
      |                          |                         |                      |
      |                          | 2. Find empty slot      |                      |
      |                          |----------------------------------------------->|
      |                          | (Found Slot #5, remembers it's FREE)           |
      |                          |                         |                      |
      | 3. Check equality?       |                         |                      |
      |<-------------------------|                         |                      |
      |                          |                         |                      |
      | 4. __eq__ calls add(X)   |                         |                      |
      |--------------------------------------------------->|                      |
      |                          |                         |                      |
      |                          |                         | 5. Find empty slot   |
      |                          |                         |--------------------->|
      |                          |                         | (Found Slot #5)      |
      |                          |                         |                      |
      |                          |                         | 6. Write X to Slot #5|
      |                          |                         |--------------------->|
      |                          |                         |                      |
      |                          |                         | 7. Count++           |
      |                          |                         | (Count = N+1)        |
      |                          |                         |                      |
      | 8. Return                |                         |                      |
      |<---------------------------------------------------|                      |
      |                          |                         |                      |
      | 9. Return False          |                         |                      |
      |------------------------->|                         |                      |
      |                          |                         |                      |
      |                          | (Resumes. Thinks Slot #5 is still FREE)        |
      |                          |                         |                      |
      |                          | 10. Overwrite Slot #5   |                      |
      |                          |----------------------------------------------->|
      |                          | (Previous X is overwritten)                    |
      |                          |                         |                      |
      |                          | 11. Count++             |                      |
      |                          | (Count = N+2)           |                      |
      |                          |                         |                      |
      v                          v                         v                      v

      RESULT: Count is N+2, but only N+1 items exist.
              Slot #5 was written twice.

[yihong0618]

try to solve with the root cause

this diff can fix the problem but I am not sure the fix is good enough and maybe lower the performance

so left comment here

diff --git a/Objects/setobject.c b/Objects/setobject.c
index 85f4d7d403..f545ea958e 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -175,6 +175,8 @@ set_add_entry_takeref(PySetObject *so, PyObject *key, Py_hash_t hash)
                     goto comparison_error;
                 if (table != so->table || entry->key != startkey)
                     goto restart;
+                if (freeslot != NULL && freeslot->key != dummy)
+                    goto restart;
                 mask = so->mask;
             }
             else if (entry->hash == -1) {

---

update
the latest comment is the real root cause fix!

[kemingy]

By using the GDB, I found that this is caused by the improper handled freeslot in set_add_entry_takeref.

1. tasks.pop() this leave a dummy slot in the 0-index
2. tasks.add(Corrupt()) this found this freeslot, but the logic goes into next iteration, and trigger the __eq__ by PyObject_RichCompareBool
3. __eq__ trigger another tasks.add(self) defined inside the Corrupt
4. the new insert also found the freeslot, goes into the next iteration, then fill the freeslot, increase the so->used, return False to the __eq__
5. the original insert continue, still hold the freeslot, but it's already taken, override the freeslot and increase the so->used (twice for this elem)

[serhiy-storchaka]

Unfortunately, solution in #142007 is not correct. Surprisingly, there was no test for this case. #143781 adds a test which will fail with such change.

The right solution is to check if freeslot still points to a dummy entry before replacing it. #143815 implements this.