Fil-C on Nix

Filnix wiki

the formal campaign

rocq/theories/Guard.v

Campaign 3's reuse forms, part three: renew_if and check_limit (formal.md, Campaign 3; rocq.md, Guards and limits).

Both take their evidence from a single definition that tested the pointer earlier, not from a check. A renew_if of a pointer P with guard G trusts G, a span test of a pointer N0 (guard_covers/5): where G is nonzero, the span from N0+GLo up to N0+GHi lay inside its object, and P's span lies inside that one at the offset P's guard chain gives (guard_chain/3). The interpreter renews then, and a failed access test that is not on a freed object is unchecked(span) (renew_res/4). A check_limit of P with U trusts U, a limit of N0 whose size is the check's span (limit_covers/5), and P has N0's lower (a lower chain, lower_chain/3). The interpreter checks then, and a limit of another capability or another size is unchecked(limit). This file proves neither unchecked outcome happens where the pass accepted the instruction.

Decisions

DecisionWhy
the span test's memory is the one it read, which persistsa span test changes nothing; the object it found is as it was or freed (Identity.v)
a guard of 0 needs no argumentkind_res/8 then checks, and a check is never unchecked
the span's width is bounded by valid_op/1's span test, not by the objectthe span test's two addresses are each reduced modulo 2^64; their difference is the span only because the span is less than 2^64
From Stdlib Require Import String ZArith List Bool Lia
From Nanofil Require Import Term Maps Syntax Cfg Values Memory Runtime Ops Semantics Machine Validate Dominance Interval Sites Identity Coverage Walk Invariant Persistence Single Evidence Chain Renew
Import ListNotations
Open Scope Z_scope

Span tests

A span test gn of the pointer n0, in a block b of a function f of a checked_module md, tests a nonempty span from offset glo up to ghi, both signed 64-bit offsets. The validator requires this of every span test (valid_op/1); the lemma reads it back through inst_valid.

42Lemma span_test_ok
∀ md f b gn glo ghi n0
glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1
Explore proof 6 tactics

Initial goal

⊢
∀md : module f : func b : block gn : name glo ghi : Z n0 : name, checked_modulemd → InIFuncf md → Inb fn_blocksf → InLetgn W SpanTestglo ghi Tmpn0 b_instsb → glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1

intros md f b gn glo ghi n0 Hmd Hin Hb Hi

md :
f :
gn :
glo, ghi :
Z
n0 :
Hin :
InIFuncf md
Hb :
Hi :
InLetgn W SpanTestglo ghi Tmpn0 b_instsb
⊢
glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1

destruct inst_valid_ _ _ _ Hmd Hin Hb Hi as cls Hv

md :
f :
gn :
glo, ghi :
Z
n0 :
Hin :
InIFuncf md
Hb :
Hi :
InLetgn W SpanTestglo ghi Tmpn0 b_instsb
cls :
listname × class
Hv :
valid_instmd cls Letgn W SpanTestglo ghi Tmpn0 = true
⊢
glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1

simpl in Hv

md :
f :
gn :
glo, ghi :
Z
n0 :
Hin :
InIFuncf md
Hb :
Hi :
InLetgn W SpanTestglo ghi Tmpn0 b_instsb
cls :
listname × class
Hv :
glo <? ghi && −9223372036854775808 ≤? glo && ghi ≤? 9223372036854775807 && true && true
&&
match lookupn0 cls with
Somek0
⇒
→
match k0 with
⇒
true
_
⇒
false
→
match k0 with
⇒
true
_
⇒
false
→
true
else
false
None
⇒
false
&&
true
=
true
⊢
glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1

repeat match goal withH : _ && _ = true |- _⇒apply andb_true_iff in H as ? ?end

md :
f :
gn :
glo, ghi :
Z
n0 :
Hin :
InIFuncf md
Hb :
Hi :
InLetgn W SpanTestglo ghi Tmpn0 b_instsb
cls :
listname × class
H :
glo <? ghi = true
H5 :
−9223372036854775808 ≤? glo = true
H4 :
ghi ≤? 9223372036854775807 = true
H3, H2 :
true = true
H0 :
match lookupn0 cls with
Somek0
⇒
→
match k0 with
⇒
true
_
⇒
false
→
match k0 with
⇒
true
_
⇒
false
→
true
else
false
None
⇒
false
=
true
H1 :
true = true
⊢
glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1

repeat match goal withH : _ <? _ = true |- _⇒apply Z.ltb_lt in HH : _ ≤? _ = true |- _⇒apply Z.leb_le in Hend

md :
f :
gn :
glo, ghi :
Z
n0 :
Hin :
InIFuncf md
Hb :
Hi :
InLetgn W SpanTestglo ghi Tmpn0 b_instsb
cls :
listname × class
H :
glo < ghi
H5 :
−9223372036854775808 ≤ glo
H4 :
ghi ≤ 9223372036854775807
H3, H2 :
true = true
H0 :
match lookupn0 cls with
Somek0
⇒
→
match k0 with
⇒
true
_
⇒
false
→
match k0 with
⇒
true
_
⇒
false
→
true
else
false
None
⇒
false
=
true
H1 :
true = true
⊢
glo < ghi ∧ −2 ^ 63 ≤ glo ∧ ghi ≤ 2 ^ 63 − 1

lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros md f b gn glo ghi n0 Hmd Hin Hb Hi
destruct inst_valid_ _ _ _ Hmd Hin Hb Hi as cls Hv
simpl in Hv
repeat match goal withH : _ && _ = true |- _⇒apply andb_true_iff in H as ? ?end
repeat match goal withH : _ <? _ = true |- _⇒apply Z.ltb_lt in HH : _ ≤? _ = true |- _⇒apply Z.leb_le in Hend
lia

The arithmetic of a guard. Where a span test of a pointer at address B found its span, from L = B+GLo up to H = B+GHi modulo 2^64, inside an object from base up to end_, which ends in the address space (at or below 2^48), an access from A+Lo up to A+Hi, with A = B+X modulo 2^64 and both X+Lo and X+Hi between GLo and GHi, lies inside the object too. H - L is the span's width exactly, since the width is below 2^64.

64Lemma guard_inside
∀ base end_ B x glo ghi A lo hi
base ≤ raw_addressB glo
raw_addressB ghi ≤ end_
end_ ≤ 2 ^ 48
glo < ghi
ghi − glo < 2 ^ 64
A mod 2 ^ 64 = B + x mod 2 ^ 64
glo ≤ x + lo
x + hi ≤ ghi
lo < hi
base ≤ raw_addressA lo ∧ raw_addressA lo + hi − lo ≤ end_
Explore proof 17 tactics

Initial goal

⊢
∀base end_ B x glo ghi A lo hi : Z, base ≤ raw_addressB glo → raw_addressB glo < raw_addressB ghi → raw_addressB ghi ≤ end_ → end_ ≤ 2 ^ 48 → glo < ghi → ghi − glo < 2 ^ 64 → A mod 2 ^ 64 = B + x mod 2 ^ 64 → glo ≤ x + lo → x + hi ≤ ghi → lo < hi → base ≤ raw_addressA lo ∧ raw_addressA lo + hi − lo ≤ end_

intros base end_ B x glo ghi A lo hi Hb HLH Hend Hfit Hg Hw HA Hlo Hhi Hl

base, end_, B, x, glo, ghi, A, lo, hi :
Z
Hb :
base ≤ raw_addressB glo
HLH :
Hend :
raw_addressB ghi ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
⊢
base ≤ raw_addressA lo ∧ raw_addressA lo + hi − lo ≤ end_

unfold raw_address in *

base, end_, B, x, glo, ghi, A, lo, hi :
Z
Hb :
base ≤ B + glo mod 2 ^ 64
HLH :
B + glo mod 2 ^ 64 < B + ghi mod 2 ^ 64
Hend :
B + ghi mod 2 ^ 64 ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

pose proof Z.div_modB + glo 2 ^ 64 ltac:lia as DL

base, end_, B, x, glo, ghi, A, lo, hi :
Z
Hb :
base ≤ B + glo mod 2 ^ 64
HLH :
B + glo mod 2 ^ 64 < B + ghi mod 2 ^ 64
Hend :
B + ghi mod 2 ^ 64 ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
DL :
B + glo = 2 ^ 64 × B + glo / 2 ^ 64 + B + glo mod 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

pose proof Z.div_modB + ghi 2 ^ 64 ltac:lia as DH

base, end_, B, x, glo, ghi, A, lo, hi :
Z
Hb :
base ≤ B + glo mod 2 ^ 64
HLH :
B + glo mod 2 ^ 64 < B + ghi mod 2 ^ 64
Hend :
B + ghi mod 2 ^ 64 ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
DL :
B + glo = 2 ^ 64 × B + glo / 2 ^ 64 + B + glo mod 2 ^ 64
DH :
B + ghi = 2 ^ 64 × B + ghi / 2 ^ 64 + B + ghi mod 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

pose proof Z.mod_pos_boundB + glo 2 ^ 64 ltac:lia as RL

base, end_, B, x, glo, ghi, A, lo, hi :
Z
Hb :
base ≤ B + glo mod 2 ^ 64
HLH :
B + glo mod 2 ^ 64 < B + ghi mod 2 ^ 64
Hend :
B + ghi mod 2 ^ 64 ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
DL :
B + glo = 2 ^ 64 × B + glo / 2 ^ 64 + B + glo mod 2 ^ 64
DH :
B + ghi = 2 ^ 64 × B + ghi / 2 ^ 64 + B + ghi mod 2 ^ 64
RL :
0 ≤ B + glo mod 2 ^ 64 < 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

pose proof Z.mod_pos_boundB + ghi 2 ^ 64 ltac:lia as RH

base, end_, B, x, glo, ghi, A, lo, hi :
Z
Hb :
base ≤ B + glo mod 2 ^ 64
HLH :
B + glo mod 2 ^ 64 < B + ghi mod 2 ^ 64
Hend :
B + ghi mod 2 ^ 64 ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
DL :
B + glo = 2 ^ 64 × B + glo / 2 ^ 64 + B + glo mod 2 ^ 64
DH :
B + ghi = 2 ^ 64 × B + ghi / 2 ^ 64 + B + ghi mod 2 ^ 64
RL :
0 ≤ B + glo mod 2 ^ 64 < 2 ^ 64
RH :
0 ≤ B + ghi mod 2 ^ 64 < 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

set L := B + glo mod 2 ^ 64 in *

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
HLH :
L < B + ghi mod 2 ^ 64
Hend :
B + ghi mod 2 ^ 64 ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
DL :
B + glo = 2 ^ 64 × B + glo / 2 ^ 64 + L
DH :
B + ghi = 2 ^ 64 × B + ghi / 2 ^ 64 + B + ghi mod 2 ^ 64
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ B + ghi mod 2 ^ 64 < 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

set H := B + ghi mod 2 ^ 64 in *

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
DL :
B + glo = 2 ^ 64 × B + glo / 2 ^ 64 + L
DH :
B + ghi = 2 ^ 64 × B + ghi / 2 ^ 64 + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

set qL := B + glo / 2 ^ 64 in *

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
DH :
B + ghi = 2 ^ 64 × B + ghi / 2 ^ 64 + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

set qH := B + ghi / 2 ^ 64 in *

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

assert Eq : qH = qL by lia

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

assert EA : A + lo mod 2 ^ 64 = L + x + lo − glo

2 open

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
⊢
A + lo mod 2 ^ 64 = L + x + lo − glo
focused goal
base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
EA :
A + lo mod 2 ^ 64 = L + x + lo − glo
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

{rewrite <- Z.add_mod_idemp_l , HA , Z.add_mod_idemp_l by lia

2 open

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
⊢
B + x + lo mod 2 ^ 64 = L + x + lo − glo
deferred goal
base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
EA :
A + lo mod 2 ^ 64 = L + x + lo − glo
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

symmetry

2 open

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
⊢
L + x + lo − glo = B + x + lo mod 2 ^ 64
deferred goal
base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
EA :
A + lo mod 2 ^ 64 = L + x + lo − glo
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

apply Z.mod_unique_ _ qL ; lia

deferred goal
base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
EA :
A + lo mod 2 ^ 64 = L + x + lo − glo
⊢
base ≤ A + lo mod 2 ^ 64 ∧ A + lo mod 2 ^ 64 + hi − lo ≤ end_

rewrite EA

base, end_, B, x, glo, ghi, A, lo, hi :
Z
L :=
B + glo mod 2 ^ 64 : Z
Hb :
base ≤ L
H :=
B + ghi mod 2 ^ 64 : Z
HLH :
L < H
Hend :
H ≤ end_
Hfit :
end_ ≤ 2 ^ 48
Hg :
glo < ghi
Hw :
ghi − glo < 2 ^ 64
HA :
A mod 2 ^ 64 = B + x mod 2 ^ 64
Hlo :
glo ≤ x + lo
Hhi :
x + hi ≤ ghi
Hl :
lo < hi
qL :=
B + glo / 2 ^ 64 : Z
DL :
B + glo = 2 ^ 64 × qL + L
qH :=
B + ghi / 2 ^ 64 : Z
DH :
B + ghi = 2 ^ 64 × qH + H
RL :
0 ≤ L < 2 ^ 64
RH :
0 ≤ H < 2 ^ 64
Eq :
qH = qL
EA :
A + lo mod 2 ^ 64 = L + x + lo − glo
⊢
base ≤ L + x + lo − glo ∧ L + x + lo − glo + hi − lo ≤ end_

lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros base end_ B x glo ghi A lo hi Hb HLH Hend Hfit Hg Hw HA Hlo Hhi Hl
unfold raw_address in *
pose proof Z.div_modB + glo 2 ^ 64 ltac:lia as DL
pose proof Z.div_modB + ghi 2 ^ 64 ltac:lia as DH
pose proof Z.mod_pos_boundB + glo 2 ^ 64 ltac:lia as RL
pose proof Z.mod_pos_boundB + ghi 2 ^ 64 ltac:lia as RH
set L := B + glo mod 2 ^ 64 in *
set H := B + ghi mod 2 ^ 64 in *
set qL := B + glo / 2 ^ 64 in *
set qH := B + ghi / 2 ^ 64 in *

The two reductions take off the same multiple of 2^64.

assert Eq : qH = qL by lia
assert EA : A + lo mod 2 ^ 64 = L + x + lo − glo
{rewrite <- Z.add_mod_idemp_l , HA , Z.add_mod_idemp_l by lia
symmetry
apply Z.mod_unique_ _ qL ; lia
rewrite EA
lia

A renew through a pointer p with an object's capability c, of an access from a up to a + size inside that object as a memory m1 had it, in a memory m that persists from m1, traps misaligned, or renews (renew_res/4): it passes, traps read-only, or finds the object freed (kind_res/8). It is never unchecked.

91Lemma renew_inside
∀ m1 m c base reg a size r al p
c = Objbase ∨ c = Robase
object_regionbase m_regionsm1 = Somereg
base ≤ a
a + size ≤ r_endreg
0 < size
ptr_capp = c
∃chk, access_resm a c size r al = Somechk ∧ chk = RTrapMisaligned ∨ ∃rr, renew_reschk p m = Somerr ∧ ∀why, rr ≠ RUncheckedwhy
Explore proof 30 tactics

Initial goal

⊢
∀m1 m : Memory.mem c : cap base : Z reg : region a size : Z r : rights al : Z p : ptr, c = Objbase ∨ c = Robase → object_regionbase m_regionsm1 = Somereg → base ≤ a → a + size ≤ r_endreg → 0 < size → persistsm1 m → ptr_capp = c → ∃chk : resunit, access_resm a c size r al = Somechk ∧ chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

intros m1 m c base reg a size r al p Hc E Hb He Hs Hp Hpc

m1, m :
Memory.mem
c :
base :
Z
reg :
a, size :
Z
al :
Z
p :
Hc :
c = Objbase ∨ c = Robase
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = c
⊢
∃chk : resunit, access_resm a c size r al = Somechk ∧ chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

pose proof object_region_base_ _ _ E as Hrb

m1, m :
Memory.mem
c :
base :
Z
reg :
a, size :
Z
al :
Z
p :
Hc :
c = Objbase ∨ c = Robase
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = c
Hrb :
r_basereg = base
⊢
∃chk : resunit, access_resm a c size r al = Somechk ∧ chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

unfold access_res , cap_access_res , readonly_access_res , aligned_res

m1, m :
Memory.mem
c :
base :
Z
reg :
a, size :
Z
al :
Z
p :
Hc :
c = Objbase ∨ c = Robase
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = c
Hrb :
r_basereg = base
⊢
∃ chk : resunit  ,
match c with
Objbase0
⇒
let* reg0 ≔ object_regionbase0 m_regionsm in
Some
base0 ≤? a && a + size ≤? r_endreg0
→
a mod al =? 0
→
Robase0
⇒
let* reg0 ≔ object_regionbase0 m_regionsm in
Some
base0 ≤? a && a + size ≤? r_endreg0
→
match r with
⇒
a mod al =? 0
→
⇒
None
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

destruct Hp_ _ E as E′ | E′ ; destruct Hc as → | → ; rewrite E′

4 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
focused goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
focused goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
focused goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

–replace base ≤? a && a + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia

4 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

destruct a mod al =? 0 ; eexists ; split ; reflexivity | ; right | left ; reflexivity

4 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃rr : resword, renew_resok p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

eexists

5 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
renew_resok p m = Some?rr ∧ ∀why : reason, ?rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
shelved goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg

split ; reflexivity | discriminate

3 open

deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

–replace base ≤? a && a + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia

3 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
object_regionbase m_regionsm = Somereg
⊢
∃ chk : resunit  ,
Some
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

destruct r ; destruct a mod al =? 0 | ; eexists ; split ; reflexivity | ; first left ; reflexivity | right ; eexists ; split ; reflexivity | discriminate

2 open

deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

–simpl

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_basereg
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

rewrite Hrb

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? base
→
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

replace base ≤? a && a + size ≤? base with false by symmetry ; apply andb_false_iff ; destruct Z.le_gt_casesbase a ; right ; apply Z.leb_gt ; lia | left ; apply Z.leb_gt ; lia

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃chk : resunit, SomeRTrapOutOfBounds = Somechk ∧ chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

eexists

3 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
SomeRTrapOutOfBounds = Some?chk ∧ ?chk = RTrapMisaligned ∨ ∃rr : resword, renew_res?chk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
shelved goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
resunit

split ; reflexivity |

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
RTrapOutOfBounds = RTrapMisaligned ∨ ∃rr : resword, renew_resRTrapOutOfBounds p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

right

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃rr : resword, renew_resRTrapOutOfBounds p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

unfold renew_res

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ rr : resword  ,
match ptr_capp with
Objbase0 | Robase0
⇒
let* reg0 ≔ object_regionbase0 m_regionsm in
=
Somerr
∧
∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

rewrite Hpc , E′

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∃ rr : resword  ,
∧
∀why : reason, rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

eexists

3 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :
⊢
∧
∀why : reason, ?rr ≠ RUncheckedwhy
deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
shelved goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Objbase
Hrb :
r_basereg = base
E′ :

split ; reflexivity | discriminate

deferred goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_endfreed_regionreg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

–simpl

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? r_basereg
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

rewrite Hrb

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ chk : resunit  ,
Some
base ≤? a && a + size ≤? base
→
match r with
⇒
a mod al =? 0
→
=
Somechk
∧
chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

replace base ≤? a && a + size ≤? base with false by symmetry ; apply andb_false_iff ; destruct Z.le_gt_casesbase a ; right ; apply Z.leb_gt ; lia | left ; apply Z.leb_gt ; lia

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃chk : resunit, SomeRTrapOutOfBounds = Somechk ∧ chk = RTrapMisaligned ∨ ∃rr : resword, renew_reschk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

eexists

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
SomeRTrapOutOfBounds = Some?chk ∧ ?chk = RTrapMisaligned ∨ ∃rr : resword, renew_res?chk p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy
shelved goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
resunit

split ; reflexivity |

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
RTrapOutOfBounds = RTrapMisaligned ∨ ∃rr : resword, renew_resRTrapOutOfBounds p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

right

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃rr : resword, renew_resRTrapOutOfBounds p m = Somerr ∧ ∀why : reason, rr ≠ RUncheckedwhy

unfold renew_res

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ rr : resword  ,
match ptr_capp with
Objbase0 | Robase0
⇒
let* reg0 ≔ object_regionbase0 m_regionsm in
=
Somerr
∧
∀why : reason, rr ≠ RUncheckedwhy

rewrite Hpc , E′

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∃ rr : resword  ,
∧
∀why : reason, rr ≠ RUncheckedwhy

eexists

2 open

m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :
⊢
∧
∀why : reason, ?rr ≠ RUncheckedwhy
shelved goal
m1, m :
Memory.mem
base :
Z
reg :
a, size :
Z
al :
Z
p :
E :
object_regionbase m_regionsm1 = Somereg
Hb :
base ≤ a
He :
a + size ≤ r_endreg
Hs :
0 < size
Hp :
Hpc :
ptr_capp = Robase
Hrb :
r_basereg = base
E′ :

split ; reflexivity | discriminate

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m1 m c base reg a size r al p Hc E Hb He Hs Hp Hpc
pose proof object_region_base_ _ _ E as Hrb
destruct Hp_ _ E as E′ | E′ ; destruct Hc as → | → ; rewrite E′

an object as it was: the access is inside

–replace base ≤? a && a + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia
destruct a mod al =? 0 ; eexists ; split ; reflexivity | ; right | left ; reflexivity
eexists
split ; reflexivity | discriminate

a read-only object as it was

–replace base ≤? a && a + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia
destruct r ; destruct a mod al =? 0 | ; eexists ; split ; reflexivity | ; first left ; reflexivity | right ; eexists ; split ; reflexivity | discriminate

freed since: out of bounds, on a freed object

–simpl
rewrite Hrb
replace base ≤? a && a + size ≤? base with false by symmetry ; apply andb_false_iff ; destruct Z.le_gt_casesbase a ; right ; apply Z.leb_gt ; lia | left ; apply Z.leb_gt ; lia
eexists
split ; reflexivity |
right
unfold renew_res
rewrite Hpc , E′
eexists
split ; reflexivity | discriminate
–simpl
rewrite Hrb
replace base ≤? a && a + size ≤? base with false by symmetry ; apply andb_false_iff ; destruct Z.le_gt_casesbase a ; right ; apply Z.leb_gt ; lia | left ; apply Z.leb_gt ; lia
eexists
split ; reflexivity |
right
unfold renew_res
rewrite Hpc , E′
eexists
split ; reflexivity | discriminate

The result a check makes of an access test chk (checked_res) is never unchecked, since the access test itself never is.

128Lemma checked_res_access
∀ m a c size r al chk w why
access_resm a c size r al = Somechk
checked_reschk w ≠ RUncheckedwhy
Explore proof 4 tactics

Initial goal

⊢
∀m : Memory.mem a : Z c : cap size : Z r : rights al : Z chk : resunit w : word why : reason, access_resm a c size r al = Somechk → checked_reschk w ≠ RUncheckedwhy

intros m a c size r al chk w why H E

m :
Memory.mem
a :
Z
c :
size :
Z
al :
Z
chk :
resunit
w :
why :
H :
access_resm a c size r al = Somechk
E :
⊢
False

destruct chk ; try discriminate E

m :
Memory.mem
a :
Z
c :
size :
Z
al :
Z
r0 :
w :
why :
H :
access_resm a c size r al = SomeRUncheckedr0
⊢
False

injection E as →

m :
Memory.mem
a :
Z
c :
size :
Z
al :
Z
w :
why :
H :
access_resm a c size r al = SomeRUncheckedwhy
⊢
False

exact cap_access_res_checked_ _ _ _ _ _ _ H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros m a c size r al chk w why H E
destruct chk ; try discriminate E
injection E as →
exact cap_access_res_checked_ _ _ _ _ _ _ H

If the lower chain of a value d reaches a single-definition name n0 (lower_chain/3), d is a single-definition name too, or not a name at all.

138Lemma lower_chain_once
∀ once fuel d n0 y
once_hasonce n0 = true
lower_chainonce fuel d Tmpn0 = true
d = Tmpy
once_hasonce y = true
Explore proof 9 tactics

Initial goal

⊢
∀once : listname × def fuel : nat d : value n0 : name, once_hasonce n0 = true → lower_chainonce fuel d Tmpn0 = true → ∀y : name, d = Tmpy → once_hasonce y = true

intros once fuel d n0 Ho H y →

once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
lower_chainonce fuel Tmpy Tmpn0 = true
⊢
once_hasonce y = true

destruct fuel as | fuel ; simpl in H

2 open

once :
listname × def
n0 :
Ho :
once_hasonce n0 = true
y :
H :
name_eqby n0 || false = true
⊢
once_hasonce y = true
focused goal
once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
||
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
once_hasonce y = true

–rewrite orb_false_r in H

2 open

once :
listname × def
n0 :
Ho :
once_hasonce n0 = true
y :
H :
name_eqby n0 = true
⊢
once_hasonce y = true
deferred goal
once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
||
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
once_hasonce y = true

apply name_eqb_true in H

2 open

once :
listname × def
n0 :
Ho :
once_hasonce n0 = true
y :
H :
y = n0
⊢
once_hasonce y = true
deferred goal
once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
||
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
once_hasonce y = true

subst

2 open

once :
listname × def
n0 :
Ho :
once_hasonce n0 = true
⊢
once_hasonce n0 = true
deferred goal
once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
||
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
once_hasonce y = true

exact Ho

deferred goal
once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
||
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
once_hasonce y = true

–apply orb_true_iff in H as H | H ; apply name_eqb_true in H ; subst ; exact Ho |

once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
once_hasonce y = true

unfold once_has

once :
listname × def
fuel :
nat
n0 :
Ho :
once_hasonce n0 = true
y :
H :
match lookupy once with
⇒
lower_chainonce fuel d Tmpn0
_
⇒
false
=
true
⊢
match lookupy once with
Some_
⇒
true
None
⇒
false
=
true

destruct lookupy once ; reflexivity | discriminate H

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros once fuel d n0 Ho H y →
destruct fuel as | fuel ; simpl in H
–rewrite orb_false_r in H
apply name_eqb_true in H
subst
exact Ho
–apply orb_true_iff in H as H | H ; apply name_eqb_true in H ; subst ; exact Ho |
unfold once_has
destruct lookupy once ; reflexivity | discriminate H

The frame lemmas: a frame fr runs a function of a checked_module md, in memory m, at index k of a reachable block l, and every single definition in scope but a check_ahead replays (scope_plain).

152Section Guard
154Variables ge : genv
154Variables md : module
154Variables fr : frame
154Variables m : Memory.mem
154Variables l : name
154Variables k : Z
155Hypothesis Hmd
156Hypothesis Hin
157Hypothesis Hr
158Hypothesis Hs
159Hypothesis Hpt

A span test gn of the pointer n0, both single definitions, whose site dominates the frame's point, holds an integer v. Where v is not 0, n0 holds a pointer pb of an object whose span from offset glo up to ghi the test found inside the object, in a memory m1 that lay in the address space and that the current memory persists from.

167Lemma span_guard_holds
∀ gn glo ghi n0
∃v, lookupgn fr_envfr = SomeWIntv ∧ v ≠ 0 → ∃pb base reg m1, lookupn0 fr_envfr = SomeWPtrpb ∧ ptr_cappb = Objbase ∨ ptr_cappb = Robase ∧ object_regionbase m_regionsm1 = Somereg ∧ base ≤ raw_addressptr_addrpb glo ∧ raw_addressptr_addrpb glo < raw_addressptr_addrpb ghi ∧ raw_addressptr_addrpb ghi ≤ r_endreg ∧ persistsm1 m ∧ objects_fitm_regionsm1
Proof 19 steps Qed
intros gn glo ghi n0 Hgn Ho Hdom
destruct plain_replays_ _ _ _ _ _ _ Hs Hpt Hgn eq_refl eq_refl Hdom as fr0 & m0 & e1 & l1 & m1 & Hst & He1 & Hops & Hp & Hfit
pose proof Hopsn0 or_introleq_refl Ho as En0
rewrite inst_step_let in Hst by reflexivity
rewrite En0 in Hst
destruct lookupn0 fr_envfr as w | eqn: Ew ; | discriminate Hst
destruct w as u | pb | c0 sz ; simpl in Hst ; try discriminate Hst
unfold op_res , op_res_int in Hst
cbn beta iota zeta in Hst
destruct ptr_cappb as | base | base | fn | x eqn: Ec

A capability that is not an object's: the test holds 0.

all: try injection Hst as ← _ _ ; rewrite lookup_put , name_eqb_refl in He1 ; exists 0 ; split ; symmetry ; exact He1 | intros ; reflexivity
all: destruct object_regionbase m_regionsm0 as reg | eqn: E ; | discriminate Hst
all: injection Hst as ← _ ← ; rewrite lookup_put , name_eqb_refl in He1
all: eexists ; split ; symmetry ; exact He1 | ; intros Hv
all: destruct _ && _ eqn: Eb ; | exfalso ; exact Hveq_refl
all: repeat rewrite andb_true_iff in Eb ; destruct Eb as E1 & E2 & E3
all: apply Z.leb_le in E1 , E3 ; apply Z.ltb_lt in E2
all: exists pb, base, reg, m0 ; auto 10

A pointer value p whose lower chain reaches the single-definition name n0 (lower_chain/3), where p's single definition dominates the point, has the capability of the pointer n0 holds. Each step of the chain is a flight, whose capability is its lower donor's (flight_cap/4).

204Lemma lower_chain_sound
∀ fuel p pp n0
∃pn, value_xge fr_envfr P Tmpn0 = SomeWPtrpn ∧ ptr_cappn = ptr_cappp
Proof 36 steps Qed
induction fuel as | fuel IH ; intros p pp n0 Hp Hdom Ho H
–simpl in H
rewrite orb_false_r in H
apply value_eqb_eq in H
subst
eauto
–simpl in H
apply orb_true_iff in H as H | H ; apply value_eqb_eq in H ; subst ; eauto |
destruct p as x | c | g ; try discriminate H
destruct lookupx single_definitionsfr_fnfr as | ph | i | eqn: Ex ; try discriminate H
destruct i as | d o args lw | | | | | | | ; try discriminate H
destruct lw as | b ; try discriminate H
pose proof flight_def_name_ _ _ _ _ _ Ex as →
assert Hox : once_hassingle_definitionsfr_fnfr x = true by unfold once_has ; rewrite Ex ; reflexivity
pose proof Hdomx eq_refl Hox as Hdx
destruct plain_replays_ _ _ _ _ _ _ Hs Hpt Ex eq_refl eq_refl Hdx as fr0 & m0 & e1 & l1 & m1 & Hst & Hx1 & Hops & _

The lower donor b reads now what it read then.

assert Hub : ∀y, b = Tmpy → Iny inst_usesFlightx o args LowerOfb by intros y → ; simpl ; apply value_temps_in , in_or_app ; right ; left ; reflexivity
pose proof lower_chain_once_ _ _ _ Ho H as Hob
assert Hbe : value_xge fr_envfr0 P b = value_xge fr_envfr P b by apply value_x_agree ; intros y E ; exact Hops_ Huby E Hoby E
simpl in Hst
unfold flight_cap in Hst
rewrite Hbe in Hst
destruct map_option_ args as xs | ; | discriminate Hst
simpl in Hst
destruct aluo L xs as a | ; | discriminate Hst
simpl in Hst
destruct value_xge fr_envfr P b as u | pb | c0 s0 | eqn: Eb ; simpl in Hst ; try discriminate Hst
destruct a as n | | ; try discriminate Hst
injection Hst as ← _ _
rewrite lookup_put , name_eqb_refl in Hx1
simpl in Hp
rewrite <- Hx1 in Hp
simpl in Hp
injection Hp as ←
simpl
exact IHb pb n0 Eb λy E Hoy ⇒ operand_dominating_ _ _ _ _ _ _ Hmd Hin Hr Ex Hdx Huby E Hoy Ho H

A renew_if of a pointer p with guard g, the instruction at index k of block b, that the pass accepts (checked_inst_rest, which asks guard_covers/5) does not step to unchecked. Either its guard is 0 and it checks, which is never unchecked; or its span test passed (span_guard_holds), the renewed span lies inside the tested one (guard_inside), and so it renews (renew_inside).

244Theorem renew_if_not_unchecked
∀ b kk q lo hi r al p g rest live out why
nth_errorb_instsb kk = SomeLetq A RenewIflo hi r al p; g
k = Z.of_natkk
checked_inst_restfn_srcmd fr_fnfr Letq A RenewIflo hi r al p; g rest live = Someout
inst_stepge fr m Letq A RenewIflo hi r al p; g ≠ SomeIStopUncheckedwhy
Proof 68 steps Qed
intros b kk q lo hi r al p g rest live out why Hb Hk Hkk H
set i := Letq A RenewIflo hi r al p; g in Hk

What the pass checked: a span test of N0 whose span covers P's.

unfold checked_inst_rest in H
cbn beta iota zeta in H
destruct guard_covers_ p g lo hi eqn: Eg ; clear H | discriminate H
unfold guard_covers in Eg
destruct g as gn | | ; try discriminate Eg
destruct lookupgn s_oncefn_srcmd fr_fnfr as | | gi | eqn: Egn ; try discriminate Eg
destruct gi as gn′ gk go gargs | | | | | | | | ; try discriminate Eg
destruct gk ; try discriminate Eg
destruct go ; try discriminate Eg
destruct gargs as | n0 | | | ; try discriminate Eg
repeat rewrite andb_true_iff in Eg
destruct Eg as Egn′ & Ho & Ech
apply name_eqb_true in Egn'
subst gn'
rename lo0 into glo , hi0 into ghi
destruct first_some_ guard_chain_ p as olo ohi | eqn: Ef ; | discriminate Ech
apply andb_true_iff in Ech as E1 E2
apply Z.leb_le in E1 , E2

A function with a setjmp has no single definitions.

destruct fn_src_casesmd fr_fnfr as _ Es | _ Es ; rewrite Es in Egn ; cbn [ s_once ] in Egn ; discriminate Egn |
try rewrite Es in Ho ; cbn [ s_once ] in Ho
try rewrite Es in Ef ; cbn [ s_once ] in Ef

The step, with the operands it reads.

intros Hst
rewrite inst_step_let in Hst by reflexivity
destruct value_xge fr_envfr P p as u | pp | c0 s0 | eqn: Ep ; destruct value_xge fr_envfr W Tmpgn as gv | pg | cg sg | eqn: Ev ; simpl in Hst ; try discriminate Hst ; unfold op_res , op_res_int in Hst ; cbn beta iota zeta in Hst ; try discriminate Hst
destruct access_resm raw_addressptr_addrpp lo ptr_cappp hi − lo r al as chk | eqn: Echk ; | discriminate Hst
cbn beta iota in Hst
destruct gv =? 0 eqn: Eg0

a guard of 0: a check

{injection Hst as Hst
unfold bind_res in Hst
destruct checked_reschk WPtrpp eqn: Ec ; try discriminate Hst
injection Hst as ←
exact checked_res_access_ _ _ _ _ _ _ _ _ Echk Ec

The guard is not 0: its span test found N0's span inside its object.

assert Hdg : dominatingfr_fnfr l k gn by apply operand_atmd fr l k Hmd Hin Hr Hpt b kk i gn Hb Hk Hkk ; unfold i ; simpl ; apply in_or_app ; right ; left ; reflexivity | unfold once_has ; rewrite Egn ; reflexivity
destruct span_guard_holdsgn glo ghi n0 Egn Ho Hdg as v & Ev′ & Hspan
simpl in Ev
rewrite Ev' in Ev
simpl in Ev
injection Ev as ←
destruct Hspanltac:intros → ; discriminate Eg0 as pb & base & reg & m1 & En0 & Hc & E & Hb1 & HLH & Hend & Hp & Hfit

P is a known offset from N0, by its guard chain.

destruct first_some_in_ _ _ _ _ Ef as v0 olo′ ohi′ & Hel & Hf
simpl in Hf
destruct value_eqbv0 Tmpn0 eqn: Ev0 ; | discriminate Hf
apply value_eqb_eq in Ev0
subst v0
injection Hf as → →
assert Hdp : ∀y, p = Tmpy → once_hassingle_definitionsfr_fnfr y = true → dominatingfr_fnfr l k y by intros y → Hoy ; exact operand_atmd fr l k Hmd Hin Hr Hpt b kk i y Hb Hk Hkk ltac:unfold i ; simpl ; auto Hoy
assert Hst0 : stablesingle_definitionsfr_fnfr Tmpn0 by intros y E′ ; injection E' as ← ; exact Ho
destruct guard_chain_soundge md fr m l k Hmd Hin Hr Hs Hpt p pp Tmpn0 olo ohi Ep Hdp Hel Hst0 as pb′ & x & Hpb & Hcap & Hx & Haddr
simpl in Hpb
rewrite En0 in Hpb
injection Hpb as ←

Sizes the validator guarantees.

destruct find_block_in_ _ _ Hb as Hbin _
destruct check_fact_ok_ _ _ _ _ Hmd Hin Hbin nth_error_In_ _ Hk eq_refl as Hsz _
simpl in Hsz
destruct once_position_ _ _ Egn as sg & Hpos & _
destruct dinst_site_ _ _ _ Hpos as d & j & →
destruct position_inst_ _ _ _ _ Hpos as bg & kg & Hbg & _ & Hkg & _ & _
destruct span_test_ok_ _ _ _ _ _ _ Hmd Hin Hbg nth_error_In_ _ Hkg as Hgw & Hglo & Hghi
destruct guard_insidebase r_endreg ptr_addrpb x glo ghi ptr_addrpp lo hi Hb1 HLH Hend proj2Hfit_ _ E Hgw ltac:lia Haddr ltac:lia ltac:lia Hsz as Hi1 Hi2

The renew of an access inside the object.

rewrite Hcap in Hc
destruct renew_insidem1 m ptr_cappp base reg raw_addressptr_addrpp lo hi − lo r al pp Hc E Hi1 Hi2 ltac:lia Hp eq_refl as chk′ & Echk′ & Hres
rewrite Echk in Echk'
injection Echk' as ←
destruct Hres as → | rr & Hrr & Hnot ; discriminate Hst |
destruct chk as | | w ; try rewrite Hrr in Hst ; cbn beta iota in Hst ; injection Hst as Hst ; unfold bind_res in Hst ; destruct rr ; try discriminate Hst ; injection Hst as ← ; exact Hnot_ eq_refl ; discriminate Hst

A check_limit of a pointer p with limit u, the instruction at index k of block b, that the pass accepts (checked_inst_rest, which asks limit_covers/5) does not step to unchecked. Its limit u holds the capability of a pointer N0 and the check's span as its size, and p has N0's capability (lower_chain_sound), so the limit matches and the instruction checks.

327Theorem check_limit_not_unchecked
∀ b kk q lo hi r al p u rest live out why
nth_errorb_instsb kk = SomeLetq A CheckLimitlo hi r al p; u
k = Z.of_natkk
checked_inst_restfn_srcmd fr_fnfr Letq A CheckLimitlo hi r al p; u rest live = Someout
inst_stepge fr m Letq A CheckLimitlo hi r al p; u ≠ SomeIStopUncheckedwhy
Proof 48 steps Qed
intros b kk q lo hi r al p u rest live out why Hb Hk Hkk H
set i := Letq A CheckLimitlo hi r al p; u in Hk

What the pass checked: a limit of N0 of the check's span, and P's lower chain reaches N0.

unfold checked_inst_rest in H
cbn beta iota zeta in H
destruct limit_covers_ p u lo hi eqn: Eu ; clear H | discriminate H
unfold limit_covers in Eu
destruct u as un | | ; try discriminate Eu
destruct lookupun s_oncefn_srcmd fr_fnfr as | | ui | eqn: Eun ; try discriminate Eu
destruct ui as un′ uk uo uargs | | | | | | | | ; try discriminate Eu
destruct uk ; try discriminate Eu
destruct uo ; try discriminate Eu
destruct uargs as | n0 | | | ; try discriminate Eu
repeat rewrite andb_true_iff in Eu
destruct Eu as Eun′ & Elo & Ehi & Ho & Hlc
apply name_eqb_true in Eun'
subst un'
apply Z.eqb_eq in Elo , Ehi
subst lo hi

A function with a setjmp has no single definitions.

destruct fn_src_casesmd fr_fnfr as _ Es | _ Es ; rewrite Es in Eun ; cbn [ s_once ] in Eun ; discriminate Eun |
try rewrite Es in Ho ; cbn [ s_once ] in Ho
try rewrite Es in Hlc ; cbn [ s_once ] in Hlc

The limit holds N0's capability and the size it read.

assert Hdu : dominatingfr_fnfr l k un by apply operand_atmd fr l k Hmd Hin Hr Hpt b kk i un Hb Hk Hkk ; unfold i ; simpl ; apply in_or_app ; right ; left ; reflexivity | unfold once_has ; rewrite Eun ; reflexivity
destruct plain_replays_ _ _ _ _ _ _ Hs Hpt Eun eq_refl eq_refl Hdu as fr0 & m0 & e1 & l1 & m1 & Hst0 & He1 & Hops & _
pose proof Hopsn0 or_introleq_refl Ho as En0
rewrite inst_step_let in Hst0 by reflexivity
rewrite En0 in Hst0
destruct lookupn0 fr_envfr as w | pn | cn sn | eqn: Ew ; simpl in Hst0 ; try discriminate Hst0
injection Hst0 as ← _ _
rewrite lookup_put , name_eqb_refl in He1

The step.

intros Hst
rewrite inst_step_let in Hst by reflexivity
replace value_xge fr_envfr L Tmpun with SomeWLimitptr_cappn size in Hst by simpl ; rewrite <- He1 ; reflexivity
destruct value_xge fr_envfr P p as x | pp | c0 s0 | eqn: Ep ; simpl in Hst ; try discriminate Hst ; unfold op_res , op_res_int in Hst ; cbn beta iota zeta in Hst ; try discriminate Hst

P has N0's capability.

assert Hdp : ∀y, p = Tmpy → once_hassingle_definitionsfr_fnfr y = true → dominatingfr_fnfr l k y by intros y → Hoy ; exact operand_atmd fr l k Hmd Hin Hr Hpt b kk i y Hb Hk Hkk ltac:unfold i ; simpl ; auto Hoy
destruct lower_chain_sound64 p pp n0 Ep Hdp Ho Hlc as pn′ & Epn & Hcap
simpl in Epn
rewrite Ew in Epn
injection Epn as ←
rewrite Hcap , cap_eqb_refl , Z.sub_0_r , Z.eqb_refl in Hst
cbn beta iota in Hst
destruct access_resm raw_addressptr_addrpp 0 ptr_cappp size r al as chk | eqn: Echk ; cbn beta iota in Hst ; | discriminate Hst
injection Hst as Hst
unfold bind_res in Hst
destruct checked_reschk WPtrpp eqn: Ec ; try discriminate Hst
injection Hst as ←
exact checked_res_access_ _ _ _ _ _ _ _ _ Echk Ec

Along every run

The instructions this file covers: a let of a renew_if or a check_limit, of any class and operands. Neither is a raw access.

388Definition guard_formi : inst : Prop ≔
∃q kc lo hi r al args, i = Letq kc RenewIflo hi r al args ∨ ∃q kc lo hi r al args, i = Letq kc CheckLimitlo hi r al args

A renew_if or check_limit that steps to unchecked is of the proof class A with two operands (op_arg_classes/4, kind_res/8); of any other shape it does not step at all. So the run theorem covers every such instruction with the frame lemmas, which take only that shape.

397Lemma guard_shape
∀ ge fr m i why
∃q o a1 a2, i = Letq A o a1; a2 ∧ ∃lo hi r al, o = RenewIflo hi r al ∨ ∃lo hi r al, o = CheckLimitlo hi r al
Explore proof 1 tactics

Initial goal

⊢
∀ge : genv fr : frame m : Memory.mem i : inst why : reason, guard_formi → inst_stepge fr m i = SomeIStopUncheckedwhy → ∃q : name o : op a1 a2 : value, i = Letq A o a1; a2 ∧ ∃lo hi : Z r : rights al : Z, o = RenewIflo hi r al ∨ ∃lo hi : Z r : rights al : Z, o = CheckLimitlo hi r al

intros ge fr m i why q & kc & lo & hi & r & al & args & → | q & kc & lo & hi & r & al & args & → H ; rewrite inst_step_let in H by reflexivity ; cbn beta iota zeta delta [ op_arg_classes ] in H ; destruct map2_option_ _ args as xs | eqn: Ex ; try discriminate H ; destruct map2_option_two_ _ _ _ _ _ _ _ Ex as a1 & a2 & → ; destruct kc ; unfold op_res , op_res_int in H ; cbn beta iota zeta delta [ fmt_of ] in H ; try discriminate H ; eauto 12

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge fr m i why q & kc & lo & hi & r & al & args & → | q & kc & lo & hi & r & al & args & → H ; rewrite inst_step_let in H by reflexivity ; cbn beta iota zeta delta [ op_arg_classes ] in H ; destruct map2_option_ _ args as xs | eqn: Ex ; try discriminate H ; destruct map2_option_two_ _ _ _ _ _ _ _ Ex as a1 & a2 & → ; destruct kc ; unfold op_res , op_res_int in H ; cbn beta iota zeta delta [ fmt_of ] in H ; try discriminate H ; eauto 12

The frame lemmas carried along every run of the machine of a runtime R, as Renew.v's Reuse carries its own.

412Module Guards R : Runtime
414Module G ≔ Reuse R

In every state a run reaches from a call of a function f of a checked_module md, started in a memory where the runtime is ready, a frame that is not doomed runs no renew_if and no check_limit to an unchecked outcome. Every runtime spares the pass's facts at safepoints (spares_any; see The evidence invariant over runs).

422Theorem run_guard_checked
∀ ge md f xs fr m fuel s0 c s l i rest j why
ge_modulege = md
ge_freege = R.free
InIFuncf md
call_framef xs = Somefr
R.readys0 m
G.H.P.I.RM.mreachablege mkConfigfr [ ] m fuel, s0 c, s
fr_atc_framec = Execl i :: rest j
Explore proof 6 tactics

Initial goal

⊢
∀ge : genv md : module f : func xs : listword fr : frame m : Memory.mem fuel : Z s0 : R.state c : config s : R.state l : name i : inst rest : listinst j : jump why : reason, checked_modulemd → ge_modulege = md → ge_freege = R.free → InIFuncf md → call_framef xs = Somefr → R.readys0 m → G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → guard_formi → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy

intros ge md f xs fr m fuel s0 c s l i rest j why Hmd Hge Hfree Hin Hcf H0 Hreach Hd Ha Hi Hst

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
i :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
Hst :
⊢
False

destruct guard_shape_ _ _ _ _ Hi Hst as q & o & a1 & a2 & → & Ho

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
q :
o :
a1, a2 :
Hst :
inst_stepge c_framec c_memc Letq A o a1; a2 = SomeIStopUncheckedwhy
Hi :
guard_formLetq A o a1; a2
Ha :
fr_atc_framec = Execl Letq A o a1; a2 :: rest j
Ho :
∃lo hi : Z r : rights al : Z, o = RenewIflo hi r al ∨ ∃lo hi : Z r : rights al : Z, o = CheckLimitlo hi r al
⊢
False

destruct G.run_point_ _ _ _ _ _ _ _ _ _ _ _ _ _ Hmd Hge Hfree Hin Hcf H0 Hreach Hd Ha ltac:destruct Ho as ? & ? & ? & ? & → | ? & ? & ? & ? & → ; reflexivity ltac:intros ? ? ? E ; discriminate E ltac:intros ? E ; discriminate E as b & kk & live & out & Hinf & Hr & Hsc & Hpt & Hb & Hnth & Hc & _ & _

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
q :
o :
a1, a2 :
Hst :
inst_stepge c_framec c_memc Letq A o a1; a2 = SomeIStopUncheckedwhy
Hi :
guard_formLetq A o a1; a2
Ha :
fr_atc_framec = Execl Letq A o a1; a2 :: rest j
Ho :
∃lo hi : Z r : rights al : Z, o = RenewIflo hi r al ∨ ∃lo hi : Z r : rights al : Z, o = CheckLimitlo hi r al
kk :
nat
live :
listfact
out :
listinst × listfact
Hinf :
Hpt :
point_sitefr_fnc_framec fr_atc_framec = Somel, Z.of_natkk
Hnth :
nth_errorb_instsb kk = SomeLetq A o a1; a2
Hc :
checked_inst_restfn_srcmd fr_fnc_framec Letq A o a1; a2 rest live = Someout
⊢
False

destruct Ho as lo & hi & r & al & → | lo & hi & r & al & →

2 open

ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
q :
a1, a2 :
lo, hi :
Z
al :
Z
Ha :
fr_atc_framec = Execl Letq A RenewIflo hi r al a1; a2 :: rest j
Hi :
guard_formLetq A RenewIflo hi r al a1; a2
Hst :
inst_stepge c_framec c_memc Letq A RenewIflo hi r al a1; a2 = SomeIStopUncheckedwhy
kk :
nat
live :
listfact
out :
listinst × listfact
Hinf :
Hpt :
point_sitefr_fnc_framec fr_atc_framec = Somel, Z.of_natkk
Hc :
checked_inst_restfn_srcmd fr_fnc_framec Letq A RenewIflo hi r al a1; a2 rest live = Someout
Hnth :
nth_errorb_instsb kk = SomeLetq A RenewIflo hi r al a1; a2
⊢
False
focused goal
ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
q :
a1, a2 :
lo, hi :
Z
al :
Z
Ha :
fr_atc_framec = Execl Letq A CheckLimitlo hi r al a1; a2 :: rest j
Hi :
guard_formLetq A CheckLimitlo hi r al a1; a2
Hst :
inst_stepge c_framec c_memc Letq A CheckLimitlo hi r al a1; a2 = SomeIStopUncheckedwhy
kk :
nat
live :
listfact
out :
listinst × listfact
Hinf :
Hpt :
point_sitefr_fnc_framec fr_atc_framec = Somel, Z.of_natkk
Hc :
checked_inst_restfn_srcmd fr_fnc_framec Letq A CheckLimitlo hi r al a1; a2 rest live = Someout
Hnth :
nth_errorb_instsb kk = SomeLetq A CheckLimitlo hi r al a1; a2
⊢
False

–exact renew_if_not_uncheckedge md c_framec c_memc l Z.of_natkk Hmd Hinf Hr scope_plain_of_ _ _ Hsc Hpt b kk q lo hi r al a1 a2 rest live out why Hb Hnth eq_refl Hc Hst

deferred goal
ge :
md :
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
s0 :
R.state
s :
R.state
l :
rest :
listinst
j :
why :
Hge :
ge_modulege = md
Hfree :
ge_freege = R.free
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
H0 :
R.readys0 m
Hreach :
G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
q :
a1, a2 :
lo, hi :
Z
al :
Z
Ha :
fr_atc_framec = Execl Letq A CheckLimitlo hi r al a1; a2 :: rest j
Hi :
guard_formLetq A CheckLimitlo hi r al a1; a2
Hst :
inst_stepge c_framec c_memc Letq A CheckLimitlo hi r al a1; a2 = SomeIStopUncheckedwhy
kk :
nat
live :
listfact
out :
listinst × listfact
Hinf :
Hpt :
point_sitefr_fnc_framec fr_atc_framec = Somel, Z.of_natkk
Hc :
checked_inst_restfn_srcmd fr_fnc_framec Letq A CheckLimitlo hi r al a1; a2 rest live = Someout
Hnth :
nth_errorb_instsb kk = SomeLetq A CheckLimitlo hi r al a1; a2
⊢
False

–exact check_limit_not_uncheckedge md c_framec c_memc l Z.of_natkk Hmd Hinf Hr scope_plain_of_ _ _ Hsc Hpt b kk q lo hi r al a1 a2 rest live out why Hb Hnth eq_refl Hc Hst

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge md f xs fr m fuel s0 c s l i rest j why Hmd Hge Hfree Hin Hcf H0 Hreach Hd Ha Hi Hst
destruct guard_shape_ _ _ _ _ Hi Hst as q & o & a1 & a2 & → & Ho
destruct G.run_point_ _ _ _ _ _ _ _ _ _ _ _ _ _ Hmd Hge Hfree Hin Hcf H0 Hreach Hd Ha ltac:destruct Ho as ? & ? & ? & ? & → | ? & ? & ? & ? & → ; reflexivity ltac:intros ? ? ? E ; discriminate E ltac:intros ? E ; discriminate E as b & kk & live & out & Hinf & Hr & Hsc & Hpt & Hb & Hnth & Hc & _ & _
destruct Ho as lo & hi & r & al & → | lo & hi & r & al & →
–exact renew_if_not_uncheckedge md c_framec c_memc l Z.of_natkk Hmd Hinf Hr scope_plain_of_ _ _ Hsc Hpt b kk q lo hi r al a1 a2 rest live out why Hb Hnth eq_refl Hc Hst
–exact check_limit_not_uncheckedge md c_framec c_memc l Z.of_natkk Hmd Hinf Hr scope_plain_of_ _ _ Hsc Hpt b kk q lo hi r al a1 a2 rest live out why Hb Hnth eq_refl Hc Hst

The interpreter's runtime

446Module InterpGuards ≔ Guards InterpRuntime

run_guard_checked for the interpreter's runtime: in every state of a run of a checked module's function that starts ready, a frame that is not doomed runs no renew_if and no check_limit to unchecked. No hypothesis remains but the ready start.

452Corollary interp_guard_checked
∀ md globals f xs fr m fuel s0 c s l i rest j why
let ge ≔ mkGenvmd globals InterpRuntime.free in
checked_modulemd → InIFuncf md → call_framef xs = Somefr → InterpRuntime.readys0 m → InterpGuards.G.H.P.I.RM.mreachablege mkConfigfr [ ] m fuel, s0 c, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → guard_formi → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy
Explore proof 2 tactics

Initial goal

⊢
∀ md : module globals : listname × ptr f : func xs : listword fr : frame m : Memory.mem fuel : Z s0 : InterpRuntime.state c : config s : InterpRuntime.state l : name i : inst rest : listinst j : jump why : reason  ,
let ge ≔ ge_module ≔ md; ge_globals ≔ globals; ge_free ≔ InterpRuntime.free in
checked_modulemd → InIFuncf md → call_framef xs = Somefr → InterpRuntime.readys0 m → InterpGuards.G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s → fr_doomedc_framec = None → fr_atc_framec = Execl i :: rest j → guard_formi → inst_stepge c_framec c_memc i ≠ SomeIStopUncheckedwhy

intros md globals f xs fr m fuel s0 c s l i rest j why ge Hmd Hin Hcf H0 Hreach Hd Ha Hi

md :
globals :
listname × ptr
f :
xs :
listword
fr :
m :
Memory.mem
fuel :
Z
l :
i :
rest :
listinst
j :
why :
ge :=
ge_module ≔ md; ge_globals ≔ globals; ge_free ≔ InterpRuntime.free : genv
Hin :
InIFuncf md
Hcf :
call_framef xs = Somefr
Hreach :
InterpGuards.G.H.P.I.RM.mreachablege c_frame ≔ fr; c_callers ≔ [ ]; c_mem ≔ m; c_fuel ≔ fuel, s0 c, s
Hd :
Ha :
fr_atc_framec = Execl i :: rest j
⊢

exact InterpGuards.run_guard_checkedge md f xs fr m fuel s0 c s l i rest j why Hmd eq_refl eq_refl Hin Hcf H0 Hreach Hd Ha Hi

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros md globals f xs fr m fuel s0 c s l i rest j why ge Hmd Hin Hcf H0 Hreach Hd Ha Hi
exact InterpGuards.run_guard_checkedge md f xs fr m fuel s0 c s l i rest j why Hmd eq_refl eq_refl Hin Hcf H0 Hreach Hd Ha Hi