蜕变测试

时间：2016-12-19 07:22:16 来源：免费论文网

篇一：蜕变测试方法在面向服务软件中的应用

蜕变测试方法在面向服务软件中的应用

摘要

在面向服务软件测试过程中，由于在服务发现之前不可知的交互对象和同一个服务可能会有不同的实现，往往出现程序执行结果不能提前预知的Oracle问题。为了有效地解决面向服务软件测试中的Oracle问题，基于面向服务架构（SOA）的特点，提出将蜕变测试方法用于面向服务软件的单元测试和集成测试过程中，依据面向服务软件每个服务的自身特质构造蜕变关系，设计蜕变测试类执行测试用例并验证蜕变关系是否保持，如果蜕变关系被违反了，则发现和报告缺陷，从而有效地支持面向服务软件测试。

关键词：软件测试；面向服务架构；蜕变测试；蜕变关系

Abstract

During the process of service-oriented software testing, Oracle problem that the program result is unpredictable comes into existence frequently because of issues like the unknown communication partners before the service discovery and the potential existence of non-identical implementations of the same service. In this paper, based on the benefits of the SOA environments, Metamorphic Testing ( MT) approach was applied in the phase of unit testing and integration testing of service-oriented software. Metamorphic Relation ( MR) can be built according to the service properties. A metamorphic testing class can invoke relevant services to execute test cases and use their metamorphic relations to detect failures． Any violation of any relevant metamorphic relation indicates a failure．

Key words: software testing; Service-Oriented Architecture ( SOA) ; Metamorphic Testing (MT) ; Metamorphic Relation (MR)

1 引言

面向服务架构（Service-Oriented Architecture, SOA）是以服务为基础的松耦合的分布式应用系统的结构，基于服务的形式功能描述为软件系统的灵活性、可扩展性和开放性提供了基础，有效地支持了异构资源共享、动态升级和演化。随着SOA的应用越来越广泛，确保面向服务软件的质量尤为重要，而软件测试是保证面向服务软件质量的主要手段。

SOA的基本元素就是服务，服务就是一个软件模块，这个软件模块能够描述自己，能够被顶级服务发现和定位，能够使用良好的接口和顶级服务进行交互。由于服务是动态发现的，因此没有必要硬编码，服务松散集成在一起，这种结构会极大地增强构建复杂SOA的能力。然而，因为服务松散集成，向一个服务提供另一个服务很难提前确定；而且服务通常在异构环境下开发，并且是由不同组织开发的，知道服务实现的所有细节是不现实的，因此，在面向服务软件测试过程中更多地使用墨盒测试方法。

然而，在对面向服务软件进行黑盒测试时，存在两个问题：首先，一种服务的实现的行为表现不一样，一种特定实现的测试结果并不能被看做其他实现的预期结果；其次，一种服务的期望结果很难预测，或者为了预知结果使用人工方法需要花费较大的代价。这两个问题都带来了测试这类应用程序的挑战，这种程序的执行结果不能预知的现象在测试理论中称为“Oracle 问题”。本文提出将蜕变测试方法用于面向服务软件的单元测试和集成测试过程中，依据面向服务软件每个服务的自身性质构造蜕变关系，检测几个输出之间的关系来判断服务的功能是否正确，而不仅仅依赖判定单个输出结果是否正确，从而允许在SOA框架下测试结果的交叉验证，能够有效减少SOA应用测试中的Oracle问题的发生。蜕变测试技术通过检查程序的多个执行结果之间的关系来测试程序，经过近十几年的研究，蜕变测试技术已经在测试过程的优化、与其他验证或测试方法的结合等方面取得了巨大的进展，并被广泛地应用于各个领域中。

2. 蜕变测试方法

软件测试是保证软件质量和可靠性的一种重要手段，用于发现和纠正软件中存在的缺陷和错误，但该技术中存在着两大局限，即测试用例集可靠性问题和Oracle

问题。测试用例可靠性问题是指对于某个程序很难构造一个可靠的测试用例集，使得程序的正确性可以由基中所有测试用例的正确执行来保证。而Oracle问题是指在某些情况下，测试人员无法确定程序执行结果与期望结果是否相同，或者很难构造预期输出结果。

2.1 基本概念和原理

为了解决Oracle问题，澳大利亚斯威本科大学的Chen等人提出了蜕变测试的概念。该方法认为测试过程中没有发现错误的测试用例（成功的用例）也同样蕴涵着有用的信息，它们可又用来构造新的用例以对程序进行更加深入的检测，蜕变测试技术通过检查这些成功用例及由它们构造的新用例所对应的程序执行结果之间的关系来测试程序，无需构造预期输出。而程序执行结果之间所应当满足的关系属于程序的功能属性，可又根据程序的规约推导出来。假如函数P用来计算函数f，那么f显然是P必需遵守的规约，判定程序正确性的关系可以从f中推导出来。

1）蜕变关系

蜕变测试就是依据被测试软件的领域知识和软件的实现方法建立蜕变关系（Metamorphic Relation, MR）,利用蜕变关系来生成新的测试用例，通过难蜕变关系是否被保持来决定测试是否通过。蜕变关系是指函数的一系列输入及相应输出的关系。假设函数f是待测的函数，{I1,I2,?,In}n>1表示程序f的输入数据，基于输入数据{I1,I2,?,In}n>1给定一个关系r，{I1,I2,?,In}n>1相应的输出 {f (I1), f (I2),?, f (In)}必须满足属性r f，即：r{I1,I2,?,In}n>1?r f{f (I1), f (I2),?, f (In)}。蜕变关系MR可表示如下：

MRf=

I1,I2,…,In,?? I1 ,?? I2 ,…,?? In ?? I1,I2,…,In

?? ??(I1,I2,…,In,?? I1 ,?? I2 ,…,?? In )}

假设程序P用来计算函数f, x1,x2,?,xn(n>1)是f的n组变元，且f(x1),f(x2),?,f(xn)是它们所对应的函数结果。若x1,x2,?,xn之间满足关系r时，f(x1),f(x2),?,f(xn)满足关系rf,,即：r(x1,x2,?,xn)rf(f(x1),f(x2),?,f(xn)),称为P的蜕变关系。显然，如果

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的正确性。以正弦（sin）函数为例，根据该函数的重要性质：对于输入变量x1和x2，如果满足x1+ x2=π，那么sin(x1) = sin(x2),这就是蜕变测试时找到的蜕变关系，若x1是源测试用例，则依据蜕变关系就可又得到新的后续测试用例x2, x2=π- x1。通常蜕变测试依据蜕变关系生成更多的后续测试用例，测试时就会有多次执行目标程序，使得程序可又进一步被验证。蜕变测试方法可以用于数值计算、无向图遍历、二叉树查询和中间件软件测试等很多领域。

2）原始/衍生测试用例

使用蜕变关系MRf测试程序P时，起初给定（利用其他测试用例生成方法生成的）测试用例是原始测试用例；由原始测试用例根据关系r计算出的用例是该原始用例基于蜕变关系MRf的衍生测试用例。

蜕变测试技术具有三个显著的特点：为了检验程序的执行结果，测试时需要构造蜕变关系；为了从多个方面判定程序功能的正确性，通常需要为待测程序构造多条蜕变关系；为了获得原始测试用例，蜕变测试需要与其他测试用例生成策略结合使用。

2.2 蜕变测试过程

一般而言，蜕变测试过程可以划分为以下几个阶段：

1）使用其他测试用例生成策略为待测程序的生成原始测试用例；

2）若这些原始用例均通过测试，则为待测程序构造一组蜕变关系；

3）基于上述关系计算衍生测试用例；

4）检查原始和衍生用例的输出是否满足相应的蜕变关系，得出测试结果。该过程如图1所示。

图1 锐变测试示意图

下面的例子详细地说明了蜕变测试的过程。假设在测试计算sin函数的程序P时，t=57.3是根据诸如分支覆盖之类的测试准则生成的测试用例，且t对应的输出结果为P(t)=0.8415，由于sin(57.3o)的值难又确定，所以P(t)的正确性不易判定。用蜕变测试的方法检验程序P的正确性。显然，根据sin(x) = sin(180o-x)的性质可又构造出一条蜕变关系MR，且t基于MR的衍生用例为t’ = 180o-57.3o = 122.7o，以t’为输入执行P所得的输出为P(t’)=0.8402,通过对比P(t)和P(t’)可又容易地发现它们之间不满足MR，可见程序P中存在错误。 o

3 蜕变测试方法在面向服务软件测试中的运用

面向服务的架构是一种针对诸如Web service之类的分布式广泛应用程序的模型，SOA的基本元素是一种被称为服务的软件模块，服务可以描述自己，可以审美观点其他服务发现和定位，并且可又通过接口与其他服务通讯。SOA应用软件已经得到了广泛地应用，但是在测试它们时，往往存在着诸如直到发现服务才知道消息对象；组件中存在不精确的黑盒信息；同一服务的潜在实现不同等问题，这些问题使得传统的测试方法无法很好地得又应用，而利用蜕变测试方法可以避开这些棘手的麻烦，达到良好的测试效果。Chen首先将待测服务和蜕变关系的实现都封装在蜕变服务中。随后的测试分为单元测试和集成测试两步进行，在

在面向服务软件的测试过程中，单元测试和集成测试非常重要。在单元测试阶段，软件系统中每一个单个服务都经过测试，要为待测服务设计蜕变关系，由原始测试用例产生衍生测试用例，并通过执行结果来检测服务的正确性; 在集成测试阶段，对已测试过的服务之间交互进行测试，单元测试时的测试用例被用来产生衍生测试用例，蜕变服务会激发相关的服务以执行测试用例，并使用封装在里面的蜕变关系来发现错误。在上述基础上，他还提出了一种在线测试SOA

软件的方

篇二：心智系统蜕变测评

意识流明测评表

《心智系统蜕变-意识流明测评表》

意识流明测评表

篇三：基于程序路径分析的有效蜕变测试

基于程序路径分析的有效蜕变测试

董国伟聂长海徐宝文

(东南大学计算机科学与工程学院南京 210096)

(江苏省软件质量研究所南京 210096)

摘要蜕变测试对于预期输出难以构造的程序是实用和高效的. 作者在系统研究已有蜕变测试方法和路径分析技术的基础上，首先针对使用二元蜕变关系的测试提出了一组蜕变测试准则，以在多个不同的层次上定义蜕变测试用例集的充分性；然后给出了三种能够生成相应测试用例集的算法；最后通过变异分析的方法证实这些算法的有效性. 实验结果表明蜕变关系和测试准则的选取直接影响到测试的效果，另外，使用蜕变关系全路径覆盖可满足性算法(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 Institute 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 metamorphic 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’ performances 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 traditional method.

Keywords software testing; metamorphic testing; oracle problem; metamorphic relation; path-coverage criterion 1 引言

软件测试是一种重要的、不可缺少的软件质量保证技术，用于发现和纠正软件中存在的缺陷和错误。但在很多情况下，测试时存在着oracle问题[1]，即测试人员很难构造程序的预期输出，确定执行结果与期望结果是否相同。为了能够有效地解决此类问题， Chen等人提出了蜕变测试 (metamorphic testing) 的概念[2]，该方法通过检查程序的多个执行结果之间的关系来测试程序，不需要构造预期输出。

蜕变测试技术具有三个突出的特点：为了检查程序的执行结果，测试时需要构造蜕变关系[2]；为了从多个方面判定程序功能的正确性，测试时通常需要构造多条蜕变关系；为了获得原始测试用例[2]，蜕变测试需要与其他测试用例生成方法相结合。

Chen和吴鹏分析了使用特殊值和随机值作为原始用例时的差异[3,4]，吴鹏还提出了迭代蜕变测试算法 (IMT) 以循环地产生原始用例[5]，但复杂度较高，我们基于路径分析技术对IMT算法进行了改进[6]。Chen和Mayer还通过实验对比总结出了蜕变关系选取的一般性策略[7, 8]；虽然对于蜕变测试技术自身的改进可以提高测试效率，但它经常与其他验证或测试技术结合使用。Chen将蜕变测试与全局符号执行结合提出了一种准验证方法[9]。将蜕变技术与基于缺陷的测试[10]、STECC[11]、基于模型的测试[12]等方法结合，也可以获* 本课题得到国家杰出青年科学基金项目(60425206), 国家自然科学基金重大研究计划(90818027)与重点项目(60633010), 国家高技术研究发展计划(863计划)目标导向类项目(2009AA01Z147), 国家自然科学基金项目(60773104)的资助. 董国伟,男,1983年生,博士研究生,研究方向为软件分析与测试, Email: [email protected], 电话:13675106871; 聂长海,男,1971年生,博士,副教授,研究方向为软件工程和软件测试技术、模糊信息处理、神经网络等, Email: [email protected], 电话:13851784496; 徐宝文,男,1961年生,教授,博士生导师,研究方向为程序设计语言,软件工程,并行与网络软件等, Email: [email protected],电话: 13327800488.

得高效的测试技术；蜕变测试技术的实用性使得它已经被广泛地应用于数值型程序[13]、图论计算程序[14]、图象处理软件[14-16]、并行编译器[14]、交互式软件[14]、铸造模拟软件[17]、普适计算软件[18,19]、SOA软件[20,21]和面向对象软件[22-25]等的测试中。上述研究证实了蜕变测试在解决oracle问题时的有效性，但是这些方法大都只考虑程序的功能，没有充分利用程序结构的信息。

本文针对二输入蜕变关系，在程序路径分析的基础上，首先定义了三种蜕变测试准则，从不同角度规定了蜕变测试用例集的充分性。然后基于这些准则给出了有效蜕变测试算法。最后将这些算法应用于计算三角形面积的程序中，结果表明APCEMST算法能够产生具有较强检错能力的测试用例集。文章第2节介绍了一些基本概念和原理；第3节给出了一组蜕变测试准则、蜕变关系选取策略和基于它们的有效蜕变测试算法；第4节通过实验证实了本文算法的性能；第5节对全文进行总结。

2 基本概念

定义1 假设程序P用来计算函数f，x1, x2, …, xn (n>1)是f的n个自变量，且f(x1), f(x2), …, f(xn) 是它们所对应的函数结果。若x1, x2, …, xn之间满足关系r时，f(x1), f(x2), …, 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的输入域，D’?D，在D’上可以对P进行蜕变测试，则称D’为程序P的蜕变域，记作DMT (P)，称D - D’为P的非蜕变域，记作DUMT (P)。

定义3 假设 (r, rf) 是程序P的蜕变关系，若r是一个二元等式关系( r(x1, x2) )，则称 (r, rf) 是程序P的二元蜕变关系，记作 (rb, rfb)。若对于?I1?ξ?DMT (P)，?I2?DMT (P)，使得rb (I1, I2)成立，则称ξ是二元蜕变关系(rb, rfb)的定义域，记作DR ((rb, rbf))，称I1为原始输入，I2为I1基于 (rb, rbf) 的衍生输入，记作I2 = FU (I1, (rb, rbf))。

例如，在测试计算函数f(x)

x?0?0f?x??? ?sin(x)x?0

的程序Psin时，依照定义2，Psin的蜕变域DMT (Psin) = (0, +?)。

MRsin：(x1+x2 =?2, [f(x1)]2 + [f(x2)]2 = 1)

是为Psin构造的一条二元蜕变关系，依照定义3，MRsin的定义域DR (MRsin) = (0,?2)，任选一值?? DR (MRsin)作为原始输入，它基于MRsin的衍生输入FU (?, MRsin) =?6。

根据输入关系rb(x1, x2)形式的差别，我们将二元蜕变关系 (rb, rbf) 分为三类。1-1型关系：若x1是x2

3 的函数并且x2也是x1的函数，则 (rb, rbf) 是1-1型蜕变关系。例如rb(x1, x2) 为x1 +x2= 1的关系；1-n型

关系：若x1是x2的函数或者x2是x1的函数，但是反之不成立，则 (rb, rbf) 是1-n型蜕变关系。例如rb(x1, x2)为x12+ x2 = 1 (x1?[-1, 1]) 的关系，这里x2是x1的函数(x2 = 1-x12)，但x1不是x2的函数；n-n型关系：若x1

2不是x2的函数并且x2也不是x1的函数，则 (rb, rbf) 是n-n型的蜕变关系，例如rb(x1, x2) 为x12+x2= 1 (x1?[-1,

1]) 的关系。由于蜕变测试时大都使用比较容易构造的二输入蜕变关系，并且1-1或1-n型关系的输入关系rb能够表示为函数式的形式，可以实现衍生输入的自动生成，另外在很多情况下，n-n型关系也可以通过限定输入范围、替换参数等方法转换为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型蜕变关系，若对于?I1?δ?DR (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) 的功能：

(x?0)?(y?0)?x?yS?x,y??? Errorotherwise?

我们为其构造一条二元蜕变关系

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可知，Dbl (MRs) = {(a, b) | a = b > 0}，Dapp(MRs) = {(a, b) | (a > 0)?(b > 0)?(a?b)}。

使用某条蜕变关系测试程序时，应当尽量避免在其测试盲区中选取原始输入。由上面的例子也可以发现，测试盲区往往是由于蜕变关系自身结构上的特点而引入的，因此可以比较容易地确定此类区域。使用m条二元蜕变关系MR1, MR2, …, MRm测试程序P时，它们必须满足DMT(P) =?i?1Dapp(MRi)，否则称蜕变关系不充分，需要补充新的关系。

定义5 假设MR是程序P的1-1型蜕变关系，若对于?I?Dapp(MR)，FU (FU (I, MR), MR) = I成立，则称MR是程序P的对称蜕变关系。明显地，MRsin是程序Psin的对称蜕变关系。

定义6 假设MR是程序P的1-1或1-n型蜕变关系，以原始输入I、衍生输入FU (I, MR)运行P时执行m

?Path2。到的路径分别为Path1、Path2，则称Path1和Path2是基于MR的一个路径对，记作Path1???

?Path2与Path2????Path1是等价的。 Path1???

定义7 假设MR是程序P的1-1或1-n型蜕变关系，D?Dapp(MR)，则称区域{I2 | (I1∈D)?(I2 = FU(I1, MR))}为D基于MR的衍生域，记作DFU (D, MR)。

由定义7可知，(0,?4)基于MRsin的衍生域DFU ( (0,?4), MRsin ) = (?4,?2)。 MRMRMR

3 面向路径覆盖的有效蜕变测试

现有的蜕变测试技术大多只通过将原始输入和蜕变关系简单地进行组合来计算衍生输入，然后测试程序。这种方法虽然简单易行，但是由于缺少准则的规范，所以不可避免地会带来两个方面的问题，一方面可能会产生大量测试功能相似的测试用例 (比如大量测试用例执行同一条路径或分支)，造成测试成本的浪费；另一方面，由于待测程序的某些结构性元素 (分支、特定语句) 没有被覆盖到，从而导致测试的不充分性。因此，如果在进行蜕变测试的同时考虑待测程序的白盒信息，并使用这些信息来指导用例的产生，那么上面的两个问题就会得到解决，测试效率也会大幅度提高。本节首先提出了一组蜕变测试准则和蜕变关系选取策略，然后在此基础上给出了有效蜕变测试算法。

下文中，根据待测程序P构造的二元蜕变关系记作MRi (i?[1, m])；每条蜕变测试用例记作一个由蜕变关系及满足它的原始输入和衍生输入所构成的三元组(MRi, Ii1, Ii2)，测试用例所组成的用例集记作TC；每条可执行路径记作Pathj (j?[1, n])，执行Pathj的输入所组成的集合，即Pathj对应的输入子域记作DS(Pathj)；以输入I运行P时的执行路径记作ExcPath(I)。

3.1 蜕变测试的路径覆盖准则

路径覆盖准则要求设计充足的测试用例以保证测试时每条可能执行到的路径都至少被执行一次[27]，它是一种比较严格的测试准则，比其他几种覆盖准则[27]具有更广的覆盖面。我们在传统路径覆盖准则的基础上，考虑到蜕变测试技术自身的特点，提出了三种覆盖准则。

蜕变域全路径覆盖APC (All-Path Coverage)：使用TC测试P时，对于?Pathj, 若DMT(P)?DS(Pathj) ??, ?(MRi, Ii1, Ii2)?TC，使得(ExcPath(Ii1) = Pathj)?(ExcPath(Ii2) = Pathj)成立，则称TC满足APC。

图1是某程序的控制流图，假设该程序含有5条可执行路径，但只有3条使用蜕变方法测试，分别记为Path1、Path2、Path3，MR1、MR2是根据程序构造的两条蜕变关系，它们的定义域与程序的蜕变域相同，实线段和虚线段分别指向它们所测试的路径。我们为该程序设计了3个蜕变测试用例：T1 = (MR1, i1, i2)、T2 = (MR2, i3, i4)和T3 = (MR1, i5, i6)，以i1-i6运行程序时，执行路径的路径标号依次为1, 2, 2, 3, 1, 3，由APC的定义可知，{T1, T2}和{T1, T3}都满足APC准则，因为使用它们分别测试程序时，3条路径都至少执行了一次。

APC准则保证了每条需要使用蜕变测试方法进行测试的可执行路径至少执行一次。一般地，满足APC的测试用例集含有较少数量的蜕变测试用例，但这些用例不一定涉及到所有的蜕变关系，如上例的{T1, T3}。

蜕变关系全路径覆盖APCEM (All-Path Coverage for Every

Metamorphic Relation)：使用TC测试P时，对于?MRi和Pathj，

若Dapp(MRi)?DS(Pathj)??, ?(MRi, Ii1, Ii2)?TC，使得

(ExcPath(Ii1) = Pathj)?(ExcPath(Ii2) = Pathj)成立，则称TC满足

APCEM。

针对图1中的程序，我们设计了另外4个测试用例，T4 = (MR1,

i7, i8)、T5 = (MR1, i9, i10)、T6 = (MR2, i11, i12)、T7 = (MR2, i13, i14)，以

i7 - i14运行程序时，执行路径的路径标号依次为1, 2, 3, 1, 2, 1, 2,

3，根据上面的定义可知，{T4, T5, T6, T7}满足APCEM准则，因为

使用MR1、MR2分别测试程序时，3条路径都至少执行了一次。

APCEM准则考虑到了每条蜕变关系的测试功能的差别，它

保证测试时所有的蜕变关系都被使用到。但通常情况下，满足

APCEM的测试用例集的用例数量远远大于满足APC的用例集。

12图1 蜕变测试覆盖准则示意图蜕变关系全路径对覆盖APPCEM (All-Path-Pair Coverage for Every Metamorphic Relation)：使用TC测i?Pathj2，若(Dapp(MRi)?DS(Pathj1)??)?(Dapp(MRi)?DS(Pathj2) 试P时，对于?MRi和Pathj1???

??), ?(MRi, Ii1, Ii2)?TC, 使得((ExcPath(Ii1) = Pathj1)?(ExcPath(Ii2) = Pathj2) )?( (ExcPath(Ii1) = Pathj2)?(ExcPath(Ii2) = Pathj1) )成立，其中j1, j2?[1, n]，则称TC满足APPCEM。

图1中，实折线和虚折线分别表示基于MR1和MR2的所有不同的路径对，通过分析可知，{T4, T5, T6, T7}也满足APPCEM准则，因为使用它测试程序时，基于MR1、MR2的所有路径对都被覆盖到了。

一般而言，蜕变测试的结果可以分为三类：(1) 待测程序中没有错误，则原始输入和衍生输入的执行结果均无误，它们满足相应的蜕变关系，测试通过。(2) 待测程序中存在着错误，且原始输入和衍生输入的执行结果不满足相应的蜕变关系，测试未通过。(3) 待测程序中存在着错误，但原始输入和衍生输入的执行结果满足相应的蜕变关系，错误没有被发现。

APPCEM正是针对情况(3)提出的，它考虑到了使用

不同蜕变关系测试相同路径对时的差别，要求测试

时每条蜕变关系能够涉及的所有路径对都要被覆盖

到，但是APPCEM是一种非常严格的测试准则，满

足APPCEM的测试用例集往往较难构造。

以上我们系统地介绍了三种蜕变测试准则，它

们从不同的角度规定了蜕变测试用例集的充分性。

不难看出，三者并不是孤立的，对于同一个待测程

序，满足三种准则的蜕变测试用例集所组成的不同

集合存在着图2所示的包含关系。

3.2 蜕变测试路径覆盖准则的可满足性算法

本节的算法只涉及蜕变域上的测试，它们能够产生满足三种测试准则的用例集。由于程序的每条路径对应一个输入子域，所以可以将路径的覆盖情况反映为输入子域的覆盖情况。为了获取路径和输入子域的信息，我们使用符号执行技术[28,29]计算一条新执行到的路径所对应的输入子域。

3.2.1 蜕变关系的选取策略

通常情况下，不同蜕变关系的检错能力存在着差异，因此测试时蜕变关系使用的先后次序会影响到测试的效率和结果，即使在相同的覆盖准则下，这种影响依然存在。测试时总是希望优先使用检测能力优良的关系，根据Chen的研究，使得两次执行尽可能不同的蜕变关系比较有效

了细化，提出了一组测试时选取蜕变关系的策略：

策略1：优先选取输入关系rb的表达式较复杂的蜕变关系。

2输入关系x12+x2= 4显然比x2 = 2?x1复杂。优先选取rb表达式较复杂的蜕变关系，可以尽量避免由于错误！未找到引用源。图2 满足三种测试准则的用例集的包含关系。本节对该结论进行

程序结构的特点而隐藏错误的情况。

策略2：对于输入为多元组的程序，优先选取使得两输入中对应元不同的数量较多的蜕变关系。

假设某程序的输入是一个三元组，MR1和MR2是该程序的两条蜕变关系，对于某原始输入I = (x, y, z)，FU(I, MR1)、FU(I, MR2)分别为(x’, y’, z)和(x’’, y, z) (x’?x, x’’?x, y’?y)，则我们优先选取MR1，因为它使得I和FU(I, MR1)中有2组对应元 ( x和x’, y和y’ ) 不同，多于MR2。优先选取此类关系，可以尽量避免由于原始用例和衍生用例均只使用相同元执行程序而隐藏错误的情况。

策略3：优先选取适用区域较大的蜕变关系。

优先选取适用区域较大的关系，可以尽量避免因测试盲区未被测试而隐藏错误的情况。

在选取蜕变关系时，应该综合考虑上述三条策略，当它们之间发生冲突时，按照策略1、2、3优先级依次降低的顺序选取。

3.2.2 蜕变域全路径覆盖可满足性算法APCST

APCST算法每次从未测试域中选取一个值I作为原始输入，然后随机地选取一条蜕变关系MR，使用测试用例(MR, I, FU(I, MR))测试程序，重复上述操作直到发现错误或未测试域为空。详细见算法1。

APCST算法的时间复杂性为O (m?n + n?p)，其中m表示蜕变关系的数量，n表示蜕变域上路径的数量，p表示程序路径中结点个数的最大值 (符号执行时需要检查执行到的每条语句)。算法的时间复杂性主要取决于n和p。假设APCST算法生成的测试用例集为TC1，则n/2?|TC1|?n，由于测试时蜕变关系是随机选取的，所以对于某个特定的待测程序，|TC1|的差别可能很大。

3.2.3 蜕变关系全路径覆盖可满足性算法APCEMST

使用APCST算法测试程序时，并不能保证所有的蜕变关系都被涉及到。APCEMST算法针对每条蜕变关系都进行一次类似于APCST算法所描述的测试过程，实现了对蜕变关系和路径两者组合的覆盖。APCEMST算法依照3.2.1节中的策略选取蜕变关系，循环地构造基于每条关系的测试用例，对于每一次循环，测试过程与APCST算法类似，只是无需随机地选取蜕变关系。详细见算法2。

APCEMST算法的时间复杂性为O(m?n?p)，各符号的含义与3.2.2节中相同。由于测试时总共进行n次符号执行，且很多情况下，路径之间拥有公共子路径，所以算法的时间复杂性一般比m?n?p小得多。假设APCEMST算法生成的测试用例集为TC2，则|TC2|?m?n。

《蜕变测试》
由：免费论文网互联网用户整理提供,链接地址：
http://m.csmayi.cn/show/125141.html
转载请保留,谢谢!