Reference. Ivy: A Multi-modal Verification Tool for Distributed Algorithms
Ivy is a multi-modal verification tool for correct design and implementation of distributed protocols and algorithms, supporting modular specification, implementation and proof. Ivy supports proving safety and liveness properties of parameterized and infinite-state systems via three modes: deductive verification using an SMT solver, abstraction and model checking, and manual proofs using natural deduction. It supports light-weight formal methods via compositional specification-based testing and bounded model checking. Ivy can extract executable distributed programs by translation to efficient C++ code. It is designed to support decidable automated reasoning, to improve proof stability and to provide transparency in the case of proof failures. For this purpose, it presents concrete finite counterexamples, automatically audits proofs for decidability of verification conditions, and provides modular hiding of theories.
Cite
Cited by (2)
Verus: A Practical Foundation for Systems Verification lattuada-2024-verus
Grove: A Separation-Logic Library for Verifying Distributed Systems sharmaGroveSeparationLogicLibrary2023
Grove is a concurrent separation logic library for verifying distributed systems. Grove is the first to handle time-based leases, including their interaction with reconfiguration, crash recovery, thread-level concurrency, and unreliable networks. This paper uses Grove to verify several distributed system components written in Go, including vKV, a realistic distributed multi-threaded key-value store. vKV supports reconfiguration, primary/backup replication, and crash recovery, and uses leases to execute read-only requests on any replica. vKV achieves high performance (67–73% of Redis on a single core), scales with more cores and more backup replicas (achieving about 2× the throughput when going from 1 to 3 servers), and can safely execute reads while reconfiguring.
Cites 30 works (1 here)
With notes (1)
Ivy: Safety verification by interactive generalization padonIvySafetyVerification
Despite several decades of research, the problem of formal verification of infinite-state systems has resisted effective automation. We describe a system — Ivy — for interactively verifying safety of infinite-state systems. Ivy’s key principle is that whenever verification fails, Ivy graphically displays a concrete counterexample to induction. The user then interactively guides generalization from this counterexample. This process continues until an inductive invariant is found. Ivy searches for universally quantified invariants, and uses a restricted modeling language. This ensures that all verification conditions can be checked algorithmically. All user interactions are performed using graphical models, easing the user’s task. We describe our initial experience with verifying several distributed protocols.
External (29)
- Ivy (tool website) (2020)
- Formal specification and testing of QUIC (2019)
- Inferring Inductive Invariants from Phase Structures (2019)
- The Rust Programming Language (2018)
- Temporal Prophecy for Proving Temporal Properties of Infinite-State Systems (2018)
- Modularity for decidability of deductive verification with applications to distributed systems (2018)
- Eager Abstraction for Symbolic Model Checking (2018)
- Reducing liveness to safety in first-order logic (2017)
- Modular specification and verification of a cache-coherent interface (2016)
- Horn clause solvers for program verification (2015)
- Dafny: an automatic program verifier for functional correctness (2010)
- ABC: An Academic Industrial-Strength Verification Tool (2010)
- Complete Instantiation for Quantified Formulas in Satisfiabiliby Modulo Theories (2009)
- Z3: An Efficient SMT Solver (2008)
- Assume-guarantee testing (2006)
- Interactive Theorem Proving and Program Development - Coq’Art: The Calculus of Inductive Constructions (2004)
- Deterministic second-order patterns (2004)
- Liveness Checking as Safety Checking (2002)
- Extended static checking for Java (2002)
- QuickCheck (2000)
- A methodology for hardware verification using compositional model checking (2000)
- Liveness and Acceleration in Parameterized Verification (2000)
- Model checking TLA+ specifications (1999)
- MOCHA: modularity in model checking (1998)
- Reactive modules (1996)
- Isabelle (1994)
- A Framework for Defining Logics (1993)
- The Esterel synchronous programming language: design, semantics, implementation (1992)
- Reduction (1975)