rocq/theories/Coverage.v
Campaign 3's coverage lemma (docs/formal.md, Campaign 3; docs/rocq.md, The coverage lemma): a raw access that a passed check covers, as ir.pl's covered_access/6 says, does not give unchecked.
A check let(Q, a, check(Lo, Hi, Rights, Align), [P]) is the access check of the bytes from P+Lo up to P+Hi with Rights and Align, and when it passes it yields P itself. A raw access that uses Q afterwards reads or writes Size bytes at Q+Off with no check of its own: the model makes its access check again, and where that would trap the run is unchecked (raw_res/2). covered_access/6 asks that the access lie inside the checked bytes, at an alignment the check's implies, with rights the check's allow. This file proves that this is enough: the access's own check then passes (covered_access_not_unchecked). It is arithmetic over cap_access_res/7.
An address is a sum modulo 2^64 (raw_address/3), while the model's bounds are unbounded integers, so the lemma also needs every object to end inside the address space (objects_fit). The runtime's address_space axiom gives that in every state of a run that starts ready (Machine.v's mreachable_objects_fit; docs/rocq.md, An object past 2^64). That the check passes in the memory the access runs in, not only when it ran, is the evidence invariant's to show (Evidence.v, Persistence.v).
The hypotheses
The check check(Lo, Hi, Rights, Align) of the pointer p passes in memory m: the access check of the bytes from p's address plus lo up to plus hi, with rights r and alignment al, as kind_res/8 makes it for check/4.
Arithmetic
An address a aligned to al is aligned to every positive divisor aa of al.
Explore proof 10 tactics
Initial goal
intros a al aa Haa Ha Hal
destruct Z.eq_decal 0 as → | Hne
2 openfocused goal
–rewrite Zmod_0_r in Ha
2 opendeferred goal
subst
2 opendeferred goal
apply Z.mod_0_l
2 opendeferred goal
lia
deferred goal
–apply Z.mod_divide in Ha ; | exact Hne
apply Z.mod_divide in Hal ; | lia
apply Z.mod_divide ; lia |
eapply Z.divide_trans ; eassumption
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Adding a multiple d of aa to an address aligned to aa keeps it aligned.
Explore proof 5 tactics
Initial goal
intros a d aa Haa Ha Hd
apply Z.mod_divide in Ha ; | lia
apply Z.mod_divide in Hd ; | lia
apply Z.mod_divide ; lia |
apply Z.divide_add_r ; assumption
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Offset off from a is offset lo plus off - lo bytes, where lo <= off and the sum stays below 2^64: inside the address space, address arithmetic (raw_address, raw_address/3, modulo 2^64) does not wrap.
Explore proof 7 tactics
Initial goal
unfold raw_address
intros a lo off Hlo Hb
replace a + off with a + lo + off − lo by lia
rewrite <- Z.add_mod_idemp_la + lo off − lo 2 ^ 64 by lia
pose proof Z.mod_pos_bounda + lo 2 ^ 64 ltac:lia
apply Z.mod_small
lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The alignment check (aligned_res/3) passes for an address a that is a multiple of al.
Explore proof 4 tactics
Initial goal
unfold aligned_res
intros a al H
rewrite H
reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Conversely, where the alignment check passes, a is a multiple of al.
Explore proof 5 tactics
Initial goal
unfold aligned_res
intros a al H
destruct a mod al =? 0 eqn: E ; | discriminate H
apply Z.eqb_eq
exact E
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The access check
Where every object of the region list rs ends in the address space (objects_fit) and the access check through the capability c of the bytes from a+lo up to a+hi, with rights r and alignment al, passed, the check of any part of them, from a+off up to a+off+size, passes too, at an alignment aa that divides both al and off - lo, with rights need that r allows. The first hypothesis matters: an object ending above 2^64 would let a check from 2^64-64 up to 2^64+64 pass and the covered access at offset 64 wrap to address 0, outside it.
Explore proof 14 tactics
Initial goal
intros c rs a lo hi r al off size need aa Hfit H Hlo Hhi Hs Haa Hal Hoff Hr
unfold cap_access_res in *
destruct c as | base | base | f | n ; try discriminate H ; destruct object_regionbase rs as reg | eqn: E ; try discriminate H ; pose proof Hfit_ _ E as Hend ; destruct base ≤? raw_addressa lo && raw_addressa lo + hi − lo ≤? r_endreg eqn: Eb ; try discriminate H ; apply andb_true_iff in Eb as E1 E2 ; apply Z.leb_le in E1 ; apply Z.leb_le in E2 ; rewrite raw_address_withina lo off Hlo ltac:lia ; replace base ≤? raw_addressa lo + off − lo && raw_addressa lo + off − lo + size ≤? r_endreg with true by symmetry ; apply andb_true_iff ; split ; apply Z.leb_le ; lia
2 openfocused goal
–injection H as H
2 opendeferred goal
f_equal
2 opendeferred goal
apply aligned_res_ok , aligned_add ; auto
2 opendeferred goal
apply aligned_divisor_ al ; auto using aligned_res_mod
deferred goal
–destruct r ; simpl in H ; | discriminate H
destruct need ; simpl in Hr ; | discriminate Hr
injection H as H
simpl
f_equal
apply aligned_res_ok , aligned_add ; auto
apply aligned_divisor_ al ; auto using aligned_res_mod
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
An access check that passes at some alignment passes at alignment 1, as an integer load makes it.
Explore proof 6 tactics
Initial goal
unfold cap_access_res
intros c rs a size need al H
destruct c as | base | base | f | n ; try exact H ; destruct object_regionbase rs as reg | ; try exact H ; destruct base ≤? a && a + size ≤? r_endreg ; try exact H
2 openfocused goal
–f_equal
2 opendeferred goal
apply aligned_res_ok , Z.mod_1_r
deferred goal
–destruct need ; simpl in * ; f_equal ; apply aligned_res_ok , Z.mod_1_r | exact H
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Raw accesses
Every raw access type x reads or writes some bytes, at a positive alignment (access_size_align/3).
Explore proof 1 tactics
Initial goal
intros | | | | t | w | ; try destruct t ; try destruct w ; simpl ; lia
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
Where objects fit the address space and the validator accepts the instruction i as an access through q covered by the check of p from lo up to hi (covered_access), and that check passed in m, i is a raw access (raw_access: through q, of access type x, at offset off, with rights need) whose own access check, at its address, size, rights and alignment, passes in m.
Explore proof 19 tactics
Initial goal
unfold covered_access , check_passes , access_res
intros m p i q lo hi r al Hfit Hc Hp
destruct raw_accessi as q′ x off need | eqn: Ei ; | discriminate Hc
pose proof access_size_align_posx as Hs Ha
destruct access_size_alignx as size aa eqn: Ex
simpl in Hs , Ha |- *
repeat rewrite andb_true_iff in Hc
destruct Hc as Hq & H1 & H2 & H3 & H4 & H5
apply term_eqb_eq in Hq
subst q′
apply Z.leb_le in H1
apply Z.leb_le in H2
apply Z.eqb_eq in H3
apply Z.eqb_eq in H4
exists x, off, need
split ; reflexivity |
rewrite Ex
simpl
eapply cap_access_covered ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The loads and stores
An integer load of type t (int_load_res, int_load_res/6) whose access check passes gives a value, not a trap or unchecked.
Explore proof 3 tactics
Initial goal
unfold int_load_res
intros t k m a c rr Ha H
destruct t as | | | | n ; simpl in Ha ; rewrite Ha in H ; cases H ; injection H as ← ; eauto
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
A store of width w (store_res, store_res/7) whose access check passes succeeds.
Explore proof 3 tactics
Initial goal
unfold store_res
intros w m a c x rr m′ Ha H
destruct w , x ; simpl in Ha , H ; try discriminate H ; rewrite Ha in H ; injection H as ← _ ; reflexivity
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
The raw access instruction
Explore proof 25 tactics
Initial goal
intros ge fr m i q x off need p why Ei Hq Ha Hst
destruct i ; simpl in Ei ; cases Ei
9 openfocused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
focused goal
all: try discriminate Ei
4 openfocused goal
focused goal
focused goal
all: injection Ei as ← ← ← ← ; subst
4 openfocused goal
focused goal
focused goal
all: try rewrite inst_step_let in Hst by reflexivity
4 openfocused goal
focused goal
focused goal
all: cbn - [ int_load_res access_res pointer_load_effects store_res pointer_store_effects raw_address ] in Hst
4 openfocused goal
focused goal
focused goal
all: rewrite Hq in Hst
4 openfocused goal
focused goal
focused goal
–assert Ha1 := cap_access_align_one_ _ _ _ _ _ Ha
4 opendeferred goal
deferred goal
deferred goal
destruct int_load_res_ _ _ _ _ eqn: El ; simpl in Hst ; | discriminate Hst
4 opendeferred goal
deferred goal
deferred goal
destruct int_load_res_checked_ _ _ _ _ _ Ha1 El as x′ →
4 opendeferred goal
deferred goal
deferred goal
simpl in Hst
4 opendeferred goal
deferred goal
deferred goal
discriminate Hst
3 opendeferred goal
deferred goal
deferred goal
–simpl in Ha ; rewrite Ha in Hst
3 opendeferred goal
deferred goal
destruct k ; try discriminate Hst
3 opendeferred goal
deferred goal
destruct pointer_load_effects_ _ _ ; discriminate Hst
2 opendeferred goal
deferred goal
–destruct width_value_classw ; simpl in Hst ; try discriminate Hst
2 opendeferred goal
destruct value_x_ _ _ _ ; simpl in Hst ; try discriminate Hst
2 opendeferred goal
destruct store_res_ _ _ _ _ as rr m′ | eqn: Es ; try discriminate Hst
2 opendeferred goal
rewrite store_res_checked_ _ _ _ _ _ _ Ha Es in Hst
2 opendeferred goal
discriminate Hst
deferred goal
–simpl in Ha
destruct value_x_ _ _ _ as x | ; simpl in Hst ; try discriminate Hst
rewrite Ha in Hst
destruct x ; try discriminate Hst
destruct pointer_store_effects_ _ _ _ ; discriminate Hst
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.
Source script
No other instruction is a raw access.
raw_load: the value loaded is a value, not unchecked.
raw_load_pointer: its check is the one that passed.
raw_store: the store succeeds.
raw_store_pointer: its check is the one that passed.
The coverage lemma. Where objects fit the address space, the validator says the raw access instruction i is covered by the check that yielded q (covered_access, the check of the pointer p from lo up to hi with rights r and alignment al), and that check passes in the memory m that i runs in (check_passes), i gives no unchecked.
Explore proof 3 tactics
Initial goal
intros ge fr m i q lo hi r al p why Hfit Hc Hq Hp
destruct covered_access_checked_ _ _ _ _ _ _ _ Hfit Hc Hp as x & off & need & Ei & Ha
exact access_ok_not_unchecked_ _ _ _ _ _ _ _ _ _ Ei Hq Ha
No remaining goals.
Qed
✓ Proof checked and closed by Rocq.