回歸測(cè)試中測(cè)試用例優(yōu)化技術(shù)研究與探索

劉 音 范 雯 徐林雪

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

0 引言

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

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

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

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

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

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

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

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

1.2 測(cè)試用例優(yōu)先級(jí)排序

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

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

2 本文工作

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

2.1 實(shí)現(xiàn)測(cè)試用例約簡(jiǎn)

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

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

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

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

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

（5）解碼，得到約簡(jiǎn)后的測(cè)試用例。

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

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

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

（1）計(jì)算每個(gè)測(cè)試用例的優(yōu)先級(jí)（錯(cuò)誤檢測(cè)率）。

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

（3）輸出排序后的測(cè)試用例集。

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

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

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

3 仿真實(shí)驗(yàn)

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

表1：實(shí)驗(yàn)結(jié)果對(duì)比

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

（2）由測(cè)試用例未排序和排序后錯(cuò)誤檢測(cè)情況對(duì)比可知，排序后的測(cè)試用例能有效縮短測(cè)試時(shí)間。

4 結(jié)論

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