An Empirical Study of Greedy Test Suite Minimization Techniques Using Mutation Coverage

Abstract

Test suite minimization is the task of finding a smaller test suite that still fulfills the properties of the original test suite but which comprises fewer test cases. It is important in practice, especially in the context of regression testing, where test suites are re-executed. However, test suite minimization as a set covering problem is known as an NP-complete problem, which requires applications of heuristics. Although many test suite minimization techniques have been applied previously but obtained conflicting results primarily due to inherent differences in underlying programming languages and experimental setup. In this respect, we study traditional greedy-based algorithms for test suite minimization that allow to remove test cases in a way such that the reduced test suite satisfies all requirements. Specifically, we evaluated commonly discussed approaches on publicly available JavaScript applications using mutation coverage. We show that the discussed algorithms reduce the test suite size of the studied example programs on average to 70% without compromising the fault-detection capability of the original test suite. The suggested approach not only minimizes the test suite’s size, thereby reducing the regression testing cost, but also ensures that the reduced test suite catches the same number of faults as that of the original test suite. Further, we also examine their performance in scenarios when meeting all testing requirements is not feasible due to time and budget constraints.

Keywords

• Test suite minimization
• mutation testing
• regression testing
• JavaScript