google-deepmind / google-deepmind/tree

Free-threaded (no-GIL) use-after-free: borrowed dict key from PyDict_Next used across __hash__/__eq__ in assert_same_structure

Open
#143 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
1k
Forks
73
PR merge metrics
No merged PRs in 30d

Description

On a free-threaded build (`3.14t`), `tree.assert_same_structure` can dereference a freed `PyObject*` when the compared structures are dicts that another thread mutates concurrently. It reproduces as SIGSEGV / SIGTRAP; under the GIL it is clean.

### Site

`tree/tree.cc:552` on current `master`:

```c
while (PyDict_Next(o1, &pos, &key, nullptr)) { // key is a borrowed reference
if (PyDict_GetItem(o2, key) == nullptr) { // runs key.__hash__ / __eq__
```

`o1` and `o2` are the two caller-supplied structures. `key` is borrowed from `o1`, and `PyDict_GetItem(o2, key)` calls `key`'s `__hash__` and `__eq__`. If those are Python (e.g. a `str` subclass), the lookup leaves C while holding the borrowed `key`. Another thread mutating `o1` at that moment can drop `key`'s last reference and free it. Two documented hazards stack: `PyDict_Next` is itself unsafe against concurrent mutation, and the key it returns is borrowed.

The same borrowed-`PyDict_GetItem` shape is at `tree.cc:283` (with a comment already noting the borrow); I have not exercised that path.

### Exposure

dm-tree is built with pybind11, which declares the module `Py_MOD_GIL_NOT_USED` by default on a free-threaded build. So on a stock free-threaded interpreter `import tree` leaves the GIL **disabled** - no `PYTHON_GIL=0` override is needed to reach this - while the module has not been made free-threading-safe.

### Measured

`python3.14.0rc1t`, 8 comparer threads calling `assert_same_structure(a, b)` while 3 mutator threads replace keys in `a`; keys are a `str` subclass so `__hash__` is real Python. 4000 rounds, 10 runs per arm:

| arm | result |
|---|---|
| free-threaded | **10/10 crash** (SIGSEGV 4, SIGTRAP 6) |
| control - no mutator thread | clean 10/10 |
| control - mutator touches a decoy dict, not the compared one | clean 10/10 |
| same script, GIL build (3.14) | clean 10/10 |

Both controls matter: without the first, concurrent comparison alone could be blamed; without the second, generic thread pressure could be.

Reproducer (ft_dmtree.py)

```python
"""dm-tree `tree.cc:552` — borrowed key from PyDict_Next used across arbitrary Python.

while (PyDict_Next(o1, &pos, &key, nullptr)) { /* key is borrowed */
if (PyDict_GetItem(o2, key) == nullptr) { /* runs __hash__/__eq__ */

`o1` and `o2` are the two structures the caller passed to
`tree.assert_same_structure`. Under Py_GIL_DISABLED another thread mutating `o1`
can free the borrowed `key` while the lookup in `o2` is running user code.

Two hazards stacked: PyDict_Next itself is documented as unsafe against
concurrent mutation, and the key it hands back is borrowed.

Keys here are a str subclass whose __hash__ is real Python, so the lookup in `o2`
genuinely leaves C.
"""
import gc
import sys
import threading

import tree

N_CMP, N_MUT, ROUNDS, SIZE = 8, 3, 4000, 32

class Key(str):
"""A str subclass: __hash__ goes through Python, so PyDict_GetItem leaves C."""
__slots__ = ()

def __hash__(self):
return str.__hash__(self)

def main():
print(f"py={sys.version.split()[0]}{sys.abiflags} "
f"gil={getattr(sys, '_is_gil_enabled', lambda: True)()}", flush=True)
a = {Key(f"k{i}"): i for i in range(SIZE)}
b = {Key(f"k{i}"): i for i in range(SIZE)}
stop = threading.Event()
barrier = threading.Barrier(N_CMP + N_MUT + 1)
done = [0] * N_CMP

def comparer(t):
barrier.wait()
n = 0
for _ in range(ROUNDS):
try:
tree.assert_same_structure(a, b)
except Exception:
pass
n += 1
done[t] = n

def mutator():
barrier.wait()
i = 0
while not stop.is_set():
k = Key(f"k{i % SIZE}")
a[k] = i # replace: the old Key object loses its last ref
i += 1

cs = [threading.Thread(target=comparer, args=(t,)) for t in range(N_CMP)]
ms = [threading.Thread(target=mutator) for _ in range(N_MUT)]
gc.disable()
for t in cs + ms:
t.start()
barrier.wait()
for t in cs:
t.join()
stop.set()
for t in ms:
t.join()
gc.enable()
print(f"clean: {sum(done)} comparisons", flush=True)
return 0

if __name__ == "__main__":
raise SystemExit(main())
```

The two controls are one-line variants: control A removes the mutator threads; control B points the mutators at a separate decoy dict instead of `a`.

### A possible fix

Matching what CPython added for exactly this: take a strong reference to the key for the duration of the lookup - `PyDict_GetItemRef` / `Py_NewRef(key)` around the `PyDict_GetItem`, or wrap the walk in a critical section on `o1`.

### Not claimed

No severity - whether an application shares a structure across threads while calling `assert_same_structure` is application-specific. No exploitability - the observed faults are consistent with the mechanism and I did not build a primitive.

Contributor guide

Open the contributing guide

Research direction

Start at tree/tree.cc:552 and inspect the related borrowed PyDict_GetItem path at tree.cc:283, then run the supplied ft_dmtree.py reproducer on a free-threaded build. Compare the relevant Python C API reference and concurrency guarantees before choosing the ownership or synchronization approach. Done means the free-threaded stress case remains clean and regression coverage exercises the affected path.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, python
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.