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

Cite as @mcmillanIvyMultimodalVerification2020 (helia, typst) · \cite{mcmillanIvyMultimodalVerification2020} (LaTeX)
BibTeX
bibtex · 18 lines
@incollection{mcmillanIvyMultimodalVerification2020,
 title = {Ivy: {{A Multi-modal Verification Tool}} for {{Distributed Algorithms}}},
 author = {McMillan, Kenneth L. and Padon, Oded},
 date = {2020},
 isbn = {978-3-030-53290-1 978-3-030-53291-8},
 doi = {10.1007/978-3-030-53291-8_12},
 url = {http://link.springer.com/10.1007/978-3-030-53291-8_12},
 urldate = {2023-02-07},
 booktitle = {Computer {{Aided Verification}}},
 editor = {Lahiri, Shuvendu K. and Wang, Chao},
 volume = {12225},
 pages = {190--202},
 publisher = {Springer International Publishing},
 langid = {english},
 abstract = {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.},
 location = {Cham},
 shorttitle = {Ivy}
}
hayagriva YAML (typst)
yaml · 28 lines
mcmillanIvyMultimodalVerification2020:
  type: anthos
  title:
    value: 'Ivy: {A Multi-modal Verification Tool} for {Distributed Algorithms}'
    short: Ivy
  author:
  - McMillan, Kenneth L.
  - Padon, Oded
  date: 2020
  editor:
  - Lahiri, Shuvendu K.
  - Wang, Chao
  page-range: 190-202
  url:
    value: http://link.springer.com/10.1007/978-3-030-53291-8_12
    date: 2023-02-07
  serial-number:
    doi: 10.1007/978-3-030-53291-8_12
    isbn: 978-3-030-53290-1 978-3-030-53291-8
  language: en-US
  abstract: '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.'
  parent:
    type: anthology
    title: Computer {Aided Verification}
    publisher:
      name: Springer International Publishing
      location: Cham
    volume: 12225
Cited by (2)

Verus: A Practical Foundation for Systems Verification lattuada-2024-verus

DOI

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.
DOI
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.
PDF · DOI · pldb
External (29)
mcmillanIvyMultimodalVerification2020 reference entries/refs/mcmillanIvyMultimodalVerification2020/mcmillanIvyMultimodalVerification2020.hel