Оцінювання ефективності вдосконалених жадібного й дельта-дебагінг алгоритмів оптимізації тестових сценаріїв для C++ бібліотек
DOI:
https://doi.org/10.30837/2522-9818.2026.1.039Ключові слова:
програмне забезпечення; тестовий сценарій; алгоритм; оптимізація; покриття; часові витрати; дефектАнотація
Ефективна оптимізація тестових сценаріїв (ТС) є необхідною умовою для підвищення ефективності тестування С++ бібліотек. Предметом дослідження є алгоритми оптимізації ТС для C++ бібліотек. Мета роботи – підвищення ефективності тестування С++ бібліотек завдяки вдосконаленню класичного алгоритму жадібного формування (оптимізації) ТС і алгоритму дельта-дебагінг мінімізації ТС для С++ бібліотек. Завдання. Удосконалити жадібний алгоритм оптимізації ТС і усунути його детермінованість, що забезпечить ефективне стиснення ТС зі збереження гілкового покриття коду. Удосконалити алгоритм дельта-дебагінг мінімізації тестових сценаріїв для ТС із розрідженим розташуванням надлишкових дій. Оцінити ефективності вдосконалених алгоритмів оптимізації ТС для С++ бібліотек порівняно з класичними алгоритмами. У роботі застосовано такі методи: жадібний алгоритм оптимізації тестових сценаріїв, алгоритм дельта-дебагінг мінімізації ТС, математичне моделювання та методи статистичного аналізу. Ефективність удосконалених алгоритмів оцінено на основі статистичного аналізу 100 моделювань для кожного алгоритму на двох С++ бібліотеках із відкритим вихідним кодом різної структурної складності. Результати оцінювання ефективності вказують на те, що вдосконалені алгоритми забезпечують збереження (збільшення) гілкового покриття з коефіцієнтом до 1,058, підвищення коефіцієнта стиснення ТС до 0,86 та скорочення часу на виконання тестового набору (ТН) від 1,5 до 2,5 раза, якщо порівнювати з класичними алгоритмами. Висновки. Удосконалені алгоритми істотно зменшують час на тестування С++ бібліотек без втрати гілкового покриття коду. Запропоновано вдосконалений жадібний алгоритм оптимізації тестових сценаріїв, у якому вибір дій ТС здійснюється з огляду на їх майбутню користь, визначену за очікуваним приростом гілкового покриття коду. Такий підхід усуває детермінованість класичного жадібного алгоритму, підвищує інформативність тестових сценаріїв і забезпечує збалансованість між збереженням гілкового покриття та стисненням ТС. Запропоновано вдосконалений алгоритм дельта-дебагінгу, який виконує групове вилучення неунікальних дій ТС за внеском у гілкове покриття, що дає змогу суттєво знизити довжину тестових сценаріїв без втрати ефективності тестування.
Посилання
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
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Наше видання використовує положення про авторські права Creative Commons для журналів відкритого доступу.
Автори, які публікуються у цьому журналі, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0), котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.
Автори мають право укладати самостійні додаткові угоди щодо не комерційного та не ексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому журналі.
Політика журналу дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису опублікованої роботи, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи.
