Оцінювання ефективності методу формування тестових сценаріїв для C++ бібліотек на основі агента з Q-навчанням
DOI:
https://doi.org/10.30837/0135-1710.2025.187.020Ключові слова:
оптимізація тестових сценаріїв, тестування програмного забезпечення, Q-навчання, Q-таблиця, дельта-дебаггінг, покриття коду, мінімізація, C , агент, навчання з підкріпленнямАнотація
Оптимізація тестових сценаріїв (ТС) є необхідною умовою підвищення ефективності регресійного тестування C++ бібліотек. Предметом дослідження є методи формування (оптимізації) ТС для C++ бібліотек. Мета роботи – оцінити ефективність методу формування ТС для С++ бібліотек на основі агента з Q‑навчанням. Завдання дослідження: удосконалити математичну модель агента з Q-навчанням для підвищення ефективності формування ТС для С++ бібліотек в умовах високої розрідженості простору станів агента з Q‑навчанням; дослідити вплив параметрів удосконаленої моделі агента з Q-навчанням на його поведінку за такими умовами; розглянути можливість мінімізації сформованих ТС методом їх формування завдяки алгоритму дельта‑дебаггінг мінімізації ТС; оцінити ефективність запропонованого методу й порівняти з відомими методами оптимізації ТС. Методи дослідження. У роботі застосовано метод пошуку на дереві Монте-Карло, класичну математичну модель Q-навчання, алгоритм дельта-дебаггінг мінімізації ТС і жадібний алгоритм оптимізації ТС. Ефективність запропонованого методу оцінено на двох C++ бібліотеках з відкритим вихідним кодом за допомогою статистичного аналізу 100 математичних моделювань конфігурацій методів, які досліджуються. Досягнуті результати: оцінка ефективності вказує на те, що запропонований метод забезпечує такі середні значення показників ефективності оптимізації ТС для С++ бібліотек: коефіцієнт збереження покриття становить до 1.225, коефіцієнт стиснення тестового набору (ТН) – до 0.86 й коефіцієнт скорочення часу на виконання ТН – до 0.74. Установлено, якщо порівнювати з жадібним алгоритмом оптимізації ТС, дельта-дебаггінг алгоритмом мінімізації ТС та методом оптимізації ТС на основі пошуку на дереві Монте-Карло, то запропонований метод має суттєве підвищення ефективності формування (оптимізації) ТС для С++ бібліотек. Висновки. Удосконалена математична модель забезпечує узагальнення досвіду агента з Q-навчанням між подібними ТС і підвищує ефективність їх формування в умовах високої розрідженості простору станів агента з Q-навчанням. Отже, за результатами оцінювання методу формування ТС для С++ бібліотек на основі агента з Q-навчанням підтверджено його доцільність у розв’язанні задачі формування (оптимізації) ТС для C++ бібліотек, що дає змогу скоротити довжину ТС без втрати гілкового покриття коду С++ бібліотеки, яка тестується, і зменшити час на виконання ТН. Подальші дослідження будуть присвячені формуванню ТС для С++ бібліотек на основі агента глибинного навчання з підкріпленням.
Посилання
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(15), Art. No. 8596. DOI: https://doi.org/10.3390/app15158596
Alian, M., Suleiman, D., Shaout, A. (2016), "Test Case Reduction Techniques – Survey", International Journal of Advanced Computer Science and Applications, Vol. 7(5), P. 264–275. DOI: https://doi.org/10.14569/IJACSA.2016.070537
Khan, S. U. R., Lee, S., Javaid, N., Abdul, W. (2018), "A Systematic Review on Test Suite Reduction: Approaches, Experiment’s Quality Evaluation, and Guidelines", IEEE Access, Vol. 6, P. 11816-11841. DOI: https://doi.org/10.1109/ACCESS.2018.2809600
Rahman, M., Zamli, K., Kader, M., Sidek, R., Din, F. (2024), "Comprehensive Review on the State-of-the-arts and Solutions to the Test Redundancy Reduction Problem with Taxonomy", Journal of Advanced Research in Applied Sciences and Engineering Technology, Vol. 35(1), P. 62–87. DOI: https://doi.org/10.37934/araset.34.3.6287
Marappan, R., Raja, S. (2025), "Recent Trends in Regression Testing: Modeling and Analyzing the Critiques in Selection, Optimization, and Prioritization", National Academy Science Letters. DOI: https://doi.org/10.1007/s40009-025-01613-6
Fontes, A., Gay, G. (2023), "The integration of machine learning into automated test generation: A systematic mapping study", Software Testing, Verification and Reliability, Vol. 33(4), e1845. DOI: https://doi.org/10.1002/stvr.1845
Sebastian, A., Naseem, H., Catal, C. (2024), "Unsupervised Machine Learning Approaches for Test Suite Reduction", Applied Artificial Intelligence, Vol. 38(1), Art. No. 2322336. DOI: https://doi.org/10.1080/08839514.2024.2322336
Nayab, S., Wotawa, F. (2024), "Testing and Reinforcement Learning: A Structured Literature Review", 2024 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C), Cambridge, United Kingdom, 2024, P. 326-335. DOI: https://doi.org/10.1109/QRS-C63300.2024.00049
Coviello, C., Romano, S., Scanniello, G., Marchetto, A., Corazza, A., Antoniol, G. (2019), "Adequate vs. inadequate test suite reduction approaches", Information and Software Technology, Vol. 119, Art. No. 106224. DOI: https://doi.org/10.1016/j.infsof.2019.106224
Hulevych, M., Kolomiitsev, O. (2025), "Automated Test Generation Techniques for C++ Software", Control, Navigation and Communication Systems, Vol. 2(80), P. 102-107. DOI: https://doi.org/10.26906/SUNZ.2025.2.102
Pan, R., Ghaleb, T. A., Briand, L. (2023), "ATM: Black-box Test Case Minimization Based on Test Code Similarity and Evolutionary Search", Proceedings of the 45th International Conference on Software Engineering (ICSE ’23), Melbourne, Australia, 2023, pp. 1700-1711. DOI: https://doi.org/10.1109/ICSE48619.2023.00146
Koitz‐Hristov, R., Sterner, T., Stracke, L., Wotawa, F. (2024), "On the suitability of checked coverage and genetic parameter tuning in test suite reduction", Journal of Software: Evolution and Process, Vol. 36(8), e2656. DOI: https://doi.org/10.1002/smr.2656
Dang, Z., Wang, H. (2024), "Leveraging meta-heuristic algorithms for effective software fault prediction: A comprehensive study", Journal of Engineering and Applied Science, Vol. 71, Art. No. 189. DOI: https://doi.org/10.1186/s44147-024-00529-0
Rheaf, T. S. (2025), "Prioritization of Modules to Reduce Software Testing Time and Costs Using Evolutionary Algorithms and the KLOC Method", Journal of Education for Pure Science, Vol. 15(1). P. 116-131. DOI: https://doi.org/10.32792/jeps.v15i1.658
Bai, R., Chen, R., Lei, X., Wu, K. (2024), "A Test Report Optimization Method Fusing Reinforcement Learning and Genetic Algorithms", Electronics, Vol. 13(21), Art. No. 4281. DOI: https://doi.org/10.3390/electronics13214281
Świechowski, M., Godlewski, K., Sawicki, B., Mańdziuk, J. (2023), "Monte Carlo Tree Search: A review of recent modifications and applications", Artificial Intelligence Review, Vol. 56, P. 2497–2562. DOI: https://doi.org/10.1007/s10462-022-10228-y
Ye, A., Wang, L., Zhao, L., Ke, J. (2022), "Ex²: Monte Carlo Tree Search-based test inputs prioritization for fuzzing deep neural networks", International Journal of Intelligent Systems, Vol. 37(12), P. 11966–11984. DOI: https://doi.org/10.1002/int.23072
Kocsis, L.; Szepesvári, C. (2006), "Bandit Based Monte-Carlo Planning", Lecture Notes in Computer Science (ECML 2006), Vol. 4212, P. 282-293. DOI: https://doi.org/10.1007/11871842_29
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, P. 1-25. DOI: https://doi.org/10.1016/j.scico.2017.05.004
Parsa, S.; Khalilian, A. (2009), "A Bi-objective Model Inspired Greedy Algorithm for Test Suite Minimization", Lecture Notes in Computer Science (FGIT 2009) Vol. 5899, P. 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, P. 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(2), P. 290–303. DOI: https://doi.org/10.3844/jcssp.2025.290.303
Zeller, A., Hildebrandt, R. (2002), "Simplifying and isolating failure-inducing input", IEEE Transactions on Software Engineering, Vol. 28(2), P. 183–200. DOI: https://doi.org/10.1109/32.988498
Cleve, H., Zeller, A. (2005), "Locating causes of program failures", Proceedings of the 27th International Conference on Software Engineering (ICSE ’05), Association for Computing Machinery, New York, USA, 2005, P. 342–351. DOI: https://doi.org/10.1145/1062455.1062522
Misherghi, G., Su, Z. (2006), "HDD: Hierarchical delta debugging", Proceedings of the 28th International Conference on Software Engineering (ICSE ’06), Association for Computing Machinery, New York, USA, 2006, P. 142–151. DOI: https://doi.org/10.1145/1134285.1134307
Wang, G., Wu, Y., Zhu, Q., Xiong, Y., Zhang, X., Zhang, L. (2023), "A Probabilistic Delta Debugging Approach for Abstract Syntax Trees", 2023 IEEE 34th International Symposium on Software Reliability Engineering (ISSRE), Florence, Italy, 2023, pp. 763–773. DOI: https://doi.org/10.1109/ISSRE59848.2023.00060
Puterman, M. L. (1994), "Markov Decision Processes: Discrete Stochastic Dynamic Programming", John Wiley & Sons. DOI: https://doi.org/10.1002/9780470316887
Singh, S. P. (1992), "Transfer of learning by composing solutions of elemental sequential tasks", Machine Learning, Vol. 8, P. 323–339. DOI: https://doi.org/10.1007/BF00992700
Sutton, R. S., Barto, A. G. (2018), "Reinforcement Learning: An Introduction", (2nd ed.). MIT Press.
Li, L., Walsh, T. J., Littman, M. L. (2006), "Towards a Unified Theory of State Abstraction for MDPs", Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics, 2006.
Watkins, C.J.C.H., Dayan, P. (1992), "Q-learning", Machine Learning, Vol. 8, P. 279–292. DOI: https://doi.org/10.1007/BF00992698
Hasselt, H. (2010), "Double Q-learning", Advances in Neural Information Processing Systems (NIPS 2010), Vol. 23.
Groce, A., Alipour, M. A., Zhang, C., Chen, Y., Regehr, J. (2016), "Cause reduction: Delta debugging, even without bugs", Software Testing, Verification and Reliability, Vol. 26, P. 40–68. DOI: https://doi.org/10.1002/stvr.1574
Auer, P., Cesa-Bianchi, N., Fischer, P. (2002), "Finite-time Analysis of the Multiarmed Bandit Problem", Machine Learning, Vol. 47, P. 235–256. DOI: https://doi.org/10.1023/A:1013689704352
UA 
EN 
