Using feature model knowledge to speed up the generation of covering arrays

ABSTRACT

Combinatorial Interaction Testing has shown great potential for effectively testing Software Product Lines (SPLs). An important part of this type of testing is determining a subset of SPL products in which interaction errors are more likely to occur. Such sets of products are obtained by computing a so called t-wise Covering Array (tCA), whose computation is known to be NP-complete. Recently, the ICPL algorithm has been proposed to compute these covering arrays. In this research-in-progress paper, we propose a set of rules that exploit basic feature model knowledge to reduce the number of elements (i.e. t-sets) required by ICPL without weakening the strength of the generated arrays. We carried out a comparison of runtime performance that shows a significant reduction of the needed execution time for the majority of our SPL case studies.

References

1. Software Product Line Online Tools(SPLOT), Accesed July 2011. http://www.splot-research.org/.
2. N. Alon, D. Moshkovitz, and S. Safra. Algorithmic construction of sets for k-restrictions. ACM Transactions on Algorithms, 2(2):153--177, 2006.
3. D. Batory, J. N. Sarvela, and A. Rauschmayer. Scaling Step-Wise Refinement. IEEE TSE, 30(6), 2004.
4. D. Benavides, S. Segura, and A. Ruiz-Cortés. Automated analysis of feature models 20 years later: A literature review. Information Systems, In Press, Corrected Proof:--, 2010.
5. M. Cohen, M. Dwyer, and J. Shi. Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach. Software Engineering, IEEE Transactions on, 34(5):633--650, sept.--oct. 2008.
6. K. Czarnecki and U. Eisenecker. Generative Programming: Methods, Tools, and Applications. Addison-Wesley, 2000.
7. E. S. de Almeida, C. Schwanninger, and D. Benavides, editors. 16th International Software Product Line Conference, SPLC '12, Salvador, Brazil - September 2--7, 2012, Volume 1. ACM, 2012.
8. E. Engström and P. Runeson. Software product line testing - a systematic mapping study. Information & Software Technology, 53(1):2--13, 2011.
9. J. Ferrer, P. M. Kruse, J. F. Chicano, and E. Alba. Evolutionary algorithm for prioritized pairwise test data generation. In T. Soule and J. H. Moore, editors, GECCO, pages 1213--1220. ACM, 2012.
10. S. Fouché, M. B. Cohen, and A. A. Porter. Incremental covering array failure characterization in large configuration spaces. In G. Rothermel and L. K. Dillon, editors, ISSTA, pages 177--188. ACM, 2009.
11. B. J. Garvin, M. B. Cohen, and M. B. Dwyer. Evaluating improvements to a meta-heuristic search for constrained interaction testing. Empirical Software Engineering, 16(1):61--102, 2011.
12. 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. Kühne, editors, MoDELS, volume 6981 of Lecture Notes in Computer Science, pages 638--652. Springer, 2011.
13. M. F. Johansen, Ø. Haugen, and F. Fleurey. An algorithm for generating t-wise covering arrays from large feature models. In de Almeida et al. {7}, pages 46--55.
14. K. Kang, S. Cohen, J. Hess, W. Novak, and A. Peterson. Feature-Oriented Domain Analysis (FODA) Feasibility Study. Technical Report CMU/SEI-90-TR-21, Software Engineering Institute, Carnegie Mellon University, 1990.
15. R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, The IBM Research Symposia Series, pages 85--103. Plenum Press, New York, 1972.
16. D. R. Kuhn, D. R. Wallace, and A. M. Gallo, Jr. Software fault interactions and implications for software testing. IEEE Trans. Softw. Eng., 30(6):418--421, June 2004.
17. J. Lee, S. Kang, and D. Lee. A survey on software product line testing. In de Almeida et al. {7}, pages 31--40.
18. Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence. Ipog: A general strategy for t-way software testing. In ECBS, pages 549--556. IEEE Computer Society, 2007.
19. C. Nie and H. Leung. A survey of combinatorial testing. ACM Comput. Surv., 43(2):11:1--11:29, Feb. 2011.
20. 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.
21. K. Pohl, G. Bockle, and F. J. van der Linden. Software Product Line Engineering: Foundations, Principles and Techniques. Springer, 2005.
22. 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, 2006.
23. S. Segura. Automated analysis of feature models using atomic sets. In S. Thiel and K. Pohl, editors, SPLC (2), pages 201--207. Lero Int. Science Centre, University of Limerick, Ireland, 2008.
24. E. Uzuncaova, S. Khurshid, and D. S. Batory. Incremental test generation for software product lines. IEEE Trans. Software Eng., 36(3):309--322, 2010.
25. P. Zave. Faq sheet on feature interaction. http://www.research.att.com/pamela/faq.html.

Index Terms

• Software and its engineering

  • Software creation and management

    • Software development techniques

      • Reusability

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software notations and tools

    • Software libraries and repositories