基于深度强化学习的类集成测试序列生成方法

doi:10.12263/DZXB.20210688

电子学报 ›› 2023, Vol. 51 ›› Issue (2): 455-466.DOI: 10.12263/DZXB.20210688

基于深度强化学习的类集成测试序列生成方法

张颖辉¹^,², 张艳梅¹^,²^,³, 张志成⁴, 姜淑娟¹^,², 丁艳茹¹^,², 袁冠¹^,²^,³

^1.中国矿业大学矿山数字化教育部工程研究中心，江苏徐州 221116
^2.中国矿业大学计算机科学与技术学院，江苏徐州 221116
^3.广西可信软件重点实验室（桂林电子科技大学），广西桂林541004
^4.南方科技大学工学院计算机科学与工程系，广东深圳 518055

收稿日期:2021-05-08 修回日期:2022-05-31 出版日期:2023-02-25
- 作者简介:
- 张颖辉男，1996年生，河南商丘人. 中国矿业大学计算机科学与技术硕士研究生.主要研究方向为类集成测试序列生成、深度强化学习.
  张艳梅（通讯作者）女，1982年生，唐山人.博士，中国矿业大学计算机科学与技术学院副教授.主要研究方向为软件分析与测试、强化学习.E-mail: ymzhang@cumt.edu.cn
  张志成男，1998年生，湖北宜昌人. 南方科技大学工学院计算机科学与工程系硕士研究生.主要研究方向为自动程序修复、移动应用分析与软件测试.
  姜淑娟女，1966年生，山东莱阳人.博士，中国矿业大学教授、博士生导师.主要研究方向为软件分析与测试、缺陷预测、故障定位、进化计算等.E-mail: shjjiang@cumt.edu.cn
  丁艳茹女，1996年生，河北沧州人.中国矿业大学计算机科学与技术学院博士研究生.主要研究方向为软件分析与测试，强化学习.E-mail: yrding@cumt.edu.cn
  袁冠男，1982年生，江苏睢宁人.博士，中国矿业大学教授、博士生导师.主要研究方向为时空大数据技术以及计算智能等.E-mail: yuanguan@cumt.edu.cn
- 基金资助:
- 国家自然科学基金(61673384);中国博士后基金特别资助(2021T140707);广西可信软件重点实验室研究课题(kx201609)

Generation Method of Class Integration Test Order Based on Deep Reinforcement Learning

ZHANG Ying-hui¹^,², ZHANG Yan-mei¹^,²^,³, ZHANG Zhi-cheng⁴, JIANG Shu-juan¹^,², DING Yan-ru¹^,², YUAN Guan¹^,²^,³

^1.Mine Digitization Engineering Research Center of the Ministry of Education, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China
^2.School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China
^3.Guangxi Key Laboratory of Trusted Software, Guilin, Guangxi 541004, China
^4.Department of Computer Science and Engineering, College of Engineering, Southern University of Science and Technology, Shenzhen, Guangdong 518055, China

Received:2021-05-08 Revised:2022-05-31 Online:2023-02-25 Published:2023-04-14
- Supported by:
- National Natural Science Foundation of China(61673384);Postdoctoral Foundation of China(2021T140707);Guangxi Trusted Software Key Laboratory(kx201609)

摘要/Abstract

摘要：

类集成测试序列的生成是面向对象软件测试中的关键步骤，当类的测试序列不同时，相应的测试代价也不相同.在集成测试中生成一个合理的类集成测试序列可以有效降低软件测试的代价.本文将深度强化学习中的Advantage Actor-Critic算法应用于解决类集成测试序列生成问题.首先，利用类间各种依赖关系构建与智能体交互的环境模型；然后，记录智能体从初始状态到终止状态的路径，即每次选择的动作对应每次选择集成到序列的类编号；最后，得出最终的类集成测试序列.实验结果表明，本文方法所得到的类集成测试序列花费的总体测试桩复杂度，在选取的7个项目中有5个表现最佳，在剩余2个项目中表现中等.

关键词: 集成测试, 测试序列, 深度强化学习, advantage actor-critic, 测试桩复杂度

Abstract:

The generation of class integration test order is the key step in object-oriented software testing. When the class integration test order is different, the corresponding test cost is different. Generating a reasonable class integration test order in integration testing can effectively reduce the cost of software testing. This paper applies the advantage actor-critic algorithm in deep reinforcement learning to solve the problem of class integration test order generation. Firstly, the environment model of interaction with agents is constructed by using various dependencies between classes. Then, the path of the agent from the initial state to the termination state is recorded, that is, each selected action corresponds to each selected class number integrated into the order. Finally, the final class integration test order is obtained. The experimental results show that the total test stubs complexity of class integration test order cost obtained by the method in this paper has the best performance in 5 out of 7 selected subjects, and the average performance in the remaining 2 subjects.

Key words: integration test, test order, deep reinforcement learning, advantage actor-critic, complexity

中图分类号:

TP311

张颖辉, 张艳梅, 张志成, 等. 基于深度强化学习的类集成测试序列生成方法[J]. 电子学报, 2023, 51(2): 455-466.

Ying-hui ZHANG, Yan-mei ZHANG, Zhi-cheng ZHANG, et al. Generation Method of Class Integration Test Order Based on Deep Reinforcement Learning[J]. Acta Electronica Sinica, 2023, 51(2): 455-466.

图/表 14

图1 基于DRL的CITO解决方法框架

表1 elevator 各类编号

类编号	类名称	类编号	类名称
0	Building	6	ElevatorState
1	DoorClosedException	7	Floor
2	Elevator	8	Logger
3	ElevatorController	9	Person
4	ElevatorFullException	10	PersonState
5	ElevatorMovingException	11	Simulator

表2 elevator 属性依赖和方法依赖

类编号	0	2	3	7	9	11
0	-	-	-	-	(2,3)	(0,2)
1	-	(0,2)	-	-	-	-
2	-	-	(4,33)	(2,2)	(2,9)	-
3	(1,7)	(2,1)	-	(2,2)	-	-
4	-	(0,1)	-	-	-	-
5	-	(0,2)	-	-	-	-
6	(1,2)	(1,0)	(1,0)	-	-	-
7	(2,2)	-	(1,15)	-	(1,10)	-
8	-	(1,24)	(1,27)	(1,9)	(1,4)	-
9	-	(2,1)	(2,2)	(3,9)	-	(0,4)
10	-	(0,2)	-	-	(1,2)	-

表3 elevator 耦合代价矩阵

类编号	0	2	3	7	9	11
0	0	0	0	0	0.359	0.043
1	0	0.043	0	0	0	0
2	0	0	1	0.356	0.403	0
3	0.232	0.354	0	0.356	0	0
4	0	0.021	0	0	0	0
5	0	0.043	0	0	0	0
6	0.177	0.182	0.177	0	0	0
7	0.356	0	0.367	0	0.278	0
8	0	0.544	0.605	0.262	0.197	0
9	0	0.354	0.356	0.564	0	0.086

图2 DRL应用到CITO问题的过程图

表5 项目详细信息

System	Description	Classes	Deps	Cycles	LOC
ANT	部署工具	25	83	654	4 093
ATM	自动柜员机系统	21	67	30	1 390
SPM	安全巡逻监视项目	19	72	1 178	1 198
DNS	域名解析系统	61	276	16	6 710
daisy	网络文件系统	23	36	4	1 148
email-spl	电子邮件工具	39	64	38	2 276
BCEL	创建、分析、操作Java类文件的插桩工具	45	294	416 091	3 033

表6 参数设置

参数	含义	值	参数	意义	值
W_A	属性权重	0.5	$ε$ -start	$ε$ 初始值	1
W_M	方法权重	0.5	$ε$ -end	$ε$ 结束值	0.01
γ	折扣率	0.8	T	训练次数	200 000
c	奖励倍数	10 000	batch_size	批处理单位	64
min_value	最大惩罚	-150 000	$ε$ _decay	$ε$ 降低速率	1 000 $×$ N
max_value	最大奖励	150 000	-	-	-

表6 参数设置

参数	含义	值	参数	意义	值
W_A	属性权重	0.5	$ε$ -start	$ε$ 初始值	1
W_M	方法权重	0.5	$ε$ -end	$ε$ 结束值	0.01
γ	折扣率	0.8	T	训练次数	200 000
c	奖励倍数	10 000	batch_size	批处理单位	64
min_value	最大惩罚	-150 000	$ε$ _decay	$ε$ 降低速率	1 000 $×$ N
max_value	最大奖励	150 000	-	-	-

图3 总体测试桩复杂度箱型图

表7 总体测试桩复杂度对比表

Category	Method	ANT	ATM	SPM	DNS	daisy	email-spl	BCEL
Graph	Le Traon	3.72	3.37	8.4	5.02	-	-	8.23
	Tai	3.87	2.99	8.08	4.63	-	-	8.68
	Briand	3.31	2.7	5.82	1.51	-	-	8.58
Heuristic	GA	3.64	2.68	5.77	7.15	2.63	1.56	13.70
	RIA	2.32	2.39	3.25	8.56	0.33	0.95	7.95
	PSO	2.25	2.53	3.01	5.82	0.90	1.04	8.59
RL	DRL	1.479 5	2.052	4.028 3	3.409 1	0.192 8	0.52	7.105 1

表8 特定测试桩个数对比表

Category	Method	ANT	ATM	SPM	DNS	daisy	email-spl	BCEL
Graph	Le Traon	18	9.1	24.7	11	-	-	67.5
	Tai	28	8	20.2	27	-	-	128
	Briand	11	7	17	6	-	-	70
Heuristic	GA	12	7	17	6	12	27	71
	RIA	14.97	7.43	12.77	20.07	6	15	53.60
	PSO	14.33	7.83	12.07	17.33	8	19	55.47
RL	RL	19.33	7.33	21.33	14.33	4.13	11.07	88.33
RL	DRL	19	18	19	32	4	13	93

图4 总体测试桩复杂度对比图

表9 通用测试桩个数

	ANT	ATM	SPM	DNS	daisy	email-spl	BCEL
DRL	11.33	14	17.33	22.5	4	12	18.34

表10 通用测试桩详细信息

项目名称	通用测试桩信息
ANT	1:BuildEvent,3:BuildListener,14:PathTokenizer,16:ProjectComponent,19:Target,20:Task,21:TaskAdapter,17:ProjectHelper,22:TaskContainer,23:UnknownElement,4:BuildLogger
ATM	0:ReceiptPrinter,1:Display,2:Keyboard,3:CardReader,4:OperatorPanel,5:EnvelopeAcceptor,6:CashDispenser,8:Bank,9:Session,10:Transaction,11:WithdrawlTransaction,12:DepositTransaction,13:TransferTransaction,14:InquiryTransaction
SPM	3:CheckpointControllerIdleState,4:CheckpointControllerNormalCheckingState,5:CheckpointControllerState,6:CheckpointControllerViolationCheckingState,7:CheckpointControllerViolationState,8:CheckpointReferences,0:CardReaderInterface,12:DoorLockInterface,13:GuardDueTimer,14:GuardLateTimer,15:PatrolSchedule,18:SecurityZone
DNS	4:BitString,7:Compression,10:DNAMERecord,27:Options,48:WireParseException,31:Record,54:Message,60:ResolverListener,6:CNAMERecord,34:RRset,43:TTL,9:DClass,14:Flags,26:Opcode,28:OPTRecord,42:TSIGRecord,52:Header,47:UNKRecord,11:dns,55:MX_KXRecord,37:SimpleResolver,51:ExtendedResolver,21:NameSet
Daisy	17:util.Debug,1:daisy.Daisy,21:util.SplitPrintStream,14:DaisyUserThread
email-spl	2:defpackage.PL_Interface,3:defpackage.PL_Interface_impl,8:EmailSystem.Client,24:runspl.RunSPL,16:featuremodel.FeatureID,14:featuremodel.Configuration,21:featuremodel.RelevantModelIterator,7:EmailSystem.ClientKeyringEntry,36:TestSpecifications.SpecificationManager,13:featuremodel.Configuration1,34:TestSpecifications.Specification9
BCEL	7:ConstantCP,44:Visitor,5:Constant,16:ConstantObject,17:ConstantPool,1:Attribute,35:Node,10:ConstantFloat,11:ConstantInteger,12:ConstantInterfaceMethodref,15:ConstantNameAndType,0:AccessFlags,25:Field,34:Method,20:ConstantValue,21:Deprecated,36:PMGClass,37:Signature

图5 总体测试桩复杂度变化图

参考文献 39

1	KUNG D, GAO J, HSIA P, et al. A test strategy for object-oriented programs[C]//Proceedings of the 19th Annual International Computer Software and Applications Conference. Texas: IEEE, 1995: 239-244.
2	BRIAND L C, FENG J, LABICHE Y. Using genetic algorithms and coupling measures to devise optimal integration test orders[C]//Proceedings of the 14th International Conference on Software Engineering and Knowledge Engineering. Ischia: Association for Computing Machinery, 2002: 43-50.
3	CZIBULA G, CZIBULA I G, MARIAN Z. An effective approach for determining the class integration test order using reinforcement learning[J]. Applied Soft Computing, 2018, 65: 517-530.
4	KUNG D C, GAO J, PEI H, et al. On regression testing of object-oriented programs[J]. Journal of Systems and Software, 2015, 32(1): 21-40.
5	TAI K C, DANIELS F J. Test order for inter-class integration testing of object-oriented software[C]//Proceedings of the 21st Annual International Computer Software and Applications Conference. Washington: IEEE, 1997: 602-607.
6	LE TRAON Y, JÉRON T, JÉZÉQUEL J M, et al. Efficient object-oriented integration and regression testing[J]. IEEE Transactions on Reliability, 2000, 49(1): 12-25.
7	BRIAND L C, LABICHE Y, WANG Y. An investigation of graph-based class integration test order strategies[J]. IEEE Transactions on Software Engineering, 2003, 29(7): 594-607.
8	LE HANH V, AKIF K, LE TRAON Y, et al. Selecting an efficient OO integration testing strategy: An experimental comparison of actual strategies[C]//Proceedings of the European Conference on Object-Oriented Programming. Heidelberg: Springer, 2001: 381-401.
9	ZAIDMAN A, DEMEYER S. Automatic identification of key classes in a software system using webmining techniques[J]. Journal of Software Maintenance and Evolution: Research and Practice, 2008, 20(6): 387-417.
10	HASHIM N L, SCHMIDT H W, RAMAKRISHNAN S. Test order for class-based integration testing of java applications[C]//Proceedings of the 5th International Conference on Quality Software. Victoria: IEEE, 2005: 11-18.
11	张艳梅, 姜淑娟, 张红昌. 一种基于动态依赖关系的类集成测试方法[J]. 计算机学报, 2011(6): 1075-1089.
	ZHANG Y M, JIANG S J, ZHANG H C. A method of class integration testing based on dynamic dependency[J]. Chinese Journal of Computers, 2011(6): 1075-1089. (in Chinese)
12	张艳梅. 基于依赖性分析的面向对象程序测试技术研究[D]. 徐州: 中国矿业大学, 2012.
	ZHANG Y M. Research on Testing Technology of Object-Oriented Programs Based on Dependency Analysis[D]. Xuzhou: China University of Mining and Technology, 2012. (in Chinese)
13	CHEN Q, LI X. An order-assigned strategy of classes integration testing based on test level[C]//Proceedings of the 8th International Conference on Computer Supported Cooperative Work in Design. Heidelberg: Springer, 2004: 653-657.
14	郑磊. 面向对象集成测试的分层增量测试策略[D]. 上海: 上海交通大学, 2007.
	ZHENG L. Layered and Incremental Strategy for Objected-Oriented Integration Testing[D]. Shanghai: Shanghai Jiaotong University, 2007. (in Chinese)
15	BORNER L, PAECH B. Integration test order strategies to consider test focus and simulation effort[C]//Proceedings of the 1st International Conference on Advances in System Testing and Validation Lifecycle. Proto: IEEE, 2009: 80-85.
16	WANG Z, LI B, WANG L, et al. Using coupling measure technique and random iterative algorithm for inter-class integration test order problem[C]//Proceedings of the IEEE 34th Annual Computer Software and Applications Conference Workshops. Seoul: IEEE, 2010: 329-334.
17	WANG Z, LI B, WANG L, et al. A brief survey on automatic integration test order generation[C]//Proceedings of the 23rd International Conference on Software Engineering and Knowledge Engineering. Miami Beach: ACM, 2011: 254-257.
18	VERGILIO S R, POZO A, ÁRIAS J C G, et al. Multi-objective optimization algorithms applied to the class integration and test order problem[J]. International Journal on Software Tools for Technology Transfer, 2012, 14(4): 461-475.
19	ASSUNÇÃO W K G, COLANZI T E, POZO A T R, et al. Establishing integration test orders of classes with several coupling measures[C]//Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. Dublin: ACM, 2011: 1867-1874.
20	DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II[C]// Proceedings of the International Conference on Parallel Problem Solving From Nature. Berlin: Springer, 2000: 849-858.
21	ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm[J]. TIK-report, 2001: 103.
22	KNOWLES J D, CORNE D W. Approximating the nondominated front using the pareto archived evolution strategy[J]. Evolutionary Computation, 2014, 8(2): 149-172.
23	JAROENPIBOONKIT J, SUWANNASART T. Finding a test order using object-oriented slicing technique[C]//Proceedings of the 14th Asia-Pacific Software Engineering Conference. Aichi: IEEE Computer Society, 2007: 49-56.
24	刘颖莲. 面向对象软件集成测试策略研究[D]. 北京: 北京邮电大学, 2013.
	LIU Y L. Research of Object-Oriented Software Integration Testing Strategy[D]. Beijing: Beijing University of Post and Telecommunications, 2013. (in Chinese)
25	赵玉丽, 王莹, 于海等. 基于复杂网络的类间集成测试序列生成方法[J]. 东北大学学报(自然科学版), 2015, 36(12): 1696-1700.
	ZHAO Y L, WANG Y, YU H, et al. An inter-class integration test order generation method based on complex networks[J]. Journal of Northeastern University (Natural Science), 2015, 36(12): 1696-1700. (in Chinese)
26	王莹, 于海, 朱志良. 基于软件节点重要性的集成测试序列生成方法[J]. 计算机研究与发展, 2016, 53(3): 517-530.
	WANG Y, YU H, ZHU Z L. A class integration test order method based on the node importance of software[J]. Journal of Computer Research and Development, 2016, 53(3): 517-530. (in Chinese)
27	ZAIDMAN A, CALDERS T, DEMEYER S, et al. Applying webmining techniques to execution traces to support the program comprehension process[C]//Proceedings of the 9th European Conference on Software Maintenance and Reengineering. Manchester: IEEE Computer Society, 2005: 134-142.
28	HESSEL M, MODAYIL J, HASSELT H V, et al. Rainbow: Combining improvements in deep reinforcement learning[EB/OL].(2017-10-06)[2021-05-08]. .
29	黄志清, 曲志伟, 张吉, 等. 基-于深度强化学习的端到端无人驾驶决策[J]. 电子学报, 2020, 48(9): 1711-1719.
	HUANG Z Q, QU Z W, ZHANG J, et al. End-to-end autonomous driving decision based on deep reinforcement learning[J]. Acta Electronica Sinica, 2020, 48(9): 1711-1719. (in Chinese)
30	刘春阳, 谭应清, 柳长安, 等. 多智能体强化学习在足球机器人中的研究与应用[J]. 电子学报, 2010, 38(8): 1958-1962.
	LIU C Y, TAN Y Q, LIU C A, et al. Application of multi-agent reinforcement learning in robot soccer[J]. Acta Electronica Sinica, 2010, 38(8): 1958-1962. (in Chinese)
31	WANG F Y, ZHANG J J, ZHENG X, et al. Where does AlphaGo go: From church-turing thesis to AlphaGo thesis and beyond[J]. IEEE/CAA Journal of Automatica Sinica, 2016, 3(2): 113-120.
32	QIANG W, ZHONG L Z. Reinforcement learning model, algorithms and its application[C]//Proceedings of the 2011 International Conference on Mechatronic Science. Jilin: IEEE, 2011: 1143-1146.
33	VAN HASSELT H, GUEZ A, SILVER D. Deep reinforcement learning with double q-learning[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence. Phoenix: Arizona, 2016: 2094-2100.
34	JANG H C, HUANG Y C, CHIU H A. A study on the effectiveness of A2C and A3C reinforcement learning in parking space search in urban areas problem[C]//Proceedings of the 2020 International Conference on Information and Communication Technology Convergence. Jeju Island: IEEE, 2020: 567-571.
35	ZHANG M, JIANG S J, ZHANG Y M, et al. A multi-level feedback approach for the class integration and test order problem[J]. Journal of Systems and Software, 2017, 133: 54-67.
36	TAN A H, LU N, XIAO D. Integrating temporal difference methods and self-organizing neural networks for reinforcement learning with delayed evaluative feedback[J]. IEEE Transactions on Neural Networks, 2008, 19(2): 230.
37	SCHAUL T, QUAN J, ANTONOGLOU I, et al. Prioritized experience replay[EB/OL]. (2015-11-18)[2021-05-08]. .
38	BRIAND L C, LABICHE Y, WANG Y. Revisiting strategies for ordering class integration testing in the presence of dependency cycles[C]//Proceedings of the 12th International Symposium on Software Reliability Engineering. Hong Kong: IEEE, 2001: 287-296.
39	张悦宁, 姜淑娟, 张艳梅. 基于梦境粒子群优化的类集成测试序列生成方法[J]. 计算机科学, 2019, 46(2): 168-174.
	ZHANG Y N, JIANG S J, ZHANG Y M. Approach for generating class integration test sequence based on dream particle swarm optimization algorithm[J]. Computer Science, 2019, 46(2): 168-174. (in Chinese)

[1]	许艺瀚, 田永波, 张扬刚, 花敏, 周雯. 基于学习的能量采集认知M2M通信资源分配算法[J]. 电子学报, 2023, 51(2): 467-476.
[2]	段世红, 何昊, 徐诚, 殷楠, 王然. 未知环境下基于深度序列蒙特卡罗树搜索的信源导航方法[J]. 电子学报, 2022, 50(7): 1744-1752.
[3]	宋佰霖, 许华, 齐子森, 饶宁, 彭翔. 一种基于深度强化学习的协同通信干扰决策算法[J]. 电子学报, 2022, 50(6): 1301-1309.
[4]	饶宁, 许华, 蒋磊, 宋佰霖, 史蕴豪. 基于多智能体深度强化学习的分布式协同干扰功率分配算法[J]. 电子学报, 2022, 50(6): 1319-1330.
[5]	易令, 李泽平. 基于深度强化学习的码率自适应算法研究[J]. 电子学报, 2022, 50(5): 1192-1200.
[6]	肖硕, 黄珍珍, 张国鹏, 杨树松, 江海峰, 李天旭. 基于SAC的多智能体深度强化学习算法[J]. 电子学报, 2021, 49(9): 1675-1681.
[7]	韩冲, 王俊丽, 吴雨茜, 张超波. 基于神经进化的深度学习模型研究综述[J]. 电子学报, 2021, 49(2): 372-379.
[8]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[9]	陈思光, 陈佳民, 赵传信. 基于深度强化学习的云边协同计算迁移研究[J]. 电子学报, 2021, 49(1): 157-166.
[10]	黄志清, 曲志伟, 张吉, 张严心, 田锐. 基于深度强化学习的端到端无人驾驶决策[J]. 电子学报, 2020, 48(9): 1711-1719.
[11]	李书浩, 王戟, 齐治昌, 董威, . 一种面向性质的实时系统测试方法[J]. 电子学报, 2005, 33(5): 827-834.
[12]	王林章;李宣东;郑国梁. 一个基于UML协作图的集成测试用例生成方法[J]. 电子学报, 2004, 32(8): 1290-1296.

基于深度强化学习的类集成测试序列生成方法

Generation Method of Class Integration Test Order Based on Deep Reinforcement Learning

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 39

相关文章 12

编辑推荐

Metrics