Fil-C on Nix

Filnix wiki

the formal campaign

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).

From Stdlib Require Import String ZArith List Bool Lia
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Machine Validate
Import ListNotations
Open Scope Z_scope

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.

38Definition check_passesm : Memory.mem p : ptr lo hi : Z r : rights al : Z : Prop ≔
access_resm raw_addressptr_addrp lo ptr_capp hi − lo r al = Someok

Arithmetic

An address a aligned to al is aligned to every positive divisor aa of al.

45Lemma aligned_divisor
∀ a al aa
0 < aa
a mod al = 0
al mod aa = 0
a mod aa = 0
Explore proof 10 tactics

Initial goal

⊢
∀a al aa : Z, 0 < aa → a mod al = 0 → al mod aa = 0 → a mod aa = 0

intros a al aa Haa Ha Hal

a, al, aa :
Z
Haa :
0 < aa
Ha :
a mod al = 0
Hal :
al mod aa = 0
⊢
a mod aa = 0

destruct Z.eq_decal 0 as → | Hne

2 open

a, aa :
Z
Haa :
0 < aa
Hal :
0 mod aa = 0
Ha :
a mod 0 = 0
⊢
a mod aa = 0
focused goal
a, al, aa :
Z
Haa :
0 < aa
Ha :
a mod al = 0
Hal :
al mod aa = 0
Hne :
al ≠ 0
⊢
a mod aa = 0

–rewrite Zmod_0_r in Ha

2 open

a, aa :
Z
Haa :
0 < aa
Hal :
0 mod aa = 0
Ha :
a = 0
⊢
a mod aa = 0
deferred goal
a, al, aa :
Z
Haa :
0 < aa
Ha :
a mod al = 0
Hal :
al mod aa = 0
Hne :
al ≠ 0
⊢
a mod aa = 0

subst

2 open

aa :
Z
Haa :
0 < aa
Hal :
0 mod aa = 0
⊢
0 mod aa = 0
deferred goal
a, al, aa :
Z
Haa :
0 < aa
Ha :
a mod al = 0
Hal :
al mod aa = 0
Hne :
al ≠ 0
⊢
a mod aa = 0

apply Z.mod_0_l

2 open

aa :
Z
Haa :
0 < aa
Hal :
0 mod aa = 0
⊢
aa ≠ 0
deferred goal
a, al, aa :
Z
Haa :
0 < aa
Ha :
a mod al = 0
Hal :
al mod aa = 0
Hne :
al ≠ 0
⊢
a mod aa = 0

lia

deferred goal
a, al, aa :
Z
Haa :
0 < aa
Ha :
a mod al = 0
Hal :
al mod aa = 0
Hne :
al ≠ 0
⊢
a mod aa = 0

–apply Z.mod_divide in Ha ; | exact Hne

a, al, aa :
Z
Haa :
0 < aa
Ha :
al | a
Hal :
al mod aa = 0
Hne :
al ≠ 0
⊢
a mod aa = 0

apply Z.mod_divide in Hal ; | lia

a, al, aa :
Z
Haa :
0 < aa
Ha :
al | a
Hal :
aa | al
Hne :
al ≠ 0
⊢
a mod aa = 0

apply Z.mod_divide ; lia |

a, al, aa :
Z
Haa :
0 < aa
Ha :
al | a
Hal :
aa | al
Hne :
al ≠ 0
⊢
aa | a

eapply Z.divide_trans ; eassumption

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros a al aa Haa Ha Hal
destruct Z.eq_decal 0 as → | Hne
–rewrite Zmod_0_r in Ha
subst
apply Z.mod_0_l
lia
–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

Adding a multiple d of aa to an address aligned to aa keeps it aligned.

55Lemma aligned_add
∀ a d aa
0 < aa
a mod aa = 0
d mod aa = 0
a + d mod aa = 0
Explore proof 5 tactics

Initial goal

⊢
∀a d aa : Z, 0 < aa → a mod aa = 0 → d mod aa = 0 → a + d mod aa = 0

intros a d aa Haa Ha Hd

a, d, aa :
Z
Haa :
0 < aa
Ha :
a mod aa = 0
Hd :
d mod aa = 0
⊢
a + d mod aa = 0

apply Z.mod_divide in Ha ; | lia

a, d, aa :
Z
Haa :
0 < aa
Ha :
aa | a
Hd :
d mod aa = 0
⊢
a + d mod aa = 0

apply Z.mod_divide in Hd ; | lia

a, d, aa :
Z
Haa :
0 < aa
Ha :
aa | a
Hd :
aa | d
⊢
a + d mod aa = 0

apply Z.mod_divide ; lia |

a, d, aa :
Z
Haa :
0 < aa
Ha :
aa | a
Hd :
aa | d
⊢
aa | a + d

apply Z.divide_add_r ; assumption

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

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.

65Lemma raw_address_within
∀ a lo off
lo ≤ off
raw_addressa lo + off − lo < 2 ^ 64
raw_addressa off = raw_addressa lo + off − lo
Explore proof 7 tactics

Initial goal

⊢
∀a lo off : Z, lo ≤ off → raw_addressa lo + off − lo < 2 ^ 64 → raw_addressa off = raw_addressa lo + off − lo

unfold raw_address

⊢
∀a lo off : Z, lo ≤ off → a + lo mod 2 ^ 64 + off − lo < 2 ^ 64 → a + off mod 2 ^ 64 = a + lo mod 2 ^ 64 + off − lo

intros a lo off Hlo Hb

a, lo, off :
Z
Hlo :
lo ≤ off
Hb :
a + lo mod 2 ^ 64 + off − lo < 2 ^ 64
⊢
a + off mod 2 ^ 64 = a + lo mod 2 ^ 64 + off − lo

replace a + off with a + lo + off − lo by lia

a, lo, off :
Z
Hlo :
lo ≤ off
Hb :
a + lo mod 2 ^ 64 + off − lo < 2 ^ 64
⊢
a + lo + off − lo mod 2 ^ 64 = a + lo mod 2 ^ 64 + off − lo

rewrite <- Z.add_mod_idemp_la + lo off − lo 2 ^ 64 by lia

a, lo, off :
Z
Hlo :
lo ≤ off
Hb :
a + lo mod 2 ^ 64 + off − lo < 2 ^ 64
⊢
a + lo mod 2 ^ 64 + off − lo mod 2 ^ 64 = a + lo mod 2 ^ 64 + off − lo

pose proof Z.mod_pos_bounda + lo 2 ^ 64 ltac:lia

a, lo, off :
Z
Hlo :
lo ≤ off
Hb :
a + lo mod 2 ^ 64 + off − lo < 2 ^ 64
H :
0 ≤ a + lo mod 2 ^ 64 < 2 ^ 64
⊢
a + lo mod 2 ^ 64 + off − lo mod 2 ^ 64 = a + lo mod 2 ^ 64 + off − lo

apply Z.mod_small

a, lo, off :
Z
Hlo :
lo ≤ off
Hb :
a + lo mod 2 ^ 64 + off − lo < 2 ^ 64
H :
0 ≤ a + lo mod 2 ^ 64 < 2 ^ 64
⊢
0 ≤ a + lo mod 2 ^ 64 + off − lo < 2 ^ 64

lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

The alignment check (aligned_res/3) passes for an address a that is a multiple of al.

78Lemma aligned_res_ok
∀ a al
a mod al = 0
Explore proof 4 tactics

Initial goal

⊢
∀a al : Z, a mod al = 0 → aligned_resa al = ok

unfold aligned_res

⊢
∀ a al : Z  ,
a mod al = 0
→
a mod al =? 0
→
=

intros a al H

a, al :
Z
H :
a mod al = 0
⊢
a mod al =? 0
→
=

rewrite H

a, al :
Z
H :
a mod al = 0
⊢
0 =? 0
→
=

reflexivity

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros a al H
rewrite H
reflexivity

Conversely, where the alignment check passes, a is a multiple of al.

83Lemma aligned_res_mod
∀ a al
a mod al = 0
Explore proof 5 tactics

Initial goal

⊢
∀a al : Z, aligned_resa al = ok → a mod al = 0

unfold aligned_res

⊢
∀ a al : Z  ,
a mod al =? 0
→
=
→
a mod al = 0

intros a al H

a, al :
Z
H :
a mod al =? 0
→
=
⊢
a mod al = 0

destruct a mod al =? 0 eqn: E ; | discriminate H

a, al :
Z
E :
a mod al =? 0 = true
H :
ok = ok
⊢
a mod al = 0

apply Z.eqb_eq

a, al :
Z
E :
a mod al =? 0 = true
H :
ok = ok
⊢
a mod al =? 0 = true

exact E

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros a al H
destruct a mod al =? 0 eqn: E ; | discriminate H
apply Z.eqb_eq
exact E

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.

100Lemma cap_access_covered
∀ c rs a lo hi r al off size need aa
cap_access_resc rs raw_addressa lo hi − lo r al = Someok
lo ≤ off
off + size ≤ hi
0 < size
0 < aa
al mod aa = 0
off − lo mod aa = 0
rights_allowr need = true
cap_access_resc rs raw_addressa off size need aa = Someok
Explore proof 14 tactics

Initial goal

⊢
∀c : cap rs : listregion a lo hi : Z r : rights al off size : Z need : rights aa : Z, objects_fitrs → cap_access_resc rs raw_addressa lo hi − lo r al = Someok → lo ≤ off → off + size ≤ hi → 0 < size → 0 < aa → al mod aa = 0 → off − lo mod aa = 0 → rights_allowr need = true → cap_access_resc rs raw_addressa off size need aa = Someok

intros c rs a lo hi r al off size need aa Hfit H Hlo Hhi Hs Haa Hal Hoff Hr

c :
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
H :
cap_access_resc rs raw_addressa lo hi − lo r al = Someok
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
⊢
cap_access_resc rs raw_addressa off size need aa = Someok

unfold cap_access_res in *

c :
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
H :
match c with
Objbase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? raw_addressa lo && raw_addressa lo + hi − lo ≤? r_endreg
→
Robase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? raw_addressa lo && raw_addressa lo + hi − lo ≤? r_endreg
→
⇒
None
=
Someok
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
⊢
match c with
Objbase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? raw_addressa off && raw_addressa off + size ≤? r_endreg
→
Robase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? raw_addressa off && raw_addressa off + size ≤? r_endreg
→
⇒
None
=
Someok

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 open

base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Somealigned_resraw_addressa lo al = Someok
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somealigned_resraw_addressa lo + off − lo aa = Someok
focused goal
base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resneed raw_addressa lo + off − lo aa = Someok

–injection H as H

2 open

base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somealigned_resraw_addressa lo + off − lo aa = Someok
deferred goal
base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resneed raw_addressa lo + off − lo aa = Someok

f_equal

2 open

base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
aligned_resraw_addressa lo + off − lo aa = ok
deferred goal
base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resneed raw_addressa lo + off − lo aa = Someok

apply aligned_res_ok , aligned_add ; auto

2 open

base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
raw_addressa lo mod aa = 0
deferred goal
base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resneed raw_addressa lo + off − lo aa = Someok

apply aligned_divisor_ al ; auto using aligned_res_mod

deferred goal
base :
Z
rs :
listregion
a, lo, hi :
Z
al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowr need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resneed raw_addressa lo + off − lo aa = Someok

–destruct r ; simpl in H ; | discriminate H

base :
Z
rs :
listregion
a, lo, hi, al, off, size :
Z
need :
aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Somealigned_resraw_addressa lo al = Someok
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
rights_allowRead need = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resneed raw_addressa lo + off − lo aa = Someok

destruct need ; simpl in Hr ; | discriminate Hr

base :
Z
rs :
listregion
a, lo, hi, al, off, size, aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
H :
Somealigned_resraw_addressa lo al = Someok
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
true = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resRead raw_addressa lo + off − lo aa = Someok

injection H as H

base :
Z
rs :
listregion
a, lo, hi, al, off, size, aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
true = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somereadonly_access_resRead raw_addressa lo + off − lo aa = Someok

simpl

base :
Z
rs :
listregion
a, lo, hi, al, off, size, aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
true = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
Somealigned_resraw_addressa lo + off − lo aa = Someok

f_equal

base :
Z
rs :
listregion
a, lo, hi, al, off, size, aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
true = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
aligned_resraw_addressa lo + off − lo aa = ok

apply aligned_res_ok , aligned_add ; auto

base :
Z
rs :
listregion
a, lo, hi, al, off, size, aa :
Z
Hfit :
reg :
E :
object_regionbase rs = Somereg
E1 :
base ≤ raw_addressa lo
E2 :
raw_addressa lo + hi − lo ≤ r_endreg
Hlo :
lo ≤ off
Hhi :
off + size ≤ hi
Hs :
0 < size
Haa :
0 < aa
Hal :
al mod aa = 0
Hoff :
off − lo mod aa = 0
Hr :
true = true
Hend :
0 ≤ base ∧ r_endreg ≤ 2 ^ 48
⊢
raw_addressa lo mod aa = 0

apply aligned_divisor_ al ; auto using aligned_res_mod

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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
–injection H as H
f_equal
apply aligned_divisor_ al ; auto using aligned_res_mod
–destruct r ; simpl in H ; | discriminate H
destruct need ; simpl in Hr ; | discriminate Hr
injection H as H
simpl
f_equal
apply aligned_divisor_ al ; auto using aligned_res_mod

An access check that passes at some alignment passes at alignment 1, as an integer load makes it.

129Lemma cap_access_align_one
∀ c rs a size need al
cap_access_resc rs a size need al = Someok
cap_access_resc rs a size need 1 = Someok
Explore proof 6 tactics

Initial goal

⊢
∀c : cap rs : listregion a size : Z need : rights al : Z, cap_access_resc rs a size need al = Someok → cap_access_resc rs a size need 1 = Someok

unfold cap_access_res

⊢
∀ c : cap rs : listregion a size : Z need : rights al : Z  ,
match c with
Objbase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
Robase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
⇒
None
=
Someok
→
match c with
Objbase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
Robase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
⇒
None
=
Someok

intros c rs a size need al H

c :
rs :
listregion
a, size :
Z
need :
al :
Z
H :
match c with
Objbase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
Robase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
⇒
None
=
Someok
⊢
match c with
Objbase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
Robase
⇒
let* reg ≔ object_regionbase rs in
Some
base ≤? a && a + size ≤? r_endreg
→
⇒
None
=
Someok

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 open

base :
Z
rs :
listregion
a, size :
Z
need :
al :
Z
reg :
H :
Somealigned_resa al = Someok
⊢
Somealigned_resa 1 = Someok
focused goal
base :
Z
rs :
listregion
a, size :
Z
need :
al :
Z
reg :
H :
Somereadonly_access_resneed a al = Someok
⊢
Somereadonly_access_resneed a 1 = Someok

–f_equal

2 open

base :
Z
rs :
listregion
a, size :
Z
need :
al :
Z
reg :
H :
Somealigned_resa al = Someok
⊢
deferred goal
base :
Z
rs :
listregion
a, size :
Z
need :
al :
Z
reg :
H :
Somereadonly_access_resneed a al = Someok
⊢
Somereadonly_access_resneed a 1 = Someok

apply aligned_res_ok , Z.mod_1_r

deferred goal
base :
Z
rs :
listregion
a, size :
Z
need :
al :
Z
reg :
H :
Somereadonly_access_resneed a al = Someok
⊢
Somereadonly_access_resneed a 1 = Someok

–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
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
–f_equal
apply aligned_res_ok , Z.mod_1_r
–destruct need ; simpl in * ; f_equal ; apply aligned_res_ok , Z.mod_1_r | exact H

Raw accesses

Every raw access type x reads or writes some bytes, at a positive alignment (access_size_align/3).

144Lemma access_size_align_pos
∀ x
0 < fstaccess_size_alignx ∧ 0 < sndaccess_size_alignx
Explore proof 1 tactics

Initial goal

⊢
∀x : access_type, 0 < fstaccess_size_alignx ∧ 0 < sndaccess_size_alignx

intros | | | | t | w | ; try destruct t ; try destruct w ; simpl ; lia

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros | | | | t | w | ; try destruct t ; try destruct w ; simpl ; lia

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.

153Lemma covered_access_checked
∀ m p i q lo hi r al
covered_accessi q lo hi r al = true
check_passesm p lo hi r al
∃x off need, raw_accessi = Someq, x, off, need ∧ access_resm raw_addressptr_addrp off ptr_capp fstaccess_size_alignx need sndaccess_size_alignx = Someok
Explore proof 19 tactics

Initial goal

⊢
∀m : Memory.mem p : ptr i : inst q : name lo hi : Z r : rights al : Z, objects_fitm_regionsm → covered_accessi q lo hi r al = true → check_passesm p lo hi r al → ∃x : access_type off : Z need : rights, raw_accessi = Someq, x, off, need ∧ access_resm raw_addressptr_addrp off ptr_capp fstaccess_size_alignx need sndaccess_size_alignx = Someok

unfold covered_access , check_passes , access_res

⊢
∀ m : Memory.mem p : ptr i : inst q : name lo hi : Z r : rights al : Z  ,
→
match raw_accessi with
Someq′, x, off, need
⇒
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
None
⇒
false
=
true
→
cap_access_resptr_capp m_regionsm raw_addressptr_addrp lo hi − lo r al = Someok → ∃x : access_type off : Z need : rights, raw_accessi = Someq, x, off, need ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off fstaccess_size_alignx need sndaccess_size_alignx = Someok

intros m p i q lo hi r al Hfit Hc Hp

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
Hc :
match raw_accessi with
Someq′, x, off, need
⇒
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
None
⇒
false
=
true
Hp :
⊢
∃x : access_type off : Z need : rights, raw_accessi = Someq, x, off, need ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off fstaccess_size_alignx need sndaccess_size_alignx = Someok

destruct raw_accessi as q′ x off need | eqn: Ei ; | discriminate Hc

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
Hc :
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
=
true
Hp :
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

pose proof access_size_align_posx as Hs Ha

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
Hc :
let size, aa ≔ access_size_alignx in
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need
=
true
Hp :
Hs :
Ha :
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

destruct access_size_alignx as size aa eqn: Ex

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
Hc :
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need = true
Hp :
Hs :
0 < fstsize, aa
Ha :
0 < sndsize, aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

simpl in Hs , Ha |- *

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
Hc :
name_eqbq′ q && lo ≤? off && off + size ≤? hi && al mod aa =? 0 && off − lo mod aa =? 0 && rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

repeat rewrite andb_true_iff in Hc

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
Hc :
name_eqbq′ q = true ∧ lo ≤? off = true ∧ off + size ≤? hi = true ∧ al mod aa =? 0 = true ∧ off − lo mod aa =? 0 = true ∧ rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

destruct Hc as Hq & H1 & H2 & H3 & H4 & H5

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
Hq :
name_eqbq′ q = true
H1 :
lo ≤? off = true
H2 :
off + size ≤? hi = true
H3 :
al mod aa =? 0 = true
H4 :
off − lo mod aa =? 0 = true
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

apply term_eqb_eq in Hq

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
q′ :
off :
Z
need :
Ei :
raw_accessi = Someq′, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
Hq :
q′ = q
H1 :
lo ≤? off = true
H2 :
off + size ≤? hi = true
H3 :
al mod aa =? 0 = true
H4 :
off − lo mod aa =? 0 = true
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq′, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

subst q′

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤? off = true
H2 :
off + size ≤? hi = true
H3 :
al mod aa =? 0 = true
H4 :
off − lo mod aa =? 0 = true
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

apply Z.leb_le in H1

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤? hi = true
H3 :
al mod aa =? 0 = true
H4 :
off − lo mod aa =? 0 = true
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

apply Z.leb_le in H2

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa =? 0 = true
H4 :
off − lo mod aa =? 0 = true
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

apply Z.eqb_eq in H3

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa = 0
H4 :
off − lo mod aa =? 0 = true
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

apply Z.eqb_eq in H4

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa = 0
H4 :
off − lo mod aa = 0
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
∃x0 : access_type off0 : Z need0 : rights, Someq, x, off, need = Someq, x0, off0, need0 ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off0 fstaccess_size_alignx0 need0 sndaccess_size_alignx0 = Someok

exists x, off, need

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa = 0
H4 :
off − lo mod aa = 0
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
Someq, x, off, need = Someq, x, off, need ∧ cap_access_resptr_capp m_regionsm raw_addressptr_addrp off fstaccess_size_alignx need sndaccess_size_alignx = Someok

split ; reflexivity |

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa = 0
H4 :
off − lo mod aa = 0
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa

rewrite Ex

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa = 0
H4 :
off − lo mod aa = 0
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa
⊢
cap_access_resptr_capp m_regionsm raw_addressptr_addrp off fstsize, aa need sndsize, aa = Someok

simpl

m :
Memory.mem
p :
i :
q :
lo, hi :
Z
al :
Z
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
size, aa :
Z
Ex :
access_size_alignx = size, aa
H1 :
lo ≤ off
H2 :
off + size ≤ hi
H3 :
al mod aa = 0
H4 :
off − lo mod aa = 0
H5 :
rights_allowr need = true
Hp :
Hs :
0 < size
Ha :
0 < aa

eapply cap_access_covered ; eauto

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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

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.

177Lemma int_load_res_checked
∀ t k m a c rr
int_load_rest k m a c = Somerr
∃x, rr = RValx
Explore proof 3 tactics

Initial goal

⊢
∀t : load_type k : class m : Memory.mem a : Z c : cap rr : resword, access_resm a c fstaccess_size_alignXLoadt Read 1 = Someok → int_load_rest k m a c = Somerr → ∃x : word, rr = RValx

unfold int_load_res

⊢
∀ t : load_type k : class m : Memory.mem a : Z c : cap rr : resword  ,
→
match access_resm a c match t with LdS ⇒ 4 | LdX ⇒ 10 | LdNarrown ⇒ fstnarrow_typen | _ ⇒ 8 end Read 1 with
SomeRVal_
⇒
match t with
⇒
let* x0 ≔
match t with
⇒
4
⇒
10
_
⇒
8
in
SomeRValx0
_
⇒
Some
match t with
⇒
4
⇒
10
_
⇒
8
SomeRTrapwhy
⇒
SomeRTrapwhy
SomeRUncheckedwhy
⇒
SomeRUncheckedwhy
None
⇒
None
=
Somerr
→
∃x : word, rr = RValx

intros t k m a c rr Ha H

m :
Memory.mem
a :
Z
c :
H :
match access_resm a c match t with LdS ⇒ 4 | LdX ⇒ 10 | LdNarrown ⇒ fstnarrow_typen | _ ⇒ 8 end Read 1 with
SomeRVal_
⇒
match t with
⇒
let* x0 ≔
match t with
⇒
4
⇒
10
_
⇒
8
in
SomeRValx0
_
⇒
Some
match t with
⇒
4
⇒
10
_
⇒
8
SomeRTrapwhy
⇒
SomeRTrapwhy
SomeRUncheckedwhy
⇒
SomeRUncheckedwhy
None
⇒
None
=
Somerr
⊢
∃x : word, rr = RValx

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
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

A store of width w (store_res, store_res/7) whose access check passes succeeds.

187Lemma store_res_checked
∀ w m a c x rr m′
store_resw m a c x = Somerr, m′
rr = ok
Explore proof 3 tactics

Initial goal

⊢
∀w : width m : Memory.mem a : Z c : cap x : word rr : resunit m′ : Memory.mem, access_resm a c fstaccess_size_alignXWidthw Write sndaccess_size_alignXWidthw = Someok → store_resw m a c x = Somerr, m′ → rr = ok

unfold store_res

⊢
∀ w : width m : Memory.mem a : Z c : cap x : word rr : resunit m′ : Memory.mem  ,
→
match w with
⇒
match x with
⇒
let* chk ≔ access_resm a c width_bytesw Write 8 in
Some
chk
match chk with
_
⇒
None
_
⇒
match x with
⇒
let* chk ≔
match w with
⇒
8
_
⇒
1
in
Some
chk
match chk with
_
⇒
None
=
Somerr, m′
→
rr = ok

intros w m a c x rr m′ Ha H

m :
Memory.mem
a :
Z
c :
x :
rr :
resunit
m′ :
Memory.mem
H :
match w with
⇒
match x with
⇒
let* chk ≔ access_resm a c width_bytesw Write 8 in
Some
chk
match chk with
_
⇒
None
_
⇒
match x with
⇒
let* chk ≔
match w with
⇒
8
_
⇒
1
in
Some
chk
match chk with
_
⇒
None
=
Somerr, m′
⊢
rr = ok

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
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

The raw access instruction

A raw access instruction i whose own access check passes, at the address of the pointer its operand q holds, is not stopped by inst_step with unchecked. The access may still fail otherwise (a pointer load of a word that is not a pointer, an operand of the wrong class); only unchecked is ruled out.

202Lemma access_ok_not_unchecked
∀ ge fr m i q x off need p why
raw_accessi = Someq, x, off, need
lookupq fr_envfr = SomeWPtrp
inst_stepge fr m i ≠ SomeIStopUncheckedwhy
Explore proof 25 tactics

Initial goal

⊢
∀ge : genv fr : frame m : Memory.mem i : inst q : name x : access_type off : Z need : rights p : ptr why : reason, raw_accessi = Someq, x, off, need → lookupq fr_envfr = SomeWPtrp → access_resm raw_addressptr_addrp off ptr_capp fstaccess_size_alignx need sndaccess_size_alignx = Someok → inst_stepge fr m i ≠ SomeIStopUncheckedwhy

intros ge fr m i q x off need p why Ei Hq Ha Hst

ge :
fr :
m :
Memory.mem
i :
q :
off :
Z
need :
p :
why :
Ei :
raw_accessi = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m i = SomeIStopUncheckedwhy
⊢
False

destruct i ; simpl in Ei ; cases Ei

9 open

ge :
fr :
m :
Memory.mem
d :
o :
args :
listvalue
q :
off :
Z
need :
p :
why :
off0 :
Z
Heqo0 :
o = RawLoadt off0
l :
listvalue
n :
Heqv0 :
v = Tmpn
Heql0 :
l = [ ]
Heql :
args = Tmpn
Ei :
Somen, XLoadt, off0, Read = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Letd k RawLoadt off0 Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
o :
args :
listvalue
q :
off :
Z
need :
p :
why :
off0 :
Z
es :
listeffect
Heqo0 :
o = RawLoadPointeroff0 es
l :
listvalue
n :
Heqv0 :
v = Tmpn
Heql0 :
l = [ ]
Heql :
args = Tmpn
Ei :
Somen, XPtr, off0, Read = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Letd k RawLoadPointeroff0 es Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
o :
args :
q :
off :
Z
need :
p :
why :
Ei :
None = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Flightd o args lower = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
v, a :
q :
off :
Z
need :
p :
why :
n :
Heqv0 :
a = Tmpn
Ei :
Somen, XWidthw, off0, Write = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorew off0 v Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
v, a :
es :
listeffect
q :
off :
Z
need :
p :
why :
n :
Heqv0 :
a = Tmpn
Ei :
Somen, XPtr, off0, Write = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorePointeroff0 v Tmpn es = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
callee :
args :
listarg
q :
off :
Z
need :
p :
why :
Ei :
None = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Callr callee args = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
callee :
args :
listarg
q :
off :
Z
need :
p :
why :
Ei :
None = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawCallr callee args = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
x0 :
size :
Z
q :
off :
Z
need :
p :
why :
Ei :
None = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m LocalAllocx0 size = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
file :
line :
Z
q :
off :
Z
need :
p :
why :
Ei :
None = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Locfile line = SomeIStopUncheckedwhy
⊢
False

all: try discriminate Ei

4 open

ge :
fr :
m :
Memory.mem
d :
o :
args :
listvalue
q :
off :
Z
need :
p :
why :
off0 :
Z
Heqo0 :
o = RawLoadt off0
l :
listvalue
n :
Heqv0 :
v = Tmpn
Heql0 :
l = [ ]
Heql :
args = Tmpn
Ei :
Somen, XLoadt, off0, Read = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Letd k RawLoadt off0 Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
o :
args :
listvalue
q :
off :
Z
need :
p :
why :
off0 :
Z
es :
listeffect
Heqo0 :
o = RawLoadPointeroff0 es
l :
listvalue
n :
Heqv0 :
v = Tmpn
Heql0 :
l = [ ]
Heql :
args = Tmpn
Ei :
Somen, XPtr, off0, Read = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Letd k RawLoadPointeroff0 es Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
v, a :
q :
off :
Z
need :
p :
why :
n :
Heqv0 :
a = Tmpn
Ei :
Somen, XWidthw, off0, Write = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorew off0 v Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
v, a :
es :
listeffect
q :
off :
Z
need :
p :
why :
n :
Heqv0 :
a = Tmpn
Ei :
Somen, XPtr, off0, Write = Someq, x, off, need
Hq :
lookupq fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorePointeroff0 v Tmpn es = SomeIStopUncheckedwhy
⊢
False

all: injection Ei as ← ← ← ← ; subst

4 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Letd k RawLoadt off0 Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m Letd k RawLoadPointeroff0 es Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorew off0 v Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorePointeroff0 v Tmpn es = SomeIStopUncheckedwhy
⊢
False

all: try rewrite inst_step_let in Hst by reflexivity

4 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let e ≔ fr_envfr in
let locals ≔ fr_localsfr in
let* classes ≔ op_arg_classesRawLoadt off0 k in
let* xs ≔ map2_optionvalue_xge e classes Tmpn in
match op_resRawLoadt off0 k xs m with
SomeOpResr m′
⇒
Somebind_resd r e locals m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x e, locals, m′
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let e ≔ fr_envfr in
let locals ≔ fr_localsfr in
let* classes ≔ op_arg_classesRawLoadPointeroff0 es k in
let* xs ≔ map2_optionvalue_xge e classes Tmpn in
match op_resRawLoadPointeroff0 es k xs m with
SomeOpResr m′
⇒
Somebind_resd r e locals m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x e, locals, m′
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorew off0 v Tmpn = SomeIStopUncheckedwhy
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
inst_stepge fr m RawStorePointeroff0 v Tmpn es = SomeIStopUncheckedwhy
⊢
False

all: cbn - [ int_load_res access_res pointer_load_effects store_res pointer_store_effects raw_address ] in Hst

4 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* xs ≔
let* z ≔
let* x ≔ lookupn fr_envfr in
Somex
in
Somez
in
match match xs with WPtrp ⇒ let* r ≔ int_load_rest k m raw_addressptr_addrp off0 ptr_capp in SomeOpResraw_resr m | WPtrp :: _ :: _ ⇒ None | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* xs ≔
let* z ≔
let* x ≔ lookupn fr_envfr in
Somex
in
Somez
in
match match k with P ⇒ match xs with WPtrp ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | WPtrp :: _ :: _ ⇒ None | _ ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match let* x0 ≔ lookupn fr_envfr in Somex0 with
SomeWPtrp
⇒
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
_
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
match let* x0 ≔ lookupn fr_envfr in Somex0 with
SomeWPtrp
⇒
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
_
⇒
None
=
⊢
False

all: rewrite Hq in Hst

4 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match let* r ≔ int_load_rest k m raw_addressptr_addrp off0 ptr_capp in SomeOpResraw_resr m with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
focused goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

–assert Ha1 := cap_access_align_one_ _ _ _ _ _ Ha

4 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match let* r ≔ int_load_rest k m raw_addressptr_addrp off0 ptr_capp in SomeOpResraw_resr m with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct int_load_res_ _ _ _ _ eqn: El ; simpl in Hst ; | discriminate Hst

4 open

deferred goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct int_load_res_checked_ _ _ _ _ _ Ha1 El as x′ →

4 open

deferred goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

simpl in Hst

4 open

⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

discriminate Hst

3 open

deferred goal
ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ match access_resm raw_addressptr_addrp off0 ptr_capp 8 Read 8 with SomeRVal_ ⇒ let* x0 ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx0 m | SomeRTrapwhy | SomeRUncheckedwhy ⇒ SomeOpResRUncheckedwhy m | None ⇒ None end | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

–simpl in Ha ; rewrite Ha in Hst

3 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match match k with P ⇒ let* x ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx m | _ ⇒ None end with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct k ; try discriminate Hst

3 open

ge :
fr :
m :
Memory.mem
d :
p :
why :
off0 :
Z
es :
listeffect
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
match let* x ≔ pointer_load_effectsm raw_addressptr_addrp off0 es in SomeOpResRValWPtrx m with
SomeOpResr m′
⇒
Somebind_resd r fr_envfr fr_localsfr m′
SomeOpUBwhy
⇒
SomeIStopUBwhy
SomeOpAllocq kont
⇒
Some
λ base : Z  ⇒
let x, m′ ≔ kontbase in
putd x fr_envfr, fr_localsfr, m′
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct pointer_load_effects_ _ _ ; discriminate Hst

2 open

deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* vk ≔ width_value_classw in
let* x ≔ value_xge fr_envfr vk v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

–destruct width_value_classw ; simpl in Hst ; try discriminate Hst

2 open

ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr c v in
match store_resw m raw_addressptr_addrp off0 ptr_capp x with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct value_x_ _ _ _ ; simpl in Hst ; try discriminate Hst

2 open

ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
w0 :
Hst :
match store_resw m raw_addressptr_addrp off0 ptr_capp w0 with
Somer, m′
⇒
None
⇒
None
=
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct store_res_ _ _ _ _ as rr m′ | eqn: Es ; try discriminate Hst

2 open

ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
w0 :
rr :
resunit
m′ :
Memory.mem
Es :
store_resw m raw_addressptr_addrp off0 ptr_capp w0 = Somerr, m′
Hst :
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

rewrite store_res_checked_ _ _ _ _ _ _ Ha Es in Hst

2 open

ge :
fr :
m :
Memory.mem
off0 :
Z
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
w0 :
rr :
resunit
m′ :
Memory.mem
Es :
store_resw m raw_addressptr_addrp off0 ptr_capp w0 = Somerr, m′
⊢
False
deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

discriminate Hst

deferred goal
ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

–simpl in Ha

ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
Hst :
let* x ≔ value_xge fr_envfr P v in
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

destruct value_x_ _ _ _ as x | ; simpl in Hst ; try discriminate Hst

ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
x :
Hst :
SomeRVal_
⇒
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
SomeRTrapwhy | SomeRUncheckedwhy
⇒
None
⇒
None
=
⊢
False

rewrite Ha in Hst

ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
x :
Hst :
match x with
⇒
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 xp m es in
_
⇒
None
=
⊢
False

destruct x ; try discriminate Hst

ge :
fr :
m :
Memory.mem
off0 :
Z
es :
listeffect
p :
why :
n :
Hq :
lookupn fr_envfr = SomeWPtrp
p0 :
Hst :
let* m′ ≔ pointer_store_effectsraw_addressptr_addrp off0 p0 m es in
=
⊢
False

destruct pointer_store_effects_ _ _ _ ; discriminate Hst

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
intros ge fr m i q x off need p why Ei Hq Ha Hst
destruct i ; simpl in Ei ; cases Ei

No other instruction is a raw access.

all: try discriminate Ei
all: injection Ei as ← ← ← ← ; subst
all: try rewrite inst_step_let in Hst by reflexivity
all: rewrite Hq in Hst

raw_load: the value loaded is a value, not unchecked.

–assert Ha1 := cap_access_align_one_ _ _ _ _ _ Ha
destruct int_load_res_ _ _ _ _ eqn: El ; simpl in Hst ; | discriminate Hst
destruct int_load_res_checked_ _ _ _ _ _ Ha1 El as x′ →
simpl in Hst
discriminate Hst

raw_load_pointer: its check is the one that passed.

–simpl in Ha ; rewrite Ha in Hst
destruct k ; try discriminate Hst
destruct pointer_load_effects_ _ _ ; discriminate Hst

raw_store: the store succeeds.

–destruct width_value_classw ; simpl in Hst ; try discriminate Hst
destruct value_x_ _ _ _ ; simpl in Hst ; try discriminate Hst
destruct store_res_ _ _ _ _ as rr m′ | eqn: Es ; try discriminate Hst
rewrite store_res_checked_ _ _ _ _ _ _ Ha Es in Hst
discriminate Hst

raw_store_pointer: its check is the one that passed.

–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

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.

243Lemma covered_access_not_unchecked
∀ ge fr m i q lo hi r al p why
covered_accessi q lo hi r al = true
lookupq fr_envfr = SomeWPtrp
check_passesm p lo hi r al
inst_stepge fr m i ≠ SomeIStopUncheckedwhy
Explore proof 3 tactics

Initial goal

⊢
∀ge : genv fr : frame m : Memory.mem i : inst q : name lo hi : Z r : rights al : Z p : ptr why : reason, objects_fitm_regionsm → covered_accessi q lo hi r al = true → lookupq fr_envfr = SomeWPtrp → check_passesm p lo hi r al → inst_stepge fr m i ≠ SomeIStopUncheckedwhy

intros ge fr m i q lo hi r al p why Hfit Hc Hq Hp

ge :
fr :
m :
Memory.mem
i :
q :
lo, hi :
Z
al :
Z
p :
why :
Hc :
covered_accessi q lo hi r al = true
Hq :
lookupq fr_envfr = SomeWPtrp
Hp :
check_passesm p lo hi r al
⊢
inst_stepge fr m i ≠ SomeIStopUncheckedwhy

destruct covered_access_checked_ _ _ _ _ _ _ _ Hfit Hc Hp as x & off & need & Ei & Ha

ge :
fr :
m :
Memory.mem
i :
q :
lo, hi :
Z
al :
Z
p :
why :
Hc :
covered_accessi q lo hi r al = true
Hq :
lookupq fr_envfr = SomeWPtrp
Hp :
check_passesm p lo hi r al
off :
Z
need :
Ei :
raw_accessi = Someq, x, off, need
⊢
inst_stepge fr m i ≠ SomeIStopUncheckedwhy

exact access_ok_not_unchecked_ _ _ _ _ _ _ _ _ _ Ei Hq Ha

No remaining goals.

Qed

✓ Proof checked and closed by Rocq.

Source script
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