On the Application of SAT Solvers to the Test Suite Minimization Problem - Arito, Franco; Chicano-García, José-Francisco; Alba-Torres, Enrique (My University, 2014)
The Test Suite Minimization problem in regression testing is a software engineering problem which consists in selecting a set of test cases from a large test suite that satisfies a given condition, like maximizing the coverage and/or minimizing the oracle cost. In this work we use an approach based on SAT solvers to find optimal solutions for the Test Suite Minimization Problem. The approach comprises two translations: from the original problem instance into Pseudo-Boolean constraints and then to a propositional Boolean formula. In order to solve a problem, we first translate it into a SAT instance. Then the SAT instance is solved using a state-of-the-art SAT solver. Our main contributions are: we create an encoding for single and multi-objective formulations of the Test Suite Minimization Problem as Pseudo-Boolean constraints and we compute optimal solutions for well-known and highly-used instances of this problem for future reference.
Arito, F., Chicano F., & Alba E. (2012). On the Application of SAT Solvers to the Test Suite Minimization Problem. (Fraser, G., & de Souza J. Teixeira, Ed.).Search Based Software Engineering - 4th International Symposium, {SSBSE} 2012, Riva del Garda, Italy, September 28-30, 2012. Proceedings. 45–59.
Keywords: Ingeniería del software; Test suite minimization; Satisfiability problem; Multi-objective optimization