No abstract available.

This extended abstract takes advantage of a theory of software testing based on formal specifications to point out the benefits and limits of the use of formal methods to this end. A notion of exhaustive test set is defined according to the semantics of the formal notation, the considered conformance relation, and some testability hypotheses on the system under test. This gives a framework for the formalisation of test selection, test execution, and oracles, and, moreover, leads to the explicitation of those hypotheses underlying test selection strategies, such as uniformity hypotheses or regularity hypotheses. This explicitation provides some guides to complementary proofs, or tests, or instrumentations of the system under test. This approach has been applied to various formalisms: axiomatic specifications of data types, model-based specifications, process algebras, transition systems, etc. It provides some guiding principles for the development of testing methods given a formal specification notation and an associated conformance/refinement relation. It is at the origin of the development of some test environments based on SMT solvers and theorem provers.

Context: The demand from industry for more dependable and scalable test-development mechanisms has fostered the use of formal models to guide the generation of tests.Despite many advancements having been obtained with state-based models, such as Finite State Machines (FSMs) and Input/Output Transition Systems (IOTSs), more advanced formalisms are required to specify large, state-rich, concurrent systems.Circus, a state-rich process algebra combining Z, CSP and a refinement calculus, is suitable for this; however, deriving tests from such models is accordingly more challenging.Recently, a testing theory has been stated for Circus, allowing the verification of process refinement based on exhaustive test sets.Objective: We investigate fault-based testing for refinement from Circus specifications using mutation.We seek the benefits of such techniques in test-set quality assertion and fault-based test-case selection.We target results relevant not only for Circus, but to any process algebra for refinement that combines CSP with a data language.Method: We present a formal definition for fault-based test sets, extending the Circus testing theory, and an extensive study of mutation operators for Circus.Using these results, we propose an approach to generate tests to kill mutants.Finally, we explain how prototype tool support can be obtained with the implementation of a mutant generator, a translator from Circus to CSP, and a refinement checker for CSP, and with a more sophisticated chain of tools that support the use of symbolic tests.Results: We formally characterise mutation testing for Circus, defining the exhaustive test sets that can kill a given mutant.We also provide a technique to select tests from these sets based on specification traces of the mutants.Finally, we present mutation operators that consider faults related to both reactive and data manipulation behaviour.Altogether, we define a new fault-based test-generation technique for Circus.Conclusion: We conclude that mutation testing for Circus can truly aid making test generation from state-rich model more tractable, by focussing on particular faults.

Path-biased random testing is an interesting alternative to classical path-based approaches faced to the explosion of the number of paths, and to the weak structural coverage of random methods based on the input domain only. Given a graph representation of the system under test a probability distribution on paths of a certain length is computed and then used for drawing paths. A limitation of this approach, similarly to other methods based on symbolic execution and static analysis, is the existence of infeasible paths that often leads to a lot of unexploitable drawings. We present a prototype for pruning some infeasible paths, thus eliminating useless drawings. It is based on graph transformations that have been proved to preserve the actual behaviour of the program. It is driven by symbolic execution and heuristics that use detection of subsumptions and the abstract-check-refine paradigm. The approach is illustrated on some detailed examples.

Theories for model-based testing identify exhaustive test sets: typically infinite sets of tests whose execution establishes the conformance relation of interest. Practical techniques rely on selection strategies to identify finite subsets of these tests, and popular approaches are based on requirements to cover the model. In previous work, we have defined testing theories for refinement-based process algebra, namely, CSP and Circus, a state-rich process algebra. In this paper, we consider the selection of tests designed to establish traces refinement. In this case, conformance does not require that all traces of the model are available in the system under test, and this can raise challenges regarding coverage criteria for selection. To address these difficulties, we present a framework for formalising a variety of selection strategies. We exemplify its use in the formalisation of a selection criterion based on coverage of process communications for integration testing. We consider models written in Circus, whose symbolic testing theory facilitates the definition of uniformity and regularity hypotheses based on data operations, but also imposes extra challenges for selection of concrete tests. Our results, however, are relevant for any formalism where the conformance relation does not require all the traces of the specification to be executable by the system under test.

No abstract available.

This paper addresses the problem of selecting finite test sets and automating this selection. Among these methods, some are deterministic and some are statistical. The kind of statistical testing we consider has been inspired by the work of Thevenod-Fosse and Waeselynck. There, the choice of the distribution on the input domain is guided by the structure of the program or the form of its specification. In the present paper, we describe a new generic method for performing statistical testing according to any given graphical description of the behavior of the system under test. This method can be fully automated. Its main originality is that it exploits recent results and tools in combinatorics, precisely in the area of random generation of combinatorial structures. Uniform random generation routines are used for drawing paths from the set of execution paths or traces of the system under test. Then a constraint resolution step is performed, aiming to design a set of test data that activate the generated paths. This approach applies to a number of classical coverage criteria. Moreover, we show how linear programming techniques may help to improve the quality of test, i.e. the probabilities for the elements to be covered by the test process. The paper presents the method in its generality. Then, in the last section, experimental results on applying it to structural statistical software testing are reported.

Deriving test cases from formal specifications of communicating processes has been studied for awhile. Several methods have been proposed for specifications based on FSM (Finite State Machines), LTS (Labelled Transition Systems), IOTS (Input Output Transition Systems), etc. However, most approaches are limited to a finite set of actions, excluding the possibility of communicating typed values between processes. This article presents a test derivation and selection method based on a model of communicating processes with inputs, outputs and data types, which is closer to actual implementations of communication protocols.

We propose a novel way of automating statistical structural testing of software, based on the combination of uniform generation of combinatorial structures, and of randomized constraint solving techniques. More precisely, we show how to draw test cases which balance the coverage of program structures according to structural testing criteria. The control flow graph is formalized as a combinatorial structure specification. This provides a way of uniformly drawing execution paths which have suitable properties. Once a path has been drawn, the predicate characterizing those inputs which lead to its execution is solved using a constraint solving library. The constraint solver is enriched with powerful heuristics in order to deal with resolution failures and random choice strategies.

In this article we report on the development of a group-communication service using the formal specification language LOTOS, and present our experience in using publicly available tools for this purpose. The service implements atomic broadcast through a Two-Phase-Commit protocol, providing at-least-once delivery semantics and with no restriction on message delivery order. First we wrote an informal specification describing the desired properties from the service, the interfaces with the underlying network layer and the upper user layer, and the protocol to be used by the service. Then we developed the formal specification of the protocol in LOTOS. After validating the formal specification and thus having a certain confidence in its adequacy with respect to the informal specification, we derived test cases from the formal specification and implemented the service using the Concert/C distributed programming language. While testing the implementation, we found that most errors were related to unspecified features or bugs in the execution environment. From this experience, we draw our conclusions on the usefulness of software development based on formal techniques. Copyright © 1999 John Wiley & Sons, Ltd.

Abstract. There is now a lot of interest in program testing based on formal specifications. However, most the works in this area focus on one formalized aspect of the software under test. For instance, some previous works of the first author consider abstract data type specifications. Other works are based on behavioural descriptions, such as finite state machines or finite labelled transition systems. This paper begins by brie y recalling the principles of test data selection from algebraic data types specifications. Then, it transposes them to basic and full LOTOS. Finally it exploits this uniform framework and suggests a new integrated approach to test derivation from full LOTOS specifications, where both behavioural properties and data types properties are taken into account when dealing with processes.

We present an algebraic specification language (PLUSS) and a program construction method. Programs are built systematically from an algebraic specification of the data they deal with. The method was tested on a realistic problem (part of a telephone switching system). In these experiments, it turned out that error handling was the difficult part to specify and to program. This paper shows how to cope with this problem at the specification level and during the program development process.