Time Domain Verification of Oscillator Circuit Properties

The application of formal methods to analog and mixed signal circuits requires efficient methods for constructing abstractions of circuit behaviors. This paper concerns the verification of properties of oscillator circuits. Generic monitor automata are proposed to facilitate the application of hybrid system reachability computations to characterize time domain features of oscillatory behavior, such as bounds on the signal amplitude and jitter. The approach is illustrated for a nonlinear tunnel-diode circuit model using PHAVer, a hybrid system analysis tool that provides sound verification results based on linear hybrid automata approximations and infinite precision computations.     

Analog Circuit Verification: a State of an Art

Extending formal verification methodology toward analog circuits is a very challenging task that will occupy researchers for some time. To put this challenge in context we sketch some of the history of digital circuit verification as well as more recent attempts to adapt it to continnuous and hybrid systems.     

On simulation-based probabilistic model checking of mixed-analog circuits

In this paper, we consider verifying properties of mixed-signal circuits, i.e., circuits for which there is an interaction between analog (continuous) and digital (discrete) values. We use a simulation-based approach that consists of evaluating the property on a representative subset of behaviors and answering the question of whether the circuit satisfies the property with a probability greater than or equal to some threshold. We propose a logic adapted to the specification of properties of mixed-signal circuits in the temporal domain as well as in the frequency domain. We also demonstrate the applicability of the method on different models of Δ–Σ modulators for which previous formal verification attempts were too conservative and required excessive computation time.     

Analog property checkers: a DDR2 case study

The formal specification component of verification can be exported to simulation through the idea of property checkers. The essence of this approach is the automatic construction of an observer from the specification in the form of a program that can be interfaced with a simulator and alert the user if the property is violated by a simulation trace. Although not complete, this lighter approach to formal verification has been effectively used in software and digital hardware to detect errors. Recently, the idea of property checkers has been extended to analog and mixed-signal systems.     

Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware

We propose to utilize a formal verification algorithm to reduce the fitness evaluation time for evolutionary post-synthesis optimization in evolvable hardware. The proposed method assumes that a fully functional digital circuit is available. A post-synthesis optimization is then conducted using Cartesian Genetic Programming (CGP) which utilizes a satisfiability problem solver to decide whether a candidate solution is functionally correct or not. It is demonstrated that the method can optimize digital circuits of tens of inputs and thousands of gates. Furthermore, the number of gates was reduced for the LGSynth93 benchmark circuits by 37.8% on average with respect to results of the conventional SIS tool.     

Verifying global start-up for a Möbius ring-oscillator

This paper presents the formal verification of start-up for a differential ring-oscillator circuit used in industrial designs. We present an efficient algorithm for finding DC equilibria to establish a condition that ensure the oscillator is free from lock-up. Further, we present a formal verification solution for the problem. Using dynamical systems theory, we show that any oscillator must have a non-empty set of states from which it fails to start properly. However, it is possible to show that these failures only occur with zero probability. To do so, this paper generalizes the “cone argument” initially presented in (Mitchell and Greenstreet, in Proceedings of the third workshop on designing correct circuits, 1996) and proves the soundness of this generalization. This paper also shows how concepts from analog design such as differential operation can be soundly incorporated into the verification to produce simpler models and reduce the complexity of the verification task.     

Enterprise model verification and validation: an approach

This article presents a verification and validation approach which is used here in order to complete the classical tool box the industrial user may utilize in enterprise modeling and integration domain. This approach, which has been defined independently from any application domain is based on several formal concepts and tools presented in this paper. These concepts are property concepts, property reference matrix, properties graphs, enterprise modeling domain ontology, conceptual graphs and formal reasoning mechanisms.     

Time Constrained Verification of Analog Circuits using Model-Checking Algorithms

In this contribution we present algorithms for model checking of analog circuits enabling the specification of time constraints. Furthermore, a methodology for defining time-based specifications is introduced. An already known method for model checking of integrated analog circuits has been extended to take into account time constraints. The method will be presented using three industrial circuits. The results of model checking will be compared to verification by simulation.     

多值开关级代数在MOS电路形式验证中的应用

本文讨论了ＭＯＳ电路多值开关级代数表达式的三种标准结构，给出了将多值开关级表达式转换成布尔表达式的定理，基于这些理论，提出了ＭＯＳ电路开关级形式验证的一种方法。     

On Using B in the Design of Secure Micro-controllers: An Experience Report

The stepwise formal development of safety critical software is now a well established engineering practice, noticeably in railway systems. However, it has not been applied as successfully to hardware development, where formal methods are mainly used for verification and gate level transformations and optimizations. In this paper, we report our recent experience in the stepwise formal development of a real macro-cell, that opens the way to the design of synchronous digital circuits with zero functional bugs. We propose a development flow suited for obtaining proven correct-by-construction circuits that further possess additional robustness properties desirable for secure chips. The reported work is prospective and is meant to show the feasibility of such a technique for high confidence trustful devices.     

区域控制器的安全需求建模与自动验证

轨道交通区域控制器（ZC）是我国轨道交通信号系统选型的主流制式——基于通信的列车控制系统（CBTC）的核心子系统，其突出的安全性使得安全需求的形式化验证成为一个非常重要的问题.但是ZC自身的复杂性以及领域知识的繁杂难以掌握，使得形式化方法很难应用到安全需求的验证中去.针对这些问题，提出一种安全需求的自动验证方法，使用半形式化的问题框架方法（PF）来建模和分解安全需求，根据需求模型自动生成安全需求的验证模型和验证性质，在此基础上自动生成验证模型的Scade语言实现，并通过Design Verifier验证器对需求进行组合验证.最后，使用了某个实际案例ZC的一个子问题CAL_EOA进行了研究，实验结果证明了该方法的可行性与有效性，它能自动地将安全需求模型进行组合验证，改善了验证的效率.     

Analysing the Robustness of Surfing Circuits

Surfing is a technique for implementing high-speed digital pipelines that exploits the analog dynamics of the underlying circuits. Thus, verification must consider the analog behaviour of the design. We have presented a method for analysing the robustness of surfing circuits. We formulate noise margin analysis as a non-linear optimization problem where we find the smallest disturbance waveform that results in a qualitative change in the behavior of the circuit. We present a practical method for solving these optimization problems based on deriving a sensitivity matrix for the small-signal response of the circuit.     

基于电路拓扑结构分析的等价性验证方法

随着集成电路设计规模的日益增大,结合多种推理引擎已成为组合电路形式化等价性验证的重要手段.提出一种基于电路拓扑结构分析的组合等价性验证方法,将电路的拓扑结构与验证算法的复杂性关联起来.在验证过程开始之前,利用min-cut方法计算表征电路复杂性的"电路宽度",以确定最佳的推理引擎,避免了传统的引擎切换过程,提高了算法的效率.针对ISCAS85电路的实验结果表明了该方法的效率和可行性.     

利用SMT约束分解方法求解RTL可满足性问题

随着集成电路技术与工艺的不断发展,目前工业界所采用的形式验证工具已很难适应集成电路规模的飞速增长.为了对RTL电路的可满足性问题进行形式验证,提出基于超图划分的约束分解实现可满足性模理论(SMT)求解的分级验证方法.通过分析RTL电路的结构约束,对约束集合中的元素和相关变量进行约束建模,并构建带有合适权重的超图模型;利用超图划分的机制寻找带有最小割集的等量划分,实现约束分解,完成RTL电路的定界模型检验.实验结果表明,该方法能够减小处理问题的规模和求解过程中的搜索空间,提高验证效率.     

基于斜率故障模型的模拟电路软故障字典法

提出了一种新的模拟电路故障字典法。与传统方法不同,该方法利用两个节点电压之间的关系函数作为故障特征。对于线性模拟电路,节点电压关系函数为一次函数,函数的斜率可以作为故障模型,同时可以诊断硬故障和参数(软)故障。由于模拟电路存在容差,最小直线距离法可以用于处理电路中的容差问题。     

基于Object-Z的形式化验证方法

定理证明是一种形式化验证技术,也是形式化方法的重要组成部分,它能从形式规格说明中推理出应具备的性质与属性,从而可以对规格说明进行形式验证。Obiect-Z是形式规格说明语言Z的面向对象扩充,基于集合论与数理逻辑,具有严密的逻辑性,适合精确地描述大型软件系统,并且可以对其形式规格说明进行推理。本文首先给出了基于Object—Z规格说明的定理证明验证方法,接着用Object-Z描述了一个电梯操作系统的实例,在此基础上给出了其形式规格说明的定理证明方法来进行形式化验证。