Fil-C on Nix

Filnix wiki

the formal campaign

rocq/glibc/SayLogic.v

rocq/glibc/say.c, linked with nanofil's IR of user glibc's string/strlen.c and io/write.c, through the program logic of Logic.v (docs/glibc-ir.md).

main writes the literal "hello, glibc\n" to descriptor 1 with write(1, msg, strlen(msg)). Both calls run glibc's own IR: strlen is __strlen's word-at-a-time scan, taken by StrlenLogic.v's triple wp_glibc_strlen, and write is the alias of __libc_write, whose body calls libpizlo's zsys_write and returns what it returns. The linked module defines everything but zsys_write, so that one name is the registry's, with the trusted contract of ZsysWrite.v; the rest is proved.

The world is ZsysWrite.v's fd_world, interpreted by fd_wi for descriptor 1: errno a writable int apart from the literal, and descriptor 1 not libpizlo's log. ZsysWrite.v names what the world is trusted to be: the thread's own allocated errno, glibc's errno handler registered, no errno logging. say_logic_safe is the labelled machine's safety of main from any such memory and world holding the literal, with the result 0.

From iris.proofmode Require Import proofmode
From iris.base_logic.lib Require Import gen_heap
From iris.program_logic Require Import language weakestpre
From Stdlib Require Import String ZArith Lia
From Nanofil Require Import Term Syntax Values Memory Runtime Ops Semantics Run Machine Panics StepRules ExternalCalls ExternalMachine Transport Pieces Heap ContractFrame Language Logic
From Glibc Require Import SayCode GlibcLogic ZsysWrite StrlenLogic
Open Scope Z_scope
Open Scope list_scope

The module

The checked module: say.c's main and its literal, glibc's __strlen and __libc_write with their aliases (say_term).

36Definition say_module: module ≔
Somemd
⇒
md
None
⇒
[ ]

The fixture decodes to say_module.

40Lemma say_decodes
Proof 2 steps Qed
vm_compute
reflexivity

The address of the literal msg, renamed say#msg by link.pl.

44Definition msg_base: Z ≔
65552

The literal's capability, read-only.

47Definition msg_ptr: ptr ≔

The literal's region: its 14 bytes rounded up to 16.

50Definition msg_reg: region ≔

The module's symbols, as laying it out places them.

53Definition say_globals: listname × ptr ≔
TAtom"write", mkPtr65600 FnTAtom"__libc_write"; TAtom"strlen", mkPtr65584 FnTAtom"__strlen"; TAtom"__libc_write", mkPtr65600 FnTAtom"__libc_write"; TAtom"__strlen", mkPtr65584 FnTAtom"__strlen"; TAtom"say#msg", msg_ptr; TAtom"main", mkPtr65536 FnTAtom"main"

Laying out the module gives say_globals.

62Lemma say_layout
Proof 2 steps Qed
vm_compute
reflexivity

The function named n of the module, or an empty one.

66Definition say_fnn : string : func ≔
SomeDefinedf
⇒
f
_
⇒
mkFuncTAtomn TAtom"export" RClassW [ ] [ ]

say.c's main.

73Definition main_fn: func ≔
Eval vm_compute in say_fn"main"

glibc's __strlen.

75Definition strlen_fn: func ≔
Eval vm_compute in say_fn"__strlen"

glibc's __libc_write.

77Definition write_fn: func ≔
Eval vm_compute in say_fn"__libc_write"

The literal's pieces

The literal's first word, "hello, g", little-endian.

82Definition msg_w0: Z ≔
7430988242233353576

Its second word, "libc\n" and the NUL, then the two zero bytes the layout's rounding adds.

85Definition msg_w1: Z ≔
44617066860

The pieces the program owns: the literal's life and its two words.

88Definition msg_ps: listpiece × pval ≔

The pieces' keys are distinct.

92Lemma msg_ps_nodup
NoDupmsg_ps.*1
Proof 3 steps Qed
cbn
repeat apply NoDup_cons_2 ; intros H ; apply list_elem_of_In in H ; cbn in H ; repeat destruct H as H | H ; first discriminate | injection H ; unfold msg_base ; lia | exact H |
apply NoDup_nil_2

Every piece is of the literal's object.

101Lemma msg_ps_id
∀ l v
l, v ∈ msg_ps
Proof 4 steps Qed
intros H
apply list_elem_of_In in H
cbn in H
repeat destruct H as H | H ; first injection H as ← _ ; reflexivity | contradiction

Where the pieces agree, the literal's 13 bytes are readable through its capability: what zsys_write's precondition asks of the buffer.

109Lemma msg_readable
Proof 29 steps Qed
intros Ha
unfold msg_ps in Ha
apply all_agree_app in Ha as Hl _ Ha
apply all_agree_app in Ha as H0 H1
rewrite all_agree_cell in H0
rewrite all_agree_cell in H1
cbn [ agree_piece fst snd ] in Hl
destruct Hl as E Lv
split ; lia |
split ; exists msg_base, msg_reg ; auto |
split
–apply access_read_ msg_base msg_reg ptr_capmsg_ptr ; right ; reflexivity | exact E | | | ; cbn [ ptr_addr msg_ptr msg_reg r_end ] ; unfold msg_base ; lia | lia | apply Z.mod_1_r
–intros i Hi
destruct Z.lt_ge_casesi 8 as Hi8 | Hi8
+destruct H0i ltac:lia as _ Hin
destruct Hinmsg_reg E Lv as _ & _ & Hb
replace msg_base + i with msg_base + 0 + i by lia
rewrite Hb
unfold byte_of
apply Z.mod_pos_bound
lia
+destruct H1i − 8 ltac:lia as _ Hin
destruct Hinmsg_reg E Lv as _ & _ & Hb
replace msg_base + i with msg_base + 8 + i − 8 by lia
rewrite Hb
unfold byte_of
apply Z.mod_pos_bound
lia

The contracts

The registry: zsys_write's contract alone; everything else the program calls is in the module.

130Definition say_registrysymbol : name : optioncontractfd_world ≔
name_eqbsymbol TAtom"zsys_write"
→
else
None

main called with no arguments.

134Definition main_entry: frame ≔
mkFramemain_fn [ ] [ ] None EnterTAtom"start" None

Over any runtime

The proof over the runtime R.

139Module SayLogic R : Runtime
140Module LG ≔ Logic R
141Module GL ≔ GlibcLogicOn R LG
142Module ZW ≔ ZsysWriteOn R LG
143Module SO ≔ StrlenOn R LG
144Module L ≔ LG.L
Import L LG GL ZW

The linked genv: the module, its symbols, R's free.

148Definition say_ge: genv ≔

A call of strlen runs __strlen.

151Lemma find_strlen
Proof 2 steps Qed
vm_compute
reflexivity

A call of write runs __libc_write.

155Lemma find_write
Proof 2 steps Qed
vm_compute
reflexivity
158Section wp
159Context `{!invGS_genhlc Σ, !gen_heapGSpiece pval Σ}

The Iris instance of say.c: zsys_write's contract and fd_wi for descriptor 1.

163Instance say_irisGS: irisGS_genhlc nanofil_langsay_registry say_ge Σ ≔
nanofil_irisGSsay_registry fd_wi1 say_ge

The expressions of say.c's language.

167Notation sexpr ≔ language.exprnanofil_langsay_registry say_ge

glibc's strlen, called with the literal, owning its pieces: wp_glibc_strlen with its two words, returning 13.

171Lemma strlen_msg_spec
∀ Φ
ptsmsg_ps −∗ ptsmsg_ps −∗ ΦRetWInt13 −∗ WPERunmkFramestrlen_fn TAtom"v0", WPtrmsg_ptr [ ] None EnterTAtom"start" None : sexpr {Φ}
Proof 30 steps Qed
iIntros Hps HΦ
rewrite / msg_ps ! pts_app
iDestruct Hps as (Hl & H0 & H1)
–right
reflexivity
–vm_compute
reflexivity
–vm_compute
reflexivity
–vm_compute
congruence
–vm_compute
congruence
–vm_compute
congruence
–repeat constructor ; vm_compute ; congruence
–split ; vm_compute ; reflexivity |
intros u Hu
do 13 destruct u as | u ; vm_compute ; congruence |
lia
–cbn [ words_ps ]
rewrite app_nil_r pts_app
iFrame
–iIntros Hl Hps
cbn [ words_ps ]
rewrite app_nil_r pts_app
iDestruct Hps as [H0 H1]
iApply HΦ
iFrame

main, owning the literal, returns 0: glibc's strlen measures it, glibc's write hands it to zsys_write for descriptor 1, whatever that returns, and the pieces are still owned.

195Lemma main_spec
ptsmsg_ps −∗ WPERunmain_entry : sexpr {o. ⌜o = RetWInt0⌝}
Proof 24 steps Qed
iIntros Hps
repeat step
iApply wp_call_bind ; side | exact find_strlen | side |
iNext
iApply strlen_msg_spec with Hps
iIntros Hps
iExists _
iSplit ; iPureIntro ; reflexivity |
iNext
iApply wp_call_bind ; side | exact find_write | side |
iNext
iApply wp_zsys_write1 say_registry say_ge with Hps ; reflexivity | side | side | side | left ; reflexivity | exact msg_readable |
iNext
iIntros k _ Hps
iApply wp_ret ; reflexivity | reflexivity |
iNext
iExists _
iSplit ; iPureIntro ; reflexivity |
iNext
iApply wp_ret ; reflexivity | reflexivity |
iNext
done

main is safe: from a ready runtime, live objects apart, a memory holding the literal as msg_ps says, and a world whose errno is a writable int outside the literal's object and whose log descriptor, if any, is not 1, with any fuel, no labelled run stops with a failure_ending, and a run that returns returns 0. By heap_labelled_safe from main_spec, the ghost heap starting with the literal's pieces.

221Theorem say_logic_safe
∀ Σ HinvP : invGpreSΣ HheapP : gen_heapGpreSpiece pval Σ m s w fuel
R.readys m
log_fdw ≠ Some1
∀a, span_containserrno_spanw a → ¬msg_base ≤ a < msg_base + 16
Proof 22 steps Qed
intros Hr Hd Ha Hw Hlog Hapart
–exact Hr
–exact Hd
–intros l v Hl
exact all_agree_elem_ _ _ _ Ha elem_of_list_to_map_2_ _ _ Hl
–split ; exact Hw |
split ; | constructor ; exact Hlog | constructor
intros sp a Hin Hs l & v & reg & Hl & _ & E _ & Hb
destruct Hin as [ <-| [ ] ]
apply elem_of_list_to_map_2 in Hl
rewrite msg_ps_id_ _ Hl in E , Hb
unfold msg_ps in Ha
apply all_agree_app in Ha as E′ _ _ _
cbn [ fst snd ] in E'
rewrite E' in E
injection E as ←
exact Haparta Hs Hb
–intros HinvG HheapG
rewrite big_sepM_list_to_map ; | exact msg_ps_nodup
iIntros Hps
iApply main_spec with Hps

The theorem for the interpreter's runtime.

244Module InterpSayLogic ≔ SayLogic InterpRuntime