Repository navigation
Expand file tree
/
Copy pathRun.v
More file actions
6827 lines (6078 loc) · 328 KB
/
Copy pathRun.v
File metadata and controls
6827 lines (6078 loc) · 328 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
(** * LinuxProcessSem.Run — Kleene-star trace semantics and trace equivalence
TRUST BOUNDARY: this file is part of the trusted specification.
Machine words are [bv 64], bytes are [bv 8], and the segment/stack
range arithmetic is in [Z] over unsigned values. [machine_state]
carries an LR/SC reservation field [ms_resv] (initialized [None];
cleared on each system call return, as Linux clears it — see
[advance_past_svc]).
A binary's observable behavior is its set of finite trace prefixes
plus TWO error facts: whether SOME execution can reach the explicit
error transition ([reaches_error]), and whether ALL executions must
reach it ([all_traces_error]). Equivalence is equality of prefix
sets (with an escape only when all source executions error — see
[Equivalence.equiv]). For the TARGET an error is fatal
([Equivalence.equiv] requires the target error-free). For the
SOURCE, the vacuity escape applies only when [all_traces_error]
proves that EVERY nondeterministic execution reaches error; one
erroring resolution is not enough when another resolution exits or
runs forever without error.
A behavior additionally records [reaches_unmodeled]: whether the run
can reach a configuration where THIS MODEL gave up, as opposed to one
where the PROGRAM died. The two are distinct — [MachineFault] and
[MachineUnmodeled] on the machine side, and on the syscall side an
errno-returning [Ok] versus the fail-closed [Unmodeled] — and the source
side of [Equivalence.strong_equiv] requires the model to cover the
source everywhere, so that its equivalence claim cannot be satisfied
by a semantics too weak to follow the binary. *)
From Stdlib Require Import ZArith NArith List String.
From LinuxProcessSemantics.LinuxProcessSem Require Import BvBase RiscvSemantics MemImageType StackLayout Fs State Monad Specs Vdso.
Import ListNotations.
Open Scope bv_scope.
Local Open Scope bool_scope.
(* =========================================================================
Trace prefixes and observable behaviors
========================================================================= *)
Fixpoint is_prefix {A : Type} (l1 l2 : list A) : Prop :=
match l1, l2 with
| [], _ => True
| _ :: _, [] => False
| x :: xs, y :: ys => x = y /\ is_prefix xs ys
end.
Lemma is_prefix_refl {A} : forall (l : list A), is_prefix l l.
Proof. induction l; cbn; auto. Qed.
Lemma is_prefix_nil {A} : forall (l : list A), is_prefix [] l.
Proof. destruct l; cbn; auto. Qed.
Lemma is_prefix_trans {A} : forall (l1 l2 l3 : list A),
is_prefix l1 l2 -> is_prefix l2 l3 -> is_prefix l1 l3.
Proof.
induction l1 as [|x l1 IH]; cbn; [auto|].
destruct l2 as [|y l2]; cbn; [contradiction|].
destruct l3 as [|z l3]; cbn; [contradiction|].
intros [-> H1] [-> H2]; eauto.
Qed.
Lemma is_prefix_app {A} : forall (l1 l2 : list A), is_prefix l1 (l1 ++ l2).
Proof. induction l1; cbn; auto. Qed.
(** Everything observable about one binary on one input: its finite
trace prefixes, whether it CAN reach the error transition, whether
EVERY execution MUST reach the error transition, and whether it can
reach a place where THIS MODEL — rather than the program — gave up.
The two error propositions deliberately have different quantifiers:
the source escape consumes [bh_all_errors], while target safety
consumes [~ bh_errors].
[bh_unmodeled] is not an observation about the program at all; it is
an observation about the semantics' COVERAGE of the program, and it
is what the [modeled] clause of [Equivalence.strong_equiv] rules out
for the source. It is a strict sub-case of [bh_errors]: everything
unmodeled errors, but not everything that errors is unmodeled (see
[reaches_unmodeled_reaches_error]). *)
Record behavior := mkBehavior {
bh_traces : list event -> Prop;
bh_errors : Prop;
bh_all_errors : Prop;
bh_unmodeled : Prop;
}.
(* =========================================================================
Applying a chosen syscall effect to the machine
========================================================================= *)
(** The decoded syscall argument registers a0..a5 at the [ecall]. *)
Definition syscall_args (ms : machine_state) : list word :=
[ms_gpr ms 0; ms_gpr ms 1; ms_gpr ms 2; ms_gpr ms 3; ms_gpr ms 4; ms_gpr ms 5].
Fixpoint apply_writes (mem : word -> option byte) (ws : list (word * list byte))
: word -> option byte :=
match ws with
| [] => mem
| (a, bs) :: r => apply_writes (write_to_mem mem a bs) r
end.
(** Is [a] inside one of the (base, size) ranges? Computed in [Z] over
unsigned values (grant ranges never wrap; see Specs.v). *)
Definition zeros_cover (zs : list (word * word)) (a : word) : bool :=
existsb (fun z => Z.leb (bv_unsigned (fst z)) (bv_unsigned a)
&& Z.ltb (bv_unsigned a)
(bv_unsigned (fst z) + bv_unsigned (snd z))) zs.
(** Zero-fill the effect's granted ranges (anonymous mmap/brk memory):
every covered address reads as byte 0, REPLACING whatever was
there. Kept as a functional overlay so multi-megabyte grants never
materialize byte lists. *)
Definition apply_zeros (mem : word -> option byte) (zs : list (word * word))
: word -> option byte :=
match zs with
| [] => mem
| _ => fun a => if zeros_cover zs a then Some (Z_to_bv 8 0) else mem a
end.
(** Erase the effect's inaccessible ranges (munmap, a PROT_NONE
mapping, mremap, or the tail a brk shrink frees — see
[State.eff_unmaps]): every covered address becomes UNMAPPED in the
writable overlay, so a later load faults instead of reading stale
bytes, as on Linux. The SPECS only unmap recorded anonymous mappings,
their subranges, or ranges of them and free pages, disjoint from every
loaded segment and from the stack, so erasing the overlay really makes the range inaccessible
(there is no segment underneath for reads to fall back to). *)
Definition apply_unmaps (mem : word -> option byte) (us : list (word * word))
: word -> option byte :=
match us with
| [] => mem
| _ => fun a => if zeros_cover us a then None else mem a
end.
(** Apply symbolic copies against an immutable snapshot of the memory from
BEFORE this syscall effect. Destination ranges use list order (later
copies override earlier ones); every source read uses [before], never a
range already zeroed, copied, or unmapped by the effect. *)
Definition apply_copy (before mem : word -> option byte) (c : MemCopy)
: word -> option byte :=
fun a =>
if Z.leb (bv_unsigned (copy_dst c)) (bv_unsigned a)
&& Z.ltb (bv_unsigned a)
(bv_unsigned (copy_dst c) + bv_unsigned (copy_len c))
then before (Z_to_bv 64
(bv_unsigned (copy_src c)
+ (bv_unsigned a - bv_unsigned (copy_dst c))))
else mem a.
Fixpoint apply_copies (before mem : word -> option byte) (cs : list MemCopy)
: word -> option byte :=
match cs with
| [] => mem
| c :: r => apply_copies before (apply_copy before mem c) r
end.
(** Apply a chosen effect: set a0 (= x10) to the return value, snapshot the
pre-effect memory, erase the unmapped ranges, zero-fill the granted
ranges, copy preserved bytes from the snapshot, and write exactly the
declared byte ranges. SP, every other GPR, the LR/SC reservation,
ROM, and all memory outside the declared ranges are preserved BY
CONSTRUCTION — the generative spec cannot silently rewrite anything
it did not declare, so no frame side-conditions are needed.
(Mechanically, writes land in the writable overlay [ms_mem] at
whatever addresses the effect declares; the SPECS guarantee those
addresses are writable-mapped — output buffers are checked against
[in_wmem], the copy_to_user/EFAULT analogue, zero ranges are fresh
anonymous grants, mremap growth tails, noaccess pages made rw, or a
live rw range replaced by MAP_FIXED or zapped by
madvise(MADV_DONTNEED), and unmap ranges are tracked anonymous
subranges. A moved-growing mremap
deliberately combines all three symbolic ledgers; the ordering above
preserves its old prefix. A brk transition either grows (zeros, no
unmaps) or shrinks (unmaps, no zeros).) *)
Definition apply_effect (ms : machine_state) (eff : SyscallEffect)
: machine_state :=
let ms' := set_reg ms 10 (eff_ret eff) in
{| ms_regs := ms_regs ms'; ms_fregs := ms_fregs ms';
ms_pc_val := ms_pc_val ms';
ms_svc_pending := ms_svc_pending ms';
ms_resv := ms_resv ms'; ms_fcsr := ms_fcsr ms';
ms_mem := apply_writes
(apply_copies (ms_mem ms')
(apply_zeros (apply_unmaps (ms_mem ms') (eff_unmaps eff))
(eff_zeros eff))
(eff_copies eff))
(eff_writes eff);
ms_rom := ms_rom ms' |}.
(** Advance PC past the ecall instruction (+4), clear svc_pending, and
CLEAR THE LR/SC RESERVATION.
Linux breaks the reservation on every return to user mode.
[ret_from_exception] (arch/riscv/kernel/entry.S, Linux v6.18.46,
commit 1f99e9ab748f) ends with
REG_L a2, PT_EPC(sp)
REG_SC x0, a2, PT_EPC(sp)
above the comment "so instead here we clear any existing reservation
-- it's always legal for implementations to clear load reservations
at any point". An [ecall] from user mode enters [handle_exception],
which dispatches [do_trap_ecall_u] and then jumps to
[ret_from_exception], so that [REG_SC] runs on the syscall return
too. The unprivileged specification (the A extension, LR/SC) makes
that enough: "An SC must fail if there is another SC (to any
address) between the LR and the SC in program order". So after
[lr.w a0,(s0); ecall; sc.w a1,a2,(s0)] the [sc] fails on Linux,
whatever the memory holds.
QEMU user mode answers otherwise: its syscall path
([RISCV_EXCP_U_ECALL] in [cpu_loop], linux-user/riscv/cpu_loop.c,
QEMU 10.0.11) never writes [env->load_res], and the only
[load_res = -1] outside CPU reset and [gen_sc] is in
[riscv_cpu_set_mode] (target/riscv/cpu_helper.c), which
[CONFIG_USER_ONLY] builds out. So the [sc] of that sequence can
succeed under qemu-user. LPS describes Linux v6.18.46, so it
answers Linux's; SCOPE.md's list "Where QEMU user mode differs"
carries the difference. *)
Definition advance_past_svc (ms : machine_state) : machine_state :=
{| ms_regs := ms_regs ms; ms_fregs := ms_fregs ms;
ms_pc_val := ms_pc ms + Z_to_bv 64 4;
ms_svc_pending := None;
ms_resv := None; ms_fcsr := ms_fcsr ms;
ms_mem := ms_mem ms;
ms_rom := ms_rom ms |}.
(* =========================================================================
Configurations and the one-step relation
========================================================================= *)
Record config := mkCfg {
cfg_ms : machine_state;
cfg_model : Model;
}.
(** The address space the kernel already used at [execve]: each LOAD
segment, PAGE-ROUNDED. Segments are [N]-based snapshot data far
below 2^64, so the rounding in [Z] re-enters [word] losslessly. *)
Definition segment_reservation (s : Segment) : word * word :=
let lo := page_round_down_Z (Z.of_N (seg_base s)) in
let hi := page_round_up_Z (Z.of_N (seg_base s) + Z.of_N (seg_size s)) in
(Z_to_bv 64 lo, Z_to_bv 64 (hi - lo)).
(** The LOADER's reservations only. [run] puts the kernel's own vDSO
text and vvar pages into the same segment list (see
[MemImageType.seg_kernel_map] and [vdso_segments] below), and they
are reserved by [State.init_reserved], from the ledger's own
[State.vdso_reserved]. Counting them here as well would put the
pair's top ([vdso_pair_top]: the mmap base, or the lower
[page_round_down (sp - stack_max_size)] on the launches SCOPE.md's
R-a describes) into [valid_brk]'s [reserved_top], and no Linux break
is up there. *)
Definition segments_reserved (segs : list Segment) : list (word * word) :=
map segment_reservation (filter (fun s => negb (seg_kernel_map s)) segs).
(** ** The pair [execve] installs
Linux maps the vDSO text directly below [mm->mmap_base] and the
four vvar data pages directly below the text
([__setup_additional_pages], arch/riscv/kernel/vdso.c, reached
through [ARCH_SETUP_ADDITIONAL_PAGES] in [load_elf_binary],
fs/binfmt_elf.c, Linux v6.18.46, commit 1f99e9ab748f). The model
maps them there when [sp - stack_max_size] is at or above the base,
and lower otherwise ([vdso_pair_top]; SCOPE.md, R-a). The ledger
reserves exactly the range the model maps ([State.vdso_reserved] at
[State.vdso_top]); these are the same two ranges as SEGMENTS, so
that a load, a store and a fetch there are answered by the rules
every other address is answered by.
The TEXT carries the chosen image's bytes and is READABLE, so a
libc's lookup reads the ELF header, the program headers, the
dynamic section and the symbol, string and version tables with
ordinary machine loads. It is marked WITHOUT 'x', although Linux
maps it PROT_READ|PROT_EXEC: the model's 'x' flag says "the model
fetches and executes these bytes", and of the vDSO's bytes it does
not — [Run.sstep]'s vDSO arm answers a call to an exported entry
with the system call's own specification, and
[RiscvSemantics.fetch_failure] answers every other address of the
text [MachineUnmodeled]. SCOPE.md names the difference.
The VVAR pages are readable and carry NO bytes, which is the
model's statement that it has the pages but not their contents.
Neither mapping is writable: the kernel maps both without
[VM_WRITE], so a store into either is the SIGSEGV
[RiscvSemantics.store_ok] delivers.
The pair is EMPTY when the ledger reserves nothing — a stack
pointer and a base so low that the pair would run off the bottom of
the address space, which [State.vdso_reserved] declines. Such a
launch is not one Linux makes, and the entry premises exclude it;
the model simply has no pair there. *)
(** THE PAIR'S TOP: the mmap base, or [sp - stack_max_size] where that
is lower, each rounded down to a page — the ceiling of the model's
top-down search ([State.mmap_top]), from which the ledger reserves
the pair ([State.vdso_top]). Where [sp - stack_max_size] is below
the base, this is lower than the base Linux places the pair under;
SCOPE.md's R-a says when that happens. *)
Definition vdso_pair_top (sp mbase : word) : Z :=
page_round_down_Z
(Z.min (bv_unsigned mbase)
(page_round_down_Z (bv_unsigned sp - stack_max_size))).
(** THE TEXT'S START, T pages below the pair's top. It is the ONE
definition of where the text is: [vdso_segments] maps the text there
and [launch_auxv] publishes it as AT_SYSINFO_EHDR, so a C library
that looks the vDSO up through the auxiliary vector finds the text
the run maps ([VdsoSegs.launch_auxv_sysinfo_ehdr_is_the_text]). *)
Definition vdso_text_base (kb : KernelBuild) (sp mbase : word) : word :=
Z_to_bv 64 (vdso_pair_top sp mbase - vdso_text_pages kb * page_size).
Definition vdso_segments (kb : KernelBuild) (sp mbase : word) : list Segment :=
let top := vdso_pair_top sp mbase in
let base := (top - vdso_len kb)%Z in
if (base <? page_size)%Z then []
else
let im := vdso_image_of kb in
[ {| seg_base := Z.to_N base;
seg_size := Z.to_N (vdso_vvar_pages * page_size);
seg_perms := "r--"%string;
seg_bytes := []; seg_kind := SegVdsoVvar |}
; {| seg_base := Z.to_N (bv_unsigned (vdso_text_base kb sp mbase));
seg_size := Z.to_N (vdso_text_pages kb * page_size);
seg_perms := "r--"%string;
seg_bytes := vi_bytes im; seg_kind := SegVdsoText |} ].
(** OPAQUE TO REDUCTION, and that is a performance decision with a
measured cause. The text segment carries the whole measured image
— 5704 bytes in twelve chunks — so a [vm_compute] of any term that
mentions the run's segment list normalizes those bytes, even when
the address it is asking about lies in the binary's own segments
and [find_segment] answers before it reaches the pair. One
[Example] of [Checks.Omni] ran for 59 minutes that way.
Opaque, the pair is one symbol: [find_segment] tests the binary's
segments, which come first, answers there, and never forces it.
Every fixture that is not ABOUT the vDSO therefore computes as it
did before the pair existed. A proof that IS about the vDSO —
[Checks.Cases.Kernel.Vdso] — writes [Local Transparent
vdso_segments] and pays the cost once. *)
Global Opaque vdso_segments.
(** The segment list a RUN is read against: the binary's LOAD segments
and the pair above. [Run.run] and every variant beside it use
this, and nothing else does, so the binary's own list stays what
[valid_brk] and [Equivalence.image_phdrs_readable] read. *)
Definition run_segments (segs : list Segment) (inp : ProcInput)
(sp mbase : word) : list Segment :=
segs ++ vdso_segments (in_kernel inp) sp mbase.
(** Where a step can go: on to another configuration, or the explicit
error transition. *)
Inductive step_to :=
| SNext (c : config)
| SError.
Section WithMemImage.
Variable mi_loaded_segments : list Segment.
Variable mi_init_pc : N. (* [N]-based snapshot datum (MemImage) *)
(** Where the binary's program header table landed ([MemImageType.PhdrInfo]):
[N]-based snapshot data like [mi_init_pc], published to the process
through AT_PHDR/AT_PHENT/AT_PHNUM in the initial stack's auxiliary
vector ([StackLayout.auxv_entries]). It is what lets a static libc
find PT_TLS and lay out thread-local storage; see [PhdrInfo]. *)
Variable mi_phdrs : PhdrInfo.
Variable mi_init_sp : word.
(** The initial program break, chosen NON-DETERMINISTICALLY at [execve]
(brk ASLR), exactly like [mi_init_sp]: any [valid_brk] value —
page-aligned, from the page-rounded image top up to [brk_aslr_max]
above it — quantified INDEPENDENTLY for the two binaries in
[Equivalence.strong_universal_T]. It is not snapshot data, and a
target may not assume the source's break placement. Seeds
[State.init_model]'s [vm_brk]; [Mmap.brk_spec]'s query path
(brk(0)) reports it, as [sbrk(0)] observes on Linux. *)
Variable mi_init_brk : word.
(** The run's [mm->mmap_base], chosen NON-DETERMINISTICALLY at [execve]
exactly like [mi_init_sp] and [mi_init_brk]: any [valid_mmap_base]
value — page-aligned, within [State.mmap_base_min ..
State.mmap_base_max] — quantified INDEPENDENTLY for the two binaries
in [Equivalence.strong_universal_T]. On Linux the value is a
function of the stack rlimit, [stack_guard_gap], the layout
personality and sysctls, [vm.mmap_rnd_bits] and the mmap ASLR draw
([arch_pick_mmap_layout], mm/util.c:465-479, Linux v6.18.46, commit
1f99e9ab748f — the derivation is on [State.mmap_base_min] and the cap
on [State.mmap_base_max]); none of that is snapshot data, so the
model quantifies over the band instead. The band is exactly the set
of bases Linux gives under the assumptions SCOPE.md names
([Checks.Cases.MmapBase.sv48_band_is_linux_set]).
Seeds [State.init_model]'s [vm_mmap_base]. THE SPEC READS THAT
VALUE: both fresh-grant arms of [Mmap.mmap_spec], and [mremap]'s
move, choose their address with [Mmap.linux_place], whose top-down
half searches below [State.mmap_top], which is the minimum of this
base and [State.alloc_top] (see [Mmap.mmap_spec]'s PLACEMENT
section). The untrusted search in
theories/Common/PlacementSearch.v takes its floor as a bare argument
rather than off a [VmMaps]. The ASan plan checker's placement gate
([Common.AsanCeil.placement_ok]) reads it too; that gate is the
theorem [Common.AsanCeil.placement_policy_holds], proved from
[Mmap.linux_place], and no longer a hypothesis the checker names.
The PREDICATE over the value
is what [valid_entry] carries — see [valid_mmap_base]. *)
Variable mi_mmap_base : word.
(** The 16 bytes of startup entropy AT_RANDOM points at, drawn afresh at
[execve] exactly like [mi_init_sp], [mi_init_brk] and
[mi_mmap_base]: [create_elf_tables] (fs/binfmt_elf.c, Linux
v6.18.46, commit 1f99e9ab748f) calls
[get_random_bytes(k_rand_bytes, sizeof(k_rand_bytes))] and copies the
result onto the new stack for AT_RANDOM to point at. Carried as a
[bv 128] and serialized by [StackLayout.at_random_bytes]; unlike the
three placements it has NO validity predicate, because every 128-bit
value is a draw the kernel can make. Quantified INDEPENDENTLY for
the two binaries in [Equivalence.strong_universal_T], which is what
makes a program whose output depends on its startup entropy
unprovable against anything — the same treatment, for the same
reason, as a program that leaks its stack address. It is read by
exactly one thing, the last 16 bytes of
[StackLayout.build_stack_bytes]; no address in the layout moves with
it ([StackLayout.build_stack_bytes_split_random]).
Carried inside [StackLayout.EntryDraw] together with [ed_slack], the
bytes of the entry stack's last page ABOVE that block: the two are
the byte-level things [execve] settles that this model does not
determine, and both are read only through [entry_stack_image] below.
See that record for the kernel side of each and for why neither is
zeros. *)
Variable mi_draw : EntryDraw.
(** The run's backed anonymous-memory budget in bytes ([State.vm_limit]):
[State.vm_backing_used] may never rise above it, so the out-of-memory
point of an unboundedly-allocating program is forced — by a fixed
budget, not by a quantified draw. It is NOT determined
by the grant-and-free history alone: overlapping [vm_maps] entries
make the total depend on placement too (see [State.live_bytes]), and
[Equivalence.equiv] compares trace SETS, so the target must
reproduce every point the source can reach.
A PARAMETER of the semantics rather than a baked-in constant so
a caller can choose a small budget (exhaustion is then
cheap to reach);
[Equivalence.strong_equiv] pins it per role to
[State.source_alloc_limit]/[State.target_alloc_limit]. *)
Variable mi_alloc_limit : Z.
Let mi_step := RiscvSemantics.step mi_loaded_segments.
Let mi_step_accesses := RiscvSemantics.step_accesses mi_loaded_segments.
(** Execute one instruction and atomically charge every newly touched page in
a lazy anonymous reservation. The interpreter returns the complete access
report before this function changes the model, so an instruction spanning
two new pages either charges both or takes the fault transition. *)
Definition mi_account_step (ms : machine_state) (model : Model)
: machine_result (machine_state * Model) :=
match mi_step_accesses ms with
| MachineOk report =>
match materialize_model_accesses model (@accessed_ranges _ report) with
| Some model' => MachineOk (@access_value _ report, model')
| None => MachineFault
end
| MachineFault => MachineFault
| MachineUnmodeled => MachineUnmodeled
end.
(** Accounting is an overlay on the authoritative instruction semantics: a
successful accounted step has exactly the machine state produced by
[RiscvSemantics.step]. *)
Lemma mi_account_step_projects : forall ms model ms' model',
mi_account_step ms model = MachineOk (ms', model') ->
mi_step ms = MachineOk ms'.
Proof.
intros ms model ms' model' Haccount.
unfold mi_account_step, mi_step_accesses in Haccount.
remember (RiscvSemantics.step_accesses mi_loaded_segments ms) as stepped
eqn:Hstepped.
destruct stepped as [report| |]; [|discriminate|discriminate].
destruct (materialize_model_accesses model (@accessed_ranges _ report))
as [accounted|] eqn:Hmaterialized; [|discriminate].
inversion Haccount; subst.
pose proof (RiscvSemantics.drop_step_accesses mi_loaded_segments ms) as Hdrop.
rewrite <- Hstepped in Hdrop. cbn in Hdrop. symmetry. exact Hdrop.
Qed.
Lemma mi_account_step_model_frame : forall ms model ms' model',
mi_account_step ms model = MachineOk (ms', model') ->
m_fd model' = m_fd model /\
m_vmmaps model' = m_vmmaps model /\
m_vm_lazy model' = m_vm_lazy model /\
m_io model' = m_io model /\
m_fsys model' = m_fsys model /\
m_proc model' = m_proc model /\
m_lim model' = m_lim model.
Proof.
intros ms model ms' model' Haccount.
unfold mi_account_step, mi_step_accesses in Haccount.
destruct (RiscvSemantics.step_accesses mi_loaded_segments ms)
as [report| |] eqn:Hstepped; [|discriminate|discriminate].
destruct (materialize_model_accesses model (@accessed_ranges _ report))
as [accounted|] eqn:Hmaterialized; [|discriminate].
inversion Haccount; subst.
exact (materialize_model_accesses_frame model
(@accessed_ranges _ report) model' Hmaterialized).
Qed.
(** With no lazy mappings there is nothing to charge, so accounting erases
completely and preserves the model as well as the machine step. *)
Lemma mi_account_step_no_lazy : forall ms model,
m_vm_lazy model = [] ->
mi_account_step ms model =
match mi_step ms with
| MachineOk ms' => MachineOk (ms', model)
| MachineFault => MachineFault
| MachineUnmodeled => MachineUnmodeled
end.
Proof.
intros ms model Hlazy.
unfold mi_account_step, mi_step_accesses, mi_step.
remember (RiscvSemantics.step_accesses mi_loaded_segments ms) as stepped
eqn:Hstepped.
pose proof (RiscvSemantics.drop_step_accesses mi_loaded_segments ms) as Hdrop.
rewrite <- Hstepped in Hdrop.
rewrite <- Hdrop.
destruct stepped as [[ms' accesses]| |]; cbn; try reflexivity.
rewrite (materialize_model_accesses_no_lazy model accesses Hlazy).
reflexivity.
Qed.
(** The input handed to the syscall spec: the syscall number, the
argument registers, the COMPLETE pre-syscall memory ([ms_read_byte])
and the WRITABLE view ([ms_writable_byte]). *)
Definition sys_input (ms : machine_state) (x8 : word) : SyscallInput :=
mkInput x8 (syscall_args ms) (ms_read_byte ms)
(ms_writable_byte mi_loaded_segments ms).
(* -------------------------------------------------------------------------
A vDSO call
------------------------------------------------------------------------- *)
(** Read the caller-saved registers, in [Vdso.vdso_caller_saved]'s
order, and write them back from a draw's answer. A register the
draw's list is too short for keeps its value: a draw is a function
into [VdsoLeftovers] and nothing types its list's LENGTH, so the
model takes what the draw gives and no more. *)
Definition vdso_read_regs (ms : machine_state) : list word :=
map (fun r => ms_reg ms (Z_to_bv 5 r)) vdso_caller_saved.
Fixpoint vdso_write_regs (ms : machine_state) (rs : list Z) (vs : list word)
: machine_state :=
match rs, vs with
| r :: rs', v :: vs' =>
vdso_write_regs (set_reg ms (Z_to_bv 5 r) v) rs' vs'
| _, _ => ms
end.
(** The frame's bytes before the call. A byte the process has not
mapped reads 0 here rather than making the whole read fail: this is
an ARGUMENT to the draw, not an access the program made, and a draw
that is handed 0 for an unmapped byte still gives back a value the
write below declines to store. Nothing the program can observe
turns on it. *)
Fixpoint vdso_read_frame (m : word -> option byte) (a : word) (n : nat)
: list byte :=
match n with
| O => []
| S n' =>
(match m a with Some b => b | None => Z_to_bv 8 0 end)
:: vdso_read_frame m (a + 1) n'
end.
(** Store the draw's frame bytes, skipping every address the process
has not mapped WRITABLE. Skipping rather than faulting, and
skipping rather than creating a mapping, because the leftovers are
not a store the program made: on Linux the vDSO writes its own
frame inside the stack VMA, and a model that let them create
mappings below the stack window would answer a later load from an
address Linux faults on. *)
Fixpoint vdso_write_frame (m : word -> option byte) (a : word)
(bs : list byte) : word -> option byte :=
match bs with
| [] => m
| b :: rest =>
let m' := match wview mi_loaded_segments m a with
| Some _ => fun x => if bv_eqb x a then Some b else m x
| None => m
end in
vdso_write_frame m' (a + 1) rest
end.
Definition vdso_with_mem (ms : machine_state) (m : word -> option byte)
: machine_state :=
{| ms_regs := ms_regs ms; ms_fregs := ms_fregs ms;
ms_pc_val := ms_pc_val ms;
ms_svc_pending := ms_svc_pending ms;
ms_resv := ms_resv ms; ms_fcsr := ms_fcsr ms;
ms_mem := m; ms_rom := ms_rom ms |}.
Definition vdso_set_pc (ms : machine_state) (pc : word) : machine_state :=
{| ms_regs := ms_regs ms; ms_fregs := ms_fregs ms;
ms_pc_val := pc;
ms_svc_pending := None;
ms_resv := ms_resv ms; ms_fcsr := ms_fcsr ms;
ms_mem := ms_mem ms; ms_rom := ms_rom ms |}.
(** THE MACHINE STATE AFTER A vDSO CALL.
In the order the design states it: the draw's leftovers go into the
caller-saved registers and into [[sp - F, sp)]; then the system
call's own effect — its return value in a0 and the bytes it wrote
into the caller's buffers — goes on top, so the RESULT is the
specification's and not the draw's; then pc becomes ra.
The frame write takes AT MOST THE FIRST F BYTES of the draw's
[vl_frame], from [sp - F] up, so every byte it writes is one of the F
addresses [sp - F], ..., [sp - 1], with the 64-bit wrapping
arithmetic the machine's own addresses use. Where sp >= F, which is
every sp the launch lays out, that is the interval [[sp - F, sp)] and
no written byte is at or above sp. A draw is any function, and
nothing else bounds the length of the list it gives back; without
the [firstn], a draw longer than F would write over what the caller
keeps at and above sp, its saved registers and return address among
them. The measured image's functions write no memory but their own
frame below sp and the buffers their arguments point at, and F is
the largest such frame of the image ([Vdso.vi_frame]):
[measure/MEASUREMENT.md], "F, the largest frame" and "The
callee-saved registers and the memory writes", and the assumption
SCOPE.md states as "A vDSO function keeps the callee-saved registers
and sp". A draw shorter than F writes only its own bytes, from
[sp - F] up.
[tests/VdsoFrameBound.v] checks the bound on a draw of F + 64 bytes.
sp, gp, tp and s0-s11 are untouched, because they are not in
[Vdso.vdso_caller_saved] and neither [apply_effect] nor this
function writes a register outside it and a0. That is the psABI's
requirement on a compiled function, which the vDSO's functions are,
and [measure]'s step-5 report checks it against each image's
disassembly before the image joins the list. *)
Definition vdso_post (ms : machine_state) (model : Model) (f : N)
(eff : SyscallEffect) : machine_state :=
let ra := ms_reg ms 1 in
let lo := ms_sp ms - Z_to_bv 64 (Z.of_N f) in
let left := vdr_draw (m_vdso model) (vdr_calls (m_vdso model))
(vdso_read_regs ms)
(vdso_read_frame (ms_read_byte ms) lo (N.to_nat f))
(eff_ret eff) in
let ms1 := vdso_write_regs ms vdso_caller_saved (vl_regs left) in
let ms2 := vdso_with_mem ms1
(vdso_write_frame (ms_mem ms1) lo
(firstn (N.to_nat f) (vl_frame left))) in
vdso_set_pc (apply_effect ms2 eff) ra.
(** WHERE THE MODEL DECLINES A CALL, with the reason each case is a
decline rather than an answer:
- no system call number ([__vdso_getrandom], [__vdso_rt_sigreturn]
— see [Vdso.vdso_fn_sysno]);
- the specification itself declines, which is every number this
development has no arm for, and every argument shape the arm it
does have declines;
- the outcome returns [-EFAULT]. The vDSO writes the result
ITSELF, with an ordinary store through the caller's pointer, so a
bad pointer kills the process there; only its FALLBACK to the
system call turns a bad pointer into [-EFAULT]. Which of the two
a given call takes depends on the clock source, which this model
does not carry, so it covers neither;
- the outcome halts the process. No arm of a mapped number can,
and a model that let one halt through this arm would have to say
what the vDSO's own exit path is. *)
Definition vdso_call_unmodeled (ms : machine_state) (model : Model)
(fn : VdsoFn) : Prop :=
vdso_fn_sysno fn = None
\/ (exists n, vdso_fn_sysno fn = Some n
/\ syscall_spec (sys_input ms (Z_to_bv 64 n)) model Unmodeled)
\/ (exists n eff model' evs,
vdso_fn_sysno fn = Some n
/\ syscall_spec (sys_input ms (Z_to_bv 64 n)) model (Ok eff model' evs)
/\ (eff_ret eff = errno_ret EFAULT \/ m_halted model' <> None)).
(** One transition. *)
Inductive sstep : config -> list event -> step_to -> Prop :=
| sstep_instr : forall ms model ms' model',
m_halted model = None ->
ms_svc_pending ms = None ->
mi_account_step ms model = MachineOk (ms', model') ->
sstep (mkCfg ms model) [] (SNext (mkCfg ms' model'))
| sstep_instr_fault : forall ms model,
m_halted model = None ->
ms_svc_pending ms = None ->
mi_account_step ms model = MachineFault ->
sstep (mkCfg ms model) [] SError
(** The MODEL gave up on the instruction at pc.
The vDSO's text is not one of those places, which is what the last
premise says. [RiscvSemantics.step_accesses] answers
[MachineUnmodeled] for EVERY pc in the text — the model does not
run the vDSO's instructions — and at the ENTRY of an exported
symbol the three arms below say what the step is instead. Without
this premise both would fire, and every program that reads the
clock through its libc would reach the error transition. *)
| sstep_instr_unmodeled : forall ms model,
m_halted model = None ->
ms_svc_pending ms = None ->
mi_account_step ms model = MachineUnmodeled ->
vdso_entry_fn mi_loaded_segments (ms_pc ms) = None ->
sstep (mkCfg ms model) [] SError
(** A CALL TO AN EXPORTED vDSO ENTRY: one step, with the system call's
own specification applied to a0-a5.
The vDSO answers from the same clocks the system call reads and
falls back to the system call for everything else
([__cvdso_clock_gettime_common], lib/vdso/gettimeofday.c, Linux
v6.18.46, commit 1f99e9ab748f), so the return value, the bytes it
writes and the model it leaves are the system call's. Handing
[Specs.syscall_spec] the number rather than copying the
specification is what makes the two routes agree by construction:
see [Checks.Cases.Kernel.Vdso]'s agreement lemma, which is then a
statement about [sys_input] alone. *)
| sstep_vdso_call : forall ms model fn n eff model' model'' evs,
m_halted model = None ->
ms_svc_pending ms = None ->
mi_account_step ms model = MachineUnmodeled ->
vdso_entry_fn mi_loaded_segments (ms_pc ms) = Some fn ->
vdso_fn_sysno fn = Some n ->
syscall_spec (sys_input ms (Z_to_bv 64 n)) model (Ok eff model' evs) ->
eff_ret eff <> errno_ret EFAULT ->
m_halted model' = None ->
materialize_model_accesses model' (syscall_effect_accesses eff)
= Some model'' ->
sstep (mkCfg ms model) evs
(SNext (mkCfg (vdso_post ms model (vdso_frame mi_loaded_segments) eff)
(with_vdso_bump model'')))
(** The backed-memory budget refuses what the call would touch, exactly
as it can refuse a system call's ([sstep_syscall_materialization_fault]). *)
| sstep_vdso_materialization_fault : forall ms model fn n eff model' evs,
m_halted model = None ->
ms_svc_pending ms = None ->
mi_account_step ms model = MachineUnmodeled ->
vdso_entry_fn mi_loaded_segments (ms_pc ms) = Some fn ->
vdso_fn_sysno fn = Some n ->
syscall_spec (sys_input ms (Z_to_bv 64 n)) model (Ok eff model' evs) ->
eff_ret eff <> errno_ret EFAULT ->
m_halted model' = None ->
materialize_model_accesses model' (syscall_effect_accesses eff) = None ->
sstep (mkCfg ms model) [] SError
(** The model does not cover this call; [vdso_call_unmodeled] says
which case and why. Together with the two arms above, every
resolution of [Specs.syscall_spec] at an exported entry has an arm,
so no such configuration is STUCK. *)
| sstep_vdso_unmodeled : forall ms model fn,
m_halted model = None ->
ms_svc_pending ms = None ->
mi_account_step ms model = MachineUnmodeled ->
vdso_entry_fn mi_loaded_segments (ms_pc ms) = Some fn ->
vdso_call_unmodeled ms model fn ->
sstep (mkCfg ms model) [] SError
| sstep_syscall : forall ms model x8 eff model' model'' evs,
m_halted model = None ->
ms_svc_pending ms = Some x8 ->
syscall_spec (sys_input ms x8) model (Ok eff model' evs) ->
m_halted model' = None ->
materialize_model_accesses model' (syscall_effect_accesses eff)
= Some model'' ->
sstep (mkCfg ms model) evs
(SNext (mkCfg (advance_past_svc (apply_effect ms eff)) model''))
| sstep_syscall_materialization_fault : forall ms model x8 eff model' evs,
m_halted model = None ->
ms_svc_pending ms = Some x8 ->
syscall_spec (sys_input ms x8) model (Ok eff model' evs) ->
m_halted model' = None ->
materialize_model_accesses model' (syscall_effect_accesses eff) = None ->
sstep (mkCfg ms model) [] SError
| sstep_exit : forall ms model x8 eff model' evs code,
m_halted model = None ->
ms_svc_pending ms = Some x8 ->
syscall_spec (sys_input ms x8) model (Ok eff model' evs) ->
m_halted model' = Some code ->
m_killed model' = None ->
sstep (mkCfg ms model) (evs ++ [ExitEv code (m_fs model')])
(SNext (mkCfg ms model'))
(** The other way a process ends: a fatal signal it sent itself. Same
shape as [sstep_exit] and the same discarded effect -- the syscall
completes in the kernel and the process is killed on the way back to
user space, so what it wrote to its own memory is never read -- and
the two arms are disjoint by [m_killed], which [sstep_exit]
requires to be [None].
THE DECLARATION IS NOT A PREMISE HERE. For SIGABRT it is one
inside [Kernel.Signal.tkill_spec]; for SIGPIPE it is one inside
[Sys.Fs.ReadWrite.sigpipe_write], which declines the write while
[State.m_sigpipe_terminal] is clear. Putting a declaration here as
well would make this rule unable to fire on an outcome the spec
layer produced -- which is a STUCK configuration, not a decline,
and [sstep_cfg_progress] below would be false. What carries the
claim that no kill is reachable while the declarations are clear is
[kill_frame] below, consumed by [sstep_kill_off] and proved by
[Checks.KillFree.kill_frame_holds]. *)
| sstep_killed : forall ms model x8 eff model' evs sig,
m_halted model = None ->
ms_svc_pending ms = Some x8 ->
syscall_spec (sys_input ms x8) model (Ok eff model' evs) ->
m_killed model' = Some sig ->
sstep (mkCfg ms model) (evs ++ [KillEv sig (m_fs model')])
(SNext (mkCfg ms model'))
| sstep_syscall_unmodeled : forall ms model x8,
m_halted model = None ->
ms_svc_pending ms = Some x8 ->
syscall_spec (sys_input ms x8) model Unmodeled ->
sstep (mkCfg ms model) [] SError.
(** Kleene star of [sstep], accumulating events. *)
Inductive star : config -> list event -> config -> Prop :=
| star_refl : forall c, star c [] c
| star_step : forall c1 evs c2 tr c3,
sstep c1 evs (SNext c2) ->
star c2 tr c3 ->
star c1 (evs ++ tr) c3.
Lemma star_one : forall c evs c',
sstep c evs (SNext c') -> star c evs c'.
Proof.
intros c evs c' H. rewrite <- (app_nil_r evs).
econstructor; eauto using star_refl.
Qed.
Lemma star_trans : forall c1 t1 c2 t2 c3,
star c1 t1 c2 -> star c2 t2 c3 -> star c1 (t1 ++ t2) c3.
Proof.
intros c1 t1 c2 t2 c3 H1; revert t2 c3.
induction H1; intros t2 c3' H2; cbn; [assumption|].
rewrite <- app_assoc. econstructor; eauto.
Qed.
(* =========================================================================
Observable behavior: finite trace prefixes + reachability of error
========================================================================= *)
(** [tr] is an event-level prefix of an admissible run (prefix-closed at
BYTE granularity). *)
Definition obs_trace (c0 : config) (tr : list event) : Prop :=
exists tr' c, star c0 tr' c /\ is_prefix tr tr'.
Lemma obs_trace_nil : forall c0, obs_trace c0 [].
Proof.
intros c0. exists [], c0. split; [apply star_refl | apply is_prefix_nil].
Qed.
Lemma obs_trace_prefix_closed : forall c0 tr tr',
obs_trace c0 tr -> is_prefix tr' tr -> obs_trace c0 tr'.
Proof.
intros c0 tr tr' (tr'' & c & Hstar & Hp) Hp'.
exists tr'', c. eauto using is_prefix_trans.
Qed.
(* =========================================================================
No kill while every kill gate is closed: the frame and its consequences
========================================================================= *)
(** THE FOUR GATES, all closed. A [State.KillEv] enters a trace only
through [sstep_killed], which needs a spec outcome whose model has
[State.m_killed] set, and [State.with_killed] is called from exactly
four places in the spec layer, each behind one of these fields:
- [Sys.Fs.ReadWrite.raise_sigpipe] (signal 13), reached only through
[Sys.Fs.ReadWrite.sigpipe_write], which declines at EITHER
disposition while [State.m_sigpipe_terminal] is clear
([Sys.Fs.ReadWrite.sigpipe_write_off_unmodeled]), so with this
gate closed the write never reaches [raise_sigpipe] at all;
- [Kernel.Signal.sigmask_deliver_model]'s SIGPIPE branch, which needs
[State.m_sigpipe_pending], set only by [raise_sigpipe]'s blocked
branch;
- its SIGABRT branch, which needs [State.m_sigabrt_pending], set only
by [Kernel.Signal.send_sigabrt];
- [Kernel.Signal.send_sigabrt] itself, reached only through
[tkill]/[tgkill], which decline while [State.m_abort_terminal] is
clear.
The two declarations are written only by [State.init_model], and the
two pending bits only behind the declarations, so the four together
are an invariant. NEITHER PAIR ALONE IS ONE: a pending bit set with
its declaration clear is directly constructible, and the
[rt_sigprocmask] that uncovers it kills
([Checks.Cases.Kernel.Signal.decl_off_frame_one_sided_refuted]). *)
Definition kill_off (m : Model) : Prop :=
m_abort_terminal m = false /\ m_sigabrt_pending m = false
/\ m_sigpipe_terminal m = false /\ m_sigpipe_pending m = false.
(** A list of events carries no death by a signal. *)
Definition no_kill (evs : list event) : Prop :=
forall sig fs, ~ In (KillEv sig fs) evs.
(** THE FRAME, over every arm of the spec table: from a RUNNING model
with all four gates closed, an outcome keeps them closed, records no
kill and emits no [State.KillEv].
IT IS PROVED, NOT ASSUMED: [Checks.KillFree.kill_frame_holds] proves
it arm by arm over [Checks.Sys.Dispatch.checked_table] and carries it
to [Specs.syscall_spec] through [Checks.ExecutableSpecs.check_syscall_ok_iff].
It is stated here, and consumed as a premise by the run-level lemmas
below, only because this file cannot import the checker.
THE RUNNING PREMISE IS LOAD-BEARING. Without [m_halted m = None] a
model a signal has already killed meets the other premises, and any
arm that carries [State.ProcState] across hands its [m_killed] back;
the frame this one replaced, [decl_off_frame], lacked it and was
false, in the published model too. Every [sstep] rule that consumes
a spec outcome requires the model to be running, so the premise
costs the consumers below nothing. *)
Definition kill_frame : Prop :=
forall i m eff m' evs,
syscall_spec i m (Ok eff m' evs) ->
m_halted m = None ->
kill_off m ->
kill_off m' /\ m_killed m' = None /\ no_kill evs.
(** The ONE-SIDED form, which guards with the abort declaration alone.
It is FALSE, and kept ONLY so that
[Checks.Cases.Kernel.Signal.decl_off_frame_one_sided_refuted] has
something to refute: it is the shape a reader reaches for first --
the declaration is the switch, so surely the declaration is the
guard -- and the refutation says why that reading is wrong. Nothing
may consume it. *)
Definition decl_off_frame_one_sided : Prop :=
forall i m eff m' evs,
syscall_spec i m (Ok eff m' evs) ->
m_abort_terminal m = false ->
m_abort_terminal m' = false
/\ m_killed m' = None
/\ (forall sig fs, ~ In (KillEv sig fs) evs).
(** The four gates are fields of [State.ProcState], so a step that keeps
[State.m_proc] keeps them. *)
Lemma kill_off_proc : forall m1 m2,
m_proc m1 = m_proc m2 -> kill_off m2 -> kill_off m1.
Proof.
intros m1 m2 H.
unfold kill_off, m_abort_terminal, m_sigabrt_pending, m_sigpipe_terminal,
m_sigpipe_pending.
rewrite H. exact (fun x => x).
Qed.
(** One step from a model with the gates closed: they stay closed, and
the step's events carry no kill. *)
Lemma sstep_kill_off : kill_frame ->
forall ms model evs c',
kill_off model ->
sstep (mkCfg ms model) evs (SNext c') ->
kill_off (cfg_model c') /\ no_kill evs.
Proof.
intros Hframe ms model evs c' Hoff Hstep.
inversion Hstep; subst.
- (* instruction: accounting keeps [State.m_proc] fixed *)
match goal with
| [ H : mi_account_step _ _ = MachineOk (_, _) |- _ ] =>
destruct (mi_account_step_model_frame _ _ _ _ H) as (_&_&_&_&_&Hp&_)
end.
cbn [cfg_model]. split; [exact (kill_off_proc _ _ Hp Hoff) | intros sig fs []].
- (* a vDSO call: the syscall frame, then materialization, then the
call count -- and none of the last two touches [State.m_proc] *)
match goal with
| [ Hs : syscall_spec _ ?m0 (Ok _ ?m1 _), Hh : m_halted ?m0 = None,
Hm : materialize_model_accesses ?m1 _ = Some ?m2 |- _ ] =>
destruct (Hframe _ _ _ _ _ Hs Hh Hoff) as (Hoff' & _ & Hev);
destruct (materialize_model_accesses_frame _ _ _ Hm) as (_&_&_&_&_&Hp&_)
end.
cbn [cfg_model]. split; [| exact Hev].
eapply kill_off_proc; [| exact Hoff'].
rewrite m_proc_with_vdso_bump. exact Hp.
- (* a syscall that materializes: the frame, then materialization *)
match goal with
| [ Hs : syscall_spec _ ?m0 (Ok _ ?m1 _), Hh : m_halted ?m0 = None,
Hm : materialize_model_accesses ?m1 _ = Some ?m2 |- _ ] =>
destruct (Hframe _ _ _ _ _ Hs Hh Hoff) as (Hoff' & _ & Hev);
destruct (materialize_model_accesses_frame _ _ _ Hm) as (_&_&_&_&_&Hp&_)
end.
cbn [cfg_model]. split; [exact (kill_off_proc _ _ Hp Hoff') | exact Hev].
- (* exit: the post-model is the spec's, and the appended event is an
[ExitEv] *)
match goal with
| [ Hs : syscall_spec _ ?m0 (Ok _ _ _), Hh : m_halted ?m0 = None |- _ ] =>
destruct (Hframe _ _ _ _ _ Hs Hh Hoff) as (Hoff' & _ & Hev)
end.
split; [exact Hoff' |].
intros sig fs Hin. apply in_app_or in Hin.
destruct Hin as [Hin | [Hin | []]]; [exact (Hev _ _ Hin) | discriminate].
- (* kill: the frame says the outcome records no kill, which this rule
needs *)
match goal with
| [ Hs : syscall_spec _ ?m0 (Ok _ _ _), Hh : m_halted ?m0 = None |- _ ] =>
destruct (Hframe _ _ _ _ _ Hs Hh Hoff) as (_ & Hk & _)
end.
congruence.
Qed.
(** A whole execution from a configuration with the gates closed. *)