Design and verification of a coordination protocol for cooperating systems

 This paper proposes an approach to producing a verified design of a complex intelligent system. The system is modeled using a hierarchical structure based on a coordination protocol. The coordination protocol and the system architecture are described using a state machine representation. The Clarke-McMillan Symbolic Model Checker based on branching time temporal logic is used to verify some of the desired formal properties of the protocol such as completeness, boundedness and termination. This work shows that the model checker helps to bring the automatic verification of complex intelligent systems closer to a practical proposition.     

Safety verification and reachability analysis for hybrid systems

Safety verification and reachability analysis for hybrid systems is a very active research domain. Many approaches that seem quite different, have been proposed to solve this complex problem. This paper presents an overview of various approaches for autonomous, continuous-time hybrid systems and presents them with respect to basic problems related to verification.     

Compiling and verifying SC-SystemJ programs for safety-critical reactive systems

Most of today's embedded systems are very complex. These systems, controlled by computer programs, continuously interact with their physical environments through network of sensory input and output devices. Consequently, the operations of such embedded systems are highly reactive and concurrent. Since embedded systems are deployed in many safety-critical applications, where failures can lead to catastrophic events, an approach that combines mathematical logic and formal verification is employed in order to ensure correct behavior of the control algorithm. This paper presents What You Prove Is What You Execute (WYPIWYE) compilation strategy for a Globally Asynchronous Locally Synchronous (GALS) programming language called Safey-Critical SystemJ. SC-SystemJ is a safety-critical subset of the SystemJ language. A formal big-step transition semantics of SC-SystemJ is developed for compiling SC-SystemJ programs into propositional Linear Temporal Logic formulas. These LTL formulas are then converted into a network of Mealy automata using a novel and efficient compilation algorithm. The resultant Mealy automata have a straightforward syntactic translation into Promela code. The resultant Promela models can be used for verifying correctness properties via the SPIN model-checker. Finally there is a single translation procedure to compile both: Promela and C/Java code for execution, which satisfies the De-Bruijn index, i.e. this final translation step is simple enough that is can be manually verified.     

Coloured Petri Nets and CPN Tools for modelling and validation of concurrent systems

Coloured Petri Nets (CPNs) is a language for the modelling and validation of systems in which concurrency, communication, and synchronisation play a major role. Coloured Petri Nets is a discrete-event modelling language combining Petri nets with the functional programming language Standard ML. Petri nets provide the foundation of the graphical notation and the basic primitives for modelling concurrency, communication, and synchronisation. Standard ML provides the primitives for the definition of data types, describing data manipulation, and for creating compact and parameterisable models. A CPN model of a system is an executable model representing the states of the system and the events (transitions) that can cause the system to change state. The CPN language makes it possible to organise a model as a set of modules, and it includes a time concept for representing the time taken to execute events in the modelled system. CPN Tools is an industrial-strength computer tool for constructing and analysing CPN models. Using CPN Tools, it is possible to investigate the behaviour of the modelled system using simulation, to verify properties by means of state space methods and model checking, and to conduct simulation-based performance analysis. User interaction with CPN Tools is based on direct manipulation of the graphical representation of the CPN model using interaction techniques, such as tool palettes and marking menus. A license for CPN Tools can be obtained free of charge, also for commercial use.     

基于CPN TOOLS的网络协议建模与仿真技术研究

高级网的引入,大大增强了petri网的描述能力,但也导致了重复开发相似的仿真工具,造成了极大的浪费,不利于学术界的整体发展。有色petri网的仿真工具CPN Tools支持强大的元语言(ML),具有很强的扩展性。具有易于建模、易于仿真、易于分析的特点,并集成了较为强大的模型检验功能,如状态空间分析工具等。协议建模是对协议进行分析和研究的基础,CPN Tools的出现对于petri网建模与仿真具有重大的意义。     

Early verification and validation of mission critical systems

Complex software and systems are pervasive in today’s world. In a growing number of fields they come to play a critical role. In order to provide a high assurance level, verification and validation (V&V) should be considered early in the development process. This paper shows how this can be achieved based on a goal-oriented requirements engineering framework which combines complementary semi-formal and formal notations. This allows the analyst to formalize only when and where needed and also preserves optimal communication with stakeholders and developers. For the industrial application of the methodology, a supporting toolbox was developed. It consist of a number of tightly integrated tools for performing V&V tasks at requirements level. This is achieved through the use of (1) a roundtrip mapping between the requirements language and the specific formal languages used in the underlying formal tools (such as SAT or constraint solvers) and (2) graphical views using domain-based representations. This paper will focus on two major and representative tools: the Refinement Checker (about verification) and the Animator (about validation).     

Some advances in tools and algorithms for the construction and analysis of systems

Because of the complexity of software systems and their increasing criticality, there is a pressing need for sophisticated and highly automated tools for the analysis of software artifacts and their expected behavioral properties. A growing body of research is using formal methods to produce increasingly powerful and scalable analysis tools, although several challenges still remain. We briefly outline some recent achievements in automated analysis represented by four selected papers from the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2015). Two of the selected papers describe major achievements in the field of parallel model checking. The third paper presents an auto-active theorem prover for the verification of Eiffel programs. The fourth paper reports on a non-trivial case study with hybrid automata and interactive theorem proving techniques.     

Abstraction and composition: a verification method for co-operating systems

Behaviour of systems is described by formal languages: the sets of all sequences of actions. Regarding abstraction, alphabetic language homomorphisms are used to compute abstract behaviours. To avoid loss of important information when moving to the abstract level, abstracting homomorphisms have to satisfy a certain property called simplicity on the concrete (i.e. not abstracted) behaviour. To be suitable for verification of so called co-operating systems, a modified type of satisfaction relation for system properties (approximate satisfaction) is considered. The well known state space explosion problem is tackled by a compositional method formalized by so called co-operation products of formal languages.     

Verification and validation of safety applications based on PLCopen safety function blocks

Functional Safety is a major concern in the design of automation systems today. Many of those systems are realized using Programmable Logic Controllers (PLCs) programmed according to IEC 61131-3. PLCopen - as IEC 61131 user organization - semi-formally specified a set of software function blocks to be used in safety applications according to IEC 61508. In the presented work, formal models in the form of timed automata for the safety function blocks (SFBs) are constructed from the semi-formal specifications. The accordance of the formalized blocks to the specification is verified using model checking. Furthermore, their behaviour is validated against specified test cases by simulation. The resulting verified and validated library of formal models is used to build a formal model of a given safety application - built from SFBs - and to verify and validate its properties.     

Query-based verification of qualitative trends and oscillations in biochemical systems

We investigate the application of query-based verification to the analysis of behavioural trends of stochastic models of biochemical systems. We derive temporal logic properties which address specific behavioural questions, such as the likelihood for a species to reach a peak/deadlock state, or to exhibit monotonic/oscillatory trends. We introduce a specific modelling convention through which stochastic models of biochemical systems are made suitable to verification of the behavioural queries we define. Based on the queries we identify, we define a classification procedure which, given a stochastic model, allows for identifying meaningful qualitative behavioural trends. We illustrate the proposed query-based classification on a number of simple abstract models of biochemical systems.     

Boolean and Cartesian abstraction for model checking C programs

We show how to attack the problem of model checking a C program with recursive procedures using an abstraction that we formally define as the composition of the Boolean and the Cartesian abstractions. It is implemented through a source-to-source transformation into a Boolean C program; we give an algorithm to compute the transformation with a cost that is exponential in its theoretical worst-case complexity but feasible in practice.     

Formal and incremental construction of distributed algorithms: On the distributed reference counting algorithm

The development of distributed algorithms and, more generally, distributed systems, is a complex, delicate and challenging process. Refinement techniques of (system) models improve the process by using a proof assistant, and by applying a design methodology aimed at starting from the most abstract model and leading, in an incremental way, to the most concrete model, for producing a distributed solution. We show, using the distributed reference counting (DRC) problem as our study, how models can be produced in an elegant and progressive way, thanks to the refinement and how the final distributed algorithm is built starting from these models. The development is carried out within the framework of the event B method and models are validated with a proof assistant.     

Visual Basic编程中的错误捕获与处理

VisualBasic编程中的错误是不可避免的,应该在减少错误发生的同时,对可能发生的错误进行捕获和相应的处理,达到完善程序的目的。     

A survey of tools for the validation and verification of knowledge-based systems: 1985-1995

This paper presents the findings of a survey of software tools built to assist in the verification and validation of knowledge-based systems. The tools were identified from literature sources from the period 1985-1995. The tool builders were contacted and asked to complete and return a survey that identified which testing and analysis techniques were utilised and covered by their tool. From these survey results it is possible to identify trends in tool development, technique coverage and areas for future research.     

虚拟机下的Ubuntu安装VMware Tools与MPlayer的探究

Ubuntu有着独特的理念与自身优点,使其成为Linux系统新宠.通过虚拟机下的Ubuntu 8.04桌面系统.把VMware Tools与MPlayer的重要作用与安装过程进行详细地介绍.针对在安装过程中出现的常见问题提出相应的解决办法,并且解决了主机和客户机之间实现文件共享的问题.     

Numerical analysis of the reduction of linear systems into orthogonal canonical form

An efficient numerically stable computational algorithm for reduction of linear systems into orthogonal canonical form is described. The algorithm is based on QR decomposition with column pivoting. Exact error bounds and operation count for the algorithm are derived.     

Some algorithms for the construction of coordinated solutions in hierarchical distributed systems

Algorithms for constructing coordinated solutions in multilevel distributed systems are proposed. These algorithms utilize the nonformalizable knowledge of the decision maker about each subsystem and modify the set of feasible solutions of the local problems. Convergence of the proposed algoritms is proved.Translated from Kibernetika, No. 2, pp. 42–46, March–April, 1990.     

Pi-coefficient analysis of update algorithms for adaptive systems

This paper finds the appropriate pi-coefficients for a parameter estimation adaptive system and uses them to analyze the stability of two estimation algorithms. The estimation error dynamics of the system are modeled by a linear time-invariant subsystem and a nonlinear time-varying update law in a feedback loop. Then the so-called max-p problems are formulated and solved to obtain the pi-coefficients for the linear subsystem and nonlinear update low. For the investigated system, the quantitative results show that the least-squares update algorithm has larger stability range than that of the gradient algorithm, and the σ-modification scheme gives larger stability ranges for both algorithms.     

Uncertainty analysis of structural systems by perturbation techniques

The formulation of an efficient method to evaluate the uncertainty of the structural response by applying perturbation techniques is described. Structural random variables are defined by their mean values, standard deviations and correlations. The uncertainty of structural behaviour is evaluated by the covariance matrix of response according to the developed perturbation methodology. It is also presented the procedure used to implement this method in a structural finite element framework. The implemented computational program allows, in only one structural analysis, to evaluate the mean value and the standard deviation of the structural response, defined in terms of displacements or forces. The proposed method is exact for problems with linear design functions and normal-distributed random variables. Results remain accurate for non-linear design functions if they can be approximated by a linear combination of the basic random variables.     

正交试验在优化气体容积式流量计检定条件中应用

针对气体流量计检定影响因素较多的问题,以容积式气体流量计为例,提出以示值误差为优化综合指标,采用正交试验法分析检定过程中主要影响因素,包括温度、湿度、同轴度、取压方式等。确定各因素对示值误差影响的主次顺序,找出相对最优的检定条件。实验结果表明：采用正交试验方法优化检定条件方案具有可行性和有效性。