SymInfer: Inferring Program Invariants using Symbolic States
Preprint
Abstract
We introduce a new technique for inferring program invariants that uses symbolic states generated by symbolic execution. Symbolic states, which consist of path conditions and constraints on local variables, are a compact description of sets of concrete program states and they can be used for both invariant inference and invariant verification. Our technique uses a counterexample-based algorithm that creates concrete states from symbolic states, infers candidate invariants from concrete states, and then verifies or refutes candidate invariants using symbolic states. The refutation case produces concrete counterexamples that prevent spurious results and allow the technique to obtain more precise invariants. This process stops when the algorithm reaches a stable set of invariants. We present SymInfer, a tool that implements these ideas to automatically generate invariants at arbitrary locations in a Java program. The tool obtains symbolic states from Symbolic PathFinder and uses existing algorithms to infer complex (potentially nonlinear) numerical invariants. Our preliminary results show that SymInfer is effective in using symbolic states to generate precise and useful invariants for proving program safety and analyzing program runtime complexity. We also show that SymInfer outperforms existing invariant generation systems.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Directed Symbolic Execution2011
- Automated fixing of programs with contracts2010
- Control-flow refinement and progress invariants for bound analysisACM SIGPLAN Notices, 2009
- SPEED: Symbolic Complexity Bound Analysis2009
- InvGen: An Efficient Invariant GeneratorLecture Notes in Computer Science, 2009
- Z3: An Efficient SMT Solver2008
- The Daikon system for dynamic detection of likely invariantsScience of Computer Programming, 2007
- JPF–SE: A Symbolic Execution Extension to Java PathFinder2007
- Generating all polynomial invariants in simple loopsJournal of Symbolic Computation, 2007
- Automatically validating temporal safety properties of interfaces2001