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
| Decision | Why |
|---|---|
| the span test's memory is the one it read, which persists | a span test changes nothing; the object it found is as it was or freed (Identity.v) |
| a guard of 0 needs no argument | kind_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 object | the 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 |
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.
Explore proof 6 tactics
Initial goal
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
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Explore proof 17 tactics
Initial goal
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 *
assert Eq : qH = qL by lia
assert EA : A + lo mod 2 ^ 64 = L + x + lo − glo
2 openfocused goal
{rewrite <- Z.add_mod_idemp_l , HA , Z.add_mod_idemp_l by lia
2 opendeferred goal
symmetry
2 opendeferred goal
apply Z.mod_unique_ _ qL ; lia
deferred goal
rewrite EA
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The two reductions take off the same multiple of 2^64.
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.
Explore proof 30 tactics
Initial goal
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
unfold access_res , cap_access_res , readonly_access_res , aligned_res
destruct Hp_ _ E as E′ | E′ ; destruct Hc as → | → ; rewrite E′
4 openfocused goal
focused goal
focused goal
–replace base ≤? a && a + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia
4 opendeferred goal
deferred goal
deferred goal
destruct a mod al =? 0 ; eexists ; split ; reflexivity | ; right | left ; reflexivity
4 opendeferred goal
deferred goal
deferred goal
eexists
5 opendeferred goal
deferred goal
deferred goal
split ; reflexivity | discriminate
3 opendeferred goal
deferred goal
deferred goal
–replace base ≤? a && a + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia
3 opendeferred goal
deferred goal
destruct r ; destruct a mod al =? 0 | ; eexists ; split ; reflexivity | ; first left ; reflexivity | right ; eexists ; split ; reflexivity | discriminate
2 opendeferred goal
deferred goal
–simpl
2 opendeferred goal
rewrite Hrb
2 opendeferred goal
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 opendeferred goal
eexists
3 opendeferred goal
shelved goal
split ; reflexivity |
2 opendeferred goal
right
2 opendeferred goal
unfold renew_res
2 opendeferred goal
rewrite Hpc , E′
2 opendeferred goal
eexists
3 opendeferred goal
shelved goal
split ; reflexivity | discriminate
deferred goal
–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
2 openshelved goal
split ; reflexivity |
right
unfold renew_res
rewrite Hpc , E′
eexists
2 openshelved goal
split ; reflexivity | discriminate
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
an object as it was: the access is inside
a read-only object as it was
freed since: out of bounds, on a freed object
The result a check makes of an access test chk (checked_res) is never unchecked, since the access test itself never is.
Explore proof 4 tactics
Initial goal
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
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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.
Explore proof 9 tactics
Initial goal
intros once fuel d n0 Ho H y →
destruct fuel as | fuel ; simpl in H
2 open–rewrite orb_false_r in H
2 openapply name_eqb_true in H
2 opensubst
2 openexact 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
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
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).
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.
Explore proof 19 tactics
Initial goal
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
cbn [ op_arg_classes map2_option value_x ] in Hst
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
5 openfocused goal
focused goal
focused goal
focused goal
all: try injection Hst as ← _ _ ; rewrite lookup_put , name_eqb_refl in He1 ; exists 0 ; split ; symmetry ; exact He1 | intros ; reflexivity
2 openfocused goal
all: destruct object_regionbase m_regionsm0 as reg | eqn: E ; | discriminate Hst
2 openfocused goal
all: injection Hst as ← _ ← ; rewrite lookup_put , name_eqb_refl in He1
2 openfocused goal
all: eexists ; split ; symmetry ; exact He1 | ; intros Hv
2 openfocused goal
all: destruct _ && _ eqn: Eb ; | exfalso ; exact Hveq_refl
2 openfocused goal
all: repeat rewrite andb_true_iff in Eb ; destruct Eb as E1 & E2 & E3
2 openfocused goal
all: apply Z.leb_le in E1 , E3 ; apply Z.ltb_lt in E2
2 openfocused goal
all: exists pb, base, reg, m0 ; auto 10
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A capability that is not an object's: the test holds 0.
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).
Proof 36 steps Qed
The lower donor b reads now what it read then.
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).
Proof 66 steps Qed
What the pass checked: a span test of N0 whose span covers P's.
The step, with the operands it reads.
a guard of 0: a check
The guard is not 0: its span test found N0's span inside its object.
P is a known offset from N0, by its guard chain.
Sizes the validator guarantees.
The renew of an access inside the object.
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.
Proof 46 steps Qed
What the pass checked: a limit of N0 of the check's span, and P's lower chain reaches N0.
The limit holds N0's capability and the size it read.
The step.
P has N0's capability.
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.
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.
Explore proof 1 tactics
Initial goal
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
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).
Explore proof 6 tactics
Initial goal
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 as b & kk & live & out & Hinf & Hr & Hsc & Hpt & Hb & Hnth & Hc & _ & _
destruct Ho as lo & hi & r & al & → | lo & hi & r & al & →
2 openfocused goal
–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
–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
The interpreter's runtime
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.
Explore proof 2 tactics
Initial goal
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
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.