FA-90366 / Garbage collector invariants / Open access
Reference counting: old value released before the new value is retained · case 01
Self-assignment or storing a child of the old value frees the object being stored.
ROOT CAUSE
The store releases the overwritten reference before incrementing the new target.
VERIFIED REPAIR
Retain the new target first, then write, then release the old value.
Unsuccessful approach: Special-casing identical references fixes self-assignment but still frees a new target reachable only through the old value.
Case contract
Objects carry a strong count and a weak count. new id k: strong 1 (the creating reference), k null fields. drop id: release one strong reference. store src i dst: retain dst, then write, then release the old value. When the strong count reaches 0 the object is destroyed (recorded in freed, its fields released recursively in field order) and, if no weak references remain, its control block is deallocated too; unweak deallocates a destroyed object's block when the last weak reference goes. upgrade id succeeds (and adds a strong reference) only while the strong count is positive. Touching a deallocated block reports "use-after-free".
Why this case matters
Reference-counting collectors must order retains and releases and separate destruction from deallocation.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(events):
objs = {}
freed = []
dealloc = []
out = []
def release(o):
if o is None:
return
b = objs[o]
b['rc'] -= 1
if b['rc'] == 0:
freed.append(o)
kids, b['fields'] = b['fields'], []
if b['weak'] == 0:
dealloc.append(o)
del objs[o]
for c in kids:
release(c)
try:
for ev in events:
op = ev[0]
if op == 'new':
objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
elif op == 'drop':
release(ev[1])
elif op == 'store':
_, src, field, dst = ev
old = objs[src]['fields'][field]
release(old)
if dst is not None:
objs[dst]['rc'] += 1
objs[src]['fields'][field] = dst
elif op == 'weak':
objs[ev[1]]['weak'] += 1
elif op == 'unweak':
b = objs[ev[1]]
b['weak'] -= 1
if b['weak'] == 0 and b['rc'] == 0:
dealloc.append(ev[1])
del objs[ev[1]]
else:
b = objs[ev[1]]
if b['rc'] > 0:
b['rc'] += 1
out.append(True)
else:
out.append(False)
except (KeyError, IndexError):
out.append('use-after-free')
return {'out': out, 'freed': freed, 'dealloc': dealloc,
'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
([['new', 11, 1],
['new', 12, 1],
['new', 13, 0],
['store', 12, 0, 13],
['drop', 13],
['store', 11, 0, 12],
['drop', 12],
['store', 11, 0, 13]],),
{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
('self-assignment of the only reference',
([['new', 11, 1],
['new', 12, 0],
['store', 11, 0, 12],
['drop', 12],
['store', 11, 0, 12],
['upgrade', 12]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
('object referenced twice by one parent',
([['new', 11, 2],
['new', 12, 0],
['store', 11, 0, 12],
['store', 11, 1, 12],
['drop', 12],
['drop', 11]],),
{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 11, 1],
['new', 12, 0],
['store', 11, 0, 12],
['weak', 11],
['drop', 11],
['upgrade', 11],
['unweak', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 11, 1],
['new', 12, 1],
['new', 13, 0],
['store', 11, 0, 12],
['store', 12, 0, 13],
['drop', 12],
['drop', 13],
['drop', 11]],),
{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 21, 1],
['new', 22, 1],
['new', 23, 0],
['store', 22, 0, 23],
['drop', 23],
['store', 21, 0, 22],
['drop', 22],
['store', 21, 0, 23]],),
{'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
('self-assignment of the only reference',
([['new', 21, 1],
['new', 22, 0],
['store', 21, 0, 22],
['drop', 22],
['store', 21, 0, 22],
['upgrade', 22]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
('object referenced twice by one parent',
([['new', 21, 2],
['new', 22, 0],
['store', 21, 0, 22],
['store', 21, 1, 22],
['drop', 22],
['drop', 21]],),
{'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 21, 1],
['new', 22, 0],
['store', 21, 0, 22],
['weak', 21],
['drop', 21],
['upgrade', 21],
['unweak', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 21, 1],
['new', 22, 1],
['new', 23, 0],
['store', 21, 0, 22],
['store', 22, 0, 23],
['drop', 22],
['drop', 23],
['drop', 21]],),
{'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 31, 1],
['new', 32, 1],
['new', 33, 0],
['store', 32, 0, 33],
['drop', 33],
['store', 31, 0, 32],
['drop', 32],
['store', 31, 0, 33]],),
{'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
('self-assignment of the only reference',
([['new', 31, 1],
['new', 32, 0],
['store', 31, 0, 32],
['drop', 32],
['store', 31, 0, 32],
['upgrade', 32]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
('object referenced twice by one parent',
([['new', 31, 2],
['new', 32, 0],
['store', 31, 0, 32],
['store', 31, 1, 32],
['drop', 32],
['drop', 31]],),
{'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 31, 1],
['new', 32, 0],
['store', 31, 0, 32],
['weak', 31],
['drop', 31],
['upgrade', 31],
['unweak', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 31, 1],
['new', 32, 1],
['new', 33, 0],
['store', 31, 0, 32],
['store', 32, 0, 33],
['drop', 32],
['drop', 33],
['drop', 31]],),
{'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 41, 1],
['new', 42, 1],
['new', 43, 0],
['store', 42, 0, 43],
['drop', 43],
['store', 41, 0, 42],
['drop', 42],
['store', 41, 0, 43]],),
{'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
('self-assignment of the only reference',
([['new', 41, 1],
['new', 42, 0],
['store', 41, 0, 42],
['drop', 42],
['store', 41, 0, 42],
['upgrade', 42]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
('object referenced twice by one parent',
([['new', 41, 2],
['new', 42, 0],
['store', 41, 0, 42],
['store', 41, 1, 42],
['drop', 42],
['drop', 41]],),
{'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 41, 1],
['new', 42, 0],
['store', 41, 0, 42],
['weak', 41],
['drop', 41],
['upgrade', 41],
['unweak', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 41, 1],
['new', 42, 1],
['new', 43, 0],
['store', 41, 0, 42],
['store', 42, 0, 43],
['drop', 42],
['drop', 43],
['drop', 41]],),
{'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 51, 1],
['new', 52, 1],
['new', 53, 0],
['store', 52, 0, 53],
['drop', 53],
['store', 51, 0, 52],
['drop', 52],
['store', 51, 0, 53]],),
{'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
('self-assignment of the only reference',
([['new', 51, 1],
['new', 52, 0],
['store', 51, 0, 52],
['drop', 52],
['store', 51, 0, 52],
['upgrade', 52]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
('object referenced twice by one parent',
([['new', 51, 2],
['new', 52, 0],
['store', 51, 0, 52],
['store', 51, 1, 52],
['drop', 52],
['drop', 51]],),
{'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 51, 1],
['new', 52, 0],
['store', 51, 0, 52],
['weak', 51],
['drop', 51],
['upgrade', 51],
['unweak', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 51, 1],
['new', 52, 1],
['new', 53, 0],
['store', 51, 0, 52],
['store', 52, 0, 53],
['drop', 52],
['drop', 53],
['drop', 51]],),
{'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: overwrite with a child of the old value | {'dealloc': [12, 13], 'freed': [12, 13], 'out': ['use-after-free'], 'rc': {'11': [1, 0]}} | {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}} | Failed |
| self-assignment of the only reference | {'dealloc': [12], 'freed': [12], 'out': ['use-after-free'], 'rc': {'11': [1, 0]}} | {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}} | Failed |
| object referenced twice by one parent | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | Passed |
| upgrade after the last strong reference dies | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}} | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}} | Passed |
| weak reference keeps the control block only | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}} | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}} | Passed |
| dropping a weak reference to a live object | {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}} | {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}} | Passed |
| control: chain release order | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | Passed |
SHA-256 / 742ba234f800810d9477fe02c77a8a8e5227a85d806ed3633ddef254b9597ee1
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(events):
objs = {}
freed = []
dealloc = []
out = []
def release(o):
if o is None:
return
b = objs[o]
b['rc'] -= 1
if b['rc'] == 0:
freed.append(o)
kids, b['fields'] = b['fields'], []
if b['weak'] == 0:
dealloc.append(o)
del objs[o]
for c in kids:
release(c)
try:
for ev in events:
op = ev[0]
if op == 'new':
objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
elif op == 'drop':
release(ev[1])
elif op == 'store':
_, src, field, dst = ev
old = objs[src]['fields'][field]
if old is not dst:
release(old)
if dst is not None:
objs[dst]['rc'] += 1
objs[src]['fields'][field] = dst
elif op == 'weak':
objs[ev[1]]['weak'] += 1
elif op == 'unweak':
b = objs[ev[1]]
b['weak'] -= 1
if b['weak'] == 0 and b['rc'] == 0:
dealloc.append(ev[1])
del objs[ev[1]]
else:
b = objs[ev[1]]
if b['rc'] > 0:
b['rc'] += 1
out.append(True)
else:
out.append(False)
except (KeyError, IndexError):
out.append('use-after-free')
return {'out': out, 'freed': freed, 'dealloc': dealloc,
'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
([['new', 11, 1],
['new', 12, 1],
['new', 13, 0],
['store', 12, 0, 13],
['drop', 13],
['store', 11, 0, 12],
['drop', 12],
['store', 11, 0, 13]],),
{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
('self-assignment of the only reference',
([['new', 11, 1],
['new', 12, 0],
['store', 11, 0, 12],
['drop', 12],
['store', 11, 0, 12],
['upgrade', 12]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
('object referenced twice by one parent',
([['new', 11, 2],
['new', 12, 0],
['store', 11, 0, 12],
['store', 11, 1, 12],
['drop', 12],
['drop', 11]],),
{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 11, 1],
['new', 12, 0],
['store', 11, 0, 12],
['weak', 11],
['drop', 11],
['upgrade', 11],
['unweak', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 11, 1],
['new', 12, 1],
['new', 13, 0],
['store', 11, 0, 12],
['store', 12, 0, 13],
['drop', 12],
['drop', 13],
['drop', 11]],),
{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 21, 1],
['new', 22, 1],
['new', 23, 0],
['store', 22, 0, 23],
['drop', 23],
['store', 21, 0, 22],
['drop', 22],
['store', 21, 0, 23]],),
{'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
('self-assignment of the only reference',
([['new', 21, 1],
['new', 22, 0],
['store', 21, 0, 22],
['drop', 22],
['store', 21, 0, 22],
['upgrade', 22]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
('object referenced twice by one parent',
([['new', 21, 2],
['new', 22, 0],
['store', 21, 0, 22],
['store', 21, 1, 22],
['drop', 22],
['drop', 21]],),
{'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 21, 1],
['new', 22, 0],
['store', 21, 0, 22],
['weak', 21],
['drop', 21],
['upgrade', 21],
['unweak', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 21, 1],
['new', 22, 1],
['new', 23, 0],
['store', 21, 0, 22],
['store', 22, 0, 23],
['drop', 22],
['drop', 23],
['drop', 21]],),
{'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 31, 1],
['new', 32, 1],
['new', 33, 0],
['store', 32, 0, 33],
['drop', 33],
['store', 31, 0, 32],
['drop', 32],
['store', 31, 0, 33]],),
{'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
('self-assignment of the only reference',
([['new', 31, 1],
['new', 32, 0],
['store', 31, 0, 32],
['drop', 32],
['store', 31, 0, 32],
['upgrade', 32]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
('object referenced twice by one parent',
([['new', 31, 2],
['new', 32, 0],
['store', 31, 0, 32],
['store', 31, 1, 32],
['drop', 32],
['drop', 31]],),
{'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 31, 1],
['new', 32, 0],
['store', 31, 0, 32],
['weak', 31],
['drop', 31],
['upgrade', 31],
['unweak', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 31, 1],
['new', 32, 1],
['new', 33, 0],
['store', 31, 0, 32],
['store', 32, 0, 33],
['drop', 32],
['drop', 33],
['drop', 31]],),
{'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 41, 1],
['new', 42, 1],
['new', 43, 0],
['store', 42, 0, 43],
['drop', 43],
['store', 41, 0, 42],
['drop', 42],
['store', 41, 0, 43]],),
{'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
('self-assignment of the only reference',
([['new', 41, 1],
['new', 42, 0],
['store', 41, 0, 42],
['drop', 42],
['store', 41, 0, 42],
['upgrade', 42]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
('object referenced twice by one parent',
([['new', 41, 2],
['new', 42, 0],
['store', 41, 0, 42],
['store', 41, 1, 42],
['drop', 42],
['drop', 41]],),
{'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 41, 1],
['new', 42, 0],
['store', 41, 0, 42],
['weak', 41],
['drop', 41],
['upgrade', 41],
['unweak', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 41, 1],
['new', 42, 1],
['new', 43, 0],
['store', 41, 0, 42],
['store', 42, 0, 43],
['drop', 42],
['drop', 43],
['drop', 41]],),
{'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 51, 1],
['new', 52, 1],
['new', 53, 0],
['store', 52, 0, 53],
['drop', 53],
['store', 51, 0, 52],
['drop', 52],
['store', 51, 0, 53]],),
{'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
('self-assignment of the only reference',
([['new', 51, 1],
['new', 52, 0],
['store', 51, 0, 52],
['drop', 52],
['store', 51, 0, 52],
['upgrade', 52]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
('object referenced twice by one parent',
([['new', 51, 2],
['new', 52, 0],
['store', 51, 0, 52],
['store', 51, 1, 52],
['drop', 52],
['drop', 51]],),
{'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 51, 1],
['new', 52, 0],
['store', 51, 0, 52],
['weak', 51],
['drop', 51],
['upgrade', 51],
['unweak', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 51, 1],
['new', 52, 1],
['new', 53, 0],
['store', 51, 0, 52],
['store', 52, 0, 53],
['drop', 52],
['drop', 53],
['drop', 51]],),
{'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: overwrite with a child of the old value | {'dealloc': [12, 13], 'freed': [12, 13], 'out': ['use-after-free'], 'rc': {'11': [1, 0]}} | {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}} | Failed |
| self-assignment of the only reference | {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}} | {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}} | Passed |
| object referenced twice by one parent | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | Passed |
| upgrade after the last strong reference dies | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}} | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}} | Passed |
| weak reference keeps the control block only | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}} | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}} | Passed |
| dropping a weak reference to a live object | {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}} | {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}} | Passed |
| control: chain release order | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | Passed |
SHA-256 / df50e3894ea7f91d2229693ede090edfe9aa305a93603daf818cf5d2d013d624
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(events):
objs = {}
freed = []
dealloc = []
out = []
def release(o):
if o is None:
return
b = objs[o]
b['rc'] -= 1
if b['rc'] == 0:
freed.append(o)
kids, b['fields'] = b['fields'], []
if b['weak'] == 0:
dealloc.append(o)
del objs[o]
for c in kids:
release(c)
try:
for ev in events:
op = ev[0]
if op == 'new':
objs[ev[1]] = {'rc': 1, 'weak': 0, 'fields': [None] * ev[2]}
elif op == 'drop':
release(ev[1])
elif op == 'store':
_, src, field, dst = ev
if dst is not None:
objs[dst]['rc'] += 1
old = objs[src]['fields'][field]
objs[src]['fields'][field] = dst
release(old)
elif op == 'weak':
objs[ev[1]]['weak'] += 1
elif op == 'unweak':
b = objs[ev[1]]
b['weak'] -= 1
if b['weak'] == 0 and b['rc'] == 0:
dealloc.append(ev[1])
del objs[ev[1]]
else:
b = objs[ev[1]]
if b['rc'] > 0:
b['rc'] += 1
out.append(True)
else:
out.append(False)
except (KeyError, IndexError):
out.append('use-after-free')
return {'out': out, 'freed': freed, 'dealloc': dealloc,
'rc': {str(k): [v['rc'], v['weak']] for k, v in sorted(objs.items())}}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: overwrite with a child of the old value',
([['new', 11, 1],
['new', 12, 1],
['new', 13, 0],
['store', 12, 0, 13],
['drop', 13],
['store', 11, 0, 12],
['drop', 12],
['store', 11, 0, 13]],),
{'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}}),
('self-assignment of the only reference',
([['new', 11, 1],
['new', 12, 0],
['store', 11, 0, 12],
['drop', 12],
['store', 11, 0, 12],
['upgrade', 12]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}}),
('object referenced twice by one parent',
([['new', 11, 2],
['new', 12, 0],
['store', 11, 0, 12],
['store', 11, 1, 12],
['drop', 12],
['drop', 11]],),
{'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 11, 0], ['weak', 11], ['drop', 11], ['upgrade', 11], ['unweak', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 11, 1],
['new', 12, 0],
['store', 11, 0, 12],
['weak', 11],
['drop', 11],
['upgrade', 11],
['unweak', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 11, 0], ['weak', 11], ['unweak', 11], ['upgrade', 11], ['drop', 11], ['drop', 11]],),
{'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 11, 1],
['new', 12, 1],
['new', 13, 0],
['store', 11, 0, 12],
['store', 12, 0, 13],
['drop', 12],
['drop', 13],
['drop', 11]],),
{'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 21, 1],
['new', 22, 1],
['new', 23, 0],
['store', 22, 0, 23],
['drop', 23],
['store', 21, 0, 22],
['drop', 22],
['store', 21, 0, 23]],),
{'dealloc': [22], 'freed': [22], 'out': [], 'rc': {'21': [1, 0], '23': [1, 0]}}),
('self-assignment of the only reference',
([['new', 21, 1],
['new', 22, 0],
['store', 21, 0, 22],
['drop', 22],
['store', 21, 0, 22],
['upgrade', 22]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'21': [1, 0], '22': [2, 0]}}),
('object referenced twice by one parent',
([['new', 21, 2],
['new', 22, 0],
['store', 21, 0, 22],
['store', 21, 1, 22],
['drop', 22],
['drop', 21]],),
{'dealloc': [21, 22], 'freed': [21, 22], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 21, 0], ['weak', 21], ['drop', 21], ['upgrade', 21], ['unweak', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 21, 1],
['new', 22, 0],
['store', 21, 0, 22],
['weak', 21],
['drop', 21],
['upgrade', 21],
['unweak', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [False], 'rc': {'22': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 21, 0], ['weak', 21], ['unweak', 21], ['upgrade', 21], ['drop', 21], ['drop', 21]],),
{'dealloc': [21], 'freed': [21], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 21, 1],
['new', 22, 1],
['new', 23, 0],
['store', 21, 0, 22],
['store', 22, 0, 23],
['drop', 22],
['drop', 23],
['drop', 21]],),
{'dealloc': [21, 22, 23], 'freed': [21, 22, 23], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 31, 1],
['new', 32, 1],
['new', 33, 0],
['store', 32, 0, 33],
['drop', 33],
['store', 31, 0, 32],
['drop', 32],
['store', 31, 0, 33]],),
{'dealloc': [32], 'freed': [32], 'out': [], 'rc': {'31': [1, 0], '33': [1, 0]}}),
('self-assignment of the only reference',
([['new', 31, 1],
['new', 32, 0],
['store', 31, 0, 32],
['drop', 32],
['store', 31, 0, 32],
['upgrade', 32]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'31': [1, 0], '32': [2, 0]}}),
('object referenced twice by one parent',
([['new', 31, 2],
['new', 32, 0],
['store', 31, 0, 32],
['store', 31, 1, 32],
['drop', 32],
['drop', 31]],),
{'dealloc': [31, 32], 'freed': [31, 32], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 31, 0], ['weak', 31], ['drop', 31], ['upgrade', 31], ['unweak', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 31, 1],
['new', 32, 0],
['store', 31, 0, 32],
['weak', 31],
['drop', 31],
['upgrade', 31],
['unweak', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [False], 'rc': {'32': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 31, 0], ['weak', 31], ['unweak', 31], ['upgrade', 31], ['drop', 31], ['drop', 31]],),
{'dealloc': [31], 'freed': [31], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 31, 1],
['new', 32, 1],
['new', 33, 0],
['store', 31, 0, 32],
['store', 32, 0, 33],
['drop', 32],
['drop', 33],
['drop', 31]],),
{'dealloc': [31, 32, 33], 'freed': [31, 32, 33], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 41, 1],
['new', 42, 1],
['new', 43, 0],
['store', 42, 0, 43],
['drop', 43],
['store', 41, 0, 42],
['drop', 42],
['store', 41, 0, 43]],),
{'dealloc': [42], 'freed': [42], 'out': [], 'rc': {'41': [1, 0], '43': [1, 0]}}),
('self-assignment of the only reference',
([['new', 41, 1],
['new', 42, 0],
['store', 41, 0, 42],
['drop', 42],
['store', 41, 0, 42],
['upgrade', 42]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'41': [1, 0], '42': [2, 0]}}),
('object referenced twice by one parent',
([['new', 41, 2],
['new', 42, 0],
['store', 41, 0, 42],
['store', 41, 1, 42],
['drop', 42],
['drop', 41]],),
{'dealloc': [41, 42], 'freed': [41, 42], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 41, 0], ['weak', 41], ['drop', 41], ['upgrade', 41], ['unweak', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 41, 1],
['new', 42, 0],
['store', 41, 0, 42],
['weak', 41],
['drop', 41],
['upgrade', 41],
['unweak', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [False], 'rc': {'42': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 41, 0], ['weak', 41], ['unweak', 41], ['upgrade', 41], ['drop', 41], ['drop', 41]],),
{'dealloc': [41], 'freed': [41], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 41, 1],
['new', 42, 1],
['new', 43, 0],
['store', 41, 0, 42],
['store', 42, 0, 43],
['drop', 42],
['drop', 43],
['drop', 41]],),
{'dealloc': [41, 42, 43], 'freed': [41, 42, 43], 'out': [], 'rc': {}})],
[('regression: overwrite with a child of the old value',
([['new', 51, 1],
['new', 52, 1],
['new', 53, 0],
['store', 52, 0, 53],
['drop', 53],
['store', 51, 0, 52],
['drop', 52],
['store', 51, 0, 53]],),
{'dealloc': [52], 'freed': [52], 'out': [], 'rc': {'51': [1, 0], '53': [1, 0]}}),
('self-assignment of the only reference',
([['new', 51, 1],
['new', 52, 0],
['store', 51, 0, 52],
['drop', 52],
['store', 51, 0, 52],
['upgrade', 52]],),
{'dealloc': [], 'freed': [], 'out': [True], 'rc': {'51': [1, 0], '52': [2, 0]}}),
('object referenced twice by one parent',
([['new', 51, 2],
['new', 52, 0],
['store', 51, 0, 52],
['store', 51, 1, 52],
['drop', 52],
['drop', 51]],),
{'dealloc': [51, 52], 'freed': [51, 52], 'out': [], 'rc': {}}),
('upgrade after the last strong reference dies',
([['new', 51, 0], ['weak', 51], ['drop', 51], ['upgrade', 51], ['unweak', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {}}),
('weak reference keeps the control block only',
([['new', 51, 1],
['new', 52, 0],
['store', 51, 0, 52],
['weak', 51],
['drop', 51],
['upgrade', 51],
['unweak', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [False], 'rc': {'52': [1, 0]}}),
('dropping a weak reference to a live object',
([['new', 51, 0], ['weak', 51], ['unweak', 51], ['upgrade', 51], ['drop', 51], ['drop', 51]],),
{'dealloc': [51], 'freed': [51], 'out': [True], 'rc': {}}),
('control: chain release order',
([['new', 51, 1],
['new', 52, 1],
['new', 53, 0],
['store', 51, 0, 52],
['store', 52, 0, 53],
['drop', 52],
['drop', 53],
['drop', 51]],),
{'dealloc': [51, 52, 53], 'freed': [51, 52, 53], 'out': [], 'rc': {}})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: overwrite with a child of the old value | {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}} | {'dealloc': [12], 'freed': [12], 'out': [], 'rc': {'11': [1, 0], '13': [1, 0]}} | Passed |
| self-assignment of the only reference | {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}} | {'dealloc': [], 'freed': [], 'out': [True], 'rc': {'11': [1, 0], '12': [2, 0]}} | Passed |
| object referenced twice by one parent | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | {'dealloc': [11, 12], 'freed': [11, 12], 'out': [], 'rc': {}} | Passed |
| upgrade after the last strong reference dies | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}} | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {}} | Passed |
| weak reference keeps the control block only | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}} | {'dealloc': [11], 'freed': [11], 'out': [False], 'rc': {'12': [1, 0]}} | Passed |
| dropping a weak reference to a live object | {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}} | {'dealloc': [11], 'freed': [11], 'out': [True], 'rc': {}} | Passed |
| control: chain release order | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | {'dealloc': [11, 12, 13], 'freed': [11, 12, 13], 'out': [], 'rc': {}} | Passed |
SHA-256 / bb0a242343e9a77d89dc0d20b2d39e1043b2ec3079fa8c8f2860209e66e25442
Verification & scope
A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:25.946933+00:00.
Case digest / 15e4178949196d839391a90ed1a025f2b9ce8fd5a28c344cb083907751588d8b