An Experiment of Different Similarity Measures on Test Case Prioritization for Software Product Lines

Muhammad Sahak, Dayang N. A. Jawawi, Shahliza A. Halim


Software product line (SPL) engineering paradigm is commonly used to manage variability and commonalities of business applications to satisfy a specific need or goal of a particular market. However, due to time and space complexity, combinatorial interaction testing (CIT) has been suggested to reduce the size of test suites. Although CIT is known as a promising approach to overcome these problems, there are still issues such as combinatorial explosion of features, which drains budget allocated for testing. Therefore, test case prioritization (TCP) is preferred to gain a better result in terms of producing an efficient detection of faults. Among prioritization techniques used in regression testing is similarity-based test case prioritization. Similarity-based test case prioritization rearranges test cases through calculation of distance between test cases using similarity measures. Result from the use of similarity measures in test case prioritization contributes to a much better testing process. This paper provides a comparison of selected similarity measures to investigate the feasibility and suitability of similarity measures to be used in SPL through experimentation. Jaccard, Hamming, Jaro-Winkler, Cosine similarity, Counting, and Sorensein distances have been chosen as similarity measures in this study. The result showed JaroWinkler as the best similarity measure with an 84.96% Average Percentage of Faults Detected (APFD) value across eight feature models. The study offers insights on similarity measures in SPL context. Further, the paper concludes with suggestions on room for improvement, which could be achieved through experimentation and comparison studies.


Similarity-based; Similarity Measure; Software Product Line Testing; Test Case Prioritization;

Full Text:



X. Davier, G. Perrouin, M. Cordy, P. Schobbens, A. Legay, and P. Heymans, “Towards statistical prioritization for software product lines testing,” in Proc. of the Eighth Int. Workshop on Variability Modelling of Software-Intensive Systems, 2014, pp. 10.

A. Ensan, E. Bagheri, M. Asadi, D. Gasevic, and Y. Biletskiy, “Goaloriented test case selection and prioritization for product line feature models,” in IEEE Eighth Int. Conf. on Information Technology: New Generations (ITNG), 2011, 2011, pp. 291-298.

C. Henard, M. Papadakis, G. Perrouin, J. Klein, P. Heymans, and Y. L. Traon, “Bypassing the combinatorial explosion: Using similarity to generate and prioritize t-wise test configurations for software product lines,” IEEE Trans. on Software Engineering, vol. 40, no. 7, pp. 650- 670, 2014.

M. Johansen, Ø. Haugen, F. Fleurey, A. Eldegard, and T. Syversen. “Generating better partial covering arrays by modeling weights on subproduct lines,” in Model Driven Engineering Languages and Systems, R. B. France, J. Kazmeier, R. Breu, and C. Atkinson, Eds. Berlin, Heidelberg: Springer, 2012, pp. 269-284.

R. Lachmann, S, Lity, S. Lischke, S. Beddig, S. Schulze, and I. Schaefer, “Delta-oriented test case prioritization for integration testing of software product lines,” in Proc. of the 19th Int. Conf. on Software Product Line, 2015, pp. 81-90.

M. Al-Hajjaji, T. Thüm, J. Meinicke, M. Lochau, and G. Saake, “Similarity-based prioritization in software product-line testing,” in Proc. of the 18th ACM International Software Product Line Conference-Volume 1, 2014, pp. 197-206.

Pohl, Klaus, and A. Metzger. “Software product line testing,” Communications of the ACM, vol. 49, no. 12, pp. 78-81, 2006.

P. Bielkowicz, P. Patel, and T. T. Tun, “Evaluating information systems development methods: a new framework,” in Int. Conf. on Object-Oriented Information Systems, 2002, pp. 311-322.

J. Lee, S. Kang, and D. Lee, “A survey on software product line testing,” in Proc. of the ACM 16th Int. Software Product Line Conference-Volume 1, 2012, pp. 31-40.

A. B. Sánchez, S. Segura, and A. Ruiz-Cortés, “A comparison of test case prioritization criteria for software product lines,” in 2014 IEEE Seventh International Conference on Software Testing, Verification and Validation (ICST), 2014, pp. 41-50.

S. Yoo, and M. Harman, “Regression testing minimization, selection and prioritization: a survey,” Software Testing, Verification and Reliability, vol. 22, no. 2, pp. 67-120, 2012.

A. Ahnassay, E. Bagheri, and D. Gasevic, Empirical Evaluation in Software Product Line Engineering. Technical report, Tech. Rep. TRLS3-130084R4T, Laboratory for Systems, Software and Semantics, Ryerson University, 2013.

E. Engström, and P. Runeson, “Software product line testing–a systematic mapping study,” Information and Software Technology, vol. 53, no. 1, pp. 2-13, 2011,

P. A. M. S. Neto, I. C. Machado, J. D. McGregor, E. S. Almeida, and S. R. L. Meira. “A systematic mapping study of software product lines testing,” Information and Software Technology, vol. 53, no. 5, pp. 407- 423. 2011.

I. C. Machado, J. D. Mcgregor, and E.S. Almeida. “On strategies for testing software product lines: A systematic literature review,” Information and Software Technology, 2014, vol. 56, no. 10 pp.1183-1199, 2014.

B. P. Lamancha, M. Polo, and M. Piattini, “Systematic review on software product line testing,” in Int. Conf. on Software and Data Technologies, 2010, pp. 58-71.

I. C. Machado, J. D. McGregor, and E. S. Almeida. “Strategies for testing products in software product lines,” ACM SIGSOFT Software Engineering Notes, vol. 37, no. 6, pp. 1-8, 2012.

L. Jin-Hua, L. Qiong, and L. Jing. “The w-model for testing software product lines,” in Int. Symposium on Computer Science and Computational Technology (ISCSCT'08), 2008, pp. 690-693.

G. J. Myers, C. Sandler, and T. Badgett. The Art of Software Testing. John Wiley & Sons, 2011.

T. Thomas, S. Apel, C. Kästner, I. Schaefer, and G. Saake. “A classification and survey of analysis strategies for software product lines,” ACM Computing Surveys (CSUR), vol. 47, no. 1, p. 6, 2014.

R. E. Lopez-Herrejon, S. Fischer, R. Ramler, and A. Egyed, “A first systematic mapping study on combinatorial interaction testing for software product lines,” in 2015 IEEE Eighth Int. Conf. on Software Testing, Verification and Validation Workshops (ICSTW), 2015, pp. 1- 10.

S.S. Choi, S. H. Cha, and Charles C. Tappert. “A survey of binary similarity and distance measures,” Journal of Systemics, Cybernetics and Informatics, vol. 8, no. 1, pp.43-48, 2010.

M. Bilenko, “Learnable similarity functions and their applications to clustering and record linkage,” in AAAI'04 Proceedings of the 19th National Conference on Artificial Intelligence, 2004, pp. 981-982.

S. Oster, F. Markert, and P. Ritter. “Automated incremental pairwise testing of software product lines,” in Software Product Lines: Going Beyond, J. Bosch, and J. Lee, Eds. Berlin, Heidelberg: Springer, 2010, pp.196-210.

G. Perrouin, S. Oster, S. Sen, J. Klein, B. Baudry, and Y. L. Traon, “Pairwise testing for software product lines: comparison of two approaches,” Software Quality Journal, vol. 20, no. 3-4, pp. 605-643, 2012.

G. Perrouin,, S. Sen, J. Klein, B. Baudry, and Y. L. Traon, “Automated and scalable t-wise test case generation strategies for software product lines,” in 2010 Third Int. Conf. on Software Testing, Verification and Validation (ICST), 2010, pp. 459-468.

G. Rothermel, R. H. Untch, C.Chu, and M. J. Harrold. “Prioritizing test cases for regression testing,” IEEE Trans. on Software Engineering, vol. 27, no. 10, pp. 929-948, 2001.

X. Devroey, G. Perrouin, A. Legay, P. Schobbens, and P. Heymans, “Search-based similarity-driven behavioural SPL testing,” in Proc. of the Tenth International Workshop on Variability Modelling of Software-intensive Systems, 2016, pp. 89-96.

K. C. Kang, S. G. Cohen, J. A. Hess, W. E. Novak, and A. Spencer Peterson. Feature-Oriented Domain Analysis (FODA) Feasibility Study. No. CMU/SEI-90-TR-21. Carnegie-Mellon Univ. Pittsburgh Pa Software Engineering Inst, 1990.

D. R. Kuhn, D. R. Wallace, and A. M. Gallo. “Software fault interactions and implications for software testing,” IEEE Trans. on Software Engineering, vol. 30, no. 6, pp.418-421, 2004.

F. Ensan, E. Bagheri, and D. Gasevic, “Evolutionary search-based test generation for software product line feature models,” in CAiSE, vol. 7328, 2012, pp. 613-628.

M. Muja, and DG. Lowe, “Scalable nearest neighbor algorithms for high dimensional data,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 36, no. 11, pp. 2227-2240, 2014.

M. Kowal, S. Schulze, and I. Schaefer. “Towards efficient SPL testing by variant reduction,” in Proc. of the 4th international workshop on Variability & composition, 2013, pp. 1-6.

H. Hemmati, and L. Briand, “An industrial investigation of similarity measures for model-based test case selection,” in 2010 IEEE 21st Int.Symposium on Software Reliability Engineering (ISSRE), 2010, pp. 141-150.

C. Fang, Z. Chen, K. Wu, and Z. Zhao, “Similarity-based test case prioritization using ordered sequences of program entities,” Software Quality Journal, vol. 22, no. 2, pp. 335-361, 2014.

Y. Ledru, A. Petrenko, S. Boroday, and N. Mandran. “Prioritizing test cases with string distances,” Automated Software Engineering, vol. 19, no. 1, pp.65-95, 2012

D. Hao, L. Zhang, L. Zang, Y. Wang, X. Wu, and T. Xie, “To be optimal or not in test-case prioritization,” IEEE Trans. on Software Engineering, vol. 42, no. 5 pp. 490-505, 2016.

W. Cohen, P. Ravikumar, and S. Fienberg. “A comparison of string metrics for matching names and records,” in KDD workshop on Data Cleaning and Object Consolidation, 2003, pp. 73-78.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

ISSN: 2180-1843

eISSN: 2289-8131