article

Pairwise testing for software product lines: comparison of two approaches

Authors:

Gilles Perrouin,

Sebastian Oster,

Yves TraonAuthors Info & Claims

Software Quality Journal, Volume 20, Issue 3-4

Pages 605 - 643

https://doi.org/10.1007/s11219-011-9160-9

Published: 01 September 2012 Publication History

Abstract

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability, which in turn leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large products space is hardly feasible. Hence, one possible option is to test SPLs by generating test configurations that cover all possible t feature interactions (t-wise). It dramatically reduces the number of test products while ensuring reasonable SPL coverage. In this paper, we report our experience on applying t-wise techniques for SPL with two independent toolsets developed by the authors. One focuses on generality and splits the generation problem according to strategies. The other emphasizes providing efficient generation. To evaluate the respective merits of the approaches, measures such as the number of generated test configurations and the similarity between them are provided. By applying these measures, we were able to derive useful insights for pairwise and t-wise testing of product lines.

References

[1]

Batory, D. S. (2005). Feature models, grammars, and propositional formulas. In: Software product line conference (SPLC) (pp. 7-20).

[2]

Batory, D., Benavides, D., & Ruiz-Cortés, A. (2006). Automated analysis of feature models: Challenges ahead. Communications of the ACM.

[3]

Benavides, D., Segura, S., & Ruiz-Cortés, A. (2010). Automated analysis of feature models 20 years later: A literature review. Information Systems, 35(6), 615-636.

Digital Library

[4]

Bennaceur, H. (2004). A comparison between SAT and CSP techniques. Constraints, 9(2), 123-138.

[5]

Berger, T., She, S., Lotufo, R., Wasowski, A., & Czarnecki, K. (2010). Variability modeling in the real: A perspective from the operating systems domain. In: Proceedings of the IEEE/ACM international conference on automated software engineering (pp. 73-82). New York, NY, USA: ACM, automated software engineering conference (ASE) '10.

[6]

Bryce, R., & Colbourn, C. (2009). A density-based greedy algorithm for higher strength covering arrays. Software Testing, Verification and Reliability, 19(1), 37-53.

Digital Library

[7]

Bryce, R. C., & Colbourn, C. J. (2006). Prioritized interaction testing for pair-wise coverage with seeding and constraints. Information and Software Technology, 48(10):960-970, advances in Model-based Testing.

[8]

Budinsky, F., Steinberg, D., Merks, E., Ellersick, R., & Grose, T. (2003). Eclipse modeling framework. The Eclipse Series, Addison Wesley Professional.

[9]

Calvagna, A., & Gargantini, A. (2009). Combining satisfiability solving and heuristics to constrained combinatorial interaction testing. In: International conference on tests and proofs (pp. 27-42). Berlin, Heidelberg: Springer.

[10]

Calvagna, A., & Gargantini, A. (2008). A logic-based approach to combinatorial testing with constraints. In Beckert, B., Hähnle, R., (Eds.), Tests and proofs (Vol. 4966, pp. 66-83). Berlin/Heidelberg: Springer, Lecture Notes in Computer Science.

[11]

Cartaxo, E. G., Machado, P. D. L., & Neto F. G. O. (2011). On the use of a similarity function for test case selection in the context of model-based testing. Software Testing, Verification & Reliability, 21, 75-100.

Digital Library

[12]

Classen, A., Heymans, P., & Schobbens, P. (2008). What's in a feature: A requirements engineering perspective. In Proceedings of the theory and practice of software, 11th international conference on fundamental approaches to software engineering (pp. 16-30). Springer.

[13]

Clements, P., & Northrop, L. (2001a). Software product lines: Practices and patterns. Reading, MA, USA: Addison Wesley.

[14]

Clements, P., & Northrop, L. (2001b). Software product lines: practices and patterns. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc.

[15]

Cohen, M., Dwyer, M., & Shi, J. (2007). Interaction testing of highly-configurable systems in the presence of constraints. In International symposium on software testing and analysis (Vol. 4961/2008, pp. 129-139).

[16]

Cohen, M. B., Dwyer, M. B., & Shi, J. (2006). Coverage and adequacy in software product line testing. In ROSATEA@ISSTA (pp. 53-63).

[17]

Cohen, D. M., Dalal, S. R., Fredman, M. L., & Patton, G. C. (1997). The AETG system: An approach to testing based on combinatorial design. IEEE Transactions on Software Engineering, 23(7), 437-444.

Digital Library

[18]

Czarnecki, K., Wasowski, A. (2007). Feature diagrams and logics: There and back again. In 11th software product line conference (pp. 23-34). Kyoto, Japan: IEEE Computer Society.

[19]

Czarnecki, K., & Antkiewicz, M. (2005). Mapping features to models: A template approach based on superimposed variants. In Generative programming and component engineering (GPCE) (Vol. 3676, pp. 422-437). Springer, LNCS.

[20]

Czarnecki, K., Helsen, S., & Eisenecker, U. (2005). Formalizing cardinality-based feature models and their specialization. Software Process Improvement and Practice, 10(1), 7-29.

[21]

Ganesan, D., Knodel, J., Kolb, R., Haury, U., & Meier, G. (2007). Comparing costs and benefits of different test strategies for a software product line: A study from testo ag. In: 11th International software product line conference (pp. 74-83). Los Alamitos, CA, USA: IEEE Computer Society.

Digital Library

[22]

Griss, M. L., Favaro, J., & d' Alessandro, M. (1998). Integrating feature modeling with the RSEB. In Fifth international conference on software reuse (pp. 76-85). Washington, DC, USA.

[23]

Haralick, R., & Elliott, G. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14(3), 263-313.

[24]

Hemmati, H., & Briand, L. (2010). An industrial investigation of similarity measures for model-based test case selection. In International symposium on software reliability engineering (ISSRE) (pp. 141-150). Los Alamitos, CA, USA: IEEE Computer Society.

[25]

Hemmati, H., Arcuri, A., & Briand, L. (2010). Reducing the cost of model-based testing through test case diversity. In 22nd IFIP international conference on testing software and systems (ICTSS)-- formerly TestCom/FATES (Vol. 6435/2010, pp. 63-78).

[26]

Hemmati, H., Arcuri, A., & Briand, L. (2011). Empirical investigation of the effects of test suite properties on similarity-based test case selection. In 4th international conference on software testing, verification and validation (ICST) (pp. 327-336), Berlin, Germany.

[27]

Jackson, D. (2006). Software abstractions: Logic, language, and analysis. MIT Press: Cambridge.

[28]

Kang, K., Cohen, S., Hess, J., Novak, W., & Peterson, S. (1990). Feature-oriented domain analysis (FODA) feasibility study. Tech. Rep. CMU/SEI-90-TR-21, Software Engineering Institute.

[29]

Kang, K. C., Kim, S., Lee, J., Kim, K., Shin, E., Huh, M. (1998). FORM: A feature-oriented reuse method with domain-specific reference architectures. Annals of Software Engineering, 5, 143-168.

Digital Library

[30]

Kuhn, R., Lei, Y., Kacker, R. (2008). Practical combinatorial testing: Beyond pairwise. IT Professional, 10, 19-23. http://doi.ieeecomputersociety.org/10.1109/MITP.2008.54.

Digital Library

[31]

Kuhn, D. R., Wallace, D. R., & Gallo, A. M. (2004). Software fault interactions and implications for software testing. IEEE Transactions on Software Engineering, 30(6), 418-421.

Digital Library

[32]

Lei, Y., & Tai, K. (1998). In-parameter-order: A test generation strategy for pairwise testing. In IEEE high assurance systems engineering symposium (pp. 254-261).

[33]

Lei, Y., Kacker, R., Kuhn, D., Okun, V., & Lawrence, J. (2008). IPOG/IPOG-D: Efficient test generation for multi-way combinatorial testing. Software Testing, Verification and Reliability, 18(3), 125-148.

[34]

Mahajan, Y. S., Fu, Z. S. M. (2004). Zchaff 2004: An efficient sat solver. In SAT 2004 (pp. 360-375).

[35]

McGregor, J. (2001). Testing a software product line. Tech. Rep. ESC-TR-2001-022, CMU/SEI.

[36]

Mendon¿a, M., Wasowski, A., & Czarnecki, K. (2009). Sat-based analysis of feature models is easy. In 13th international software product line conference (SPLC) (pp. 231-240). San Francisco, CA, USA.

[37]

Mendonca, M., Branco, M., & Cowan, D. (2009). SPLOT: Software product lines online tools. In Proceeding of the 24th ACM SIGPLAN conference companion on object oriented programming systems languages and applications (pp. 761-762). ACM.

[38]

Metzger, A., Pohl, K., Heymans, P., Schobbens, P. Y., & Saval, G. (2007). Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis. In IEEE conference on requirements engineering (pp. 243-253). Delhi, India: IEEE Computer Society.

[39]

Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999). Determining computational complexity from characteristic phase transitions. Nature, 400(6740), 133-137.

[40]

MoSo-PoLiTe (2011). http://www.sharq.tu-darmstadt.de/projects/mosopolite/. Accessed 8th April 2011.

[41]

Muller, P. A., Fleurey, F., & Jézéquel, J. M. (2005). Weaving executability into object-oriented metalanguages. In MODELS/UML. Springer.

[42]

Niklas, E., & Niklas, S. (2005). MiniSat: A SAT solver with conflict-clause minimization, poster. In SAT 2005.

[43]

Oster, S., Markert, F., & Ritter, P. (2010). Automated incremental pairwise testing of software product lines. In Bosch, J., & Lee, J. (Eds.), Software product line conference (SPLC) (Vol. 6287, pp. 196-210). Springer, Lecture Notes in Computer Science.

[44]

Oster, S., Wübbeke, A., Engels, G., & Schürr, A. (2011). Model-based software product lines testing survey. In Zander, J., Schieferdecker, I., & Mosterman, P. (Eds.), Model-based testing for embedded systems. CRC Press Taylor & Francis, to appear on September 9th, 2011.

[45]

Perrouin, G., Klein, J., Guelfi, N., & Jézéquel, J. M. (2008). Reconciling automation and flexibility in product derivation. In Software product line conference (SPLC) (pp. 339-348). Limerick, Ireland: IEEE Computer Society.

[46]

Perrouin, G., Sen, S., Klein, J., Baudry, B., & le Traon, Y. (2010). Automated and scalable t-wise test case generation strategies for software product lines. In International conference on software testing, verification, and validation (ICST) (pp. 459-468). IEEE Computer Society, Paris, France.

[47]

Phadke, M. (1995). Quality engineering using robust design. Upper Saddle River, NJ, USA: Prentice Hall PTR

[48]

Pohl, K., Böckle, G., & van der Linden. F. J. (2005). Software Product Line Engineering: Foundations, Principles and Techniques. Secaucus, NJ, USA: Springer-Verlag New York, Inc.

[49]

Gheyi, R. T. M., & Borba, P. (2006). A theory for feature models in alloy. In First alloy workshop (pp. 71-80).

[50]

Scheidemann, K. (2007). Verifying families of system configurations. Doctoral Thesis TU Munich.

[51]

Schobbens, P. Y., Heymans, P., Trigaux, J. C., & Bontemps, Y. (2006). Feature diagrams: A survey and a formal semantics. In Requirements engineering, IEEE international conference on (pp. 139-148).

[52]

Schobbens, P., Heymans, P., Trigaux, J., & Bontemps, Y. (2007). Generic semantics of feature diagrams. Computer Networks, 51(2), 456-479.

Digital Library

[53]

Tan, P., Steinbach, M., Kumar, V., et al. (2006). Introduction to data mining. Boston: Pearson Addison Wesley

[54]

Tevanlinna, A., Taina, J., & Kauppinen, R. (2004). Product family testing: A survey. SIGSOFT Software Engineering Notes, 29(2), 12-12.

Digital Library

[55]

Torlak, E., & Jackson, D. (2007). Kodkod: A relational model finder. In Tools and algorithms for construction and analysis of systems (Vol. 4424/2007, pp. 632-647).

[56]

Uzuncaova, E., Garcia, D., Khurshid, S., & Batory, D. (2008). Testing software product lines using incremental test generation. In ISSRE (pp. 249-258). IEEE Computer Society.

[57]

Westphal, M., & Wölfl, S. (2009). Qualitative csp, finite csp, and sat: Comparing methods for qualitative constraint-based reasoning. In IJCAI'09: Proceedings of the 21st international jont conference on artificial intelligence (pp. 628-633). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

[58]

White, J., Dougherty, B., & Schmidt, D. C. (2009). Selecting highly optimal architectural feature sets with filtered cartesian flattening. Journal of Systems and Software, 82(8), 1268-1284.

Digital Library

[59]

Yoon, I., Sussman, A., Memon, A., & Porter, A. (2007). Direct-dependency-based software compatibility testing. In Automated software engineering conference (ASE) (pp. 409-412). Atlanta, Georgia, USA.

[60]

Ziadi, T., & Jézéquel, J. M. (2006). Product line engineering with the UML: Deriving products. In Families research book. Springer.

Cited By

Becker MRabiser RBotterweck G(2024)Not Quite There Yet: Remaining Challenges in Systems and Software Product Line Engineering as Perceived by Industry PractitionersProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3672587(179-190)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3672587
Böhm SKrieter SHeß TThüm TLochau M(2024)Incremental Identification of T-Wise Feature InteractionsProceedings of the 18th International Working Conference on Variability Modelling of Software-Intensive Systems10.1145/3634713.3634715(27-36)Online publication date: 7-Feb-2024
https://dl.acm.org/doi/10.1145/3634713.3634715
Arrieta AValle PAgirre JSagardui G(2023)Some Seeds Are Strong: Seeding Strategies for Search-based Test Case SelectionACM Transactions on Software Engineering and Methodology10.1145/353218232:1(1-47)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3532182
Show More Cited By

Pairwise testing for software product lines: comparison of two approaches
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Automated and Scalable T-wise Test Case Generation Strategies for Software Product Lines
ICST '10: Proceedings of the 2010 Third International Conference on Software Testing, Verification and Validation

Software Product Lines (SPL) are difficult to validate due to combinatorics induced by variability across their features. This leads to combinatorial explosion of the number of derivable products. Exhaustive testing in such a large space of products is ...
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 ...
Model-based pairwise testing for feature interaction coverage in software product line engineering

Testing software product lines (SPLs) is very challenging due to a high degree of variability leading to an enormous number of possible products. The vast majority of today's testing approaches for SPLs validate products individually using different ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software Quality Journal

Software Quality Journal Volume 20, Issue 3-4

September 2012

311 pages

ISSN:0963-9314

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
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

Becker MRabiser RBotterweck G(2024)Not Quite There Yet: Remaining Challenges in Systems and Software Product Line Engineering as Perceived by Industry PractitionersProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3672587(179-190)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3672587
Böhm SKrieter SHeß TThüm TLochau M(2024)Incremental Identification of T-Wise Feature InteractionsProceedings of the 18th International Working Conference on Variability Modelling of Software-Intensive Systems10.1145/3634713.3634715(27-36)Online publication date: 7-Feb-2024
https://dl.acm.org/doi/10.1145/3634713.3634715
Arrieta AValle PAgirre JSagardui G(2023)Some Seeds Are Strong: Seeding Strategies for Search-based Test Case SelectionACM Transactions on Software Engineering and Methodology10.1145/353218232:1(1-47)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1145/3532182
Cazzola WFavalli L(2022)Towards a recipe for language decomposition: quality assessment of language product linesEmpirical Software Engineering10.1007/s10664-021-10074-627:4Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10664-021-10074-6
Cordy MDevroey XLegay APerrouin GClassen AHeymans PSchobbens PRaskin J(2022)A Decade of Featured Transition SystemsFrom Software Engineering to Formal Methods and Tools, and Back10.1007/978-3-030-30985-5_18(285-312)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-030-30985-5_18
Sundermann CFeichtinger KEngelhardt DRabiser RThüm TMousavi MSchobbens P(2021)Yet another textual variability language?Proceedings of the 25th ACM International Systems and Software Product Line Conference - Volume A10.1145/3461001.3471145(136-147)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3461001.3471145
Markiegi UArrieta AEtxeberria LSagardui G(2021)Dynamic test prioritization of product lines: An application on configurable simulation modelsSoftware Quality Journal10.1007/s11219-021-09571-029:4(943-988)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11219-021-09571-0
Ferrer JChicano FOrtega-Toro J(2021)CMSA algorithm for solving the prioritized pairwise test data generation problem in software product linesJournal of Heuristics10.1007/s10732-020-09462-w27:1-2(229-249)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10732-020-09462-w
Arrieta AAgirre JSagardui GCoello Coello C(2020)Seeding strategies for multi-objective test case selectionProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389810(1222-1231)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389810
Markiegi UArrieta AEtxeberria LSagardui GHung CPapadopoulos G(2019)Test case selection using structural coverage in software product lines for time-budget constrained scenariosProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297512(2362-2371)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297512
Show More Cited By

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