基于數據挖掘和決策樹的測試用例重用技術研究

劉 偉，安鵬偉，王嬴超

(1. 北京京航計算通訊研究所， 北京 100074；2. 北京市涉密信息載體安全管理工程技術研究中心, 北京 100074)

0 引言

測試工作具有復雜性和創造性,需要高度智慧。其目的在于發現軟件錯誤，衡量軟件質量[1],即測試工作只能查找出程序的錯誤，而不是證明程序沒有缺陷[2]。即便測試過程非常嚴格，測試后的程序中仍然可能隱藏缺陷。

目前國內外的測試用例重用主要分為腳本測試用例重用和文本類型測試用例重用[3]。其中，腳本類型測試重用的思想是將腳本類型的測試用例當成軟件構件來管理，并借用軟件重用的方法，規定了重用用例的命名要求、注釋要求、復雜度要求和編程規則要求等，便于后續重復使用。文本類型測試用例主要包含測試輸入、執行步驟和預期結果等方面，針對文本類型的測試用例重用研究，主要集中在如何管理測試用例和如何查詢上。

本文首先研究了可重用的測試用例的特性，為采集可重用的測試用例提供指導，并對飛航軟件評測中心4個型號的平臺式慣性導航軟件和2個型號的捷聯式慣性導航軟件的近2000個測試用例進行了總結分類，提煉出了247個可以重用的測試用例。然后將數據挖掘技術應用于飛航軟件測試用例重用中，建立了飛航測試用例重用模型。通過決策樹算法，將測試專家分類重用測試用例的思想固化，并可以根據新采集的可重用的測試用例，不斷擴充分類規則，使測試用例重用庫具有不斷自擴充和自完善的能力。最后通過應用上述模型建立導航軟件測試用例重用庫，并在實際項目中開展應用，取得了較好的效果。

1 軟件測試用例重用

1.1 軟件測試用例重用概述

軟件測試重用是指在2次或多次不同的軟件測試過程中重復使用相同或相近的測試資源來開展測試的過程[4]。它的出發點是保證對程序的測試不再采用一切從零開始的測試模式，而是充分利用現有測試經驗，實現對軟件測試過程中可重用成分最大程度的重用,避免重復勞動[5]。軟件測試重用主要包含測試流程的重用、測試思想的重用和測試用例的重用這3個方面。其中，測試用例作為軟件測試的核心，它的重用也就成為開展軟件測試重用過程的關鍵環節[6]。

對第三方測試機構來說，首先總結出某一個導彈分系統的軟件測試中可以重用的測試用例，并采用智能算法，對測試用例進行重用的分類和預測，實現測試用例重用，能夠提高軟件測試的質量和效率，增加其覆蓋性，降低測試成本[7]。

1.2 測試用例重用的評估標準

通過參考國內外文獻，并結合飛航軟件測試用例的特點，可以使用以下4個標準對測試用例的可重用性進行評估[8]。

1)通用性

有些測試用例具有特殊性,只能在特定條件和環境下應用，而不能移植至其他程序中，就沒有必要也不能夠重用這些用例，所以說可重用的測試用例具有通用性。為了讓采集的測試用例是通用的，本文針對某一類(如慣導)軟件的測試用例，保留它們的共性，去除個性，以此來提高用例的可重用性。

2)簡潔性

測試用例的設計與所測模塊具有很強的相關性，其信息很復雜，為了進行有效的重用，必須將它處理成簡單形式，僅包含對它的使用和重用的基本部分。本文采集的測試用例，僅保留了原測試用例中的用例說明、測試類型、測試輸入、測試步驟和期望測試結果這5項內容。

3)實施信息豐富性

可重用的測試用例需要有豐富的參考信息，包括軟件功能和實施環境等信息。但是測試用例中不包含此類信息，為后續重用該測試用例帶來一定困難。本文在采集可重用的測試用例的同時，還增加了軟件功能和實施環境等方面的描述，增加了用例的重用可能性。

4)對軟件功能驗證的全面性

一組好的測試用例需要充分驗證其軟件功能。相對于單個測試用例的重用，軟件測試用例中體現的測試思想和測試策略具有更高的價值。本文對每一個可重用的測試用例，提煉了該用例的設計思想，為后續使用者提供參考，提高了測試用例的設計水平和測試效果。

2 數據挖掘與決策樹算法

本文使用數據挖掘中的決策樹算法模擬測試專家對測試用例的屬性分類方法和對重用性的決策方法，然后使用訓練好的決策樹對新采集的測試用例進行智能分類和決策，得到新采集的測試用例的重用性高低。下面簡要介紹了數據挖掘以及決策樹算法。

2.1 數據挖掘基本概念步驟

數據挖掘[8](Data Mining, DM)是數據庫知識發現的過程，它是指從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，通過算法提取隱含在其中的、人們事先不知道的、但又有用的潛在信息和知識的過程[9]。目前數據挖掘廣泛應用于關聯分析、分類、聚類分析和序列分析中[10]。

整個數據挖掘過程包含若干挖掘步驟，主要步驟有：

1)數據清洗(data cleaning)，其目的是清除數據噪聲,并去除與挖掘主題不相關的數據。本文首先對飛航軟件評測中心的測試用例進行初步整理，去除部分明顯無法重用的測試用例。

2)數據轉換(data transformation)，其目的是將數據處理為易于進行數據挖掘的特定存儲形式。本文中將測試用例中的軟件功能、測試思想、測試類型和設計人員4項屬性和1項決策用離散的數字進行表示，便于進行數據挖掘。

3)數據挖掘(data mining)，知識挖掘的關鍵步驟，其目的是利用智能算法挖掘數據模式和規律知識。本文使用決策樹算法對測試用例的屬性和決策數據進行挖掘，得到測試用例的分類與決策規則[11]。

4)知識表示(knowledge presentation)，其作用就是利用可視化和知識表達技術，向用戶展示挖掘出的知識成果。本文使用產生式規則表示決策樹挖掘出的相關知識。

分類和預測是數據挖掘的主要功能之一,應用領域眾多。在數據挖掘中常用的分類方法有決策樹、貝葉斯網絡[12]和神經網絡[13]等。其中，決策樹學習算法作為一種逼近離散函數的方法, 能夠學習析取表達式,同時對噪聲數據有很好的健壯性,因此應用尤為廣泛[14]。

2.2 決策樹算法概述

決策樹學習算法是以實例為基礎的歸納學習算法，能夠從一組無次序和無規則的事例中推導出決策樹表示形式的分類規則，通常用來形成分類器和預測模型，可以對未知數據進行分類或預測、數據挖掘等。決策樹在分類、預測、規則提取等領域有著廣泛應用。

2.3 決策樹算法

一棵決策樹的內部結點是屬性或屬性的集合，葉結點是所要學習劃分的類，內部結點的屬性稱為測試屬性。用決策樹進行分類的過程具有2個步驟：第一步是建立基于訓練集的決策樹模型，這個過程的作用是從數據中獲取知識，從而進行機器學習；第二步是利用生成的決策樹模型對未知的數據樣本進行分類。使用決策樹對未知的數據樣本進行分類時，從根結點開始逐一測試該對象的屬性，順著分支走，直至到達某個葉結點，此葉結點代表的類即為該對象所處的類。

決策樹分類方法首先利用訓練集建立決策樹模型，然后依據該模型對輸入數據進行分類。分類的關鍵在于決策樹的構建，這一過程包含建樹和剪枝兩步：第一步是建樹，選取部分訓練數據建立決策樹，建樹依據廣度優先遞歸算法，其中止條件為每個葉子結點屬于同一個類；第二步是剪枝，利用剩余數據對生成的決策樹進行檢驗和完善，調整不正確的內容，對決策樹進行剪枝和增加結點，直到建立一個正確的決策樹。決策樹的建樹算法是通過遞歸過程，最終得到一棵決策樹，而剪枝則是為了降低噪聲數據對分類正確率的影響。

2.3.1 ID3算法

ID3算法是一種基于信息熵的決策樹分類算法?；镜腎D3算法通過自頂向下構造決策樹來進行學習，其工作過程如下：首先選出最具有分類能力的測試屬性作為根結點；然后為根結點屬性的每個可能值產生一個分支，并把訓練樣例排列到適當的分支之下，形成多個子集；每個子集又選擇最具有分類能力的另一個測試屬性進行劃分，如此一直進行到最后劃分出的所有子集僅包括同一類型的數據為止；最后得到一棵決策樹，可以用它對新的例子進行分類。ID3是一種自頂向下增長樹的貪婪算法，其測試屬性的選取以信息熵的下降速度為標準，信息熵的下降也就是信息不確定性的下降。

1)屬性選擇

ID3算法的研究核心是選取最具有分類能力的測試屬性。為此，ID3算法引入了信息論中熵(entropy)的概念，將信息增益(information gain)這個統計屬性作為選擇分類測試屬性的標準。設S為一個訓練樣例集，目標分類屬性C具有n個不同的值，記為C={C1，C2，…，Cn)，pi代表分類屬性值為Ci的樣例在訓練樣例集S中所占的比例。那么S相對于目標分類屬性C的熵計算如下

(1)

屬性的信息增益代表由于使用這個屬性分割樣例而導致的期望熵降低。一個屬性A相對樣例集合S的信息增益Gain(S，A)定義如下

Gain(S,A)=

(2)

其中，Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集即Sv={s∈S|A(s)=v}，Entropy(Sv)為子集Sv相對于目標分類屬性C的熵。式(2)的第一項是原集合S的熵，第二項是屬性A的每個子集的熵的加權和，權值為屬于Sv的樣例占原始樣例S的比例。

該算法計算每個屬性的信息增益，將具有最高信息增益的屬性選作給定集合S的測試屬性，創建一個結點，并以該屬性標記，對屬性的每個值創建分枝，并據此劃分樣本。

2.3.2 C4.5算法

ID3算法在數據挖掘中具有重要意義，但在實際應用中，ID3算法存在不能處理連續屬性、計算信息增益時偏向選取值較多的屬性、抗噪性能差等弱點。在ID3算法的基礎上發展起來的C4.5算法，繼承了ID3算法的全部優點，同時增加了更多功能。新增功能有：引入增益比率的概念，合并具有連續值的屬性，可以處理缺少屬性值的訓練樣本，以及通過使用不同的修剪技術避免樹的不平衡等[15-16]。

1)信息增益比率

在C4.5算法中，為了克服使用信息增益選擇屬性時偏向選擇取值多的屬性的不足， Quinlan定義了一種新的測試屬性選取標準，即信息增益比率，其定義為

(3)

式(3)表明：在不同屬性提供相同的信息增益Gain(S，A)時，SplitInfo(S，A)取值越小越好，其值越小說明為了獲取關于屬性A的取值所需付出的代價也就越小。式(3)中SplitInfo(S，A)為屬性A的信息熵，即對于一個屬性A，根據其不同取值v1,v2,…，vn，將訓練集分割成集合S1,S2,…,Sn，則

(4)

本文將使用數據挖掘技術中的決策樹算法對可重用的測試用例進行分類，將測試專家的重用用例分類的思想固化下來，并且可以針對一個新的測試用例重用查詢需求，可以預測出能夠滿足需求的、重用度最高的測試用例。

3 基于數據挖掘的飛航測試用例重用技術

目前，國內外針對軟件測試用例重用技術的研究，主要針對如何對測試用例進行存儲和如何進行查詢上。缺少對測試用例重用庫如何構建和如何擴充的研究。

飛航軟件評測中心根據有關軟件測試用例重用實踐經驗，并結合數據挖掘技術，開展了基于數據挖掘的飛航嵌入式軟件測試用例重用技術的研究。

3.1 基于數據挖掘的測試用例重用技術

該技術可以通過數據挖掘的方法，不斷發現新的知識規則，不斷擴充測試用例庫，使測試用例重用庫形成一個不斷自擴充和不斷自學習的智能系統。測試用例重用庫構建模型結構見圖1，模型描述如下：

1)通過飛航嵌入式軟件測試專家使用1.2節中的測試用例可重用的標準，對本領域(按照飛航導彈武器系統的各個分系統進行分類)中測試用例進行總結分析，選出通用性好、覆蓋全面的測試用例，提煉出這些測試用例的設計思想，并去除無法重用的測試用例。

2)對測試用例進行抽象化處理，去除測試用例中和具體軟件相關性特別強的方面，提高測試用例重用的可能性，如性能測試中涉及的具體參數。

3)選擇用于數據挖掘的測試用例的屬性和決策。根據飛航軟件測試用例的特點，選用的屬性為：軟件所屬分系統(如綜控機、慣導、電調等)；軟件功能點；測試類型(功能測試、性能測試、余量測試等)；用例設計思想(專家提煉的設計思想)。決策為兩種，分別為：重用性高和重用性低。并對上述文字信息做相應變換，轉化為數值信息。

4)軟件測試專家使用1.2節中的測試用例的可重用的標準評價這些測試用例可重用性，建立基于決策樹的數據挖掘技術的規則訓練集。其中決策樹算法使用第2節中描述的相關算法的式(1)～式(4)。

5)使用規則訓練集訓練決策樹，生成知識規則集。

6)使用生成的知識規則對新采集的測試用例進行分類管理，生成一個不斷自擴充的測試用例重用庫。如果新采集的測試用例無法用舊有的知識規則進行分類，則通過基于決策樹的數據挖掘技術可以擴充知識規則，形成新的知識規則集。

基于數據挖掘的測試用例重用技術的結構圖如圖1所示。

圖1 基于數據挖掘的測試用例重用技術的結構圖Fig.1 Structure diagram of test case reuse technology based on data mining

3.2 慣導軟件測試用例重用庫構建和應用

3.1節中研究了通用的飛航軟件測試用例重用技術，下面將該技術應用在慣導軟件中并構建慣導軟件測試用例重用庫。

3.2.1 基于數據挖掘的慣導軟件測試用例重用庫構建

1)對慣導軟件測試用例進行分類總結。

慣導軟件測試專家對飛航軟件評測中心4個型號的平臺式慣性導航軟件和2個型號的捷聯式慣性導航軟件的近2000個測試用例進行了總結分類，選擇出了247個可以重用的測試用例，作為建立導航軟件測試用例初始重用庫的基礎。

2)對慣導測試用例進行抽象化處理。

慣導軟件測試專家針對慣導軟件的247個文本測試用例進行總結和評估，由于這些用例使用的模板不一樣，導致用例的具體描述不一樣。經過專家討論，去除個性描述，保留共性描述，以最大可能增加用例的可重用性，所以只保留247個測試用例的用例說明、測試類型、測試輸入、測試步驟和期望測試結果這5項。而且，增加了型號名稱、研制階段、軟件版本號、軟件功能、測試思想、測試環境和設計人員等7項屬性。對這些用例重用性進行了初步評估，并分別給出了重用性高和重用性低的評價，該評價可以作為數據挖掘算法的決策訓練集和測試集。

3)選擇用于數據挖掘的測試用例的屬性和決策。

在第2步中，每一個測試用例擁有12項屬性，和1項決策。需要對屬性進行簡化，去除對決策影響小的屬性，保留對決策影響大的屬性。經過專家討論，保留軟件功能、測試思想、測試類型和設計人員4項屬性，決策為重用性高和重用性低。由于測試思想和具體的軟件功能有關，所以對測試思想的取值進行了歸一化處理，將同類測試思想進行合并，并簡化描述。各個屬性和決策的可能取值如表1和表2所示。

4)針對屬性和決策，構建數據挖掘的訓練樣本集。

結合專家對247個文本測試用例中的200個測試用例給出的決策值，可以得到數據挖掘的訓練樣本。限于篇幅，不列舉訓練樣本集。

5)使用第2節中的算法，針對每一個屬性計算相應的信息增益的取值，然后根據信息熵的取值得到決策樹的根節點。

本文使用MATLAB進行仿真與計算，經過計算后第一層屬性的信息增益的取值如表3所示。

表1 導航軟件測試用例重用屬性取值表

表3 各個屬性的信息增益取值

從表3可以看出，軟件功能具有最大的信息增益，為根節點。

從第二層開始，以后的分枝產生過程完全重復前面的步驟，直到完全分類了所有的訓練數據為止。不同的是，此時不再考慮已經使用過的上一層的根結點屬性。最終，決策樹的規則固化在MATLAB工作空間的決策樹結構中。經過逐層的分解，導航軟件測試用例重用決策樹如圖2所示。

圖2 導航軟件測試用例重用決策樹Fig.2 Navigation software test case reuse decision tree

根據上述決策樹，可以生成產生式知識規則，描述如下：

a)IF軟件功能=“上電初始化功能” AND 測試類型=“功能測試”AND 測試思想=“遍歷功能項”AND 設計人員=“人員1”THEN 重用性=“重用性高”。

b)IF軟件功能=“上電初始化功能”AND 測試類型=“性能測試”THEN 重用性=“重用性低”。

c)IF 軟件功能=“上電初始化功能”AND 測試類型=“接口測試”THEN 重用性=“重用性高”。

d)IF 軟件功能=“看門狗功能” THEN 重用性=“重用性高”。

e)IF 測試人員=“人員3” THEN 重用性=“重用性低”。

……

通過對導航測試用例進行數據挖掘，得到了上述判斷測試用例重用性高低的知識規則。這些知識規則不僅僅將導航軟件測試專家的知識規則固定下來，而且發現了新的知識，例如：通過數據挖掘得知，如果是人員3編制的測試用例，則其測試用例的重用性低。后續采集測試用例時，如果是人員3的測試用例，則通過決策樹算法，自動將該測試用例歸類為重用性低。

這些規則將導航軟件測試專家的知識規則固定下來，如果有新的測試用例，可以很容易判斷該用例的可重用程度，并且針對測試用例重用需求，可以很方便地從測試用例重用庫中找到最可能被重用的測試用例。

6)讓專家對剩余的47個測試用例的重用性進行評估，并給出決策值，作為上述決策樹的測試樣本集，對決策樹的決策能力進行評估。其中有3組樣本的結果與專家評估值不一致，決策正確率為：94%。結果證明了該算法可以對新采集的測試用例的可重用性進行準確評估與分類。

3.2.2 基于數據挖掘的慣導軟件測試用例重用庫工具開發與應用

通過使用COM技術，將MATLAB中的決策樹生成DLL動態鏈接庫文件，并使用.NET技術開發了飛航軟件測試用例重用庫系統工具。該系統可以對新采集的測試用例完成數據挖掘、擴充知識規則和擴充測試用例重用庫的功能。該庫中存放了3.2.1節中描述的4個型號的平臺式慣性導航軟件和2個型號的捷聯式慣性導航軟件的247個可以重用的測試用例。

測試人員根據測試項目中設計測試用例的需要，輸入測試用例重用的需求。然后，該工具使用決策樹規則，列出最有可能重用的一組用例，并按照被重用性高低的順序排序，方便測試人員使用。

該工具在采集新的測試用例時，將會根據決策樹規則，對該用例進行分類，并決策出該用例重用性的高低。如果該用例不能用舊的規則進行分類，則需要重新訓練決策樹，擴充決策規則，使測試用例庫不斷自完善和自擴充。

慣導軟件測試用例重用庫工具主界面、測試用例采集與重用性決策界面、測試用例查詢和重用界面如圖3所示。

圖3 慣導軟件測試用例重用庫工具主界面Fig.3 Main interface of the test case reuse library tool of inertial navigation software

該工具在飛航軟件評測中心導航軟件的動態測試中開展了應用，在某合同項目的捷聯慣導軟件動態測試中，重用了上電初始化功能的2個測試用例、自檢功能的3個測試用例、對準功能的3個測試用例、數據封裝/裝訂功能的4個測試用例和導航功能的7個測試用例，取得了較好的效果。

4 總結

本文首先研究了可重用的測試用例的特性，為采集可重用的測試用例提供指導，并結合飛航型號軟件的特點，提出了測試用例重用的關鍵在于測試思想的重用。然后將數據挖掘技術應用于飛航軟件測試用例重用中，建立了飛航測試用例重用模型。通過決策樹算法，將測試專家分類重用測試用例的思想固化，并可以根據新采集的可重用的測試用例，不斷擴充分類規則，使測試用例重用庫具有不斷自擴充和自完善的能力。最后通過應用上述模型建立導航軟件測試用例重用庫，并在實際項目中開展應用，取得了較好的效果。