Nemo: Multi-Criteria Test-Suite Minimization with Integer Nonlinear Programming

Multi-criteria test-suite minimization aims to remove redundant test cases from a test suite based on some criteria such as code coverage, while trying to optimally maintain the capability of the reduced suite based on other criteria such as fault-detection effectiveness. Existing techniques addressing this problem with integer linear programming claim to produce optimal solutions. However, the multi-criteria test-suite minimization problem is inherently nonlinear, due to the fact that test cases are often dependent on each other in terms of test-case criteria. In this paper, we propose a framework that formulates the multi-criteria test-suite minimization problem as an integer nonlinear programming problem. To solve this problem optimally, we programmatically transform this nonlinear problem into a linear one and then solve the problem using modern linear solvers. We have implemented our framework as a tool, called Nemo, that supports a number of modern linear and nonlinear solvers. We have evaluated Nemo with a publicly available dataset and minimization problems involving multiple criteria including statement coverage, fault-revealing capability, and test execution time. The experimental results show that Nemo can be used to efficiently find an optimal solution for multi-criteria test-suite minimization problems with modern solvers, and the optimal solutions outperform the suboptimal ones by up to 164.29% in terms of the criteria considered in the problem.

Approach Overview

Nemo takes test-related data and a configuration as input. Test-related data includes the original test suite and the corresponding coverage data such as statement and fault coverage of the test suite. In the configuration file, users can specify the optimization and constraint criteria. Users can also specify which approaches should be used in the minimization of the test suite. The Formulator component takes the input and expresses the minimization problem as an integer programming problem. Formulator is capable of representing the problem as either linear or nonlinear, as well as transforming the nonlinear formulation into a linear form. The output model can then be fed into external solvers to compute the solution. For now our tool supports lp and ampl formats, which many modern solvers, such as lp_solve, CPLEX and Couenne use. Once the solution for the encoded problem is computed, the Generator component produces the minimized test suite in various formats for presentation to the user. Currently, our tool handles solutions generated by the aforementioned solvers and web services using those solvers, such as the NEOS Server and DropSolve. The proposed tool is the only one of its kind to formulate and consider the inherent nonlinearity of the MCTSM problem.

[Nemo overview picture]

Using Nemo in Action

Download Nemo here.

Publications

More details about Nemo can be found in our publication:

[seal's logo]
[uci's logo]