Latticed k-Induction with an Application to Probabilistic Programs
Open Access
- 15 July 2021
- book chapter
- Published by Springer Nature
- p. 524-549
Abstract
We revisit two well-established verification techniques,k-inductionandbounded model checking(BMC), in the more general setting of fixed point theory over complete lattices. Our main theoretical contribution islatticed k-induction, which (i) generalizes classicalk-induction for verifying transition systems, (ii) generalizes Park induction for bounding fixed points of monotonic maps on complete lattices, and (iii) extends from naturalskto transfinite ordinals $$\kappa $$ , thus yielding $$\kappa $$ -induction.The lattice-theoretic understanding ofk-induction and BMC enables us to apply both techniques to thefully automatic verification of infinite-state probabilistic programs. Our prototypical implementation manages to automatically verify non-trivial specifications for probabilistic programs taken from the literature that—using existing techniques—cannot be verified without synthesizing a stronger inductive invariant first.
Keywords
All Related Versions
This publication has 60 references indexed in Scilit:
- Automatic analysis of DMA races using model checking and k-inductionFormal Methods in System Design, 2011
- A counterexample-guided abstraction-refinement framework for markov decision processesACM Transactions on Computational Logic, 2010
- Bounded model checking of infinite state systemsFormal Methods in System Design, 2006
- Probabilistic guarded commands mechanized in HOLTheoretical Computer Science, 2005
- An interpolating theorem proverTheoretical Computer Science, 2005
- Abstraction and refinement in probabilistic systemsACM SIGMETRICS Performance Evaluation Review, 2005
- A probabilistic PDLJournal of Computer and System Sciences, 1985
- Fixed point theorems and semantics: a folk taleInformation Processing Letters, 1982
- Constructive versions of Tarski’s fixed point theoremsPacific Journal of Mathematics, 1979
- A lattice-theoretical fixpoint theorem and its applicationsPacific Journal of Mathematics, 1955