LVT: a layered verification technique for distributed computing systems

This paper presents a layered verification technique, called LVT, for the verification of distributed computing systems with multiple component layers. Each lower layer in such a system provides services in support of functionality of the higher layer. By taking a very general view of programming languages as interfaces of systems, LVT treats each layer in a distributed computing system as a distributed programming language. Each relatively higher‐level language in the computing system is implemented in terms of a lower‐level language. The verification of each layer in a distributed computing system can then be viewed as the verification of implementation correctness for a distributed language. This paper also presents the application of LVT to the verification of a distributed computing system, which has three layers: a small high‐level distributed programming language; a multiple processor architecture consisting of an instruction set and system calls for inter‐process message passing; and a network interface. Programs in the high‐level language are implemented by a compiler mapping from the language layer to the multiprocessor layer. System calls are implemented by network services. LVT and its application demonstrate that the correct execution of a distributed program, most notably its inter‐process communication, is verifiable through layers. The verified layers guarantee the correctness of (1) the compiled code that makes reference to operating system calls, (2) the operating system calls in terms of network calls, and (3) the network calls in terms of network transmission steps. The specification and verification involved are carried out by using the Cambridge Higher Order Logic (HOL) theorem proving system. Copyright © 1999 John Wiley & Sons, Ltd.     

Verification and analysis of domain-specific models of physical characteristics in embedded control software

ContextA considerable portion of the software systems today are adopted in the embedded control domain. Embedded control software deals with controlling a physical system, and as such models of physical characteristics become part of the embedded control software.ObjectiveDue to the evolution of system properties and increasing complexity, faults can be left undetected in these models of physical characteristics. Therefore, their accuracy must be verified at runtime. Traditional runtime verification techniques that are based on states/events in software execution are inadequate in this case. The behavior suggested by models of physical characteristics cannot be mapped to behavioral properties of software. Moreover, implementation in a general-purpose programming language makes these models hard to locate and verify. Therefore, this paper proposes a novel approach to perform runtime verification of models of physical characteristics in embedded control software.MethodThe development of an approach for runtime verification of models of physical characteristics and the application of the approach to two industrial case studies from the printing systems domain.ResultsThis paper presents a novel approach to specify models of physical characteristics using a domain-specific language, to define monitors that detect inconsistencies by exploiting redundancy in these models, and to realize these monitors using an aspect-oriented approach. We complement runtime verification with static analysis to verify the composition of domain-specific models with the control software written in a general-purpose language.ConclusionsThe presented approach enables runtime verification of implemented models of physical characteristics to detect inconsistencies in these models, as well as broken hardware components and wear and tear of hardware in the physical system. The application of declarative aspect-oriented techniques to realize runtime verification monitors increases modularity and provides the ability to statically verify this realization. The complementary static and runtime verification techniques increase the reliability of embedded control software.     

C program verification in SPECTRUM multilanguage system

An extendable multilanguage analysis and verification system SPECTRUM is presented; this system is being developed in the framework of the project SPECTRUM. The prospects of the application of this system are demonstrated, as exemplified by the verification of C programs. The project SPECTRUM is aimed at the creation of a new integrated approach to the verification of imperative programs that makes it possible to integrate, unify, and combine methods and approaches for verification of imperative programs and accumulate and apply information about these programs. The specific feature of this approach is the application of a specialized executable specification language Atoment for the development of program verification tools; this language makes it possible to represent methods and approaches for verification and data for them (program models, annotations, logical formulae) in a unified format. The C component of the SPECTRUM system uses a two-level C program verification method. This method is a good illustration of the integrated approach, since it provides complex verification of C programs based on a combination of the operational, axiomatic, and transformational approaches.     

Verification of distributed control systems in intelligent manufacturing

This paper presents an application of formal methods for validation of flexible manufacturing systems controlled by distributed controllers. A software tool verification environment for distributed applications (VEDA) is developed for modeling and verification of distributed control systems. The tool provides an integrated environment for formal, model-based verification of the execution control of function blocks following the new international standard IEC61499. The modeling is performed in a closed-loop way using manually developed models of plants and automatically generated models of controllers.     

Component-based analysis of embedded control applications

The widespread use of embedded systems requires the creation of industrial software technology that will make it possible to engineer systems being correct by construction. That can be achieved through the use of validated (trusted) components, verification of design models, and automatic configuration of applications from validated design models and trusted components. This design philosophy has been instrumental for developing COMDES—a component-based framework for distributed embedded control systems. A COMDES application is conceived as a network of embedded actors that are configured from instances of reusable, executable components—function blocks (FBs). System actors operate in accordance with a timed multitasking model of computation, whereby I/O signals are exchanged with the controlled plant at precisely specified time instants, resulting in the elimination of I/O jitter. The paper presents an analysis technique that can be used to validate COMDES design models in SIMULINK. It is based on a transformation of the COMDES design model into a SIMULINK analysis model, which preserves the functional and timing behaviour of the application. This technique has been employed to develop a feasible (light-weight) analysis method based on runtime observers. The latter are conceived as special-purpose actors running in parallel with the application actors, while checking system properties specified in Linear Temporal Logic. Observers are configured from reusable FBs that can be exported to SIMULINK in the same way as application components, making it possible to analyze system properties via simulation. The discussion is illustrated with an industrial case study—a Medical Ventilator Control System, which has been used to validate the developed design and analysis methods.     

基于确定性因子的启发式属性值约简模型

现有属性值约简模型程序复杂,难以实现,而且模型所提取的关键信息往往过于追求简明,会削弱决策系统的表达能力。为解决以上问题,提出一种基于确定性因子的启发式属性值约简模型。首先,构造几种不同性质的属性集工具,并给出其相关定理及证明;同时开发一种约简信息函数,从而为约简属性赋值;然后,将确定性因子作为启发信息,并采用自底向上式分层搜索策略来构建启发式属性值约简模型,并以程序伪代码的形式直观展示模型的布置路径与运行流程;最后,采用已有研究中的模拟数据开展模型的应用与验证,并对模型的优势、适用性与延展性展开总结与讨论。结果表明,新模型可行有效,易于编程实现;对数据特征要求低,适合一般性专家系统;所提取的价值信息多元简约,泛化性强,不丢失决策系统的关键信息。     

复杂系统仿真模型和软件的校核方法

对复杂仿真系统而言,对其性能评估是仿真领域研究的一个重要问题,其中仿真可信度是最重要的指标,因为仿真可信度能否达到要求,直接关系到仿真系统应用的成败,而仿真可信度要解决的关键问题之一就是模型的校核（Verification）问题。该文就复杂系统的仿真,分别从不同角度给出了仿真算法和软件的校核方法,如对多层次结构系统模型给出了分层、逐级校核方法,对多输入多输出系统给出了化复杂为简单、逐步进行模型校核的方法,同时对某类武器系统仿真模型给出了逆解法校核方法,并对多人对同一问题相互校核的方法给出了仿真算例和结论。这些方法可对提高模型和软件的可信度起到一定的参考作用。     

A verification framework with application to a propulsion system

This paper introduces a novel verification framework for Prognostics and Health Management (PHM) systems. Critical aircraft, spacecraft and industrial systems are required to perform robustly, reliably and safely. They must integrate hardware and software tools intended to detect and identify incipient failures and predict the remaining useful life (RUL) of failing components. Furthermore, it is desirable that non-catastrophic faults be accommodated, that is fault tolerant or contingency management algorithms be developed that will safeguard the operational integrity of such assets for the duration of the emergency. It is imperative, therefore, that models and algorithms designed to achieve these objectives be verified before they are validated and implemented on-board an aircraft. This paper develops a verification approach that builds upon concepts from system analysis, specification definition, system modeling, and Monte Carlo simulations. The approach is implemented in a hierarchical structure at various levels from component to system safety. Salient features of the proposed methodology are illustrated through its application to a spacecraft propulsion system.     

Modularity the key to system growth potential

General Electric's Apollo Systems has developed several information systems over the last eight years in support of the Apollo project. The expertise gained in these development efforts has shown the efficiency of a modularized approach to retrieval system design Systems analysts and programmers who design and build these systems should follow the normal systems engineering approach of requirements definition, system design, system implementation, test and verification and operational installation. Short-cutting any one of these phases leads to greater effort in one of the later phases, usually with a longer over-all schedule or greater developmental cost Project management, too, is a major factor in the success of such systems. The tracking of critical milestones in the schedule, consistent and up-to-date documentation, and comprehensive test and verification plans are necessary to a controlled approach to systems implementation Finally, the benefits of such an approach are reduced cost and implementation time, along with simplification of system maintenance, standardized software, adaptability to new environments, and a potential for continued growth to meet users' ever-expanding needs.     

Comparison of hydrodynamical models of the Gulf of Finland in 1995: a case study

Three-dimensional hydrodynamic models of the Gulf of Finland, namely Finnflow and Finest, have been compared with observations of salinity, temperature water levels and currents in 1995. The Finnflow model had a vertical co-ordinate system with fixed levels whereas in the Finest model a modified sigma co-ordinate system was used. The model results were also compared with each other. Both models were able to reproduce the main spatial east–west gradient of salinity, the temporal variability of temperatures in the uppermost layers and the height variations of water levels. Problems were caused by the inaccuracies of the open boundary conditions. The verification of the models with current measurements gave less satisfactory results, mainly due to the too coarse horizontal resolution of the models. The accuracy of the near-bottom salinity and temperature suffered from inaccuracies in the open boundary condition and related problems in defining the stratification conditions in the Gulf. The Finnflow model described better up- and downwellings, while the stratification conditions were more accurately described by the Finest model. These differences are probably best explained by the different co-ordinate systems in the models.     

Compositional Verification of Knowledge-Based Task Models and Problem-Solving Methods

In this paper a compositional verification method for task models and problem-solving methods for knowledge-based systems is introduced. Required properties of a system are formally verified by deriving them from assumptions that themselves are properties of sub-components, which in their turn may be derived from assumptions on sub-sub-components, and so on. The method is based on properties that are formalized in terms of temporal semantics; both static and dynamic properties are covered. The compositional verification method imposes structure on the verification process. Because of the possibility of focusing at one level of abstraction (information and process hiding), compositional verification provides transparency and limits the complexity per level. Since verification proofs are structured in a compositional manner, they can be reused in the event of reuse of models or modification of an existing system. The method is illustrated for a generic model for diagnostic reasoning.     

An event-based approach for formally verifying runtime adaptive real-time systems

Real-time and embedded systems are required to adapt their behavior and structure to runtime unpredicted changes in order to maintain their feasibility and usefulness. These systems are generally more difficult to specify and verify owning to their execution complexity. Hence, ensuring the high-level design and the early verification of system adaptation at runtime is very crucial. However, existing runtime model-based approaches for adaptive real-time and embedded systems suffer from shortcoming linked to efficiently and correctly managing the adaptive system behavior, especially that a formal verification is not allowed by modeling languages such as UML and MARTE profile. Moreover, reasoning about the correctness and the precision of high-level models is a complex task without the appropriate tool support. In this work, we propose an MDE-based framework for the specification and the verification of runtime adaptive real-time and embedded systems. Our approach stands for Event-B method to formally verify resources behavior and real-time constraints. In fact, thanks to MDE M2T transformations, our proposal translates runtime models into Event-B specifications to ensure the correctness of runtime adaptive system properties, temporal constrains and nonfunctional properties using Rodin platform. A flood prediction system case study is adopted for the validation of our proposal.

     

Probabilistic verification and synthesis of the next generation airborne collision avoidance system

The next generation airborne collision avoidance system, ACAS X, departs from the traditional deterministic model on which the current system, TCAS, is based. To increase robustness, ACAS X relies on probabilistic models to represent the various sources of uncertainty. The work reported in this paper identifies verification challenges for ACAS X, and studies the applicability of probabilistic verification and synthesis techniques in addressing these challenges. Due to shortcomings of off-the-shelf probabilistic analysis tools, we developed a new framework, named VeriCA (Verification for Collision Avoidance). VeriCA is a combined probabilistic synthesis and verification framework that is custom designed for ACAS X and systems with similar characteristics. VeriCA supports Java as a modeling language, is memory efficient, employs parallelization, and provides an interactive simulator that displays aircraft encounters and the corresponding ACAS X behavior. We describe the application of our framework to ACAS X, together with the results and recommendations that our analysis produced.     

参数化系统二维抽象的理论基础

模型之间的等价关系和抽象模型的性质保持是保证验证正确的必要条件,参数化系统二维抽象从构成系统状态空间的二维方向分别进行抽象,证明了此抽象方法的正确性和合理性,即TDA模型与原始模型存在模拟关系,而且在TDA模型中成立的只对单个变量进行全称量化的单索引ACTL*公式,在任意规模的原始模型中也成立,为简化参数化系统验证提供了理论依据。     

Formal verification and simulation for platform screen doors and collision avoidance in subway control systems

For hybrid systems, hybrid automata-based tools are capable of verification, while Matlab Simulink/Stateflow is proficient in simulation. We propose a co-verification procedure, in which the verification tool SpaceEx/PHAVer and simulation tool Matlab are integrated to analyze and verify hybrid systems. For the application of this procedure, a platform screen door system (PSDS, a subsystem of the subway control system), is modeled with hybrid automata and Simulink/Stateflow charts, respectively. The models of PSDS are simulated by Matlab and verified by SpaceEx/PHAVer. The simulation and verification results indicate that the sandwiched situation can be avoided under time interval conditions. We improve the model with four trains and four stations on a subway line and analyze the urgent control scenario for the safety distance requirement. In this paper, the Simulink/Stateflow model is a refinement of the SpaceEx/PHAVer model, which is closer to a final implementation. Moreover, the two models are complementary for some features (e.g.,visualization of simulation, correctness proving by verification), stressing different aspects of the overall system and permitting complementary analysis techniques, i.e., verification versus simulation. We conclude that this integration procedure is competent in verifying subway control systems.     

On combining classifiers for speaker authentication

Speaker verification and utterance verification are examples of techniques that can be used for speaker authentication purposes.Speaker verification consists of accepting or rejecting the claimed identity of a speaker by processing samples of his/her voice. Usually, these systems are based on HMM models that try to represent the characteristics of the speakers’ vocal tracts.Utterance verification systems make use of a set of speaker-independent speech models to recognize a certain utterance. If the utterances consist of passwords, this can be used for identity verification purposes.Up to now, both techniques have been used separately. This paper is focused on the problem of how to combine these two sources of information. New architectures are presented to join an utterance verification system and a speaker verification system in order to improve the performance in a speaker verification task.     

Model driven code checking

Model checkers were originally developed to support the formal verification of high-level design models of distributed system designs. Over the years, they have become unmatched in precision and performance in this domain. Research in model checking has meanwhile moved towards methods that allow us to reason also about implementation level artifacts (e.g., software code) directly, instead of hand-crafted representations of those artifacts. This does not mean that there is no longer a place for the use of high-level models, but it does mean that such models are used in a different way today. In the approach that we describe here, high-level models are used to represent the environment for which the code is to be verified, but not the application itself. The code of the application is now executed as is by the model checker, while using powerful forms of abstraction on-the-fly to build the abstract state space that guides the verification process. This model-driven code checking method allows us to verify implementation level code efficiently for high-level safety and liveness properties. In this paper, we give an overview of the methodology that supports this new paradigm of code verification.     

Logic-based modeling of information transfer in cyber–physical multi-agent systems

In modeling multi-agent systems, the structure of their communication is typically one of the most important aspects, especially for systems that strive toward self-organization or collaborative adaptation. Traditionally, such structures have often been described using logic-based approaches as they provide a formal foundation for many verification methods. However, these formalisms are typically not well suited to reflect the stochastic nature of communication in the cyber–physical setting. In particular, their level of abstraction is either too high to provide sufficient accuracy or too low to be practicable in more complex models. Therefore, we propose an extension of the logic-based modeling language SALMA, which we have introduced recently, that provides adequate high-level constructs for communication and data propagation, explicitly taking into account stochastic delays and errors. In combination with SALMA’s tool support for simulation and statistical model checking, this creates a pragmatic approach for verification and validation of cyber–physical multi-agent systems.     

Discrete Event Systems for autonomous mobile agents

Discrete Event Systems (DES) are a special type of dynamic system. The ‘state’ of these systems changes at discrete instants in time and the term ‘event’ represents the occurrence of discontinuous change (at possibly unknown intervals). Different Discrete Event Systems models are currently used for specification, verification, synthesis as well as for analysis and evaluation of different qualitative and quantitative properties of existing physical systems. The focus of this paper is the presentation of the automata and formal language model for DES introduced by Ramadge and Wonham and its application to the domain of mobile manipulator/observer agents. We demonstrate the feasibility of the DES framework for modeling, analysis and synthesis of some visually guided behaviors of agents engaged in navigational tasks and address synchronization issues between different components of the system. The use of DES formalism allows us to synthesize complex behaviors in a systematic fashion and guarantee their controllability.     

Model checking Trampoline OS: a case study on safety analysis for automotive software

Model checking is an effective technique used to identify subtle problems in software safety using a comprehensive search algorithm. However, this comprehensiveness requires a large number of resources and is often too expensive to be applied in practice. This work strives to find a practical solution to model‐checking automotive operating systems for the purpose of safety analysis, with minimum requirements and a systematic engineering approach for applying the technique in practice. The paper presents methods for converting the Trampoline kernel code into formal models for the model checker SPIN, a series of experiments using an incremental verification approach, and the use of embedded C constructs for performance improvement. The conversion methods include functional modularization and treatment for hardware‐dependent code, such as memory access for context switching. The incremental verification approach aims at increasing the level of confidence in the verification even when comprehensiveness cannot be provided because of the limitations of the hardware resource. We also report on potential safety issues found in the Trampoline operating system during the experiments and present experimental evidence of the performance improvement using the embedded C constructs in SPIN. Copyright © 2012 John Wiley & Sons, Ltd.