高 杰, 趙逢禹, 劉 亞

(上海理工大學(xué) 光電信息與計算機工程學(xué)院， 上海 200093)

0 引 言

軟件測試是指使用人工或自動的手段來運行或測定某個軟件系統(tǒng)的過程，其目的在于檢驗它是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實際結(jié)果之間的差別[1]，科學(xué)應(yīng)用測試方法可以盡可能地避免軟件在運行過程中出現(xiàn)各種故障問題[2]。軟件測試的核心任務(wù)之一就是構(gòu)建測試用例集。但軟件規(guī)模的擴大會導(dǎo)致測試用例集會變得復(fù)雜龐大，若對其分類和約簡，會節(jié)省測試的時間和資源消耗。因此，測試用例集的約簡旨在最大限度地減少執(zhí)行的測試用例的數(shù)量。

測試用例約簡的研究可以分為兩類，一類是基于模型的測試用例約簡[3]，如：通過構(gòu)建多優(yōu)化目標(biāo)模型，提出了不同的基于多優(yōu)化目標(biāo)的測試用例集約簡算法[4]。建模過程復(fù)雜，且該嚴(yán)重依賴于模型設(shè)計的好壞；另一類是貪心算法、啟發(fā)式算法等基于人工智能技術(shù)的測試用例約簡。由于這些算法過早收斂、優(yōu)化效率低的局限性，不斷有學(xué)者對其進行改進，如：針對傳統(tǒng)貪婪算法存在過擬合的問題，提出了一種基于貝葉斯網(wǎng)絡(luò)模型的黑匣子測試選擇方法[5]，該方法可以確保僅將黑盒測試之間的強關(guān)系用于測試選擇，達到減少測試用例冗余的目的，而且該方法對于過度擬合更為健壯。但這種算法的效果仍取決于初始的測試用例集；應(yīng)用二分K-means聚類算法對回歸測試的測試用例集約簡，以白盒測試的路徑覆蓋為準(zhǔn)則，對每個測試用例進行量化，使每個用例變成一個點[6]。以黑盒測試的功能需求數(shù)作為聚類數(shù)，在聚類結(jié)果的每一簇中，按照離中心點的距離排序，依次從每一簇中選擇測試用例，直至滿足所有測試需求，得到約簡的測試用例集。

本文認(rèn)為不論是采用模型的方法還是采用貪心、啟發(fā)式算法等方法，基于路徑覆蓋的測試用例約簡是基本的方法，為了獲取測試用例的執(zhí)行路徑，必須計算關(guān)鍵變量的狀態(tài)。此外，約簡后的測試用例集能否與原測試用例集具有相同的錯誤檢測率對測試用例約簡至關(guān)重要[7]。本文提出一種基于謂詞和關(guān)鍵狀態(tài)變量分析的測試用例約簡方法，旨在減少測試用例的冗余，提高測試效率，降低測試成本，并與原測試用例集具有相同的錯誤檢測率。

1 關(guān)鍵狀態(tài)變量

1.1 關(guān)鍵狀態(tài)變量定義

本文將影響謂詞表達式中判斷條件的變量稱為關(guān)鍵狀態(tài)變量。在程序運行過程中，程序傳遞的參數(shù)的值會影響謂詞表達式中的判斷條件，而謂詞表達式中的判斷條件的結(jié)果會影響程序運行的路徑。關(guān)鍵狀態(tài)變量包括以下3種參數(shù)：

(1) 程序運行過程中傳遞給方法的參數(shù)；

(2)程序中影響謂詞表達式中的判斷條件的輸入或讀取的成員變量；

(3) (1)、(2)中經(jīng)過一系運算之后所得到的新參數(shù)。

通過代碼來說明本文所定義的關(guān)鍵狀態(tài)變量。

代碼1關(guān)鍵狀態(tài)變量定義范例。

1.int compute(int x)

2.{

3. intd= 7;

4. if(d> 3)

5.{

6.x= 2 *x;

7. }else

8.{

9.x=x*x;

10.}

11. inta,b,c;

12.b=x/ 2;

13.a=b;

14.c=a* 3;

15. if(a!= 0)

16.{

17. return 1;

18. }

19. return 0;

20.}

在代碼1范例中，有x,a,b,c,d這5個變量，其中x是傳入的參數(shù)，a,d是謂詞判斷中的參數(shù)，而a的值是由b賦予的。因此，本文認(rèn)為x,a,b,d是關(guān)鍵狀態(tài)變量。

1.2 關(guān)鍵狀態(tài)變量獲取

本文利用抽象語法樹(Abstract Syntax Tree, AST) 來獲取關(guān)鍵狀態(tài)變量。抽象語法樹是程序源代碼的抽象語法結(jié)構(gòu)的樹狀表現(xiàn)形式。

不同的計算機高級語言都提供了抽象語法樹的處理包。本文所做的研究以C代碼為實驗對象，C語言中的gcc編譯器可以構(gòu)造抽象語法樹。

通過在程序源代碼的抽象語法樹中搜索不同的節(jié)點類型得到關(guān)鍵狀態(tài)變量。其具體步驟是：首先在抽象語法樹中找到這些節(jié)點類型，針對不同的節(jié)點類型做不同的處理，最終將滿足本文定義的所有關(guān)鍵狀態(tài)變量添加到關(guān)鍵狀態(tài)變量集合中。

2 測試用例約簡方案

測試用例集約簡的目的是去除測試用例中冗余的、無法發(fā)現(xiàn)程序缺陷的測試用例，從而減少測試成本，提高測試效率。

本文所提出的測試用例約簡方案主要有6步：

(1) 測試用例聚類。本文所提出的測試用例約簡方法與代碼執(zhí)行的路徑和關(guān)鍵狀態(tài)變量密切相關(guān)。因此，要將測試用例按其測試的功能以及輸入?yún)?shù)的參數(shù)列表聚類，聚類成若干個不同的測試用例集。

(2)查找每類測試用例集對應(yīng)的源代碼。針對聚類后的每類測試用例集，根據(jù)測試的功能與輸入?yún)?shù)的型構(gòu)確定被測程序的程序源代碼。

(3)代碼預(yù)處理。程序源代碼中的每個文件可能會有多個方法，每個方法中的局部變量可能會出現(xiàn)多次賦值和使用的情況。

例如代碼2所示的代碼中，當(dāng)程序執(zhí)行執(zhí)行到第11行的條件判斷語句時，x的值并不能確定，可能會取第5行的x，也可能會取第8行的x，即同一個變量在不同的情況下可能會被賦予不同的值。為了解決這種情況，本文對代碼進行了預(yù)處理，保證每個變量對應(yīng)一個值。

代碼2代碼預(yù)處理示例

1.int compute(intx)

2. {

3. if(x> 3)

4. {

5.x= 2 *x;

6. }else

7. {

8.x=x*x;

9. }

10. …

11. if(x> 10)

12. {

13. inty=x;

14. }

15. }

對代碼中的變量進行預(yù)處理就是針對同一變量可能會被賦予不同值的變量換成不同的變量名。代碼2中示例代碼經(jīng)預(yù)處理后的結(jié)果如代碼3所示。

代碼3代碼預(yù)處理結(jié)果示例

1.int compute(intx)

2. {

3. if(x> 3)

4. {

5.x1= 2 *x;

6. }else

7. {

8.x2=x*x;

9. }

10. …

11. if (x1> 10)

12. {

13. inty=x1;

14. }else if

15. {

16. inty=x2;

17. }

18.}

(4)基于抽象語法樹的信息提取。利用高級語言中所提供的技術(shù)構(gòu)建程序源代碼的抽象語法樹。獲取抽象語法樹中的每個節(jié)點信息，從而找到代碼中的關(guān)鍵狀態(tài)變量、關(guān)鍵狀態(tài)變量的計算表達式以及謂詞表達式中的判斷條件，并將它們分別添加到相應(yīng)的集合中。

(5)構(gòu)建測試用例關(guān)聯(lián)矩陣。測試用例集中的每個測試用例對應(yīng)測試用例關(guān)聯(lián)矩陣的一行信息，多個測試用例構(gòu)成了測試用例關(guān)聯(lián)矩陣。測試用例關(guān)聯(lián)矩陣用M表示，M矩陣中每一行對應(yīng)一個測試用例的輸入?yún)?shù)、關(guān)鍵狀態(tài)變量、關(guān)鍵狀態(tài)變量的計算表達式和謂詞表達式中的判斷條件，形式化表示為式(1)：

Mi=(ti,,,) .

(1)

其中，ti表示測試用例中第i個測試用例的輸入?yún)?shù)，V表示關(guān)鍵狀態(tài)變量的集合，E表示關(guān)鍵狀態(tài)變量的計算表達式集合，C表示謂詞表達式中的條件判斷的集合。

(6)測試用例約簡。本文采用的測試用例約簡準(zhǔn)則是：任意二個測試用例ti,tk，如果對應(yīng)的謂詞表達式中的條件判斷的邏輯值完全相同，即=，那么這二個或多個測試用例屬于同一等價類的測試用例，具有相同或相似的測試效果，可以選取其中的一個作為約簡后測試用例。

該約簡方案的整體流程框架，如圖1所示。

圖1 約簡方法流程框架

3 主要算法實現(xiàn)

在圖1所示的流程圖中，主要有二個重要的算法：

(1)在抽象語法樹中獲取關(guān)鍵狀態(tài)變量；

(2)在測試用例關(guān)聯(lián)矩陣中查找并移除等效的測試用例，實現(xiàn)測試用例約簡。

3.1 基于抽象語法樹的信息提取

任何一個C程序文件都可以轉(zhuǎn)換為抽象語法樹的樹狀結(jié)構(gòu)，任意一個包括一個變量和一個方法的C程序文件的樹形結(jié)構(gòu)，如圖2所示。利用抽象語法樹中提供的方法可以獲取樹中的各個節(jié)點。

為獲取關(guān)鍵狀態(tài)變量、關(guān)鍵狀態(tài)變量的計算表達式以及謂詞表達式中的判斷條件，需要從抽象語法樹中找到與其相關(guān)的3類節(jié)點：params節(jié)點、IfStatement節(jié)點以及ExpressionStatement節(jié)點。針對這3類不同的節(jié)點分別找出關(guān)鍵狀態(tài)變量、關(guān)鍵狀態(tài)變量的計算表達式和謂詞表達式中的判斷條件集合，并分別將其添加到相應(yīng)的集合。算法1給出了獲取關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合的算法。

圖2 抽象語法樹

算法1基于抽象語法樹的信息提取算法

輸入預(yù)處理后的程序源代碼的抽象語法樹。

輸出關(guān)鍵狀態(tài)變量集合keyVariable，關(guān)鍵狀態(tài)變量的計算表達式集合comExpression，謂詞表達式中的判斷條件集合conExpression。

(1)算法以root為根節(jié)點；

(2)初始化關(guān)鍵狀態(tài)變量集合keyVariable = null，關(guān)鍵狀態(tài)變量的計算表達式集合comExpression = null,謂詞表達式中的判斷條件集合conExpression=null，根root入隊enqueue(root)；

(3) 循環(huán)queue中的元素。取出隊首元素，如果為空，轉(zhuǎn)(8)，算法結(jié)束，否則轉(zhuǎn)(4)；

(4)如果該節(jié)點的節(jié)點類型是IfStatement，找到該節(jié)點下的表達式，并將該節(jié)點添加到謂詞表達式中的判斷條件集合conExpression中，并將該節(jié)點下的變量放入一個set集合中；

(5)如果該節(jié)點的節(jié)點類型是VariableDeclaration或者params或者Identifier，并且該變量在(4)的set中出現(xiàn)過，將該節(jié)點添加到關(guān)鍵狀態(tài)變量集合keyVariable中；

(6)如果該節(jié)點的節(jié)點類型是BinaryExpression或者CallExpression或者UnaryExpression。繼續(xù)向下判斷，若該節(jié)點包括符號“<”,“>”,“<=”,“>=”,“!=”,“==”，找到該節(jié)點下的表達式，并將該節(jié)點添加到謂詞表達式中的判斷條件集合conExpression中；若該節(jié)點包括符號“=”，找到該節(jié)點下的表達式，并將該節(jié)點添加到關(guān)鍵狀態(tài)變量的計算表達式集合comExpression中；

(7)如果該節(jié)點的節(jié)點類型不屬于以上節(jié)點，則把該節(jié)點的子節(jié)點入隊；

(8) 算法結(jié)束。

通過算法1可以獲取測試用例關(guān)聯(lián)矩陣M中的關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合。

3.2 基于測試用例關(guān)聯(lián)矩陣的約簡

3.2.1 構(gòu)建測試用例關(guān)聯(lián)矩陣

測試用例關(guān)聯(lián)矩陣的列由關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合中的每個元素組成，每個測試用例的輸入值、關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合構(gòu)成測試用例關(guān)聯(lián)矩陣的每一行，n個測試用例構(gòu)成了測試用例關(guān)聯(lián)矩陣。圖3給出了一個測試用例關(guān)聯(lián)矩陣示例。

圖3 測試用例關(guān)聯(lián)矩陣示例

構(gòu)造測試用例關(guān)聯(lián)矩陣的輸入可以概括為：測試用例集T={t1,t2,t3,…,tm}，由算法1中得到的關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合，其數(shù)學(xué)表達式為式(1)。

在圖3的示例中，t1,t2,t3,t4表示4個測試用例，每個測試用例有3個輸入?yún)?shù)：a、b、c；a1=a*2和a2=c*3表示代碼中的計算表達式；a-b>4，a1>5，a2>2則表示謂詞表達式中的判斷條件。

3.2.2 測試用例約簡算法

根據(jù)本文所提出的測試用例約簡準(zhǔn)則對測試用例關(guān)聯(lián)矩陣進行約簡，算法2給出了測試用例關(guān)聯(lián)矩陣的約簡描述。

算法2測試用例關(guān)聯(lián)矩陣中測試用例的約簡

輸入測試用例關(guān)聯(lián)矩陣M

輸出約簡后的測試用例關(guān)聯(lián)矩陣M'

(1)for eachito row // row是測試用例關(guān)聯(lián)矩陣的行數(shù)

(2) for eachj=i+ 1 to row

(3) 如果第i行和第j行的測試用例對應(yīng)的謂詞表達式中的判斷條件集合中的每一列的結(jié)果值都相同，表示第i行和第j行的測試用例具有相同或相似的功能，保留第i行的測試用例

(4) end for

(5) end for

4 實驗分析

4.1 實驗數(shù)據(jù)及評價指標(biāo)

本文選擇了西門子測試用例集中4個程序作為實驗對象來驗證本文所提出的測試用例約簡的方法。為了評估本文所提出的方法的有效性，將本文算法與傳統(tǒng)HGS算法和貪心算法(Greedy, G算法)從約簡率作對比和分析。約簡率的計算公式(2)。

(2)

其中：|OriginalTestSuite|表示原測試用例集中測試用例數(shù)量，|T*|表示約簡后測試用例集中測試用例的數(shù)量，約簡率越大則約簡程度越高。

西門子測試用例集中4個程序的程序集信息如見表1。schedule2是優(yōu)先級調(diào)度器；tcas是防止航空器空中相撞系統(tǒng)[8]；print_tokens和print_tokens2主要用于詞法分析。

表1 西門子程序集信息

4.2 實驗方案

實驗的具體方案：

(1) 按不同的功能及輸入?yún)?shù)的參數(shù)列表分別將四個開源程序中的測試用例集進行聚類，確定每一類測試用例集所對應(yīng)的程序源代碼；

(2)將對應(yīng)的程序源代碼預(yù)處理，將預(yù)處理后的源代碼轉(zhuǎn)換成抽象語法樹，再使用本文所提出的算法1獲取關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合；

(3)構(gòu)建測試用例與關(guān)鍵狀態(tài)變量集合、關(guān)鍵狀態(tài)變量的計算表達式集合以及謂詞表達式中的判斷條件集合的測試用例關(guān)聯(lián)矩陣，再計算測試用例關(guān)聯(lián)矩陣中每一項所對應(yīng)的值，最后根據(jù)測試用例約簡準(zhǔn)則對其進行約簡。

4.3 實驗結(jié)果和分析

實驗結(jié)果如圖4所示，可以看出本文所提出的算法可以有效的減少原測試用例集數(shù)量。

圖4 3種算法的測試用例約簡率

3種算法約簡后的測試用例數(shù)量見表2。

表2 約簡后測試用例的數(shù)量

通過對西門子測試用例集中4個開源程序自帶的測試用例集進行實驗，本文所提算法對每個程序中的原測試用例數(shù)量都有不同程度程度的減少，測試用例數(shù)量的約簡率還與原測試用例集中冗余測試用例數(shù)量的多少相關(guān)。

本文所提出的方法在保證測試用例集完整性的基礎(chǔ)上減少了測試用例的數(shù)量。實驗中針對約簡掉的每個測試用例都經(jīng)過了人工檢測，通過對比測試用例關(guān)聯(lián)矩陣中的測試用例，判斷測試用例關(guān)聯(lián)矩陣中存在與被約簡的測試用例的每一列對應(yīng)的值都是相同的，運行被約簡的測試用例，進一步證實了這些測試用例集確實不能檢測到程序中存在的缺陷。但本文算法涉及到的步驟相對較多，會增加計算方面的開銷。

5 結(jié)束語

測試用例的約簡是軟件測試中一項非常重要的工作，約簡測試用例可以極大地減少測試成本，因此對測試用例約簡的研究具有十分重要的意義。

本文提出一種基于謂詞分析和關(guān)鍵狀態(tài)變量的測試用例約簡方法，主要考慮了變量對測試路徑的影響，提出一種基于謂詞分析和關(guān)鍵狀態(tài)變量的測試用例約簡方法，主要考慮了變量對測試路徑的影響。該方法通過捕獲源代碼中與關(guān)鍵狀態(tài)變量相關(guān)語句和謂詞表達式中的判斷條件之間的關(guān)系來構(gòu)造測試用例和關(guān)鍵狀態(tài)變量、關(guān)鍵狀態(tài)變量計算表達

式以及謂詞表達式中判斷條件之間的測試用例關(guān)聯(lián)矩陣，并提出了測試用例約簡的準(zhǔn)則，根據(jù)該準(zhǔn)則對測試用例集進行約簡。實驗結(jié)果表明，本文所提出的約簡策略可以對原測試用例集的數(shù)量進行約簡，而且并沒有降低原測試用例集的錯誤檢測率，但增加了計算開銷。

基于代碼分析的測試用例約簡所涉及測試路徑以及本文所提的關(guān)鍵狀態(tài)變量、謂詞表達式中的判斷條件等因素，是一個十分復(fù)雜的問題，如果程序中包含程序間調(diào)用、數(shù)據(jù)庫交互等更加復(fù)雜的場景，研究方案仍需要進一步完善。另外，文本所做的驗證實驗只是在西門子測試用例套件中選取的四個程序所自帶的測試數(shù)據(jù)集上完成的，這4個程序的源代碼規(guī)模較小，本方法的有效性還需要進行大規(guī)模的實驗加以驗證。