FA-43811 / Borrow checking / Open access
Loop analysis accepts the preheader state without backedge loan facts · case 01
Loop analysis accepts the preheader state without backedge loan facts.
ROOT CAUSE
The static analyzer mishandles loop backedge join: loop analysis accepts the preheader state without backedge loan facts.
VERIFIED REPAIR
Apply the specified transfer or inference rule at this site: if not set(d['backedge'])<=set(d['header']): errors.append('loop-backedge-join').
Unsuccessful approach: The partial repair uses if not d['header'] and bool(d['backedge']): errors.append('loop-backedge-join'), which still violates the stipulated analysis contract.
Case contract
Check dataflow certificates for loan analysis. Reachability starts at entry and ignores dead blocks; all normal and exceptional successors participate; loop header solution includes backedge loans; kill transfer is edge-specific; phi origins correspond to predecessor edge; dominator proof must cover every incoming edge; a loan definition cannot be live before its definition except on a proven loop backedge; unreachable kills do not invalidate reachable loans; terminal return kills only function-local loans. Input is a fully explicit descriptor of the stated toy IR. Return rule identifiers in declaration order; absent optional obligations use the provided neutral defaults. No rule is an assertion about a production language.
Why this case matters
A finite offline static-analysis model of ownership and borrowing; it does not execute the analyzed program.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
errors=[]
if d['entry'] is not None and d['entry'] not in d['reachable']: errors.append('entry-reachability')
if bool(set(d['dead'])&set(d['reachable'])): errors.append('dead-block-exclusion')
if not set(d['normal'])<=set(d['processed']): errors.append('all-normal-successors')
if not set(d['exceptional'])<=set(d['processed']): errors.append('exceptional-successors')
if False: errors.append('loop-backedge-join')
if d['edge_kills']!=d['applied_kills']: errors.append('edge-kill-locality')
if d['phi_edges']!=d['expected_phi_edges']: errors.append('phi-edge-origin')
if not set(d['incoming'])<=set(d['dominated']): errors.append('all-path-dominance')
if not set(d['predef_live'])<=set(d['loop_allowed']): errors.append('predefinition-liveness')
if not set(d['return_killed'])<=set(d['local_loans']): errors.append('return-local-kill')
return errors
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
base={'entry': None, 'reachable': [], 'dead': [], 'normal': [], 'processed': [], 'exceptional': [], 'backedge': [], 'header': [], 'edge_kills': {}, 'applied_kills': {}, 'phi_edges': {}, 'expected_phi_edges': {}, 'incoming': [], 'dominated': [], 'predef_live': [], 'loop_allowed': [], 'dead_killed': [], 'reachable_invalidated': [], 'return_killed': [], 'local_loans': []}
check('well formed empty obligations',solve(base),[])
check('entry-reachability regression 0', solve(dict(base, **({'entry':'e','reachable':['x']}))), ['entry-reachability'])
check('entry-reachability regression 1', solve(dict(base, **({'entry':N,'reachable':[N+1]}))), ['entry-reachability'])
check('dead-block-exclusion regression 0', solve(dict(base, **({'dead':['d'],'reachable':['e','d']}))), ['dead-block-exclusion'])
check('dead-block-exclusion regression 1', solve(dict(base, **({'dead':[N],'reachable':[N,N+1]}))), ['dead-block-exclusion'])
check('all-normal-successors regression 0', solve(dict(base, **({'normal':['a','b'],'processed':['a']}))), ['all-normal-successors'])
check('all-normal-successors regression 1', solve(dict(base, **({'normal':[N,N+1],'processed':[N]}))), ['all-normal-successors'])
check('exceptional-successors regression 0', solve(dict(base, **({'exceptional':['u'],'processed':['n']}))), ['exceptional-successors'])
check('exceptional-successors regression 1', solve(dict(base, **({'exceptional':[N],'processed':[N+1]}))), ['exceptional-successors'])
check('loop-backedge-join regression 0', solve(dict(base, **({'backedge':['a','b'],'header':['a']}))), ['loop-backedge-join'])
check('loop-backedge-join regression 1', solve(dict(base, **({'backedge':[N,N+1],'header':[N]}))), ['loop-backedge-join'])
check('edge-kill-locality regression 0', solve(dict(base, **({'edge_kills':{'a':['r'],'b':[]},'applied_kills':{'a':['r'],'b':['r']}}))), ['edge-kill-locality'])
check('edge-kill-locality regression 1', solve(dict(base, **({'edge_kills':{N:['r'],N+1:[]},'applied_kills':{N:['r'],N+1:['r']}}))), ['edge-kill-locality'])
check('phi-edge-origin regression 0', solve(dict(base, **({'phi_edges':{'a':'y','b':'x'},'expected_phi_edges':{'a':'x','b':'y'}}))), ['phi-edge-origin'])
check('phi-edge-origin regression 1', solve(dict(base, **({'phi_edges':{N:'y',N+1:'x'},'expected_phi_edges':{N:'x',N+1:'y'}}))), ['phi-edge-origin'])
check('all-path-dominance regression 0', solve(dict(base, **({'incoming':['a','b'],'dominated':['a']}))), ['all-path-dominance'])
check('all-path-dominance regression 1', solve(dict(base, **({'incoming':[N,N+1],'dominated':[N]}))), ['all-path-dominance'])
check('predefinition-liveness regression 0', solve(dict(base, **({'predef_live':['a','b'],'loop_allowed':['a']}))), ['predefinition-liveness'])
check('predefinition-liveness regression 1', solve(dict(base, **({'predef_live':[N,N+1],'loop_allowed':[N]}))), ['predefinition-liveness'])
check('return-local-kill regression 0', solve(dict(base, **({'return_killed':['caller'],'local_loans':['callee']}))), ['return-local-kill'])
check('return-local-kill regression 1', solve(dict(base, **({'return_killed':[N],'local_loans':[N+1]}))), ['return-local-kill'])
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 |
|---|---|---|---|
| well formed empty obligations | [] | [] | Passed |
| entry-reachability regression 0 | ['entry-reachability'] | ['entry-reachability'] | Passed |
| entry-reachability regression 1 | ['entry-reachability'] | ['entry-reachability'] | Passed |
| dead-block-exclusion regression 0 | ['dead-block-exclusion'] | ['dead-block-exclusion'] | Passed |
| dead-block-exclusion regression 1 | ['dead-block-exclusion'] | ['dead-block-exclusion'] | Passed |
| all-normal-successors regression 0 | ['all-normal-successors'] | ['all-normal-successors'] | Passed |
| all-normal-successors regression 1 | ['all-normal-successors'] | ['all-normal-successors'] | Passed |
| exceptional-successors regression 0 | ['exceptional-successors'] | ['exceptional-successors'] | Passed |
| exceptional-successors regression 1 | ['exceptional-successors'] | ['exceptional-successors'] | Passed |
| loop-backedge-join regression 0 | [] | ['loop-backedge-join'] | Failed |
| loop-backedge-join regression 1 | [] | ['loop-backedge-join'] | Failed |
| edge-kill-locality regression 0 | ['edge-kill-locality'] | ['edge-kill-locality'] | Passed |
| edge-kill-locality regression 1 | ['edge-kill-locality'] | ['edge-kill-locality'] | Passed |
| phi-edge-origin regression 0 | ['phi-edge-origin'] | ['phi-edge-origin'] | Passed |
| phi-edge-origin regression 1 | ['phi-edge-origin'] | ['phi-edge-origin'] | Passed |
| all-path-dominance regression 0 | ['all-path-dominance'] | ['all-path-dominance'] | Passed |
| all-path-dominance regression 1 | ['all-path-dominance'] | ['all-path-dominance'] | Passed |
| predefinition-liveness regression 0 | ['predefinition-liveness'] | ['predefinition-liveness'] | Passed |
| predefinition-liveness regression 1 | ['predefinition-liveness'] | ['predefinition-liveness'] | Passed |
| return-local-kill regression 0 | ['return-local-kill'] | ['return-local-kill'] | Passed |
| return-local-kill regression 1 | ['return-local-kill'] | ['return-local-kill'] | Passed |
SHA-256 / b8568ff9be790188776bf5c749ba08a9056994a6e0080a59e194a8b92487f64c
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
errors=[]
if d['entry'] is not None and d['entry'] not in d['reachable']: errors.append('entry-reachability')
if bool(set(d['dead'])&set(d['reachable'])): errors.append('dead-block-exclusion')
if not set(d['normal'])<=set(d['processed']): errors.append('all-normal-successors')
if not set(d['exceptional'])<=set(d['processed']): errors.append('exceptional-successors')
if not d['header'] and bool(d['backedge']): errors.append('loop-backedge-join')
if d['edge_kills']!=d['applied_kills']: errors.append('edge-kill-locality')
if d['phi_edges']!=d['expected_phi_edges']: errors.append('phi-edge-origin')
if not set(d['incoming'])<=set(d['dominated']): errors.append('all-path-dominance')
if not set(d['predef_live'])<=set(d['loop_allowed']): errors.append('predefinition-liveness')
if not set(d['return_killed'])<=set(d['local_loans']): errors.append('return-local-kill')
return errors
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
base={'entry': None, 'reachable': [], 'dead': [], 'normal': [], 'processed': [], 'exceptional': [], 'backedge': [], 'header': [], 'edge_kills': {}, 'applied_kills': {}, 'phi_edges': {}, 'expected_phi_edges': {}, 'incoming': [], 'dominated': [], 'predef_live': [], 'loop_allowed': [], 'dead_killed': [], 'reachable_invalidated': [], 'return_killed': [], 'local_loans': []}
check('well formed empty obligations',solve(base),[])
check('entry-reachability regression 0', solve(dict(base, **({'entry':'e','reachable':['x']}))), ['entry-reachability'])
check('entry-reachability regression 1', solve(dict(base, **({'entry':N,'reachable':[N+1]}))), ['entry-reachability'])
check('dead-block-exclusion regression 0', solve(dict(base, **({'dead':['d'],'reachable':['e','d']}))), ['dead-block-exclusion'])
check('dead-block-exclusion regression 1', solve(dict(base, **({'dead':[N],'reachable':[N,N+1]}))), ['dead-block-exclusion'])
check('all-normal-successors regression 0', solve(dict(base, **({'normal':['a','b'],'processed':['a']}))), ['all-normal-successors'])
check('all-normal-successors regression 1', solve(dict(base, **({'normal':[N,N+1],'processed':[N]}))), ['all-normal-successors'])
check('exceptional-successors regression 0', solve(dict(base, **({'exceptional':['u'],'processed':['n']}))), ['exceptional-successors'])
check('exceptional-successors regression 1', solve(dict(base, **({'exceptional':[N],'processed':[N+1]}))), ['exceptional-successors'])
check('loop-backedge-join regression 0', solve(dict(base, **({'backedge':['a','b'],'header':['a']}))), ['loop-backedge-join'])
check('loop-backedge-join regression 1', solve(dict(base, **({'backedge':[N,N+1],'header':[N]}))), ['loop-backedge-join'])
check('edge-kill-locality regression 0', solve(dict(base, **({'edge_kills':{'a':['r'],'b':[]},'applied_kills':{'a':['r'],'b':['r']}}))), ['edge-kill-locality'])
check('edge-kill-locality regression 1', solve(dict(base, **({'edge_kills':{N:['r'],N+1:[]},'applied_kills':{N:['r'],N+1:['r']}}))), ['edge-kill-locality'])
check('phi-edge-origin regression 0', solve(dict(base, **({'phi_edges':{'a':'y','b':'x'},'expected_phi_edges':{'a':'x','b':'y'}}))), ['phi-edge-origin'])
check('phi-edge-origin regression 1', solve(dict(base, **({'phi_edges':{N:'y',N+1:'x'},'expected_phi_edges':{N:'x',N+1:'y'}}))), ['phi-edge-origin'])
check('all-path-dominance regression 0', solve(dict(base, **({'incoming':['a','b'],'dominated':['a']}))), ['all-path-dominance'])
check('all-path-dominance regression 1', solve(dict(base, **({'incoming':[N,N+1],'dominated':[N]}))), ['all-path-dominance'])
check('predefinition-liveness regression 0', solve(dict(base, **({'predef_live':['a','b'],'loop_allowed':['a']}))), ['predefinition-liveness'])
check('predefinition-liveness regression 1', solve(dict(base, **({'predef_live':[N,N+1],'loop_allowed':[N]}))), ['predefinition-liveness'])
check('return-local-kill regression 0', solve(dict(base, **({'return_killed':['caller'],'local_loans':['callee']}))), ['return-local-kill'])
check('return-local-kill regression 1', solve(dict(base, **({'return_killed':[N],'local_loans':[N+1]}))), ['return-local-kill'])
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 |
|---|---|---|---|
| well formed empty obligations | [] | [] | Passed |
| entry-reachability regression 0 | ['entry-reachability'] | ['entry-reachability'] | Passed |
| entry-reachability regression 1 | ['entry-reachability'] | ['entry-reachability'] | Passed |
| dead-block-exclusion regression 0 | ['dead-block-exclusion'] | ['dead-block-exclusion'] | Passed |
| dead-block-exclusion regression 1 | ['dead-block-exclusion'] | ['dead-block-exclusion'] | Passed |
| all-normal-successors regression 0 | ['all-normal-successors'] | ['all-normal-successors'] | Passed |
| all-normal-successors regression 1 | ['all-normal-successors'] | ['all-normal-successors'] | Passed |
| exceptional-successors regression 0 | ['exceptional-successors'] | ['exceptional-successors'] | Passed |
| exceptional-successors regression 1 | ['exceptional-successors'] | ['exceptional-successors'] | Passed |
| loop-backedge-join regression 0 | [] | ['loop-backedge-join'] | Failed |
| loop-backedge-join regression 1 | [] | ['loop-backedge-join'] | Failed |
| edge-kill-locality regression 0 | ['edge-kill-locality'] | ['edge-kill-locality'] | Passed |
| edge-kill-locality regression 1 | ['edge-kill-locality'] | ['edge-kill-locality'] | Passed |
| phi-edge-origin regression 0 | ['phi-edge-origin'] | ['phi-edge-origin'] | Passed |
| phi-edge-origin regression 1 | ['phi-edge-origin'] | ['phi-edge-origin'] | Passed |
| all-path-dominance regression 0 | ['all-path-dominance'] | ['all-path-dominance'] | Passed |
| all-path-dominance regression 1 | ['all-path-dominance'] | ['all-path-dominance'] | Passed |
| predefinition-liveness regression 0 | ['predefinition-liveness'] | ['predefinition-liveness'] | Passed |
| predefinition-liveness regression 1 | ['predefinition-liveness'] | ['predefinition-liveness'] | Passed |
| return-local-kill regression 0 | ['return-local-kill'] | ['return-local-kill'] | Passed |
| return-local-kill regression 1 | ['return-local-kill'] | ['return-local-kill'] | Passed |
SHA-256 / 2b9811da16b8022c585177489d9f701cc29f0007ef1baf779be5bcb13dd8ad28
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
errors=[]
if d['entry'] is not None and d['entry'] not in d['reachable']: errors.append('entry-reachability')
if bool(set(d['dead'])&set(d['reachable'])): errors.append('dead-block-exclusion')
if not set(d['normal'])<=set(d['processed']): errors.append('all-normal-successors')
if not set(d['exceptional'])<=set(d['processed']): errors.append('exceptional-successors')
if not set(d['backedge'])<=set(d['header']): errors.append('loop-backedge-join')
if d['edge_kills']!=d['applied_kills']: errors.append('edge-kill-locality')
if d['phi_edges']!=d['expected_phi_edges']: errors.append('phi-edge-origin')
if not set(d['incoming'])<=set(d['dominated']): errors.append('all-path-dominance')
if not set(d['predef_live'])<=set(d['loop_allowed']): errors.append('predefinition-liveness')
if not set(d['return_killed'])<=set(d['local_loans']): errors.append('return-local-kill')
return errors
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
base={'entry': None, 'reachable': [], 'dead': [], 'normal': [], 'processed': [], 'exceptional': [], 'backedge': [], 'header': [], 'edge_kills': {}, 'applied_kills': {}, 'phi_edges': {}, 'expected_phi_edges': {}, 'incoming': [], 'dominated': [], 'predef_live': [], 'loop_allowed': [], 'dead_killed': [], 'reachable_invalidated': [], 'return_killed': [], 'local_loans': []}
check('well formed empty obligations',solve(base),[])
check('entry-reachability regression 0', solve(dict(base, **({'entry':'e','reachable':['x']}))), ['entry-reachability'])
check('entry-reachability regression 1', solve(dict(base, **({'entry':N,'reachable':[N+1]}))), ['entry-reachability'])
check('dead-block-exclusion regression 0', solve(dict(base, **({'dead':['d'],'reachable':['e','d']}))), ['dead-block-exclusion'])
check('dead-block-exclusion regression 1', solve(dict(base, **({'dead':[N],'reachable':[N,N+1]}))), ['dead-block-exclusion'])
check('all-normal-successors regression 0', solve(dict(base, **({'normal':['a','b'],'processed':['a']}))), ['all-normal-successors'])
check('all-normal-successors regression 1', solve(dict(base, **({'normal':[N,N+1],'processed':[N]}))), ['all-normal-successors'])
check('exceptional-successors regression 0', solve(dict(base, **({'exceptional':['u'],'processed':['n']}))), ['exceptional-successors'])
check('exceptional-successors regression 1', solve(dict(base, **({'exceptional':[N],'processed':[N+1]}))), ['exceptional-successors'])
check('loop-backedge-join regression 0', solve(dict(base, **({'backedge':['a','b'],'header':['a']}))), ['loop-backedge-join'])
check('loop-backedge-join regression 1', solve(dict(base, **({'backedge':[N,N+1],'header':[N]}))), ['loop-backedge-join'])
check('edge-kill-locality regression 0', solve(dict(base, **({'edge_kills':{'a':['r'],'b':[]},'applied_kills':{'a':['r'],'b':['r']}}))), ['edge-kill-locality'])
check('edge-kill-locality regression 1', solve(dict(base, **({'edge_kills':{N:['r'],N+1:[]},'applied_kills':{N:['r'],N+1:['r']}}))), ['edge-kill-locality'])
check('phi-edge-origin regression 0', solve(dict(base, **({'phi_edges':{'a':'y','b':'x'},'expected_phi_edges':{'a':'x','b':'y'}}))), ['phi-edge-origin'])
check('phi-edge-origin regression 1', solve(dict(base, **({'phi_edges':{N:'y',N+1:'x'},'expected_phi_edges':{N:'x',N+1:'y'}}))), ['phi-edge-origin'])
check('all-path-dominance regression 0', solve(dict(base, **({'incoming':['a','b'],'dominated':['a']}))), ['all-path-dominance'])
check('all-path-dominance regression 1', solve(dict(base, **({'incoming':[N,N+1],'dominated':[N]}))), ['all-path-dominance'])
check('predefinition-liveness regression 0', solve(dict(base, **({'predef_live':['a','b'],'loop_allowed':['a']}))), ['predefinition-liveness'])
check('predefinition-liveness regression 1', solve(dict(base, **({'predef_live':[N,N+1],'loop_allowed':[N]}))), ['predefinition-liveness'])
check('return-local-kill regression 0', solve(dict(base, **({'return_killed':['caller'],'local_loans':['callee']}))), ['return-local-kill'])
check('return-local-kill regression 1', solve(dict(base, **({'return_killed':[N],'local_loans':[N+1]}))), ['return-local-kill'])
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 |
|---|---|---|---|
| well formed empty obligations | [] | [] | Passed |
| entry-reachability regression 0 | ['entry-reachability'] | ['entry-reachability'] | Passed |
| entry-reachability regression 1 | ['entry-reachability'] | ['entry-reachability'] | Passed |
| dead-block-exclusion regression 0 | ['dead-block-exclusion'] | ['dead-block-exclusion'] | Passed |
| dead-block-exclusion regression 1 | ['dead-block-exclusion'] | ['dead-block-exclusion'] | Passed |
| all-normal-successors regression 0 | ['all-normal-successors'] | ['all-normal-successors'] | Passed |
| all-normal-successors regression 1 | ['all-normal-successors'] | ['all-normal-successors'] | Passed |
| exceptional-successors regression 0 | ['exceptional-successors'] | ['exceptional-successors'] | Passed |
| exceptional-successors regression 1 | ['exceptional-successors'] | ['exceptional-successors'] | Passed |
| loop-backedge-join regression 0 | ['loop-backedge-join'] | ['loop-backedge-join'] | Passed |
| loop-backedge-join regression 1 | ['loop-backedge-join'] | ['loop-backedge-join'] | Passed |
| edge-kill-locality regression 0 | ['edge-kill-locality'] | ['edge-kill-locality'] | Passed |
| edge-kill-locality regression 1 | ['edge-kill-locality'] | ['edge-kill-locality'] | Passed |
| phi-edge-origin regression 0 | ['phi-edge-origin'] | ['phi-edge-origin'] | Passed |
| phi-edge-origin regression 1 | ['phi-edge-origin'] | ['phi-edge-origin'] | Passed |
| all-path-dominance regression 0 | ['all-path-dominance'] | ['all-path-dominance'] | Passed |
| all-path-dominance regression 1 | ['all-path-dominance'] | ['all-path-dominance'] | Passed |
| predefinition-liveness regression 0 | ['predefinition-liveness'] | ['predefinition-liveness'] | Passed |
| predefinition-liveness regression 1 | ['predefinition-liveness'] | ['predefinition-liveness'] | Passed |
| return-local-kill regression 0 | ['return-local-kill'] | ['return-local-kill'] | Passed |
| return-local-kill regression 1 | ['return-local-kill'] | ['return-local-kill'] | Passed |
SHA-256 / 1002a19ebe0b879f36ebafc9769e6b822bf106a7136c51f5e7c0bfad741985f4
Verification & scope
The explicitly stated toy language is the complete scope; this is not a production compiler or a claim about Rust semantics. 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:44:05.933864+00:00.
Case digest / 2db0487fa67ea46d13bb5a193eb8b64040e8532daafa1384c1a4879c715006f3