基于OTT策略的可變力度組合測試用例優先級排序方法

，， ，，

(1.浙江理工大學 信息學院, 杭州 310018; 2.山口大學 東亞研究科, 日本 山口 753-8513)

0 引言

組合測試已廣泛應用于軟件測試中，該方法能夠縮減測試用例的規模[1]。由于軟件產品更新換代的頻率逐漸上升，對組合測試用例進行完全測試的成本不斷增加[2]。針對此問題，將優先級技術[3-4]引入到組合測試內，能夠在軟件測試過程中，提高測試效率。Kuhn等人[5]發現組合測試中，兩個參數相互組合所生成的用例可以檢測出70%的錯誤，90%以上的錯誤可由三個以內參數相互組合找出。圍繞組合測試用例優先級排序問題已有相應研究：Bryce等人[6]利用單一組合覆蓋信息實現組合測試用例的排序問題；黃如兵等[7]從多重組合覆蓋情況角度保證測試的有序進行；王子元等[8]提出了以組合權重和測試代價為標準的組合測試用例優先級排序的方法。

目前，針對可變力度的組合測試用例優先級排序方法的研究仍然較少，排序過程中組合力度選取困難，且當前固定力度組合測試用例的優先級排序方法無法滿足復雜的交互關系，因此結合局部組合覆蓋率、測試用例失效率和測試用例的重要程度，避免優先級排序因素單一；利用測試過程中的反饋信息，實現優先級在線排序；本文提出了一種基于OTT策略思想的可變力度組合測試用例優先級在線排序方法。

1 優先級排序因素

待測軟件系統(Software Under Test，SUT)中，組合測試內部影響因子的相互關系并非完全一致，部分影響因子之間的相互作用可能更加緊密[9]，僅依靠固定力度的組合測試優先級排序方法無法滿足影響因子之間這種復雜的交互關系。假設存在n個影響因素，這些影響因子構成一個有限集合F={f1,f2,…fn}，其中每個影響因素fi的取值為vi={p1,p2,…pj}。那么，SUT的一條測試用例tc={x1,x2,…xn}(x1∈v1,x2∈v2,…xn∈vn)。為了更好地描述可變力度組合測試用例優先級排序方法，對本文出現的相關概念進行如下描述：初始測試用例序列St0表示組合測試用例排序之前，測試用例序列的集合，一般為φ。初始測試用例集Tt0={tc1,tc2,…tcN}是針對SUT，根據組合測試方法及可變強度覆蓋表VSCA(N,λm,n,F,CA(N′,λs,n′,F′))生成的測試用例集合。顯然，1≤λm<λs≤|F′|

可變力度的組合測試用例優先級中，需考慮組合覆蓋率的影響。然而，如何在影響因子集下選取一個合適的組合力度作為衡量組合覆蓋率的標準成為了難題。研究表明[7]：若選取λm為組合覆蓋力度，當覆蓋了所有λm組合后，優先級的選取演變成了隨機排序方式；若選取λs為組合覆蓋力度，則忽略了影響因子集F′中λm的組合覆蓋情況；若選取的組合覆蓋力度介于λm與λs之間，則面臨了上述兩種問題。故根據不同的組合覆蓋力度，需考慮不同局部影響因子集下組合測試用例的組合覆蓋率情況。測試用例的優先級排序中，用例的缺陷檢測能力往往是一個衡量測試執行效率的重要標準，大量研究[10-11]中也通過觀察測試執行的失效情況來評判測試用例的缺陷檢測能力。而實際測試過程中，測試人員通常需要根據需求分析或概要設計來分辨測試用例在此次測試執行過程中的重要程度。為了盡快滿足可變力度的組合覆蓋要求和缺陷的檢測能力，實現SUT設計文檔的需求，本文引入局部組合覆蓋率、測試用例失效率和測試用例重要程度這3個排序因素確定可變力度的組合測試用例的優先級問題。

1)局部組合覆蓋率(Locally-Interaction-Coverage Rate，LICR)，局部組合覆蓋率是當前時刻下測試用例在局部影響因子集中覆蓋所有λ元組合，且這些λ元組合尚未被測試用例序列覆蓋的概率。

LICR(λ,ti,F′)(tc,Sti-1)=

(1)

其中:CombSet(λ,F′)(tc)是測試用例tc在F′中覆蓋所有λ元組合的集合，UncovCombSet(λ,F′)(Sti-1)是測試用例序列Sti-1在F′中未覆蓋所有λ元組合的集合，n為F′中影響因子的個數。當F′=F時，局部組合覆蓋率LICR(λ,ti,F′)(tc,Sti-1)即為測試用例tc在ti時刻的λ元組合覆蓋率。

為了便于對局部組合覆蓋率的理解，給出圖1所示的計算實例。當前存在5個影響因子F={f1,f2,f3,f4,f5}，每個因素分別有兩種取值。St3中已經執行了三個測試用例，Tt3中余下測試用例tc1和tc2。t4時刻，λ=2時，局部影響因子集F′={f1,f3,f4,f5}分別計算LICR(2,t4,F′)(tc1,St3)和LICR(2,t4,F′)(tc2,St3)。

圖1 局部組合覆蓋率計算實例

2)測試用例失效率(test case failure rate，FR)，測試用例失效率是當前時刻下測試用例局部影響因子集F′中所有影響因子對應參數取值失效率的平均值。參數取值失效率FR(tc,ti,F′)(fk,p)是ti時刻測試用例tc在影響因子集F′中，fk對應取值為p的失效率。用m(tc,ti,F′)表示取值失效個數，即測試用例tc在局部影響因子集F′中，ti時刻參數取值失效率不為0的參數取值個數，即FR(tc,ti,F′)(fk,p)≠0的參數取值個數。那么ti時刻下，測試用例失效率FR(tc,ti,F′)計算公式如下：

(2)

其中:fk∈F′，∑FR(tc,ti,F′)(fk,p)是計算局部影響因子集F′中所有fk對應取值為p失效率之和。

表1 某組合空間配置在ti-1時刻參數取值失效率的情況

2 優先級排序因素在線調整策略

2.1 局部組合覆蓋率調整方法設計

測試過程中，測試用例序列和測試用例集中測試用例的個數不斷發生變化，使得局部組合覆蓋率也不斷發生變化。優先執行局部組合覆蓋率較大的測試用例，能夠保證盡快滿足組合覆蓋率的要求。若ti-1(i≥1)時刻所選取的測試用例為Ati-1，那么在該測試用例執行測試后，測試用例序列Sti-1和測試用例集Tti-1都發生了改變，進而得到每個測試用例在當前時刻下的覆蓋組合集CombSet和未覆蓋組合集UncovCombSet，并為下一次求解局部組合覆蓋率做準備。

其中，ti時刻的測試用例序列Sti以ti-1時刻執行的測試用例Ati-1順序插入到ti-1時刻的測試序列Sti-1的形式表示，如公式(3)所示。

Sti=Sti-1?Ati-1,Ati-1∈Tti-1

(3)

ti時刻的測試用例集Tti通過測試用例Ati-1從ti-1時刻的測試用例集Tti-1中移除得到，如公式(4)所示。

Tti=Tti-1-Ati-1,Ati-1∈Tti-1

(4)

ti時刻，未覆蓋λ元組合集UncovCombSet(λ,F′)(Sti)是通過移除測試用例Ati-1在ti-1時刻覆蓋了測試用例序列Sti尚未覆蓋的λ元組合集而得，如公式(5)所示。

UncovCombSet(λ,F′)(Sti)=UncovCombSet(λ,F′)(Sti-1)-

(UncovCombSet(λ,F′)(Sti-1)∩CombSet(λ,F′)(Ati-1)),

Ati-1∈Tti-1

(5)

每執行一個測試用例，都需要對當前測試用例序列、測試用例集和每個測試用例的局部組合覆蓋率了進行更新，執行完測試用例Ati-1后，每個測試用例的局部組合覆蓋率的計算公式如(6)所示。

LICR(λ,ti,F′)(tc,Sti)=

(6)

2.2 測試用例失效率調整方法設計

實際測試中，當前測試用例的執行結果能夠反饋出SUT存在的問題。研究表明，相同組合影響因子的參數取值引起的失效，可能隱藏了更多的錯誤，并且可以會檢測出相同或者類似的錯誤[12-13]。測試用例的執行能夠發現存在的錯誤與缺陷，那么測試用例在當前選取的局部影響因子集F′中所覆蓋的參數取值的失效率需要做出相應的調整，以保證測試用例失效率能夠實時計算，確保最終優先級排序的準確性。若ti-1(i≥1)時刻，測試用例Cti-1檢測出SUT中存在缺陷，測試結果只能反應軟件失效，但無法判斷究竟是由哪些參數相互作用引發的失效。因此，只能對Cti-1覆蓋部分影響因子集F′中所有參數取值的失效率相應增加，其他參數取值的失效率保持不變。則ti時刻，各參數取值失效率可用以下公式進行調整：

(7)

其中:Δc是一個較小的常量。

若ti-1時刻，測試用例Cti-1未檢測出SUT中存在缺陷，測試結果能夠反應出當前測試用例中所有參數取值不會對SUT造成缺陷，則該測試用例覆蓋局部影響因子集F′中所有參數取值的失效率變為0，其他參數取值的失效率保持不變。則ti時刻，各參數取值失效率可用以下公式進行調整：

(8)

為了便于對局部影響因子集F′中參數取值失效率在線調整的過程，通過以下示例對其做出解釋。參數取值失效率情況見表1。若當前測試用例tc={5,1,2,8,4}在ti-1時刻檢測出SUT中存在缺陷，測試時對應的局部影響因子集F′={f1,f3,f4,f5}，此時需要對測試用例tc覆蓋部分影響因子集F′中所有參數取值的失效率相應增加Δc,故這個組合空間配置參加取值失效率發生變化，則ti時刻參數取值失效率的情況如表2；同理，若tc未檢測出缺陷，相應參數取值失效率變為0即可。

表2 某組合空間配置在ti時刻的參數取值失效率情況

3 組合測試用例優先級排序方法分析

3.1 OTT基本算法框架

在組合測試過程中，由于OTT策略高效、簡單、便于擴展等特點[14]，使得該策略在組合測試中得到了廣泛的應用，其在組合測試用例優先級排序中的作用也不容忽視。張娜等人[15]在固定力度組合測試用例優先級排序算法中，結合了OTT策略，使得排序后的測試用例具有更強的缺陷檢測能力。為此，有必要進一步對OTT策略在可變力度的組合測試用例優先級排序中的應用進行研究。Cohen等人[16]在組合測試的研究中，利用OTT策略構建了Greedy算法的框架。該策略為一維擴展機制，本文結合該策略構建了可變力度組合測試用例優先級排序的算法框架，即每次選取當前優先級最高的測試用例用于執行。本文OTT策略的可變力度組合測試用例優先級排序算法框架流程圖見圖2。

圖2 OTT策略基本算法框架流程圖

3.2 優先級排序方法設計

隨著軟件版本更新升級速度的提升，對測試效率的要求也隨之增高。由于資源時間等的限制，目前的情形無法達到完全測試的目標，那么如何選取測試用例用于執行、測試用例的執行順序顯得尤為重要。本文結合OTT策略將可變力度的組合測試用例優先級排序方法轉換成綜合考慮多個優先級排序影響因素共同計算優先級、每次選取當前優先級最高的用例用于執行的問題。為了盡快滿足可變力度組合測試在不同影響因子集下的組合覆蓋率，盡可能選取局部組合覆蓋率較高的測試用例；同時，提高缺陷檢測的能力，要求優先考慮測試用例失效率較高的測試用例；并且，測試用例的設計和生成過程中，本身存在一定的優先級，測試人員可結合需求設計文檔或憑借測試經驗，給組合測試用例賦予一定的重要程度。那么，不同參數取值的重要程度本身存在差異，使用參數取值重要程度的加權平均值作為測試用例重要程度的計算。根據OTT策略基本算法框架擴展組合測試用例優先級排序算法，每次選擇出當前優先級最高的測試用例。測試用例重要程度I(tc,F′)是測試用例tc的重要程度，即測試用例在局部影響因子集F′所有影響因子對應取值權重的平均值。參數取值重要程度ω(fk,p)是影響因子fk中，取值為p的重要程度。

那么，測試用例tc在ti時刻的優先級Pr由測試用例的局部組合覆蓋率、測試用例失效率和測試用例重要程度這三個排序因素共同決定，并利用權重因子，以便不同測試環境下對這三個排序因素比重做出相應調整，保證該方法能夠廣泛的用于軟件測試中。優先級計算方法如下所示：

Pr(tc,ti)=α·LICR(λ,ti,F′)(tc,Sti-1)+

β·FR(tc,ti,F′)+γ·I(tc,F′)

(9)

其中:α、β、γ分別表示局部組合覆蓋率、測試用例失效率和測試用例重要程度的權重因子，實際測試過程中可根據具體情況相應調整，只有保證α+β+γ=1即可。測試用例的重要程度使用每個參數取值重要程度的平均值進行計算。通過上述公式的描述，測試用例tc在ti時刻的優先級Pr(tc,ti)實際可以表示成如下形式：

Pr(tc,ti)=

(10)

其中:fk∈F′，n為F′中影響因子的個數，∑ω(fk,p)是計算計算局部影響因子集F′中所有fk對應取值為p重要程度之和。

測試用例tc在ti時刻優先級Pr計算過程中，還應當考慮當前影響因子集如何選取的問題，此問題是可變力度的組合測試用例優先級計算時必須著重討論的。ti時刻，當所有λm元組合還未被測試用例序列Sti-1所覆蓋時，考慮影響因子集F上λm元的組合覆蓋率；若此時所有λm元組合均被測試用例序列Sti-1所覆蓋，則不再考慮影響因子集F上λs元組合覆蓋情況，而是僅考慮影響因子集F′上λs元的組合覆蓋率。

基于OTT策略的可變力度組合測試用例優先級排序算法(Variable Combinatorial Test Case Prioritization Based Strategy of One-test-at-a-time，VCPO)如下所示。

算法1:VCPO算法。

輸入：初始測試用例集Tt0，組合測試覆蓋表VSCA(N,λm,n,F,CA(N′,λs,n′,F′))。

輸出：測試用例序列Sti。

1)St0=φ;i=0;

2)while |Sti|≠Ndo//未達到測試目標

3)highest=0;

4)TestCase=φ;//當前優先級最高的測試用例集

5)R=F;λ=λm;

6)for each elemente∈(Tti\Sti)do

//e在(初始)候選測試用例集Tti中，但不在測試用例序列Sti中

7)ifR==F&&λ==λm&&UncovCombSet(λ,R)(St)≠φ

//根據測試用例序列Sti中覆蓋組合情況，選擇影響因子集和測試力度

8)R=F;λ=λm;

9)else

10)R=F′;λ=λs;

11)priority=α·LICR(λ,ti+1,R)(e,Sti)+β·FR(e,ti+1,R)+γ·I(e,R);

12)ifpriority≥highestthen

13)TestCase=φ;

14)highest=priority;

15)TestCase=TestCase∪{e};

16)end if

17)end for

18)tc=random(TestCase); //在TestCase隨機選取一個測試用例

19)執行測試用例tc;

20)iftcis false then //測試用例檢測出缺陷，按照公式(7)調整失效率

21)for each elementfk∈Rdo

22)for each elementp∈fkdo

23)ifp∈tcthen

FR(tc,ti+1,R)(fk,p)=FR(tc,ti,R)(fk,p)+Δc;

24)elseFR(tc,ti+1,R)(fk,p)=FR(tc,ti,R)(fk,p);

25)end for

26)end for

27)else //測試用例未檢測出缺陷，按照公式(8)調整失效率

28)for each elementfk∈Rdo

29)for each elementp∈fkdo

30)ifp∈tcthenFR(tc,ti+1,R)(fk,p)=0;

31)elseFR(tc,ti+1,R)(fk,p)=FR(tc,ti,R)(fk,p);

32)end for

33)end for

34)i++;

35)Sti=Sti-1?{tc}; //將測試用例tc有序插入到測試用例序列S中

36)Tti=Tti-1-{tc}; //將測試用例tc從測試用例集T中刪除

37)UncovCombSet(λ,R)(Sti)=UncovCombSet(λ,R)(Sti-1)-(UncovCombSet(λ,R)(Sti-1)∩CombSet(λ,R)(tc));

38)end while

39)returnSti;

4 實驗與總計

4.1 實驗數據與結果分析

為了驗證所述方法的有效性，選取以下兩個組合空間配置VSCA1(N,λm,8,435362,CA(N′,λs,7,435361))和VSCA2(N,λm,9,1019181716151413121,CA(N′,λs,5,6151413121))，分別采用Random、ICBP、GISVSP、LISVSP和本文所述方法對其缺陷檢測能力進行比較。由于實際測試過程中，無法執行組合測試用例集里所有的測試用例，且組合測試用例集不能檢測出SUT中所有的缺陷，故缺陷檢測能力采用文獻[17]提出的標準化的測試用例序列度量標準(NAPFD)。VSCA1和VSCA2在ACTS工具下生成的測試用例情況如表3。

表3 ACTS生成的可變力度組合測試用例集大小

對于上述方法及組合空間配置的情況，為取得適合本文組合空間配置的權重因子α、β、γ，多次實驗以調整優先級。并且在測試過程中，每組權重因子下，分別多次模擬測試，記錄每次測試的運行結果，用于計算上述方法的NAPFD值。實驗對比后，本文對α、β、γ的取值分別為0.41、0.35、0.24，且對比每種方法在實驗中NAPFD的最大值和平均值。測試過程中某個測試用例發現缺陷時，則該測試用例覆蓋影響因子集中的所有參數取值失效率需相應增加Δc，實驗中Δc的取值為0.1。ICBP方法是固定力度組合測試用例優先級排序方法，則選取不同組合力度，以觀察力度選取的影響。實驗結果如表4。

上述表中，ICBP-λ=n為ICBP方法在測試時，選擇組合力度為n的情況；下劃線、加粗為每行中最大值；下劃線、斜體為每行中次最大值；“-”為不存在的情況，無實驗數據。

從表中描述的所有實驗結果的Max和Avg可以看到，Random、ICBP方法，在可變力度組合測試的缺陷檢測能力上幾乎無任何優勢。可變力度的組合測試用例優先級排序方法中，GISVSP方法相較于LISVSP方法有更高的最大值；VCPO方法則在最大值和平均值上都占有一定優勢，且在每行的最大值和次最大值中都能夠有較高的NAPFD值，因此缺陷檢測能力相對較高。

因此可得到如下結論：

1)Random和固定力度組合測試優先級排序方法ICBP在可變力度組合測試優先級排序中不適用，原因在于無法選取合適的組合力度用于測試；

2)可變力度的組合測試用例優先級排序方法中，GISVSP方法和LISVSP方法不會面臨組合力度選取困難的問題，能夠適用于可變力度的組合測試優先級的排序，但其僅考慮組合覆蓋率的情況，排序因素單一，故缺陷檢測能力沒有表現為最優。

3)可變力度的組合測試用例優先級排序方法中，VCPO方法能夠解決組合力度選取的難題和排序因素單一的問題，使得排序結果相對穩定。實驗結果表明，該方法在大多數情況下缺陷檢測能力比其它排序方法更優。

4.2 總結

目前組合測試領域中，因實際測試中各影響因子間相對復雜的交互關系，可變力度的組合測試備受青睞，眾多研究者關注于可變力度的組合測試用例優先級排序的問題。本文提出了一種基于OTT策略的可變力度組合測試用例優先級排序方法，該方法能夠更為廣泛的適用于可變力度的組合測試中，且結合了多個排序因素，利用在線的測試反饋信息，在符合實際的測試過程的前提下，進一步提升了缺陷檢測能力。

由于測試過程中，本文提出的方法存在不夠理想的實驗結果，且α、β、γ的權重比值需人為分配，實驗中Δc的取值相對固定，后期希望能夠選取更合適的排序因素且結合自適應的方法進行在線調整權重因子和Δc的取值。

表4 五種優先級排序算法在不同組合空間配置下的NAPFD(%)