Search

It has been pointed out by McMillan that modern satisfiability (SAT) solvers have the ability to perform on-the-fly model abstraction when examining it for the existence of paths satisfying certain conditions. The issue has therefore been raised of whether explicit abstraction refinement schemes still have a role to play in SAT-based model checking. Recent work by Gupta and Strichman has addressed this issue for bounded model checking (BMC), while in this paper we consider unbounded model checking based on interpolation. We show that for passing properties abstraction refinement leads to proofs that often require examination of shorter paths. On the other hand, there is significant overhead involved in computing efficient abstractions. We describe the techniques we have developed to minimize such overhead to the point that even for failing properties the abstraction refinement scheme remains competitive. [ABSTRACT FROM AUTHOR]

Recent work in avoiding the state explosion problem in hardware verification during breath-first symbolic traversal (BFST) based on Binary Decision Diagrams (BDDs) applies hints to constrain the transition relation of the circuit being verified [14]. Hints are expressed as constraints on the primary inputs and states of a circuit modeled as a finite transition system and can often be found with the help of simple heuristics by someone who understands the circuit well enough to devise simulation stimuli or verification properties for it. However, finding good hints requires one to constrain the transition system so that small intermediate BDDs arise during image computations that produce large numbers of reachable states. Thus, the ease of finding good hints is limited by the user's ability to predict their usefulness. In this paper we present a method to statically and automatically determine good hints. Working on the control flow graph(s) of a behavioral model of the circuit being analyzed, our algorithm extracts sets of related execution paths. Each set has a corresponding enabling predicate which is a candidate hint. Program slicing is employed to identify execution paths. Abstract interpretation and model checking are used to ascertain properties along these paths. Hints generated automatically using our technique result in orders-of-magnitude reductions in time and space requirements during state space exploration compared to BFST and are usually as good as those produced by someone who understands the circuit. [ABSTRACT FROM AUTHOR]

Finding all satisfying assignments of a propositional formula has many applications to the synthesis and verification of hardware and software. An approach to this problem that has recently emerged augments a clause-recording propositional satisfiability solver with the ability to add "blocking clauses." One generates a blocking clause from a satisfying assignment by taking its complement. The resulting clause prevents the solver from visiting the same solution again. Every time a blocking clause is added the search is resumed until the instance becomes unsatisfiable. Various optimization techniques are applied to get smaller blocking clauses, since enumerating each satisfying assignment would be very inefficient. In this paper, we present an improved algorithm for finding all satisfying assignments for a generic Boolean circuit. Our work is based on a hybrid SAT solver that can apply conflict analysis and implications to both CNF formulae and general circuits. Thanks to this capability, reduction of the blocking clauses can be efficiently performed without altering the solver's state (e.g., its decision stack). This reduces the overhead incurred in resuming the search. Our algorithm performs conflict analysis on the blocking clause to derive a proper conflict clause for the modified formula. Besides yielding a valid, nontrivial backtracking level, the derived conflict clause is usually more effective at pruning the search space, since it may encompass both satisfiable and unsatisfiable points. Another advantage is that the derived conflict clause provides more flexibility in guiding the score-based heuristics that select the decision variables. The efficiency of our new algorithm is demonstrated by our preliminary results on SAT-based unbounded model checking of VIS benchmark models. [ABSTRACT FROM AUTHOR]

Most symbolic model checkers are based on either Binary Decision Diagrams (BDDs), which may grow exponentially large, or Satisfiability (SAT) solvers, whose time requirements rapidly increase with the sequential depth of the circuit. We investigate the integration of BDD-based methods with SAT to speed up the verification of safety properties of the form Gf, where f is either propositional or contains only the next-time temporal operator X. We use BDD-based reachability analysis to find lower bounds on the reachable states and the states that reach the bad states. Then, we use these lower bounds to shorten the counterexample or reduce the depth of the induction step (termination depth). We present experimental results that compare our method to a pure BDD-based method and a pure SAT-based method. Our method can prove properties that are hard for both the BDD-based and the SAT-based methods. [ABSTRACT FROM AUTHOR]

We present an algorithm to generate small Büchi automata for LTL formulae. We describe a heuristic approach consisting of three phases: rewriting of the formula, an optimized translation procedure, and simplification of the resulting automaton. We present a translation procedure that is optimal within a certain class of translation procedures. The simplification algorithm can be used for Büchi automata in general. It reduces the number of states and transitions, as well as the number and size of the accepting sets—possibly reducing the strength of the resulting automaton. This leads to more efficient model checking of linear-time logic formulae. We compare our method to previous work, and show that it is significantly more efficient for both random formulae, and formulae in common use and from the literature. [ABSTRACT FROM AUTHOR]

Detection of fair cycles is an important task of many model checking algorithms.When the transition system is represented symbolically, the standard approach to fair cycle detection is the one of Emerson and Lei. In the last decade variants of this algorithm and an alternative method based on strongly connected component decomposition have been proposed.We present a taxonomy of these techniques and compare representatives of each major class on a collection of real-life examples. Our results indicate that the Emerson-Lei procedure is the fastest, but other algorithms tend to generate shorter counter-examples. [ABSTRACT FROM AUTHOR]

Conjunction scheduling in image computation consists of clustering the parts of a transition relation and ordering the clusters, so that the size of the BDDs for the intermediate results of image computation stay small. We present an approach based on the analysis and permutation of the dependence matrix of the transition relation. Our algorithm computes a bordered-block lower triangular form of the matrix that heuristically minimizes the active lifetime of variables, that is, the number of conjunctions in which the variables participate. The ordering procedure guides a clustering algorithm based on the affinity of the transition relation parts. The ordering procedure is then applied again to define the cluster conjunction schedule.Our experimental results show the effectiveness of the new algorithm. [ABSTRACT FROM AUTHOR]

We present a symbolic algorithm for strongly connected component decomposition. The algorithm performs Θ(n log n) image and preimage computations in the worst case, where n is the number of nodes in the graph. This is an improvement over the previously known quadratic bound. The algorithm can be used to decide emptiness of Büchi automata with the same complexity bound, improving Emerson and Lei' quadratic bound, and emptiness of Streett automata, with a similar bound in terms of nodes. It also leads to an improved procedure for the generation of nonemptiness witnesses. [ABSTRACT FROM AUTHOR]

Technology mapping transforms an abstract representation of a multilevel logic circuit into an interconnection of gates from a library. We have examined the approach to technology mapping that uses tree covering. The Boolean network is first decomposed in simple gates—typically NANDs and inverters: The result is called the subject graph. Matching then identifies all possible ways in which a gate of the subject graph can be implemented by a gate in the library. The best combination of matches is then chosen by a dynamic programming approach. Dynamic programming solves exactly only the covering part of the problem. Therefore, the results are of good quality, but no global optimality is guaranteed. [ABSTRACT FROM AUTHOR]

In this chapter, we have completed the brief, introductory treatment that was given in Section 1.4.4. Three main topics were covered. First, we gave, in Section 12.2, a summary of the various faults models in widespread usage at the time of writing. Second, our main focus was the treatment of automatic test pattern generation, in Section 12.3. After treating issues of excitation and sensitization (especially the method of unique sensitization). This led us naturally to the subject of logical implications. (Section 12.3.3). Third, we discussed at some length how the basic tools of the ATPG trade could be used to perform redundancy removal (Section 12.4) on a given multilevel logic circuit. This operation leaves the Boolean network in a locally optimum "prime and irredundant" state. [ABSTRACT FROM AUTHOR]

We began in this chapter by identifying some common characteristics of local Search algorithms (algorithms that start from an initial solution and try to find a better one by applying successive modifications). Then we studied the set of methods that combine to make the local search algorithm known as the ESPRESSO algorithm for logic minimization. Two methods were discussed for quickly checking whether a given implicant is prime: one based on tautology/equivalence checking, and one based on intersection with the OFF-set of the function to be minimized. Fast methods for tautology checking were discussed, based on unateness or partial unateness of the cover being checked. And similarly fast methods for computing the OFF-set were discussed. We then gave a method for computing the essential primes, and closed by showing how the whole paradigm of heuristic minimization could be extended to multiple-valued logics. [ABSTRACT FROM AUTHOR]

If you gave this chapter a careful reading, and went through a selection of the solved problems of Section 3.8, you should be comfortable with: 1.Sets and Venn diagrams, binary relations and functions, partitions and equivalence classes.2.Reflexivity, symmetry, antisymmetry, and transitivity of binary relations.3.Three important kinds of reflexive binary relations: equivalence classes, partial orders, and compatibility relations.4.The hierarchical relationship between partial orders, lattices, and Boolean algebras. Equivalence relations are one of the cornerstones in the theoretical foundation of FSM synthesis and formal verification. They will be a principal focus of the treatment of state minimization of completely specified FSMs in Chapter 7.1. Compatibility relations play a similar role in the discussion of state minimization for incompletely specified machines, the subject of Section 8.1 of Chapter 8. Since Boolean algebras are based on lattices and partial orders, the theory of partial orders permeates the entire book. We have treated "large" Boolean algebras and subalgebras, and have shown how logic synthesis "lives" in the world of the "large" Boolean algebra, Fn(0,1), of n- variable switching functions. We have related intervals and subalgebras of Fn(0,1) to don't cares and sets of permissible functions, which play prominent in logic synthesis algorithms. [ABSTRACT FROM AUTHOR]

In this chapter we have briefly surveyed the panoply of design methodologies which the semiconductor industry has employed in producing the powerful chips that are becoming commonplace today. We have characterized the IC design process as one of optimal tradeoff of competing design goals: 1.The area on the chip required by the circuit being designed;2.The critical path delay of the circuit;3.The testability of the circuit, measured in stuck-at fault coverage;4.The power dissipated by the circuit. Along the way we have developed basic notions of critical path delay analysis, test generation, graph models, CMOS implementation of logic functions, and complexity of algorithms. All of these notions will be recurring themes in the sequel, as we develop theoretical and intuitional background for effective use of the dominant extant VLSI CAD tools for synthesis and verification. For those inclined to take the next step and be a VLSI CAD tool developer, this book offers many sections on advanced topics, and extensive pointers into the relevant literature. The serious student will find that mastery of the techniques covered in the "Problem" section of each chapter will put him/her into the position of being immediately, effectively, and competitively productive in a VLSI CAD or design group. [ABSTRACT FROM AUTHOR]