Research On Combinatorial Testing And Its Fault Detection Ability

Combinatorial testing(CT)is a potentially powerful testing method to detect soft-ware failures triggered by parameters and their interactions.Since its idea was sketched more than thirty years ago,the literature on CT has contributed a wide variety of theories and techniques;its application is also gradually accepted by industry partners.How-ever,there are also challenges in CT that ask for new and creative solutions.On one hand,the effectiveness of CT is highly dependent on its test suite generation and optimi-sation techniques,whereas there remains huge room for improving current search based test suite generation,and the crucial switching cost has not been well accounted in pri-oritisation studies.On the other hand,there has clearly insufficient understandings on the performance of CT,especially when real-world faults are involved.Consequently,more research endeavours are needed for further promotion and application of CT.In order to apply CT in a more effective and practical manner,in this dissertation we propose search based combinatorial testing,aiming to use search based algorithms to solve the important but complex CT test suite generation and prioritisation problems.Meanwhile,we investigate the relative performance of CT under different test scenar-ios,thus suggestions on the choices of CT are provided for practising testers.The main contribution of this dissertation is summarised as follows:1.Regarding test suite(covering array)generation,we propose a new discrete particle swam(PSO)optimisation algorithm DPSO,and develop guidelines for algorithm parameter settings by systematical parameter tuning.DPSO utilises set and proba-bility theories to develop a new representation scheme for particle's velocity as well as refining the related evolution operators.As the results,the search space of DPSO is adapted to covering array generation,thus overcoming the potential substantial source of errors when the conventional(continuous space)PSO is applied.The ex-perimental results reveal that parameter tuning helps to generate smaller covering arrays in 57%of cases;DPSO significantly improves conventional PSO in 74%of cases,and also improves PSO variants and other search based algorithm.DPSO is a promising improvement on PSO for covering array generation.2.Regarding test suite prioritisation,we formalise the concept of switching cost be-tween adjacent test cases,and identify the optimal testing order in the presence of switching cost.The switching cost depicts the effort of re-configuring the environ-ment for running subsequent test cases.To find the testing order that can detect interaction triggered faults earlier,we develop six optimisation methods,including single-objective,hybrid and multi-objective,to do test suite prioritisation.These algorithms are compared under 400 simulated and 8 real-world test models.The experimental results reveal that the search based algorithm for travelling salesman problem is the best candidate to minimise the switching cost.But to achieve the highest rate of fault detection,the hybrid and multi-object algorithms that balance combination coverage and testing cost are more preferable.3.Regarding the effectiveness of CT,we empirically compare combinatorial(CT),random(RT)and adaptive random(ART)testing under different test scenarios.This is the first to account for the(more realistic)testing setting in which the tester may not have complete information about the parameters and constraints that pertain to the system,and to account for the challenge posed by different faults characterised by their failure rates.This study is conducted on nine real-world programs under a total of 1683 test scenarios.The experimental results show significant differences in the techniques‘fault detection ability when failure rate is relatively low.CT is no worse than any other in 98%of scenarios.ART enhances RT,and is comparable to CT in 96%of scenarios,but its execution cost can be up to 3.5 times higher than CT when the program is highly constrained.When constraint information is unavailable,RT is more cost-effective,otherwise,CT or ART is recommended.