CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines
- PDF / 734,542 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 184 Views
CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines Javier Ferrer1
· Francisco Chicano1 · José Antonio Ortega-Toro2
Received: 15 December 2018 / Revised: 29 September 2020 / Accepted: 23 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In Software Product Lines, it may be difficult or even impossible to test all the products of the family because of the large number of valid feature combinations that may exist (Ferrer et al. in: Squillero, Sim (eds) EvoApps 2017, LNCS 10200, Springer, The Netherlands, pp 3–19, 2017). Thus, we want to find a minimal subset of the product family that allows us to test all these possible combinations (pairwise). Furthermore, when testing a single product is a great effort, it is desirable to first test products composed of a set of priority features. This problem is called Prioritized Pairwise Test Data Generation Problem. State-of-the-art algorithms based on Integer Linear Programming for this problem are faster enough for small and medium instances. However, there exists some real instances that are too large to be computed with these algorithms in a reasonable time because of the exponential growth of the number of candidate solutions. Also, these heuristics not always lead us to the best solutions. In this work we propose a new approach based on a hybrid metaheuristic algorithm called Construct, Merge, Solve & Adapt. We compare this matheuristic with four algorithms: a Hybrid algorithm based on Integer Linear Programming, a Hybrid algorithm based on Integer Nonlinear Programming, the Parallel Prioritized Genetic Solver, and a greedy algorithm called prioritized-ICPL. The analysis reveals that CMSA is statistically significantly better in terms of quality of solutions in most of the instances and for most levels of weighted coverage, although it requires more execution time. Keywords Matheuristics · CMSA · Integer programming · Software product lines · Hybrid algorithms · Combinatorial optimization · Feature models
B
Javier Ferrer [email protected] Francisco Chicano [email protected] José Antonio Ortega-Toro [email protected]
1
ITIS Software, Universidad de Málaga, Málaga, Spain
2
VirusTotal, Málaga, Spain
123
J. Ferrer et al.
1 Introduction Software Product Lines (SPLs) are used to achieve a more efficient software development and management of the variability of software products, reducing the costs and time to market, as well as maintenance costs (Pohl et al. 2005). These product lines carry a great variability within products of the same family of products. This variability is due to the mass customization and it implies a great challenge when we face the task of testing because of the combinatorial explosion in the number of products (Engström and Runeson 2011). Many proposals have arisen having into account these difficulties (Cohen et al. 2008). Some of these are based on pairwise testing (Lopez-Herrejon et al. 2013; Oster et al. 2010; Perrouin et al. 2012), w
Data Loading...
