9827143
Making Predicate Abstraction Efficient: How to Eliminate Redundant Predicates
In this paper we consider techniques to identify and remove redundant predicates during predicate abstraction. We give three criteria for identifying redundancy. A predicate is redundant if any of the following three holds (i) the predicate is equivalent to a propositional function of other predicates. (ii) removing the predicate preserves safety properties satisfied by the abstract model (iii) removing it preserves bisimulation equivalence. We also show how to efficiently remove the redundant predicates once they are identified. Experimental results are included to demonstrate the effectiveness of our methods.
571032
Nonlinear quantification scheduling in image computation
Computing the set of states reachable in one step from a given set of states, i.e. image computation, is a crucial step in several symbolic verification algorithms, including model checking and reachability analysis. So far, the best methods for quantification scheduling in image computation, with a conjunctively partitioned transition relation, have been restricted to a linear schedule. This results in a loss of flexibility during image computation. We view image computation as a problem of constructing an optimal parse tree for the image set. The optimality of a parse tree is defined by the largest BDD that is encountered during the computation of the tree. We present dynamic and static versions of a new algorithm, VarScore, which exploits the flexibility offered by the parse tree approach to the image computation. We show by extensive experimentation that our techniques outperform the best known techniques so far.
1669235
Formal property verification by abstraction refinement with formal, simulation and hybrid engines
We present RFN, a formal property verification tool based on abstraction refinement. Abstraction refinement is a strategy for property verification. It iteratively refines an abstract model to better approximate the behavior of the original design in the hope that the abstract model alone will provide enough evidence to prove or disprove the property. However, previous work on abstraction refinement was only demonstrated on designs with up to 500 registers. We developed RFN to verify real-world designs that may contain thousands of registers. RFN differs from the previous work in several ways. First, instead of relying on a single engine, RFN employs multiple formal verification engines, including a BDD-ATPG hybrid engine and a conventional BDD-based fixpoint engine, for finding error traces or proving properties on the abstract model. Second, RFN uses a novel two-phase process involving 3-valued simulation and sequential ATPG to determine how to refine the abstract model. Third, RFN avoids the weakness of other abstraction-refinement algorithms-finding error traces on the original design, by utilizing the error trace of the abstract model to guide sequential ATPG to find an error trace on the original design. We implemented and applied a prototype of RFN to verify various properties of real-world RTL designs containing approximately 5,000 registers, which represents an order of magnitude improvement over previous results. On these designs, we successfully proved a few properties and discovered a design violation.
2942056
Automated Abstraction Refinement for Model Checking Large State Spaces Using SAT Based Conflict Analysis
We introduce a SAT based automatic abstraction refinement framework for model checking systems with several thousand state variables in the cone of influence of the specification. The abstract model is constructed by designating a large number of state variables as invisible. In contrast to previous work where invisible variables were treated as free inputs we describe a computationally more advantageous approach in which the abstract transition relation is approximated by pre-quantifying invisible variables during image computation. The abstract counterexamples obtained from model-checking the abstract model are symbolically simulated on the concrete system using a state-of-the-art SAT checker. If no concrete counterexample is found, a subset of the invisible variables is reintroduced into the system and the process is repeated. The main contribution of this paper are two new algorithms for identifying the relevant variables to be reintroduced. These algorithms monitor the SAT checking phase in order to analyze the impact of individual variables. Our method is complete for safety properties (AGp) in the sense that - performance permitting - a property is either verified or disproved by a concrete counterexample. Experimental results are given to demonstrate the power of our method on real-world designs.
8554279
High level verification of control intensive systems using predicate abstraction
Predicate abstraction has been widely used for model checking hardware/software systems. However, for control intensive systems, existing predicate abstraction techniques can potentially result in a blowup of the size of the abstract model. We deal with this problem by retaining important control variables in the abstract model. By this method we avoid having to introduce an unreasonable number of predicates to simulate the behavior of the control variables. We also show how to improve predicate abstraction by extracting useful information from a high level representation of hardware/software systems. This technique works by first extracting relevant branch conditions. These branch conditions are used to invalidate spurious abstract counterexamples through a new counterexample-based lazy refinement algorithm. Experimental results are included to demonstrate the effectiveness of our methods.
8658919
Using Combinatorial Optimization Methods for Quantification Scheduling
Model checking is the process of verifying whether a model of a concurrent system satisfies a specified temporal property. Symbolic algorithms based on Binary Decision Diagrams (BDDs) have significantly increased the size of the models that can be verified. The main problem in symbolic model checking is the image computation problem, i.e., efficiently computing the successors or predecessors of a set of states. This paper is an in-depth study of the image computation problem. We analyze and evaluate several newheuristics, metrics, and algorithms for this problem. The algorithms use combinatorial optimization techniques such as hill climbing, simulated annealing, and ordering by recursive partitioning to obtain better results than was previously the case. Theoretical analysis and systematic experimentation are used to evaluate the algorithms.
5752689
Stability analysis of biological systems with real solution classification
This paper presents a new and general approach for analyzing the stability of a large class of biological networks, modeled as autonomous systems of differential equations, using real solving and solution classification. The proposed approach, based on the classical technique of linearization from the qualitative theory of ordinary differential equations yet with exact symbolic computation, is applied to analyzing the local stability of the Cdc2-cyclin B/Wee1 system and the Mos/MEK/p42 MAPK cascade, two well-known models for cell and protein signaling that have been studied extensively in the literature. We provide rigorous proofs and generalizations for some of the previous results established experimentally and report our new findings.
37363170
Decomposing Algebraic Varieties
An algebraic variety is a geometric figure defined by the zeros of a set of multivariate polynomials. This paper explains how to adapt two general zero decomposition methods for efficient decomposition of affine algebraic varieties into unmixed and irreducible components. Two devices based on Grobner bases are presented for computing the generators of the saturated ideals of triangular sets. We also discuss a few techniques and variants which, when properly used, may speed up the decomposition. Experiments for a set of examples are reported with comparison to show the performance and effectiveness of such techniques, variants and the whole decomposition methods. Several theoretical results are stated along with the description of algorithms. The paper ends with a brief mention of some applications of variety decomposition.
980946
Image and Texture Segmentation Using Local Spectral Histograms
We present a method for segmenting images consisting of texture and nontexture regions based on local spectral histograms. Defined as a vector consisting of marginal distributions of chosen filter responses, local spectral histograms provide a feature statistic for both types of regions. Using local spectral histograms of homogeneous regions, we decompose the segmentation process into three stages. The first is the initial classification stage, where probability models for homogeneous texture and nontexture regions are derived and an initial segmentation result is obtained by classifying local windows. In the second stage, we give an algorithm that iteratively updates the segmentation using the derived probability models. The third is the boundary localization stage, where region boundaries are localized by building refined probability models that are sensitive to spatial patterns in segmented regions. We present segmentation results on texture as well as nontexture images. Our comparison with other methods shows that the proposed method produces more accurate segmentation results
16321846
Semantics modeling based image retrieval system using neural networks
Semantics based image retrieval techniques show a promising direction to the development of CBIR systems. To design such systems, semantics modeling is one of the most difficult tasks. This paper aims to develop a semantics modeling approach using neural networks. In our work, a neural network is utilized to memorize the semantic patterns within the images. An intelligent image retrieval system is designed based on this model. User's relevance feedback is used for enhancing the retrieval performance. Experimental results from the prototype system demonstrate the effectiveness of the proposed approach.
2125782
On the bounded domination number of tournaments
Abstract In a simple digraph, a star of degree t is a union of t edges with a common tail. The k -domination number γ k (G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ k (T)=⌈n/(k+1)⌉ when T is a tournament with n⩾14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n -vertex tournament is dominated by at most lg n− lg lg n+2 vertices.