《基于程序路径分析的有效蜕变测试.doc》由会员分享，可在线阅读，更多相关《基于程序路径分析的有效蜕变测试.doc（13页珍藏版）》请在金锄头文库上搜索。
1、基于程序路径分析的有效蜕变测试* 本课题得到国家杰出青年科学基金项目(60425206), 国家自然科学基金重大研究计划(90818027)与重点项目(60633010), 国家高技术研究发展计划(863计划)目标导向类项目(2009AA01Z147), 国家自然科学基金项目(60773104)的资助. 董国伟,男,1983年生,博士研究生,研究方向为软件分析与测试, Email: , 电话:13675106871; 聂长海,男,1971年生,博士,副教授,研究方向为软件工程和软件测试技术、模糊信息处理、神经网络等, Email: , 电话:13851784496; 徐宝文,男,1961年生,
2、教授,博士生导师,研究方向为程序设计语言,软件工程,并行与网络软件等, Email: ,电话: 13327800488.董国伟 聂长海 徐宝文(东南大学计算机科学与工程学院南京210096)(江苏省软件质量研究所南京210096)摘 要 蜕变测试对于预期输出难以构造的程序是实用和高效的. 作者在系统研究已有蜕变测试方法和路径分析技术的基础上，首先针对使用二元蜕变关系的测试提出了一组蜕变测试准则，以在多个不同的层次上定义蜕变测试用例集的充分性；然后给出了三种能够生成相应测试用例集的算法；最后通过变异分析的方法证实这些算法的有效性. 实验结果表明蜕变关系和测试准则的选取直接影响到测试的效果，另外，
3、使用蜕变关系全路径覆盖可满足性算法(APCEMST)可以快速准确地发现待测程序中的错误，而生成的测试用例的数量却比传统技术要少.关键词 软件测试; 蜕变测试; oracle问题; 蜕变关系; 路径覆盖准则Effective Metamorphic Testing Based on Program Path Analysis*DONG Guo-Wei NIE Chang-Hai XU Bao-Wen( School of Computer Science and Engineering , Southeast University , Nanjing 210096 )( Jiangsu Inst
4、itute of Software Quality , Nanjing 210096 )Abstract Metamorphic testing is very practical and effective for programs with oracle problems. Much research has been done in this field. Based upon existed methods of metamorphic testing and program path-analysis, the authors first present a set of metam
5、orphic testing criteria for the test with binary metamorphic relations. These criteria define the adequacy of metamorphic test suites at several different levels. Then, three new testing algorithms are given to generate test suites that could satisfy the criteria above. Finally, these algorithms per
6、formances are fully proved with the technique of mutation analysis. The experiment results show that testing effects are greatly decided by the selection of metamorphic relations and testing criteria, and the algorithm APCEMST could detect faults quickly and exactly with fewer test cases than tradit
7、ional method.Keywords software testing; metamorphic testing; oracle problem; metamorphic relation; path-coverage criterion1 引言软件测试是一种重要的、不可缺少的软件质量保证技术，用于发现和纠正软件中存在的缺陷和错误。但在很多情况下，测试时存在着oracle问题1，即测试人员很难构造程序的预期输出，确定执行结果与期望结果是否相同。为了能够有效地解决此类问题， Chen等人提出了蜕变测试 (metamorphic testing) 的概念2，该方法通过检查程序的多个执行结果之
8、间的关系来测试程序，不需要构造预期输出。蜕变测试技术具有三个突出的特点：为了检查程序的执行结果，测试时需要构造蜕变关系2；为了从多个方面判定程序功能的正确性，测试时通常需要构造多条蜕变关系；为了获得原始测试用例2，蜕变测试需要与其他测试用例生成方法相结合。Chen和吴鹏分析了使用特殊值和随机值作为原始用例时的差异3,4，吴鹏还提出了迭代蜕变测试算法 (IMT) 以循环地产生原始用例5，但复杂度较高，我们基于路径分析技术对IMT算法进行了改进6。Chen和Mayer还通过实验对比总结出了蜕变关系选取的一般性策略7, 8；虽然对于蜕变测试技术自身的改进可以提高测试效率，但它经常与其他验证或测试技术
9、结合使用。Chen将蜕变测试与全局符号执行结合提出了一种准验证方法9。将蜕变技术与基于缺陷的测试10、STECC11、基于模型的测试12等方法结合，也可以获得高效的测试技术；蜕变测试技术的实用性使得它已经被广泛地应用于数值型程序13、图论计算程序14、图象处理软件14-16、并行编译器14、交互式软件14、铸造模拟软件17、普适计算软件18,19、SOA软件20,21和面向对象软件22-25等的测试中。上述研究证实了蜕变测试在解决oracle问题时的有效性，但是这些方法大都只考虑程序的功能，没有充分利用程序结构的信息。本文针对二输入蜕变关系，在程序路径分析的基础上，首先定义了三种蜕变测试准则，
10、从不同角度规定了蜕变测试用例集的充分性。然后基于这些准则给出了有效蜕变测试算法。最后将这些算法应用于计算三角形面积的程序中，结果表明APCEMST算法能够产生具有较强检错能力的测试用例集。文章第2节介绍了一些基本概念和原理；第3节给出了一组蜕变测试准则、蜕变关系选取策略和基于它们的有效蜕变测试算法；第4节通过实验证实了本文算法的性能；第5节对全文进行总结。2 基本概念定义1 假设程序P用来计算函数f，x1, x2, , xn (n1)是f的n个自变量，且f(x1), f(x2), , f(xn) 是它们所对应的函数结果。若x1, x2, , xn之间满足关系r时，f(x1), f(x2), ,
11、 f(xn)满足关系rf，即：r (x1, x2, , xn) rf ( f (x1), f (x2), , f (xn) )则称 ( r, rf ) 是程序P的蜕变关系2。 显然，如果P是正确的，那么它一定满足下面的推导式：r (I1, I2, , In) rf ( P(I1), P(I2), , P(In) )其中I1, I2, , In是程序P的对应于x1, x2, , xn 的输入，P(I1), P(I2), , P(In) 是相应的输出。因此，可以通过检测上式是否成立来判定程序P的正确性。蜕变测试即是一种基于蜕变关系的测试。定义2 假设D为程序P的输入域，DD，在D上可以对P进行蜕变
12、测试，则称D为程序P的蜕变域，记作DMT (P)，称D - D为P的非蜕变域，记作DUMT (P)。定义3 假设 (r, rf) 是程序P的蜕变关系，若r是一个二元等式关系( r(x1, x2) )，则称 (r, rf) 是程序P的二元蜕变关系，记作 (rb, rfb)。若对于I1DMT (P)，I2DMT (P)，使得rb (I1, I2)成立，则称是二元蜕变关系(rb, rfb)的定义域，记作DR (rb, rbf)，称I1为原始输入，I2为I1基于 (rb, rbf) 的衍生输入，记作I2 = FU (I1, (rb, rbf)。例如，在测试计算函数f(x)的程序Psin时，依照定义2，
13、Psin的蜕变域DMT (Psin) = (0, +)。MRsin：(x1+x2 =, f(x1)2 + f(x2)2 = 1) 是为Psin构造的一条二元蜕变关系，依照定义3，MRsin的定义域DR (MRsin) = (0,)，任选一值 DR (MRsin)作为原始输入，它基于MRsin的衍生输入FU (, MRsin) =。根据输入关系rb(x1, x2)形式的差别，我们将二元蜕变关系 (rb, rbf) 分为三类。1-1型关系：若x1是x2的函数并且x2也是x1的函数，则 (rb, rbf) 是1-1型蜕变关系。例如rb(x1, x2) 为x1 + = 1的关系；1-n型关系：若x1是
14、x2的函数或者x2是x1的函数，但是反之不成立，则 (rb, rbf) 是1-n型蜕变关系。例如rb(x1, x2)为+ x2 = 1 (x1-1, 1) 的关系，这里x2是x1的函数(x2 = 1-)，但x1不是x2的函数；n-n型关系：若x1不是x2的函数并且x2也不是x1的函数，则 (rb, rbf) 是n-n型的蜕变关系，例如rb(x1, x2) 为+= 1 (x1-1, 1) 的关系。由于蜕变测试时大都使用比较容易构造的二输入蜕变关系，并且1-1或1-n型关系的输入关系rb能够表示为函数式的形式，可以实现衍生输入的自动生成，另外在很多情况下，n-n型关系也可以通过限定输入范围、替换参
15、数等方法转换为1-1或1-n型关系，所以本文只讨论基于1-1和1-n型蜕变关系的测试。下文中，若rb(x1, x2) 表示成函数的形式为x2 = frb (x1), 则我们规定原始输入I1与函数的自变量x1相对应, 而衍生输入I2与x2相对应, 以此来保证每个原始输入只能推导出一个衍生输入，即FU (I1, (rb, rbf)是唯一的。定义4 假设MR是程序P的1-1或1-n型蜕变关系，若对于I1DR (MR)，无论对P置入何种变异26，I1、FU(I1, MR)及它们所对应的输出均满足MR，则称为MR的测试盲区，记作Dbl (MR)，称DR(MR)-Dbl(MR)为MR的适用区域，记作Dapp(MR)。例如，程序double Square (double a, double b) 实现了计算矩形面积S(x, y) 的功能：我们为其构造一条二元蜕变关系MRs：( (x, y) = (y, x), S (x, y) = S (x, y) )即交换两条边的值，矩形面积应当不变，其中DR (MRs) = (a, b) | (a 0)(b 0)。当在(a, b) | a = b 0中选取原始输入I时，即使对程序植入将”*”改为”-”的变异，I、FU(I, MRs)及它们的输出也同样满足MRs，由定义4可知，
