New to Rocq? Read this document.
SLOT is a fully formally verified model checker that can prove safety properties of programs written in “SLOTLang”, a shallow-embedded DSL inspired by Erlang.
SLOTLang is an actor-based language capable of performing input-output operations in a simulated environment. It extends plain Gallina with 4 primitives:
- spawn: spawn a child process
- do: perform I/O operation
- yield: NOP, interrupts the computation
- die: terminate the process
They allow to write programs that (if you squint hard enough) resemble Erlang:
Let prog : prog_t h True :=
spawn c1 <- child1;
c1 ! 1;
spawn c2 <- child2;
c2 ! false;
die.I/O operations can be non-deterministic: they can fail, produce different results for the same input or block. This is sufficient, for example, to model network with packet loss and reordering. SLOT verification is total: it considers every possible outcome of such operations.
I/O is implemented via composable effect handlers. This makes SLOT extendable: user is allowed to define custom effects, and mix and match them with the existing ones.
SLOT uses setoid equivalence in every aspect. It considers states of programs and the environment equivalent according to the setoid rules. This greatly simplifies proofs involving complex data structures, such as hash tables and search trees.
SLOT uses symmetry reduction to limit the combinatorial explosion of execution paths in multi-threaded programs.
This is done via “trace canonicalization” process,
which works as following.
Of all permutations of commutative operations,
SLOT selects a single history according to an arbitrary symmetry-breaking relation.
This history is called “a canonical trace”.
Any invariant proven for the canonical trace can be extended to the full set of traces.
(See TokenMachine.canonicalize_trace theorem.)