Logics for hybrid systems

Hybrid systems are heterogenous dynamical systems characterized by interacting continuous and discrete dynamics. Such mathematical models have proved fruitful in a great diversity of engineering applications, including air-traffic control, automated manufacturing, and chemical process control. The high-profile and safety-critical nature of the application areas has fostered a large and growing body of work on formal methods for hybrid systems: mathematical logics, computational models and methods, and computer-aided reasoning tools supporting the formal specification and verification of performance requirements for hybrid systems, and the design and synthesis of control programs for hybrid systems that are provably correct with respect to formal specifications. This paper offers synthetic overview of, and original contributions to, the use of logics and formal methods in the analysis of hybrid systems     

Design and verification of a frequency domain equalizer

In this work we provide a methodology for the design and verification of a frequency domain equalizer. The performance analysis of the equalizer is conducted using two methods: simulation based verification in Simulink and System Generator and theorem proving techniques in Higher Order Logic. We conduct both floating-point and fixed-point error estimations for the design in Simulink and System Generator, respectively. Then, we use formal error analysis based on the theorem proving to verify an implementation of the frequency domain equalizer based on the Fast LMS algorithm. The formal error analysis and simulation based error estimation of the algorithm intend to show that, when converting from one number domain to another, the algorithm produces the same values with an accepted error margin caused by the round-off error accumulation. This work shows the efficiency of combining simulation and formal verification based methods in verifying complex systems such as the frequency domain equalizer.     

Cross-Abstraction Functional Verification and Performance Analysis of Chip Multiprocessor Designs

This paper introduces the cross-abstraction real-time analysis (Carta) framework for the model-based functional verification and performance estimation of chip multiprocessors (CMPs) utilizing bus matrix (crossbar switch) interconnection networks. We argue that the inherent complexity in CMP designs requires the synergistic use of various models of computation to efficiently manage the tradeoffs between accuracy and complexity. Our approach builds on domain-specific modeling languages (DSMLs) driving an open-source tool-chain that provides a cross-abstraction bridge between the finite-state machine (FSM), discrete-event (DE), and timed automata (TA) models of computation, and utilizes multiple model checkers to analyze formal properties at the cycle-accurate and transaction-level abstractions. The cross-abstraction analysis exploits accuracy for functional verification, and achieves significant speedups for performance estimation with marginal accuracy loss. We demonstrate results on an industrial strength networking CMP design utilizing a bus matrix interconnection network. To the best of our knowledge, the Carta framework is the first model-based tool-chain that utilizes multiple abstractions and model checkers for the comprehensive and formal functional verification, performance estimation, and real-time verification of bus matrix-based CMP designs.      

Research on Formal Degree Evaluation and Analysis for Domain Software Based on Evidence

Existing researches fail to involve formalized methods in evaluation and analysis of domain software and lack analysis on formal degree,this paper comes up with a formal degree evaluation approach for domain software based on evidence.Various levels of transformation models are mapped by formal analysis of evidence in life cycle of domain software so as to quantitatively measure degree of evidence.Evaluation model based on evidence is established by analyzing detailed evaluation requirement.A level model including mapping condition is established to describe formal degree at hierarchical level.This paper explains detailed evaluation process through an evaluation example.The approach stated in this paper can describe formal degree of domain software,evaluation data can support subsequent bottleneck analysis and trustworthy evolution,thus provide formal support for creditable construction and analysis.     

Applying infinite state model checking and other analysis techniques to tabular requirements specifications of safety-critical systems

Although it is most often applied to finite state models, in recent years, symbolic model checking has been extended to infinite state models using symbolic representations that encode infinite sets. This paper investigates the application of an infinite state symbolic model checker called Action Language Verifier (ALV) to formal requirements specifications of safety-critical systems represented in the SCR (Software Cost Reduction) tabular notation. After reviewing the SCR method and tools, the Action Language for representing state machine models, and the ALV infinite state model checker, the paper presents experimental results of formally analyzing two SCR specifications using ALV. The application of ALV to verify or falsify (by generating counterexample behaviors) the state and transition invariants of SCR specifications and to check Disjointness and Coverage properties is described. The results of formal analysis with ALV are then compared with the results of formal analysis using techniques that have been integrated into the SCR toolset. Based on the experimental results, strengths and weaknesses of infinite state model checking with respect to other formal analysis approaches such as explicit and finite state model checking and theorem proving are discussed.     

SMT-Based Symbolic Encoding and Formal Analysis of HML Models

Hybrid system is a dynamic system that involves continuous, discrete behaviors, and the interactions between continuous physical components and discrete controllers. In this paper a hybrid modeling language (called HML) for hybrid systems is extended with templates to achieve code reuse. For the formal analysis of the corresponding hybrid system models in this modeling language, these models are translated into SMT (satisfiability modulo theories) formulas as the input to an SMT solver dReal which retains the capability of bounded reachability analysis for non-linear hybrid systems. Moreover, dReal can produce data for potential traces of hybrid systems, thus it can be employed to simulate on hybrid systems. In this paper the simulation and reachability analysis are integrated in a prototype tool (open source). We present a case study for an inverted pendulum with PID (Proportional-Integral-Derivative) controllers and a rod reactor system for temperature control, both are verified to demonstrate the efficiency of the prototype tool. We conclude that, this modeling language is capable of modeling and verification of hybrid systems based on simulation and bounded reachability analysis.     

Modeling UML sequence diagrams using extended Petri nets

Unified modeling language (UML) sequence diagrams combined with the UML profile for modeling and analysis of real-time and embedded (MARTE) systems are used to represent systems?? requirements. To enhance formal analysis abilities, sequence diagrams annotated with MARTE stereotypes are mapped into timed colored Petri nets with inhibitor arcs (TCPNIA). The mapping rules for the fragments of sequence diagrams and MARTE stereotypes are proposed respectively. They are proposed both in graphical and formal forms. The soundness of mapping rules is analyzed. The data related issues are handled through colored properties in TCPNIA models, guard functions and operational functions. A mapping rule for state invariant is proposed based on data related information. Through state invariant, complicated control relations can be expressed. Formal definitions for morphing and substitution in TCPNIA models are given. They provide modular and hierarchical modeling methods for TCPINA models. To show the applicability and feasibility of our method, an application example in vehicular ad hoc networks (VANETs) domain is studied.     

Heterogeneous Simulation—Mixing Discrete-Event Models with Dataflow

This paper relates to system-level design of signal processing systems, which are often heterogeneous in implementation technologies and design styles. The heterogeneous approach, by combining small, specialized models of computation, achieves generality and also lends itself to automatic synthesis and formal verification. Key to the heterogeneous approach is to define interaction semantics that resolve the ambiguities when different models of computation are brought together. For this purpose, we introduce a tagged signal model as a formal framework within which the models of computation can be precisely described and unambiguously differentiated, and their interactions can be understood. In this paper, we will focus on the interaction between dataflow models, which have partially ordered events, and discrete-event models, with their notion of time that usually defines a total order of events. A variety of interaction semantics, mainly in handling the different notions of time in the two models, are explored to illustrate the subtleties involved. An implementation based on the Ptolemy system from U.C. Berkeley is described and critiqued.     

Incremental compilation for parallel logic verification systems

Although simulation remains an important part of application-specific integrated circuit (ASIC) validation, hardware-assisted parallel verification is becoming a larger part of the overall ASIC verification flow. In this paper, we describe and analyze a set of incremental compilation steps that can be directly applied to a range of parallel logic verification hardware, including logic emulators. Important aspects of this work include the formulation and analysis of two incremental design mapping steps: the partitioning of newly added design logic onto multiple logic processors and the communication scheduling of newly added design signals between logic processors. To validate our incremental compilation techniques, the developed mapping heuristics have been integrated into the compilation flow for a field-programmable gate-array-based Ikos VirtuaLogic emulator . The modified compiler has been applied to five large benchmark circuits that have been synthesized from register-transfer level and mapped to the emulator. It is shown that our incremental approach reduces verification compile time for modified designs by up to a factor of five versus complete design recompilation for benchmarks of over 100 000 gates. In most cases, verification run-time following incremental compilation of a modified design matches the performance achieved with complete design recompilation.     

Integration of phonetic and prosodic information for robustutterance verification

Mandarin speech is known for its tonal characteristic, and prosodic information plays an important role in Mandarin speech recognition. Driven by this property, phonetic and prosodic information are integrated and used for Mandarin telephone speech keyword spotting. A two-stage strategy, with recognition followed by verification, is adopted. For keyword recognition, 132 subsyllable models, two general acoustic filler models and one background/silence model are separately trained and used as the basic recognition units. For utterance verification, 12 anti-subsyllable models, 175 context-dependent prosodic models and five anti-prosodic models are constructed. A keyword verification function combining phonetic-phase and prosodic-phase verification is investigated. Using a test set of 3088 conversational speech utterances from 33 speakers (20 males and 13 females) and a vocabulary of 2583 faculty names, at 8.5% false rejection, the proposed verification method results in an 18.3% false alarm rate. Furthermore, this method is able correctly to reject 90.9% of non-keywords. Comparison with a baseline system without prosodic-phase verification shows that prosodic information can benefit the verification performance     

Physical timing modeling for bipolar VLSI

An approach for the analytical timing modeling of bipolar VLSI circuits that is based on average branch current analysis and the parametric correction scheme is presented. The combination of these techniques permits complex delay-sensitive effects of bipolar digital circuits to be incorporated in the derivation of the bipolar delay models. The delay functions of two basic bipolar subcircuit configurations (the series-gated structure and the emitter follower) are derived using the proposed techniques. It is shown that accurate timing information for the high-speed bipolar digital circuit, such as ECL, CML, and BiCMOS, can be obtained by repeated processing of these subcircuit delay functions. The delay estimates obtained with these timing models have been shown to be accurate typically within 10% of SPICE estimates. Applications include switch-level timing simulation, timing analysis and verification cell optimization, and technology mapping     

Formal Verification of Analog and Mixed Signal Designs Using SPICE Circuit Simulation Traces

Analog and Mixed Signal (AMS) designs can be formally modeled as hybrid systems [45] and therefore formal verification techniques applicable to hybrid systems can be deployed to verify them. An extension to a formal verification approach applicable to hybrid systems is proposed to verify AMS designs [31]. In this approach formal verification (FV) is carried out on an AMS block using simulation traces from SPICE, a simulator widely used in the design and verification of analog and AMS blocks. A broader implication of this approach is the ability to carry out hierarchical verification using relevant simulation traces obtained at different abstraction levels of a design when modeled in appropriate platforms. This enables a seamless transition of design and verification artifacts from the highest level of abstraction to the lowest level of implementation at the transistor level of any AMS design and a resulting increase in confidence on the correctness of the final implementation. The proposed approach has been justified with its applications to different AMS design blocks. For each design, its formal model and the proposed computational techniques have been incorporated into CheckMate [11] - a FV tool for hybrid systems based on MATLAB and the Simulink/Stateflow framework from MathWorks. A further justification of the proposed approach is the resulting improvements observed in terms of reduced verification time for different specifications in each design.     

Toward efficient protocol design through protocol profiling and performance assessment: using formal verification in a different context

The most common use of formal verification methods so far has been in identifying whether livelock and/or deadlock situations can occur during protocol execution, process, or system operation. In this work, we aim to show that an additional equally important and useful application of formal verification methods can be in protocol design in terms of performance‐related metrics. This can be achieved by using the methods in a rather different context compared with their traditional use, that is, not only as model checking tools to assess the correctness of a protocol in terms of lack of livelock and deadlock situations but rather as tools capable of building profiles of protocol operations, assessing their performance, and identifying operational patterns and possible bottleneck operations. This process can provide protocol designers with an insight about the protocols’ behavior and guide them toward further optimizations. It can also assist network operators and service providers to assess the protocols’ relative performance and select the most suitable protocol for specific deployment scenarios. We illustrate these principles by showing how formal verification tools can be applied in this protocol profiling and performance assessment context using some existing protocol implementations in mobile and wireless environments as case studies. Copyright © 2011 John Wiley & Sons, Ltd.     

Modular Verification of Computer Communication Protocols

Programs that implement computer communications protocols can exhibit extremely complicated behavior, and neither informal reasoning nor testing is reliable enough to establish their correctness. In this paper we discuss the application of modular program verification techniques to protocols. This approach is more reliable than informal reasoning, but has an advantage over formal reasoning based on finite-state models, the complexity of the proof need not grow unmanageably as the size of the program increases. Certain tools of concurrent program verification that are especially useful for protocols are presented, history variables that record sequences of input and output values, temporal logic for expressing properties that must hold in a future system state such as eventual receipt of a message), and module specification and composition rules. The use of these techniques is illustrated by verifying two data transfer protocols from the literature: the alternating bit protocol and a protocol proposed by Stenning.     

云计算虚拟环境的形式化安全验证

云计算是一种新兴的计算、存储资源使用模式,由于具备低成本、高效率等优点,得到了业界的广泛应用,但安全性仍然是云计算推广最大的障碍之一。虚拟化作为云计算的关键技术,其安全水平直接影响云环境的安全性,目前对云计算虚拟环境多采用传统的覆盖式验证方法,无法彻底解决正确性问题。文中通过结合形式化方法中的模型检测技术,经过配置采集、需求分析和性质检测3个阶段对虚拟化安全性质进行高覆盖率验证,提供了一种对云计算环境进行安全评估的可行思路。     

Causal reasoning mining approach to analog circuit verification

Functional errors in analog portion of mixed signal circuits become more severe and improvements in verification methods are increasingly important. Current verification methods fall into two categories, simulation-based verification and formal verification (Barke et al. [1]), focusing on verifying analog circuit function/performance. This paper proposes a novel approach verifying analog circuit design using causal reasoning. Causal reasoning is the inductive reasoning process to create a new design. The flow begins with mining the causal reasoning steps (design plan) that produced the circuit, including starting ideas, design step sequence, and their justifications (Jiao et al., 2015 [2]). Then, topological features corresponding to the starting ideas and design step sequence are verified individually by replacing the related devices with ideal behavior model. Performance is evaluated through Cadence Spectre simulation. Comparison with new circuit performance reveals incorrect functional issues and/or performance potentials for improvement. They are negative causes of certain starting ideas or design steps, which might have been omitted during the design process. The paper discusses three operational amplifier designs realized in 0.2-μm CMOS technology to illustrate the verification approach.