一种新的多路径覆盖测试数据进化生成方法

《一种新的多路径覆盖测试数据进化生成方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第６期电子学报Ｖｏｌ．３８Ｎｏ．６２０１０年６月ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡＪｕｎ．２０１０一种新的多路径覆盖测试数据进化生成方法巩敦卫１，张岩１，２（１．中国矿业大学信息与电气工程学院，江苏徐州２２１１１６；２．牡丹江师范学院计算机科学与技术系，黑龙江牡丹江１５７０１２）摘要：提出一种新的用于多路径覆盖的测试数据生成方法．首先，将被测程序表示成一棵二叉树，对目标路径采用赫夫曼编码方法表示成二进制串；然后，采用遗传算法生成多个测试数据，设计的适应度函数综合考虑个体穿越的路径与每个目标路径的匹配程度．将提出的方法用

2、于４个基准程序的路径覆盖测试数据生成，并与已有方法比较，结果表明本文方法计算量小，生成测试数据效率高．关键词：软件测试；路径覆盖；测试数据；遗传算法；赫夫曼编码中图分类号：ＴＰ３０１文献标识码：Ａ文章编号：０３７２２１１２（２０１０）０６１２９９０６ＮｏｖｅｌＥｖｏｌｕｔｉｏｎａｒｙＧｅｎｅｒａｔｉｏｎＡｐｐｒｏａｃｈｔｏＴｅｓｔＤａｔａｆｏｒＭｕｌｔｉｐｌｅＰａｔｈｓＣｏｖｅｒａｇｅ１，ＺＨＡＮＧＹａｎ１，２ＧＯＮＧＤｕｎｗｅｉ（１．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎａｎｄＥｌｅｃｔｒｉｃａｌＥｎｇｉｎｅｅｒｉｎ

3、ｇ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｉｎｇａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｘｕｚｈｏｕ，Ｊｉａｎｇｓｕ２２１１１６，Ｃｈｉｎａ；２．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＭｕｄａｎｊｉａｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｍｕｄａｎｊｉａｎｇ，Ｈｅｉｌｏｎｇｊｉａｎｇ１５７０１２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｎａｐｐｒｏａｃｈｔｏｇｅｎｅｒａｔｉｎｇｔｅｓｔｄａｔａｆｏｒｍｕｌｔｉｐｌｅｐａｔｈｓｃｏｖｅｒａｇｅｉｓｐｒｅｓｅｎｔｅｄ．Ｆｉｒｓｔ，ｔｈｅｐｒｏｇｒａｍｕｎｄ

4、ｅｒｔｅｓｔｉｓｅｘｐｒｅｓｓｅｄａｓａｂｉｎａｒｙｔｒｅｅ，ａｎｄｔｈｅｔａｒｇｅｔｐａｔｈｓａｒｅｅｎｃｏｄｅｄｉｎｔｏａｂｉｎａｒｙｓｔｒｉｎｇｕｓｉｎｇＨｕｆｆｍａｎｃｏｄｉｎｇ；ｔｈｅｎ，ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓｅｍｐｌｏｙｅｄｔｏｇｅｎｅｒａｔｅｍｕｌｔｉｐｌｅｔｅｓｔｄａｔａ，ａｎｄａｎｉｎｄｉｖｉｄｕａｌ′ｓｆｉｔｎｅｓｓｉｓｔｈｅｄｅｇｒｅｅｏｆｔｈｅｔｒａｖｅｒｓｅｄｐａｔｈｍａｔｃｈｉｎｇｔｈｅｔａｒｇｅｔｐａｔｈｓ．Ｔｈｅｐｒｏｐｏｓｅｄａｐｐｒｏａｃｈｉｓａｐｐｌｉｅｄｔｏ４ｂｅｎｃｈ

5、ｍａｒｋｐｒｏｇｒａｍｓ，ａｎｄｃｏｍｐａｒｅｄｗｉｔｈｐｒｅｖｉｏｕｓａｐｐｒｏａｃｈｅｓ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｐｐｒｏａｃｈｎｅｅｄｓｓｍａｌｌａｍｏｕｎｔｏｆｃａｌｃｕｌａｔｉｏｎａｎｄｈａｓｈｉｇｈｅｆｆｉｃｉｅｎｃｙｉｎｇｅｎｅｒａｔｉｎｇｔｅｓｔｄａｔａ．Ｋｅｙｗｏｒｄｓ：ｓｏｆｔｗａｒｅｔｅｓｔｉｎｇ；ｐａｔｈｃｏｖｅｒａｇｅ；ｔｅｓｔｄａｔａ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ；Ｈｕｆｆｍａｎｃｏｄｉｎｇ测试数据非常关键．但是，现有文献适应度函数大多是１引言针对一条目标路

6、径设计的，这将导致ＧＡ的一次运行，［１］软件测试是保障软件质量的重要手段，测试数据只能生成穿越一条路径的测试数据．因此，有必要提高自动生成问题是软件测试的核心问题之一．路径覆盖测生成测试数据的效率．为解决这一问题，Ａｈｍｅｄ等首次试是指在测试过程中，尽可能覆盖程序所有可行路径，提出基于ＧＡ的多路径测试数据进化生成方法，将测试许多软件测试问题都可以归结为路径覆盖测试的数据数据生成问题转化为多目标优化问题，利用ＧＡ解决该［２］生成问题．问题时，分别计算进化个体对不同目标的满足程度，使遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ，Ｇ

7、Ａ）是用于测试数据得一次运行ＧＡ，生成分别穿越多条目标路径的多个测的自动生成的有效方法．目前已有许多研究成果，如试数据［７］，并用实验验证了该方法生成测试数据优于单［３］Ｃｈｅｎ等采用多种群ＧＡ生成覆盖路径的测试数据，路径生成方法．Ａｈｍｅｄ方法的适应度函数由２部分组［４］Ｓｏｆｏｋｌｅｏｕｓ等基于ＧＡ建立了动态软件测试框架，Ｒａ成，分别是层接近度和支距离，其中，层接近度指测试数ｊａｐｐａ等利用ＧＡ并结合图论知识，生成软件的测试用据穿越的路径与每个目标路径不匹配的结点个数之和；［５］［６］例，Ｂｏｕｃｈａｃｈｉａ将免疫ＧＡ用

8、于测试数据生成中等．支距离反映被穿越的路径与目标路径分支语句的前件这些成果极大地丰富了进化测试理论．还有多少距离，将支距离和层接近度之和作为个体相对用ＧＡ生成覆盖路径的测试数据，需要将该问题转于一个目标路径的适应值，将个体针对所有目标路径的化为函数优化问题．适应度函数的设计对