Evaluation of the effecAtiveness of the enchanced greedyand delta-debugging test case optimization algorithms for C++ libraries
DOI:
https://doi.org/10.30837/2522-9818.2026.1.039Keywords:
software; test case; algorithm; optimization; coverage; time consumption; faultAbstract
Efficient optimization of test cases (TCs) is a necessary condition for improving the efficiency of testing C++ libraries. The subject of the research is test case optimization algorithms for C++ libraries. The purpose of this work is to improve the efficiency of C++ libraries testing by enhancing classical algorithms for greedy TC optimization and delta-debugging TC minimization. Goals. To improve the greedy TC optimization algorithm and eliminate its determinism, ensuring effective TC compression while preserving branch code coverage. To improve the delta-debugging TC minimization algorithm under conditions where redundant actions are sparsely distributed within TCs. To evaluate the effectiveness of the proposed algorithms in comparison with the classical algorithms. Methods. The study applies a greedy TC optimization algorithm, a delta-debugging TC minimization algorithm, mathematical modeling, and statistical analysis methods. The effectiveness of the improved algorithms is evaluated based on statistical analysis of 100 simulation runs for each algorithm on two open-source C++ libraries of different structural complexity. Results. The evaluation results indicate that the improved algorithms provide preservation (and possible increase) of branch coverage with coverage retention coefficient of up to 1.058, increase the TC compression ratio up to 0.86, and reduce the TS execution time by 1.5–2.5× compared to the classical algorithms. Conclusions. The improved algorithms significantly reduce the testing time of C++ libraries without loss of branch coverage. An improved greedy TC optimization algorithm is proposed, in which the selection of TC actions accounts for their future utility estimated by the expected increase in branch coverage. This approach removes the determinism of the classical greedy algorithm, increases the informativeness of TCs, and provides a balance between preserving branch coverage and TC compression. An improved delta-debugging algorithm is proposed that performs group removal of non-unique TC actions according to their contribution to branch coverage, which makes it possible to substantially reduce the length of TCs without losing testing effectiveness.
References
References
Hulevych, M. (2024), "CIDER: Assisted automation tool for C++ libraries testing", Control, Navigation and Communication Systems, Vol. 2, No. 76, pp. 74–77. DOI: https://doi.org/10.26906/sunz.2024.2.074
Hulevych, M., Kolomiitsev, O. (2025), "Automated test generation techniques for C++ software", Control, Navigation and Communication Systems, Vol. 2, No. 80, pp. 102–107. DOI: https://doi.org/10.26906/SUNZ.2025.2.102
Tallam, S., Gupta, N. (2005), "A concept analysis inspired greedy algorithm for test suite minimization", in Proceedings of the 6th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE ’05), Association for Computing Machinery, New York, NY, USA, pp. 35–42. DOI: https://doi.org/10.1145/1108792.1108802
Rehman Khan, S.U., Lee, S.P., Javaid, N., Abdul, W. (2018), "A Systematic Review on Test Suite Reduction: Approaches, Experiment’s Quality Evaluation, and Guidelines", IEEE Access, Vol. 6, pp. 11816–11841. DOI: https://doi.org/10.1109/ACCESS.2018.2809600
Yoo, S., Harman, M. (2012), "Regression testing minimization, selection and prioritization: A survey", Software Testing, Verification and Reliability, Vol. 22, No. 2, pp. 67–120. DOI: https://doi.org/10.1002/stvr.430
Noemmer, R., Haas, R. (2020), "An Evaluation of Test Suite Minimization Techniques", in Winkler, D., Biffl, S., Mendez, D. and Bergsmann, J. (Eds.), Software Quality: Quality Intelligence in Software and Systems Engineering (SWQD 2020), Springer, Vol. 371, pp. 51–66. DOI: https://doi.org/10.1007/978-3-030-35510-4_4
Li, Z., Harman, M., Hierons, R.M. (2007), "Search Algorithms for Regression Test Case Prioritization", IEEE Transactions on Software Engineering, Vol. 33, No. 4, pp. 225–237. DOI: https://doi.org/10.1109/TSE.2007.38
Yoo, S., Harman, M., Tonella, P., Susi, A. (2009), "Clustering test cases to achieve effective and scalable prioritisation incorporating expert knowledge", in Proceedings of the 18th International Symposium on Software Testing and Analysis (ISSTA 2009), Association for Computing Machinery, New York, NY, USA, pp. 201–212. DOI: https://doi.org/10.1145/1572272.1572296
Wang, S., Ali, S., Gotlieb, A., Liaaen, M. (2016), "A systematic test case selection methodology for product lines: Results and insights from an industrial case study", Empirical Software Engineering, Vol. 21, pp. 1586–1622. DOI: https://doi.org/10.1007/s10664-014-9345-5
Parsa, S., Khalilian, A. (2009), "A Bi-objective Model Inspired Greedy Algorithm for Test Suite Minimization", in Lee, Yh., Kim, Th., Fang, Wc. and Ślęzak, D. (Eds.), Future Generation Information Technology (FGIT 2009), Springer, Vol. 5899, pp. 208–215. DOI: https://doi.org/10.1007/978-3-642-10509-8_24
Jehan, S., Wotawa, F. (2023), "An Empirical Study of Greedy Test Suite Minimization Techniques Using Mutation Coverage", IEEE Access, Vol. 11, pp. 65427–65442. DOI: https://doi.org/10.1109/ACCESS.2023.3289073
Putra, A.W., Legowo, N. (2025), "Greedy Algorithm Implementation for Test Case Prioritization in the Regression Testing Phase", Journal of Computer Science, Vol. 21, No. 2, pp. 290–303. DOI: https://doi.org/10.3844/jcssp.2025.290.303
Górski, T. (2025), "Pattern-Based Test Suite Reduction Method for Smart Contracts", Applied Sciences, Vol. 15, No. 2, Article 620. DOI: https://doi.org/10.3390/app15020620
Lin, C.-T., Tang, K.-W., Wang, J.-S., Kapfhammer, G.M. (2017), "Empirically evaluating Greedy-based test suite reduction methods at different levels of test suite complexity", Science of Computer Programming, Vol. 150, pp. 1–25. DOI: https://doi.org/10.1016/j.scico.2017.05.004
Habib, A.S., Khan, S.U.R., Felix, E.A. (2023), "A systematic review on search-based test suite reduction: State-of-the-art, taxonomy, and future directions", IET Software, Vol. 17, No. 2, pp. 93–136. DOI: https://doi.org/10.1049/sfw2.12104
Li, F., Zhou, J., Li, Y., Hao, D., Zhang, L. (2022), "AGA: An Accelerated Greedy Additional Algorithm for Test Case Prioritization", IEEE Transactions on Software Engineering, Vol. 48, No. 12, pp. 5102–5119. DOI: https://doi.org/10.1109/TSE.2021.3137929
Pan, R., Ghaleb, T.A., Briand, L.C. (2024), "LTM: Scalable and Black-Box Similarity-Based Test Suite Minimization Based on Language Models", IEEE Transactions on Software Engineering, Vol. 50, No. 11, pp. 3053–3070. DOI: https://doi.org/10.1109/TSE.2024.3469582
Zhang, Q., Fang, C., Sun, W., Yu, S., Xu, Y., Liu, Y. (2022), "Test case prioritization using partial attention", Journal of Systems and Software, Vol. 192, Article 111419. DOI: https://doi.org/10.1016/j.jss.2022.111419
Zeller, A., Hildebrandt, R. (2002), "Simplifying and isolating failure-inducing input", IEEE Transactions on Software Engineering, Vol. 28, No. 2, pp. 183–200. DOI: https://doi.org/10.1109/32.988498
Cleve, H., Zeller, A. (2005), "Locating causes of program failures", in Proceedings of the 27th International Conference on Software Engineering (ICSE 2005), Association for Computing Machinery, New York, NY, USA, pp. 342–351. DOI: https://doi.org/10.1145/1062455.1062522
Harman, M., Hierons, R. (2001), "An overview of program slicing", Software Focus, Vol. 2, pp. 85–92. DOI: https://doi.org/10.1002/swf.41
Misherghi, G., Su, Z. (2006), "HDD: Hierarchical delta debugging", in Proceedings of the 28th International Conference on Software Engineering (ICSE 2006), Association for Computing Machinery, New York, NY, USA, pp. 142–151. DOI: https://doi.org/10.1145/1134285.1134307
Herfert, S., Patra, J., Pradel, M. (2017), "Automatically reducing tree-structured test inputs", in Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2017), IEEE, Urbana, IL, USA, pp. 861–871. DOI: https://doi.org/10.1109/ASE.2017.8115697
Wang, G., Wu, Y., Zhu, Q., Xiong, Y., Zhang, X., Zhang, L. (2023), "A Probabilistic Delta Debugging Approach for Abstract Syntax Trees", in Proceedings of the 34th IEEE International Symposium on Software Reliability Engineering (ISSRE 2023), IEEE, Florence, Italy, pp. 763–773. DOI: https://doi.org/10.1109/ISSRE59848.2023.00060
Zhou, X., Xu, Z., Zhang, M., Tian, Y., Sun, C. (2025), "WDD: Weighted Delta Debugging", in Proceedings of the 47th IEEE/ACM International Conference on Software Engineering (ICSE 2025), IEEE, Ottawa, ON, Canada, pp. 1592–1603. DOI: https://doi.org/10.1109/ICSE55347.2025.00071
Vince, D., Hodován, R., Bársony, D., Kiss, Á. (2022), "The effect of hoisting on variants of Hierarchical Delta Debugging", Journal of Software: Evolution and Process, Vol. 34, No. 11, Article e2483. DOI: https://doi.org/10.1002/smr.2483
Zhang, M., Xu, Z., Tian, Y., Cheng, X., Sun, C. (2025), "Toward a Better Understanding of Probabilistic Delta Debugging", in Proceedings of the 47th IEEE/ACM International Conference on Software Engineering (ICSE 2025), IEEE, Ottawa, ON, Canada, pp. 2024–2035. DOI: https://doi.org/10.1109/ICSE55347.2025.00117
Pontolillo, G.J., Mousavi, M.R. (2024), "Delta Debugging for Property-Based Regression Testing of Quantum Programs’, in Proceedings of the 5th ACM/IEEE International Workshop on Quantum Software Engineering (Q-SE 2024), Association for Computing Machinery, New York, NY, USA, pp. 1–8. DOI: https://doi.org/10.1145/3643667.3648219
Hoen, A., Kamp, D., Gleixner, A. (2025), "MIP-DD: Delta Debugging for Mixed-Integer Programming Solvers", INFORMS Journal on Computing. Advance online publication. DOI: https://doi.org/10.1287/ijoc.2024.0844
Vince, D., Kiss, Á. (2024), "Evaluation of the fixed-point iteration of minimizing delta debugging", Journal of Software: Evolution and Process, Vol. 36, No. 10, Article e2702. DOI: https://doi.org/10.1002/smr.2702
Kuchuk, N., Kashkevich, S., Radchenko, V., Andrusenko, Y., Kuchuk, H. (2024), “Applying edge computing in the execution IoT operative transactions”, Advanced Information Systems, Vol. 8, No. 4, pp. 49–59. DOI: https://doi.org/10.20998/2522-9052.2024.4.07
Durmaz, E., Tümer, M.B. (2022), "Intelligent software debugging: A reinforcement learning approach for detecting the shortest crashing scenarios", Expert Systems with Applications, Vol. 198, Article 116722. DOI: https://doi.org/10.1016/j.eswa.2022.116722
Kuchuk, H., Kalinin, Y., Dotsenko, N., Chumachenko, I., Pakhomov, Y. (2024), "Decomposition of integrated high-density IoT data flow", Advanced Information Systems, Vol. 8, No. 3, pp. 77–84. DOI: https://doi.org/10.20998/2522-9052.2024.3.09
Semenov, S., Kolomiitsev, O., Hulevych, M., Mazurek, P., Chernyk, O. (2025), "An Intelligent Method for C++ Test Case Synthesis Based on a Q-Learning Agent", Applied Sciences, Vol. 15, No. 15, Article 8596. DOI: https://doi.org/10.3390/app15158596 35. Hulevych М. (2025), "Evaluation of the effectiveness of the test scenarios forming method for C++ libraries based on a Q-learning agent", Management Information Systems and Devises, No. 4 (187). pp. 20–46. DOI: https://doi.org/10.30837/0135-1710.2025.187.020
Puterman, M.L. (1994), Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, New York. DOI: https://doi.org/10.1002/9780470316887
Shmatko O., Kolomiitsev O., Rekova N., Kuchuk N., Matvieiev O. (2023), "Designing and Evaluating DL-Model for Vulnerability Detection in Smart Contracts", Advanced Information Systems, Vol. 7, No. 4, pp. 41–51. DOI: https://doi.org/10.20998/2522-9052.2023.4.05
Fedorchenko V., Yeroshenko O., Shmatko O., Kolomiitsev O., Omarov M. (2024), "Password Hashing Methods and Algorithms on the .NET Platform", Advanced Information Systems, Vol. 8, No. 4, pp. 82–92. DOI: https://doi.org/10.20998/2522-9052.2024.4.11
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Our journal abides by the Creative Commons copyright rights and permissions for open access journals.
Authors who publish with this journal agree to the following terms:
Authors hold the copyright without restrictions and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-commercial and non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
Authors are permitted and encouraged to post their published work online (e.g., in institutional repositories or on their website) as it can lead to productive exchanges, as well as earlier and greater citation of published work.
