1,721,120 research outputs found
Comparing Different Variants of the IC3 Algorithm for Hardware Model Checking
No full textIC3 is one of the most successful algorithms for hardware model checking. Since its invention in 2010, several variants of the original algorithm have been published, proposing optimizations and/or alternative procedures for the many different steps of the algorithm. In this paper, we present a thorough empirical comparison of a large set of optimizations and procedures for the steps of IC3, considering "high-level" variants/extensions to the basic algorithm, as well as "low-level" optimizations/configuration settings. We implemented each of them in the same tool, optimizing the implementations to the best of our knowledge. This enabled for a flexible experimentation in a controlled environment, and to gain new insights about their most important differences and commonalities, as well as about their performance characteristics. We conducted the experiments using as benchmarks the problems used in the last four editions of the hardware model checking competition. The analysis helped us to identify several settings leading to significant improvements wrt. a basic implementation of IC3
Verification of SMT Systems with Quantifiers
No full textWe consider the problem of invariant checking for transition systems using SMT and quantified variables ranging over finite but unbounded domains. We propose a general approach, obtained by combining two ingredients: exploration of a finite instance, to obtain candidate inductive invariants, and instantiation-based techniques to discharge quantified queries. A thorough experimental evaluation on a wide range of benchmarks demonstrates the generality and effectiveness of our approach. Our algorithm is the first capable of approaching in a uniform way such a large variety of models
A Simple and Flexible Way of Computing Small Unsatisfiable Cores in SAT Modulo Theories
No full textFinding small unsatisfiable cores for SAT problems has recently received a lot of interest, mostly for its applications in formal verification. However, propositional logic is often not expressive enough for representing many interesting verification problems, which can be more naturally addressed in the framework of Satisfiability Modulo Theories, SMT. Surprisingly, the problem of finding unsatisfiable cores in SMT has received very little attention in the literature; in particular, we are not aware of any work aiming at producing small unsatisfiable cores in SMT. In this paper we present a novel approach to this problem. The main idea is to combine an SMT solver with an external propositional core extractor: the SMT solver produces the theory lemmas found during the search; the core extractor is then called on the boolean abstraction of the original SMT problem and of the theory lemmas. This results in an unsatisfiable core for the original SMT problem, once the remaining theory lemmas have been removed. The approach is conceptually interesting, since the SMT solver is used to dynamically lift the suitable amount of theory information to the boolean level, and it also has several advantages in practice. In fact, it is extremely simple to implement and to update, and it can be interfaced with every propositional core extractor in a plug-and-play manner, so that to benefit for free of all unsat-core reduction techniques which have been or will be made available. We have evaluated our approach by an extensive empirical test on SMT-LIB benchmarks, which confirms the validity and potential of this approach
LTL falsification in infinite-state systems
No full textIn finite-state systems, if an LTL property is false, there is always a counterexample path (i.e. a witness) for it which is ultimately periodic (i.e. in a lasso-shaped form). When dealing with infinite-state systems, this is no longer the case. In this work, we address this issue by proposing an automatic approach that presents witnesses in an indirect way. The approach is based on two key insights. First, we leverage the notion of well-founded funnel, where a ranking function ensures that the states in the source set are guaranteed to inevitably reach the destination set. We show that, under suitable conditions, a sequence of funnels ensures the existence of a fair path. Second, we adopt a compositional approach to partition the original system into projections and to prove that they result in a non-empty under-approximation of the original system that only contains fair paths. Then, we propose an algorithm that, working in an abstract space induced by a set of predicates, identifies candidate funnels, proves their well-foundedness, and searches for a sequencing order. We experimentally evaluate the approach on examples taken from software, timed and hybrid systems, showing its wide applicability and expressiveness, with an implementation that outperforms various competitor tools
Towards the verification of a generic interlocking logic: Dafny meets parameterized model checking
No full textInterlocking logics are at the core of critical systems controlling the traffic within stations. In this paper, we consider a generic interlocking logic, which can be instantiated to control a wide class of stations. We tackle the problem of parameterized verification, i.e. prove that the logic satisfies the required properties for all the relevant stations. We present a simplified case study, where the interlocking logic is directly encoded in Dafny. Then, we show how to automate the proof of an important safety requirement, by integrating simple, template-based invariants and more complex invariants obtained from a model checker for parameterized systems. Based on these positive preliminary results, we outline how we intend to integrate the approach by extending the IDE for the design of the interlocking logic
- …
