基于路徑關鍵狀態變量的測試用例約簡

高 杰, 趙逢禹, 劉 亞

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

0 引 言

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

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

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

1 關鍵狀態變量

1.1 關鍵狀態變量定義

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

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

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

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

通過代碼來說明本文所定義的關鍵狀態變量。

代碼1關鍵狀態變量定義范例。

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是傳入的參數，a,d是謂詞判斷中的參數，而a的值是由b賦予的。因此，本文認為x,a,b,d是關鍵狀態變量。

1.2 關鍵狀態變量獲取

本文利用抽象語法樹(Abstract Syntax Tree, AST) 來獲取關鍵狀態變量。抽象語法樹是程序源代碼的抽象語法結構的樹狀表現形式。

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

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

2 測試用例約簡方案

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

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

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

(2)查找每類測試用例集對應的源代碼。針對聚類后的每類測試用例集，根據測試的功能與輸入參數的型構確定被測程序的程序源代碼。

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

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

代碼2代碼預處理示例

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. }

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

代碼3代碼預處理結果示例

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)基于抽象語法樹的信息提取。利用高級語言中所提供的技術構建程序源代碼的抽象語法樹。獲取抽象語法樹中的每個節點信息，從而找到代碼中的關鍵狀態變量、關鍵狀態變量的計算表達式以及謂詞表達式中的判斷條件，并將它們分別添加到相應的集合中。

(5)構建測試用例關聯矩陣。測試用例集中的每個測試用例對應測試用例關聯矩陣的一行信息，多個測試用例構成了測試用例關聯矩陣。測試用例關聯矩陣用M表示，M矩陣中每一行對應一個測試用例的輸入參數、關鍵狀態變量、關鍵狀態變量的計算表達式和謂詞表達式中的判斷條件，形式化表示為式(1)：

Mi=(ti,,,) .

(1)

其中，ti表示測試用例中第i個測試用例的輸入參數，V表示關鍵狀態變量的集合，E表示關鍵狀態變量的計算表達式集合，C表示謂詞表達式中的條件判斷的集合。

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

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

圖1 約簡方法流程框架

3 主要算法實現

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

(1)在抽象語法樹中獲取關鍵狀態變量；

(2)在測試用例關聯矩陣中查找并移除等效的測試用例，實現測試用例約簡。

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

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

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

圖2 抽象語法樹

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

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

輸出關鍵狀態變量集合keyVariable，關鍵狀態變量的計算表達式集合comExpression，謂詞表達式中的判斷條件集合conExpression。

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

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

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

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

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

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

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

(8) 算法結束。

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

3.2 基于測試用例關聯矩陣的約簡

3.2.1 構建測試用例關聯矩陣

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

圖3 測試用例關聯矩陣示例

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

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

3.2.2 測試用例約簡算法

根據本文所提出的測試用例約簡準則對測試用例關聯矩陣進行約簡，算法2給出了測試用例關聯矩陣的約簡描述。

算法2測試用例關聯矩陣中測試用例的約簡

輸入測試用例關聯矩陣M

輸出約簡后的測試用例關聯矩陣M'

(1)for eachito row // row是測試用例關聯矩陣的行數

(2) for eachj=i+ 1 to row

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

(4) end for

(5) end for

4 實驗分析

4.1 實驗數據及評價指標

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

(2)

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

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

表1 西門子程序集信息

4.2 實驗方案

實驗的具體方案：

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

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

(3)構建測試用例與關鍵狀態變量集合、關鍵狀態變量的計算表達式集合以及謂詞表達式中的判斷條件集合的測試用例關聯矩陣，再計算測試用例關聯矩陣中每一項所對應的值，最后根據測試用例約簡準則對其進行約簡。

4.3 實驗結果和分析

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

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

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

表2 約簡后測試用例的數量

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

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

5 結束語

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

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

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

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