Using simulated annealing for computing test case-aware covering arrays

Official URL: http://192.168.1.20/record=b1558927 (Table of Contents)

Exhaustive testing of highly configurable software systems is generally infeasible in practice. For this reason, efficient sampling of the configuration space is important to improve the coverage of testing. A t-way covering array is a list of systematically selected configurations covering all value combinations for every t-way option combinations and it aims to discover faults caused by interactions of configuration options. Despite its many successes, it can be difficult to use covering arrays in practice. Once a traditional t-way covering array is constructed, the system is then tested by running its test cases in all the selected configurations. By doing so, traditional covering arrays assume that all test cases can run in all configurations of covering array. Recent studies, however, show that test cases of configurable systems are likely to have assumptions about the underlying configurations, i.e., they are like to have some test case-specific inter-option constraints. When a configuration does not satisfy the test casespecific constraints of a test case, that test case simply skips the configuration, which prevents the test case from testing all valid combinations of option settings appearing in the configuration an effect called a masking effect. A harmful consequence of masking effects is that they can make the developers to believe that they have tested certain option setting combinations while they in fact have not. A solution approach is to use test case-aware covering arrays a novel type of combinatorial objects for testing that has been recently introduced. Test case-aware covering arrays take test case-specific inter-option constraints into account when computing combinatorial interaction test suites, such that no masking effects caused by overlooked constraints occur. Given a configuration space model augmented with test case-specific constraints, a test case-aware covering array is not just a set of configurations as is the case in traditional covering arrays, but a set of configurations each of which is associated with a set of test cases, indicating the test cases scheduled to be executed in the configuration. Although it has been empirically demonstrated that test case-aware covering arrays, compared to traditional covering arrays, can significantly improve the quality of combinatorial interaction testing by avoiding masking e ects, there is no efficient and effective algorithms to compute them, except for a couple of proof-of-concept algorithms. We conjecture that this greatly hurts the adaptation of test case-aware covering arrays in practice. In this thesis, we have developed simulated annealing-based, efficient and effective algorithms to compute test case-aware covering arrays and a tool implementing these algorithms. We, furthermore, compare and contrast the performance of our algorithms by conducting large-scale experiments in which we used two highly configurable large software systems. The results of our empirical studies strongly suggest that the proposed algorithms are an efficient and effective way of computing test case-aware covering arrays and that they perform better than existing approaches.