Separation logic is the twenty-first-century variant of Hoare logic that permits verification of pointer-manipulating programs. This book covers practical and theoretical aspects of separation logic at a level accessible to beginning graduate students interested in software verification. On the practical side it offers an introduction to verification in Hoare and separation logics, simple case studies for toy languages, and the Verifiable C program logic for the C programming language. On the theoretical side it presents separation algebras as models of separation logics; step-indexed models of higher-order logical features for higher-order programs; indirection theory for constructing step-indexed separation algebras; tree-shares as models for shared ownership; and the semantic construction (and soundness proof) of Verifiable C. In addition, the book covers several aspects of the CompCert verified C compiler, and its connection to foundationally verified software analysis tools. All constructions and proofs are made rigorous and accessible in the Coq developments of the open-source Verified Software Toolchain.
More info
This tutorial for graduate students covers practical and theoretical aspects of separation logic with constructions and proofs in Coq.
| Road map |
|
ix | |
| Acknowledgments |
|
x | |
|
|
|
1 | (8) |
|
I Generic separation logic |
|
|
9 | (66) |
|
|
|
10 | (6) |
|
|
|
16 | (9) |
|
4 Soundness of Hoare logic |
|
|
25 | (8) |
|
5 Mechanized Semantic Library |
|
|
33 | (2) |
|
|
|
35 | (9) |
|
7 Operators on separation algebras |
|
|
44 | (5) |
|
8 First-order separation logic |
|
|
49 | (6) |
|
|
|
55 | (8) |
|
10 Covariant recursive predicates |
|
|
63 | (6) |
|
|
|
69 | (6) |
|
II Higher order separation logic |
|
|
75 | (66) |
|
12 Separation logic as a logic |
|
|
76 | (8) |
|
13 From separation algebras to separation logic |
|
|
84 | (5) |
|
14 Simplification by rewriting |
|
|
89 | (5) |
|
15 Introduction to step-indexing |
|
|
94 | (5) |
|
16 Predicate implication and subtyping |
|
|
99 | (5) |
|
17 General recursive predicates |
|
|
104 | (7) |
|
18 Case study: Separation logic with first-class functions |
|
|
111 | (12) |
|
19 Data structures in indirection theory |
|
|
123 | (7) |
|
20 Applying higher-order separation logic |
|
|
130 | (4) |
|
21 Lifted separation logics |
|
|
134 | (7) |
|
III Separation logic for CompCert |
|
|
141 | (91) |
|
|
|
142 | (6) |
|
23 Expressions, values, and assertions |
|
|
148 | (5) |
|
24 The VST separation logic for C light |
|
|
153 | (20) |
|
25 Typechecking for Verifiable C |
|
|
173 | (11) |
|
26 Derived rules and proof automation for C light |
|
|
184 | (11) |
|
|
|
195 | (13) |
|
|
|
208 | (9) |
|
29 Dependently typed C programs |
|
|
217 | (5) |
|
30 Concurrent separation logic |
|
|
222 | (10) |
|
IV Operational semantics of CompCert |
|
|
232 | (62) |
|
|
|
233 | (4) |
|
32 The CompCert memory model |
|
|
237 | (35) |
|
33 How to specify a compiler |
|
|
272 | (16) |
|
34 C light operational semantics |
|
|
288 | (6) |
|
V Higher-order semantic models |
|
|
294 | (68) |
|
|
|
295 | (21) |
|
36 Case study: Lambda-calculus with references |
|
|
316 | (24) |
|
37 Higher-order Hoare logic |
|
|
340 | (7) |
|
38 Higher-order separation logic |
|
|
347 | (4) |
|
39 Semantic models of predicates-in-the-heap |
|
|
351 | (11) |
|
VI Semantic model and soundness of Verifiable C |
|
|
362 | (48) |
|
40 Separation algebra for CompCert |
|
|
363 | (11) |
|
|
|
374 | (11) |
|
|
|
385 | (7) |
|
43 Modeling the Hoare judgment |
|
|
392 | (9) |
|
|
|
401 | (5) |
|
45 Modular structure of the development |
|
|
406 | (4) |
|
|
|
410 | (32) |
|
46 Foundational static analysis |
|
|
411 | (15) |
|
|
|
426 | (16) |
| Bibliography |
|
442 | (10) |
| Index |
|
452 | |
Andrew W. Appel is the Eugene Higgins Professor and Chairman of the Department of Computer Science at Princeton University, New Jersey, where he has been on the faculty since 1986. His research is in software verification, computer security, programming languages and compilers, automated theorem proving, and technology policy. He is known for his work on Standard ML of New Jersey and on Foundational Proof-Carrying Code. He is a Fellow of the Association for Computing Machinery, recipient of the ACM SIGPLAN Distinguished Service Award, and has served as Editor in Chief of ACM Transactions on Programming Languages and Systems. His previous books include Compiling with Continuations (1992), the Modern Compiler Implementation series (1998 and 2002) and Alan Turing's Systems of Logic (2012).
More information about ebooks