|Table of Contents|

[1] Sun Jiaze, Wang Gang,. A hybrid algorithm based on ILP and genetic algorithmfor time-aware test case prioritization [J]. Journal of Southeast University (English Edition), 2018, 34 (1): 28-35. [doi:10.3969/j.issn.1003-7985.2018.01.005]
Copy

A hybrid algorithm based on ILP and genetic algorithmfor time-aware test case prioritization()
基于ILP和GA的时间感知测试用例优先排序混合算法
Share:

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
34
Issue:
2018 1
Page:
28-35
Research Field:
Computer Science and Engineering
Publishing date:
2018-03-20

Info

Title:
A hybrid algorithm based on ILP and genetic algorithmfor time-aware test case prioritization
基于ILP和GA的时间感知测试用例优先排序混合算法
Author(s):
Sun Jiaze1, 2, Wang Gang1
1School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
2Shaanxi Key Laboratory of Network Data Intelligent Processing, Xi’an University of Posts and Telecommunications, Xi’an 710121, China
孙家泽1, 2, 王刚1
1西安邮电大学计算机学院, 西安 710121; 2西安邮电大学陕西省网络数据智能处理重点实验室, 西安 710121
Keywords:
test case prioritization integer linear programming(ILP) genetic algorithm time constraint
测试用例优先排序 整数线性规划 遗传算法 时间约束
PACS:
TP311.53
DOI:
10.3969/j.issn.1003-7985.2018.01.005
Abstract:
To solve the problem of time-aware test case prioritization, a hybrid algorithm composed of integer linear programming and the genetic algorithm(ILP-GA)is proposed. First, the test case suite which can maximize the number of covered program entities and satisfy time constraints is selected by integer linear programming. Secondly, the individual is encoded according to the cover matrices of entities, and the coverage rate of program entities is used as the fitness function and the genetic algorithm is used to prioritize the selected test cases. Five typical open source projects are selected as benchmark programs. Branch and method are selected as program entities, and time constraint percentages are 25% and 75%. The experimental results show that the ILP-GA convergence has faster speed and better stability than ILP-additional and ILP-total in most cases, which contributes to the detection of software defects as early as possible and reduces the software testing costs.
针对基于时间感知的测试用例优先排序问题, 提出了整数线性规划与遗传算法相结合的混合求解算法. 首先, 基于整数线性规划, 选择待测程序实体的覆盖量最大且满足时间约束的测试用例集;然后, 根据程序实体覆盖矩阵对个体进行编码, 以程序实体覆盖速率作为适应度函数, 利用遗传算法对测试用例集进行排序.选择5个经典的基准开源项目进行实验, 以分支和方法作为程序实体, 时间约束分别为25%和75%.实验结果表明, 混合算法收敛速度快、稳定性好, 优于传统整数线性规划方法.该算法有助于尽早发现软件缺陷, 降低回归测试成本.

References:

[1] Chittimalli P K, Harrold M J. Recomputing cover age information to assist regression testing [J]. IEEE Transactions on Software Engineering, 2009, 35(4):452-469. DOI:10.1109/TSE.2009.4.
[2] Li Z, Harman M, Hierons R M. Search algorithms for regression test case prioritization [J]. IEEE Transactions on Software Engineering, 2007, 33(4):225-237. DOI: 10.1109/TSE.2007.38.
[3] Hao D, Zhang L M, Zhang L, et al. A unified test case prioritization approach [J]. ACM Transactions on Software Engineering and Methodology, 2014, 24(2):1-31. DOI:10.1145/2685614.
[4] Luo Q, Moran K, Poshyvanyk D. A large-scale empirical comparison of static and dynamic test case prioritization techniques[J]. Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. Seattle, WA, USA, 2016: 559-570. DOI:10.1145/2950290.2950344.
[5] Mei H, Hao D, Zhang L M, et al. A static approach to prioritizing junit test cases [J]. IEEE Transactions on Software Engineering, 2012, 38(6):1258-1275. DOI: 10.1109/TSE.2011.106.
[6] Walcott K R, Soffa M L, Kapfhammer G M, et al. Time aware test suite prioritization [C]//Proceedings of the 2006 International Symposium on Software Testing and Analysis. Portland, Maine, USA, 2006: 1-11. DOI:10.1145/1146238.1146240.
[7] Zhang L, Hou S S, Guo C, et al. Time-aware test case prioritization using integer linear programming[C]//Proceedings of the Eighteenth International Symposium on Software Testing and Analysis. Chicago, IL, USA, 2009: 213-224.DOI:10.1145/1572272.1572297.
[8] You D J, Chen Z Y, Xu B W, et al. An empirical study on the effectiveness of time-aware test case prioritization techniques [C]//Proceedings of the 26th ACM Symposium on Applied Computing. Taichung, China, 2011: 1451-1456. DOI:10.1145/1982185.1982497.
[9] Do H, Mirarab S, Tahvildari L, et al. The effects of time constraints on test case prioritization: A series of controlled experiments [J]. IEEE Transactions on Software Engineering, 2010, 36(5):593-617. DOI:10.1109/TSE.2010.58.
[10] Lu Y F, Lou Y L, Cheng S Y, et al. How does regression test prioritization perform in real-world software evolution [C]//Proceedings of the 38th International Conference on Software Engineering. Austin, TX, USA, 2016:535-546. DOI:10.1145/2884781.2884874.
[11] Yoo S, Harman M. Regression testing minimization, selection and prioritization: A survey [J]. Software Testing, Verification and Reliability, 2012, 22(2):67-120. DOI:10.1002/stvr.430.
[12] Alipour M A, Shi A, Gopinath R, et al. Evaluating non-adequate test case reduction [C]//Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering. Singapore, 2016: 16-26. DOI:10.1145/2970276.2970361.

Memo

Memo:
Biography: Sun Jiaze(1980—), male, doctor, associate professor, sunjiaze@126.com.
Foundation items: The Natural Science Foundation of Education Ministry of Shaanxi Province(No.15JK1672), the Industrial Research Project of Shaanxi Province(No.2017GY-092); Special Fund for Key Discipline Construction of General Institutions of Higher Education in Shaanxi Province.
Citation: Sun Jiaze, Wang Gang.A hybrid algorithm based on ILP and genetic algorithm for time-aware test case prioritization[J].Journal of Southeast University(English Edition), 2018, 34(1):28-35.DOI:10.3969/j.issn.1003-7985.2018.01.005.
Last Update: 2018-03-20