research-article

CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines

Authors:

Francisco Chicano,

José Antonio Ortega-ToroAuthors Info & Claims

Journal of Heuristics, Volume 27, Issue 1-2

Pages 229 - 249

https://doi.org/10.1007/s10732-020-09462-w

Published: 01 April 2021 Publication History

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.

References

[1]

Arito, F., Chicano, F., Alba, E.: On the Application of Sat Solvers to the Test Suite Minimization Problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7515 LNCS, pp. 45–59 (2012)

[2]

Blum C, Pinacho P, López-Ibáñez M, and Lozano JA Construct, merge, solve & adapt a new general algorithm for combinatorial optimization Comput. Oper. Res. 2016 68 C 75-88

[3]

Cohen MB, Dwyer MB, and Shi J Constructing interaction test suites for highly-configurable systems in the presence of constraints: a Greedy approach IEEE Trans. Softw. Eng. 2008 34 5 633-650

[4]

Dächert K and Klamroth K A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems J. Glob. Optim. 2015 61 4 643-676

[5]

Engström E and Runeson P Software product line testing a systematic mapping study Inf. Softw. Technol. 2011 53 1 2-13

[6]

Ferrer J, Chicano F, and Alba E Squillero G and Sim K Hybrid algorithms based on integer programming for the search of prioritized test data in software product lines EvoApps 2017, LNCS 10200 2017 The Netherlands Springer 3-19

[7]

Henard, C., Papadakis, M., Harman, M., Le Traon, Y.: Combining multi-objective search and constraint solving for configuring large software product lines. In: Proceedings of the 37th International Conference on Software Engineering, vol. 1, pp. 517–528. ICSE ’15, IEEE Press, Piscataway (2015)

[8]

Henard C, Papadakis M, Perrouin G, Klein J, Heymans P, and Le Traon Y Bypassing the combinatorial explosion: using similarity to generate and prioritize t-wise test configurations for software product lines IEEE Trans. Softw. Eng. 2014 40 7 650-670

[9]

Hierons RM, Li M, Liu X, Segura S, and Zheng W SIP: optimal product selection from feature models using many-objective evolutionary optimization ACM Trans. Softw. Eng. Methodol. 2016 25 2 17:1-17:39

[10]

Johansen MF, Haugen Ø, Fleurey F, Eldegard AG, and Syversen T France RB, Kazmeier J, Breu R, and Atkinson C Generating better partial covering arrays by modeling weights on sub-product lines MoDELS, Volume 7590 of Lecture Notes in Computer Science 2012 New York Springer 269-284

[11]

Lopez-Herrejon, R.E., Batory, D.: A standard problem for evaluating product-line methodologies. In: International Symposium on Generative and Component-Based Software Engineering, pp. 10–24 . Springer (2001)

[12]

Lopez-Herrejon, R.E., Chicano, F., Ferrer, J., Egyed, A., Alba, E.: Multi-objective optimal test suite computation for software product line pairwise testing. In: 2013 29th IEEE International Conference on Software Maintenance (ICSM), IEEE, pp. 404–407 (2013)

[13]

Lopez-Herrejon, R.E., Ferrer, J., Chicano, F., Haslinger, E.N., Egyed, A., Alba, E.: A parallel evolutionary algorithm for prioritized pairwise testing of software product lines, pp. 1255–1262 . GECCO’14, ACM, New York, NY, USA (2014)

[14]

Nie C and Leung H A survey of combinatorial testing ACM Comput. Surv. 2011 43 2 11:1-11:29

[15]

Oster S, Markert F, and Ritter P Automated Incremental Pairwise Testing of Software Product Lines 2010 Berlin Springer 196-210

[16]

Perrouin G, Oster S, Sen S, Klein J, Baudry B, and Le Traon Y Pairwise testing for software product lines: comparison of two approaches Softw. Qual. J. 2012 20 3–4 605-643

[17]

Pohl K, Böckle G, and van Der Linden FJ Software Product Line Engineering: Foundations, Principles and Techniques 2005 New York Springer

[18]

Siegmund N, Rosenmüller M, Kästner C, Giarrusso PG, Apel S, and Kolesnikov SS Scalable prediction of non-functional properties in software product lines: footprint and memory consumption Inf. Softw. Technol. 2013 55 3 491-507 Special Issue on Software Reuse and Product Lines

[19]

Vargha A and Delaney HD A critique and improvement of the CL common language effect size statistics of McGraw and Wong J. Educ. Behav. Stat. 2000 25 2 101-132

[20]

Xue, Y., Li, Y.F.: Multi-objective integer programming approaches for solving optimal feature selection problem: a new perspective on multi-objective optimization problems in SBSE. In: Proceedings of the 40th International Conference on Software Engineering. ICSE ’18, New York, NY, USA, ACM, pp. 1231–1242 (2018)

Cited By

Agh HAzamnouri AWagner S(2024)Software product line testing: a systematic literature reviewEmpirical Software Engineering10.1007/s10664-024-10516-x29:6Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1007/s10664-024-10516-x
Khoshniat NJamarani AAhmadzadeh AHaghi Kashani MMahdipour E(2024)Nature-inspired metaheuristic methods in software testingSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08382-828:2(1503-1544)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00500-023-08382-8
Qiu W(2022)Application of Software Data Analysis Model Based on K-Means Clustering AlgorithmSecurity and Communication Networks10.1155/2022/45058142022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/4505814
Show More Cited By

Index Terms

CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines
1. Computing methodologies
  1. Artificial intelligence
2. Mathematics of computing
  1. Mathematical analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Multi-objective test generation for software product lines
SPLC '13: Proceedings of the 17th International Software Product Line Conference

Software Products Lines (SPLs) are families of products sharing common assets representing code or functionalities of a software product. These assets are represented as features, usually organized into Feature Models (FMs) from which the user can ...
Continuous test suite augmentation in software product lines
SPLC '13: Proceedings of the 17th International Software Product Line Conference

Software Product Line (SPL) engineering offers several advantages in the development of families of software products. There is still a need, however, to generate test cases for individual products in product lines more efficiently. In this paper we ...
A fix-and-optimize matheuristic for university timetabling

University course timetabling covers the task of assigning rooms and time periods to courses while ensuring a minimum violation of soft constraints that define the quality of the timetable. These soft constraints can have attributes that make it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Heuristics

Journal of Heuristics Volume 27, Issue 1-2

Apr 2021

259 pages

ISSN:1381-1231

Issue’s Table of Contents

© Springer Science+Business Media, LLC, part of Springer Nature 2020.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2021

Accepted: 23 October 2020

Revision received: 29 September 2020

Received: 15 December 2018

Author Tags

Qualifiers

Research-article

Funding Sources

Ministerio de Economıa, Industria y Competitividad, Gobierno de España
Agencia de Innovación y Desarrollo de Andalucı a
Horizon 2020 Framework Programme
Ministerio de Economıa y Competitividad (ES)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agh HAzamnouri AWagner S(2024)Software product line testing: a systematic literature reviewEmpirical Software Engineering10.1007/s10664-024-10516-x29:6Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1007/s10664-024-10516-x
Khoshniat NJamarani AAhmadzadeh AHaghi Kashani MMahdipour E(2024)Nature-inspired metaheuristic methods in software testingSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08382-828:2(1503-1544)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00500-023-08382-8
Qiu W(2022)Application of Software Data Analysis Model Based on K-Means Clustering AlgorithmSecurity and Communication Networks10.1155/2022/45058142022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/4505814
Rosati RKletzander LBlum CMusliu NSchaerf A(2022)Construct, Merge, Solve and Adapt Applied to a Bus Driver Scheduling Problem with Complex Break ConstraintsAIxIA 2022 – Advances in Artificial Intelligence10.1007/978-3-031-27181-6_18(254-267)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-27181-6_18
Rosati RBouamama SBlum C(2022)Construct, Merge, Solve and Adapt Applied to the Maximum Disjoint Dominating Sets ProblemMetaheuristics10.1007/978-3-031-26504-4_22(306-321)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-26504-4_22
Akbay MKalayci CBlum C(2022)Application of CMSA to the Electric Vehicle Routing Problem with Time Windows, Simultaneous Pickup and Deliveries, and Partial Vehicle ChargingMetaheuristics10.1007/978-3-031-26504-4_1(1-16)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-26504-4_1

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents