基于特征模型和遺傳算法的測試用例自動生成?

江志強 王金波 王曉華

（中國科學(xué)院空間應(yīng)用工程與技術(shù)中心 北京 100094）

1 引言

測試是軟件開發(fā)的關(guān)鍵一環(huán)，測試用例生成是測試過程的重要環(huán)節(jié)。測試用例是否有效、快速地生成，影響了整個測試的效率［1］。一個好的測試用例集，能以較低的測試開銷保障較高的測試性能［2］?，F(xiàn)有常見的測試用例生成方法有基于UML模型［3］，向量機(jī)［4］等方法。它們注重測試性能的同時并不能有效減小測試開銷。因此，本文選用了特征模型。特征模型作為一種功能性的模型，可對功能模塊實現(xiàn)高可復(fù)用性，從而有效降低測試開銷。

當(dāng)前，特征模型的應(yīng)用主要運用于產(chǎn)品線領(lǐng)域的測試開發(fā)。它使用特征表征功能，同一產(chǎn)品線中不同的產(chǎn)品以不同的特征組合方式表達(dá)，而每個特征又通過UML等模型方法建立測試用例［5］。因此，這些產(chǎn)品的測試用例，是通過復(fù)用這些選擇特征的測試用例進(jìn)行組合得到。與之相比，本文對被測產(chǎn)品進(jìn)行特征建模，并將特征與被測件輸入關(guān)聯(lián)，不需要將特征與其他模型相結(jié)合。由于使用組合測試策略能夠進(jìn)一步提高復(fù)用率［6］，因此本文采用組合策略對特征模型進(jìn)行選擇，得到較優(yōu)的測試用例集。

2 特征模型基本概念

特征模型［7］是在產(chǎn)品線分析的領(lǐng)域分析中誕生的，通常被視為一個產(chǎn)品與其它產(chǎn)品不同的地方，它關(guān)注的是產(chǎn)品系列中的需求和功能，并且通過需求分析構(gòu)建產(chǎn)品。

特征模型被視作一個四元組［8］：（F，?，λ，Φ）。其中F代表一組有限的特征節(jié)點，?代表各特征節(jié)點的關(guān)系，通常是以樹狀圖的形式體現(xiàn)，λ代表了特征的四類分配規(guī)則，分別是必選特征mandato?ry和三類非必須的特征：可選擇特征optional，多選一特征alternative，和至少選取一個的特征or規(guī)則。Φ則代表了特征節(jié)點集合中可能的約束，通常包括兩類約束條件：其一是依賴性約束require，也就是某個特征的存在必須以另一個特征存在為前提；其二是互斥性約束exclude，也就是兩者不能同時出現(xiàn)在同一個產(chǎn)品中。

圖1 工資計算器的特征模型

本文用于說明的實例是一個網(wǎng)頁應(yīng)用工資計算器 SalaryCalculator（SC）［9］。它的特征模型如圖 1所示。其中，根特征SC有三個功能，對應(yīng)三個特征：分別是稅率計算TaxCalculator（TC），繳納基數(shù)PayBase（PB）和住房公積金計算 HouseFund（HF）。其中，PB特征含有兩個不同的特征：保險基數(shù)InsuranceBase（IB）和公積金基數(shù)HouseBase（HB）。它們都是optional規(guī)則特征。而HF下有兩個滿足or規(guī)則的特征：代表基本公積金的Base和補充公積金的Supply。

3 模型構(gòu)建

3.1 模型細(xì)化

圖1中特征都對應(yīng)了被測軟件的一個功能模塊。相對于傳統(tǒng)的特征模型，對每個特征不再建立諸如UML等對應(yīng)的實體關(guān)系模型。而是將特征繼續(xù)細(xì)化，對應(yīng)測試的輸入值，建立子特征。

特征與輸入之間存在相互映射的關(guān)系。對特征的測試是通過一組輸入得到相應(yīng)的反饋，根據(jù)反饋結(jié)果檢查特征對應(yīng)的功能是否符合預(yù)期［10］，因此特征與輸入就存在相互影響。這種關(guān)系通常都不是一對一的關(guān)系。子特征則是特征的一部分，指該功能在部分輸入下得到相同反饋或者同一性質(zhì)的反饋的部分功能。根據(jù)特征與輸入的關(guān)系，子特征的建立按如下方式進(jìn)行。

第一，如果一個特征中受多個輸入影響，則每一個輸入都作為該特征的一個子特征。這些子特征會根據(jù)特征分配規(guī)則，被賦予四類分配規(guī)則的中的一種。

第二，如果一個輸入影響多個特征，該輸入受到特征組合的影響，其生成通過后文特征組合實現(xiàn)。

第三，當(dāng)特征或子特征中只含有一個輸入且反之亦然時，此時分為兩類情況：

第1類：布爾型特征：該特征是一個布爾型變量。具體表現(xiàn)為此輸入只會對特征對應(yīng)的子功能產(chǎn)生兩種互斥的狀態(tài)。例如開關(guān)的開啟和關(guān)閉；該特征自身就是其子特征。在特征選擇中，選擇與不選擇兩個狀態(tài)分別對應(yīng)其互斥的兩個結(jié)果，并根據(jù)其選擇狀態(tài)表征其測試輸入值。

如圖1中的Base，Supply特征，它們各自都只有一個輸入，表現(xiàn)為選項框，因此只有選擇和非選擇兩個輸入狀態(tài)表示該功能是否激活。而IB和HB，它們也是選項框輸入，選擇與非選擇分別代表該特征輸入值為系統(tǒng)設(shè)置的默認(rèn)值或最小值兩個狀態(tài)。這四個特征符合布爾型特征。

第2類：非布爾型特征：該特征與第一類不同，隨著其對應(yīng)輸入值的變化，子功能反饋兩種以上的結(jié)果。因此，該特征可以視作以分段函數(shù)，輸入值變化區(qū)間是該分段函數(shù)的定義域，可以劃分為多個子區(qū)間，不同輸入?yún)^(qū)間對應(yīng)分段函數(shù)的不同的子函數(shù)，每個子函數(shù)都可被視作一個子特征。這些子特征之間是互斥的，對應(yīng)了特征模型中的Alternative特征。在測試用例中，該類子特征可以使用邊界值或者等價類直接表示。在特征選擇中，被選中的子特征的值作為其父節(jié)點的值輸出，沒有被選擇的其他子特征的值被舍棄。

例如圖1中的TC特征，它的輸入是一個數(shù)值，隨著數(shù)值的變化，對應(yīng)的計算稅率的函數(shù)會發(fā)生變化，因此符合非布爾型特征，可以按照測試文檔說明按稅率變化分為圖2中TC下的8個子特征，分別是無稅率noTax，第一等稅率Tax_1，直到第七等Tax_7。這些子特征按照非布爾型特征規(guī)則，應(yīng)該滿足optional規(guī)則。

將特征模型通過樹形圖表示，在細(xì)分子特征之后，每個葉子節(jié)點都對應(yīng)一個值。而通過選取葉子節(jié)點，就可以得到一個特征組合并形成測試用例［11］。因此在實際運用中，只選取所有的葉子節(jié)點作為全部特征列表。為了描述測試用例生成，首先有以下定義：

圖2 建立子特征的測試特征模型

定義1：特征模型中所有的葉節(jié)點特征構(gòu)成的集合被稱為特征列表（Feature List，F(xiàn)L）。

如圖1中，所有葉子節(jié)點構(gòu)成的集合｛noTax，Tax_1，Tax_2，Tax_3，Tax_4，Tax_5，Tax_6，Tax_7，HB，IB，base，supply｝就是一個特征列表FL。

定義2：特征配置（FeatureConfigure，fc）是一組滿足特征模型規(guī)范和約束的特征組合，定義為fc={sel，}，其中 sel?FL，sel代表該選定的特征，而都是未選定的特征，它們都是FL的子集，

如圖2中，存在一特征配置fc1=｛｛Tax_1，IB，base｝，｛noTax，Tax_2，Tax_3，Tax_4，Tax_5，Tax_6，Tax_7，HB，supply｝｝，其中 fc1.sel=｛Tax_1，IB，base｝，代表了特征 Tax_1，IB 和 base被選取，=｛noTax，Tax_2，Tax_3，Tax_4，Tax_5，Tax_6，Tax_7，HB，supply｝，代表這些特征未被選擇。因為所有的葉子節(jié)點都對應(yīng)一個值，它們根據(jù)選取或未選取的狀態(tài)返回相應(yīng)的值，或者舍棄該子特征，返回值會根據(jù)特征和輸入的相互關(guān)系反向獲得測試用例的輸入，并根據(jù)測試需求得到預(yù)期結(jié)果，組成測試用例［12］。因此一個特征組合就能對應(yīng)一個測試用例。

定義3：特征配置fc構(gòu)成的集合被稱為特征配置集（Feature Configure Set）FCS。其中，特征列表FL中滿足特征模型規(guī)范和約束的全部特征配置構(gòu)成的集合被稱為完全特征配置覆蓋集。

完全特征配置覆蓋集代表了該被測件所有可能的特征配置形式，即全部的測試路徑。但一般來說這是一個較大的值。例如圖2中，12個葉節(jié)點就構(gòu)成了96個特征配置。

3.2 組合測試

完全特征配置覆蓋通常意味著龐大的測試用例集和大量測試開銷。而好的測試用例集，是選取一個較小的特征配置集合，實現(xiàn)特征覆蓋。測試用例的生成就轉(zhuǎn)化為了特征選取的問題。本文采用組合測試策略解決該問題［13］，并通過遺傳算法實現(xiàn)。研究表明，在特征模型中，采用組合測試的方式能夠?qū)崿F(xiàn)更小的組合配置，并且有更好的檢錯能力以保障其測試性能［14］。

本文在特征模型中采用二元組合策略實現(xiàn)特征配置，相關(guān)定義如下：

定義4：二元組合配置是一個二元組c，定義為的特征和非選擇的特征，并且有

相對于一般特征模型只覆蓋全部特征的方法，二元組合的特征配置集合需要對RC進(jìn)行完全覆蓋。由前文可知，測試用例對應(yīng)的一個特征組合。目標(biāo)測試用例集所滿足的特征配置集應(yīng)該實現(xiàn)對RC全覆蓋。這樣的特征配置集合被稱為結(jié)果集合（Result Set，RS）。為了定義RS，首先引入定義5。

因此結(jié)果集合RS如下定義：

定義6：存在一個特征配置集合CFS=｛fc1，fc2，… fcm｝，其中 ?fci∈CFS，fci的二元覆蓋集合為cfci，對所有 fsi∈CFS，使二元組合覆蓋集RC=該 CFS被稱為結(jié)果集合（Result Set，RS）。其中，在所有的RS中，m最小的RS是最優(yōu)的結(jié)果集合。

因此測試用例的生成就從組合特征和選取特征轉(zhuǎn)化為尋找最優(yōu)的RS，也就是尋找一個足夠小的特征配置集合，使得其能夠?qū)崿F(xiàn)對RC的完全覆蓋。

4 算法描述

一般來說，組合測試覆蓋問題是一個NP難問題，常見的解法有貪心算法和啟發(fā)式算法［15］。前者雖然運算速度快，但是作為一種近似算法，貪心算法只是近似解。而以遺傳算法為代表的啟發(fā)式算法相對于貪心算法可以跳出局部最優(yōu)陷阱，能夠得到更好的近似解。因此文本采取了遺傳算法［16］實現(xiàn)組合測試策略。計算流程如圖3所示。

圖3 基于組合測試的遺傳算法框架

在初始化RC之后，開始對組合測試進(jìn)行遺傳算法運算。每一次遺傳算法初始種群都采用隨機(jī)選擇產(chǎn)生。并不斷調(diào)整適應(yīng)度函數(shù)尋找最優(yōu)解。本文中適應(yīng)度函數(shù)主要有兩部分構(gòu)成。

第一項：判斷個體是否符合特征模型規(guī)則。所有不符合特征需求的個體都會被淘汰，在遺傳中被遺棄；

第二項：判斷個體對當(dāng)前RC的覆蓋情況。RC的覆蓋率再每一次輸出一個最優(yōu)用例的后都收到一個反饋，對當(dāng)前的RC進(jìn)行修正。其中每個個體的RC覆蓋率RCcover計算如下：

其中，RCcover代表RC覆蓋率值。此外，三個覆蓋集合被定義，分別是所有的二元組合覆蓋集AllCover，已經(jīng)被覆蓋的集合RubCover，有效地覆蓋集合 VaildCover；其中 AllCover=RubCover∪ Vaild?Cover；RubCover∩ VaildCover=? ；每個個體所包含的二元組合覆蓋定義為ChroCover；

根據(jù)上述定義，式（1）被修改為

每個個體的適應(yīng)度函數(shù)通過上面兩個項確定，因此，在每進(jìn)行一次遺傳算法后，選取一個適應(yīng)度最高的個體，該個體是一個特征配置fc，它是當(dāng)前種群中擁有最高RC覆蓋率的個體。將其保存在結(jié)果集合RS中，并且從RC中刪去該最優(yōu)解所覆蓋的二元組合。經(jīng)過多次運算，當(dāng)RC變?yōu)榭占臅r候，意味著RC已經(jīng)被完全覆蓋，此時得到的RS就是實現(xiàn)了對RC的完全覆蓋的用例集，是通過遺傳算法求得的最優(yōu)解。

在運算結(jié)束以后，最終得到的一個輸出結(jié)果是一個由特征配置fc構(gòu)成的集合FC，F(xiàn)C的所有元素都是相互獨立且不相關(guān)的。根據(jù)前文中在子特征分解中所述，對每一個特征組合，都可按照其對應(yīng)的功能關(guān)系和特征模型關(guān)系反向得到相應(yīng)的被測軟件輸入數(shù)據(jù)以及期望結(jié)果，該輸入數(shù)據(jù)和期望結(jié)果構(gòu)成測試用例，進(jìn)而獲得所需要的測試用例集。

5 實驗驗證

為應(yīng)用本文中提出的測試用例自動生成的設(shè)計方法，本文對三個被測系統(tǒng)進(jìn)行了運用，其中第一個被測件SalaryCalculator是前文特征模型圖建立的被測系統(tǒng)，該系統(tǒng)是一個運算模塊，它擁有一個數(shù)字輸入和四個參數(shù)調(diào)節(jié)項，包含12個特征；第二個被測件Blog［17］是另一個有一個輸入項和多個可選擇組合的被測項目，包含18個特征；第三個被測件WebLogin［18］是一個有兩個輸入項和多個可選組合的被側(cè)項目，包含25個特征。三個被測件都被注入了10個錯誤。

由于遺傳算法在產(chǎn)生初代種群的時候采取的是隨機(jī)生成，因此我們對每個被測件進(jìn)行10次運算，將其反映在表1中。

表1中，pp是該測試用例覆蓋全部測試用例的比例，全部測試用例數(shù)量是窮舉所有滿足特征模型的特征配置得到。其中，SalaryCalculator被測件一共有96個測試用例，Blog被測件有55520個測試用例，WedLogin被測件包含451584個測試用例。從表1中可得，三個被測件均以較小的開銷實現(xiàn)二元組合的覆蓋，而且錯誤的驗證率都在70%以上，尤其是后兩項產(chǎn)品，它們相對于第一個被測軟件，全路徑分支的測試用例數(shù)更大，但是生成的最小用例集合更小，而且保持了較高的錯誤檢測率，分別有87.8%和94.4%。因此，可以驗證得到，本文提出的測試用例自動生成方法能夠大幅度降低了測試開銷，也可以保持一個高效的錯誤檢測率。

表1 被測系統(tǒng)測試用例生成表

Size為生成的測試用例集大??；pp為測試用例集對全部測試用例的比例。

Fault為發(fā)現(xiàn)的錯誤；FP：檢查錯誤的百分比=發(fā)現(xiàn)的錯誤/注入的總錯誤。

6 結(jié)語

本文提出的基于特征模型的組合測試用例自動生成，結(jié)合了當(dāng)前特征模型測試和組合測試方法的優(yōu)勢，是一種模型簡易易用，可靠性強的測試方法。該方法繼承了特征模型的分析方法，并在此基礎(chǔ)上將特征層次深入到測試數(shù)據(jù)輸入；組合測試和特征模型的結(jié)合進(jìn)一步優(yōu)化測試空間。在實驗中，也驗證了該方法能有效降低測試開銷，保障測試性能，生成良好的測試用例集。

但是遺傳算法隨著迭代次數(shù)的增加，在后期容易出現(xiàn)收斂速度下降的問題，延長了測試用例生成的時間。當(dāng)前在已經(jīng)有很多學(xué)者對加快遺傳算法收斂速度進(jìn)行了研究［17］，在未來的工作中，可以考慮這些算法改進(jìn)策略，優(yōu)化測試用例生成速度。