Heap buffer overflow in `set_clear_internal` via re-entrant `__eq__` during `set_iand`

[jackfromeast]

What happened?

In-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.

Proof of Concept:

import random
random.seed(0)
aux = {object()}
targets = []

class Victim:
    def __hash__(self):
        return 0
    def __eq__(self, other):
        return NotImplemented

class Trigger:
    def __hash__(self):
        return 0
    def __eq__(self, other):
        if not targets:
            return False
        for s in targets:
            op = random.randrange(7)
            if op == 0:
                s.clear()
            elif op == 1:
                s.add(Victim())
            elif op == 2:
                s.discard(Victim())
            else:
                s ^= aux
        return False

for _ in range(119):
    left = {Victim() for _ in range(6)}
    right = {Victim() for _ in range(6)}
    for _ in range(3):
        right.add(Trigger())
    targets[:] = [left, right]
    left &= right

Vulnerable Code Snippet:

Click to expand

/* Buggy Re-entrant Path */
PyObject *
PyNumber_InPlaceAnd(PyObject *v, PyObject *w)
{
    return binary_iop(v, w, NB_SLOT(nb_inplace_and), NB_SLOT(nb_and), "&=");
}

static PyObject *
binary_iop1(PyObject *v, PyObject *w, const int iop_slot, const int op_slot,
            const char *op_name)
{
    PyNumberMethods *mv = Py_TYPE(v)->tp_as_number;
    if (mv != NULL) {
        binaryfunc slot = NB_BINOP(mv, iop_slot);
        if (slot) {
            return slot(v, w);  /* for sets: set_iand() */
        }
    }
    return NULL;
}

static PyObject *
set_iand(PyObject *self, PyObject *other)
{
    PySetObject *so = _PySet_CAST(self);
    /* ... */
    return set_intersection_update(so, other);
}

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{
    /* ... */
    Py_INCREF(startkey);
    cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);  /* Reentrant call site */
    /* user __eq__ can call set.clear()/add()/discard()/^= on the same sets mid-probe */
    Py_DECREF(startkey);
    if (table != so->table || entry->key != startkey)
        return set_lookkey(so, key, hash);
    /* ... */
}

static int
set_clear_internal(PyObject *self)
{
    PySetObject *so = _PySet_CAST(self);
    setentry *entry;
    setentry *table = so->table;  /* crashing pointer derived */
    Py_ssize_t used = so->used;

    /* ... */
    for (entry = table; used > 0; entry++) {
        if (entry->key && entry->key != dummy) {  /* Crash site */
            used--;
            Py_DECREF(entry->key);
        }
    }
    /* ... */
    return 0;
}

/* Clobbering Path */
static int
set_add_entry_takeref(PySetObject *so, PyObject *key, Py_hash_t hash)
{
    /* ... */
    if ((size_t)so->fill*5 < mask*3)
        return 0;
    return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

static int
set_table_resize(PySetObject *so, Py_ssize_t minused)
{
    setentry *oldtable = so->table;
    /* ... */
    so->table = newtable;
    /* ... */
    if (is_oldtable_malloced)
        PyMem_Free(oldtable);  /* state mutate site */
    return 0;
}

Sanitizer Output:

Click to expand

=================================================================
==409942==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x51500022fb00 at pc 0x62534c9e1c4e bp 0x7ffe14bf1260 sp 0x7ffe14bf1250
READ of size 8 at 0x51500022fb00 thread T0
    #0 0x62534c9e1c4d in set_clear_internal Objects/setobject.c:492
    #1 0x62534c9e1cdc in set_clear_impl Objects/setobject.c:1336
    #2 0x62534c9e1cdc in set_clear Objects/clinic/setobject.c.h:126
    #3 0x62534c721c93 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:3813
    #4 0x62534cbf12a5 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #5 0x62534cbf12a5 in _PyEval_Vector Python/ceval.c:2001
    #6 0x62534ca245e2 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #7 0x62534ca245e2 in vectorcall_unbound Objects/typeobject.c:3033
    #8 0x62534ca245e2 in maybe_call_special_one_arg Objects/typeobject.c:3175
    #9 0x62534ca245e2 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190
    #10 0x62534ca245e2 in slot_tp_richcompare Objects/typeobject.c:10729
    #11 0x62534c9962af in do_richcompare Objects/object.c:1059
    #12 0x62534c9962af in PyObject_RichCompare Objects/object.c:1108
    #13 0x62534c9962af in PyObject_RichCompareBool Objects/object.c:1130
    #14 0x62534c9e200c in set_lookkey Objects/setobject.c:114
    #15 0x62534c9ec96d in set_discard_entry Objects/setobject.c:396
    #16 0x62534c9ec96d in set_discard_key Objects/setobject.c:439
    #17 0x62534c9ec96d in set_discard_impl Objects/setobject.c:2370
    #18 0x62534c9ec96d in set_discard Objects/clinic/setobject.c.h:504
    #19 0x62534c713caf in _PyEval_EvalFrameDefault Python/generated_cases.c.h:3907
    #20 0x62534cbf12a5 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #21 0x62534cbf12a5 in _PyEval_Vector Python/ceval.c:2001
    #22 0x62534ca245e2 in _PyObject_VectorcallTstate Include/internal/pycore_call.h:169
    #23 0x62534ca245e2 in vectorcall_unbound Objects/typeobject.c:3033
    #24 0x62534ca245e2 in maybe_call_special_one_arg Objects/typeobject.c:3175
    #25 0x62534ca245e2 in _PyObject_MaybeCallSpecialOneArg Objects/typeobject.c:3190
    #26 0x62534ca245e2 in slot_tp_richcompare Objects/typeobject.c:10729
    #27 0x62534c9962af in do_richcompare Objects/object.c:1059
    #28 0x62534c9962af in PyObject_RichCompare Objects/object.c:1108
    #29 0x62534c9962af in PyObject_RichCompareBool Objects/object.c:1130
    #30 0x62534c9e200c in set_lookkey Objects/setobject.c:114
    #31 0x62534c9e6726 in set_contains_entry Objects/setobject.c:381
    #32 0x62534c9e6726 in set_intersection Objects/setobject.c:1437
    #33 0x62534c9e744a in set_intersection_update Objects/setobject.c:1531
    #34 0x62534c9e744a in set_iand Objects/setobject.c:1589
    #35 0x62534c819c45 in binary_iop1 Objects/abstract.c:1230
    #36 0x62534c819c45 in binary_iop Objects/abstract.c:1255
    #37 0x62534c819c45 in PyNumber_InPlaceAnd Objects/abstract.c:1289
    #38 0x62534c727072 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:62
    #39 0x62534cbf0ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #40 0x62534cbf0ad6 in _PyEval_Vector Python/ceval.c:2001
    #41 0x62534cbf0ad6 in PyEval_EvalCode Python/ceval.c:884
    #42 0x62534cd3616e in run_eval_code_obj Python/pythonrun.c:1365
    #43 0x62534cd3616e in run_mod Python/pythonrun.c:1459
    #44 0x62534cd3ae17 in pyrun_file Python/pythonrun.c:1293
    #45 0x62534cd3ae17 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #46 0x62534cd3b93c in _PyRun_AnyFileObject Python/pythonrun.c:81
    #47 0x62534cdaee3c in pymain_run_file_obj Modules/main.c:410
    #48 0x62534cdaee3c in pymain_run_file Modules/main.c:429
    #49 0x62534cdaee3c in pymain_run_python Modules/main.c:691
    #50 0x62534cdb071e in Py_RunMain Modules/main.c:772
    #51 0x62534cdb071e in pymain_main Modules/main.c:802
    #52 0x62534cdb071e in Py_BytesMain Modules/main.c:826
    #53 0x7e8d41c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #54 0x7e8d41c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #55 0x62534c74a634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)

0x51500022fb00 is located 0 bytes after 512-byte region [0x51500022f900,0x51500022fb00)
allocated by thread T0 here:
    #0 0x7e8d420fd9c7 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x62534c9e2d9b in set_table_resize Objects/setobject.c:340
    #2 0x62534c724038 in _PyEval_EvalFrameDefault Python/generated_cases.c.h:10647
    #3 0x62534cbf0ad6 in _PyEval_EvalFrame Include/internal/pycore_ceval.h:121
    #4 0x62534cbf0ad6 in _PyEval_Vector Python/ceval.c:2001
    #5 0x62534cbf0ad6 in PyEval_EvalCode Python/ceval.c:884
    #6 0x62534cd3616e in run_eval_code_obj Python/pythonrun.c:1365
    #7 0x62534cd3616e in run_mod Python/pythonrun.c:1459
    #8 0x62534cd3ae17 in pyrun_file Python/pythonrun.c:1293
    #9 0x62534cd3ae17 in _PyRun_SimpleFileObject Python/pythonrun.c:521
    #10 0x62534cd3b93c in _PyRun_AnyFileObject Python/pythonrun.c:81
    #11 0x62534cdaee3c in pymain_run_file_obj Modules/main.c:410
    #12 0x62534cdaee3c in pymain_run_file Modules/main.c:429
    #13 0x62534cdaee3c in pymain_run_python Modules/main.c:691
    #14 0x62534cdb071e in Py_RunMain Modules/main.c:772
    #15 0x62534cdb071e in pymain_main Modules/main.c:802
    #16 0x62534cdb071e in Py_BytesMain Modules/main.c:826
    #17 0x7e8d41c2a1c9 in __libc_start_call_main ../sysdeps/nptl/libc_start_call_main.h:58
    #18 0x7e8d41c2a28a in __libc_start_main_impl ../csu/libc-start.c:360
    #19 0x62534c74a634 in _start (/home/jackfromeast/Desktop/entropy/targets/grammar-afl++-latest/targets/cpython/python+0x206634) (BuildId: 4d105290d0ad566a4d6f4f7b2f05fbc9e317b533)

SUMMARY: AddressSanitizer: heap-buffer-overflow Objects/setobject.c:492 in set_clear_internal
Shadow bytes around the buggy address:
  0x51500022f880: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x51500022f900: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x51500022f980: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x51500022fa00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x51500022fa80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x51500022fb00:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x51500022fb80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x51500022fc00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x51500022fc80: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x51500022fd00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x51500022fd80: 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
==409942==ABORTING

CPython versions tested on:

Details

Python Version	Status	Exit Code
Python 3.9.24+ (heads/3.9:111bbc15b26, Oct 28 2025, 16:51:20)	OK	0
Python 3.10.19+ (heads/3.10:014261980b1, Oct 28 2025, 16:52:08) [Clang 18.1.3 (1ubuntu1)]	OK	0
Python 3.11.14+ (heads/3.11:88f3f5b5f11, Oct 28 2025, 16:53:08) [Clang 18.1.3 (1ubuntu1)]	OK	0
Python 3.12.12+ (heads/3.12:8cb2092bd8c, Oct 28 2025, 16:54:14) [Clang 18.1.3 (1ubuntu1)]	ASAN	1
Python 3.13.9+ (heads/3.13:9c8eade20c6, Oct 28 2025, 16:55:18) [Clang 18.1.3 (1ubuntu1)]	OK	0
Python 3.14.0+ (heads/3.14:2e216728038, Oct 28 2025, 16:56:16) [Clang 18.1.3 (1ubuntu1)]	ASAN	1
Python 3.15.0a1+ (heads/main:f5394c257ce, Oct 28 2025, 19:29:54) [GCC 13.3.0]	ASAN	1

Operating systems tested on:

Linux

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

Python 3.15.0a1+ (heads/main:f5394c257ce, Oct 28 2025, 19:29:54) [GCC 13.3.0]

Linked PRs

• gh-143546: Fix heap buffer overflow in set_clear_internal #143628

[aviralgarg05]

I would like to solve this issue, please assign me this issue

[sobolevn]

@aviralgarg05 you don't need to be assigned :)
Just send a PR. Thank you!

[serhiy-storchaka]

#143815 may also fix this issue. At least the reproducer no longer reproduces a bug. But it have nothing to do with set_clear_internal, so there may be different bug. The code in main differs from the code cited in the original report, we have to check all maintained versions.

[serhiy-storchaka]

Sorry, ran with wrong Python. Still cannot reproduce, investigating.