基于元启发优化算法的数值型蜕变关系生成方法.pdf

第2 9 卷第1 期2024年1 月doi:10.13682/j.issn.2095-6533.2024.01.009基于元启发优化算法的数值型蜕变关系生成方法西安邮电大学学报JOURNAL OF XIAN UNIVERSITY OF POSTS AND TELECOMMUNICATIONSVol.29No.1Jan,2024王曙燕1 2，王思维（1.西安邮电大学计算机学院，陕西西安7 1 0 1 2 1;2.西安市物联网智能信息采集与处理工程研究中心，陕西西安7 1 0 1 2 1)摘要：针对蜕变测试难以获取蜕变关系且容易出现错误导致测试成本过高的问题，提出一种基于元启发优化算法的数值型蜕变关系生成方法。通过分析数值型蜕变关系的数学特征并组合等式与不等式关系，构成输入、输出参数矩阵。结合粒子群和模拟退火两种元启发优化搜索算法，设定合适的代价函数，将构成的参数矩阵作为搜索粒子，搜索并生成各种等式、不等式的蜕变关系。实验结果表明，与仅使用一种搜索算法相比，所提方法能够在不改变解的类型情况下跳过局部最优，节省时间开销，提高了蜕变关系生成效率。关键词：软件测试；蜕变测试；蜕变关系；粒子群算法；模拟退火算法中图分类号：TP311.5Generation method of numerical metamorphic relations based on(1.School of Computer Science of Technology,Xian University of Posts and Telecommunications,Xian 710121,China;2.Xian Engineering Research Center of IoT Intelligent Information Collection and Processing,Xian 710121,China)Abstract:A numerical metamorphic relationship generation method based on metaheuristic optimi-zation algorithm is proposed to address the problem of difficult to obtain metamorphic relationshipsand high testing costs caused by errors in metamorphic testing.By analyzing the mathematical char-acteristics of numerical metamorphic relationships and combining equations and inequality relation-ships,an input and output parameter matrix is formed.Through the combination of two metaheu-ristic optimization algorithms,namely the particle swarm optimization and the simulated annealing,appropriate cost functions are set,and the constructed parameter matrix is used as the search parti-cle to search and generate metamorphic relationships of various equations and inequalities.Experi-ment results show that compared to using only one search algorithm,the proposed method can skiplocal optima without changing the type of solution,and can save the time costs and improve the effi-ciency of metamorphic relationship generation.Keywords:software testing;metamorphic testing;metamorphic relationships;particle swarm algo-rithm;simulated annealing algorithm传统软件测试技术检验待测程序时，是通过对比测试用例的实际输出和预期输出是否相等来确定执行结果与期望结果是否相同，但在多数情况下测试人员难以构造程序的预期输出或预期输出收稿日期：2 0 2 3-0 3-2 8基金项目：陕西省教改重点攻关项目（2 1 BG038）引文格式：王曙燕，王思维.基于元启发优化算法的数值型蜕变关系生成方法J.西安邮电大学学报，2 0 2 4，2 9（1）：8 1-8 6.WANG S Y,WANG S W.Generation method of numerical metamorphic relations based on metaheuristic algorithmJJ.Journal ofXian University of Posts and Telecommunications,2024,29(1):81-86.文献标识码：Ametaheuristic algorithmWANG Shuyan2,WANG Siweil文章编号：2 0 9 5-6 533（2 0 2 4)0 1-0 0 8 1-0 6结果，即存在Oracle问题。而蜕变测试2 1（Meta-morphic Testing,MT)则是通过构建输人和输出结果的蜕变关系（Metamorphic Relationships,MR），根据蜕变关系是否保持不变来测试软件的可靠性，82无需构建预期输出，有效改善了Oracle问题3,现已广泛应用于图像识别4、搜索引擎5-6 和神经网络机器翻译评估7 等领域。蜕变测试的本质是对多组输人和输出之间是否满足蜕变关系进行验证，因此需要找到适合的蜕变关系，但其对于一个简单的程序都会需要大量的蜕变关系及测试用例8 ,增加了测试成本。目前,对于削减蜕变测试成本的方法主要包括蜕变关系构造9-1 0 、测试用例选取及蜕变关系自动化生成，如Zhang等1 2 提出了一种新的系统推断和净化蜕变关系的方法，穆翔宇等1 3 提出一种基于梯度下降算法的蜕变关系生成方法，研究蜕变关系的多项式形式，张瀚月1 4提出一种面向数值计算程序的蜕变关系获取方法。然而，上述方法对于蜕变关系的选取均为数值型，多是简单的线性或非线性关系1 3-1 4，仅使用单一的算法或者搜索方法难以高效识别各种类型的蜕变关系，生成全面准确的蜕变关系较为困难，导致蜕变测试成本还是较高。针对蜕变测试难以高效识别蜕变关系且测试成本过高的问题，提出一种基于元启发优化算法的数值型蜕变关系生成方法。该方法在对蜕变关系形式化的基础上将蜕变关系进行参数化，并将粒子群1 51(Particle Swarm Optimization,PSO)和模拟退火1 6-1 7（SimulateAnnealing，SA)两种元启发优化搜索算法相结合，利用PSO-SA算法多次执行程序，识别和生成大量数值型蜕变关系。最后，以科学数学库中的数值程序为研究目标，与其他蜕变关系生成方法在生成蜕变关系效率方面进行对比，验证所提方法的性能。1蜕变测试原理蜕变测试原理2 是利用正确的测试用例（未能发现错误的用例）构建新的测试用例检测程序，通过检测测试用例与衍生用例之间的关系在测试中是否保持不变判断程序正确与否，而无需构建预期输出。定义1 假设使用程序P计算函数f，f 的n组变量为i,，,n（n 1）,对应的结果为f(a），f(2),f(c）。若1,az,满足关系r,f(ai),f(a2),f(an)满足关系ry，即r(ai,2,.,an)=rr(f(ai),f(a2),.,f(a,)则称（r，r）为P的蜕变关系。同理，若P是正确的，则其将满足推导式西安邮电大学学报r(I,I2,.,I,)rr(P(I),P(I2),.,P(I,)其中，I,I2，,I为P对应1,2，,n的输人,P(I),P(I,),P(In)为对应输出。通过测试蜕变关系成立与否可验证程序P是否正确。2数值型蜕变关系生成方法基于元启发优化算法的数值型蜕变关系生成方法主要分为蜕变关系参数化和搜索蜕变关系参数。蜕变关系参数化是指根据数值型蜕变关系的特点，对蜕变关系先进行形式化，以推导式方法表达，然后分析其数学特征，等式问题可将输入、输出关系参数化并以矩阵的形式表现，不等式问题则使用加入随机矩阵的方法进行处理。组合等式与不等式关系，产生构成输入、输出参数的A、B矩阵。搜索蜕变关系参数是指在构成参数矩阵的基础上,使用 PSO-SA算法将参数矩阵作为搜索粒子，设定合适的代价函数使搜索算法向代价更小的方向搜索，从而得到合适的参数矩阵。该方法实现流程如图1 所示。参数化输入、输出关系构成A、B矩阵生成基本输入根据基本输入和矩阵A生成所有输入立设定粒子的代价函数立搜索蜕变关系参数矩阵A、B立生成蜕变关系参数结束图1 方法实现流程2.1虫蜕变关系参数化2.1.1娄数值蜕变关系形式化定义2 对于被测程序P，假设程序接受输人后产生相应的输出为P(I）=O，每个输入I是具有n个元素的向量，即I=（I i,I 2，,I n）T，每个输出0是具有m个元素的向量，即0=（O，O z，,O m）T，则将蜕变关系形式化2 为2024年1 月开始第2 9 卷第1 期R.(1,I2,.,I,)=R。(O r,O 2,.,O m)式中：I,I，,I，为输人，I为基本输人,其余的为衍生输人；O1，O 2，,O m 为对应的输出；R为输入之间的关系，R。为输出之间的关系。虽然式（1)可以表示一个蜕变关系，但是R和R。的形式并不能确定,不能推理蜕变关系。考虑到数值型蜕变关系大多为多项式、不等式等线性或非线性的表达式，因此可将R，和R。限制其中，使用线性、非线性表达式的参数值表示一个蜕变关系。2.1.2输人关系参数化使用矩阵方法1 2 进行输入关系参数化，表征蜕变关系。假设向量u包含基本输入I1的指数从0 到k的所有可能组合，由多项式的展开项数公式得到u的元素数量为t=1+n+CH2-+.+C#i-1为了满足R，除了I不用表示外，其他衍生输入均可表示为I,=Au，其中：j=2,3,n；A,为输人关系的n行t列矩阵，则其他衍生输入关系可以表示为R:I,=Aju对于不等式关系R:I,Au和R:l 0R。:Bv En式中：为接受新解的概率；E，为，对应的系统能量（目标函数）；E+1为n+1对应的系统能量；T为温度。将PSO和SA两种元启发优化搜索算法相结合，在PSO算法中引入Metropolis准则，即跳出局部最优机制，改进PSO算法不善于摆脱局部极值点(2)的缺点，并保留简单的优点，加快算法的收敛进程，减少陷入局部最优的风险。PSO-SA算法的流程如图2 所示。初始化、设置初始温度(3)定义适应度函数是满足结束条件(4)工否更新粒子速度和位置评估粒子的适应度更新粒子最优位置(5)计算适应度之差（6)是接受新解(7)(8)83.陷入局部最优。SA算法也是一种元启发优化算法，在搜索过程中引入随机因素，迭代新的可行解(9)开始适应度之差0按Metropolis准则接受新解立退温满足结束条件是结束图2 PSO-SA算法流程Ei+1 E,否否84在PSO-SA算法中,设置适应度函数1-1 2（代价函数)评价粒子性能。设随机生成的测试输人个数为s，通过测试的输人个数为q。对于等式蜕变关系，粒子的适应度为所有输入到0 的累积距离，即满足矩阵B、相乘后的累加结果，适应度函数表示为C(A,B)=2 IBv:/1对于不等式蜕变关系，粒子代价是失败测试粒子的比例，适应度函数表示为C(A,B)=1-IS给定一个待测程序P和输入I1，I 2，,I n，将推断数值程序蜕变关系1 9-2 0 1 问题转化为寻找满足输人、输出关系的矩阵对2 1 A、B的搜索问题，一个粒子代表一个矩阵对，多次执行PSO-SA算法，此时最优解也即就是蜕变关系的多项式参数。3实验结果及分析3.1实验设置实验环境设置为IntelCore2.20GHz处理器、12 GiB内存和Pycharm开发平台。为了验证所提基于元启发优化算法的数值型蜕变关系生成方法的有效性，将所提方法应用在Python的科学数学函数库Numpyl.14的2 5个数学程序上。数学程序包括abs、a r c c o s、a r c c o s h、a r c s i n、a r c s i n h、a r c t a n、arctanh、c e i l、c o s、c o s h、e x p、f l o o r、l o g、l o g 1 p、l o g10、a ma x、a mi n、r o u n d、s i n、s i n h、s q r t、t a n、t a n h 等23个单变量输人和输出程序，以及arctan2、h y p o t两个多重化输人和输出程序。实验参数设置：在粒子群算法中设置学习因子为1.49 445；粒子个数为30；迭代次数为350；初始输入输出关系的系数区间为一2,2 ；常数区间为一1 0,1 0；设置惯性权重分别为0.9、0.4。在模拟退火算法中，设置初始、终止温度分别为1 0 0 0 0、0，更新步长为0.8。3.2实验结果分别使用单一使用粒子群算法的Au-toMR121和所提方法在2 5个科学数学程序上搜索蜕变关系，执行时间分别如表1 和表2 所示。对比表1 和表2 数据可知,单一使用粒子群算法的Au-toMR执行时间约为2 7 9 6 47 32 s，在arctan2数学程序上执行时间最长，而所提方法执行时间约为西安邮电大学学报272536 0 2 s，并在tan数学程序上执行耗时最少。对比2 5个科学数学程序方法的执行总时间，所提方法相较于AutoMR执行时间节省了2185.383s，耗时降低了2.8 4%，生成蜕变关系较为高效。表1 AutoMR搜索蜕变关系的执行时间/s序科学数(10)号学程序1abs2arccos3arccosh(11)4arcsin5arcsinh6arctan7arctan28arctanh9ceil10cos11cosh12exp13floor表2 月所提方法搜索蜕变关系的执行时间/s序科学数号学程序1abs2arccos3arcosh4arcsin5arcsinh6arctan7arctan28arctanh9ceil10coS11cosh12exp13floor所提方法在每个科学数学程序中生成1 3个不同类别的文件，每个文件中分别生成35个蜕变关系。为了进一步验证所提方法的高效性，在每个科学数学程序生成1 3个类别文件的基础上，选取具有代表性的单个数学程序abs、a r c c o s 和arctan2，分别对比AutoMR和所提方法生成蜕变关系的耗时,结果如图3所示。2024年1 月执行序科学数时间号学程序3601.559143701.063153 406.995163065.746173030.938182906.841194 732.245202872.933212.796.018222.807.861232800.860242.802.752252802.311执行时间3601.5593118.4752914.7513 119.5223018.5672861.2113266.9672898.0212 804.7472812.2432829.7552820.2412821.356执行时间hypot3232.3761og2814.782loglp2909.4161og102807.515amax3396.160amin3406.281round3028.314sin2823.828sinh2812.234sqrt2812.529tan2814.360tanh2819.454序科学数号学程序14hypot151og16loglp171og1018amax19amin20round21sin22sinh23sqrt24tan25tanh执行时间3 261.3322837.3372927.2392 818.0563407.9343413.0203048.4062879.2753 017.2432785.5542725.2732 812.004第2 9 卷第1 期800700600500400300200100700600500E3002001008007006005000400300200100由图3可知，在单个数学程序中，所提方法生成每个类别蜕变关系耗时明显减少，图3（b)中有两个类别的蜕变关系耗时平均减少1 0 7 s，说明所提方法在一定程度上提升了蜕变关系的生成效率，节省了时间开销，降低了蜕变测试成本。4结语基于元启发优化算法的数值型蜕变关系生成王曙燕，等：基于元启发优化算法的数值型蜕变关系生成方法四 AutoMR所提方法文件类别(a)abs四AutoMR口所提方法文件类别(b)arccos四 AutoMR所提方法文件类别(c)arctan2图3两种方法耗时对比结果85.方法使用矩阵形式对输入输出的蜕变关系进行参数化，通过粒子群和模拟退火相结合的搜索算法生成各种等式或不等式蜕变关系，从而推断出数值蜕变关系。实验结果表明，相比于单一的粒子群算法，使用基于元启发优化算法的数值型蜕变关系生成方法在生成蜕变关系的耗时上降低了2.8 4%，节省时间开销，提高了蜕变关系生成效率，降低了蜕变测试成本。但是，所提方法仅考虑了数值型的蜕变关系生成，未来将对非数值型蜕变关系进行深人研究。参考文献1王曙燕，张海清，孙家泽.改进教与学算法的两两组合测试数据生成J.西安邮电大学学报，2 0 2 0，2 5（2）：41-45.WANG S Y,ZHANG H Q,SUN J Z.Improved pair-wise test data generation of teaching-learning-basedoptimization algorithmsJJ.Journal of Xian Universi-ty of Posts and Telecommunications,2020,25(2):41-45.(inChinese)2CHEN T Y,CHEUNG S C,YIU S M.Metamorphic tes-ting:A new approach for generating next test cases,tech-nical report HKUST-CS98-01R.Hong Kong,1998.3QIU K,ZHENG Z,CHEN T Y,et al.Theoretical andempirical analyses of the effectiveness of metamorphicrelation compositionJ.IEEE Transactions on Soft-ware Engineering,2022,48(3):1001-1017.4江竞捷，徐络，李宁.基于GAN的图像识别系统蜕变测试方法J.计算机与现代化，2 0 2 1（2）：2 4-2 9.JIANG J J,X L,LI N.Method of metamorphic testingfor image recognition system based on GANLJI.Com-puter and Modernization,2021(2):24-29.(in Chinese)5 林杨正龙，高建华.基于蜕变测试的面向用户搜索引擎性能分析J.计算机工程，2 0 1 9，45（1 0）：52-56.YANG Z L,GAO J H.User-oriented performance a-nalysis of search engine based on metamorphic testJ.Computer Engineering,2019,45（1 0):52-56.(in C h i-nese)6ZHOU Z Q,XIANG S,CHEN T Y.Metamorphic tes-ting for software quality assessment:A study of searchenginesJ.IEEE Transactions on Software Engineer-ing,2016,42(3):264-284.7PESU D,ZHOU Z Q,ZHEN J,et al.A monte carlomethod for metamorphic testing of machine translationservicesCJ/Proceedings of the 2018 IEEE/ACM 3rdInternational Workshop on Metamorphic Testing(MET).Gothenburg:IEEE,2018:38-45.8王曙燕，张振豪，孙家泽.一种覆盖数据压缩的测试用86例优先排序J.西安邮电大学学报，2 0 2 0，2 5（3）：82-87.WANG S Y,ZHANG Z H,SUN J Z.Test case priori-tization based on coverage compactionJ.Journal ofXi an University of Posts and Telecommunications,2020,25(3):82-87.(in Chinese)9SSU F H,BELL.J,MURPHY C,et al.Dynamic infer-ence of likely metamorphic properties to support differ-ential testingCJ/Proceedings of the 10th Internation-al Workshop on Automation of Software Test.Flor-ence:IEEE,2015:55-59.1o CHEN T Y,POON P L,XIE X.METRIC:Metamor-phic relation identification based on the category-choiceframeworkLJ.Journal of Systems&Software,2016,116:177-190.11 ZHANG J,CHEN J,HAO D,et al.Search-based infer-ence of polynomial metamorphic relations C/Pro-ceedings of the 29th ACM/IEEE International Confer-enceon Automated Software Engineering.S.I.:ACM,2014:701-712.12J ZHANG B,ZHANG H,CHEN J,et al.Automatic dis-covery and cleansing of numerical metamorphic rela-tionsCJ/Proceedings of the 2019 IEEE InternationalConference on Software Maintenance and Evolution(ICSME).Cleveland:IEEE,2019:235-245.13穆翔宇，范钰，李苏吉.一种基于梯度下降算法的蜕变关系生成方法J.吉林大学学报（理学版），2 0 2 0，58(6):1429-1435.MU X Y,FAN Y,LI S J.Method of generating meta-morphic relationship based on gradient descent algo-rithmJJ.Journal of Jilin University(Science Edition),2020,58(6):1429-1435.(in Chinese)14张瀚月.一种面向数值计算程序的蜕变关系获取方法D.吉林：吉林大学，2 0 2 1.ZHANG H Y.A method of obtaining metamorphic re-lations for numerical computation programsD.Jilin:Jilin University,2021.(in Chinese)15 KENNEDY J.Particleswarm optimizationMJ.Ency-clopedia of Machine Learning.Springer:2010:760-766.1 6 陈华根，吴健生，王家林.模拟退火算法机理研究J.同济大学学报（自然科学版）2 0 0 4，32（6）：8 0 2-8 0 5.CHEN H G,WU J S,WANG J L.Mechanism study ofsimulated annealing algorithmJJ.Journal of Tongji U-niversity(Natural Science),2004,32（6):8 0 2-8 0 5.（inChinese)1 7 闫群民，马瑞卿，马永翔，等，一种自适应模拟退火粒子西安邮电大学学报群优化算法J.西安电子科技大学学报，2 0 2 1，48（4：120-127.YAN Q M,MA R Q,MA Y X,et al.Adaptive simula-ted annealing particle swarm optimizationalgorithmJ.Journal of Xidian University,2021,48(4):120-127.(in Chinese)18魏雅娟，刘兆，刘意先，等.动态K-means与粒子群的网络态势预测优化算法J.西安邮电大学学报，2 0 2 0，25(5):33-38.WEI Y J,LIU Z,LIU Y X.A network situation pre-diction optimal algorithm based on dynamic K-meansclusteringand particle swarm optimization J.Journalof Xian University of Posts and Telecommunications,2020,25(5):33-38.(in Chinese)19 NIU X T,SUN Y J,WU H Y,et al.Enhance combina-torial testing with metamorphic relations J.IEEETransactions on Software Engineering,2022,48(12):5007-5029.20 LIN J,HUANG Y,CAI L.Metamorphic relationshipgeneration based on t-distribution zeroth-order optimi-zation methodCJ/Proceedings of the 2021 14th In-ternational Symposium on Computational Intelligenceand Design(ISCID).Hangzhou:IEEE,2021:316-320.21 ZHANG B.Mining numerical relations for improvingsoftware reliabilityCJ/Proceedings of the 2021 IEEEInternational Symposium on Software Reliability Engi-neering Workshops(ISSREW).Wuhan:IEEE,2021:310-313.作者简介2024年1 月王曙燕（1 9 6 4一），女，河南南阳人，博士，西安邮电大学二级教授，可信软件研究方向学术带头人，主要研究方向为可信软件。E-mail:王思维（1 9 9 8 一），女，陕西西安人，西安邮电大学硕士研究生，主要研究方向为软件测试、蜕变测试。E-mail:责任编辑：祝剑