Generalised Stream X-Machines with Output Delimited Type

Some conditions relating to the automata involved in the W-testing method are discussed. It is also shown how to use the method for reduced automata instead of minimal automata. New design test conditions (weak output distinguishable, strong test-complete and output delimited type) are considered for the generalised stream X-machines (stream X-machines with basic functions replaced by relations and having as output strings of symbols rather than single symbols). It is proved that testing methods similar to those already developed for ordinary deterministic stream X-machines may be applied for generalised stream X-machines with output delimited types. A particular case of generalised stream X-machine with output delimited type is the X-machine with output delimiter, which produces outputs having a distinct right end character. Received October 2000 / Accepted in revised form January 2001     

Testing Conformance to a Quasi-Non-Deterministic Stream X-Machine

Stream X-machines have been used in order to specify a range of systems. One of the strengths of this approach is that, under certain well-defined conditions, it is possible to produce a finite test that is guaranteed to determine the correctness of the implementation under test (IUT). Initially only deterministic stream X-machines were considered in the literature. This is largely because the standard test algorithm relies on the stream X-machine being deterministic. More recently the problem of testing to determine whether the IUT is equivalent to a non-deterministic stream X-machine specification has been tackled. Since non-determinism can be important for specifications, this is an extremely useful extension. In many cases, however, we wish to test for a weaker notion of correctness called conformance. This paper considers a particular form of non-determinism, within stream X-machines, that will be called quasi-non-determinism. It then investigates the generation of tests that are guaranteed to determine whether the IUT conforms to a quasi-non-deterministic stream X-machine specification. The test generation algorithm given is a generalisation of that used for testing from a deterministic stream X-machine. Received November 1999 / Accepted in revised form December 2000     

Generalised Stream X-Machines and Cooperating Distributed Grammar Systems

Stream X-machines are a general and powerful computational model. By coupling the control structure of a stream X-machine with a set of formal grammars a new machine called a generalised stream X-machine with underlying distributed grammars, acting as a translator, is obtained. By introducing this new mechanism a hierarchy of computational models is provided. If the grammars are of a particular class, say regular or context-free, then finite sets are translated into finite sets, when ?k, = k derivation strategies are used, and regular or context-free sets, respectively, are obtained for ?k, * and terminal derivation strategies. In both cases, regular or context-free grammars, the regular sets are translated into non-context-free languages. Moreover, any language accepted by a Turing machine may be written as a translation of a regular set performed by a generalised stream X-machine with underlying distributed grammars based on context-free rules, under = k derivation strategy. On the other hand the languages generated by some classes of cooperating distributed grammar systems may be obtained as images of regular sets through some X-machines with underlying distributed grammars. Other relations of the families of languages computed by generalised stream X-machines with the families of languages generated by cooperating distributed grammar systems are established. At the end, an example dealing with the specification of a scanner system illustrates the use of the introduced mechanism as a formal specification model. Received September 1999 / Accepted in revised form October 2000     

Testing Conditions for Communicating Stream X-machine Systems

X-machines were proposed by Holcombe as a possible specification language and since then a number of further investigations have demonstrated that the model is intuitive and easy to use. In particular, stream X-machines (SXM), a particular class of X-machines, have been found to be extremely useful in practice. Furthermore, a method of testing systems specified as SXMs exists and is proved to detect all faults of the implementation provided that the system meets certain “design for test conditions”. Recently, a system of communicating SXMs was introduced as a means of modelling parallel processing. This paper proves that each communicating machine component can be transformed in a straightforward manner so that the entire system will behave like a single stream X-machine - the equivalent SXM of the system. The paper goes on to investigate the applicability of the SXM testing method to a system of communicating SXMs and identifies a class of communicating SXMs for which the equivalent SXM of the system meets the “design for test conditions”. Received November 1999 / Accepted in revised form June 2001     

Checking experiments for stream X-machines

Stream X-machines are a state based formalism that has associated with it a particular development process in which a system is built from trusted components. Testing thus essentially checks that these components have been combined in a correct manner and that the orders in which they can occur are consistent with the specification. Importantly, there are test generation methods that return a checking experiment: a test that is guaranteed to determine correctness as long as the implementation under test (IUT) is functionally equivalent to an unknown element of a given fault domain Ψ. Previous work has show how three methods for generating checking experiments from a finite state machine (FSM) can be adapted to testing from a stream X-machine. However, there are many other methods for generating checking experiments from an FSM and these have a variety of benefits that correspond to different testing scenarios. This paper shows how any method for generating a checking experiment from an FSM can be adapted to generate a checking experiment for testing an implementation against a stream X-machine. This is the case whether we are testing to check that the IUT is functionally equivalent to a specification or we are testing to check that every trace (input/output sequence) of the IUT is also a trace of a nondeterministic specification. Interestingly, this holds even if the fault domain Ψ used is not that traditionally associated with testing from a stream X-machine. The results also apply for both deterministic and nondeterministic implementations.     

Specification and testing using generalized machines: a presentation and a case study

Although testing is a major part of software development, it rarely gets the attention it deserves from researchers, partly because its foundations are weak and ill-understood. The principal purpose of testing is to detect (and then remove) faults in a software system. However, very few of the existing methods allow the tester to make any precise statement about the type or number of faults that remain undetected after testing is completed. In particular, none of the main techniques used by the software industry can give serious guarantees that a system is fault-free after testing has been completed. This paper advocates the use of a formal method both as a specification language and as the basis of a test data selection strategy. It presents a new method for generating test cases from this type of formal specification that provides a more convincing answer to the problem of detecting all faults in a software system. The method is reductionist in the sense that it guarantees that a system is fault-free provided that its components are fault-free; in turn, the same method could be used to test the resulting sub-systems, so the reduction will continue until the components considered are either known to be correct or are fairly simple pieces of code that can be successfully tested using traditional methods. The formal method used, X-machines, is a blend of finite state machines, data structures and processing functions and provides a simple and intuitive way of specifying computer systems. The use of X-machines as a specification tool and the testing method are illustrated with a case study. © 1998 John Wiley & Sons, Ltd.     

Editorial

Formal Aspects of Computing marks the end of the first year of our re-launched format. It has not been an easy year either for the editors or for the ever-patient staff at Springer-Verlag; but it has certainly been successful with first class papers being published soon after acceptance. As with most computing journals, refereeing poses a (potential) bottleneck to getting an author's ideas into print but even here our colleagues at Springer-Verlag have come up with an incentive scheme from which our future referees will benefit and hopefully speed the refereeing process to everyone's advantage. Recently, most editions of the journal have been standard issues with a number of submitted papers. It has been our stated intention since the journal began to have special editions with whole editions on a single topic. We are currently planning such a special edition to mark Rod Burstall's retirement (in fact we have so many excellent papers that there will probably have to be a double edition). This special issue collects a number of papers on X-machines edited by Mike Holcombe and myself. Mike has written a brief introduction and there follow five papers which have all been refereed by experts in the area (I took personal charge of having Mike's paper refereed). The generalisation of the testing theory to non-deterministic stream X-machines is the focus of two articles. Non-determinism can be generalised in several ways. R. Hierons and M. Harman look at quasi-non-deterministic machines and describe an approach to dealing with the generation of test sets for such machines. F. Ipate and M. Holcombe look at another way to view non-determinism and also focus on test set generation, the issue of fairness becomes important if the strong claims about fault detection by the test sets are to be achieved. M. Gheorghe has investigated how a collection of formal grammars can be controlled by a type of generalised stream X-machine so that the languages generated by such a system of grammars can be determined. He has shown that relatively simple grammars can generate very complex languages using this approach. T. Balanescu explores further generalisations of Stream X-machines and discusses how the design for test conditions can be adapted for a specific type of machine. A. Cowling et al. look at communicating X-machine systems and consider how this approach can be used to model message passing using a simple communicating matrix metaphor. Models built this way can be used to generate, automatically, concurrent programs. In a paper to appear in Volume 13, F. Ipate and M. Holcombe look at how the test theory can be adapted to apply to the communicating X-machines systems case. Indeed, Volume 13 already looks to be an exciting mix of scientific contributions – we also expect to back on a more regular publication schedule by the end of 2001.     

Testing timed systems modeled by Stream X-machines

Stream X-machines have been used to specify real systems where complex data structures. They are a variety of extended finite state machine where a shared memory is used to represent communications between the components of systems. In this paper we introduce an extension of the Stream X-machines formalism in order to specify systems that present temporal requirements. We add time in two different ways. First, we consider that (output) actions take time to be performed. Second, our formalism allows to specify timeouts. Timeouts represent the time a system can wait for the environment to react without changing its internal state. Since timeous affect the set of available actions of the system, a relation focusing on the functional behavior of systems, that is, the actions that they can perform, must explicitly take into account the possible timeouts. In this paper we also propose a formal testing methodology allowing to systematically test a system with respect to a specification. Finally, we introduce a test derivation algorithm. Given a specification, the derived test suite is sound and complete, that is, a system under test successfully passes the test suite if and only if this system conforms to the specification.     

A Structured Way to Use Channels for Communication in X-Machine Systems

This paper presents a new model for passing messages in communicating stream X-machine systems (CSXMS). The components are stream X-machines with ε-transitions, acting simultaneously. The states are partitioned into processing and communicating states. Passing messages between the X-machines involves only communicating states. A communication matrix is used as a common memory. It is shown that a structured way of using channels, namely via select constructs with guarded alternatives and terminate clause, may be implemented. An automatic scheme for writing concurrent programs in an Ada-like style, starting from a CSXMS, is proposed. Received December 1999 / Accepted in revised form January 2001     

Testing methods for X-machines: a review

The X-machine testing method has been developed as an application of the W-method to testing the control structure of an implementation, against a specification. The method was proven to demonstrate the equivalence of the behaviour of the two, subject to a number of conditions both a specification and an implementation are expected to satisfy, such as (1) determinism of the two and (2) that functions labelling arcs on a transition diagram of a specification control structure have been tested in advance. Since the original publication of the testing method, a number of extensions have been published, removing the restrictions mentioned above. This paper surveys the extensions of the X-machine testing method, for (1) testing of functions together with testing of a transition diagram, (2) equivalence testing of a non-deterministic implementation against a non-deterministic specification, (3) conformance testing of a deterministic implementation against a non-deterministic specification and (4) equivalence testing of a system of concurrently executing and communicating X-machines, against a specification. Received June 2004 Revised March 2005 Accepted March 2005 by J. Derrick, M. Harman and R. M. Herons     

A rigorous method for test templates generation from object-oriented specifications

This paper describes a rigorous method that investigates the suitability of formal specifications written in Object-Z specification language for testing object-oriented software implementation in a black-box fashion. The insight gained in the formalization of a model, the inherent abstractions, and formally specified intended behaviours and exceptions lead to the generation of test templates that are free from any implementation bias. The method described in this paper is an extension of the one proposed by Stocks and Carrington. In particular, the focus of the paper is on generating test templates for composite operations in an Object-Z specification. The method is illustrated using the specification for an electronic mail system. The specification and the test templates generated for the electronic mail system show several interesting properties of the application that require considerable attention during testing. Copyright © 2001 John Wiley & Sons, Ltd.     

Complete deterministic stream X-machine testing

One of the strengths of using stream X-machines to specify a system is that, under certain well defined conditions, it is possible to produce a test set that is guaranteed to determine the correctness of an implementation. However, the existing method assumes that the implementation of each processing function is proved to be correct before the actual testing can take place, so it only test the system integration. This paper presents a new method for generating test sets from a deterministic stream X-machine specification that generalises the existing integration testing method. This method no longer requires the implementations of the processing functions to be proved correct prior to the actual testing. Instead, the testing of the processing functions is performed along with the integration testing.Accepted in revised form 27 February 2004 by D.A. Duce     

Generating Conformance Tests for Nondeterministic Protocol Machines

We present a method of generating test cases from the software specifications which are modeled by nondeterministic finite state machines.It is applicable to both nondeterministic and deterministic finite state machines.When applied to deterministic machines,this method yields usually smaller test suites with full fault coverage than the existing methods that also assure full fault coverage.In particular,the proposed method can be used to test the control portion of software specified in the formal specification languages SDL or ESTELLE.     

TORC: test plan optimization by requirements clustering

Acceptance testing is a time-consuming task for complex software systems that have to fulfill a large number of requirements. To reduce this effort, we have developed a widely automated method for deriving test plans from requirements that are expressed in natural language. It consists of three stages: annotation, clustering, and test plan specification. The general idea is to exploit redundancies and implicit relationships in requirements specifications. Multi-viewpoint techniques based on RM-ODP (Reference Model for Open Distributed Processing) are employed for specifying the requirements. We then use linguistic analysis techniques, requirements clustering algorithms, and pattern-based requirements collection to reduce the total effort of testing against the requirements specification. In particular, we use linguistic analysis for extracting and annotating the actor, process and object of a requirements statement. During clustering, a similarity function is computed as a measure for the overlap of requirements. In the test plan specification stage, our approach provides capabilities for semi-automatically deriving test plans and acceptance criteria from the clustered informal textual requirements. Two patterns are applied to compute a suitable order of test activities. The generated test plans consist of a sequence of test steps and asserts that are executed or checked in the given order. We also present the supporting prototype tool TORC, which is available open source. For the evaluation of the approach, we have conducted a case study in the field of acceptance testing of a national electronic identification system. In summary, we report on lessons learned how linguistic analysis and clustering techniques can help testers in understanding the relations between requirements and for improving test planning.     

Structuring formal specifications—a lesson relearned

Specifications written in the formal specification language Z often make use of a form of decomposition that is novel to programmers. A published Z specification is rewritten using the form of decomposition familiar to programmers. Whenever decomposition is used, there must be some strategy for deciding what is to go in one component and what is to go in another. At the highest level, the strategy underlying the rewritten specification is the well-known strategy of separating user interface issues from deeper system functionality issues. The effectiveness of the strategy is put to a simple test by showing how a modification to the interface can be supported by a modification to only part of the specification. The conclusions drawn are that care over decomposition is important in specifications, just as it is in programs, and that lessons learned from programming about effective decomposition strategies can be applicable at the specification level, too. In particular, the lesson relearned is that it is important to separate information about a system's functionality from information about how this functionality is presented to users.     

Process simulation and refinement

In this paper we deal with the problem of (nondeterministic and parallel) process refinement. The basic notion of refinement is defined via the improved failure semantics of CSP [BHR84, BrR85, Hoa85, Ros88]. The concept of simulation of Communicating Systems introduced in [Mil80, Par81] is generalised and proved to be sound for the correctness of refinement. A Galois connection is presented to show that up-simulation and down-simulation together provide a complete proof method. The paper also suggests that simulation can be employed to derive an implementation from a specification.     

Automating test by adding formal specification: an experience for database bound applications

This article describes a method and a generalised tool for the automatic generation of functional testcases. The test generator is part of a more comprehensive product that also includes an interpreter which is able to determine the expected results of the generated tests. The study starts from the functional specifications of a software product, based on a traditional development model, and provides a system decomposition methodology. A general formal way to describe functional specification is given, obtaining the criteria to follow in choosing the language to produce functional tests. The general approach, the tool structure and some examples are shown in this article.