Program verification using templates over predicate abstraction
Authors:
Open Access
- 28 May 2009
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 44 (6) , 223-234
Abstract
We address the problem of automatically generating invariants with quantified and boolean structure for proving the validity of given assertions or generating pre-conditions under which the assertions are valid. We present three novel algorithms, having different strengths, that combine template and predicate abstraction based formalisms to discover required sophisticated program invariants using SMT solvers. Two of these algorithms use an iterative approach to compute fixed-points (one computes a least fixed-point and the other computes a greatest fixed-point), while the third algorithm uses a constraint based approach to encode the fixed-point. The key idea in all these algorithms is to reduce the problem of invariant discovery to that of finding optimal solutions for unknowns (over conjunctions of some predicates from a given set) in a template formula such that the formula is valid. Preliminary experiments using our implementation of these algorithms show encouraging results over a benchmark of small but complicated programs. Our algorithms can verify program properties that, to our knowledge, have not been automatically verified before. In particular, our algorithms can generate full correctness proofs for sorting algorithms (which requires nested universally-existentially quantified invariants) and can also generate preconditions required to establish worst-case upper bounds of sorting algorithms. Furthermore, for the case of previously considered properties, in particular sortedness in sorting algorithms, our algorithms take less time than reported by previous techniques.Keywords
This publication has 25 references indexed in Scilit:
- VS3: SMT Solvers for Program Verification2009
- Finding Loop Invariants for Programs over Arrays Using a Theorem Prover2009
- Program analysis as constraint solving2008
- Constraint-Based Invariant Inference over Predicate AbstractionLecture Notes in Computer Science, 2008
- Predicate abstraction with indexed predicatesACM Transactions on Computational Logic, 2007
- Efficient E-Matching for SMT Solvers2007
- Boolean Heaps2005
- Symbolic Implementation of the Best Transformer2004
- Constraint-Based Linear-Relations Analysis2004
- A unified approach to global program optimization1973