Ієрархічна модель систем автоматизованого генерування модульних тестів

Ключові слова: модульне тестування, символьне виконання, ефективність обчислень, якість програмного забезпечення, евристичні алгоритми

Анотація

Описано особливості проблеми тестування програмного забезпечення (ПЗ) за допомогою автоматизованих систем генерування модульних тестів. Проаналізовано методи автоматизованого модульного тестування, що використовуються для тестування ПЗ. Виконано класифікацію методів генерування модульних тестів на підставі вхідних даних і засобів для генерування тестів. Показано, що компільований байт-код та граф контролю потоку є основними видами вхідних даних, а символьне виконання є основним методом для генерування модульних тестів. Систематизовано новітні методи автоматизованого модульного тестування: символьне виконання з використанням штучних нейронних мереж, додаткової логіки та оптимізаційних алгоритмів. Проаналізовано можливості застосування мета- та гіперевристик системами автоматизованого генерування модульних тестів. Побудовано їх ієрархічну модель: до четвертого рівня віднесено пошукові алгоритми для аналізу умов у коді; до третього – SMT-бібліотеки, які містять множину алгоритмів першого рівня та стратегії їх використання; до другого – поєднання результатів роботи SMT-бібліотеки з результатами роботи додаткової логіки; до першого – алгоритм управління, що керують процесом генерування тестів. Описано можливості виконання паралельних обчислень на всіх рівнях ієрархії. Продемонстровано наявність вузьких місць у реалізаціях систем генерування модульних тестів. Запропоновано розподіл завдання генерування модульних тестів на підставі рівнів ієрархії моделі, що дає змогу обійти вузькі місця поточних систем та покращити масштабованість. Розроблено UML-діаграму класів на запропонованій моделі. Запропоновано одночасне використання метаевристик на всіх ієрархічних рівнях моделі для підвищення якості згенерованих тестів, що покращить універсальність і модульність системи. Обґрунтовано потребу подальшого розроблення нових методів для підвищення ефективності алгоритмів генерування тестів та якості тестування.

Біографії авторів

Р. П. Базилевич, Національний університет "Львівська політехніка", м. Львів

д-р техн. наук, професор, кафедра програмного забезпечення

А. В. Франко, Національний університет "Львівська політехніка", м. Львів

аспірант, кафедра програмного забезпечення

Посилання

Anand, S., Burke, E. K., Chen, T. Y., Clark, J., Cohen, M. B., Grieskamp, W., & Zhu, H. (2013). An orchestrated survey of methodologies for automated software test case generation. Journal of Systems and Software, 86(8), 1978-2001. https://doi.org/10.1016/j.jss.2013.02.061

Bjørner, N. (2018). Z3 and SMT in industrial R&D. Springer, Cham. In International Symposium on Formal Methods, 675–678. https://doi.org/10.1007/978-3-319-95582-7_44

Bucur, S., Ureche, V., Zamfir, C., & Candea, G. (2011). Parallel symbolic execution for automated real-world software testing. Proceedings of the Sixth Conference on Computer Systems – EuroSys 11. https://doi.org/10.1145/1966445.1966463

Cadar, C., Dunbar, D., & Engler, D. R. (2008). Klee: unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI, Vol. 8, 209–224.

Cadar, C., Ganesh, V., Pawlowski, P. M., Dill, D. L., & Engler, D. R. (2008). EXE. ACM Transactions on Information and System Security, 12(2), 1–38. https://doi.org/10.1145/1455518.1455522

Campos, J., Panichella, A., & Fraser, G. (2019). EvoSuite at the SBST 2019 Tool Competition. 2019 IEEE/ACM 12th International Workshop on Search-Based Software Testing (SBST). https://doi.org/10.1109/sbst.2019.00017

Chen, J., Hu, W., Zhang, L., Hao, D., Khurshid, S., & Zhang, L. (2018). Learning to accelerate symbolic execution via code transformation. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

Dutertre, B. (2014). Yices 2.2. Lecture Notes in Computer Science, 737–744. https://doi.org/10.1007/978-3-319-08867-9_49

Fraser, G., & Arcuri, A. (2011). EvoSuite. Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering – SIGSOFT/FSE 11. https://doi.org/10.1145/2025113.2025179

He, J., Balunović, M., Ambroladze, N., Tsankov, P., & Vechev, M. (2019). Learning to Fuzz from Symbolic Execution with Application to Smart Contracts. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. https://doi.org/10.1145/3319535.3363230

Kaner, C. (1997). The impossibility of complete testing. Software QA. Vol. 4, no. 4, 28 p.

Katz, G., Barrett, C., Dill, D. L., Julian, K., & Kochenderfer, M. J. (2017). Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. Lecture Notes in Computer Science, 97–117. https://doi.org/10.1007/978-3-319-63387-9_5

Lakhotia, K., Harman, M., & Gross, H. (2013). AUSTIN: An open source tool for search based software testing of C programs. Information and Software Technology, 55(1), 112–125. https://doi.org/10.1016/j.infsof.2012.03.009

Misailovic, S., Milicevic, A., Petrovic, N., Khurshid, S., & Marinov, D. (2007). Parallel test generation and execution with Korat. In Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, 135–144. https://doi.org/10.1145/1287624.1287645

Poeplau, S., & Francillon, A. (2020). Symbolic execution with SymCC: Dont interpret, compile!. In 29th Security Symposium (Security 20), 181–198.

Scalabrino, S., Grano, G., Di, Nucci, D., Guerra, M., De Lucia, A., Gall, H. C., & Oliveto, R. (2018). Ocelot: A search-based test-data generation tool for c. In 2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE), 868–871. https://doi.org/10.1145/3238147.3240477

Sen, K., Marinov, D., & Agha, G. (2005). CUTE: A concolic unit testing engine for C. ACM SIGSOFT Software Engineering Notes, 30(5), 263–272. https://doi.org/10.21236/ada482657

Shiqi, S., Shinde, S., Ramesh, S., Roychoudhury, A., & Saxena, P. (2019). Neuro-Symbolic Execution: Augmenting Symbolic Execution with Neural Constraints. Proceedings 2019 Network and Distributed System Security Symposium. https://doi.org/10.14722/ndss.2019.23530

Siddiqui, J. H., & Khurshid, S. (2010). ParSym: Parallel symbolic execution. 2010 2nd International Conference on Software Technology and Engineering. https://doi.org/10.1109/icste.2010.5608866

Staats, M., & Pǎsǎreanu, C. (2010). Parallel symbolic execution for structural test generation. Proceedings of the 19th International Symposium on Software Testing and Analysis – ISSTA 10. https://doi.org/10.1145/1831708.1831732

Wintersteiger, C. M., Hamadi, Y., & de Moura, L. (2009). A Concurrent Portfolio Approach to SMT Solving. Lecture Notes in Computer Science, 715–720. https://doi.org/10.1007/978-3-642-02658-4_60

Yoshida, H., et. al. (2017). KLOVER: Automatic Test Generation for C and C++ Programs, Using Symbolic Execution, in IEEE Software, vol. 34, no. 5, 30–37. https://doi.org/10.1109/MS.2017.3571576

Опубліковано
2021-11-25
Як цитувати
Базилевич, Р. П., & Франко, А. В. (2021). Ієрархічна модель систем автоматизованого генерування модульних тестів. Науковий вісник НЛТУ України, 31(5), 96-101. https://doi.org/10.36930/40310515
Розділ
Інформаційні технології