Test case prioritization in highly-configurable systems

Abstract

Highly-configurable software systems (HCSs) provide a common core functionality and a set of optional features, where a feature represents an increment in system functionality. Development tools as Eclipse (with more than 3,000 plug-ins) or operating systems as Debian Wheezy (with more than 37,000 packages) have been reported as examples of HCSs. The large number of features that can be combined leading to thousands or even millions of individual software systems (a.k.a. configurations) makes the testing of HCSs a challenge. That is, testing every single configuration is too expensive in general. To overcome this problem, researchers have proposed numerous techniques mainly focused on reducing the space of testing to a manageable but representative subset of configurations to be tested. Nevertheless, even after reduce the test space, the number of configurations under test may still be large and expensive to run. In this dissertation, we address the testing of HCSs using test case prioritization, which schedules test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal, typically detect faults as quickly as possible. Test case prioritization approaches help to improve the effectiveness of testing allowing faster feedback to software testers and ensuring that test cases with the highest fault detection ability will have been executed if testing is stopped by any circumstance. Test case prioritization in HCSs can be driven by different functional and non–functional objectives, being an objective the order criterion used to accelerate the detection of faults. Functional prioritization objectives are based on the functional features of the system and their interactions. Non–functional prioritization objectives consider extra–functional information such as user preferences or cost. In this thesis we present thirteen objectives, techniques and tools for test case prioritization in HCSs. In particular, we define six objectives based on functional properties and seven objectives based on non–functional properties of the HCS under test. These objectives are evaluated using real data extracted from HCS Git repositories and bug tracking systems, which reinforces the validity of our conclusions. Regarding test case prioritization techniques, we present single–objective and multi-objective approaches based on evolutionary algorithms. Additionally, we report a comparison of 63 different com binations of up to three objectives to determine which combinations perform better in accelerating the detection of faults in an HCS. Furthermore, we propose an industrystrength HCS case study with more than 2 billions of configurations to be used as a realistic subject for further and reproducible validation of variability testing techniques. These contributions have been evaluated using extensive and rigorous experiments that reveal the efficacy and efficiency of our approach. Part of our contributions have been integrated into a tool called SmarTest for testing Drupal, a well-known web content management framework. SmarTest is a testing module that supports the analysis of the Drupal system to provide useful information to guide the testing. Also, it allows applying different prioritization testing techniques to reveals bugs faster in Drupal.