Reference. Deductive Verification in Decidable Fragments with Ivy
This paper surveys the work to date on Ivy, a language and a tool for the formal specification and verification of distributed systems. Ivy supports deductive verification using automated provers, model checking, automated testing, manual theorem proving and generation of executable code. In order to achieve greater verification productivity, a key design goal for Ivy is to allow the engineer to apply automated provers in the realm in which their performance is relatively predictable, stable and transparent. In particular Ivy focuses on the use of decidable fragments of first-order logic. We consider the rationale or Ivy’s design, the various capabilities of the tool, as well as case studies and applications.
Cite
Cited by (1)
Deductive Verification of Distributed Protocols in First-Order Logic padonDeductiveVerificationDistributed2018
Formal verification of infinite-state systems, and distributed systems in particular, is a long standing research goal. In the deductive verification approach, the programmer provides inductive invariants and pre/post specifications of procedures, reducing the verification problem to checking validity of logical verification conditions. This check is often performed by automated theorem provers and SMT solvers, substantially increasing productivity in the verification of complex systems. However, the unpredictability of automated provers presents a major hurdle to usability of these tools. This problem is particularly acute in case of provers that handle undecidable logics, for example, first-order logic with quantifiers and theories such as arithmetic. The resulting extreme sensitivity to minor changes has a strong negative impact on the convergence of the overall proof effort.
Cites 42 works (4 here)
With notes (4)
Deductive Verification of Distributed Protocols in First-Order Logic padonDeductiveVerificationDistributed2018
Formal verification of infinite-state systems, and distributed systems in particular, is a long standing research goal. In the deductive verification approach, the programmer provides inductive invariants and pre/post specifications of procedures, reducing the verification problem to checking validity of logical verification conditions. This check is often performed by automated theorem provers and SMT solvers, substantially increasing productivity in the verification of complex systems. However, the unpredictability of automated provers presents a major hurdle to usability of these tools. This problem is particularly acute in case of provers that handle undecidable logics, for example, first-order logic with quantifiers and theories such as arithmetic. The resulting extreme sensitivity to minor changes has a strong negative impact on the convergence of the overall proof effort.
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.
Decidability of inferring inductive invariants padonDecidabilityInferringInductive2016
Induction is a successful approach for verification of hardware and software systems. A common practice is to model a system using logical formulas, and then use a decision procedure to verify that some logical formula is an inductive safety invariant for the system. A key ingredient in this approach is coming up with the inductive invariant, which is known as invariant inference. This is a major difficulty, and it is often left for humans or addressed by sound but incomplete abstract interpretation. This paper is motivated by the problem of inductive invariants in shape analysis and in distributed protocols. This paper approaches the general problem of inferring first-order inductive invariants by restricting the language L of candidate invariants. Notice that the problem of invariant inference in a restricted language L differs from the safety problem, since a system may be safe and still not have any inductive invariant in L that proves safety. Clearly, if L is finite (and if testing an inductive invariant is decidable), then inferring invariants in L is decidable. This paper presents some interesting cases when inferring inductive invariants in L is decidable even when L is an infinite language of universal formulas. Decidability is obtained by restricting L and defining a suitable well-quasi-order on the state space. We also present some undecidability results that show that our restrictions are necessary. We further present a framework for systematically constructing infinite languages while keeping the invariant inference problem decidable. We illustrate our approach by showing the decidability of inferring invariants for programs manipulating linked-lists, and for distributed protocols.
IronFleet: proving practical distributed systems correct hawblitzel-2015-ironfleet
External (38)
- Eager Abstraction for Symbolic Model Checking (2018)
- Reducing liveness to safety in first-order logic (2018)
- Modularity for decidability of deductive verification with applications to distributed systems (2018)
- Ivy (tool website) (2018)
- Komodo (2017)
- Paxos made EPR: decidable reasoning about distributed protocols (2017)
- Paxos made EPR: decidable reasoning about distributed protocols (arXiv version) (2017)
- Modular specification and verification of a cache-coherent interface (2016)
- Planning for change in a formal verification of the raft consensus protocol (2016)
- Verdi: a framework for implementing and formally verifying distributed systems (2015)
- Modular reasoning about heap paths via effectively propositional formulas (2014)
- Automatic reasoning for pointer programs using decidable logics (2014)
- In search of an understandable consensus algorithm (2014)
- Secure distributed programming with value-dependent types (2013)
- Effectively-Propositional Reasoning about Reachability in Linked Data Structures (2013)
- AIGER 1.9 and beyond (2011)
- ABC: An Academic Industrial-Strength Verification Tool (2010)
- Dafny: An Automatic Program Verifier for Functional Correctness (2010)
- Satisfiability Modulo Theories (2009)
- Complete Instantiation for Quantified Formulas in Satisfiabiliby Modulo Theories (2009)
- Z3: An Efficient SMT Solver (2008)
- Assume-guarantee testing (2005)
- Interactive Theorem Proving and Program Development - Coq’Art: The Calculus of Inductive Constructions (2004)
- Liveness Checking as Safety Checking (2002)
- Extended static checking for Java (2002)
- A Proof Assistant for Higher-Order Logic Isabelle/HOL (2002)
- Paxos made simple (2001)
- Liveness and Acceleration in Parameterized Verification (2000)
- The part-time parliament (1998)
- Mona: Monadic second-order logic in practice (1995)
- The existence of refinement mappings (1991)
- The power of temporal proofs (1989)
- Translation lookaside buffer consistency: a software approach (1989)
- Verification of concurrent programs: a temporal proof system (1983)
- Techniques for program verification (1980)
- A Computational Logic (1979)
- Simplification by Cooperating Decision Procedures (1979)
- Temporal prophecy for proving temporal properties of infinite-state systems