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.
Proof 19 steps Qed
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 68 steps Qed
What the pass checked: a span test of N0 whose span covers P's.
A function with a setjmp has no single definitions.
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 48 steps Qed
What the pass checked: a limit of N0 of the check's span, and P's lower chain reaches N0.
A function with a setjmp has no single definitions.
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 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.