Towards a New Extension Relation for Compositional Test Case Generation for CSP Concurrent Processes

Abstract:Software concurrent systems such as electronic financial services are very popular today. Rigorous testing of such systems is indispensable. Nevertheless, the state-explosion problem, in which the size of a system grows exponentially with the number of concurrent components, is a severe obstacle to the generation of test cases.
 
In this study, we propose a new relationship assuring the conformities of test cases for concurrent systems. We stipulate it in Communicating Sequential Processes (CSP), which is an excellent tool to study concurrent systems. Specification of concurrent systems is expressed as processes that are composed sequentially and concurrently. Our proposal supports both abstraction and process composition.
 
This approach decomposes a given process into sequential compositions of component processes. Each component can be anti-extended into abstract forms. Sequential and concurrent combinations of abstract forms can substitute their corresponding extending components in a process to form aggregated abstract forms. Since the given processes, components and abstract forms are all processes, this approach can be applied recursively and compositionally. We prove that these aggregated abstract processes should be anti-extensions of the corresponding processes under a few necessary and sufficient conditions. Hence, test cases generated from these processes will be conformance test cases for the implementations.
 
We examine three major testing relations (conformance, extension and reduction) from the point of view of their ability to support abstraction. Extension and reduction are special kinds of conformance, which are partially ordered. However, only extension from a specification can provide abstract forms that guarantee to be conformed by an implementation of the specification. Extension is further investigated to support the compositional approach. We identify five weaknesses of extension, which we call problems of preceding, succeeding, prefix, decomposition and paralleling. Each will result in non-conforming abstraction.
 
To resolve the identified weaknesses of extension in a compositional and abstraction- oriented approach, we formulate σ-extension and identify the necessary and sufficient conditions. We also discuss a restricted sub-class of process specification so that these conditions can easily be satisfied. In the restricted sub-class, successful terminations of processes are deterministic.
 
Under these conditions, we achieve a few desirable properties. First, both preceding and succeeding components of a given sequential composition can be anti-extended. The given composition should extend the sequential composition of its corresponding anti-extended processes. Secondly, a given parallel composition whose concurrent components are sequential compositions should extend a parallel composition of anti-extensions of preceding components of corresponding sequential compositions, followed by a parallel composition of anti-extensions of corresponding succeeding components. Furthermore, a given sequential composition should σ-extend the preceding component of a resultant sequential composition. We also illustrate the generation of test cases and discuss possible enhancements.
 
In conclusion, this study achieves three important aims:
(i) we identify extension as a superior tool for abstraction over conformance and reduction from the testing perspective, and identify its weaknesses in compositional approach;
(ii) we propose an abstraction-oriented and compositional approach to test case generation; and
(iii) we recommend a restricted sub-class of CSP specification that can utilize our results easily.
Grants:HKU 7033/99E, HKU 7029/01E, ITF UIM/77
Links:PDF
Citation:W.K. Chan, Towards a New Extension Relation for Compositional Test Case Generation for CSP Concurrent Processes, Ph.D. Thesis, The University of Hong Kong (2004).
Remarks:-
Related Papers:-

Selected Tags

Tag Groups

Links

ACM SigSoft
IEEE Software Engineering Online