2021
Ferrer, Javier; Chicano, Francisco; Ortega-Toro, José Antonio
CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines Journal Article
In: Journal of Heuristics, vol. 27, no. 1-2, pp. 229–249, 2021, ISSN: 1381-1231.
Abstract | Links | BibTeX | Tags: CMSA, Combinatorial optimization, Feature Models, Hybrid algorithms, Integer programming, Matheuristics, Software Product Lines
@article{Ferrer2021,
title = {CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines},
author = {Javier Ferrer and Francisco Chicano and José Antonio Ortega-Toro},
url = {http://link.springer.com/10.1007/s10732-020-09462-w},
doi = {10.1007/s10732-020-09462-w},
issn = {1381-1231},
year = {2021},
date = {2021-04-01},
journal = {Journal of Heuristics},
volume = {27},
number = {1-2},
pages = {229--249},
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 = {CMSA, Combinatorial optimization, Feature Models, Hybrid algorithms, Integer programming, Matheuristics, Software Product Lines},
pubstate = {published},
tppubtype = {article}
}
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.
2017
Ferrer, Javier; Chicano, Francisco; Alba, Enrique
Hybrid algorithms based on integer programming for the search of prioritized test data in software product lines Inproceedings
In: Squillero, Giovanni; Sim, Kevin (Ed.): Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 3–19, Springer International Publishing, Cham, 2017, ISSN: 16113349.
Abstract | Links | BibTeX | Tags: Combinatorial Interaction Testing, Feature Models, Integer linear programming, Integer nonlinear programming, Pairwise Testing, prioritization, Software Product Lines
@inproceedings{Ferrer2017,
title = {Hybrid algorithms based on integer programming for the search of prioritized test data in software product lines},
author = {Javier Ferrer and Francisco Chicano and Enrique Alba},
editor = {Giovanni Squillero and Kevin Sim},
url = {http://dx.doi.org/10.1007/978-3-319-55792-2_1},
doi = {10.1007/978-3-319-55792-2_1},
issn = {16113349},
year = {2017},
date = {2017-01-01},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
volume = {10200 LNCS},
pages = {3--19},
publisher = {Springer International Publishing},
address = {Cham},
abstract = {In Software Product Lines (SPLs) it is not possible, in general, to test all products of the family. The number of products denoted by a SPL is very high due to the combinatorial explosion of features. For this reason, some coverage criteria have been proposed which try to test at least all feature interactions without the necessity to test all products, e.g., all pairs of features (pairwise coverage). In addition, it is desirable to first test products composed by a set of priority features. This problem is known as the Prioritized Pairwise Test Data Generation Problem. In this work we propose two hybrid algorithms using Integer Programming (IP) to generate a prioritized test suite. The first one is based on an integer linear formulation and the second one is based on a integer quadratic (nonlinear) formulation. We compare these techniques with two state-of- the-art algorithms, the Parallel Prioritized Genetic Solver (PPGS) and a greedy algorithm called prioritized-ICPL. Our study reveals that our hybrid nonlinear approach is clearly the best in both, solution quality and computation time. Moreover, the nonlinear variant (the fastest one) is 27 and 42 times faster than PPGS in the two groups of instances analyzed in this work. © Springer International Publishing AG 2017.},
keywords = {Combinatorial Interaction Testing, Feature Models, Integer linear programming, Integer nonlinear programming, Pairwise Testing, prioritization, Software Product Lines},
pubstate = {published},
tppubtype = {inproceedings}
}
In Software Product Lines (SPLs) it is not possible, in general, to test all products of the family. The number of products denoted by a SPL is very high due to the combinatorial explosion of features. For this reason, some coverage criteria have been proposed which try to test at least all feature interactions without the necessity to test all products, e.g., all pairs of features (pairwise coverage). In addition, it is desirable to first test products composed by a set of priority features. This problem is known as the Prioritized Pairwise Test Data Generation Problem. In this work we propose two hybrid algorithms using Integer Programming (IP) to generate a prioritized test suite. The first one is based on an integer linear formulation and the second one is based on a integer quadratic (nonlinear) formulation. We compare these techniques with two state-of- the-art algorithms, the Parallel Prioritized Genetic Solver (PPGS) and a greedy algorithm called prioritized-ICPL. Our study reveals that our hybrid nonlinear approach is clearly the best in both, solution quality and computation time. Moreover, the nonlinear variant (the fastest one) is 27 and 42 times faster than PPGS in the two groups of instances analyzed in this work. © Springer International Publishing AG 2017.
2016
Lopez-Herrejon, Roberto E; Ferrer, Javier; Chicano, Francisco; Egyed, Alexander; Alba, Enrique
Evolutionary Computation for Software Product Line Testing: An Overview and Open Challenges Incollection
In: Studies in Computational Intelligence, vol. 617, pp. 59–87, 2016, ISSN: 1860949X.
Abstract | Links | BibTeX | Tags: Feature Models, Feature set, Product line testing, Reverse engineering, search based software engineering, Software Product Lines, Variability modeling
@incollection{Lopez-Herrejon2016,
title = {Evolutionary Computation for Software Product Line Testing: An Overview and Open Challenges},
author = {Roberto E Lopez-Herrejon and Javier Ferrer and Francisco Chicano and Alexander Egyed and Enrique Alba},
url = {http://link.springer.com/10.1007/978-3-319-25964-2_4},
doi = {10.1007/978-3-319-25964-2_4},
issn = {1860949X},
year = {2016},
date = {2016-01-01},
booktitle = {Studies in Computational Intelligence},
volume = {617},
pages = {59--87},
abstract = {textcopyright Springer International Publishing Switzerland 2016. Because of economical, technological and marketing reasons today's software systems are more frequently being built as families where each product variant implements a different combination of features. Software families are commonly called Software Product Lines (SPLs) and over the past three decades have been the subject of extensive research and application. Among the benefits of SPLs are: increased software reuse, faster and easier product customization, and reduced time to market. However, testing SPLs is specially challenging as the number of product variants is usually large making it infeasible to test every single variant. In recent years there has been an increasing interest in applying evolutionary computation techniques for SPL testing. In this chapter, we provide a concise overview of the state of the art and practice in SPL testing with evolutionary techniques as well as to highlight open questions and areas for future research.},
keywords = {Feature Models, Feature set, Product line testing, Reverse engineering, search based software engineering, Software Product Lines, Variability modeling},
pubstate = {published},
tppubtype = {incollection}
}
textcopyright Springer International Publishing Switzerland 2016. Because of economical, technological and marketing reasons today's software systems are more frequently being built as families where each product variant implements a different combination of features. Software families are commonly called Software Product Lines (SPLs) and over the past three decades have been the subject of extensive research and application. Among the benefits of SPLs are: increased software reuse, faster and easier product customization, and reduced time to market. However, testing SPLs is specially challenging as the number of product variants is usually large making it infeasible to test every single variant. In recent years there has been an increasing interest in applying evolutionary computation techniques for SPL testing. In this chapter, we provide a concise overview of the state of the art and practice in SPL testing with evolutionary techniques as well as to highlight open questions and areas for future research.
2014
Lopez-Herrejon, Roberto Erick; Ferrer, Javier Javier; Chicano, Francisco; Haslinger, Evelyn Nicole; Egyed, Alexander; Alba, Enrique; Ferrer, Javier; Chicano, Francisco; Haslinger, Evelyn Nicole; Egyed, Alexander; Alba, Enrique
A Parallel Evolutionary Algorithm for Prioritized Pairwise Testing of Software Product Lines Inproceedings
In: Genetic and Evolutionary Computation Conference (GECCO'14), pp. 1255–1262, 2014, ISBN: 9781450326629.
Abstract | Links | BibTeX | Tags: Combinatorial Interaction Testing, Feature Models, Pairwise Testing, Software Product Lines
@inproceedings{Lopez-Herrejon2014b,
title = {A Parallel Evolutionary Algorithm for Prioritized Pairwise Testing of Software Product Lines},
author = {Roberto Erick Lopez-Herrejon and Javier {Javier Ferrer} and Francisco Chicano and Evelyn Nicole Haslinger and Alexander Egyed and Enrique Alba and Javier Ferrer and Francisco Chicano and Evelyn Nicole Haslinger and Alexander Egyed and Enrique Alba},
url = {http://apps.webofknowledge.com.offcampus.ozyegin.edu.tr:2048/full_record.do?product=UA&search_mode=GeneralSearch&qid=1&SID=S1BBM4vYnmigGrZakJ3&page=1&doc=10&cacheurlFromRightClick=no},
doi = {10.1145/2576768.2598305},
isbn = {9781450326629},
year = {2014},
date = {2014-01-01},
booktitle = {Genetic and Evolutionary Computation Conference (GECCO'14)},
pages = {1255--1262},
abstract = {Software Product Lines (SPLs) are families of related software systems, which provide di ff erent feature combinations. Di ff erent SPL testing approaches have been proposed. However, despite the extensive and successful use of evolutionary computation techniques for software testing, their application to SPL testing remains largely unexplored. In this paper we present the Parallel Prioritized product line Genetic Solver (PPGS), a parallel genetic algorithm for the generation of prioritized pairwise testing suites for SPLs. We perform an extensive and comprehensive analysis of PPGS with 235 feature models from a wide range of number of features and products, using 3 di ff erent priority assignment schemes and 5 product prioritization selection strategies. We also compare PPGS with the greedy algorithm prioritized-ICPL. Our study reveals that overall PPGS obtains smaller covering arrays with an acceptable performance di ff erence with prioritized-ICPL.},
keywords = {Combinatorial Interaction Testing, Feature Models, Pairwise Testing, Software Product Lines},
pubstate = {published},
tppubtype = {inproceedings}
}
Software Product Lines (SPLs) are families of related software systems, which provide di ff erent feature combinations. Di ff erent SPL testing approaches have been proposed. However, despite the extensive and successful use of evolutionary computation techniques for software testing, their application to SPL testing remains largely unexplored. In this paper we present the Parallel Prioritized product line Genetic Solver (PPGS), a parallel genetic algorithm for the generation of prioritized pairwise testing suites for SPLs. We perform an extensive and comprehensive analysis of PPGS with 235 feature models from a wide range of number of features and products, using 3 di ff erent priority assignment schemes and 5 product prioritization selection strategies. We also compare PPGS with the greedy algorithm prioritized-ICPL. Our study reveals that overall PPGS obtains smaller covering arrays with an acceptable performance di ff erence with prioritized-ICPL.
2013
Lopez-Herrejon, Roberto E; Chicano, Francisco; Ferrer, Javier; Egyed, Alexander; Alba, Enrique
Multi-objective Optimal Test Suite Computation for Software Product Line Pairwise Testing Inproceedings
In: IEEE International Conference on Software Maintenance, pp. 404–407, 2013, ISSN: 1063-6773.
Abstract | Links | BibTeX | Tags: Multi-objective optimization, Pairwise Testing, Software Product Lines
@inproceedings{Lopez-Herrejon2013,
title = {Multi-objective Optimal Test Suite Computation for Software Product Line Pairwise Testing},
author = {Roberto E Lopez-Herrejon and Francisco Chicano and Javier Ferrer and Alexander Egyed and Enrique Alba},
url = {http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6676918 http://neo.lcc.uma.es/staff/javi/files/icsm2013.pdf http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6676918},
doi = {10.1109/ICSM.2013.58},
issn = {1063-6773},
year = {2013},
date = {2013-09-01},
booktitle = {IEEE International Conference on Software Maintenance},
pages = {404--407},
abstract = {Software Product Lines (SPLs) are families of related software products, which usually provide a large number of feature combinations, a fact that poses a unique set of challenges for software testing. Recently, many SPL testing approaches have been proposed, among them pair wise combinatorial techniques that aim at selecting products to test based on the pairs of feature combinations such products provide. These approaches regard SPL testing as an optimization problem where either coverage (maximize) or test suite size (minimize) are considered as the main optimization objective. Instead, we take a multi-objective view where the two objectives are equally important. In this exploratory paper we propose a zero-one mathematical linear program for solving the multi-objective problem and present an algorithm to compute the true Pareto front, hence an optimal solution, from the feature model of a SPL. The evaluation with 118 feature models revealed an interesting trade-off between reducing the number of constraints in the linear program and the runtime which opens up several venues for future research.},
keywords = {Multi-objective optimization, Pairwise Testing, Software Product Lines},
pubstate = {published},
tppubtype = {inproceedings}
}
Software Product Lines (SPLs) are families of related software products, which usually provide a large number of feature combinations, a fact that poses a unique set of challenges for software testing. Recently, many SPL testing approaches have been proposed, among them pair wise combinatorial techniques that aim at selecting products to test based on the pairs of feature combinations such products provide. These approaches regard SPL testing as an optimization problem where either coverage (maximize) or test suite size (minimize) are considered as the main optimization objective. Instead, we take a multi-objective view where the two objectives are equally important. In this exploratory paper we propose a zero-one mathematical linear program for solving the multi-objective problem and present an algorithm to compute the true Pareto front, hence an optimal solution, from the feature model of a SPL. The evaluation with 118 feature models revealed an interesting trade-off between reducing the number of constraints in the linear program and the runtime which opens up several venues for future research.