6555974
Lazy constraints and SAT heuristics for proof-based abstraction
SAT proof analysis techniques have been used recently with BMC in order to generate proof-based abstractions that preserve the correctness of the property up to a certain depth. In this paper, we propose various techniques for handling BMC constraints that are targeted at reducing the size of the abstract model while preserving bounded correctness. We propose lazy constraints, where the idea is to delay propagation of certain implied values without modifying a standard SAT solver. We propose different methods for automatic use of lazy constraints in SAT-based BMC. Their use can be regarded as a heuristic, which typically leads to significant reduction in the size of the abstract model, frequently accompanied by an overall performance improvement. We also use SAT proof analysis to loosen the user-specified environmental constraints, in order to generate smaller abstract models for conservative verification. We briefly describe other SAT-based heuristics for reducing the size of the abstract model. We have implemented our techniques in a prototype verification platform, and demonstrate their effectiveness on several large industry designs.
12763151
Efficient Modeling of Embedded Memories in Bounded Model Checking
We describe a viable approach for memory abstraction that preserves memory semantics, thereby augmenting the capability of SAT-based BMC to handle designs with large embedded memory without explicitly modeling each memory bit. Our method does not require examining the design or changing the SAT-solver and is guaranteed not to generate false negatives. The proposed method is similar, but with key enhancements, to the previous interpretation of memory that captures its forwarding semantics, i.e., a data read from a memory location is same as the most recent data written at the same location. In our method, we construct an abstract model for BMC by eliminating memory arrays, but retaining the memory interface signals and adding constraints on those signals at every analysis depth to preserve the memory semantics. The size of these memory-modeling constraints depends quadratically on the number of memory accesses and linearly on the bus widths of memory interface signals. Since the analysis depth of BMC bounds the number of memory accesses, these constraints are significantly smaller than the explicit memory model. The novelty of our memory-modeling constraints is that they capture the exclusivity of a read and write pair explicitly, i.e., when a SAT-solver decides on a valid read and write pair, other pairs are implied invalid immediately, thereby reducing the solve time. We have implemented these techniques in our SAT-based BMC framework where we demonstrate the effectiveness of such an abstraction on a number of hardware and software designs with large embedded memories. We show at least an order of magnitude improvement (both in time and space) using our method over explicit modeling of each memory bit. We also show that our method of adding constraints boosts the performance of the SAT solver (in BMC) significantly as opposed to the conventional way of modeling these constraints as nested if-then-else expressions.
46604085
Assertion-based verification turns the corner
The "formal verification method: Getting around the Brick Wall" panel at the 2002Design Automation Conference highlighted the industrial emergence of assertion-based verification and the need to go beyond current methods. Moderator David Dill initiated a discussion on the three brick walls to formal verifcation methods: handling high computational complexity, formulating properties to check, and characterizing the set of legal inputs to the design underverification. The panelists addressed moving to higher abstraction levels and assertion-based.verification as two strategies to solve these problems.
11038357
Reasoning About Threads Communicating via Locks
We propose a new technique for the static analysis of concurrent programs comprised of multiple threads. In general, the problem is known to be undecidable even for programs with only two threads but where the threads communicate using CCS-style pairwise rendezvous [11]. However, in practice, a large fraction of concurrent programs can either be directly modeled as threads communicating solely using locks or can be reduced to such systems either by applying standard abstract interpretation techniques or by exploiting separation of control from data. For such a framework, we show that for the commonly occurring case of threads with nested access to locks, the problem is efficiently decidable. Our technique involves reducing the analysis of a concurrent program with multiple threads to individually analyzing augmented versions of the given threads. This not only yields decidability but also avoids construction of the state space of the concurrent program at hand and thus bypasses the state explosion problem making our technique scalable. We go on to show that for programs with threads that have non-nested access to locks, the static analysis problem for programs with even two threads becomes undecidable even for reachability, thus sharpening the result of [11]. As a case study, we consider the Daisy file system [1] which is a benchmark for analyzing the efficacy of different methodologies for debugging concurrent programs and provide results for the detection of several bugs.
6311626
Combining strengths of circuit-based and CNF-based algorithms for a high-performance SAT solver
We propose Satisfiability Checking (SAT) techniques that lead to a consistent performance improvement of up to 3x over state-of-the-art SAT solvers like Chaff on important problem domains in VLSI CAD. We observe that in circuit oriented applications like ATPG and verification, different software engineering techniques are required for the portions of the formula corresponding to learnt clauses compared to the original formula. We demonstrate that by employing the same innovations as in advanced CNF-based SAT solvers, but in a hybrid approach where these two portions of the formula are represented differently and processed separately, it is possible to obtain the consistently highest performing SAT solver for circuit oriented problem domains. We also present controlled experiments to highlight where these gains come from. Once it is established that the hybrid approach is faster, it becomes possible to apply low overhead circuit-based heuristics that would be unavailable in the CNF domain for greater speedup.
11387042
Predicate learning and selective theory deduction for a difference logic solver
Design and verification of systems at the register-transfer (RT) or behavioral level require the ability to reason at higher levels of abstraction. Difference logic consists of an arbitrary Boolean combination of propositional variables and difference predicates and therefore provides an appropriate abstraction. In this paper, we present several new optimization techniques for efficiently deciding difference logic formulas. We use the lazy approach by combining a DPLL Boolean SAT procedure with a dedicated graph-based theory solver, which adds transitivity constraints among difference predicates on a "need-to" basis. Our new optimization techniques include flexible theory constraint propagation, selective theory deduction, and dynamic predicate learning. We have implemented these techniques in our lazy solver. We demonstrate the effectiveness of the proposed techniques on public benchmarks through a set of controlled experiments
6212306
Constraint checking with partial information
Constraints are a valuable tool for managing information across multiple databases, as well as for general purposes of assuring data integrity. However, efficient implementation of constraint checking is difficult. In this paper we explore techniques for assuring constraint satisfaction without performing a complete evaluation of the constraints. We consider methods that use only constraint definitions, methods that use constraints and updates, and methods that use constraints, updates, and “local” data.
8765967
A Dual-Pathway Neural Network Model of Control Relinquishment in Motor Skill Learning
Cognitive psychologists have long recognized that the acquisition of a motor skill involves a transition from attention-demanding controlled processing to more fluent automatic processing. Neuroscientific studies suggest that controlled and automatic processing rely on two largely distinct neural pathways. The controlled pathway, which includes the prefrontal cortex, is seen as acquiring declarative representations of skills. In comparison, the automatic pathway is thought to develop procedural representations. Automaticity in motor skill learning involves a reduction in dependence on frontal systems and an increased reliance on the automatic pathway. In this paper, we propose a biologically plausible computational model of motor skill automaticity. This model offers a dual-pathway neurocomputational account of the translation of declarative knowledge into procedural knowledge during motor learning. In support of the model, we review some previously reported human experimental results involving the learning of a sequential key pressing task, and we demonstrate, through simulation, howthe model provides a parsimonious explanation for these results.
18838099
Infrastructure Leasing Problems
Consider the following Steiner Tree leasing problem. Given a graph G= (V,E) with root r, and a sequence of terminal sets D t i¾? Vfor each day ti¾? [T]. A feasible solution to the problem is a set of edges E t for each tconnecting D t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we leaseedges for say, { a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.
11054622
Classification using Efficient LU Decomposition in Sensornets
We consider the popular application of detection, classification and tracking and their feasibility in resource constrained sensornets. We concentrate on the classification aspect, by decomposing the complex, computationally intensive signal processing Maximum-APosterior (MAP) classifier into simpler computationally and communicationally load balanced procedures, using a clustering approach. LU decomposition is an efficient approach for computing the inverse of covariance matrices required in the MAP classifier. We thus explore feasibility of LU decomposition in sensornets. We present power-aware and load balanced techniques for LU decomposition of the covariance matrices in sensornets alongwith their analytical and power consumption analyses.
2840997
A survey of recent advances in SAT-based formal verification
Dramatic improvements in SAT solver technology over the last decade and the growing need for more efficient and scalable verification solutions have fueled research in verification methods based on SAT solvers. This paper presents a survey of the latest developments in SAT-based formal verification, including incomplete methods such as bounded model checking and complete methods for model checking. We focus on how the surveyed techniques formulate the verification problem as a SAT problem and how they exploit crucial aspects of a SAT solver, such as application-specific heuristics and conflict-driven learning. Finally, we summarize the noteworthy achievements in this area so far and note the major challenges in making this technology more pervasive in industrial design verification flows.