簡單循環(huán)約減三三組合測試用例生成方法

艾 華，宋曉秋，安 恒

(中國航天科工集團(tuán)第二研究院706所，北京 100854)

0 引 言

軟件測試在軟件開發(fā)過程中占重要地位，而測試用例是進(jìn)行軟件測試工作的基石[1]，研究結(jié)果表明覆蓋強(qiáng)度為n的最小測試用例集生成問題是NPC問題，隨著參數(shù)數(shù)量的增多，測試用例集規(guī)模也成倍增長，覆蓋所有的組合勢必使得測試用例集過大，從而導(dǎo)致測試工作占用巨大花費(fèi)，研究發(fā)現(xiàn)約70%的軟件缺陷可以通過兩兩組合測試發(fā)現(xiàn)，而通過三三組合測試能發(fā)現(xiàn)90%的軟件缺陷，最后可以通過六六組合測試發(fā)現(xiàn)幾乎所有的軟件缺陷。隨著覆蓋強(qiáng)度的增加，測試用例集規(guī)模成指數(shù)形式增長，因此研究人員在如何覆蓋強(qiáng)度為2的最小測試用例集的問題上進(jìn)行了大量的研究，從不同角度出發(fā)提出了多種算法[2,3]。

迄今為止，軟件測試領(lǐng)域?qū)蓛山M合測試已有充分的研究，而針對三三組合測試用例集的生成方法研究較少，主要包括IPOG算法、ITCH算法、Jenny算法等由兩兩組合測試算法改進(jìn)而來的通用算法，以及王小銀等提出的基于蟻群算法的三三組合測試用例集的生成方法[4]。三三組合測試能彌補(bǔ)兩兩組合測試缺陷發(fā)現(xiàn)率較低的不足，還能避免更高覆蓋強(qiáng)度組合測試成本過大的問題，本文以貪心算法為基礎(chǔ)[5]，借鑒IPO算法的思路，針對三三組合測試問題，提出了一種簡單循環(huán)約減三三組合測試用例生成方法(simple-cyclic-reduce，SCR)，算法的基本思路是先找到取值最少的前3個(gè)參數(shù)形成的最小測試用例集，再對剩下的參數(shù)進(jìn)行逐個(gè)擴(kuò)展，在擴(kuò)展的同時(shí)進(jìn)行循環(huán)約減，尋找當(dāng)前已擴(kuò)展參數(shù)的局部最優(yōu)解[6]，直到參數(shù)完全擴(kuò)展，得到的解近似代替全局最優(yōu)解[7]。

1 組合測試概念及其模型

假定待測系統(tǒng)SUT(software under testing)有n個(gè)輸入?yún)?shù)，用集合X={x1,x2,x3,…,xn}表示，輸入?yún)?shù)xi對應(yīng)的值域?yàn)閅i(i=1,2,3,…,n)。

定義1 測試用例集：假定某集合Ts={t1,t2,t3,…,tn}，對于集合中任意元素ti∈Ts,ti={ti1,ti2,ti3,…,tin},且tij∈Yj(i=1,2,3,…,n;j=1,2,3,…,n;i,j不相等)，則稱集合Ts為待測系統(tǒng)SUT的一個(gè)測試用例集，ti為待測系統(tǒng)的一個(gè)測試用例。

定義2 兩兩組合測試用例集：假定某集合Ts為待測系統(tǒng)SUT的一個(gè)測試用例集，如果集合X中任意兩個(gè)不同參數(shù)組成的任意組合對(xi,xj)，滿足如下條件，存在t∈Ts，使得任意xi∈t,xj∈t(其中i=1,2,3,…,n;j=1,2,3,…,n，i,j不相等)，則稱Ts為待測系統(tǒng)SUT的一個(gè)兩兩組合測試用例集。

例：設(shè)待測系統(tǒng)SUT有3個(gè)輸入?yún)?shù){x1,x2,x3}，各參數(shù)對應(yīng)的值域{a,b}、{c,d}、{e,f},則SUT共有12個(gè)兩兩組合對，見表1。

覆蓋這些兩兩組合對至少需要4個(gè)測試用例：(a,c,e)、(a,d,f)、(b,c,f)、(b,d,e)。兩兩組合測試能保證由一個(gè)參數(shù)及兩個(gè)參數(shù)間相互作用引發(fā)的軟件缺陷能被發(fā)現(xiàn)。

表1 3個(gè)2值參數(shù)SUT的兩兩組合對

定義3 三三組合測試用例集：假定某集合Ts為待測系統(tǒng)SUT的一個(gè)測試用例集，如果集合X中任意3個(gè)不同參數(shù)組成的任意組合對(xi,xj,xk)，滿足如下條件，存在t∈Ts，使得任意xi∈t,xj∈t,xk∈t(其中i=1,2,3,…n;j=1,2,3,…n;k=1,2,3,…n;i,j,k互不相等)，則稱Ts為待測系統(tǒng)SUT的一個(gè)三三組合測試用例集。

例：設(shè)待測系統(tǒng)SUT有4個(gè)輸入?yún)?shù){x1,x2,x3,x4}，各參數(shù)對應(yīng)的取值{a,b}、{c,d}、{e,f}、{g,h},則SUT共有32個(gè)三三組合對，見表2。

覆蓋這些三三組合對至少需要8個(gè)測試用例(a,c,e,g)、(a,c,f,g)、(a,d,f,g)、(b,c,f,g)、(a,d,e,h)、(b,d,e,g)、(b,c,e,h)、(b,d,f,h)。三三組合測試能保證到一個(gè)參數(shù)、兩個(gè)參數(shù)及3個(gè)參數(shù)間相互作用引發(fā)的軟件缺陷能被發(fā)現(xiàn)。

表2 4個(gè)2值參數(shù)SUT的三三組合對

2 相關(guān)研究

通過幾十年的研究與積累，在組合測試用例集生成的研究中，兩兩組合測試用例集的研究已經(jīng)相當(dāng)充分，相關(guān)的算法有很多，其中較為常見的有基于代數(shù)構(gòu)造法的正交拉丁方技術(shù)，及其變種Williams算法和Kobayashi算法；有基于貪心算法的IPO算法、AETG算法等；有基于解空間樹的PSST算法；有基于蟻群算法的ACO算法，以及在這些算法的基礎(chǔ)之上進(jìn)行的通用化研究，將這些算法中的部分算法擴(kuò)展到了三三組合測試用例集生成甚至n-way組合測試用例集生成，以下介紹幾種常用的組合測試用例生成算法。

2.1 AETG算法簡介

Cohen等提出通過“one-test-at-a-time”的思想來構(gòu)建測試用例集直到所有的兩兩組合對都被覆蓋的AETG算法，AETG算法在構(gòu)建測試用例時(shí)采用盡可能多地覆蓋較多的未覆蓋組合對的貪心策略來生成較小的測試用例集。最初AETG算法旨在生成兩兩組合測試用的組合測試用例集，隨著AETG算法的豐富與發(fā)展，出現(xiàn)了較多以AETG算法為基礎(chǔ)的變種以及通用的組合測試用例生成方法。

2.2 IPO算法簡介

Yu Lei等提出了生成結(jié)對測試用例的IPO算法，IPO算法采用貪心算法依次對參數(shù)進(jìn)行水平擴(kuò)展和垂直擴(kuò)展直到擴(kuò)展完所有的參數(shù)。IPO算法的基本思想是先對所有參數(shù)按照取值域非遞增排序，先用前兩個(gè)參數(shù)構(gòu)造初始測試用例集，再依此進(jìn)行水平擴(kuò)展和垂直擴(kuò)展，水平擴(kuò)展在測試用例數(shù)量不變的基礎(chǔ)上，添加新的參數(shù)的取值，使之包含的未覆蓋組合對數(shù)量最多；垂直擴(kuò)展在參數(shù)數(shù)量不變的基礎(chǔ)上，增加新測試用例使得包含的未覆蓋組合數(shù)量較多，或者改變已有的測試用例來實(shí)現(xiàn)覆蓋，直到所有組合對都被覆蓋，再擴(kuò)展下一個(gè)參數(shù)，直到所有的參數(shù)都擴(kuò)展完成。

同樣地IPO算法最初也是解決兩兩組合測試的測試用例集生成問題，Yu Lei等對IPO算法進(jìn)行通用化改進(jìn)，提出IPOG算法和IPOG-D算法，使得該算法能解決n-way(2≤n≤6)組合測試用例集生成問題。IPOG算法整體與IPO算法相似，在初始化測試用例集所用參數(shù)個(gè)數(shù)以及組合對的覆蓋強(qiáng)度上有變化，IPOG-D算法改變了擴(kuò)展方式，將參數(shù)分為兩組采用遞歸的形式進(jìn)行求解，水平擴(kuò)展過程是直接將列復(fù)制的過程，垂直擴(kuò)展是將兩種覆蓋強(qiáng)度的組合合并的過程，結(jié)果往往比IPOG算法差，但節(jié)省了遍歷并判斷所有的n-way組合對是否被覆蓋的時(shí)間，速度方面比IPOG算法快。

2.3 ACO算法簡介

王小銀等提出了基于蟻群算法的解決思路(ant colony optimization，ACO)，和AETG算法一樣，采用“one-test-at-a-time”的思想來逐個(gè)測試用例地生成組合測試用例集。在蟻群搜索組合測試用例生成過程中，將參數(shù)對應(yīng)成節(jié)點(diǎn)，參數(shù)的取值對應(yīng)為從節(jié)點(diǎn)引出的有向邊，一個(gè)測試用例為經(jīng)過各節(jié)點(diǎn)的一條路徑。蟻群算法過程是先將所有的螞蟻匯集在出第一個(gè)節(jié)點(diǎn)，然后每只螞蟻根據(jù)當(dāng)前節(jié)點(diǎn)各邊的信息素和動(dòng)態(tài)啟發(fā)信息的概率來選擇到下一節(jié)點(diǎn)的邊，直到螞蟻?zhàn)咄晁泄?jié)點(diǎn)，此路徑對應(yīng)一條測試用例，并添加到測試用例集中，直到覆蓋所有的三三組合對。

2.4 算法比較與工具介紹

AETG算法每次生成測試用例時(shí)都會產(chǎn)生M個(gè)候選的測試用例，Cohen通過實(shí)驗(yàn)驗(yàn)證M=50時(shí)，算法的時(shí)間花費(fèi)和結(jié)果相對較好，但總體時(shí)間花費(fèi)較大。IPO算法直接對參數(shù)進(jìn)行擴(kuò)展，每次擴(kuò)展一個(gè)參數(shù)，生成測試用例的速度快，但局部尋優(yōu)能力有限，產(chǎn)生的結(jié)果往往不如AETG算法。ACO算法將蟻群算法的思路應(yīng)用到測試用例集的生成問題上，但該算法信息素計(jì)算過程復(fù)雜，產(chǎn)生的結(jié)果有局限。目前三三組合測試方面的研究相對較少，逐參數(shù)擴(kuò)展方面還有待改進(jìn)，本文就此進(jìn)行了研究。

Bob Jenkins在用C語言寫了基于貪心算法的Jenny工具并公布在個(gè)人網(wǎng)站上供測試人員研究，此工具能生成2～6-way的測試用例集，Jenny工具操作簡單，無界面，能直接輸入?yún)?shù)調(diào)用并返回測試用例集。IBM研究院綜合幾種代數(shù)方法用Java語言設(shè)計(jì)了ITCH(intelligent test case handler)工具。Yu Lei用Java語言實(shí)現(xiàn)了IPOG算法和IPOG-D算法等多種逐參數(shù)形式生成測試用例集的策略，開發(fā)了具有用戶界面的ACTS工具，ACTS工具可操作性強(qiáng)，能選擇不同策略，不同覆蓋強(qiáng)度以及制定參數(shù)間的約束，生成測試用例集后還可以驗(yàn)證組合對的覆蓋率。

3 SCR算法

SCR算法以貪心算法為基礎(chǔ)，根據(jù)逐參數(shù)擴(kuò)展的思想來逐步生成三三組合測試用例集[8]。先從參數(shù)集中選擇取值最少的前3個(gè)參數(shù)生成一個(gè)初始測試用例集，初始測試用例集包含所選3個(gè)參數(shù)的所有取值組合，接著向測試用例集中添加第4個(gè)參數(shù)，在添加參數(shù)時(shí)，利用該參數(shù)的所有取值[9]對測試用例集中所有的測試用例進(jìn)行直接擴(kuò)展，最后再對測試用例集中所有測試用例進(jìn)行循環(huán)約減，直到循環(huán)約減測試用例集前后測試用例的數(shù)量不變，再添加下一參數(shù)，重復(fù)直接擴(kuò)展和循環(huán)約減過程，直到擴(kuò)展完所有參數(shù)[10]。

直接擴(kuò)展過程：在增加參數(shù)時(shí)對當(dāng)前測試用例集的所有測試用例，直接利用待擴(kuò)展參數(shù)的所有取值對測試用例集的所有測試用例逐一擴(kuò)展，使得新的測試用例包含的參數(shù)個(gè)數(shù)比之前的測試用例多一個(gè)。

直接擴(kuò)展保證了完全覆蓋性，增加參數(shù)時(shí)利用該參數(shù)的所有取值情況對上一步得到的測試用例集逐一擴(kuò)展，擴(kuò)展該參數(shù)后，由已擴(kuò)展參數(shù)組成的所有三三組合對均包含在測試用例集中，而且測試用例之間可能重復(fù)包含部分三三組合對，因此需要再進(jìn)行循環(huán)約減過程來進(jìn)一步找到局部最小測試用例集。

循環(huán)約減過程：直接擴(kuò)展后的測試用例集中可能存在大量可以約減的測試用例，判斷測試用例能否約減的依據(jù)是該測試用例包含的所有三三組合對是否都被其它測試用例包含。遍歷直接擴(kuò)展后得到的測試用例集中的每個(gè)測試用例，若可以約減則從測試用例集中刪除，循環(huán)上述過程，直到循環(huán)前后測試用例集大小不變[11]。

循環(huán)約減保證了局部最優(yōu)性，每次循環(huán)約減后的測試用例集是包含已擴(kuò)展參數(shù)的局部最優(yōu)解，并作為擴(kuò)展下一個(gè)參數(shù)的初始測試用例集，重復(fù)以上過程當(dāng)擴(kuò)展完所有參數(shù)并循環(huán)約減后得到的測試用例集即為全局近似的最優(yōu)解。

如圖1所示，SCR算法求解過程中需要輸入?yún)?shù)集X={x1,x2,…,xn}， X含有n個(gè)參數(shù)(n不小于3)，SCR算法輸出測試用例集Ts。

圖2舉例說明了SCR算法求解4個(gè)2值參數(shù)SUT的具體過程，以下將結(jié)合SCR算法描述具體分析求解過程，以便進(jìn)一步說明SCR算法的基本思路。

圖1 SCR算法描述

圖2 SCR算法求解4個(gè)2值參數(shù)SUT過程

算法首先將測試用例集Ts初始化為空(line 1)，在調(diào)整參數(shù)集X順序,使得X中前3個(gè)參數(shù)的取值數(shù)最少(line 2)，并利用X中前3個(gè)參數(shù)x1、x2、x3的所有組合加入Ts(line 3)，得到的結(jié)果如圖2(a)所示。

接著在Ts中的每個(gè)測試用例添加x4，使之?dāng)U展成新的Ts(lines 6-11)，因?yàn)閤4有兩種取值，此前Ts規(guī)模為8，故擴(kuò)展之后的Ts包含16個(gè)測試用例。對于第一個(gè)測試用例(a,c,e)，應(yīng)該擴(kuò)展為(a,c,e,*)，因?yàn)閤4可以是g或h，故(a,c,e)被擴(kuò)展為(a,c,e,g)和(a,c,e,h)，將擴(kuò)展后的測試用例添加到Ts，并將被擴(kuò)展的測試用例刪除，得到最終的結(jié)果如圖2(b)所示。

最后循環(huán)約減Ts，遍歷直接擴(kuò)展后的Ts中所有的測試用例t(line 18)，如果t中是否包含只有t覆蓋的三三組合對，則t不可約減，Ts不變(line 22)，否則t可約減，將t從Ts中刪除(line 24)，循環(huán)對Ts進(jìn)行約減處理，直到在約減前后Ts中測試用例數(shù)量不減少(line 16)。對于第一條測試用例(a,c,e,g),包含的三三組合對有(a,c,e)、(a,c,g)、(a,e,g)、(c,e,g)，而這些三三組合還分別被Ts中測試用例(a,c,e,h)、(a,c,f,g)、(a,d,e,g)、(b,c,e,g)包含，因此測試用例(a,c,e,g)可以被約減。對Ts中每個(gè)測試用例重復(fù)第一條測試用例的操作，可知(a,c,e,g)、(a,c,f,h)、(a,d,e,h)、(a,d,f,g)、(b,c,e,h)、(b,c,f,g)、(b,c,f,h)、(b,d,e,g)、(b,d,f,h)均可被約減，且此時(shí)Ts中的測試用例都不能被約減，即循環(huán)約減結(jié)束，則最終得到的結(jié)果如圖2(c)所示。

4 實(shí)驗(yàn)驗(yàn)證

SCR算法使用貪心策略逐個(gè)地尋找局部最優(yōu)解，在尋找添加下一個(gè)待擴(kuò)展參數(shù)之后的局部最優(yōu)解時(shí)，以當(dāng)前局部最優(yōu)解為基礎(chǔ)，并利用待擴(kuò)展參數(shù)的所有取值直接擴(kuò)展，再循環(huán)約減得到添加下一個(gè)參數(shù)之后的局部最優(yōu)解，直到找到所有參數(shù)都被擴(kuò)展后的局部最優(yōu)解，這個(gè)局部最優(yōu)解近似地代替全局最優(yōu)解。

本文最后通過Java編程語言在Eclipse編程工具下實(shí)現(xiàn)了SCR算法[12]，在搭載了Intel(R) Core(TM) i5-7500 處理器，8G內(nèi)存的64位Windows 10的操作系統(tǒng)的臺式機(jī)上進(jìn)行了如下實(shí)驗(yàn)，為充分比較算法的有效性，還從http://ranger.uta.edu/～ylei/fireeye/下載了FireEye開源工具，F(xiàn)ireEye工具實(shí)現(xiàn)了IPOG算法等多種逐參數(shù)擴(kuò)展的方法，F(xiàn)ireEye工具重新命名為ACTS，以下實(shí)驗(yàn)中用ACTS來進(jìn)行表示。此外還有C語言編寫的開源工具Jenny，同樣地，從http://www.burtleburtle.net./bob/math/jenny.html下載了Jenny工具進(jìn)行實(shí)驗(yàn)比較。

表3和圖3展示了具有3～10個(gè)2值參數(shù)的SUT，SCR算法生成的結(jié)果規(guī)模與時(shí)耗，含有3個(gè)或3個(gè)以上的2值參數(shù)的系統(tǒng)滿足三三覆蓋的測試用例數(shù)量至少是23=8，因此在表3中3個(gè)、4個(gè)參數(shù)的系統(tǒng)的最終解即最優(yōu)解，隨著參數(shù)個(gè)數(shù)的增加，最終解偏離了最優(yōu)解，但隨著參數(shù)個(gè)數(shù)的增加，測試用例數(shù)量增加慢，測試用例的增長趨勢大致成線性趨勢增長，而不是指數(shù)趨勢增長。

表4和圖4展示了具有4個(gè)2值到7值參數(shù)的SUT，SCR算法生成的結(jié)果規(guī)模與時(shí)耗，含有3個(gè)或3個(gè)以上的2值參數(shù)系統(tǒng)滿足三三覆蓋的測試用例數(shù)量至少是23=8，在表4中4個(gè)2值參數(shù)的最終解即最優(yōu)解，隨著參數(shù)取值個(gè)數(shù)的增加，最終解偏離了最優(yōu)解，隨著參數(shù)個(gè)數(shù)的增加，測試用例數(shù)量增加較快，測試用例的增長趨勢大致成指數(shù)趨勢增長。

表3 3～10個(gè)2值參數(shù)結(jié)果

圖3 測試用例數(shù)量與2值參數(shù)個(gè)數(shù)曲線

結(jié)果參數(shù)取值數(shù)量234567大小840120272520888時(shí)間0.1230.1760.6340.8822.0524.673

圖4 測試用例數(shù)量與參數(shù)取值個(gè)數(shù)曲線

表5和圖5展示了具有5-15個(gè)5值參數(shù)的SUT，SCR算法和基于蟻群算法的ACO算法結(jié)果規(guī)模的比較，ACO算法在求解過程中利用信息素能迅速得到結(jié)果，SCR算法采用循環(huán)約減的方式運(yùn)行時(shí)間長，測試用例集規(guī)模小。

表5 5～15個(gè)5值參數(shù)生成結(jié)果比較

圖5 SCR算法與ACO算法比較

表6展示了不同系統(tǒng)下各種算法的結(jié)果，其中工具ACTS有多種策略，對于此實(shí)驗(yàn)，IPOG算法生成結(jié)果較好，選擇ACTS中IPOG算法生成的結(jié)果進(jìn)行比較(實(shí)驗(yàn)系統(tǒng)：25314151表示5個(gè)2值參數(shù)，1個(gè)3值參數(shù)，1個(gè)4值參數(shù)和1個(gè)5值參數(shù)組成的系統(tǒng))。

綜合以上結(jié)果，可以看出SCR算法生成的三三組合測試用例集規(guī)模小，且方法簡單只包含直接擴(kuò)展和循環(huán)約減的過程，能逐個(gè)添加參數(shù)并輸出測試用例，隨著參數(shù)的增多測試用例集規(guī)模變大，在測試時(shí)可以給測試人員提供參考，根據(jù)測試成本與測試需求選擇合理的參數(shù)規(guī)模。

表6 3種方式生成的結(jié)果比較

5 結(jié)束語

本文提出了以貪心算法為基礎(chǔ)，逐參數(shù)生成測試用例的簡單循環(huán)約減的三三組合測試用例生成算法(SCR算法)。此方法先生成包含3個(gè)參數(shù)的最小測試用例集，再進(jìn)行直接擴(kuò)展和循環(huán)約減，得到最終結(jié)果。使用直接擴(kuò)展和循環(huán)約減的方式生成測試用例集，方法簡單，結(jié)果較好，能輸出每次添加待擴(kuò)展參數(shù)的之后用例集，運(yùn)行時(shí)間比基于蟻群的三三組合測試用例集的生成方法和IPOG方法長。此外，SCR算法在求解過程中，參數(shù)的順序不同會導(dǎo)致結(jié)果有顯著的差異，因此SCR算法的時(shí)間復(fù)雜度和參數(shù)排序方面有待進(jìn)一步研究。