Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis

Computer Science – Logic in Computer Science

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Accepted for publication in Logical Methods in Computer Science

Scientific paper

10.2168/LMCS-6(4:10)2010

The safety of infinite state systems can be checked by a backward reachability procedure. For certain classes of systems, it is possible to prove the termination of the procedure and hence conclude the decidability of the safety problem. Although backward reachability is property-directed, it can unnecessarily explore (large) portions of the state space of a system which are not required to verify the safety property under consideration. To avoid this, invariants can be used to dramatically prune the search space. Indeed, the problem is to guess such appropriate invariants. In this paper, we present a fully declarative and symbolic approach to the mechanization of backward reachability of infinite state systems manipulating arrays by Satisfiability Modulo Theories solving. Theories are used to specify the topology and the data manipulated by the system. We identify sufficient conditions on the theories to ensure the termination of backward reachability and we show the completeness of a method for invariant synthesis (obtained as the dual of backward reachability), again, under suitable hypotheses on the theories. We also present a pragmatic approach to interleave invariant synthesis and backward reachability so that a fix-point for the set of backward reachable states is more easily obtained. Finally, we discuss heuristics that allow us to derive an implementation of the techniques in the model checker MCMT, showing remarkable speed-ups on a significant set of safety problems extracted from a variety of sources.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Backward Reachability of Array-based Systems by SMT solving: Termination and Invariant Synthesis will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-87837

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.