Compositional Comparison of Formal Software Specifications Using Transformation Systems

In a model-based software systems development formal specifications of the components of the system are developed. Thereby different specifications are used to represent the different aspects or views of the components, possibly following different paradigms. These heterogeneous viewpoint specifications have to be integrated in order to obtain a consistent global specification of the whole system. In this paper transformation systems are introduced as a common semantic domain where specifications written in different languages can be interpreted and formally compared. A transformation system is a transition system where the transitions are labelled by sets of actions and the states are labelled by algebras representing the data states. Development relations and composition operations for transformation systems are investigated, and it is shown that compatible local developments of components induce a global development of their composition. As an application two specifications of the alternating bit protocol are formally compared component-wise, one given in the process calculus CCS, the other one in the parallel programming language UNITY. Received September 2000 / Accepted in revised form June 2001     

Enabling metrology-oriented specification of geometrical variability – A categorical approach

In this paper a metrology-oriented specification schema is proposed to enrich the specification semantics with sufficient metrological information. It is designed particularly for applications where non-traditional measurement methods are applied; and it can also identify any redundancies, inconsistencies or incompletenesses of a specification. The proposed schema is based on category theoretical semantics which uses category theory as the foundation to model the semantics. A set of verification operations that derived from the measurement process was firstly formalised using the categorical semantics. Then a set of full faithful functors were constructed to map the set of verification operations to a set of specification operations. A set of simplification rules was then developed to deduce all of the necessary specification objects which are independent to each other. Then the residual specification objects provide a compact structure of the specification. Three test cases were conducted to validate the proposed schema. An industrial computed tomography (CT) measurement process for an impeller manufacturing using selective laser sintering (SLS) technique, was modelled and a set of independent specification elements was then deduced. The other two test cases for checking redundancy and incompleteness on general ISO specifications were carried out. The results show that the proposed schema works for proposing semantic enriched specification that are characterised by non-traditional measurement methods and for testing redundancy and incompleteness of specifications based on geometrical product specifications and verification (GPS) standards system.     

A Case Study on Applying a Tool for Automated System Analysis Based on Modular Specifications Written in TRIO

An effective means for analyzing and reasoning on software systems is to use formal specifications to simulate their execution. The simulation traces can be used for specification testing and reused for functional testing of the system later in the development process. It is widely acknowledged that, to deal with the complexity of industrial-size systems, specifications must be structured into modules providing abstraction mechanisms and clear interfaces. In our past work, we defined and implemented a method for simulating specifications written in the TRIO temporal logic language, and applied it to functional testing of time-critical industrial systems. In the present paper, we report on a case study with a tool that analyzes TRIO specifications by taking advantage of their modular structure, so as to overcome the well-known state-explosion problem and make the proposed method really scalable. We discuss the fundamental operations and the algorithms on which the tool is based. Then, we illustrate its use in a realistic case study, inspired from an industrial application. Finally, we comment on the overall results in terms of usability of the tool and effectiveness of the approach, and we outline future improvements.     

A Methodology for Constructing User-Oriented Requirements Specifications for Large-Scale Systems Using Electronic Hypermedia

requirements specifications are developed for large-scale systems, the final specification is usually an abstraction of the original requirements data into a text-based form that is often foreign to end-users. A method was developed for representing requirements through use of electronic multimedia. The resulting specification is capable of representing requirements and requirements data in a manner that is more representative of the real-world problem space than traditional specifications. This paper presents a method for incorporating multimedia exhibits, notably the results of rapid prototyping activities and animated simulation, into a requirements specification for large-scale C2I systems. To examine the effectiveness of the method, a multimedia requirements specification was developed based on an existing text specification for a real-world system. An experiment was also performed that showed the product of the methodology to be effective in increasing the understandability of the specification over that obtained from the text specification alone.     

基于Petri网的统一知识表示模型

本文讨论知识表示的Ｐｅｔｒｉ网模型。将多种知识分类表示，对于开发具有较宽领域知识的系统具有重要意义。本文从统一的观点出发，在给出了Ｐｅｔｒｉ网的代数规范说明后，将三种主要的知识表示方法分别与Ｐｅｔｒｉ网模型之间建立映射系统，这三种知识表示方法为：逻辑表示法，语义网络和产生式系统。     

Requirements specification of real-time systems: temporal parameters and timing-constraints

The development of high-quality real-time systems depends on their correct requirements specification, which includes the analysis and specification of timing issues. This paper focuses on requirements specification of real-time systems, presenting a set of temporal parameters and timing-constraints related to the execution of systems processes. Timing-constraints are expressed by formulas, being useful for defining, representing, and validating the system temporal behavior, particularly in hard real-time systems specifications. The primary contribution over previous studies is the proposal of a more generic and complete set of timing-constraints, applied to the area of requirements engineering for real-time systems, which has not been sufficiently explored.     

On constructing communication protocols from component-based service specifications

Constructing communication protocols from component service specifications, each of which specifies a subfunction of the target protocol, enables efficient development of a large and complex communication protocol. Concerning this construction, related techniques have been already proposed: integration of component protocol specifications into a single protocol specification and transformation of service specifications to protocol specifications. However, the integration needs special knowledge of communication protocols, and the transformation requires that a large and complex service specification should be developed as input to produce the target protocol. In order to cope with these problems, this paper proposes a new method which at first integrates component service specifications into a single service specification, and then transforms the service specification into the target protocol by a protocol synthesis technique. The most important point of view is that component integration is performed at the service specification level rather than the protocol specification level. Additionally, we define a class of ‘well-formed’ service specification which ensures correctness of the target protocol. As a result, the integration and transformation can be efficiently executed in small state space without special knowledge of communication protocols. Finally, we have shown the effectiveness of the proposed method by constructing a part of the real-life OSI protocol FTAM.     

Development graphs—Proof management for structured specifications

Development graphs are a tool for dealing with structured specifications in a formal program development in order to ease the management of change and reusing proofs. In this work, we extend development graphs with hiding (e.g. hidden operations). Hiding is a particularly difficult to realize operation, since it does not admit such a good decomposition of the involved specifications as other structuring operations do. We develop both a semantics and proof rules for development graphs with hiding. The rules are proven to be sound, and also complete relative to an oracle for conservative extensions. We also show that an absolutely complete set of rules cannot exist.The whole framework is developed in a way independent of the underlying logical system (and thus also does not prescribe the nature of the parts of a specification that may be hidden). We also show how various other logic independent specification formalisms can be mapped into development graphs; thus, development graphs can serve as a kernel formalism for management of proofs and of change.     

Layered specifications to support reusability and integrability

Building systems by integrating components and building systems by reusing components are but two sides of the same coin. In both cases one faces the problem of producing systems out of prefabricated parts, either parts which have been designed for a different environment than the one they will be used in now, or parts which have been designed for a yet undefined target system.This situation differs from classical software design situations. It demands that in parts engineering as well as in systems engineering, certain interface decisions are postponed to a rather late point in time. This is only permissible, though, if other aspects are very precisely specified. Having the right model of specification of both, the target (system) and source (component) will substantially aid the retrieval and integration problem.This article argues for a layered approach towards system specification. It will show, how relational specifications will help system designers not to bind themselves too early into premature decisions and how designs aiming for heavy reuse can grow by stepwise enriching specifications.     

Using units of measurement in formal specifications

In the physical sciences and engineering, units of measurement provide a valuable aid to both the exposition and comprehension of physical systems. In addition, they provide an error checking facility comparable to static type checking commonly found with programming languages. It is argued that units of measurement can provide similar benefits in the specification and design of software and computer systems.To demonstrate this, we present an extension of the Z specification notation with support for the incorporation of units in specifications and demonstrate the feasibility of static dimensional analysis of the resulting language.     

A Functional Rephrasing of the Assumption/Commitment Specification Style

The assumption/commitment (also called rely/guarantee) style has been advocated for the specification of interactive components of distributed systems. It suggests the structuring of specifications into assumptions about the behavior of the component's environment and into commitments that are fulfilled by the component, provided the environment fulfills these assumptions. One of its motivations is to achieve modularity (also called compositionality) for state transition specifications of system components. Another reason for writing specifications in this format lies in proof rules that refer to this format. We define the assumption/commitment formats for functional system specifications. In particular, we work out a canonical decomposition of system specifications following the assumption/commitment format into safety and liveness aspects. We demonstrate the format of assumption/commitment specifications by a number of examples. Finally, we discuss the methodological significance of the assumption/commitment format in the stepwise development of specifications.     

Overlaps in Requirements Engineering

Although overlap between specifications—that is the incorporation of elements which designate common aspects of the system of concern—is a precondition for specification inconsistency, it has only been a side concern in requirements engineering research. This paper is concerned with overlaps. It defines overlap relations in terms of specification interpretations, identifies properties of these relations which are derived from the proposed definition, shows how overlaps may affect the detection of inconsistency; shows how specifications could be rewritten to reflect overlap relations and still be amenable to consistency checking using theorem proving; analyses various methods that have been proposed for identifying overlaps with respect to the proposed definition; and outlines directions for future research.     

Making Workflow Change Acceptable

Virtual professional communities are supported by network information systems composed from standard Internet tools. To satisfy the interests of all community members, a user-driven approach to requirements engineering is proposed that produces not only meaningful but also acceptable specifications. This approach is especially suited for workflow systems that support partially structured, evolving work processes. To ensure the acceptability, social norms must guide the specification process. The RENISYS specification method is introduced, which facilitates this process using composition norms as formal representations of social norms. Conceptual graph theory is used to represent four categories of knowledge definitions: type definitions, state definitions, action norms and composition norms. It is shown how the composition norms guide the legitimate user-driven specification process by analysing a case on the development of an electronic law journal.     

线性混成系统的参数分析

针对线性混成系统中存在的一类典型未知参数问题,如实时系统的验证通常局限于给定矍体数值,未考虑系统中任何时间参数或物理特征参数的计算等,给出了具体的计算过程,实例应用表明,该计算过程可以有效地求解线性混成系统中这类未知参数,并能保证系统按照规约的要求正确运行。     

Logical Object as a Basis of Knowledge Based Systems

This paper presents a framework called logical knowledge object (LKO),which is taken as a basis of the dependable development of knowledge based systems(KBSs).LKO combines logic programming and object-oriented programming paradigms,where objects are viewed as abstractions with states,constraints,behaviors and inheritance.The operational semantics defined in the style of natural semantics is simple and clear.A hybrid knowledge representation amalgamating rule,frame,semantic network and blackboard is available for both most structured and flat knowledge.The management of knowledge bases has been formally specified.Accordingly,LKO is well suited for the formal representation of knowledge and requirements of KBSs.Based on the framework,verification techniques are also explored to enhance the analysis of requirement specifications and the validation of KBSs.In addition,LKO provides a methodology for the development of KBSs,applying the concepts of rapid prototyping and top-down design to deal with changing and incomplete requirements,and to provide multiple abstract models of the domain,where formal methods might be used at each abstract level.     

非线性代数规范的直接实现技术

代数规范是支持软件规格说明和设计的一种有效的方法，代数规范的直接实现技术是该研究领域的一个主要分支，目前这方面的研究基本上局限于线性代数规范，本文介绍一个实现非线性代数规范的转换过程，从该过程可自然是导出针对不同程序设计语言的转换系统，我们已实现了一个基于Ｐａｓｃａｌ语言的转换系统。     

A safe regression testing approach for safety critical systems

Regression testing is important activity during the software maintenance to deal with adverse effects of changes. Our approach is important for safety critical system as usually formal methods are preferred and highly recommended for the safety critical systems but they are also applied for the systems development of other than critical system. Our approach is based on Regression testing using VDM++ which takes two VDM++ specifications, one baseline and other delta (Changed) along with test suite for the baseline version. It compares both versions by using comparator module, identifies the change. By analyzing the change we classify the test cases from original test suite into obsolete, re-testable, and reusable test cases. Our scope is at unit level i.e. at class level. Our approach gets two versions of VDM++ specification and returns regression test suite for the delta version. Our approach distinguishes test cases which are still effective for the delta version of VDM++ specification and it differs from re-test all strategy as it can distinguish the test cases and identifies test cases which are useful for delta version. Test cases reusability and test case reduction is the main objective of our approach. Our approach presents how to perform regression testing using VDM++ specification during the maintenance of systems.     

Data structures and program correctness: Bridging the gap

An assertion language for data structures is presented, leading to the following results: formal semantics of operations on data structures are given in terms of the weakest precondition formula for assignment statements; input/output specifications for data-structure manipulating algorithms can be stated with precision; there is a clear relationship between the output specification and intermediate assertions; and knowledge about standard types of data structures can be schematized. These ideas are illustrated on an algorithm to reverse the arcs on a one-way linked list, and on a threaded tree example.