A framework for formally verifying distributed systems implementations in Coq
Coq Shell Other
Latest commit ebd7bb5 Feb 23, 2017 @palmskog palmskog committed on GitHub Merge pull request #109 from uwplse/ordered-dynamic-labeled
added labeled semantics for step_ordered_dynamic

README.md

Verdi

Build Status

A framework for formally verifying distributed systems implementations in Coq.

Requirements

Framework:

Runtime:

Building

We recommend installing Verdi via OPAM, which will automatically build and install its dependencies.

opam repo add coq-released https://coq.inria.fr/opam/released
opam repo add distributedcomponents-dev http://opam-dev.distributedcomponents.net
opam install verdi

To build Verdi manually, it is a good idea to first consult the opam file for exact requirements.

Then, run ./configure in the Verdi root directory. This will check for the appropriate version of Coq and ensure all necessary dependencies can be located. By default, the script assumes that StructTact and InfSeqExt are installed in Coq's user-contrib directory, but this can be overridden by setting the StructTact_PATH and/or InfSeqExt_PATH environment variables.

Finally, run make in the Verdi root directory. This will compile the framework's core specifications and proofs, as well as some simple example systems and their correctness proofs.

Runtime Library

To run Verdi systems on real hardware, event handler code must be extracted to OCaml and linked with one of the shims in the Verdi runtime library that handles low-level network communication.

To install the runtime library via OPAM, make sure the distributedcomponents-dev repo has been added as above and use the following command:

opam install verdi-runtime

Documentation

In addition to the example verified systems listed below, see the scientific papers and blog posts listed at the Verdi website.

Files

  • Core Verdi files:
    • Verdi.v: exporting of core Verdi theories, imported by systems
    • Net.v: core (unlabeled) network semantics
    • LabeledNet.v: labeled network semantics, for use in liveness reasoning
    • HandlerMonad.v: a monad for writing network/input handlers
    • StatePacketPacket.v: a technique for writing easily decomposable invariants
  • Example systems:
    • Counter.v: counting server with backup
    • LockServ.v: lock server with proof of safety
    • LiveLockServ.v: lock server with proof of liveness
    • VarD.v: vard, a key-value store
  • Verified system transformers:
    • SeqNum.v and SeqNumCorrect.v, a system transformer implementing sequence numbering
      • LockServSeqNum.v, the sequence numbering transformer applied to the lock server
    • PrimaryBackup.v, a system transformer implementing asynchronous primary-backup replication
      • VarDPrimaryBackup.v, the primary-backup transformer applied to the key-value store

Projects using Verdi

  • Verdi Raft: a verified implementation of the Raft distributed consensus protocol