基于Pairwise算法的組合測(cè)試應(yīng)用研究

鄭根讓 林正春

（1.中山職業(yè)技術(shù)學(xué)院 廣東省中山市 528404 2.廣東技術(shù)師范大學(xué) 廣東省廣州市 510665）

1 引言

隨著軟件技術(shù)的不斷發(fā)展，軟件開(kāi)發(fā)的復(fù)雜性、集成度和可靠性要求越來(lái)越高，對(duì)軟件質(zhì)量保證的軟件測(cè)試提出了更高的要求。同時(shí)，隨著軟件在各行業(yè)的廣泛應(yīng)用，軟件系統(tǒng)功能不斷強(qiáng)大，系統(tǒng)復(fù)雜度也在持續(xù)提高，軟件系統(tǒng)需要支持多平臺(tái)和多場(chǎng)景，這就需要使用組合測(cè)試方法對(duì)軟件系統(tǒng)進(jìn)行測(cè)試。

組合測(cè)試是一種重要的軟件測(cè)試方法。它以覆蓋表作為測(cè)試用例集，能夠以少量的測(cè)試用例有效地檢測(cè)由軟件各參數(shù)之間的交互作用所觸發(fā)的失效。覆蓋表生成是組合測(cè)試要解決的關(guān)鍵問(wèn)題，也是軟件測(cè)試重點(diǎn)研究的領(lǐng)域。組合測(cè)試覆蓋表生成主要基于三種框架：測(cè)試用例演化（Evolve Test Case）、參數(shù)演化（Evolve Parameter）和整表演化（Evolve Test Set）。組合測(cè)試可以通過(guò)三種框架和不同算法有效結(jié)合形成不同的覆蓋表生成算法。

配對(duì)測(cè)試（Pairwise）可以根據(jù)已設(shè)定的條件，自動(dòng)生成在測(cè)試效率和測(cè)試覆蓋率之間做出平衡的組合，由于兩因素組合測(cè)試在測(cè)試用例個(gè)數(shù)和錯(cuò)誤檢測(cè)能力上達(dá)到了較好的平衡，因此它是目前主流的組合測(cè)試方法。

組合測(cè)試的研究與發(fā)展一直是由應(yīng)用驅(qū)動(dòng)的。電商平臺(tái)是目前應(yīng)用廣泛，功能龐雜的應(yīng)用系統(tǒng)，因其功能模塊多，用戶需求多，應(yīng)用終端結(jié)構(gòu)多樣，使得測(cè)試工作復(fù)雜而困難。

PICT是一個(gè)現(xiàn)有的公共可用工具，構(gòu)建在一個(gè)靈活的組合測(cè)試用例生成引擎之上，通過(guò)設(shè)計(jì)許多組合策略來(lái)幫助測(cè)試人員選擇能最大限度地發(fā)現(xiàn)缺陷的輸入組合子集。

本研究利用Pairwise算法思想對(duì)電商平臺(tái)系統(tǒng)測(cè)試，使用PICT工具對(duì)電商平臺(tái)進(jìn)行組合測(cè)試實(shí)驗(yàn)，根據(jù)電商平臺(tái)運(yùn)行需求利用貪心算法對(duì)約束關(guān)系進(jìn)行了優(yōu)化，進(jìn)一步提高組合測(cè)試效能。

2 組合測(cè)試

2.1 組合測(cè)試及其發(fā)展

組合測(cè)試是一種充分考慮了各種因素及其組合相互作用的軟件測(cè)試方法，實(shí)踐證明組合測(cè)試在多種因素及其相互作用下的復(fù)雜軟件系統(tǒng)測(cè)試中應(yīng)用極為廣泛也最為有效。

組合測(cè)試CT(combinatorial testing)采用系統(tǒng)的抽樣機(jī)制對(duì)參數(shù)間的交互作用進(jìn)行有針對(duì)性的覆蓋，從而減少測(cè)試用例的規(guī)模[1,2]。已有研究結(jié)果表明：軟件系統(tǒng)中大約70%的故障是由兩個(gè)參數(shù)間的交互作用引起的；同時(shí)，與故障相關(guān)的參數(shù)個(gè)數(shù)一般不超過(guò)6個(gè)[3]。因此，組合測(cè)試是一種科學(xué)有效的軟件測(cè)試方法。

組合測(cè)試具有廣泛的應(yīng)用場(chǎng)景和發(fā)展空間，已發(fā)展成為一種獨(dú)具特色和有影響力的科學(xué)實(shí)用的軟件測(cè)試方法。從上世紀(jì)末，美國(guó)和日本的研究者將實(shí)驗(yàn)設(shè)計(jì)思想引入計(jì)算機(jī)軟硬件測(cè)試，并逐漸發(fā)展成組合測(cè)試方法。組合測(cè)試已在輸入?yún)?shù)測(cè)試、配置測(cè)試、軟件產(chǎn)品線測(cè)試、事件驅(qū)動(dòng)軟件測(cè)試、并發(fā)程序測(cè)試、移動(dòng)應(yīng)用測(cè)試和安全測(cè)試等方面得到廣泛應(yīng)用[4]。

2.2 組合測(cè)試實(shí)現(xiàn)原理

組合測(cè)試是一種測(cè)試用例生成方法，其對(duì)傳統(tǒng)測(cè)試用例方法進(jìn)行了綜合。組合測(cè)試?yán)碚摽捎梢粋€(gè)數(shù)學(xué)模型和一個(gè)假設(shè)表示：

如果影響待測(cè)軟件系統(tǒng)的因素有n個(gè)[5]，記為F={f1,f2,…,fn}，其中，參數(shù)fi有l(wèi)i個(gè)可能取值，每個(gè)參數(shù)取值為wi={0,1,…,li-1}，1≤i≤n。

設(shè)m元組(w1,w2,…,wn)(wi∈Wi)為SUT（software under testing）的一條測(cè)試用例。組合測(cè)試的測(cè)試用例集組成覆蓋表。

SUT的t維覆蓋表CA(N;t,n,(w1,w2,…,wn))是一個(gè)N×n的數(shù)組，wi是第i列對(duì)應(yīng)的第 i 個(gè)參數(shù)，任意t個(gè)參數(shù)形成的N×t的子數(shù)組中包含了該t個(gè)參數(shù)的所有t元組，t表示組合覆蓋測(cè)試的強(qiáng)度[6]。

以電商平臺(tái)為例，它有多種應(yīng)用操作系統(tǒng)(f1)，可以使用不同的瀏覽器(f2)，有不同的網(wǎng)絡(luò)連接方式(f3)以及不同的內(nèi)存配置(f4)，電商平臺(tái)配置見(jiàn)表1，共有4個(gè)參數(shù)，每個(gè)參數(shù)都有3個(gè)取值，可以形成二維覆蓋表CA(9;2,34)。

2.3 基于Pairwise算法的組合測(cè)試

Pairwise可以根據(jù)設(shè)定的條件，自動(dòng)生成在測(cè)試效率和測(cè)試覆蓋率之間做出平衡的組合，由于兩因素組合測(cè)試在測(cè)試用例個(gè)數(shù)和錯(cuò)誤檢測(cè)能力上達(dá)到了較好的平衡，它是目前主流的組合測(cè)試方法。當(dāng)然，Pairwise也有不足，主要問(wèn)題是Pairwise對(duì)于維度的分解來(lái)說(shuō)，需要對(duì)業(yè)務(wù)很熟悉，需要正交測(cè)試法的理論支持。需要中等專業(yè)的測(cè)試人員才能完成。其次，Pairwise還是有一定的遺漏。相比于全正交設(shè)計(jì)法來(lái)說(shuō)，Pairwise算法對(duì)于多于2個(gè)因素相互作用所產(chǎn)生的bug，沒(méi)有覆蓋到。

2.4 基于Pairwise算法的組合測(cè)試工具

現(xiàn)很多程序都圍繞Pairwise算法產(chǎn)生，最著名的就是ReduceArray，SmartDesgin和微軟的PICT工具。

ReduceArray按照Pairwise覆蓋要求[6]，輸出剔除無(wú)效用例后的一個(gè)用例子集可以支持約束條件，支2持維或3維覆蓋可以給出每個(gè)用例覆蓋的Pairwise對(duì)的數(shù)量，可以給出輸入用例集和輸出用例集有哪些Pairwise對(duì)沒(méi)有覆蓋到，給出的用例集合可以達(dá)到最優(yōu)。速度很快,效率高,但隨著用例規(guī)模的增加,效率下降明顯。在表格中，編寫(xiě)的腳本來(lái)執(zhí)行，操作較簡(jiǎn)單。

SmartDesgin符合N維Pairwise全覆蓋的一組用例，支持約束條件[7]，支持2維的Pairwise覆蓋，給出的用例集合不是最優(yōu)。速度很快，但效率較低。在表格中進(jìn)行操作，稍有一慎可能導(dǎo)致結(jié)果錯(cuò)誤。運(yùn)行過(guò)程中有時(shí)會(huì)導(dǎo)致異常關(guān)閉。

PICT（The Pairwise Independent Combinatorial Testing tool）是一款由微軟公司出品的命令行用例生成工具，生成的測(cè)試集可以覆蓋任意N個(gè)變量的取值組合?；诮M合測(cè)試的理論，該測(cè)試用例集可以發(fā)現(xiàn)N個(gè)因素共同作用引發(fā)的缺陷。PICT接受純文本模式的文件作為輸入，輸入文件中包括參數(shù)類別、取值集與約束關(guān)系，輸出是一個(gè)用來(lái)組成組合覆蓋測(cè)試用例的矩陣，每一行表示一個(gè)測(cè)試用例，每一列代表系統(tǒng)的一個(gè)參數(shù)，每一項(xiàng)代表測(cè)試用例對(duì)應(yīng)的參數(shù)取值。PICT可幫助測(cè)試人員產(chǎn)生比手動(dòng)生成更高效的測(cè)試用例。

2.5 Pairwise算法在PICT中的實(shí)現(xiàn)思路

Pairwise是L.L.Thurstone(29 May1887 - 30 September 1955)[8]在1927年首先提出來(lái)的。他是美國(guó)的一位心理統(tǒng)計(jì)學(xué)家。Pairwise也正是基于數(shù)學(xué)統(tǒng)計(jì)和對(duì)傳統(tǒng)的正交分析法進(jìn)行優(yōu)化后得到的產(chǎn)物。

Pairwise基于如下2個(gè)假設(shè)：

（1）每一個(gè)維度都是正交的，即每一個(gè)維度互相都沒(méi)有交集。

（2）根據(jù)數(shù)學(xué)統(tǒng)計(jì)分析，73%的缺陷（單因子是35%，雙因子是38%）是由單因子或2個(gè)因子相互作用產(chǎn)生的。19%的缺陷是由3個(gè)因子相互作用產(chǎn)生的。因此，Pairwise基于覆蓋所有2因子的交互作用產(chǎn)生的用例集合性價(jià)比最高而產(chǎn)生的。

3 電商平臺(tái)測(cè)試設(shè)計(jì)

3.1 電商平臺(tái)適合組合測(cè)試

電子商務(wù)平臺(tái)簡(jiǎn)稱電商平臺(tái)，是一個(gè)為企業(yè)或個(gè)人提供網(wǎng)上交易洽談的平臺(tái)。企業(yè)電子商務(wù)平臺(tái)是建立在Internet網(wǎng)上進(jìn)行商務(wù)活動(dòng)的虛擬網(wǎng)絡(luò)空間和保障商務(wù)順利運(yùn)營(yíng)的管理環(huán)境；是協(xié)調(diào)、整合信息流、貨物流、資金流有序、關(guān)聯(lián)、高效流動(dòng)的重要場(chǎng)所。企業(yè)、商家可充分利用電子商務(wù)平臺(tái)提供的網(wǎng)絡(luò)基礎(chǔ)設(shè)施、支付平臺(tái)、安全平臺(tái)、管理平臺(tái)等共享資源有效地、低成本地開(kāi)展自己的商業(yè)活動(dòng)。

電商平臺(tái)具有終端多樣化、交易復(fù)雜化、信息多元化等特點(diǎn)，以終端設(shè)備為例，終端可以是PC，也可以是SP（Smartphone）、PAD還可以是PDA，再比如購(gòu)物的付款方式有貨到付款、銀行卡付款、微信付款、支付寶付款及白條等，電商平臺(tái)支付方式頁(yè)面如圖1所示。因此，電商平臺(tái)測(cè)試適用組合測(cè)試來(lái)解決多因素組合的測(cè)試問(wèn)題。

3.2 電商平臺(tái)組合測(cè)試設(shè)計(jì)

電商交易平臺(tái)是一個(gè)復(fù)雜的網(wǎng)絡(luò)交易系統(tǒng)，系統(tǒng)功能模塊多，輸入?yún)?shù)多且一般有約束關(guān)系。以某在線的電子商務(wù)平臺(tái)的商品結(jié)算模塊為例，商品支付模塊包括支付方式、配送方式和使用優(yōu)惠等3個(gè)功能選項(xiàng)。支付方式有貨到付款、在線支付、朋友代付，配送方式有自營(yíng)配送、自選快遞和上門(mén)自提，優(yōu)惠券有商品優(yōu)惠券、運(yùn)費(fèi)券和優(yōu)惠碼兌換，禮品卡有使用、無(wú)和添加3種狀態(tài)。

構(gòu)建模型

通過(guò)分析電商平臺(tái)可以構(gòu)建支付方式、配送方式、優(yōu)惠券、禮品卡等有4個(gè)輸入?yún)?shù)的模型，每個(gè)參數(shù)有3個(gè)可選值，如表2所示。

表2：電商平臺(tái)輸入?yún)?shù)及取值

生成測(cè)試用例：

將構(gòu)建模型的參數(shù)及取值，輸入PICT生成測(cè)試用例，如表3所示。

表3：PICT生成的電商平臺(tái)測(cè)試用例

3.3 約束（constraint）處理

在組合測(cè)試的基礎(chǔ)理論中，各個(gè)因素的取值是相互獨(dú)立的，即因素A的取值不會(huì)影響因素B的取值。但是，大多數(shù)被測(cè)試應(yīng)用的因素之間存在約束關(guān)系。

PICT默認(rèn)使用兩變量組合方法，生成的測(cè)試集可以覆蓋任意兩個(gè)變量的取值組合。并且由于組合測(cè)試的數(shù)學(xué)模型沒(méi)有描述變量之間的約束關(guān)系，生成的用例集存在一定的冗余，利用PICT可通過(guò)添加輸入的約束條件來(lái)進(jìn)行改進(jìn)。

在電商平臺(tái)中，當(dāng)支付方式選擇“朋友代付”時(shí)，不能選擇所有優(yōu)惠券和禮品卡。當(dāng)支付方式選擇“貨到付款”時(shí)，配送方式不能選擇“上門(mén)自提”；當(dāng)配送方式選擇“上門(mén)自提”時(shí)，優(yōu)惠券不能領(lǐng)取“運(yùn)費(fèi)券”。根據(jù)電調(diào)平臺(tái)中關(guān)于支付方式、配送方式、優(yōu)惠券及禮品卡之間的關(guān)聯(lián)關(guān)系編寫(xiě)約束條件代碼：

IF [支付方式]="朋友代付" THEN ([優(yōu)惠券]＜＞ "商品優(yōu)惠券" OR [優(yōu)惠券]＜＞ "運(yùn)費(fèi)券" OR [優(yōu)惠券]＜＞ "優(yōu)惠兌換碼");

IF [支付方式]="貨到付款" THEN [配送方式]in {"自營(yíng)配送","自選快遞"};

IF [配送方式]="上門(mén)自提" THEN [優(yōu)惠券]in {"商品優(yōu)惠券","優(yōu)惠兌換碼"};

將約束條件代碼輸入PICT，完成具有約束條件的用例生成，如表4所示。

表4：具有約束條件的PICT生成用例

4 測(cè)試結(jié)果及分析

為了進(jìn)一步分析PICT在組合測(cè)試中的效率，以某電商平臺(tái)為測(cè)試對(duì)象，設(shè)計(jì)了4個(gè)覆蓋數(shù)組CA（34）、CA（312）、CA（2100）和CA（1020）（4個(gè)3值，12個(gè)3值，200個(gè)2值，20個(gè)10值）和2個(gè)混合覆蓋數(shù)組MCA（415317220）（表示待測(cè)實(shí)例有52個(gè)參數(shù)，其中，15個(gè)4值，17個(gè)3值，20個(gè)2值）和MCA（41320235）（表示待測(cè)實(shí)例有56個(gè)參數(shù)，其中，1個(gè)4值，20個(gè)3值，35個(gè)2值），分別使用AETG、IPO、CTS、DDA等方法與PICT進(jìn)行用例覆蓋表的生成規(guī)模生成對(duì)比實(shí)驗(yàn)，結(jié)果如表5所示。

表5：用例生成規(guī)模對(duì)比實(shí)驗(yàn)

從用例覆蓋表的生成規(guī)模情況可以看出，用PICT生成的用例覆蓋表的生成規(guī)?？傮w上是處于中等的，但PICT核心算法的效率與其他工具相比還是占有優(yōu)勢(shì)的，在工具的易用性和核心引擎的可擴(kuò)展性等方面PICT具有較好的表現(xiàn)。

5 結(jié)語(yǔ)

總之，PICT是一款開(kāi)放實(shí)用的組合測(cè)試工具，它是構(gòu)建在一個(gè)靈活的組合測(cè)試用例生成引擎之上，具有簡(jiǎn)單易用、低成本、高效率的特點(diǎn)，特別是在測(cè)試生成的速度上明顯優(yōu)于其他方法。組合測(cè)試很難一次性就把工作做到很完美，在組合測(cè)試中應(yīng)該把握測(cè)試的靈活性使組合測(cè)試有更好的自適應(yīng)性和可拓展性。