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.
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.
Ferrer, Javier; Garcia-Nieto, Jose; Alba, Enrique; Chicano, Francisco
Validación Inteligente para la Sincronización de Semáforos Basada en Feature Models Inproceedings
In: IX Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB'13), 2013.
Abstract | Links | BibTeX | Tags: Metaheurísticas, Modelos de Características, Pairwise Testing, Priorización, Semáforos, Testing Funcional, Tráfico - Regulación - Automatización
@inproceedings{Ferrer2013,
title = {Validación Inteligente para la Sincronización de Semáforos Basada en Feature Models},
author = {Javier Ferrer and Jose Garcia-Nieto and Enrique Alba and Francisco Chicano},
url = {http://riuma.uma.es/xmlui/handle/10630/5634},
year = {2013},
date = {2013-01-01},
booktitle = {IX Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados (MAEB'13)},
abstract = {Ministerio de Economía y Competitividad y FEDER: TIN2011-28194, BES-2012-055967 y BES-2009-018767},
keywords = {Metaheurísticas, Modelos de Características, Pairwise Testing, Priorización, Semáforos, Testing Funcional, Tráfico - Regulación - Automatización},
pubstate = {published},
tppubtype = {inproceedings}
}
Ministerio de Economía y Competitividad y FEDER: TIN2011-28194, BES-2012-055967 y BES-2009-018767