An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer Proximity

QIAN Zhong-sheng; CHENG Yi-wei; YU Qing-yuan; ZHANG Ding; YAO Chang-sen; QIN Lang-yue

doi:10.12263/DZXB.20220983

您当前的位置：

首页 >

文章列表页 >

An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer Proximity

PAPERS | 更新时间：2025-12-08

- An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer Proximity
- ACTA ELECTRONICA SINICA Vol. 51, Issue 5, Pages: 1341-1349(2023)
- 作者机构：
  
  江西财经大学信息管理学院，江西南昌 330013
- 作者简介：
- 基金信息：
  
  Foundation Item(s):　Foundation Item(s): National Natural Science Foundation of China(62262025);Jiangxi Provincial Natural Science Foundation(20224ACB202012)
- DOI：10.12263/DZXB.20220983
  CLC： TP311
- Received：24 August 2022，
  
  Revised：2022-12-28，
  
  Published：25 May 2023
- 稿件说明：
移动端阅览
钱忠胜,成轶伟,俞情媛等.基于关键边概率与路径层接近度的多路径覆盖测试[J].电子学报,2023,51(05):1341-1349.

QIAN Zhong-sheng,CHENG Yi-wei,YU Qing-yuan,et al.An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer Proximity[J].ACTA ELECTRONICA SINICA,2023,51(05):1341-1349.
钱忠胜,成轶伟,俞情媛等.基于关键边概率与路径层接近度的多路径覆盖测试[J].电子学报,2023,51(05):1341-1349. DOI： 10.12263/DZXB.20220983.

QIAN Zhong-sheng,CHENG Yi-wei,YU Qing-yuan,et al.An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer Proximity[J].ACTA ELECTRONICA SINICA,2023,51(05):1341-1349. DOI： 10.12263/DZXB.20220983.

摘要

遗传算法解决多路径覆盖中难覆盖边的问题，是当前软件测试数据自动生成领域的一个研究热点.现有方法解决多路径覆盖问题的效果不够理想，本文提出一种将关键边概率与路径层接近度相结合的多路径覆盖测试方法.首先，本文计算节点被穿越概率找到难覆盖节点，通过难覆盖节点找到难覆盖边（即，关键边），生成目标路径.然后，本文根据关键边概率计算个体贡献度，并通过程序的路径层图计算路径层接近度，再由个体贡献度及路径层接近度设计适应度函数.最后，本文利用多种群遗传算法进化生成测试数据以覆盖目标路径，在进化过程中子种群覆盖当前目标路径后，继续尝试覆盖与其相似的其它路径.实验结果表明，该方法与同类经典方法相比，在保证平均进化时间和平均进化代数占优的同时，稳定性也有所提高，生成时间增幅标准偏差较最优的降低10.19%，离散系数降低10.79%.进化代数增幅标准偏差较最优的降低19.98%，离散系数降低28.02%.

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-path 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 finds 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 from 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 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 one 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%.

关键词

Keywords

references

SHARIFIPOUR H , SHAKERI M , HAGHIGHI H . Structural test data generation using a memetic ant colony optimization based on evolution strategies [J]. Swarm & Evolutionary Computation , 2018 , 40 ( 6 ): 76 - 91 .

JATANA N , SURI B . Particle swarm and genetic algorithm applied to mutation testing for test data generation: A comparative evaluation [J]. Journal of King Saud University-Computer and Information Sciences , 2020 , 2 ( 4 ): 514 - 521 .

钱忠胜 , 俞情媛 , 宋涛 , 等 . 基于支持向量机回归模型的测试用例生成与重用 [J]. 电子学报 , 2021 , 49 ( 7 ): 1386 - 1391 .

QIAN Zhong-sheng , YU Qing-yuan , SONG Tao , et al . Test case generation and reuse based on support vector machine regression model [J]. Acta Electronica Sinica , 2021 , 49 ( 7 ): 1386 - 1391 . (in Chinese)

范书平 , 张岩 , 马宝英 , 等 . 基于均衡优化理论的路径覆盖测试数据进化生成 [J]. 电子学报 , 2020 , 48 ( 7 ): 1303 - 1310 .

FAN Shu-ping , ZHANG Yan , MA Bao-ying , et al . Evolutionary generation of test data for paths coverage based on balance optimization theory [J]. Acta Electronica Sinica , 2020 , 48 ( 7 ): 1303 - 1310 . (in Chinese)

钱忠胜 , 祝洁 , 朱懿敏 , 等 . 结合关键点概率与路径相似度的多路径覆盖策略 [J]. 软件学报 , 2022 , 33 ( 2 ): 434 - 454 .

QIAN Zhong-sheng , ZHU Jie , ZHU Yi-min , et al . Multi-path coverage strategy combining key point probability and path similarity [J]. Journal of Software , 2022 , 33 ( 2 ): 434 - 454 . (in Chinese)

QIAN Zhongsheng , HONG Dafei , ZHAO Chang , et al . A strategy for multi-target paths coverage by improving individual information sharing [J]. KSII Transactions on Internet and Information Systems , 2019 , 13 ( 11 ): 5464 - 5488 .

杜莹 , 孙百才 , 巩敦卫 , 等 . 软件测试路径选择优化模型及其进化求解 [J]. 软件学报 , 2022 , 33 ( 9 ): 3297 - 3311 .

DU Ying , SUN Bai-cai , GONG Dun-wei , et al . Optimization model of path selection for software testing and its evolution-based solution [J]. Journal of Software , 2022 , 33 ( 9 ): 3297 - 3311 . (in Chinese)

DANG Xiangying , GONG Dunwei , YAO Xiangjuan , 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 .

SUN Baicai , GONG Dunwei , TIAN Tian , et al . Integrating an ensemble surrogate model's estimation into test data generation [J]. IEEE Transactions on Software Engineering , 2022 , 48 ( 4 ): 1336 - 1350 .

KALAIPRIYAN T , RAJESWARI M , DEBNATH B , et al . Directed artificial bee colony algorithm with revamped search strategy to solve global numerical optimization problems [J]. Automated Software Engineering , 2022 , 29 ( 1 ): 13 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Genetic Algorithm Based MIMO Equalization Parameter Optimization Technology for Mode-Division Multiplexed System

An Absorbing Structure Covering the Whole UHF Band

A Consortium Blockchain Based Reliable Task Offloading Approach in Edge Computing

One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

Related Author

YU Qing-yuan

QIN Lang-yue

ZHAO Tian-feng

WEN Feng

FENG Bian-xia

WU Bao-jian

XU Bo

QIU Kun

Related Institution

Key Laboratory of Optical Fiber Sensing and Communication Networks, Ministry of Education, University of Electronics Science and Technology of China

School of Electronics and Information， Northwestern Polytechnical University

Key Laboratory for Novel Software Technology， Nanjing University

Guangdong Provincial Laboratory of Artificial Intelligence and Digital Economy

College of Big Data and Intelligent Engineering， Southwest Forestry University

⁰