CLUE: A CLUSTERING-BASED TEST REDUCTION APPROACH FOR SOFTWARE PRODUCT LINES
Author affiliations
DOI:
https://doi.org/10.15625/1813-9663/19694Keywords:
Test reduction, Software product line, Clustering, Feature interaction, Fault localizationAbstract
Nowadays, organizations have increasingly turned to software product lines (SPLs)/configurable systems to meet diverse user needs and market demands. SPLs offer configurability and scalability but pose a formidable challenge in testing. Assuring the quality of variants across numerous configurations demands innovative testing strategies that balance effectiveness and efficiency. To improve testing productivity, test reduction techniques have been widely employed in non-configurable code. However, test reduction for SPL systems remains mostly unexplored. This paper introduces CLUE, a novel test reduction approach to enhance testing productivity in SPLs. Our idea is that to effectively and efficiently reveal failures, tests should be distinctive and cover diverse behaviors of the system. Meanwhile, similar tests covering the same/similar behaviors of an SPL system do not need to be redundantly executed multiple times. CLUE clusters the system’s tests into distinctive groups containing similar tests. Within each cluster, tests are prioritized based on the number of feature interactions, a common root cause of defects in SPLs. CLUE continually selects and executes the top-prioritized test in each cluster until a bug is revealed or the allocated effort budget is exhausted. To evaluate CLUE, we conducted several experiments on a dataset of six widely-used SPL systems. The results show that CLUE enables developers to detect defects earlier, requiring up to 88% less effort than existing approaches. Additionally, using only 50% of the original test suites, CLUE can identify most of the bugs in the buggy SPL systems while maintaining fault localization performance.
Metrics
References
I. Abal, C. Brabrand, and A. Wasowski, “42 variability bugs in the linux kernel: a qualitative
analysis,” in Proceedings of the 29th ACM/IEEE international conference on Automated software
engineering, 2014, pp. 421–432.
I. Abal, J. Melo, S¸. St˘anciulescu, C. Brabrand, M. Ribeiro, and A. Wasowski, “Variability
bugs in highly configurable systems: A qualitative analysis,” ACM Transactions on Software
Engineering and Methodology (TOSEM), vol. 26, no. 3, pp. 1–34, 2018.
M. Abdelkarim and R. ElAdawi, “Tcp-net: Test case prioritization using end-to-end deep
neural networks,” in 2022 IEEE International Conference on Software Testing, Verification and
Validation Workshops (ICSTW). Los Alamitos, CA, USA: IEEE Computer Society, apr 2022,
pp. 122–129. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/ICSTW55395.
00034
M. R. Ackermann, J. Bl¨omer, D. Kuntze, and C. Sohler, “Analysis of agglomerative clustering,”
Algorithmica, vol. 69, pp. 184–215, 2014.
M. Al-Hajjaji, S. Krieter, T. Th¨um, M. Lochau, and G. Saake, “Incling: efficient product-line
testing using incremental pairwise sampling,” ACM SIGPLAN Notices, vol. 52, no. 3, pp. 144–
, 2016.
M. Al-Hajjaji, T. Th¨um, M. Lochau, J. Meinicke, and G. Saake, “Effective product-line testing
using similarity-based product prioritization,” Software & Systems Modeling, vol. 18, pp. 499–
, 2019.
M. Al-Hajjaji, T. Th¨um, J. Meinicke, M. Lochau, and G. Saake, “Similarity-based prioritization
in software product-line testing,” in Proceedings of the 18th International Software Product Line
Conference-Volume 1, 2014, pp. 197–206.
S. Apel, D. Batory, C. K¨astner, and G. Saake, Feature-Oriented Software Product Lines: Concepts and Implementation. Springer Publishing Company, Incorporated, 2013.
A. Arrieta, S. Segura, U. Markiegi, G. Sagardui, and L. Etxeberria, “Spectrum-based fault
localization in software product lines,” Information and Software Technology, vol. 100, pp. 18–
, 2018.
M. Azizi and H. Do, “Retest: A cost effective test case selection technique for modern software
development,” in 2018 IEEE 29th International Symposium on Software Reliability Engineering
(ISSRE), 2018, pp. 144–154.
H. B¨acklund, A. Hedblom, and N. Neijman, “A density-based spatial clustering of application
with noise,” Data Mining TNM033, vol. 33, pp. 11–30, 2011.
C. Birchler, S. Khatiri, P. Derakhshanfar, S. Panichella, and A. Panichella, “Single and multiobjective test cases prioritization for self-driving cars in virtual environments,” ACM Transactions on Software Engineering and Methodology, vol. 32, no. 2, pp. 1–30, 2023.
E. Bodden, T. Tolˆedo, M. Ribeiro, C. Brabrand, P. Borba, and M. Mezini, “Spllift: Statically
analyzing software product lines in minutes instead of years,” ACM SIGPLAN Notices, vol. 48,
no. 6, pp. 355–364, 2013.
I. Cabral, M. B. Cohen, and G. Rothermel, “Improving the testing and testability of software
product lines,” in International Conference on Software Product Lines. Springer, 2010, pp.
–255.
T. Y. Chen and M. F. Lau, “Dividing strategies for the optimization of a test suite,” Information
Processing Letters, vol. 60, no. 3, pp. 135–141, 1996.
C. Coviello, S. Romano, G. Scanniello, A. Marchetto, A. Corazza, and G. Antoniol, “Adequate
vs. inadequate test suite reduction approaches,” Information and Software Technology, vol. 119,
p. 106224, 2020.
Z. Ding, H. Li, W. Shang, and T.-H. P. Chen, “Can pre-trained code embeddings improve model
performance? revisiting the use of code embeddings in software engineering tasks,” Empirical
Software Engineering, vol. 27, no. 3, pp. 1–38, 2022.
I. do Carmo Machado, J. D. McGregor, Y. C. Cavalcanti, and E. S. De Almeida, “On strategies
for testing software product lines: A systematic literature review,” Information and Software
Technology, vol. 56, no. 10, pp. 1183–1199, 2014.
S. Elbaum, G. Rothermel, S. Kanduri, and A. G. Malishevsky, “Selecting a cost-effective test
case prioritization technique,” Software Quality Journal, vol. 12, pp. 185–210, 2004.
B. J. Garvin and M. B. Cohen, “Feature interaction faults revisited: An exploratory study,” in
IEEE 22nd International Symposium on Software Reliability Engineering. IEEE, 2011,
pp. 90–99.
J. Goldberger and S. Roweis, “Hierarchical clustering of a mixture model,” Advances in neural
information processing systems, vol. 17, 2004.
M. Greiler, A. van Deursen, and M.-A. Storey, “Test confessions: A study of testing practices
for plug-in systems,” in 2012 34th International Conference on Software Engineering (ICSE).
IEEE, 2012, pp. 244–254.
M. J. Harrold, J. A. Jones, T. Li, D. Liang, A. Orso, M. Pennings, S. Sinha, S. A. Spoon, and
A. Gujarathi, “Regression test selection for java software,” ACM Sigplan Notices, vol. 36, no. 11,
pp. 312–326, 2001.
J. R. Horgan and S. London, “A data flow coverage testing tool for c,” in Proceedings of the
Second Symposium on Assessment of Quality Software Development Tools. IEEE Computer
Society, 1992, pp. 2–3.
M. F. Johansen, Ø. Haugen, and F. Fleurey, “An algorithm for generating t-wise covering arrays from large feature models,” in Proceedings of the 16th International Software Product Line
Conference-Volume 1, 2012, pp. 46–55.
C. K¨astner, S. Apel, T. Th¨um, and G. Saake, “Type checking annotation-based product lines,”
ACM Transactions on Software Engineering and Methodology, vol. 21, no. 3, pp. 1–39, 2012.
J. Liebig, A. Von Rhein, C. K¨astner, S. Apel, J. D¨orre, and C. Lengauer, “Scalable analysis
of variable software,” in Proceedings of the 2013 9th Joint Meeting on Foundations of Software
Engineering, 2013, pp. 81–91.
A. Likas, N. Vlassis, and J. J. Verbeek, “The global k-means clustering algorithm,” Pattern
recognition, vol. 36, no. 2, pp. 451–461, 2003.
W. Masri and R. A. Assi, “Prevalence of coincidental correctness and mitigation of its impact
on fault localization,” ACM transactions on software engineering and methodology (TOSEM),
vol. 23, no. 1, pp. 1–28, 2014.
F. Medeiros, C. K¨astner, M. Ribeiro, R. Gheyi, and S. Apel, “A comparison of 10 sampling
algorithms for configurable systems,” in 2016 IEEE/ACM 38th International Conference on
Software Engineering (ICSE). IEEE, 2016, pp. 643–654.
J. Meinicke, C.-P. Wong, C. K¨astner, T. Th¨um, and G. Saake, “On essential configuration
complexity: measuring interactions in highly-configurable systems,” in Proceedings of the 31st
IEEE/ACM International Conference on Automated Software Engineering, 2016, pp. 483–494.
T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations
in vector space,” in 1st International Conference on Learning Representations, ICLR 2013,
Scottsdale, Arizona, USA, May 2-4, 2013, Y. Bengio and Y. LeCun, Eds., 2013.
K.-T. Ngo, T.-T. Nguyen, S. Nguyen, and H. D. Vo, “Variability fault localization: A benchmark,” in Proceedings of the 25th ACM International Systems and Software Product Line Conference - Volume A, ser. SPLC ’21, 2021, p. 120–125.
——, “Variability fault localization: a benchmark,” in Proceedings of the 25th ACM International
Systems and Software Product Line Conference-Volume A, 2021, pp. 120–125.
S. Nguyen, H. Nguyen, N. Tran, H. Tran, and T. Nguyen, “Feature-interaction aware configuration prioritization for configurable code,” in 2019 34th IEEE/ACM International Conference
on Automated Software Engineering (ASE). IEEE, 2019, pp. 489–501.
T.-T. Nguyen, K.-T. Ngo, S. Nguyen, and H. D. Vo, “A variability fault localization approach
for software product lines,” IEEE Transactions on Software Engineering, vol. 48, no. 10, pp.
–4118, 2021.
——, “Detecting false-passing products and mitigating their impact on variability fault localization in software product lines,” Information and Software Technology, vol. 153, p. 107080,
T.-T. Nguyen and H. D. Vo, “Detecting coincidental correctness and mitigating its impacts on
localizing variability faults,” in 2022 14th International Conference on Knowledge and Systems
Engineering (KSE). IEEE, 2022, pp. 1–6.
S. Niwattanakul, J. Singthongchai, E. Naenudorn, and S. Wanapu, “Using of jaccard coefficient
for keywords similarity,” in Proceedings of the international multiconference of engineers and
computer scientists, vol. 1, no. 6, 2013, pp. 380–384.
S. Oster, F. Markert, and P. Ritter, “Automated incremental pairwise testing of software product
lines,” in International Conference on Software Product Lines. Springer, 2010, pp. 196–210.
S. Pearson, J. Campos, R. Just, G. Fraser, R. Abreu, M. D. Ernst, D. Pang, and B. Keller,
“Evaluating & improving fault localization techniques,” University of Washington Department
of Computer Science and Engineering, Seattle, WA, USA, Tech. Rep. UW-CSE-16-08-03, p. 27,
——, “Evaluating and improving fault localization,” in 2017 IEEE/ACM 39th International
Conference on Software Engineering (ICSE). IEEE, 2017, pp. 609–620.
A. Perez, R. Abreu, and A. Van Deursen, “A theoretical and empirical analysis of program
spectra diagnosability,” IEEE Transactions on Software Engineering, vol. 47, no. 2, pp. 412–
, 2019.
X. Ren, F. Shah, F. Tip, B. G. Ryder, O. Chesley, and J. Dolby, “Chianti: A prototype change
impact analysis tool for java,” Rutgers University, Tech. Rep., 2003.
G. Rothermel, R. Untch, C. Chu, and M. Harrold, “Test case prioritization: an empirical study,”
in Proceedings IEEE International Conference on Software Maintenance - 1999 (ICSM’99). ’Software Maintenance for Business Change’ (Cat. No.99CB36360), 1999, pp. 179–188.
G. Rothermel and M. J. Harrold, “A safe, efficient regression test selection technique,” ACM
Transactions on Software Engineering and Methodology (TOSEM), vol. 6, no. 2, pp. 173–210,
L. R. Soares, J. Meinicke, S. Nadi, C. K¨astner, and E. S. de Almeida, “Exploring feature interactions without specifications: A controlled experiment,” ACM SIGPLAN Notices, vol. 53,
no. 9, pp. 40–52, 2018.
X. Wang and S. Zhang, “Cluster-based adaptive test case prioritization,” Information and Software Technology, p. 107339, 2023.
C.-P. Wong, J. Meinicke, L. Lazarek, and C. K¨astner, “Faster variational execution with transparent bytecode transformation,” Proceedings of the ACM on Programming Languages, vol. 2,
no. OOPSLA, pp. 1–30, 2018.
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.
H. Zhong, L. Zhang, and H. Mei, “An experimental study of four typical test suite reduction
techniques,” Information and Software Technology, vol. 50, no. 6, pp. 534–546, 2008.
Downloads
Published
How to Cite
Issue
Section
License
1. We hereby assign copyright of our article (the Work) in all forms of media, whether now known or hereafter developed, to the Journal of Computer Science and Cybernetics. We understand that the Journal of Computer Science and Cybernetics will act on my/our behalf to publish, reproduce, distribute and transmit the Work.2. This assignment of copyright to the Journal of Computer Science and Cybernetics is done so on the understanding that permission from the Journal of Computer Science and Cybernetics is not required for me/us to reproduce, republish or distribute copies of the Work in whole or in part. We will ensure that all such copies carry a notice of copyright ownership and reference to the original journal publication.
3. We warrant that the Work is our results and has not been published before in its current or a substantially similar form and is not under consideration for another publication, does not contain any unlawful statements and does not infringe any existing copyright.
4. We also warrant that We have obtained the necessary permission from the copyright holder/s to reproduce in the article any materials including tables, diagrams or photographs not owned by me/us.
