基于Pairwise算法的组合测试应用研究

郑根让 林正春

（1.中山职业技术学院 广东省中山市 528404 2.广东技术师范大学 广东省广州市 510665）

1 引言

随着软件技术的不断发展，软件开发的复杂性、集成度和可靠性要求越来越高，对软件质量保证的软件测试提出了更高的要求。同时，随着软件在各行业的广泛应用，软件系统功能不断强大，系统复杂度也在持续提高，软件系统需要支持多平台和多场景，这就需要使用组合测试方法对软件系统进行测试。

组合测试是一种重要的软件测试方法。它以覆盖表作为测试用例集，能够以少量的测试用例有效地检测由软件各参数之间的交互作用所触发的失效。覆盖表生成是组合测试要解决的关键问题，也是软件测试重点研究的领域。组合测试覆盖表生成主要基于三种框架：测试用例演化（Evolve Test Case）、参数演化（Evolve Parameter）和整表演化（Evolve Test Set）。组合测试可以通过三种框架和不同算法有效结合形成不同的覆盖表生成算法。

配对测试（Pairwise）可以根据已设定的条件，自动生成在测试效率和测试覆盖率之间做出平衡的组合，由于两因素组合测试在测试用例个数和错误检测能力上达到了较好的平衡，因此它是目前主流的组合测试方法。

组合测试的研究与发展一直是由应用驱动的。电商平台是目前应用广泛，功能庞杂的应用系统，因其功能模块多，用户需求多，应用终端结构多样，使得测试工作复杂而困难。

PICT是一个现有的公共可用工具，构建在一个灵活的组合测试用例生成引擎之上，通过设计许多组合策略来帮助测试人员选择能最大限度地发现缺陷的输入组合子集。

本研究利用Pairwise算法思想对电商平台系统测试，使用PICT工具对电商平台进行组合测试实验，根据电商平台运行需求利用贪心算法对约束关系进行了优化，进一步提高组合测试效能。

2 组合测试

2.1 组合测试及其发展

组合测试是一种充分考虑了各种因素及其组合相互作用的软件测试方法，实践证明组合测试在多种因素及其相互作用下的复杂软件系统测试中应用极为广泛也最为有效。

组合测试CT(combinatorial testing)采用系统的抽样机制对参数间的交互作用进行有针对性的覆盖，从而减少测试用例的规模[1,2]。已有研究结果表明：软件系统中大约70%的故障是由两个参数间的交互作用引起的；同时，与故障相关的参数个数一般不超过6个[3]。因此，组合测试是一种科学有效的软件测试方法。

组合测试具有广泛的应用场景和发展空间，已发展成为一种独具特色和有影响力的科学实用的软件测试方法。从上世纪末，美国和日本的研究者将实验设计思想引入计算机软硬件测试，并逐渐发展成组合测试方法。组合测试已在输入参数测试、配置测试、软件产品线测试、事件驱动软件测试、并发程序测试、移动应用测试和安全测试等方面得到广泛应用[4]。

2.2 组合测试实现原理

组合测试是一种测试用例生成方法，其对传统测试用例方法进行了综合。组合测试理论可由一个数学模型和一个假设表示：

如果影响待测软件系统的因素有n个[5]，记为F={f1,f2,…,fn}，其中，参数fi有li个可能取值，每个参数取值为wi={0,1,…,li-1}，1≤i≤n。

设m元组(w1,w2,…,wn)(wi∈Wi)为SUT（software under testing）的一条测试用例。组合测试的测试用例集组成覆盖表。

SUT的t维覆盖表CA(N;t,n,(w1,w2,…,wn))是一个N×n的数组，wi是第i列对应的第 i 个参数，任意t个参数形成的N×t的子数组中包含了该t个参数的所有t元组，t表示组合覆盖测试的强度[6]。

以电商平台为例，它有多种应用操作系统(f1)，可以使用不同的浏览器(f2)，有不同的网络连接方式(f3)以及不同的内存配置(f4)，电商平台配置见表1，共有4个参数，每个参数都有3个取值，可以形成二维覆盖表CA(9;2,34)。

2.3 基于Pairwise算法的组合测试

Pairwise可以根据设定的条件，自动生成在测试效率和测试覆盖率之间做出平衡的组合，由于两因素组合测试在测试用例个数和错误检测能力上达到了较好的平衡，它是目前主流的组合测试方法。当然，Pairwise也有不足，主要问题是Pairwise对于维度的分解来说，需要对业务很熟悉，需要正交测试法的理论支持。需要中等专业的测试人员才能完成。其次，Pairwise还是有一定的遗漏。相比于全正交设计法来说，Pairwise算法对于多于2个因素相互作用所产生的bug，没有覆盖到。

2.4 基于Pairwise算法的组合测试工具

现很多程序都围绕Pairwise算法产生，最著名的就是ReduceArray，SmartDesgin和微软的PICT工具。

ReduceArray按照Pairwise覆盖要求[6]，输出剔除无效用例后的一个用例子集可以支持约束条件，支2持维或3维覆盖可以给出每个用例覆盖的Pairwise对的数量，可以给出输入用例集和输出用例集有哪些Pairwise对没有覆盖到，给出的用例集合可以达到最优。速度很快,效率高,但随着用例规模的增加,效率下降明显。在表格中，编写的脚本来执行，操作较简单。

SmartDesgin符合N维Pairwise全覆盖的一组用例，支持约束条件[7]，支持2维的Pairwise覆盖，给出的用例集合不是最优。速度很快，但效率较低。在表格中进行操作，稍有一慎可能导致结果错误。运行过程中有时会导致异常关闭。

PICT（The Pairwise Independent Combinatorial Testing tool）是一款由微软公司出品的命令行用例生成工具，生成的测试集可以覆盖任意N个变量的取值组合。基于组合测试的理论，该测试用例集可以发现N个因素共同作用引发的缺陷。PICT接受纯文本模式的文件作为输入，输入文件中包括参数类别、取值集与约束关系，输出是一个用来组成组合覆盖测试用例的矩阵，每一行表示一个测试用例，每一列代表系统的一个参数，每一项代表测试用例对应的参数取值。PICT可帮助测试人员产生比手动生成更高效的测试用例。

2.5 Pairwise算法在PICT中的实现思路

Pairwise是L.L.Thurstone(29 May1887 - 30 September 1955)[8]在1927年首先提出来的。他是美国的一位心理统计学家。Pairwise也正是基于数学统计和对传统的正交分析法进行优化后得到的产物。

Pairwise基于如下2个假设：

（1）每一个维度都是正交的，即每一个维度互相都没有交集。

（2）根据数学统计分析，73%的缺陷（单因子是35%，双因子是38%）是由单因子或2个因子相互作用产生的。19%的缺陷是由3个因子相互作用产生的。因此，Pairwise基于覆盖所有2因子的交互作用产生的用例集合性价比最高而产生的。

3 电商平台测试设计

3.1 电商平台适合组合测试

电子商务平台简称电商平台，是一个为企业或个人提供网上交易洽谈的平台。企业电子商务平台是建立在Internet网上进行商务活动的虚拟网络空间和保障商务顺利运营的管理环境；是协调、整合信息流、货物流、资金流有序、关联、高效流动的重要场所。企业、商家可充分利用电子商务平台提供的网络基础设施、支付平台、安全平台、管理平台等共享资源有效地、低成本地开展自己的商业活动。

电商平台具有终端多样化、交易复杂化、信息多元化等特点，以终端设备为例，终端可以是PC，也可以是SP（Smartphone）、PAD还可以是PDA，再比如购物的付款方式有货到付款、银行卡付款、微信付款、支付宝付款及白条等，电商平台支付方式页面如图1所示。因此，电商平台测试适用组合测试来解决多因素组合的测试问题。

3.2 电商平台组合测试设计

电商交易平台是一个复杂的网络交易系统，系统功能模块多，输入参数多且一般有约束关系。以某在线的电子商务平台的商品结算模块为例，商品支付模块包括支付方式、配送方式和使用优惠等3个功能选项。支付方式有货到付款、在线支付、朋友代付，配送方式有自营配送、自选快递和上门自提，优惠券有商品优惠券、运费券和优惠码兑换，礼品卡有使用、无和添加3种状态。

构建模型

通过分析电商平台可以构建支付方式、配送方式、优惠券、礼品卡等有4个输入参数的模型，每个参数有3个可选值，如表2所示。

表2：电商平台输入参数及取值

生成测试用例：

将构建模型的参数及取值，输入PICT生成测试用例，如表3所示。

表3：PICT生成的电商平台测试用例

3.3 约束（constraint）处理

在组合测试的基础理论中，各个因素的取值是相互独立的，即因素A的取值不会影响因素B的取值。但是，大多数被测试应用的因素之间存在约束关系。

PICT默认使用两变量组合方法，生成的测试集可以覆盖任意两个变量的取值组合。并且由于组合测试的数学模型没有描述变量之间的约束关系，生成的用例集存在一定的冗余，利用PICT可通过添加输入的约束条件来进行改进。

在电商平台中，当支付方式选择“朋友代付”时，不能选择所有优惠券和礼品卡。当支付方式选择“货到付款”时，配送方式不能选择“上门自提”；当配送方式选择“上门自提”时，优惠券不能领取“运费券”。根据电调平台中关于支付方式、配送方式、优惠券及礼品卡之间的关联关系编写约束条件代码：

IF [支付方式]="朋友代付" THEN ([优惠券]＜＞ "商品优惠券" OR [优惠券]＜＞ "运费券" OR [优惠券]＜＞ "优惠兑换码");

IF [支付方式]="货到付款" THEN [配送方式]in {"自营配送","自选快递"};

IF [配送方式]="上门自提" THEN [优惠券]in {"商品优惠券","优惠兑换码"};

将约束条件代码输入PICT，完成具有约束条件的用例生成，如表4所示。

表4：具有约束条件的PICT生成用例

4 测试结果及分析

为了进一步分析PICT在组合测试中的效率，以某电商平台为测试对象，设计了4个覆盖数组CA（34）、CA（312）、CA（2100）和CA（1020）（4个3值，12个3值，200个2值，20个10值）和2个混合覆盖数组MCA（415317220）（表示待测实例有52个参数，其中，15个4值，17个3值，20个2值）和MCA（41320235）（表示待测实例有56个参数，其中，1个4值，20个3值，35个2值），分别使用AETG、IPO、CTS、DDA等方法与PICT进行用例覆盖表的生成规模生成对比实验，结果如表5所示。

表5：用例生成规模对比实验

从用例覆盖表的生成规模情况可以看出，用PICT生成的用例覆盖表的生成规模总体上是处于中等的，但PICT核心算法的效率与其他工具相比还是占有优势的，在工具的易用性和核心引擎的可扩展性等方面PICT具有较好的表现。

5 结语

总之，PICT是一款开放实用的组合测试工具，它是构建在一个灵活的组合测试用例生成引擎之上，具有简单易用、低成本、高效率的特点，特别是在测试生成的速度上明显优于其他方法。组合测试很难一次性就把工作做到很完美，在组合测试中应该把握测试的灵活性使组合测试有更好的自适应性和可拓展性。