基于程序依赖关系的变异体生成策略

doi:10.11772/j.issn.1001-9081.2023091319

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (9): 2863-2870.DOI: 10.11772/j.issn.1001-9081.2023091319

基于程序依赖关系的变异体生成策略

田甜, 邵阳阳(), 王苗苗, 杨欢

山东建筑大学计算机科学与技术学院，济南 250101

收稿日期:2023-09-25 修回日期:2023-11-16 接受日期:2023-11-20 发布日期:2023-12-01 出版日期:2024-09-10
通讯作者: 邵阳阳
作者简介:田甜（1987—），女，山东德州人，副教授，博士，CCF会员，主要研究方向：程序分析与测试
王苗苗（2000—），女，河南济源人，硕士研究生，主要研究方向：变异测试
杨欢（1997—），男，江苏苏州人，硕士研究生，CCF会员，主要研究方向：程序分析、缺陷检测。
基金资助:
山东省自然科学基金资助项目(ZR2020MF084)

Mutant generation strategy based on program dependencies

Tian TIAN, Yangyang SHAO(), Miaomiao WANG, Huan YANG

School of Computer Science and Technology，Shandong Jianzhu University，Jinan Shandong 250101，China

Received:2023-09-25 Revised:2023-11-16 Accepted:2023-11-20 Online:2023-12-01 Published:2024-09-10
Contact: Yangyang SHAO
About author:TIAN Tian， born in 1987， Ph. D.， associate professor. Her research interests include program analysis and testing.
WANG Miaomiao， born in 2000， M. S. candidate. Her research interests include mutation testing.
YANG Huan， born in 1997， M. S. candidate. His research interests include program analysis， defect detection.
Supported by:
Shandong Provincial Natural Science Foundation(ZR2020MF084)

摘要/Abstract

摘要：

针对数量庞大的变异体导致高昂变异测试代价的问题，提出一种基于程序依赖关系的变异体生成（PDMG）策略，选择满足一定约束条件的变异实施对象用于变异体生成。首先，基于数据依赖和控制依赖生成程序依赖图；其次，基于变异对象选择策略和程序依赖图选择被依赖语句作为变异对象；最后，对选择的变异对象注入变异算子生成变异体。将所提策略用于8个基准测试程序的变异测试。实验结果表明，与随机选择（RS）和变异算子选择（MOS）策略相比，PDMG策略在不降低变异测试有效性的前提下，平均减少了52.20%的变异体，提高了变异测试的执行效率。

关键词: 变异测试, 数据依赖, 控制依赖, 变异对象, 变异体约减

Abstract:

Aiming at the problem of large numbers of mutants leading to high mutation testing cost， a Program Dependency based Mutant Generation （PDMG） strategy was proposed to select the mutation implementation objects satisfying certain constraint conditions for mutation generation. Firstly， program dependency graphs were generated based on data dependencies and control dependencies. Then， based on the mutation object selection strategy and program dependency graphs， the dependency statements were selected as mutation objects. Finally， the mutation operator was injected to the selected mutation objects in order to generate mutants. The proposed method was applied to mutation testing of 8 benchmark test programs. Experimental results show that compared with Random Selection （RS） and Mutation Operator Selection （MOS） strategies， PDMG strategy can reduce the mutants by 52.20% on average， improving the execution efficiency of mutation testing without reducing the effectiveness of mutation testing.

Key words: mutation testing, data dependence, control dependence, mutation object, mutant reduction

中图分类号:

TP311

田甜, 邵阳阳, 王苗苗, 杨欢. 基于程序依赖关系的变异体生成策略[J]. 计算机应用, 2024, 44(9): 2863-2870.

Tian TIAN, Yangyang SHAO, Miaomiao WANG, Huan YANG. Mutant generation strategy based on program dependencies[J]. Journal of Computer Applications, 2024, 44(9): 2863-2870.

图/表 7

图1 示例程序及程序依赖图

Fig. 1 Example program and program dependency graph

图2 变异实施对象选择策略

Fig. 2 Strategies of mutation implementation object selection

图3 示例程序

Fig.3 Example program

图4 基于程序依赖关系的变异测试流程

Fig. 4 Mutation testing flow based on program dependencies

表1 实验对象信息

Tab.1 Experimental object information

程序编号	程序名称	程序来源	代码行数	类数量	方法数	被依赖语句数
PG1	Triangle	http：//www.blogjava.net/qileilove/archive/2013/08/09/402610.html	38	1	3	15
PG2	BackPack	https：//blog.csdn.net/m0_52729352/article/details/121935091	50	1	2	31
PG3	Merge	https：//blog.csdn.net/qq_45954420/article/details/123412430	78	1	5	44
PG4	DateUtil	https：//www.codetd.com/article/228905	215	1	5	112
PG5	Cruise Control	https：//sir.csc.ncsu.edu/portal/index.php	358	4	34	214
PG6	OrdSet		393	2	23	234
PG7	Elevator		581	8	74	320
PG8	Apollo		4 109	55	627	2 311
平均值			728	9	97	410

表2 不同策略下的变异体数及约减率对比结果

Tab. 2 Comparison results of number of mutants and reduction rate of mutants under different strategies

程序编号	$M O$	RS		MOS		PDMG
程序编号	$M O$	$M R S$	MRR/%	$M M O S$	MRR/%	$M S D S$	MRR/%
平均值	1 726	1 230	27.57	1 284	31.26	771	52.20
PG1	307	259	15.64	216	29.64	178	42.02
PG2	403	306	24.07	230	42.93	225	44.17
PG3	451	328	27.27	258	42.79	224	50.33
PG4	597	419	29.82	381	36.19	282	52.76
PG5	588	396	32.65	448	23.81	245	58.33
PG6	930	623	33.01	697	25.05	342	63.23
PG7	1 246	879	29.45	917	26.40	617	50.48
PG8	9 287	6 628	28.63	7 128	23.25	4 058	56.30

表2 不同策略下的变异体数及约减率对比结果

Tab. 2 Comparison results of number of mutants and reduction rate of mutants under different strategies

程序编号	$M O$	RS		MOS		PDMG
程序编号	$M O$	$M R S$	MRR/%	$M M O S$	MRR/%	$M S D S$	MRR/%
平均值	1 726	1 230	27.57	1 284	31.26	771	52.20
PG1	307	259	15.64	216	29.64	178	42.02
PG2	403	306	24.07	230	42.93	225	44.17
PG3	451	328	27.27	258	42.79	224	50.33
PG4	597	419	29.82	381	36.19	282	52.76
PG5	588	396	32.65	448	23.81	245	58.33
PG6	930	623	33.01	697	25.05	342	63.23
PG7	1 246	879	29.45	917	26.40	617	50.48
PG8	9 287	6 628	28.63	7 128	23.25	4 058	56.30

表3 RS策略与PDMG策略下的RMS对比 (%)

Tab.3 RMS comparison under RS strategy and PDMG strategy

程序编号	RS	PDMG
平均值	97.45	96.94
PG1	99.65	99.13
PG2	99.86	99.31
PG3	99.73	99.70
PG4	99.05	98.74
PG5	96.87	96.77
PG6	96.04	95.94
PG7	95.72	95.46
PG8	92.64	90.46

参考文献 41

1	姚香娟，田甜，党向盈，等. 智能优化在软件测试中的应用综述［J］. 控制与决策， 2022， 37（2）： 257-266.
	YAO X J， TIAN T， DANG X Y， et al. Review on the application of intelligent optimization in software testing ［J］. Control and Decision， 2022， 37（2）： 257-266.
2	TAMBON F， KHOMH F， ANTONIOL G. A probabilistic framework for mutation testing in deep neural networks ［J］. Information and Software Technology， 2023， 155： No.107129.
3	田甜，巩敦卫. 并发程序变异测试研究综述［J］. 电子学报， 2020， 48（11）： 2267-2277.
	TIAN T， GONG D W. Survey on mutation testing of concurrent programs ［J］. Acta Electronica Sinica， 2020， 48（11）： 2267-2277.
4	KURTZ B， AMMANN P， OFFUTT J， et al. Analyzing the validity of selective mutation with dominator mutants ［C］// Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York： ACM， 2016： 571-582.
5	GOPINATH R， AHMED I， ALIPOUR M A， et al. Mutation reduction strategies considered harmful ［J］. IEEE Transactions on Reliability， 2017， 66（3）： 854-874.
6	宋利，刘靖. 基于SOM神经网络的二阶变异体约简方法［J］. 软件学报， 2019， 30（5）： 1464-1480.
	SONG L， LIU J. Second-order mutant reduction based on SOM neural network ［J］. Journal of Software， 2019， 30（5）： 1464-1480.
7	DANG X， GONG D， YAO X， et al. Enhancement of mutation testing via fuzzy clustering and multi-population genetic algorithm［J］. IEEE Transactions on Software Engineering， 2022， 48（6）： 2141-2156.
8	SINGH S P， SINGH V P， MEHTA A K. Differential evolution using homeostasis adaption based mutation operator and its application for software cost estimation ［J］. Journal of King Saud University — Computer and Information Sciences， 2021， 33（6）： 740-752.
9	FENG L C， WANG X Y， ZHANG S Y， et al. Mutation operator reduction for cost-effective deep learning software testing via decision boundary change measurement ［J］. Journal of Internet Technology， 2022， 23（3）： 601-610.
10	GUARNIERI G F， PIZZOLETO A V， FERRARI F C. An automated framework for cost reduction of mutation testing based on program similarity ［C］// Proceedings of the 2022 IEEE International Conference on Software Testing， Verification and Validation Workshops. Piscataway： IEEE， 2022： 179-188.
11	WEDYAN F， AL-SHISHANI A， JARARWEH Y. GaSubtle： a new genetic algorithm for generating subtle higher-order mutants［J］. Information， 2022， 13（7）： No.327.
12	DO V N， NGUYEN Q V， NGUYEN T B. Toward improving the quality of mutation operator and test case effectiveness in higher-order mutation testing ［J］. Vietnam Journal of Computer Science， 2022， 9（4）： 511-526.
13	OFFUTT A J， LEE S D. An empirical evaluation of weak mutation［J］. IEEE Transactions on Software Engineering， 1994， 20（5）： 337-344.
14	KINTIS M， MALEVRIS N. Using data flow patterns for equivalent mutant detection ［C］// Proceedings of the IEEE 7th International Conference on Software Testing， Verification and Validation Workshops. Piscataway： IEEE， 2014： 196-205.
15	MATEO P R， USAOLA M P. Mutant execution cost reduction： through music （mutant schema improved with extra code）［C］// Proceedings of the IEEE 5th International Conference on Software Testing， Verification and Validation. Piscataway： IEEE， 2012： 664-672.
16	KINTIS M， PAPADAKIS M， JIA Y， et al. Detecting trivial mutant equivalences via compiler optimisations ［J］. IEEE Transactions on Software Engineering， 2018， 44（4）： 308-333.
17	MATEO P R， USAOLA M P. Parallel mutation testing ［J］. Software Testing， Verification and Reliability， 2013， 23（4）： 315-350.
18	DEHIMI N E H， BENKHALEF A H， TOLBA Z. A novel mutation analysis-based approach for testing parallel behavioural scenarios in multi-agent systems ［J］. Electronics， 2022， 11（22）： No.3642.
19	陈杰，冯秀芳，陈永乐. 基于耦合度和PDG混合特征的源代码作者归属预测［J］. 计算机工程与科学， 2021， 43（7）： 1324-1330.
	CHEN J， FENG X F， CHEN Y L. A source code authorship attribution prediction based on code coupling and PDG hybrid features ［J］. Computer Engineering & Science， 2021， 43（7）： 1324-1330.
20	孙昌爱，卫新洁，刘镇贤，等. DFSampling：一种数据流分析指导的变异体精简策略［J］. 软件学报， 2022， 33（9）： 3407-3421.
	SUN C A， WEI X J， LIU Z X， et al. DFSampling： mutant reduction technique guided by data flow analysis ［J］. Journal of Software， 2022， 33（9）： 3407-3421.
21	HARMAN M， HIERONS R， DANICIC S. The relationship between program dependence and mutation analysis ［M］// WONG W E. Mutation Testing for the New Century， ADBS 24. Boston： Springer， 2001： 5-13.
22	ACREE A T， DEMILLO R A， BUDD T， et al. Mutation Analysis： GIT-ICS-79/08 ［R］. Atlanta， GA： Georgia Institute of Technology， 1979.
23	WONG W E， MATHUR A P. Reducing the cost of mutation testing： an empirical study ［J］. Journal of Systems and Software， 1995， 31（3）： 185-196.
24	ZHANG L， HOU S S， HU J J， et al. Is operator-based mutant selection superior to random mutant selection？［C］// Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering — Volume 1. New York： ACM， 2010： 435-444.
25	HUSSAIN S. Mutation clustering ［D/OL］. （2008-09-05）［2022-10-08］. .
26	曾凡平，黄玉涵，张美超，等. 基于遗传算法聚类的变异体约简［J］. 计算机应用， 2011， 31（5）： 1314-1317.
	ZENG F P， HUANG Y H， ZHANG M C， et al. Mutants reduction based on genetic algorithm for clustering ［J］. Journal of Computer Applications， 2011， 31（5）： 1314-1317.
27	JI C， CHEN Z， XU B， et al. A novel method of mutation clustering based on domain analysis ［C］// Proceedings of the 21st International Conference on Software Engineering and Knowledge Engineering. Skokie， IL： Knowledge Systems Institute Graduate School， 2009： 422-425.
28	MATHUR A P. Performance， effectiveness， and reliability issues in software testing ［C］// Proceedings of the 15th Annual International Computer Software and Applications Conference. Piscataway： IEEE， 1991： 604-605.
29	OFFUTT A J， ROTHERMEL G， ZAPF C. An experimental evaluation of selective mutation ［C］// Proceedings of 15th International Conference on Software Engineering. Piscataway： IEEE， 1993： 100-107.
30	JIA Y， HARMAN M. Constructing subtle faults using higher order mutation testing ［C］// Proceedings of the 8th IEEE International Working Conference on Source Code Analysis and Manipulation. Piscataway： IEEE， 2008： 249-258.
31	王子健. 基于多目标差分进化算法的二阶变异体约简方法研究［D］. 呼和浩特：内蒙古大学， 2022： 1-34.
	WANG Z J. Research on second order mutant reduction method based on multi-objective differential evolution algorithm ［D］. Hohhot： Inner Mongolia University， 2022： 1-34.
32	孙昌爱，曾国峰，张守峰，等. CWMT：一种基于并发机制的弱变异测试加速技术［J］. 计算机学报， 2023， 46（7）： 1409-1426.
	SUN C A， ZENG G F， ZHANG S F， et al. CWMT： a concurrency based acceleration technique for weak mutation testing［J］. Chinese Journal of Computers， 2023， 46（7）： 1409-1426.
33	YAO X， ZHANG G， PAN F， et al. Orderly generation of test data via sorting mutant branches based on their dominance degrees for weak mutation testing ［J］. IEEE Transactions on Software Engineering， 2022， 48（4）： 1169-1184.
34	ALTAMIMI E， ELKAWAKJY A， CATAL C. Metamorphic relation automation： rationale， challenges， and solution directions［J］. Journal of Software： Evolution and Process， 2023， 35（1）： No.e2509.
35	山东建筑大学. 一种用于变异测试的程序语句选择方法及系统： CN202310457585.9 ［P］. 2023-07-14.
	Shandong Jianzhu University. A program statement selection method and system for mutation testing： CN202310457585.9 ［P］. 2023-07-14.
36	王珣，孙玉雪，董玉坤，等. 抽象语义引导的空指针引用自动修复［J］. 计算机系统应用， 2023， 32（1）： 376-384.
	WANG X， SUN Y X， DONG Y K， et al. Automatic repair for null pointer reference guided by abstract semantics ［J］. Computer Systems and Applications， 2023， 32（1）： 376-384.
37	于畅. 基于机器学习的变异测试优化技术研究［D］. 北京：北京邮电大学， 2020： 1-29.
	YU C. Mutation testing optimization using machine learning technique ［D］. Beijing： Beijing University of Posts and Telecommunications， 2020： 1-29.
38	DO H， ELBAUM S， ROTHERMEL G. Supporting controlled experimentation with testing techniques： an infrastructure and its potential impact ［J］. Empirical Software Engineering， 2005， 10： 405-435.
39	MOUCHAWRAB S， BRIAND L C， LABICHE Y， et al. Assessing， comparing， and combining state machine-based testing and structural testing： a series of experiments ［J］. IEEE Transactions on Software Engineering， 2011， 37（2）： 161-187.
40	QIN X， LIU S， TAO Z. A new mutant generation algorithm based on basic path coverage for mutant reduction ［C］// Proceedings of the 2019 International Workshop on Structured Object-Oriented Formal Language and Method. Cham： Springer， 2020： 167-186.
41	KIM Y， HONG S. Learning-based mutant reduction using fine-grained mutation operators［J］. Software Testing， Verification and Reliability， 2022， 32（7）： No.e1786.

[1]	汤兴恒, 郭强, 徐天慧, 张彩明. 基于多尺度核自适应滤波的股票收益预测[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1385-1393.
[2]	刘其源, 焦健, 曹宏盛. Android隐式信息流检测的本体模型[J]. 计算机应用, 2018, 38(1): 61-66.
[3]	郭后钱, 王微微, 尚颖, 赵瑞莲. 基于动态集合进化算法的弱变异测试用例集生成[J]. 计算机应用, 2017, 37(9): 2659-2664.
[4]	程勇, 秦丹, 杨光. 针对JavaScript浏览器兼容性的变异测试方法[J]. 计算机应用, 2017, 37(4): 1143-1148.
[5]	王定成, 赵友志, 陈北京, 陆一祎. 多输出数据依赖核支持向量回归快速学习算法[J]. 计算机应用, 2017, 37(3): 746-749.
[6]	吴俞伯, 郭俊霞, 李征, 赵瑞莲. 基于并发程序数据竞争故障的变异策略[J]. 计算机应用, 2016, 36(11): 3170-3177.
[7]	曾凡平黄玉涵张美超潘能刚. 基于遗传算法聚类的变异体约简[J]. 计算机应用, 2011, 31(05): 1314-1317.
[8]	张龙杰谢晓方袁胜智. 一种改进的静态程序切片算法[J]. 计算机应用, 2009, 29(3): 705-707.
[9]	陈佳蕊蔡国永. 基于扩展WSDL变异的Web服务测试方法[J]. 计算机应用, 2007, 27(7): 1725-1728.

基于程序依赖关系的变异体生成策略

Mutant generation strategy based on program dependencies

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 41

相关文章 9

编辑推荐

Metrics