劉 音 范 雯 徐林雪

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

0 引言

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

測試用例（Test Case,TC）指的是一套詳細的測試方案，包括測試環(huán)境、測試步驟、測試數(shù)據(jù)和預(yù)期結(jié)果，是將測試具體量化的方法。軟件測試主要通過執(zhí)行測試用例來查找軟件中存在的缺陷，測試用例設(shè)計的好壞不僅影響到軟件產(chǎn)品的質(zhì)量而且關(guān)系到開發(fā)成本。

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

1 測試用例優(yōu)化

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

1.1 測試用例優(yōu)先選擇

測試用例優(yōu)先選擇技術(shù)又稱測試用例約簡，側(cè)重于研究測試用例最小化，即保持原測試用例集錯誤檢測能力基礎(chǔ)上，依據(jù)一定的規(guī)則去除冗余測試用例，縮減測試用例規(guī)模，選取最少的測試用例來覆蓋所有測試需求，降低執(zhí)行測試用例的成本。1993年，M.J.Harrold等人首次提出測試用例約簡的概念，在原始用例集中，找到一個與原始測試用例集，擁有一樣的測試覆蓋率的最小測試用例子集?？梢岳脝l(fā)式算法（貪心算法、HGS算法、GE算法、GRE算法和遺傳算法等）解決測試用例約簡問題。

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

1.2 測試用例優(yōu)先級排序

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

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

2 本文工作

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

2.1 實現(xiàn)測試用例約簡

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

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

（2）以測試用例與測試需求的覆蓋關(guān)系，設(shè)計適應(yīng)度函數(shù)：f ti=cov i。

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

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

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

2.2 實現(xiàn)測試用例優(yōu)先級排序

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

公式1中RFDn表示第n個測試用例的錯誤檢測率，F(xiàn)Nn表示第n個測試用例檢測的錯誤數(shù)量，CTn表示第n個測試用例執(zhí)行所花費的時間。錯誤檢測率越大測試用例對應(yīng)的優(yōu)先級越高。測試用例優(yōu)先級排序算法如下：

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

（2）依據(jù)優(yōu)先級降序排序測試用例。

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

2.3 實現(xiàn)測試用例優(yōu)化

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

圖1：測試用例優(yōu)化流程

3 仿真實驗

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

表1：實驗結(jié)果對比

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

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

4 結(jié)論

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