We present a formal proof of a time-triggered hardware interface. The design implements the bit-clock synchronization mechanism specified by the FlexRay standard for automotive embedded systems. The design is described at the gate-level. It can be translated to Verilog and synthesized on FPGA. The proof is based on a general model of asynchronous communications and combines interactive theorem proving in Isabelle HOL and automatic model-checking using NuSMV together with a model-reduction procedure, IHaVeIt. Our general model of asynchronous communications defines a clear separation between analog and digital concerns. This separation enables the combination of theorem proving and model-checking for an efficient methodology. The analog phenomena are formalized in the logic of Isabelle HOL. The gate-level hardware is automatically analyzed using IHaVeIt. Our proof reveals the correct values of a crucial parameter of the bit-clock synchronization mechanism. Our main theorem proves the functional correctness as well as the maximum number of cycles of the transmission.
The verification of analog and mixed signal (AMS) designs is a relatively young research field. A recent survey gave an overview of this emerging research area @cite_11 . The authors identify several successful applications of automatic techniques (equivalence checking, model checking, or run-time verification) in the context of AMS designs. Our work is more related to the last category identified in this survey, namely proof based methods. Hanna @cite_16 @cite_9 used predicates to approximate analog behaviors at the transistor level. The predicates can be embedded in digital proofs. His work is not specifically targeted to communication circuits and does not consider timing parameters, metastability or clock drift. We consider only gates and not their structure in terms of transistors. Recently, Al Sammane @cite_12 proposed a new symbolic verification methodology based on the computer algebra system Mathematica. This approach is based on a combination of induction and symbolic simulations. It is suitable to systems that can be described using discrete-time models. One contribution of our work is to combine discrete-time models with continuous time models.
@cite_9 @cite_16 @cite_12 @cite_11
2144275718 2116358561 1583869287 2964352321
The paper proposed a new symbolic verification methodology for proving the properties of analog and mixed signal (AMS) designs. Starting with an AMS description and a set of properties and using symbolic computation, a normal mathematical representation was extracted for the system in terms of recurrence equations. These normalized equations are used along with an induction verification strategy defined inside the computer algebra system Mathematica to prove the correctness of the properties. The methodology was applied on a third order DeltaSigma modulator Analog and mixed signal (AMS) designs are an important part of embedded systems that link digital designs to the analog world. Due to challenges associated with its verification process, AMS designs require a considerable portion of the total design cycle time. In contrast to digital designs, the verification of AMS systems is a challenging task that requires lots of expertise and deep understanding of their behavior. Researchers started lately studying the applicability of formal methods for the verification of AMS systems as a way to tackle the limitations of conventional verification methods like simulation. This paper surveys research activities in the formal verification of AMS designs as well as compares the different proposed approaches. Symbolic model checking with Binary Decision Diagrams (BDDs) has been successfully used in the last decade for formally verifying finite state systems such as sequential circuits and protocols. Since its introduction in the beginning of the 90's, it has been integrated in the quality assurance process of several major hardware companies. The main bottleneck of this method is that BDDs may grow exponentially, and hence the amount of available memory re- stricts the size of circuits that can be verified efficiently. In this article we survey a technique called Bounded Model Checking (BMC), which uses a propositional SAT solver rather than BDD manipulation techniques. Since its introduction in 1999, BMC has been well received by the industry. It can find many logical er- rors in complex systems that can not be handled by competing techniques, and is therefore widely perceived as a complementary technique to BDD-based model checking. This observation is supported by several independent comparisons that have been published in the last few years. Verification of temporal logic properties plays a crucial role in proving the desired behaviors of hybrid systems. In this paper, we propose an interval method for verifying the properties described by a bounded linear temporal logic. We relax the problem to allow outputting an inconclusive result when verification process cannot succeed with a prescribed precision, and present an efficient and rigorous monitoring algorithm that demonstrates that the problem is decidable. This algorithm performs a forward simulation of a hybrid automaton, detects a set of time intervals in which the atomic propositions hold, and validates the property by propagating the time intervals. A continuous state at a certain time computed in each step is enclosed by an interval vector that is proven to contain a unique solution. In the experiments, we show that the proposed method provides a useful tool for formal analysis of nonlinear and complex hybrid systems.