A LOTOS based tutorial on formal methods for object-oriented distributed systems

The majority of formal methods for distributed systems have their origins in the 1980’s and were targeted at the early generations of distributed systems. However, modern distributed systems have new features not found in the early systems, e.g. they areobject-oriented, havemobile components, aretime sensitive and are constructed according to advanced system development architectures, e.g.viewpoints models. A major topic of current research is thus, how to enhance the existing formal techniques in order to support these new features. This paper gives a tutorial level review of this research area. We particularly focus on the process algebra LOTOS and consider how the technique can be reconciled with these new features. Howard Bowman, Ph.D.: He is a lecturer in the Computing Laboratory at the University of Kent at Canterbury. He received his Ph.D. from Lancaster University in 1991. His research focuses on applying formal techniques to the construction of distributed systems and he is a grant holder for a number of projects in this area. He is on the editorial board of the journal New Generation Computing and on the programme committees of a number of conferences, including, FORTE/PSTV. He was the programme co-chair of FMOODS’97, the IFIP conference on Formal Methods for Open Object Based Distributed Systems.     

Modular specification and verification of object-oriented programs

A method for modular specification and verification using the ideas of subtype and normal type is presented. The method corresponds to informal techniques used by object-oriented programmers. The key idea is that objects of a subtype must behave like objects of that type's supertypes. An example program is used to show the reasoning problems that supertype abstraction may cause and how the method resolves them. Subtype polymorphism is addressed, and specification and verification update is discussed. A set of syntactic and semantic constraints on subtype relationships, which formalize the intuition that each object of a subtype must behave like some object of each of its supertypes, is examined. These constraints are the key to the soundness of the method. To state them precisely, a formal model of abstract type specifications is used     

Comparison of specification decomposition methods in Event-B

Decomposition is an important phase in the design of medium and large-scale systems. Various architectures of software systems and decomposition methods are studied in numerous publications. Presently, formal specifications of software systems are mainly used for experimental purposes; for this reason, their size and complexity are relatively low. As a result, in the development of a nontrivial specification, different approaches to the decomposition should be compared and the most suitable approach should be chosen. In this paper, the experience gained in the deductive verification of the formal specification of the mandatory entity-role model of access and information flows control in Linux (MROSL DP-model) using the formal Event-B method and stepwise refinement technique is analyzed. Two approaches to the refinementbased decomposition of specifications are compared and the sources and features of the complexity of the architecture of the model are investigated.     

A formal approach to object-oriented databases

Object-oriented database systems are the focus of current research and development efforts. Yet, there is no commonly accepted object model, nor is it clear whether such a model can be developed. This paper reports on efforts to develop a formal framework that contains most features found in current object oriented database systems. The framework contains two parts. The first is a structural object model, including concepts such as structured objects, identity, and some form of inheritance. For this model, we explain the distinction between values and (abstract) objects, describe a system as a directed graph, and discuss declarative languages. The second part deals with higher-order concepts, such as classes and functions as data, methods, and inheritance. This part is a sketch, and leaves many issues unresolved. Throughout the paper, the emphasis is on logic-oriented modeling.     

A purely object-oriented approach for rule-based paradigms

In this paper, I describe an approach for rule-based systems exploiting a purely object-oriented approach. The innovative idea is to consider a new kind of relation between knowledge objects which are believed to model implication relations of production rules. A knowledge base consisting of such objects can be conveniently represented as a Marker Propagating Graph (MPG), which provides rule-based-like representation features. The inference is seen as a marking propagation through the graph. This approach preserves the best of both the object orientation features and expert system functionality. This experimental study concerns the design and the implementation of a medical system for automatic interpretation of biological tests in Preventive Medicine Centers. Because the use of such a system is planned for many years, the possibilities for its future extensions are seriously considered. This would not be possible without a good appreciation of object orientation features.     

Using a formal specification contractually

A commonly made criticism of formal methods is that they increase costs. Selective use of formal methods to define critical requirements can, however, lead to a significant decrease in lifecycle costs. In particular the economic and technical benefits of outsourcing the development of software can be fully realized and the cost of outsourcing slightly reduced by use of a formal specification. In this paper we describe a development in which a formal specification prepared by the customer formed part of the contract with the supplier. We conclude that this use of a formal specification can reduce risks and costs for all concerned and can help foster fruitful and co-operative relations in situations which are often fraught with confrontation.Published with the permission of the controller of Her Britannic Majesty's Stationery Office.     

Applying formal specification in industry

Industrial software developers confront a bewildering array of software engineering techniques, each with its own promised benefits. The authors introduced formal methods into the specification and modeling activities of a security-critical system's development. They gauged the methods' effectiveness by comparing the results of the group that used them with those of the group that did not. They present their results in this paper     

The formal specification of ORN semantics

Object Relationship Notation (ORN) is a declarative scheme that permits a variety of common types of relationships to be conveniently defined to a Database Management System (DBMS), thereby allowing the DBMS to automatically enforce their semantics. Though first proposed for object DBMSs, ORN is applicable to any data model that represents binary entity-relationships or to any DBMS that implements them. In this paper, we first describe ORN semantics informally as has been done in previous papers. We then provide a formal specification of these semantics using the Z-notation. Specifying ORN semantics via formal methods gives ORN a solid mathematical foundation. The semantics are defined in the context of an abstract database of sets and relations in a recursive manner that is precise, unambiguous, and noncircular.     

Software monitoring through formal specification animation

This paper presents a formal specification-based software monitoring approach that can dynamically and continuously monitor the behaviors of a target system and explicitly recognize undesirable behaviors in the implementation with respect to its formal specification. The key idea of our approach is in building a monitoring module that connects a specification animator with a program debugger. The requirements information about expected dynamic behaviors of the target system are gathered from the formal specification animator, while the actual behaviors of concrete implementations of the target system are obtained through the program debugger. Based on the information obtained from both sides, the judgement on the conformance of the concrete implementation with respect to the formal specification is made timely while the target system is running. Furthermore, the proposed formal specification-based software monitoring technique does not embed any instrumentation codes to the target system nor does it annotate the target system with any formal specifications. It can detect implementation errors in a real-time manner, and help the developers and users of the system to react to the problems before critical failure occurs.     

Object-oriented specification and formal verification of real-time systems

An object-oriented approach for specification and verification of real-time systems is described in this paper. It is motivated by taking advantage of object-oriented techniques to produce real-time software that is easy to understand, maintain, and reuse. The approach specifies the structural, behavioral, and control aspects of objects in one model with a textual representation as well as a graphical representation. For ease to comprehend and use, the model encapsulates object states and allows an analyst to focus on specifying object operations one at a time. System behavior from individual objects can be deduced and analyzed. For safety considerations, the approach supports specification of failures to object behavior and their resultant faults. The approach also supports modeling of timed temporal constraints for specifying and verifying desirable real-time properties. An object timed temporal logic OTTL is defined for expressing the syntax and semantics of these constraints. Decision procedures for their verification are also presented.     

Integration of informal and formal development of object-oriented safety-critical software

The KeY system allows for the integrated informal and formal development of object-oriented Java software. In this paper we report on a major industrial case study involving safety-critical software for the computation of a particular kind of railway timetable used by train conductors. Our case study includes formal specification of requirements both on the analysis and the implementation level. Particular emphasis in our research is placed on the challenge to make authoring and maintenance of formal specifications easier. We demonstrate that the technique of specification patterns as implemented in KeY for the language OCL yields significant improvements.     

安全应用系统的形式化规范与求精过程研究

形式化方法是提高系统安全等级必不可少的保障技术。然而,由于诸多原因,它在安全应用系统开发过程中的应用尚不普及。本文将以Z语言为依托,以Mondex电子钱包系统为范例,探讨形式化方法在安全应用系统开发过程中的应用方法和过程。     

Towards formal specification of a distributed computing system

Onboard spacecraft computing system is a case of a functionally distributed system that requires continuous interaction among the nodes to control the operations at different nodes. A simple and reliable protocol is desired for such an application. This paper discusses a formal approach to specify the computing system with respect to some important issues encountered in the design and development of a protocol for the onboard distributed system. The issues considered in this paper are concurrency, exclusiveness and sequencing relationships among the various processes at different nodes. A 6-tuple model is developed for the precise specification of the system. The model also enables us to check the consistency of specification and deadlock caused due to improper specification. An example is given to illustrate the use of the proposed methodology for a typical spacecraft configuration. Although the theory is motivated by a specific application the same may be applied to other distributed computing system such as those encountered in process control industries, power plant control and other similar environments.     

基于UML的形式化规范说明研究

软件的规范说明阶段 ( specification phase)对于软件的整体开发过程来说是一个非常重要的阶段 ,UML方法是目前比较流行的软件工程开发方法 ,它对软件整体开发过程提供了一套有用的模型。本文根据 UML和谓词转换 ,提出一种面向对象的形式化规范说明方法 ,并给出一组和 UML相对应的数学模型。本文的方法吸收了 UML和一般形式化方法的优点 ,具有数学的严谨性和精确性 ,并且更加易于理解和表达。     

Exploring the ERTMS/ETCS full moving block specification: an experience with formal methods

International Journal on Software Tools for Technology Transfer - Shift2Rail is a joint undertaking funded by the EU via its Horizon 2020 program and by main railway stakeholders. Several...     

The influence of formal representation on solution specification

The effectiveness and value of a notation is determined by how well its users are able to work with it. This paper reports upon an empirical study aiming at investigating the influence of employing the Z specification notation upon how users approach system development. The study illustrates how the desire to employ formality can have a significant influence upon preferred choice between different solution approaches. Despite the formal representation increasing the awareness of the characteristics of a given design problem, the notation is apparently detrimental in the subjects' consideration of good-quality generic solutions. The human factor issues of the notation need to be carefully considered and the notation should be embedded into a proper method if effective use is to be achieved.