Search

Automated formal verification techniques, based on model checking and theorem proving, usually have scalability issues for contemporary digital circuits. On the other hand, interactive theorem provers can overcome this issue, by verifying circuits using universally quantified variables, at the cost of significant skilled guidance. Leveraging upon the complimentary nature of the techniques, this paper presents a hybrid model checking - theorem proving approach for the formal functional verification of digital circuits (HVoC). The main idea is to first use a higher-order-logic theorem prover to replace the structural (RTL or gate level) implementations of the combinational modules with their, formally verified, corresponding behavior and then verify the complete behavioral implementation using a model checker. This kind of a 2-step process not only reduces the computational complexity, but, is also quite effective in terms of counterexample generation time. Our experiments on some benchmarks show an average $$50\%$$ reduction in analysis time.

At present, functional verification represents the most expensive part of the digital systems design. Moreover, different problems such as: clock synchronization, code compatibility, simulation automation, new design methodologies, proper use of coverage metrics, among others represent challenges in this area. The automated test vector generation is involved in these problems. In this work, an automated functional test sequences generation for digital systems based on the use of coverage models and a binary Particle Swarm Optimization algorithm with a reinitialization mechanism (BPSOr) is described. Also, a comparison with other meta-heuristic algorithms such as: Genetic algorithms (GA) and pseudo-random generation is presented using different fitness functions, coverage models and devices under verification. The main strategy is based on the combination of the simulation and meta-heuristic algorithms to test the device behavior through the generation of test vector sequences. According to the results, the proposed test generation method represents a good alternative to increase the functional coverage during the automated functional verification of block-level digital systems verification.

At present, the functional verification of a device represents the highest cost during manufacturing. To reduce that cost, several methods have been suggested. In this work we propose a method which produces a set of binary test sequences by means of a Compact binary Differential Evolution algorithm (Compact-BinDE). The strategy employed is based on the use of coverage models and cost functions in the verification process, which are built with relevant conditions or coverage points representing the full device behavior. The main problem is to cover all difficult situations since the relationships between the test points and the input data in the design are not trivial. The test generation method is included with a proposed verification platform based on a simulation representing a hybrid method. The main contribution of this work is that the method obtains test vector sequences that maximize the coverage percentage on run-time device simulation with an efficient search in the binary domain. Also, different to the previous works that used meta-heuristics, the proposed method by means of the Compact-BinDE algorithm can reduce the simulation time used to obtain test sequences that exercise the coverage points. The results show that the proposed method represents a good alternative to generate test sequences to cover the coverage points during the functional verification.

Digital application complexity has steadily made it harder to discover and debug behavioral inconsistencies at register transfer level (RTL). Aiming to bring a solution, several techniques have appeared as alternatives to verify that a circuit description meets the requirements of its corresponding functional specification. Simulation-based verification is still far from reaching high state coverage because of cycle-accurate slowness. Formal approaches are exhaustive in theory, but due to computational limitations, workarounds must always be adopted to check only a portion of the design at a time. Bounded model checking is one of the most popular formal methods; however, a strong disadvantage resides in defining and determining the quality of the set of properties to verify. Sequential equivalence checking is also an effective alternative, but it can only be applied between circuit descriptions where a one-to-one correspondence for states and memory elements is expected. This paper presents a formal methodology to verify RTL descriptions through direct comparison with: 1) a high-level reference model and 2) a protocol reference model. Thus, it is possible to verify behavioral and interface protocol separately. Complete sequences of states are extracted from the reference models and the RTL design, and compared to determine if the design implementation is correct. The natural discrepancies between the models and RTL code are considered, including non-matching interface and memory elements, state mapping, and process concurrency. The validity of the methodology is formally justified and a related tool was developed to show, through examples, that the approach may be applied on real designs.

The verification of embedded software has become an important subject over the last years. However, neither standalone verification approaches, like simulation-based/formal verification, nor state-of-the-art semiformal verification approaches are able to verify large and complex embedded software with or without hardware dependencies. This work presents a scalable hybrid verification approach for the verification of embedded software using a semiformal algorithm optimized with static parameter assignment (SPA). These algorithms and methodologies like SPA and counterexample guided simulation are used to combine simulation-based and formal verification in a new way. SPA offers a method to interact between dynamic and static verification approaches based on an automated ranking determination of possible function parameters according to the impact on the model size. Furthermore, SPA inserts initialization code for specific function parameters into the source code under test and supports model building and optimization algorithms to reduce the state space. We have successfully applied this optimized hybrid verification methodology to embedded software applications: Motorola's Powerstone Benchmark suite and a complex automotive industrial embedded software. The results show that our approach scales better than standalone software model checkers to reach deep state spaces.

The constant pressure for making functional verification more agile has led to the conception of coverage driven verification (CDV) techniques. CDV has been implemented in verification testbenches using supervised learning techniques to model the relationship between coverage events and stimuli generation, providing a feedback between them. One commonly used technique is the classification- or decision-tree data mining, which has shown to be appropriate due to the easy modeling. Learning techniques are applied in two steps: training and application. Training is made on one or more sets of examples, which relate datasets to pre-determined classes. Precision of results by applying the predictive learning concept has shown to be sensitive to the size of the training set and the amount of imbalance of associated classes, this last meaning the number of datasets associated to each class is very different from each other. This work presents experiments on the manipulation of data mining training sets, by changing the size and reducing the imbalances, in order to check their influence on the CDV efficiency. To do that, a circuit example with a large input space and strong class imbalance was selected from the application domain of multimedia systems and another one, with a small input space that affects the coverage occurrences, was selected from the communication area.

Functional verification techniques based on fault injection and simulation at register-transfer level (RTL) have been largely investigated in the past years. Although they have various advantages such as scalability and simplicity, they commonly suffer from the low speed of the cycle-accurate RTL simulation. On the other hand, Transaction-level modeling (TLM) allows a simulation speed sensibly faster than RTL. This article presents FAST, a framework to accelerate RTL fault simulation through automatic RTL-to-TLM abstraction. FAST abstracts RTL models injected with any RTL fault model into equivalent injected TLM models thus allowing a very fast fault simulation at TLM level. The article also presents FAST-DT, a new bit-accurate data type library integrated in the framework that allows a further improvement of the simulation speed-up. Finally, the article shows how the generated TLM test patterns can be automatically synthesized into RTL test patterns by exploiting the structural information of the RTL model extracted during the abstraction process. Experimental results have been performed on several designs of different size and complexity to show the methodology effectiveness.

It has been advocated by many experts in design verification that the key to successful verification convergence lies in developing the verification plan with adequate formal rigor. Traditionally, the verification plans for simulation and formal property verification (FPV) are developed in different ways, using different formalisms, and with different coverage goals. In this paper, we propose a framework where the difference between formal properties and simulation test points is diluted by using methods for translating one form of the specification to the other. This allows us to reuse simulation coverage to facilitate formal verification and to reuse proven formal properties to cover simulation test points. We also propose the use of inline assertions in procedural (possibly randomized) test benches, and show that it facilitates the use of hybrid verification techniques between simulation and bounded model checking. We propose the use of promising combinations of formal methods presented in our earlier papers to shape a hierarchical verification flow where simulation and formal methods aim to cover a common design intent specification. The proposed flow is demonstrated using a detailed case study of the ARM AMBA verification benchmark. We believe that the methods presented in this work will stimulate new thought processes and ultimately lead to wider adoption of cohesive coverage management techniques in the design intent validation flow.

Extended finite state machines (EFSMs) can be efficiently adopted to model the functionality of complex designs without incurring the state explosion problem typical of the more traditional FSMs. However, traversing an EFSM can be more difficult than an FSM because the guards of EFSM transitions involve both primary inputs and registers. This paper first analyzes the hardness of traversing an EFSM according to the characteristics of its transitions. Then, it presents a methodology to generate an EFSM which is easy to be traversed. Finally, it proposes a functional deterministic automatic test pattern generation (ATPG) approach that exploits such EFSMs for functional verification. In particular, the ATPG approach joins backjumping, learning, and constraint solving to (i) early identify possible symptoms of design errors by efficiently exploring the whole state space of the design under verification (DUV), and (ii) generate effective input sequences to be used in further verification steps which require to stimulate the DUV. The effectiveness of the proposed approach is confirmed in the experimental result section, where it is compared with both genetic and pseudo-deterministic techniques.

In today's semiconductor industry, where time-to-profit is a critical factor to remain competitive, missing the tight market window might have serious implications including the risk of product cancellation. This places severe pressure on every aspect related to the design and the verification of semiconductor chips to get the design ready for manufacturing in the shortest time possible. To avoid the need for costly corrective steps and silicon re-spins during post-silicon verification, thorough pre-silicon verification is essential to catch any design fault and estimate the design overall reliability before the design is manufactured. This paper presents a novel EDA tool that helps the verification team improve the verification process in several ways. It can be used to generate useful statistics regarding the complexity and the coverage of the created test vectors. Experimental results prove that the verification team can successfully use the proposed tool to set their target coverage and intelligently select the set of test vectors that achieves that target using the minimum number of computing cycles.

We introduce SImulation Verification with Augmentation (SIVA), a tool for coverage-directed state space search on digital hardware designs. SIVA tightly integrates simulation with symbolic techniques for efficient state space search. Specifically, the core algorithm uses a combination of ATPG and BDDs to generate “directed” input vectors, i.e., inputs which cover behavior not excited by simulation. We also present approaches to automatically generate “lighthouses” that guide the search towards hard-to-reach coverage goals. Experiments demonstrate that our approach is capable of achieving significantly greater coverage than either simulation or symbolic techniques in isolation.

Constraining and biasing are frequently used techniques to enhance the quality of randomized vector generation. In this paper, we present a novel method that combines constraints and input biasing in automatic bit-vector generation for block-level functional verification of digital designs, which is implemented in a tool called SimGen. Vector generation in SimGen is confined to a legal input space that is defined by constraints symbolically represented in Binary Decision Diagrams (BDDs). A constraint involving state variables in the design defines a state-dependent legal input space. Input biasing can also depend on the state of the design. The effect of constraints and input biasing are combined to form what we called the constrained probabilities of input vectors. An algorithm is developed to efficiently generate input vectors on-the-fly during simulation. The vector generation is a one-pass process, i.e., no backtracking or retry is needed. Also, we describe methods of minimizing the constraint BDDs in an effort to reduce the simulation-time overhead of SimGen. Furthermore we discuss the application of SimGen to a set of commercial design blocks.

We present our formal combinational logic equivalence checking methods for industry-sized circuits. Our methods employ functional (OBDDs) algorithms for decisions on logic equivalence and structural (ATPG) algorithms to quickly identify inequivalence. The complimentary strengths of the two types of algorithms result in a significant reduction in CPU time. Our methods also involve analytical and empirical heuristics whose impact on performance for industrial designs is considerable. The combination of OBDDs, ATPG, and our heuristics resulted in a decrease in CPU time of up to 80% over OBDDs alone for the circuits we tested. In addition, we describe an algorithm for automatically determining the correspondence between storage elements in the designs being compared.

Despite great advances in the area of Formal Verification during the last ten years, simulation is currently the primary means for performing design verification. The definition of an accurate and pragmatic measure for the coverage achieved by a suite of simulation vectors and the related problem of coverage directed automatic test generation are of great importance. In this paper we introduce a new set of metrics, called the Event Sequence Coverage Metrics (ESCMs). Our approach is based on a simple and automatic method to extract the control flow of a circuit so that the resulting state space can be explored for validation coverage analysis and automatic test generation. During simulation we monitor, in addition to state and transition coverage, whether certain control event sequences take place or not. We then combine formal verification techniques, using BDDs as the underlying representation, with traditional ATPG and behavioral test generation techniques to automatically generate additional sequences which traverse uncovered parts of the control state graph, or exercise an uninstantiated control event sequence.

In this letter we report the formal verification of microprocessors. After we describe algebraically a bit-sliced microprocessor at both function and logic levels, we apply the symbolic manipulation of Mathematica.