Formal Analysis of the Probability of Interaction Fault Detection Using Random Testing
IEEE Transactions on Software Engineering 38(5):1088-1099
Modern systems are becoming highly configurable to satisfy the varying needs of customers and users. Software product lines are hence becoming a common trend in software development to reduce cost by enabling systematic, large scale reuse. However, high levels of configurability entail new challenges. Some faults might be revealed only if a particular combination of features is selected in the delivered products. But testing all combinations is usually not feasible in practice, due to their extremely large numbers. Combinatorial testing is a technique to generate smaller test suites for which all combinations of t features are guaranteed to be tested. In this paper, we formally prove that, when there are no constraints among the features that can be part of a product, then random testing is much more effective than expected at detecting feature interaction faults when compared with combinatorial testing. More importantly, this trend gets even stronger as the number of features increases and converges towards equal effectiveness. Given that combinatorial testing entails significant computational overhead in the presence of many features, the results suggest that random testing may outperform combinatorial testing in large systems. However, when constraints are present among features, then random testing can fare much worse than combinatorial testing. As a result, we claim that research effort should focus on improving combinatorial testing in the presence of feature constraints in order to have a practical impact.