回歸測試中測試用例優化技術研究與探索

劉 音 范 雯 徐林雪

（北京交通大學海濱學院 河北·滄州 061199）

0 引言

從軟件工程的角度來說，軟件質量是滿足內在系列特征要求的程度，即是否符合功能性、可靠性、易用性、可維護性和可移植性等各方面要求，直接影響著軟件的使用和維護。在軟件的生命周期中，軟件測試是一個重要環節，是質量保證的重要手段。Boris Beizer報告稱，開發一個可工作的程序的一半工作量一般都消耗在測試活動上。

測試用例（Test Case,TC）指的是一套詳細的測試方案，包括測試環境、測試步驟、測試數據和預期結果，是將測試具體量化的方法。軟件測試主要通過執行測試用例來查找軟件中存在的缺陷，測試用例設計的好壞不僅影響到軟件產品的質量而且關系到開發成本。

回歸測試是指修改代碼后重新對軟件進行測試的工作，在整個軟件測試過程中占有很大的工作量比重。隨著軟件功能和實現發生了演變，原始測試用例庫中的一些測試用例可能失去作用，需要針對修改的和添加的功能，設計新的測試用例，從而導致測試用例庫有可能變得相當大，不可能執行所有測試用例完成回歸測試。

1 測試用例優化

目前測試用例優化技術主要包括測試用例優先選擇和測試用例優先級排序技術。測試用例的選擇和執行策略，直接影響測試效率和成本。

1.1 測試用例優先選擇

測試用例優先選擇技術又稱測試用例約簡，側重于研究測試用例最小化，即保持原測試用例集錯誤檢測能力基礎上，依據一定的規則去除冗余測試用例，縮減測試用例規模，選取最少的測試用例來覆蓋所有測試需求，降低執行測試用例的成本。1993年，M.J.Harrold等人首次提出測試用例約簡的概念，在原始用例集中，找到一個與原始測試用例集，擁有一樣的測試覆蓋率的最小測試用例子集。可以利用啟發式算法（貪心算法、HGS算法、GE算法、GRE算法和遺傳算法等）解決測試用例約簡問題。

貪心算法求解測試用例約簡過程：從測試用例集中挑選出一個測試用例，使其最大限度的覆蓋尚未被覆蓋的測試需求，直到覆蓋所有測試需求。HGS算法先將測試需求分成若干組，然后從測試用例集中選擇最少數量的測試用例覆蓋每組測試需求。GE算法是先找到必不可少的測試用例，再使用貪心算法。GRE算法交替進行必要和1-1冗余測試用例的查找，直到不存在這兩種測試用例為止，最后再使用貪心算法選擇測試用例。遺傳算法是一個智能全局搜索算法，利用生物遺傳和進化過程求解全局最優解的近似解。

1.2 測試用例優先級排序

根據研究表明：測試用例庫中，前10%-15%的測試用例可以發現軟件中75%-90%的錯誤。優先級排序技術旨在采用一定的排序策略，更快的檢測出錯誤，提高現在測試用例集的性能。2000年，Rothermel給出了測試用例優先級定義：在測試用例集T的全排列集PT中，執行任意一個全排列T’時，對應的輸出函數值f越大，則T’的排序效果越好。

排序目標是以最快速度檢測出缺陷，一般以錯誤檢測率、檢測錯誤等級和檢測錯誤類型等作為排序依據，Rothermel等提出了基于測試用例分支覆蓋能力的排序方法，Elbaum等提出了基于測試用例耗費和錯誤嚴重性的排序方法，Jones等提出了基于MC/DC覆蓋率的排序方法等，Wong等人提出以累計覆蓋率對測試用例進行排序，Srikanth提出基于測試用例對需求的滿足情況的排序方法，Walcott等提出基于測試用例的歷史執行時間的排序方法，Zhang等提出基于線性規劃的排序方法，Jiang等提出基于錯誤定位的排序方法。

2 本文工作

測試用例約簡的理想結果是：在完全覆蓋測試需求的前提下，執行測試用例集的代價最小。但在有限資源的條件下，還要求測試用例集有較快速的錯誤檢測能力，因此優化測試用例時，不僅要縮減測試用例規模，而且測試時要考慮執行用例的順序。本文采用二者相結合的方法進行測試用例優化，先對測試用例進行約簡，然后在對測試用例進行優先級排序。

2.1 實現測試用例約簡

遺傳算法是模擬生物進化過程的全局搜索方法，通過選擇、交叉和變異操作得到問題最優解。基于遺傳算法的回歸測試測試用例約簡步驟如下：

（1）依據測試用例與測試需求的覆蓋關系，采用二進制編碼初始化種群，種群規模大小由測試需求數量決定，個體基因碼長度由測試用例數量決定。

（2）以測試用例與測試需求的覆蓋關系，設計適應度函數：f ti=cov i。

（3）應用輪盤賭選擇算子產生中間代，單點交叉算子和單點變異算子操作產生新一代種群。

（4）循環操作步驟3，直到新一代種群滿足終止條件。

（5）解碼，得到約簡后的測試用例。

2.2 實現測試用例優先級排序

本文采用基于錯誤檢測率的覆蓋率技術對測試用例進行排序，錯誤檢測率是單個測試用例在單位時間上檢測到的錯誤數量。

公式1中RFDn表示第n個測試用例的錯誤檢測率，FNn表示第n個測試用例檢測的錯誤數量，CTn表示第n個測試用例執行所花費的時間。錯誤檢測率越大測試用例對應的優先級越高。測試用例優先級排序算法如下：

（1）計算每個測試用例的優先級（錯誤檢測率）。

（2）依據優先級降序排序測試用例。

（3）輸出排序后的測試用例集。

2.3 實現測試用例優化

采用遺傳算法進行測試用例集約簡，然后對約簡結果按照錯誤檢測率進行降序排序，得到最終優化結果，實現流程如圖1所示。

圖1：測試用例優化流程

3 仿真實驗

本文采用matlab作為仿真開發環境，從測試用例最小化后用例集規模和檢測錯誤的速度上分析算法性能。交叉概率設定為0.6，變異概率設定為0.01。選擇5個程序作為測試對象，每個程序的初始測試用例是由小組成員精心設計的，實驗結果如表1所示。通過實驗分析發現：

表1：實驗結果對比

（1）遺傳算法能有效的縮減測試用例集規模。

（2）由測試用例未排序和排序后錯誤檢測情況對比可知，排序后的測試用例能有效縮短測試時間。

4 結論

采用遺傳算法進行測試用例集約簡，將已有測試用例錯誤檢測率作為用例優先級，并按照用例優先級取值高低決定測試用例執行順序。這種優先選擇和優先級排序結合的技術，即有利于去除冗余測試用例，又有利于盡快檢測到程序中的錯誤，提高測試效率，降低測試成本；當測試時間有限時，能夠在有限時間內執行更多有效的測試用例，充分地保證軟件質量。