Top

Software Quality Journal

Published in:

01-09-2012

Pairwise testing for software product lines: comparison of two approaches

Authors: Gilles Perrouin, Sebastian Oster, Sagar Sen, Jacques Klein, Benoit Baudry, Yves le Traon

Published in: Software Quality Journal | Issue 3-4/2012

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Model-based pairwise testing for feature interaction coverage in software product line engineering

next article AoURN-based modeling and analysis of software product lines

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Defined by Pamela Zave as “An increment in functionality”. See http://www.research.att.com/pamela/faq.html and Batory et al. 2006).

See document ad/09-12-03 on the OMG website for the full request for proposals.

In general, we will use the term “tuple” to mention a t-Tuple when t does not matter. In the special case of pairwise, i.e., when t = 2, we denote a 2-tuple by the term “pair”.

EMF (Budinsky et al. 2003) is an Eclipse framework dedicated to the manipulation of models, on which we based our generic feature modeling approach (Perrouin et al. 2008).

http://www.splot-research.org/.

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

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

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.CrossRef

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

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.

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

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.

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

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.

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.

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.CrossRef

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.

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

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

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).

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

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.CrossRef

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.

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.

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

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.

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.

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

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.

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).

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.

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

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.

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.CrossRef

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.

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.CrossRef

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).

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.CrossRef

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

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

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.

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.

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.

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

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

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

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

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.

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.

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.

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.

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

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.MATH

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

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

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).

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

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

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

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).

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.

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.

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.CrossRef

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.

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

Title: Pairwise testing for software product lines: comparison of two approaches
Authors: Gilles Perrouin
Sebastian Oster
Sagar Sen
Jacques Klein
Benoit Baudry
Yves le Traon
Publication date: 01-09-2012
Publisher: Springer US
Published in: Software Quality Journal / Issue 3-4/2012
Print ISSN: 0963-9314
Electronic ISSN: 1573-1367
DOI: https://doi.org/10.1007/s11219-011-9160-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3-4/2012

AoURN-based modeling and analysis of software product lines

In this issue

A systematic review of quality attributes and measures for software product lines

Composing multiple variability artifacts to assemble coherent workflows

SPL Conqueror: Toward optimization of non-functional properties in software product lines

Foreword to the special issue on quality engineering for software product lines

Premium Partner