An Empirical Comparison of t-GSC and ACO_TCSP Applied to Time Bound Test Selection

Background: Test case selection is a highly researched and inevitable software testing activity. Various kinds of optimization approaches are being used for solving the test selection and prioritization problem. Greedy approach and search based techniques have already been applied to address test case selection. A greedy approach to solve set cover problem is proposed to find a minimal test suite that is able to detect maximum faults. Search based approximation technique - Ant Colony Optimization reduces and prioritizes the test suite to form an optimized test suite. Time bound test case prioritization is an NP-complete problem. Mutation testing is used to inculcate known faults into the programs under test to generate effective test cases. Objective: To empirically evaluate the performance of a greedy approach and a search based approach for test case selection. Methods: This paper attempts to compare a search based approximation approach against a time sensitive greedy approach for test suite optimization using mutation testing. The proposed greedy approach for yielding optimized test suite within a time bound environment is implemented in Python. The two techniques used, search based and greedy approach have also been empirically compared on 24 programs in different languages (C, C#, and Java and Python). Results: The greedy approach has shown better complexity over the ACO approach and the same is validated by experimentation using the actual run time of the algorithms. The time bound greedy approach yielded best result for 16 out of the 24 programs. The ACO approach could find the best result 100% times for 11 programs and at least 30-95% times for rest 13 programs by running ACO 10 times on each program. Yet the percentage reductions achieved in the size and execution time of the resultant test suite were almost similar in both the techniques. Conclusion: The results inspire the further use of both the techniques in software testing.