Microscale search-based algorithm based on time-space transfer for automated test case generation
Abstract Automated test case generation for path coverage (ATCG-PC) is a major challenge in search-based software engineering due to its complexity as a large-scale black-box optimization problem. However, existing search-based approaches often fail to achieve high path coverage in large-scale unit...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2025-01-01
|
| Series: | Complex & Intelligent Systems |
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s40747-024-01706-7 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1823861501102915584 |
|---|---|
| author | Yinghan Hong Fangqing Liu Han Huang Yi Xiang Xueming Yan Guizhen Mai |
| author_facet | Yinghan Hong Fangqing Liu Han Huang Yi Xiang Xueming Yan Guizhen Mai |
| author_sort | Yinghan Hong |
| collection | DOAJ |
| description | Abstract Automated test case generation for path coverage (ATCG-PC) is a major challenge in search-based software engineering due to its complexity as a large-scale black-box optimization problem. However, existing search-based approaches often fail to achieve high path coverage in large-scale unit programs. This is due to their expansive decision space and the presence of hundreds of feasible paths. In this paper, we present a microscale (small-size subsets of the decomposed decision set) search-based algorithm with time-space transfer (MISA-TST). This algorithm aims to identify more accurate subspaces consisting of optimal solutions based on two strategies. The dimension partition strategy employs a relationship matrix to track subspaces corresponding to the target paths. Additionally, the specific value strategy allows MISA-TST to focus the search on the neighborhood of specific dimension values rather than the entire dimension space. Experiments conducted on nine normal-scale and six large-scale benchmarks demonstrate the effectiveness of MISA-TST. The large-scale unit programs encompass hundreds of feasible paths or more than 1.00E+50 test cases. The results show that MISA-TST achieves significantly higher path coverage than other state-of-the-art algorithms in most benchmarks. Furthermore, the combination of the two time-space transfer strategies significantly enhances the performance of search-based algorithms like MISA, especially in large-scale unit programs. |
| format | Article |
| id | doaj-art-c3fde83e288746d087bcd6ffb24b80f3 |
| institution | Kabale University |
| issn | 2199-4536 2198-6053 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Springer |
| record_format | Article |
| series | Complex & Intelligent Systems |
| spelling | doaj-art-c3fde83e288746d087bcd6ffb24b80f32025-02-09T13:01:18ZengSpringerComplex & Intelligent Systems2199-45362198-60532025-01-0111211910.1007/s40747-024-01706-7Microscale search-based algorithm based on time-space transfer for automated test case generationYinghan Hong0Fangqing Liu1Han Huang2Yi Xiang3Xueming Yan4Guizhen Mai5School of Computer Science (School of Artificial Intelligence), Guangzhou Maritime UniversitySchool of Management, Guangdong University of TechnologySchool of Software Engineering, South China University of TechnologySchool of Software Engineering, South China University of TechnologySchool of Information Science and Technology, Guangdong University of Foreign StudiesSchool of Computer Science (School of Artificial Intelligence), Guangzhou Maritime UniversityAbstract Automated test case generation for path coverage (ATCG-PC) is a major challenge in search-based software engineering due to its complexity as a large-scale black-box optimization problem. However, existing search-based approaches often fail to achieve high path coverage in large-scale unit programs. This is due to their expansive decision space and the presence of hundreds of feasible paths. In this paper, we present a microscale (small-size subsets of the decomposed decision set) search-based algorithm with time-space transfer (MISA-TST). This algorithm aims to identify more accurate subspaces consisting of optimal solutions based on two strategies. The dimension partition strategy employs a relationship matrix to track subspaces corresponding to the target paths. Additionally, the specific value strategy allows MISA-TST to focus the search on the neighborhood of specific dimension values rather than the entire dimension space. Experiments conducted on nine normal-scale and six large-scale benchmarks demonstrate the effectiveness of MISA-TST. The large-scale unit programs encompass hundreds of feasible paths or more than 1.00E+50 test cases. The results show that MISA-TST achieves significantly higher path coverage than other state-of-the-art algorithms in most benchmarks. Furthermore, the combination of the two time-space transfer strategies significantly enhances the performance of search-based algorithms like MISA, especially in large-scale unit programs.https://doi.org/10.1007/s40747-024-01706-7Test case generationPath coverageLarge-scale optimizationRelationship matrixTime-space transfer |
| spellingShingle | Yinghan Hong Fangqing Liu Han Huang Yi Xiang Xueming Yan Guizhen Mai Microscale search-based algorithm based on time-space transfer for automated test case generation Complex & Intelligent Systems Test case generation Path coverage Large-scale optimization Relationship matrix Time-space transfer |
| title | Microscale search-based algorithm based on time-space transfer for automated test case generation |
| title_full | Microscale search-based algorithm based on time-space transfer for automated test case generation |
| title_fullStr | Microscale search-based algorithm based on time-space transfer for automated test case generation |
| title_full_unstemmed | Microscale search-based algorithm based on time-space transfer for automated test case generation |
| title_short | Microscale search-based algorithm based on time-space transfer for automated test case generation |
| title_sort | microscale search based algorithm based on time space transfer for automated test case generation |
| topic | Test case generation Path coverage Large-scale optimization Relationship matrix Time-space transfer |
| url | https://doi.org/10.1007/s40747-024-01706-7 |
| work_keys_str_mv | AT yinghanhong microscalesearchbasedalgorithmbasedontimespacetransferforautomatedtestcasegeneration AT fangqingliu microscalesearchbasedalgorithmbasedontimespacetransferforautomatedtestcasegeneration AT hanhuang microscalesearchbasedalgorithmbasedontimespacetransferforautomatedtestcasegeneration AT yixiang microscalesearchbasedalgorithmbasedontimespacetransferforautomatedtestcasegeneration AT xuemingyan microscalesearchbasedalgorithmbasedontimespacetransferforautomatedtestcasegeneration AT guizhenmai microscalesearchbasedalgorithmbasedontimespacetransferforautomatedtestcasegeneration |