1、第 5 期2023 年5 月电子学报ACTA ELECTRONICA SINICAVol.51 No.5May 2023基于关键边概率与路径层接近度的多路径覆盖测试钱忠胜，成轶伟，俞情媛，张丁，姚昌森，秦朗悦（江西财经大学信息管理学院，江西南昌 330013）摘要：遗传算法解决多路径覆盖中难覆盖边的问题，是当前软件测试数据自动生成领域的一个研究热点.现有方法解决多路径覆盖问题的效果不够理想，本文提出一种将关键边概率与路径层接近度相结合的多路径覆盖测试方法.首先，本文计算节点被穿越概率找到难覆盖节点，通过难覆盖节点找到难覆盖边（即，关键边），生成目标路径.然后，本文根据关键边概率计算个体贡献度，
2、并通过程序的路径层图计算路径层接近度，再由个体贡献度及路径层接近度设计适应度函数.最后，本文利用多种群遗传算法进化生成测试数据以覆盖目标路径，在进化过程中子种群覆盖当前目标路径后，继续尝试覆盖与其相似的其它路径.实验结果表明，该方法与同类经典方法相比，在保证平均进化时间和平均进化代数占优的同时，稳定性也有所提高，生成时间增幅标准偏差较最优的降低10.19%，离散系数降低10.79%.进化代数增幅标准偏差较最优的降低19.98%，离散系数降低28.02%.关键词：关键边概率；路径层接近度；多路径覆盖；遗传算法；适应度函数；个体贡献度基金项目：国家自然科学基金（No.62262025）；江西省自然
3、科学基金（No.20224ACB202012）中图分类号：TP311文献标识码：A文章编号：0372-2112(2023)05-1341-09电子学报URL:http:/DOI:10.12263/DZXB.20220983An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer ProximityQIAN Zhong-sheng,CHENG Yi-wei,YU Qing-yuan,ZHANG Ding,YAO Chang-sen,QIN Lang-yue（School of I
4、nformation Management，Jiangxi University of Finance&Economics，Nanchang，Jiangxi 330013，China）Abstract:Using genetic algorithms to solve the problem of difficultly-covered edges in multi-path coverage is a hot research spot in the current field of automatic test data generation.An approach to multi-pa
5、th coverage testing that combines the key edge probability and path layer proximity is proposed,for the existing methods are not efficient enough to solve the multi-path coverage problem.Firstly,it calculates the probabilities of the nodes being traversed to get difficultly-covered nodes,and then fi
6、nds difficultly-covered edges(i.e.,key edges),so as to generate the target paths.Secondly,the individual contribution is calculated according to the key edge probability,and the path layer proximity is computed through the path layer graph of the program,and then the fitness function is designed fro
7、m the individual contribution and the path layer proximity.Finally,multi-population genetic algorithm is employed to generate test data in order to cover the target paths.After the subpopulation covers the current target path in the evolution process,it continues to try to cover other paths similar
8、to the current target path.Experimental results show that compared with those similar classic methods,this approach guarantees an improved stability besides dominant average generation time and average evolution time.The standard deviation of the generation time increase is lower than the optimal on
9、e by 10.19%,and the variation coefficient is lessen by 10.79%.The standard deviation of evolutionary time increase is lower than the optimal one by 19.98%,and the variation coefficient is decreased by 28.02%.Key words:key edge probability;path layer proximity;multi-path coverage;genetic algorithm;fi
10、tness function;individual contributionFoundation Item(s):National Natural Science Foundation of China(No.62262025);Jiangxi Provincial Natural Science Foundation(No.20224ACB202012)收稿日期：2022-08-24；修回日期：2022-12-28；责任编辑：覃怀银电子学报2023 年1引言目前对软件测试数据生成的研究较为广泛，研究者从不同角度提升测试效率.Sharifdipour等1提出一种模拟蚁群优化算法，提高蚂蚁的搜索
11、能力.Jatana等2利用粒子群优化与变异测试来生成测试数据.钱忠胜等3通过支持向量机回归模型预测个体适应度，并在进化中重用优秀个体.范书平等4根据分支均衡度设计合理适应度函数，以提高进化生成效率.钱忠胜等5通过关键点概率计算贡献度，据此设计适应度函数，进化生成测试数据.Qian等6改进个体信息共享方法，充分利用种群资源.杜莹等7利用精英策略建立优化模型，得到最优目标路径集.Dang等8提出一种模糊聚类和进化优化增强变异测试的方法.Sun 等9利用ESM（Ensemble Surrogate Model）模型生成测试数据.Kalaipriyan等10提出改进搜索策略的定向人工蜂群算法解决多目标
12、优化问题.由上可知，国内外学者已在测试生成领域取得一定成果，这些成果大多围绕多路径覆盖展开研究，但仍存在一定不足.现有判断路径难易覆盖的方法均从节点的角度考虑，路径覆盖难易程度和其包含节点的难易覆盖程度有一定关系，但还有很多其它因素.比如，包含几个难覆盖节点，并不代表该路径一定难覆盖.此外，如何恰当地设计多路径覆盖中遗传算法的适应度函数，也值得进一步研究.基于此，本文提出一种多路径覆盖测试，根据关键边概率和路径层接近度设计适应度函数，使优秀个体在进化过程中得到保护，同时结合个体信息共享策略的优势，既可保证个体信息在进化中被恰当地利用，又能避免进化时间被过多浪费，可进一步改善进化生成多路径覆盖测
13、试数据的效率.2相关定义为便于理解，先定义上面提到的相关概念，包括关键边概率、个体贡献度、路径层接近度等.2.1关键边概率定义1 关键边概率：难覆盖边被测试数据穿越的概率，记为G(Eij).其中Eij为难覆盖节点Ni与Nj构成的关键边.其概率为这两个节点的概率乘积.根据被测程序，随机生成测试数据，统计测试路径集中各节点的覆盖情况，可用Tij表示为式（1）.Tij=1 测试路径穿越节点Nj0 测试路径未穿越节点Nj（1）输入m组数据到被测程序中，可得到m条穿越路径组成的集合.这样，可构成穿越矩阵，记为C，可表示为式（2）.C=T11T1nTm1Tmn（2）其中，穿越矩阵的行代表执行被测程序得到的
14、路径；列代表路径中节点的被穿越情况.根据穿越矩阵C，得到穿越节点Nj的路径数，记为Sj，表示为Sj=i=1mTij（3）被测程序的节点概率G(Nj)，可表示为G(Nj)=Sj/m（4）被测程序关键边概率G(Eij)，可表示为G(Eij)=G(Ni)G(Nj)（5）2.2个体贡献度在进化算法中为判定个体优劣程度，可通过计算个体贡献度以考虑其是否需要被保留.定义2 个体贡献度：个体对进化生成目标路径所做贡献，记为Con=(lxPtar).其中lx(1xm)表示个体数为m的种群中某个个体，Ptar为目标路径集tar中某条目标路径.个体贡献度可表示为式（6），其中Eij表示lx对应的路径Plx与目标路
15、径Ptar的相同关键边.Con(lxPtar)=e-G(Eij)（6）2.3路径层接近度程序往往带来嵌套结构，为在适应度函数中反映此结构带来的影响，给出路径层图、路径层接近度等相关概念.定义3 路径层图（Path Layer Graph，PLG）：路径中各节点层级的图形描述，记为GL=（N，E，）.其中N为节点集，各节点均为基本语句块；E为边集，各边对应语句流向；为节点层级集合，层级从外层到内层按顺序编号，最外层为第一层，层级越高，其数值越大，表示该节点越难被执行到.从定义3不难看出，可通过赋予路径上的各条边不同的权重，从而反映嵌套结构带来的差异性.定义4 路径层接近度：测试路径与目标路径所在
16、层的接近程度，记为(Plx)，其中Plx为测试数据路径.路径层接近度可表示为(Plx)=(Eij)(Exy)（7）EijPlxPtarExyPtar；1ijxyn其中，Exy是目标路径中的边，Eij是测试路径与目标路径的共同边，(Exy)与(Eij)分别为边Exy与Eij的层级，见式（8）.(Ehk)=(Nh)+(Nk)2 1hkn（8）1342第 5 期钱忠胜:基于关键边概率与路径层接近度的多路径覆盖测试其中，(Nh)和(Nk)分别表示节点h和k的层级.对于式（8），因边由节点连接，故计算边的层级应考虑到相关节点的层级.3关键边概率与路径层接近度结合的多路径覆盖本文给出一种多路径覆盖测试，主要包括个体适应度模块和遗传算法模块.其总体框架如图1所示.3.1目标路径选取为获得目标路径，先计算被测程序的节点被穿越的概率，概率为0标记为不可达节点，为1标记为必达节点.对于其它节点根据设定的阈值判断（阈值是所有节点被穿越概率的平均值，该值会随着每组测试数据动态变化），低于阈值的记为难覆盖节点.若路径中某边的两节点均为难覆盖节点，则该边为难覆盖边（即，关键边），路径则看成是目标路径.按照各目标路
