王吉茂，尹 平，張慧穎

（北京跟蹤與通信技術(shù)研究所，北京100094）

0 引 言

測試用例執(zhí)行優(yōu)化的研究內(nèi)容主要分兩方面:一是在一組測試用例執(zhí)行前調(diào)整測試用例的執(zhí)行順序；二是在測試用例執(zhí)行過程中動態(tài)調(diào)整未執(zhí)行測試用例的順序。執(zhí)行前調(diào)整測試用例的執(zhí)行順序是為了達到一定的測試性能指標(biāo)，目前測試領(lǐng)域研究的測試性能指標(biāo)主要包括需求的覆蓋能力、代碼的覆蓋能力、錯誤探測能力、已發(fā)現(xiàn)錯誤的等級、測試耗費等，然而卻缺少對多個測試用例的執(zhí)行條件和期望結(jié)果之間聯(lián)系的研究，導(dǎo)致測試執(zhí)行時冗余操作增多；另外，按照測試?yán)碚摰腜areto原則，80%的軟件問題很可能集中在20%的程序模塊中，在測試過程中提前執(zhí)行與存在缺陷的軟件模塊相關(guān)的測試用例能夠更加全面、集中地暴露軟件問題，但目前缺少度量測試用例之間聯(lián)系的方法以及基于這種度量的動態(tài)調(diào)整算法。因此，本文從測試用例執(zhí)行條件和期望結(jié)果的關(guān)系入手設(shè)計了測試用例執(zhí)行前優(yōu)化算法，定義了測試用例距離的概念和計算方法并基于測試用例距離設(shè)計了執(zhí)行中動態(tài)調(diào)整算法。

1 相關(guān)概念及工作

測試用例的執(zhí)行優(yōu)化是對已有測試用例按照某種特定的順序執(zhí)行，從而達到某些性能指標(biāo)的調(diào)度過程[1]，其具體的定義為[2]:對于某些測試套T，PT表示對T中元素所有可能的排列的集合；f表示應(yīng)用于PT中每種排序的評價函數(shù)，輸出的是每種排序的判定值，值越高效果越好。測試用例執(zhí)行優(yōu)化就是尋找一個T＇∈PT，使得對于任意T＇∈PT，都有f（T＇）≥f（T＇）。

1.1 測試用例執(zhí)行前的優(yōu)化算法概述

Rothermel等研究人員首先將測試用例集按照對代碼的覆蓋能力進行排序[3]，然后分別使用排序前后的測試用例進行實際測試，對比測試效果，實驗結(jié)果證明為測試用例設(shè)置優(yōu)先級并排序能夠提高測試中錯誤檢測的速度和效率[4]。

在考慮代碼覆蓋能力方面，最著名的是基于MC／DC（modified condition／decision coverage）覆蓋準(zhǔn)則的排序研究。關(guān)于MC／DC的定義及基于MC／DC提出的測試用例優(yōu)先級算法可以參見文獻[5]。

對于該方法，Elbaum等認為其只考慮了覆蓋因素和出現(xiàn)頻率，而忽略了工程實踐中的測試耗費問題[6]。在這個基礎(chǔ)上，他們提出了綜合考慮測試耗費和錯誤嚴(yán)重程度的測試用例優(yōu)先級排序方法[7]，在之前覆蓋率標(biāo)準(zhǔn)上增加了對測試開銷的考慮，優(yōu)先級比較的標(biāo)準(zhǔn)改為單位覆蓋消耗比率，同時結(jié)合錯誤嚴(yán)重程度重新評估測試用例的潛在探錯能力。

測試用例執(zhí)行前的排序還可以依據(jù)其錯誤探測能力來排序，可以將錯誤探測能力定義為發(fā)現(xiàn)錯誤的數(shù)量。采用基本貪心算法將測試用例按照錯誤探測能力從大到小排序，然后依次執(zhí)行直到所有的錯誤都被探測出來。額外貪心算法則是在每次取用測試用例的時候，根據(jù)剩下的未被探測出來的錯誤動態(tài)更新測試用例的探錯能力，再采用貪心策略選用測試用例。之所以要設(shè)計額外貪心策略，是由于基本貪心策略會選擇到不必要的測試用例，但額外貪心策略容易陷入局部最優(yōu)。

依據(jù)錯誤探測能力，還可以利用啟發(fā)式方法來對測試用例進行排序。較典型的有爬山算法。作為深度優(yōu)先搜索的一種改進，爬山算法利用反饋信息幫助生成解的決策，是一種局部搜索算法。該算法的優(yōu)點在于不必進行遍歷，通過只選擇部分節(jié)點來提高效率，缺點在于不能全局搜索，容易陷入局部最優(yōu)。

北京系統(tǒng)工程研究所的楊廣華、包陽等人研究了基于需求的測試用例優(yōu)先級排序算法，包括對首次測試和回歸測試的測試用例的優(yōu)先級排序。

首次測試的優(yōu)先級排序可以分為根據(jù)需求的優(yōu)先級RP（requirement priority）排序、需求變更情況RM （requirement modify）排序、實現(xiàn)復(fù)雜度 （implementation complexity）排序。其中根據(jù)需求的優(yōu)先級排序是由于按這種方式排序可以提高測試的效益，因為據(jù)統(tǒng)計，用戶經(jīng)常使用的軟件功能只占該軟件所有功能的40%左右；按照需求變更情況來排序是由于需求的變更是引入軟件缺陷的一個重要原因，而在軟件完成之前平均有25%的需求會發(fā)生變更；另外，復(fù)雜程度較高的軟件模塊通常存在較多的缺陷，因此重點測試復(fù)雜程度較高的軟件模塊能提高發(fā)現(xiàn)軟件缺陷的效率。

回歸測試用例優(yōu)先級排序考慮之前測試發(fā)現(xiàn)軟件缺陷的情況，根據(jù)檢測到不同缺陷嚴(yán)重性等級對測試用例的錯誤探測能力進行賦值，然后根據(jù)賦值情況提高缺陷探測能力較高的測試用例的優(yōu)先級。

1.2 測試用例執(zhí)行中的優(yōu)化算法概述

除了可以在測試用例執(zhí)行之前對其進行優(yōu)化排序，還可以在測試用例執(zhí)行中對未執(zhí)行測試用例的執(zhí)行順序進行動態(tài)調(diào)整，以達到在短時間內(nèi)高效測試的目的。

戴如昕、顧春華研究了通過調(diào)整測試用例的執(zhí)行順序的測試用例優(yōu)先級方法[8]。這種方法首先根據(jù)測試用例可能暴露的錯誤類型建立一個關(guān)系矩陣R。根據(jù)矩陣R，測試用例被其可能暴露的錯誤類型分成不同的組，然后該方法調(diào)用Escalate（提高算法）和Deescalate（降低算法）來調(diào)整用例的優(yōu)先級。在這兩種算法中都有一個輸入?yún)?shù)a來確定優(yōu)先級的調(diào)整幅度。在實際執(zhí)行中，如果某個測試用例暴露了軟件問題，說明軟件在這方面存在隱患，提前執(zhí)行同組的同類型測試用例，從而有助于更高效地發(fā)現(xiàn)此問題的各個方面。

在測試用例執(zhí)行過程中，根據(jù)實時反饋的信息 （主要是未完成的測試目的或未覆蓋的測試需求），將剩余的測試用例不斷地進行順序調(diào)整。當(dāng)返回多個反饋信息時，這種調(diào)整還可以不是單隊列的，而是在并行的情況下進行多個測試用例隊列同時調(diào)整[9]。并行調(diào)整可以增加調(diào)整系統(tǒng)對反饋信息的容納能力，避免了單隊列出現(xiàn)反復(fù)調(diào)整的情況，但多隊列增加了算法的復(fù)雜度。

2 測試路徑控制陣列

為了能夠兼顧測試用例執(zhí)行前和執(zhí)行中的優(yōu)化算法，本文首先提出測試用例的組織模型:測試路徑控制陣列（test path control array，TPCA）。下面對該模型進行說明

式 （1）可簡寫為

C、V、R、O均是m×n的陣列 （并非矩陣），表示針對同一個被測功能項的m個測試用例的數(shù)據(jù)。

C為輸入控制陣列，其每一行表示一個測試用例的輸入控制量，輸入可以包括軟件當(dāng)前狀態(tài)、將要發(fā)生的事件和參數(shù)取值。C中的元素cij表示第i個測試用例的第j個輸入控制量，取值為0或1。cij取值為0表示V中的輸入vij狀態(tài)值無效、事件不發(fā)生或參數(shù)取值無效，取值為1表示V中的輸入vij狀態(tài)值有效、事件發(fā)生或參數(shù)取值有效。

V為輸入陣列，其每一行表示一個測試用例的輸入值，每個測試用例最多有n個輸入值。vij可以表示一個狀態(tài)值、事件 （0為不發(fā)生、1為發(fā)生）、輸入?yún)?shù)的具體取值。

R為期望結(jié)果控制陣列 （或輸出控制陣列），其每一行表示一個測試用例的輸出控制量，輸出可以包括測試用例執(zhí)行后軟件預(yù)期狀態(tài)、預(yù)期發(fā)生的事件和參數(shù)取值。R中的元素rij表示第i個測試用例的第j個輸出控制量，取值為0或1。rij取值為0表示O中的輸出oij狀態(tài)值無效、事件不發(fā)生或參數(shù)值無效，取值為1表示O中的輸出oij狀態(tài)值有效、事件發(fā)生或參數(shù)取值有效。

O為輸出陣列，其每一行表示一個測試用例的輸出值，每個測試用例最多有n個輸出值。當(dāng)R中的rij＝1且rij表示輸出參數(shù)控制量時，oij為第i個測試用例的第j個輸出參數(shù)的取值。vij可以表示一個狀態(tài)值、事件 （0為不發(fā)生、1為發(fā)生）、輸出參數(shù)的具體取值。

3 測試用例執(zhí)行前優(yōu)化算法

3.1 算法說明

在執(zhí)行一個測試用例前通常要對軟件的運行環(huán)境、狀態(tài)、參數(shù)等進行初始化設(shè)置，而測試用例執(zhí)行結(jié)束后會產(chǎn)生執(zhí)行結(jié)果。兩個測試用例，其輸入條件和輸出結(jié)果之間可能存在下面定義的情況。

定義1 設(shè)A、B為兩個測試用例，A.Conditions表示A執(zhí)行前的輸入條件，A.Results表示A執(zhí)行后的輸出和軟件狀 態(tài)的變化，B同理。若存在｛A.Results｝∩｛B.Conditions｝≠ ，則稱為創(chuàng)造場景條件｛A.Results｝∩｛B.Conditions｝而進行的操作為重復(fù)操作。

定義2 N｛A.Results｝∩｛B.Conditions｝為執(zhí)行測試用例B所需的輸入條件中，測試用例A在執(zhí)行后能為其產(chǎn)生的、測試人員無須進行重復(fù)輸入的操作步驟數(shù)，稱為操作重復(fù)度。

操作重復(fù)度定量描述了測試用例之間的聯(lián)系。操作重復(fù)度不為零的兩個測試用例在執(zhí)行順序上應(yīng)該被安排在相鄰的位置。尤其是針對運行狀態(tài)眾多，各狀態(tài)轉(zhuǎn)換關(guān)系復(fù)雜的軟件，需要設(shè)計一種算法來尋找操作重復(fù)度之和最大的測試用例執(zhí)行順序，該問題建模如下:

設(shè)X＝｛Xi｜i＝1……n｝是測試用例的集合，且對于任意測試用例Xi、Xj，二者之間的操作重復(fù)度N｛Xi.Results｝∩｛Xj.Conditions｝已知，求 X中測試用例的一個排序，該排序滿足操作重復(fù)度之和最大，即

這個排序問題可以轉(zhuǎn)化為圖論中尋找?guī)?quán)有向圖G（X，E）遍歷所有節(jié)點的最大路徑問題，其中X中的測試用例是有向圖中的節(jié)點，E是權(quán)值為N｛Xi.Results｝∩｛Xj.Conditions｝的邊的集合。如果某個測試用例執(zhí)行條件或期望結(jié)果與其他測試用例沒有聯(lián)系，則設(shè)其對應(yīng)邊權(quán)值為0，但仍認為該邊存在。因此G （X，E）可以視為一個有向完全圖。

圖論中解決有向圖節(jié)點排序 （即有向圖活動規(guī)劃）的方法有AOV網(wǎng)絡(luò)和AOE網(wǎng)絡(luò)。但AOV網(wǎng)絡(luò)的活動在節(jié)點上，拓撲排序僅能確定圖中是否有環(huán)，不涉及邊權(quán)值的問題；AOE網(wǎng)絡(luò)的活動在邊上，可以求解出活動節(jié)點的關(guān)鍵路徑，但并不能做到對節(jié)點的完全覆蓋[10]。因此兩種算法都不適用于測試用例排序。

雖然目前沒有現(xiàn)成的解法適用于這個問題。但實際測試中，一個測試用例執(zhí)行完成只對其他測試用例特定輸入條 件 提 供 便 利。例 如，A.Conditions＝｛a，b，c｝，B.Results＝｛b，c｝，C.Results＝｛c｝，當(dāng)B執(zhí)行后，執(zhí)行測試用例A只需要創(chuàng)造條件a即可，此時再執(zhí)行C不會給A提供任何便利。這說明一個測試用例執(zhí)行后就會給其他測試用例帶來影響，而且影響具體到某一個特定的軟件狀態(tài)，而不僅僅是狀態(tài)數(shù)量的概念。

因此，從減少操作步驟這個目的出發(fā)，以貪心策略為指導(dǎo)思想，借鑒AOV網(wǎng)絡(luò)拓撲排序中逐個取節(jié)點的方法，設(shè)計出如下有向圖節(jié)點排序算法:

首先定義數(shù)據(jù)結(jié)構(gòu)

節(jié)點 （代表測試用例）:

算法流程如圖1所示。

圖1 測試用例執(zhí)行前優(yōu)化算法

3.2 應(yīng)用驗證

以航天測控系統(tǒng)實時系統(tǒng)軟件主副機切換功能的32個測試用例為優(yōu)化排序的對象。

在經(jīng)3.1節(jié)算法優(yōu)化前，測試用例按照編號從小到大的順序執(zhí)行。經(jīng)3.1節(jié)優(yōu)化后，測試用例執(zhí)行順序為4、16、2、8、14、0、18、24、30、19、25、31、3、9、15、1、7、13、17、23、29、5、11、21、27、10、6、20、12、26、22、28。優(yōu)化排序使當(dāng)前測試用例期望結(jié)果中軟件的狀態(tài)與下一個測試用例執(zhí)行所需的輸入條件十分接近，冗余操作明顯減少。

在假設(shè)32個測試用例全部執(zhí)行通過的情況下，本文統(tǒng)計了所有測試用例的總步驟數(shù)、測試用例按0到31順序執(zhí)行省去的步驟數(shù)以及經(jīng)優(yōu)化排序后省去的步驟數(shù)，優(yōu)化效果見表1。

表1 優(yōu)化效果

4 測試用例執(zhí)行中動態(tài)調(diào)整算法

4.1 算法說明

本算法基于測試用例距離，因此首先給出測試用例距離的定義，用以衡量測試用例的相似程度。

定義3 測試用例距離dij

其中，λk表示第k個參數(shù)賦值的權(quán)重系數(shù)，視測試結(jié)果對該輸入的敏感程度由測試人員來確定。沒有賦值操作或者該參數(shù)值對測試結(jié)果沒有影響的測試用例，該值為0。

cij和vij來源于測試路徑控制陣列中的C陣列和V陣列；v＇ij是通過對輸入?yún)?shù)vij歸一化得到的，歸一化方法為:由于輸入?yún)?shù)vij的取值范圍可以被劃分成若干個等價類，一個等價類的數(shù)值范圍可能很大，例如，如果在等價類[1，10000]中vij＝2或vij＝9999時軟件的執(zhí)行結(jié)果沒有差異，則定義當(dāng)vij取值來自于同一個有效類的時候，v＇ij取值為同一個正整數(shù)q；同理，當(dāng)vij取值來自于同一個無效類的時候，v＇ij取值為同一個負整數(shù)p；當(dāng)vij取值為邊界值時，v＇ij取值為0。

當(dāng)測試用例i檢測到軟件問題時，定義測試用例i為目標(biāo)測試用例。給定測試用例距離d，如果dij＜d，則認為測試用例j與i屬于相關(guān)測試用例，測試用例j應(yīng)被提前執(zhí)行。d通常由經(jīng)驗值給出。

對于一個給定的d，可能存在多個測試用例與目標(biāo)測試用例是相關(guān)測試用例，但這些測試用例與目標(biāo)測試用例的測試用例距離可能不同。相關(guān)性較強的測試用例應(yīng)當(dāng)優(yōu)先執(zhí)行，即按照測試用例距離遞增的順序調(diào)整，其具體實現(xiàn)流程如圖2所示。

4.2 應(yīng)用驗證

這里仍以實時系統(tǒng)軟件的主副機切換功能的測試用例來驗證上節(jié)的算法對測試用例執(zhí)行順序的動態(tài)調(diào)整效果。

在API請求切換程序模塊中設(shè)置一個軟件缺陷，使API請求不能成功切換主副機。與缺陷有關(guān)的測試用例集合為｛0，2，4，6，8，16，18，20，22｝。

圖2 基于距離的動態(tài)調(diào)整算法流程

按照3.2節(jié)優(yōu)化后的測試用例執(zhí)行順序執(zhí)行32個測試用例。在執(zhí)行測試用例4時，該測試用例不通過，現(xiàn)象為:在自動模式、主副機均運行的情況下，被測軟件不能實現(xiàn)通過API請求將運行機從主機切換到副機。

用基于測試用例距離的動態(tài)調(diào)整算法對未執(zhí)行測試用例排序。現(xiàn)在，目標(biāo)測試用例為測試用例4，按照式 （3）給定測試用例距離閾值d＝1.8，自動模式、API請求的權(quán)重為3，其他輸入的權(quán)重為0.25，通過程序?qū)ふ遗c目標(biāo)測試用例的測試用例距離小于1.8的測試用例。

算法程序找到了10個測試用例｛4，8，6，0，2，20，24，22，16，18｝，雖然多出一個測試用例24，但包含了與缺陷相關(guān)的測試用例，并且優(yōu)化算法把與缺陷相關(guān)的測試用例6、20、22提前到前10位執(zhí)行。

5 結(jié)束語

本文在研究現(xiàn)有的測試用例執(zhí)行優(yōu)化方法的基礎(chǔ)上，首先提出測試路徑控制陣列模型來組織測試用例；然后從圖論角度出發(fā)提出測試用例執(zhí)行前的優(yōu)化排序算法；最后提出了測試用例距離的概念和計算方法，并基于測試用例距離提出測試用例執(zhí)行中動態(tài)調(diào)整算法。將以上兩個算法應(yīng)用于實時系統(tǒng)軟件主副機切換功能的測試用例中，優(yōu)化結(jié)果表明，執(zhí)行前優(yōu)化排序算法能夠減少一組測試用例的冗余操作，執(zhí)行中動態(tài)調(diào)整算法能夠找到與軟件缺陷相關(guān)的測試用例并將其執(zhí)行順序提前。

[1]JIANG Shanshan，ZHAO Zhonghua，WANG Qiming，et al.A requirement－based approach to system－level black－box test case prioritization[J].Computer and Digital Engineering，2010，38（5）:68－73 （in Chinese）.[姜姍姍，趙中華，王啟明，等.基于需求的系統(tǒng)級黑盒測試用例優(yōu)先化方法[J].計算機與數(shù)字工程，2010，38 （5）:68－73.]

[2]Moisiadis F.Prioritizing test cases and scenarios[C]／／37th International Conference on Technology of OO Languages and Systems，2000:108－119.

[3]Wong We，Horgan JR，London S，et al.A study of effective regression testing in practice[C]／／Proceedings of the 8th IEEE International Symposium on Software Reliability Engineering.Washington IEEE Computer Society，1997:264－274.

[4]Rothermel G，Untch H R，Chu C，et al.Test case prioritization:An empirical study[C]／／Proceedings of the International Conference on Software Maintnance.Washington:IEEE Computer Society，2001:179－188.

[5]LU Dezhong.Research for modified condition／design test case priorty algorithm[J].Science and Engineer，2009，9 （14）:4040－4044 （in Chinese）.[盧德忠.基于 MC／DC的測試用例優(yōu)先級 算 法 研 究[J].科 學(xué) 技 術(shù) 與 工 程，2009，9 （14）:4040－4044.]

[6]Elbaum S，Malishevsky G，Rothermel G.Incorporating varying test costs and faults verities into test case prioritization[C]／／Proceedings of the International Conference on Software Engineering，2001:329－338.

[7]QU Bo，NIE Changhai，XU Baowen.Survey of test case priori tization for regression testing[J].Journal of Frontiers of Computer Science and Technology，2009，3 （1）:225－233 （in Chinese）.[屈波，聶長海，徐寶文.回歸測試中測試用例優(yōu)先級技術(shù)綜述[J].計算機科學(xué)與探索，2009，3 （1）:225－233.]

[8]DAI Ruxin，GU Chunhua.Advanced test case prioritization for black box testing[J].Computer Engineering and Design，2010，31 （20）:4343－4346 （in Chinese）.[戴如昕，顧春華.用于黑盒測試的測試用例優(yōu)先級改進算法[J].計算機工程與設(shè)計，2010，31 （20）:4343－4346.]

[9]QU Bo，XU Baowen，NIE Changhai.A dynamic prioritization method for supplemental test cases[J].Journal of Shandong University，2009，39 （2）:137－140 （in Chinese）.[屈波，徐寶文，聶長海.補充生成測試用例的優(yōu)先級設(shè)定與動態(tài)調(diào)整算法[J].山東大學(xué)學(xué)報，2009，39 （2）:137－140.]

[10]WANG Guiping，WANG Yan，REN Jiachen.Algorithm，implementation and application of graph theories[M].Beijing:Press of Peking University，2011:63－82 （in Chinese）.[王桂平，王衍，任嘉辰.圖論算法理論、實現(xiàn)及應(yīng)用[M].北京:北京大學(xué)出版社，2011:63－82.]