Software component interaction testing: Coverage measurement and generation of configurations

Systems constructed from components, including distributed systems, consist of a number of elements that interact with each other. When a system is integrated, there may be undesired interactions among those components that cause system failures.; There are two complementary problems in testing a software system. The first problem is to create a test suite, given a description of the expected behaviour of a system configuration. The second problem is to deal with a large number of distinct test configurations. We investigate the second problem in this thesis: the situation when there are various system parameters, each of which can take on a value from a discrete set.; The trade-off that the system tester faces is the thoroughness of test configuration coverage, versus availability of limited resources. We introduce a coverage measure that can provide a basis for determining a set of configurations with “sufficient” coverage, or for evaluation of a set of test configurations that already exists.; This thesis addresses the problem of testing interactions among components of a software system: the “interaction test coverage” problem. We formally define this problem, and give it a set-theoretic framework. This is done through the introduction of an “interaction element,” which becomes the unit of test coverage. The problem is compared to, and distinguished from, the minimum set cover problem and the {lcub}0,1{rcub} integer programming problem. As a result, the status of the NP-completeness of this problem remains open.; Methods from statistical experimental design are introduced, and applied to the problem of generating a set of configurations that achieve coverage of all pair-wise combinations of parameter values. We present a fast, deterministic algorithm to generate such a set of test configurations. The method is compared with other methods, and shown to produce fewer configurations in most situations. The number of configurations generated is logarithmic in the number of parameters, and polynomial in the number of values per parameter. As a result, the number of configurations is usually feasible in practice, and is a significant reduction from the number of possible configurations.