利用改进遗传算法的软件故障定位辅助测试用例生成方法

杨波; 何宇泽; 许福; 陈志泊

doi:10.13700/j.bh.1001-5965.2022.0524

利用改进遗传算法的软件故障定位辅助测试用例生成方法

doi: 10.13700/j.bh.1001-5965.2022.0524

杨波^{1, 2, 3},
何宇泽³,
许福^{1, 2, ,},
陈志泊^{1, 2}

1.
北京林业大学信息学院，北京 100083
2.
国家林业和草原局林业智能信息处理工程技术研究中心，北京 100083
3.
北方工业大学信息学院，北京 100144

基金项目: 中央高校基本科研业务费专项资金(BLX202003)；国家自然科学基金(61502011)；北京林业大学热点追踪项目(BLRD202124)

详细信息

通讯作者:
E-mail：xufu@bjfu.edu.cn

中图分类号: V221⁺.3；TB553
计量
- 文章访问数: 333
- HTML全文浏览量: 106
- PDF下载量: 43
- 被引次数: 0
出版历程
- 收稿日期: 2022-06-22
- 录用日期: 2022-08-15
- 网络出版日期: 2022-11-18
- 整期出版日期: 2023-10-01

Using improved genetic algorithm for software fault localization aided test case generation

YANG Bo^{1, 2, 3},
HE Yuze³,
XU Fu^{1, 2
, ,},
CHEN Zhibo^{1, 2}

1.
School of Information，Beijing Forestry University，Beijing 100083，China
2.
Engineering Research Center for Forestry Goriented Intelligent Information Processing，National Forestry and Grassland Administration，Beijing 100083，China
3.
School of Information，North China of Science and Technology，Beijing 100144，China

Funds: Fundamental Research Funds for the Central Universities (BLX202003)； National Natural Science Foundation of China (61502011)；Focus Tracking Project of Beijing Forestry University (BLRD202124)

More Information

Corresponding author: E-mail：xufu@bjfu.edu.cn

摘要

摘要:
在软件故障自动化定位过程中，如果在给定的测试用例集合情况下故障在故障疑似度列表种排名不高，比较有效的方法为补充新的测试用例。如何在较小的代价下提升故障的可疑度排名是一项具有挑战的工作。提出一种基于改进遗传算法(IGA)的测试用例生成方法，利用软件故障定位的疑似故障排名，来辅助生成软件故障定位过程中的测试用例。依次对所提方法进行阐述和分析，在6个C程序和2个Python程序上开展实验，实验结果表明：所提方法自动生成的测试用例能够有效地帮助提高故障定位的效率。
- 故障定位 /
- 测试用例生成 /
- 遗传算法 /
- 适应度函数 /
- 随机测试
Abstract:
The ranking of suspected faults in the process of automatic software fault localization will be continuously created and is determined after the execution of existing test cases. Sometimes the program units corresponding to the fault are ranked lower in the ranking of suspected failures based on the existing test cases. If it is necessary to improve the suspected fault ranking of the program unit corresponding to the fault, supplementary test cases are a feasible method. This article suggests a technique for creating test cases based on a genetic algorithm that can make use of knowledge about the location of software faults. The paper analyzes and analyzes the methods used. Based on the joint experiment of the paper on 6 C programs and 2 Python programs, experimental results show that the test cases automatically generated by this method can effectively help improve the efficiency of fault location.
- fault localization /
- test case generation /
- genetic algorithm /
- fitness function /
- random test

HTML全文

图 1 本文方法框架

Figure 1. Framework of proposed method

下载: 全尺寸图片幻灯片

图 2 最高语句覆盖率

Figure 2. Highest statement coverage

下载: 全尺寸图片幻灯片

图 3 平均语句覆盖率

Figure 3. Average statement coverage

下载: 全尺寸图片幻灯片

图 4 平均条件覆盖数

Figure 4. Average condition coverage

下载: 全尺寸图片幻灯片

图 5 故障语句覆盖率

Figure 5. Faulty statement coverage

下载: 全尺寸图片幻灯片

表 1 实验程序信息

Table 1. Experimental objects informations

程序	语句数	测试用例数目
Print_token1（Pt1）	563	4130
Print_token2（Pt2）	508	4115
Tcas	173	1607
Schedule1（Sch1）	410	2650
Schedule2（Sch2）	307	2710
Tot_info（Tot）	406	1052
Difflib	1937	100
Zipfile	2440	100

下载: 导出CSV

表 2 测试用例应用到故障定位的效率比较（Print_token1程序）

Table 2. Comparison of the efficiency of test case applied to fault location（Print_token1）

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率 /%
XGBoost	62	6	90.32
D³Star	360	97	73.05
GP19	297	173	41.75
Ochiai1	297	97	67.34

下载: 导出CSV

表 3 测试用例应用到故障定位的效率比较（Print_token2程序）

Table 3. Comparison of the efficiency of test case applied to fault location（Print_token2）

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	160	16	90.00
D³Star	61	52	14.80
GP19	182	52	71.43
Ochiai1	64	61	4.69

下载: 导出CSV

表 4 测试用例应用到故障定位的效率比较（Tot_info程序）

Table 4. Comparison of the efficiency of test case applied to fault location（Tot_info）

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	49	24	51.02
D³Star	357	80	77.59
GP19	369	280	21.57
Ochiai1	357	80	77.59

下载: 导出CSV

表 5 测试用例应用到故障定位的效率比较（Schedule1程序）

Table 5. Comparison of the efficiency of test case applied to fault location（Schedule1）

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	8	6	50.00
D³Star	20	26	−30.00
GP19	128	139	−8.59
Ochiai1	20	26	−30.00

下载: 导出CSV

表 6 测试用例应用到故障定位的效率比较（Schedule2程序）

Table 6. Comparison of the efficiency of test case applied to fault location(Schedule2)

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	132	41	68.94
D³Star	92	16	82.61
GP19	92	16	82.61
Ochiai1	92	16	82.61

下载: 导出CSV

表 7 测试用例应用到故障定位的效率比较（Tcas程序）

Table 7. Comparison of the efficiency of test case applied to fault location(Tcas)

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	59	5	91.52
D³Star	72	32	55.00
GP19	84	60	28.57
Ochiai1	72	32	55.00

下载: 导出CSV

表 8 测试用例应用到故障定位的效率比较（Difflib程序）

Table 8. Comparison of the efficiency of test case applied to fault location(Difflib)

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	51	51	0
D³Star	136	47	65.44
GP19	136	47	65.44
Ochiai1	136	47	65.44

下载: 导出CSV

表 9 测试用例应用到故障定位的效率比较（Zipfile程序）

Table 9. Comparison of the efficiency of test case applied to fault location（Zipfile）

故障定位方法	原始检查语句数	目前检查语句数	检查语句的减少率/%
XGBoost	121	93	23.14
D³Star	336	146	56.55
GP19	336	146	56.55
Ochiai1	336	146	56.55

下载: 导出CSV

参考文献(28)

[1]	TRACEY N J. A search-based automated test-data generation framework for safety-critical software[D]. York: The University of York, 2001.
[2]	HARMAN M, JONES B F. Search-based software engineering[J]. Information and Software Technology, 2001, 43(14): 833-839. doi: 10.1016/S0950-5849(01)00189-6
[3]	RUAN H, ZHANG J, YAN J. Test data generation for C programs with string-handling functions[C]// 2008 2nd IFIP/IEEE International Symposium on Theoretical Aspects of Software Engineering. Piscataway: IEEE Press, 2008: 219-226.
[4]	DEMILLI R A, OFFUTT A J. Constraint-based automatic test data generation[J]. IEEE Transactions on Software Engineering, 1991, 17(9): 900-910. doi: 10.1109/32.92910
[5]	PENG C, RAJAN A. Automated test generation for OpenCL kernels using fuzzing and constraint solving[C]//Proceedings of the 13th Annual Workshop on General Purpose Processing Using Graphics Processing Unit. New York: ACM, 2020.
[6]	YANG F, FAN Y, XIAO P, et al. Test data generation method based on multiple convergence direction adaptive PSO[J]. Software Quality Journal, 2022, 31: 279-303.
[7]	杨波, 吴际, 徐珞, 等. 一种软件测试需求建模及测试用例生成方法[J]. 计算机学报, 2014, 37(3): 522-538. YANG B, WU J, XU L, et al. An approach of modeling software testing requirements and generating test case[J]. Chinese Journal of Computers, 2014, 37(3): 522-538(in Chinese).
[8]	BOYER R S, ELSPAS B, LEVITT K N. SELECT—a formal system for testing and debugging programs by symbolic execution[J]. ACM SIGPLAN Notices, 1975, 10(6): 234-245. doi: 10.1145/390016.808445
[9]	MARCINIAK J J. Encyclopedia of software engineering[M]. Hoboken: JohnWiley & Sons, Inc., 2002.
[10]	HARMAN M, MCMINN P. A theoretical & empirical analysis of evolutionary testing and hill climbing for structural test data generation[C]//Proceedings of the 2007 International Symposium on Software Testing and Analysis. New York: ACM, 2007: 73-83.
[11]	METROPOLIS N, ROSENBLUTH A W, ROSENBLUTH M N, et al. Equation of state calculations by fast computing machines[J]. The Journal of Chemical Physics, 1953, 21(6): 1087-1092. doi: 10.1063/1.1699114
[12]	PARGAS R P, HARROLD M J, PECK R R. Test-data generation using genetic algorithms[J]. Software Testing, Verification and Reliability, 1999, 9(4): 263-282. doi: 10.1002/(SICI)1099-1689(199912)9:4<263::AID-STVR190>3.0.CO;2-Y
[13]	LI X L, WONG W E, GAO R Z, et al. Genetic algorithm-based test generation for software product line with the integration of fault localization techniques[J]. Empirical Software Engineering, 2018, 23(1): 1-51. doi: 10.1007/s10664-016-9494-9
[14]	SHEN X J, WANG Q, WANG P P, et al. Automatic generation of test case based on GATS algorithm[C]//2009 IEEE International Conference on Granular Computing. Piscataway: IEEE Press, 2009: 496-500.
[15]	NOSRATI M, HAGHIGHI H, VAHIDI ASL M. Test data generation using genetic programming[J]. Information and Software Technology, 2021, 130: 106446. doi: 10.1016/j.infsof.2020.106446
[16]	SAHOO R R, RAY M. PSO based test case generation for critical path using improved combined fitness function[J]. Journal of King Saud University - Computer and Information Sciences, 2020, 32(4): 479-490. doi: 10.1016/j.jksuci.2019.09.010
[17]	DI NUCCI D, PANICHELLA A, ZAIDMAN A, et al. A test case prioritization genetic algorithm guided by the hypervolume indicator[J]. IEEE Transactions on Software Engineering, 2020, 46(6): 674-696. doi: 10.1109/TSE.2018.2868082
[18]	CAI G C, SU Q H, HU Z B. Automated test case generation for path coverage by using grey prediction evolution algorithm with improved scatter search strategy[J]. Engineering Applications of Artificial Intelligence, 2021, 106: 104454. doi: 10.1016/j.engappai.2021.104454
[19]	GOTLIEB A, BOTELLA B, RUEHER M. Automatic test data generation using constraint solving techniques[J]. ACM SIGSOFT Software Engineering Notes, 1998, 23(2): 53-62. doi: 10.1145/271775.271790
[20]	GUPTA N, MATHUR A P, SOFFA M L. Automated test data generation using an iterative relaxation method[J]. ACM SIGSOFT Software Engineering Notes, 1998, 23(6): 231-244. doi: 10.1145/291252.288321
[21]	WANG C H, PASTORE F, GOKNIL A, et al. Automatic generation of acceptance test cases from use case specifications: An NLP-based approach[J]. IEEE Transactions on Software Engineering, 2022, 48(2): 585-616. doi: 10.1109/TSE.2020.2998503
[22]	BERTOLINO A, MIRANDA B, PIETRANTUONO R, et al. Adaptive test case allocation, selection and generation using coverage spectrum and operational profile[J]. IEEE Transactions on Software Engineering, 2021, 47(5): 881-898. doi: 10.1109/TSE.2019.2906187
[23]	CHEN T Y, LEUNG H, MAK I K. Adaptive random testing[C]//Annual Asian Computing Science Conference. Berlin: Springer, 2004: 320-329.
[24]	CAMPOS J, GE Y, ALBUNIAN N, et al. An empirical evaluation of evolutionary algorithms for unit test suite generation[J]. Information and Software Technology, 2018, 104: 207-235. doi: 10.1016/j.infsof.2018.08.010
[25]	ZAMANI S, HEMMATI H. A cost-effective approach for hyper-parameter tuning in search-based test case generation[C]//2020 IEEE International Conference on Software Maintenance and Evolution. Piscataway: IEEE Press, 2020: 418-429.
[26]	ZAMANI S, HEMMATI H. A pragmatic approach for hyper-parameter tuning in search-based test case generation[J]. Empirical Software Engineering, 2021, 26(6): 1-35.
[27]	YANG B, HE Y Z, LIU H, et al. A lightweight fault localization approach based on XGBoost[C]//2020 IEEE 20th International Conference on Software Quality, Reliability and Security. Piscataway: IEEE Press, 2020: 168-179.
[28]	YANG B, HE Y Z, FENG L X. Automated test case generation for effective spectrum-based fault localization[J]. Journal of Physics: Conference Series, 2020, 1576(1): 012042. doi: 10.1088/1742-6596/1576/1/012042