Martin Fagereng Johansen
ABSTRACT
A scalable approach for software product line testing is required due to the size and complexity of industrial product lines. In this paper, we present a specialized algorithm (called ICPL) for generating covering arrays from feature models. ICPL makes it possible to apply combinatorial interaction testing to software product lines of the size and complexity found in industry. For example, ICPL allows pair-wise testing to be readily applied to projects of about 7,000 features and 200,000 constraints, the Linux Kernel, one of the largest product lines where the feature model is available. ICPL is compared to three of the leading algorithms for t-wise covering array generation. Based on a corpus of 19 feature models, data was collected for each algorithm and feature model when the algorithm could finish 100 runs within three days. These data are used for comparing the four algorithms. In addition to supporting large feature models, ICPL is quick, produces small covering arrays and, even though it is non-deterministic, produces a covering array of a similar size within approximately the same time each time it is run with the same feature model.
- A. Calvagna and A. Gargantini. Combining satisfiability solving and heuristics to constrained combinatorial interaction testing. In C. Dubois, editor, Tests and Proofs, volume 5668 of Lecture Notes in Computer Science, pages 27--42. Springer Berlin / Heidelberg, 2009. Google Scholar
Digital Library
- V. Chvátal. A greedy heuristic for the Set-Covering problem. Mathematics of Operations Research, 4(3): 233--235, 1979.Google ScholarDigital Library
- M. B. Cohen, M. B. Dwyer, and J. Shi. Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach. IEEE Transactions on Software Engineering, 34: 633--650, 2008. Google ScholarDigital Library
- K. Czarnecki and U. Eisenecker. Generative programming: methods, tools, and applications. ACM Press/Addison-Wesley Publishing Co. New York, NY, USA, 2000. Google ScholarDigital Library
- E. Engström and P. Runeson. Software product line testing - a systematic mapping study. Information and Software Technology, 53(1): 2--13, 2011. Google ScholarDigital Library
- S. Fouché, M. B. Cohen, and A. Porter. Incremental covering array failure characterization in large configuration spaces. In Proceedings of the eighteenth international symposium on Software testing and analysis, ISSTA '09, pages 177--188, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- B. J. Garvin, M. B. Cohen, and M. B. Dwyer. Evaluating improvements to a meta-heuristic search for constrained interaction testing. Empirical Softw. Engg., 16: 61--102, February 2011. Google ScholarDigital Library
- W. Grieskamp, X. Qu, X. Wei, N. Kicillof, and M. Cohen. Interaction coverage meets path coverage by smt constraint solving. In M. Núñez, P. Baker, and M. Merayo, editors, Testing of Software and Communication Systems, volume 5826 of Lecture Notes in Computer Science, pages 97--112. Springer Berlin / Heidelberg, 2009. Google ScholarDigital Library
- W. D. Hillis and G. L. Steele, Jr. Data parallel algorithms. Commun. ACM, 29(12): 1170--1183, Dec. 1986. Google ScholarDigital Library
- M. Janota. SAT Solving in Interactive Configuration. PhD thesis, University College Dublin, 2010.Google Scholar
- M. F. Johansen, Ø. Haugen, and F. Fleurey. Properties of realistic feature models make combinatorial testing of product lines feasible. In J. Whittle, T. Clark, and T. Kuehne, editors, Proceedings of Model Driven Engineering Languages and Systems, 14th International Conference, MODELS 2011, pages 638--652, Wellington, New Zealand, October 2011. Springer, Heidelberg. Google ScholarDigital Library
- M. F. Johansen, Ø. Haugen, and F. Fleurey. A survey of empirics of strategies for software product line testing. In L. O'Conner, editor, Proceedings of the 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation Workshops, ICSTW '11, pages 266--269, Washington, DC, USA, 2011. IEEE Computer Society. Google ScholarDigital Library
- K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, and A. S. Peterson. Feature-oriented domain analysis (foda) feasibility study. Technical report, Carnegie-Mellon University Software Engineering Institute, November 1990.Google Scholar
- C. H. P. Kim, D. S. Batory, and S. Khurshid. Reducing combinatorics in testing product lines. In Proceedings of the tenth international conference on Aspect-oriented software development, AOSD '11, pages 57--68, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- D. R. Kuhn, D. R. Wallace, and A. M. Gallo. Software fault interactions and implications for software testing. IEEE Transactions on Software Engineering, 30(6): 418--421, 2004. Google ScholarDigital Library
- Y. Lei, R. Kacker, D. Kuhn, V. Okun, and J. Lawrence. Ipog: A general strategy for t-way software testing. In Engineering of Computer-Based Systems, 2007. ECBS'07. 14th Annual IEEE International Conference and Workshops on the, pages 549--556. IEEE, 2007. Google ScholarDigital Library
- S. Oster, F. Markert, and P. Ritter. Automated incremental pairwise testing of software product lines. In J. Bosch and J. Lee, editors, SPLC, volume 6287 of Lecture Notes in Computer Science, pages 196--210. Springer, 2010. Google ScholarDigital Library
- G. Perrouin, S. Oster, S. Sen, J. Klein, B. Baudry, and Y. le Traon. Pairwise testing for software product lines: Comparison of two approaches. Software Quality Journal, 2011.Google Scholar
- K. Pohl, G. Böckle, and F. J. v. d. Linden. Software Product Line Engineering: Foundations, Principles and Techniques. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2005. Google ScholarDigital Library
- A. Reuys, S. Reis, E. Kamsties, and K. Pohl. The scented method for testing software product lines. In T. Käkölä and J. C. Dueñas, editors, Software Product Lines, pages 479--520. Springer, Berlin, Heidelberg, 2006.Google ScholarCross Ref
- J. Rivieres and W. Beaton. Eclipse Platform Technical Overview, 2006.Google Scholar
- S. She, R. Lotufo, T. Berger, A. Wasowski, and K. Czarnecki. Reverse engineering feature models. In R. N. Taylor, H. Gall, and N. Medvidovic, editors, ICSE, pages 461--470. ACM, 2011. Google ScholarDigital Library
- E. Uzuncaova, S. Khurshid, and D. Batory. Incremental test generation for software product lines. Software Engineering, IEEE Transactions on, 36(3): 309--322, may-june 2010. Google ScholarDigital Library
- T. Walsh. Sat v csp. In R. Dechter, editor, Principles and Practice of Constraint Programming -- CP 2000, volume 1894 of Lecture Notes in Computer Science, pages 441--456. Springer Berlin / Heidelberg, 2000. Google ScholarDigital Library
Index Terms
- An algorithm for generating t-wise covering arrays from large feature models
Recommendations
Generating better partial covering arrays by modeling weights on sub-product lines
MODELS'12: Proceedings of the 15th international conference on Model Driven Engineering Languages and SystemsCombinatorial interaction testing is an approach for testing product lines. A set of products to test can be set up from the covering array generated from a feature model. The products occurring in a partial covering array, however, may not focus on the ...
Goal-Oriented Test Case Selection and Prioritization for Product Line Feature Models
ITNG '11: Proceedings of the 2011 Eighth International Conference on Information Technology: New GenerationsThe software product line engineering paradigm is amongst the widely used means for capturing and handling the commonalities and variabilities of the many applications of a target domain. The large number of possible products and complex interactions ...
Automated metamorphic testing on the analyses of feature models
Context: A feature model (FM) represents the valid combinations of features in a domain. The automated extraction of information from FMs is a complex task that involves numerous analysis operations, techniques and tools. Current testing methods in this ...
Comments