面向条件筛选搜索系统的蜕变测试方法

韩育珍，陈军华，高建华

(上海师范大学 计算机科学与技术系，上海 200234)

0 引 言

条件筛选搜索系统包含大量数据信息，用户可以定制条件，以筛选并显示满足条件的数据信息，它需要承受大量用户的服务请求，必须适应长期和高频的访问操作[1]，带来保障服务可靠性的挑战。传统软件测试技术可以有效检测并纠正软件中存在的故障和缺陷以应对这一挑战，但它存在着两大问题，即测试用例集的可靠性问题[2]和 Oracle 问题。其中，Oracle问题表示待测软件的执行输出结果复杂或者无法预知的情况[3]。蜕变测试(metamorphic testing)是一种有效缓解复杂系统Oracle问题的软件测试方法[3,4]，其测试方法是检查执行程序的多次输入输出是否满足预期的蜕变关系(metamorphic relationship)。

学者们已使用蜕变测试对Oracle问题的缓解进行了初步探索，发现构建有效的蜕变关系可以帮助缓解Oracle问题[5,6]。Zhou等[6]提出通过检查程序多次输出之间的关系代替检查程序的单次输出执行测试。Segura等[3]提出了定义了等价性、等效性、子集、非交集、并集、差集6种蜕变关系输出模式(metamorphic relationship output pattern)。Zhou等[7,8]提出了基于对称(symmetry)的蜕变关系输出模式。Sun等[9]提出了蜕变关系输入模式的概念。Segura等[1]提出了输入等价、洗牌、合并条件、析取条件、不相交的分区、完整分区和分区差异7种蜕变关系模式。

研究发现，条件筛选搜索系统降低了信息的认知负载，增加了多样化的搜索模式。通过分析现有的蜕变关系模式在条件筛选搜索系统执行测试时检测到的软件设计故障及检测效率，提出了两种蜕变关系模式，有效提高了软件设计的故障检测效率。

本文的主要贡献如下：

(1)在“合并条件”和“析取条件”两种蜕变关系模式的基础上提出了检测效率更高的“IO组对称相等”蜕变关系模式；

(2)根据条件筛选搜索系统中的多项选择条件，提出了“交集等价”模式的概念；

(3)通过实验验证提出的两种蜕变关系模式具有可操作性和适用性。

1 蜕变测试

当传统软件测试在遇到复杂系统Oracle问题而无法预估程序输出结果或者程序输出结果复杂时，测试人员难以判断程序的输出结果与预期结果是否一致，于是通过检查程序多次输入输出之间的关系是否满足预期构建的蜕变关系，从而验证程序软件设计的正确性，这种测试方法被称为蜕变测试[10,11]。蜕变关系是源测试用例生成后续测试用例的前提，以便执行源和后续测试用例并检查其输出。因此，蜕变测试也被认为是一种有效的测试用例生成技术[2]。

自Chen等[12]提出检查程序多次输出之间的关系来执行蜕变测试以来，关于蜕变测试的应用研究不仅仅体现在搜索引擎方面[1,3,9]，而且也应用在生物信息学[13]、医疗系统[14]和机器学习[15]等领域。

蜕变测试过程如图1所示。

图1 蜕变测试

其中，SUT表示有a+1个输入参数，b+1个输出结果的待测软件，I0表示使用传统测试用例生成技术生成的源测试用例，Ii,i=[1,n] 是源测试用例根据蜕变关系修改输入参数作为后续测试用例，Ij1,Ij2,…,Ija,j=[1,n] 表示源测试用例和后续测试用例的a+1个待输入参数，O(I0) 和O(Ii) 为源测试用例和后续测试用例对应的n+1次输出，Oj1,Oj2,…,Ojb表示O(Ij) 的b+1个输出结果。蜕变测试是通过比较O(I0) 和O(Ii) 多个输出结果之间的关系是否满足构建的蜕变关系来验证SUT的正确性。

一般地，函数f的蜕变关系表示为一系列函数输入之间的关系I0,I1,…,In(n≥1) 及其对应的输出值f(I0),f(I1),…,f(In) 之间的关系[16]，即蜕变关系

R={(I0,I1,…,In),(f(I0),f(I1),…,f(In))|n≥1}

其中，I0为源输入，f(I0) 为源输出，I1,I2,…,In为后续输入，f(I1),f(I2),…,f(In) 成为后续输出。

2 蜕变关系模式

蜕变测试中蜕变关系的构建和识别依赖于测试人员对程序的熟悉和了解，常规方法是检查程序规范或者用户文档，并考虑如何修改程序输入，进而在输出中产生预期的变化[2]。但这个过程是一项手动操作过程，必须根据每个被测程序的预期功能从头开始检测和识别。为了减轻构建和识别蜕变关系的负担，S. Segura等[1,3]提出了7种适用于传统搜索引擎的蜕变关系模式：

等效性(shuffling)：表示源输入和后续输入相等，源输出和后续输出相同但是顺序相等或不相等的关系。

等价性(input equivalence)：指的是源输入和后续输入等价，源输出和后续输出相同且顺序也相等的关系。该关系模式是上一个关系模式的子集。

合并条件(conjunctive conditions)：表示在源输入的基础上，搜索条件不断增加作为多次后续输入，其对应的输出都是前一次输出的子集。

析取条件(disjunctive conditions)：表示在源输入的基础上，搜索条件不断减少作为多次后续输入，其相应的输出关系可以概括为前一次输出是后一次输出的子集。该关系模式是在上一个关系模式的基础上对称定义的。

不相交的分区(disjoint partitions)：表示源输入和后续输入无交集，且对应的源输出和后续输出交集为空集的关系。

完整分区(complete partitions)：表示源输入是所有后续输入的并集，源输出与所有后续输出并集相等的关系。该关系模式与上一个关系模式的定义分别源自于关系代数中的交集与并集。

分区差异(partiton difference)：表示后续输出之间两两不相交，但是都属于源输出子集的关系，在创建和更新的任务列表中比较常见。

通过对条件筛选搜索系统的了解和熟悉，分析改进了“合并条件”和“析取条件”模式，提出了“IO组对称相等”模式，并且根据条件筛选搜索系统的多项选择搜索模式在“等价性”和“完整分区”模式的基础上提出了“交集等价”模式。接下来，引入改进提出的两种蜕变关系模式，并使用数学关系表示，在下面的关系式中I0为源输入，O为源输出。Ii为后续输入，Oi为后续输出。

2.1 IO组对称相等

IO组对称相等模式是在“合并条件”和“析取条件”模式的基础上改进的,将程序中的多次输入作为一个源输入组，将源输入组中的多次输入对称得到一个后续输入组，源输出组和后续输出组对称等价。但源输入组和源输出组中的多次输入输出应该满足“合并条件”模式指定的关系，后续输入组和后续输出组中的多次输入输出应满足“析取条件”模式指定的关系。如式(1)所示，数学关系表示为

I0=I01、I02、…、I0n,I1=I11、I12、…、I1n，且I11=I0n，I12=I0(n-1)，…,I1n=I01⟹
O0=O01、O02、…、O0n,
O1=O11、O12、…、O1n，n≥1
且O11=O0n,O12=O0(n-1),…,O1n=O01

(1)

同时应满足I01⊆I02⊆…⊆I0n，I11⊇I12⊇…⊇I1n，O01⊇O02⊇…⊇O0n，O11⊆O12⊆…⊆O1n。

例如：源输入测试用例组中的3次输入分别为I01=电脑、I02=笔记本电脑、I03=戴尔笔记本电脑，满足I01⊆I02⊆I03, 对应的源测试用例组输出结果为O01、O02、O03, 且应满足O01⊇O02⊇O03， 后续输入测试用例组的3次输入分别为I11=戴尔笔记本电脑、I12=笔记本电脑、I13=电脑，满足I11⊇I12⊇I13, 对应的后续测试用例组输出结果为O11、O12、O13, 且应满足O11⊆O12⊆O13， 同时源输出组和后续输出组之间的关系应满足O01=O13，O02=O12，O03=O11， 或满足其中任意一种关系，表示测试成功，反之测试失败。

2.2 交集等价

交集等价模式的定义源自于关系代数中的交集运算，是在“等价性”和“完整分区”模式的基础上提出的一种适用于多项选择搜索功能的蜕变关系模式，它表示源输入与所有后续输入交集等价，且最后一次后续输入是其它后续输入的并集，源输出等价于n-1次后续输出之和减去第n次后续输出的关系。如式(2)所示，数学关系表示为

I0=I1∩I2∩…∩In,In=I1∪I2∪…∪In-1⟹
O0=O1+O2+…+On-1-On，n≥1

(2)

例如：安居客搜索租房的相关房源信息，添加筛选条件“户型”为“二室”作为I0，修改筛选条件为“一室&二室”生成I1、修改条件为“二室&三室”作为I2、修改条件为“一室&二室&三室”I3，满足I3=I1∪I2。 判断O0、O1、O2、O3之间的关系是否满足O0=O1+O2-O3。

3 条件筛选搜索系统的蜕变测试

利用蜕变关系模式构建的蜕变关系，简化了执行蜕变测试过程中蜕变关系的识别。下面将从理论和具体测试步骤两个角度说明如何在条件筛选搜索系统中利用蜕变关系模式构建和识别蜕变关系执行蜕变测试，是一种面向最终用户的软件测试方法。蜕变关系模式表示源输入输出和后续输入输出之间的关系，是一种抽象模式；将抽象化的蜕变关系模式实例化即为构建蜕变关系的过程，利用传统软件测试方法生成源测试用例输入，根据构建的蜕变关系修改源测试用例的输入参数生成后续测试用例输入，是抽象模式具体化的过程；执行源和后续测试用例输入，并比较源测试用例输出和后续测试用例输出结果之间的关系是否违反了蜕变关系，是识别蜕变关系的过程。如果符合蜕变关系则测试通过，反之，测试不通过。如图2所示。

图2 蜕变关系模式构建和识别蜕变关系执行蜕变测试的过程

基于条件筛选搜索系统的具体蜕变测试步骤如下：

蜕变测试：识别条件筛选搜索系统多次输出结果之间的蜕变关系

输入：用户根据需求自定义的搜索条件I,I={I0,I1,…,In|(n≥1)}

输出：满足搜索条件I的输出数据集O,O={O0,O1,…,On|(n≥1)}

步骤1 在输入框中Input并添加Select作为源测试用例输入I0, 执行搜索得到的结果为源测试用例输出O0。

步骤2 为待测搜索程序功能选择合适的蜕变关系模式(MRP)。

步骤3 修改源测试用例的Input或者Select作为后续测试用例输入Ii,i=1,2,…,n； 修改后的Ii与I0应该满足MRP指定的输入之间的关系。

步骤4 对后续测试用例输入Ii,i=1,2,…,n执行搜索，得到的后续测试用例输出结果分别为O1,…,On。

步骤5 比较源测试用例输出O0和后续测试用例输出O1,…,On是否满足蜕变关系指定的输出之间的关系，若满足，表示测试通过；反之测试不通过，基于条件筛选的搜索系统存在软件故障。

首先，确定待测条件筛选搜索系统的功能，并利用传统软件测试方式测试程序能否正确执行。若程序可以正确执行，则对程序进行蜕变测试。

其次，用户根据待测条件筛选搜索系统的功能，利用传统软件测试方法自定义搜索条件和筛选条件生成源测试用例，选择合适的蜕变关系模式，并且根据蜕变关系模式源输入和后续输入之间的关系修改源测试用例的输入参数生成后续测试用例输入。

最后，执行程序并记录程序的源测试用例输出与后续测试用例输出结果，比较多次输出结果之间的关系是否符合构建的蜕变关系。如果不违反蜕变关系，表示蜕变测试通过，若违反蜕变关系则表示测试不通过，意味着条件筛选搜索系统存在软件设计故障。

4 实 验

实验以京东商城和安居客两大网站的条件筛选搜索系统作为基础实验环境，两者在中国拥有众多的用户，数据源类型和数量丰富，样本数据真实可靠。研究显示[17]，蜕变测试只需要平均3-6种不同的蜕变关系就可以揭示至少90%的Oracle能够检测到的故障。因此，实验根据网站的搜索功能设计首先选用了现有方法中的等价性、等效性、合并条件、析取条件、不相交的分区、完整分区6种蜕变关系模式构建和识别蜕变关系执行蜕变测试，并记录检测结果。然后沿用了等价性、等效性、不相交的分区、完整分区4种蜕变关系模式并加入改进提出的交集等价和IO组对称相等两种蜕变关系模式共6种蜕变关系模式作为改进的方法构建蜕变关系执行蜕变测试作比较。最终指出两个网站中存在的软件设计问题以改进网站的设计质量。

实验欲回答3个问题：

Q1：改进提出的两种蜕变关系模式是否能够帮助简化蜕变测试，并提高检测效率？

Q2：实验过程中存在哪些潜在的有效性威胁？

Q3：改进方法中的6种蜕变关系模式在多大程度上优于现有方法中的6种蜕变关系模式？

4.1 实验过程

鉴于Web网站中庞大的数据量，实验选用了京东商城中图书、美妆、运动、电脑和安居客中新房、二手房、租房、写字楼8个具有代表性网页的条件筛选搜索结果作为实验数据，在对条件筛选搜索功能测试的过程中生成源测试用例，并通过蜕变关系模式实例化的蜕变关系，构建后续测试用例，执行蜕变测试。

利用现有方法中等价性、等效性、合并条件、析取条件、不相交的分区、完整分区6种蜕变关系模式构建的蜕变关系和测试次数数据见表1。

表1 前6种MRPS构建的蜕变关系与测试次数

采用等价性、等效性、IO组对称相等、交集等价、不相交的分区和完整分区6种蜕变关系模式作为改进方法构建的蜕变关系和测试次数数据见表2。

表1和表2第一列表示两个网站中的8个网页，其余列分别是针对数据集的8个网页利用蜕变关系模式生成的蜕变关系(MR)数量、执行蜕变测试的次数(Count)。网站中不同类型的搜索功能具有不同的筛选条件，因此根据不同的筛选条件为每种模式构建了2个-8个蜕变关系，总计473个蜕变关系，并利用这些关系执行至少两次蜕变测试，以保证检测的真实有效性。

表2 后6种MRPS构建的蜕变关系与测试次数

4.2 实验结果与分析

实验采用了精确率(Precision)和召回率(Recall)衡量检测效果。精确率如式(3)所示，可以反应算法的查准率；召回率如式(4)所示，可以反应算法的查全率

(3)

(4)

其中，P表示精确率，R表示召回率，TP表示检测到故障的相关数据量，FP表示未检测到故障的相关数据，FN表示未检测到故障的不相关信息量。实验分析了现有方法中的等价性、等效性、合并条件、析取条件、不相交的分区、完整分区6种蜕变关系模式和结合本文改进提出的两种蜕变关系模式组成的等价性、等效性、IO组对称相等、交集等价、不相交的分区、完整分区6种蜕变关系模式下对京东商城和安居客两个网站共8个网页执行蜕变测试的检测效果，根据式(3)和式(4)计算得出每个网页基于改进前和改进后的6种蜕变关系模式执行蜕变测试的精确率和召回率(见表3)。

表3 不同关系模式下的精确率和召回率

根据实验结果，可以回答实验部分提出的3个问题。

针对Q1：改进提出的蜕变关系模式能够帮助简化蜕变测试。传统的蜕变测试完全依赖于测试人员对于待测软件各个功能的熟悉程度，识别每个蜕变关系都必须根据每个被测程序的预期功能从头开始检测和识别，降低了蜕变测试的可靠性。改进提出的蜕变关系模式将程序输入输出之间的关系抽象化，使用这种关系模式和测试步骤，将蜕变关系的识别变成一个程序化问题：只需要根据蜕变关系模式，为每个搜索功能添加符合关系模式指定源输入和后续输入之间关系的输入条件，将其实例化即可。按照这个步骤，测试人员可以很容易地构建蜕变关系，检查源测输出和后续输出之间的关系是否符合关系模式指定的输出之间的关系可以很容易地识别蜕变关系。如第3章所述，每种模式定义了条件筛选搜索系统中输入输出类型之间的关系，包含了基于筛选条件搜索网站中的两种筛选条件类型(单选和多选)。实验部分利用蜕变关系模式对京东商城和安居客两个网站分别构建蜕变关系(见表1和表2)，简化了构建蜕变关系的过程。

针对Q2：实验中存在的有效性威胁主要包括：①能否有效构建蜕变关系；②能否正确检测软件故障。

对于①，构建的蜕变关系的有效性取决于蜕变关系模式定义的质量好坏。因此，通过记录两个网站执行蜕变测试构建的蜕变关系及测试次数(见表1和表2)，结合表4记录的基于改进前的6种蜕变关系模式和改进后的6种蜕变关系模式执行蜕变测试检测到故障的数量，并且对比表3记录的改进前方法和改进后方法的精确率和召回率，验证了改进提出的两种新型蜕变关系模式能够帮助构建有效的蜕变关系。

表4 前6种MRPS和后6种MRPS执行蜕变测试检测到的故障数量

对于②，研究显示[17]，蜕变测试只需要平均3到6种不同的蜕变关系就可以揭示至少90%的Oracle能够检测到的故障。因此，首先在对两个网站的前后两次测试中都选用了6种不同类型的蜕变关系模式，帮助构建6种不同类型的蜕变关系，并且根据每个蜕变关系分别进行了至少两次测试，然后分析了被违反的蜕变关系，直到故障能够被重现，然后检查故障是否被记录，如果没有记录则在记录中添加检测到的问题以及该问题如何被人为重现。最后，指出用户执行搜索的过程中可能出现的意外情况，保证记录故障文档的严谨有效以及软件检测的高质量。

针对Q3：通过表3，可见改进的方法在精确率和召回率方面均显著优于改进前的方法。结合表4，易见性能提升的原因是改进的模式“IO组对称相等”优于模式“合并条件”和“析取条件”，在“等价性”和“完整性”模式的基础上提出的“交集等价”模式也更直接提高了蜕变测试的精确率。因此，在利用蜕变关系模式简化蜕变测试执行的过程中，本文改进提出的两种蜕变关系模式能够有效地检测出更多的软件设计故障，提高蜕变测试的检测效率，更全面地指导软件设计问题以改进网站的设计质量。

5 结束语

通过分析现有蜕变关系模式中的“合并条件”和“析取条件”模式，提出了“IO组对称相等”模式，并在“等价性”和“完整性”模式的基础上提出了基于多项选择筛选条件的蜕变关系模式，即“交集等价”模式。总结现有的蜕变关系模式和改进提出的蜕变关系模式，并以此构建的蜕变关系，在简化蜕变关系识别过程的同时可以显著提高蜕变测试的故障检测质量。

实验部分以京东商城、安居客两个网站中共8个网页为对象，分别选择改进前和改进后的6种蜕变关系模式构建蜕变关系，帮助生成测试用例，进而对网站中基于条件筛选搜索的功能执行测试。通过分析蜕变测试的精确率与召回率，验证了改进提出的蜕变关系模式对条件筛选搜索系统执行蜕变测试的有效性。

未来的工作主要包括：识别更多新的并且有效的蜕变关系模式；将蜕变关系模式应用于更广泛的科学领域中；识别和推断蜕变关系以及创建有效的测试用例集。