基于傳統(tǒng)H算法改進(jìn)的回歸測試用例優(yōu)化算法

成亞玲，譚愛平，彭湘華

（湖南工業(yè)職業(yè)技術(shù)學(xué)院，湖南長沙，410208）

基于傳統(tǒng)H算法改進(jìn)的回歸測試用例優(yōu)化算法

成亞玲，譚愛平，彭湘華

（湖南工業(yè)職業(yè)技術(shù)學(xué)院，湖南長沙，410208）

回歸測試用例的優(yōu)化選擇是為了達(dá)到良好的回歸測試覆蓋率，提高回歸測試效率。根據(jù)回歸測試用例優(yōu)化問題的性質(zhì)和自身條件，針對五種經(jīng)典傳統(tǒng)啟發(fā)式算法存在的不足，論述了如何改進(jìn)傳統(tǒng)H算法得到回歸測試用例優(yōu)化選擇的局部更優(yōu)解，并給出了算法的框架、程序、結(jié)構(gòu)流程及具體實現(xiàn)。最后，通過大量算法分析和實例研究對改進(jìn)后的H算法和其它算法求得的子集總代價進(jìn)行對比，結(jié)果表明：新算法比傳統(tǒng)經(jīng)典算法和目前流行的一些智能算法能求得更優(yōu)的解，證明了算法的可行性。

回歸測試；測試用例優(yōu)化選擇；啟發(fā)式算法；測試用例集約簡；覆蓋率

1 引言

回歸測試用例優(yōu)化選擇技術(shù)著重于研究測試用例集約簡，即測試用例最小化算法策略。這種技術(shù)旨在不影響原測試用例集錯誤檢測能力的基礎(chǔ)上，從全部測試用例中選取最小同時也是最優(yōu)的測試用例子集達(dá)到對所有測試需求相同的測試覆蓋率，并獲得最高的測試效率。目前有關(guān)回歸測試用例優(yōu)化選擇的研究，主要集中在應(yīng)用一些優(yōu)化算法及交互策略在測試用例集中搜索符合既定覆蓋標(biāo)準(zhǔn)的極小化的測試用例子集，構(gòu)造優(yōu)化模型，以剔除冗余測試用例，縮減待執(zhí)行的測試用例集規(guī)模，從而減少測試成本、人力、物力的消耗。

現(xiàn)有的回歸測試用例優(yōu)化選擇研究的算法主要包括：啟發(fā)式算法、整數(shù)規(guī)劃算法、遺傳算法、蟻群算法、粒子群優(yōu)化（PSO）算法等。其中，啟發(fā)式算法因其理論基礎(chǔ)簡單，操作簡便，魯棒性好，便于實際應(yīng)用，在過去很長一段時間內(nèi)，一直在該研究領(lǐng)域中占據(jù)主導(dǎo)地位。然而，近年來，由于受傳統(tǒng)觀念影響，該領(lǐng)域的研究人員普遍認(rèn)為傳統(tǒng)啟發(fā)式算法雖然簡單易行，但很難在現(xiàn)有基礎(chǔ)上進(jìn)行進(jìn)一步的優(yōu)化和改進(jìn)，甚至得到NP-hard問題的全局最優(yōu)解，因此，遺傳算法、蟻群算法、粒子群（PSO）算法這些智能算法在當(dāng)下的回歸測試用例優(yōu)化選擇研究中較傳統(tǒng)算法得到了更廣泛的應(yīng)用。事實上，這些算法因其自身存在的過早收斂、優(yōu)化效率低等局限性，在實際應(yīng)用中往往需要通過與其它算法混合使用來得以改進(jìn)，而且算法的代價通常較高，優(yōu)化過程繁瑣。本文在回歸傳統(tǒng)啟發(fā)式算法的基礎(chǔ)上，探索基于傳統(tǒng)H算法改進(jìn)的優(yōu)化算法，解決當(dāng)下遺傳算法、蟻群算法等智能算法的不足。本文首先明確H算法約簡細(xì)節(jié)，然后在原算法的基礎(chǔ)上加入交替查找必要測試用例、刪除1-1冗余測試用例和刪除主導(dǎo)地位低的測試需求等步驟，對H算法進(jìn)行了改進(jìn)，接著給出了具體的算法描述和偽代碼，最后通過算法分析和實驗，結(jié)果表明在生成的測試用例集的大小和測試生成的時間消耗兩方面，新算法優(yōu)于已有的相關(guān)算法。

2 相關(guān)知識與概念

2.1 用非空有限集R和T分別表示基線測試需求集和基線測試用例集，r和t分別表示測試需求和測試用例；

2.2 基線測試用例集T和基線測試需求集R的二元關(guān)系組:用二元關(guān)系來表示。由于測試人員在設(shè)計測試用例時，為了充分保證測試用例對測試需求的覆蓋率，往往是針對一個測試需求設(shè)計一個或多個測試用例，因此在二元組S (T,R)中，即一個測試用例可以完成對一個或多個測試需求的測試；在以往的文獻(xiàn)研究中，二元組S(T,R)也可被抽象成一個關(guān)系矩陣T×Rn×m，矩陣行代表測試用例集ti，矩陣列代表測試需求集rj，矩陣中的元素值（ti，r）j為1或0，為1表示ti能滿足rj,為0表示不滿足；

2.5 特定測試用例滿足的測試需求集和滿足特定測試需求的測試用例集：表示測試用例t滿足的所有測試需求組成的集合，由此；同理表示滿足測試需求r的所有測試用例組成的集合，由此表示滿足所有測試需求的測試用例組成的集合，這個集合可能是T，也有可能是T的子集T'；

2.7 必要測試用例、冗余測試用例及1-1冗余測試用例：若對于t∈T，存在Req(T )≠R（即某一測試需求能且只能被某一測試用例t所滿足），則稱t為必要測試用例，用Ess(T)表示；若存在Req(T )=R，則稱t是冗余測試用例；若存在，且，則稱ti為1-1冗余測試用例；

2.8 占主導(dǎo)地位的測試需求和重要程度高的測試需求：對于測試需求r∈R，如果存在測試需求r'，使得，則稱r相對于r'來說主導(dǎo)地位高，r'相對于r來說主導(dǎo)地位低；對于測試需求r∈R，如果存在測試需求r'，使得，則稱r相對于r'來說重要程度高；

基于以上基本定義，不難看出，回歸測試用例優(yōu)化選擇算法旨在從基線測試用例集T中找到它的一個最優(yōu)代表集T''，T''能夠充分測試給定的測試需求集R，并且約簡后的測試用例互補(bǔ)。研究證明，T''一定存在，但不唯一，然而其基數(shù)一定是最小同時也是相同的。

3 優(yōu)化回歸測試用例集的改進(jìn)H算法

3.1 五種經(jīng)典傳統(tǒng)啟發(fā)式算法的優(yōu)化實例與缺陷分析

本文針對7種具有代表性的初始測試用例集和測試需求集，如表1至表7所示，分別運(yùn)用G、GE、GRE、H、CH五種經(jīng)典算法對其分析。

表1 初始測試用例集和測試需求集的關(guān)系1

表2 初始測試用例集和測試需求集的關(guān)系2

表3 初始測試用例集和測試需求集的關(guān)系3

表4 初始測試用例集和測試需求集的關(guān)系4

表5 初始測試用例集和測試需求集的關(guān)系5

表6 初始測試用例集和測試需求集的關(guān)系6

表7 初始測試用例集和測試需求集的關(guān)系7

按照五種經(jīng)典傳統(tǒng)算法的約簡步驟依次對表1～表7進(jìn)行了五種經(jīng)典傳統(tǒng)啟發(fā)式算法的約簡，其中對H算法進(jìn)行了細(xì)節(jié)分化測試：H1為從Ri中優(yōu)先選取滿足最多測試需求的測試用例，H2為從Ri中順序選取測試用例，H1、H2都對R1,R2,…,Ri進(jìn)行的是廣度優(yōu)先選取用例。約簡結(jié)果如表8所示。

表8 五種經(jīng)典傳統(tǒng)啟發(fā)式回歸測試用例優(yōu)化選擇算法運(yùn)算結(jié)果

通過該實例的實驗分析，得出以下結(jié)論：

3.1.1 歷史文獻(xiàn)對H算法的研究不夠深入，特別是在提出的新算法與H算法進(jìn)行性能比對時存在用H算法從Ri中選取相應(yīng)測試用例的環(huán)節(jié)步驟不明朗問題，如優(yōu)先選取滿足最多測試需求的測試用例和順序選取測試用例的約簡效果是不一樣的。這也必然為在H算法和其它算法特別是CH算法優(yōu)劣對比過程中提供了不確定因素。

3.1.2 對H算法進(jìn)行細(xì)節(jié)分化后的H1算法和CH算法能始終優(yōu)于其它幾種，且H1在得到與CH算法相同約簡率的前提下，比CH算法花費(fèi)開銷小、更易于實現(xiàn)。充分肯定了H1算法的實用價值，這一點(diǎn)是在以往文獻(xiàn)研究中從未涉及到的。下節(jié)提出的新算法是在現(xiàn)有的H1算法基礎(chǔ)上進(jìn)行改進(jìn)，使其能在比CH算法更節(jié)省開銷、更簡單易行的前提下保持與CH算法相同的約簡率。

3.2 改進(jìn)的H算法

3.2.1 算法思想及步驟

通過在H1算法前加入交替查找必要測試用例、刪除1-1冗余測試用例和刪除主導(dǎo)地位低的測試需求，再用傳統(tǒng)的H算法對回歸測試用例進(jìn)行優(yōu)化選擇。下面給出此算法的實現(xiàn)步驟：

第1步：刪除所有測試用例都能滿足的測試需求；

第2步：檢索所有必要測試用例并忽略掉所有必要測試用例已滿足的測試需求；

第3步：刪除1-1冗余測試用例；

第4步：進(jìn)行需求約簡，刪除主導(dǎo)地位低的測試需求，約簡掉等價需求中的多余需求；

第5步：反復(fù)執(zhí)行1、2、3、4步，直到測試用例集中不存在必要測試用例、1-1冗余測試用例及冗余測試需求為止，更新測試用例與測試需求關(guān)系表；

第6步：判斷是否有一個測試用例可以滿足所有剩余的未被滿足的測試需求，若有，轉(zhuǎn)至第8步，若無繼續(xù)第7步；

第7步：執(zhí)行H算法：將測試需求分成R1、R2、…、Ri，再依次對R1、R2、…、Ri挑選測試用例，特別注意每個Ri從相應(yīng)測試用例集中選擇測試用例時是優(yōu)先選取使其能滿足最大數(shù)量的未被滿足的測試需求的測試用例，即用貪心算法來從Ri中選取用例，約簡掉已滿足的測試需求，直到Ri中的測試需求完全被滿足。如果存在多個測試用例滿足測試需求的個數(shù)相等的情況，則根據(jù)下一需求集合中的情形進(jìn)行比較，若直到最后一個集合仍相同，則用隨機(jī)法進(jìn)行選擇；

第8步：輸出被優(yōu)化的測試用例集。

3.2.2 算法偽代碼描述

基于傳統(tǒng)H算法改進(jìn)的回歸測試用例優(yōu)化選擇算法Hnew-reduce用偽代碼描述如下：

Declare Selected:被選擇了的測試用例；

4 算法演進(jìn)及分析

4.1 算法演進(jìn)

下面引用表7的初始測試用例集和測試需求集的關(guān)系，對新算法進(jìn)行約簡。約簡過程如下：

第一步，首先通過分析每個測試用例對測試需求集的滿足關(guān)系，發(fā)現(xiàn)不存在所有測試用例都能滿足的測試需求；

第二步，通過分析每個測試用例對測試需求集的滿足關(guān)系，發(fā)現(xiàn)無必要測試用例；

第三步，繼續(xù)查找當(dāng)前測試用例中存在1-1冗余測試用例，對表刪除1-1冗余測試用例t7，t4，t6，t8，t5，t11（Req(t7)Req(t1)，Req(t4)Req(t3)，Req(t6) Req(t3)，Req(t8)Req(t3)，Req(t5)Req(t9)，Req(t11) Req(t9)），約簡后如表9所示：

表9 刪除1-1冗余測試用例后的測試用例和測試需求關(guān)系

第四步，此時表9中不再存在必要測試用例和1-1冗余測試用例，下面進(jìn)行需求約簡，約簡等價需求r4，r5（r10≡r4，r7≡r5），再刪除占主導(dǎo)地位低的測試需求r2，r3，r8，r9，r12（r6r2，r8r2，r11r2，r12r2，r5r3，r7r3，r6r8，r11r9，r11r12），約簡結(jié)果如表10所示：

表10 測試需求集約簡后的測試用例和測試需求關(guān)系

第五步，此時表中存在1-1冗余測試用例t1，t12（t1t10，t12t10），刪除t1，t12后的約簡結(jié)果如下表11：

表11 第五步約簡后的測試用例和測試需求關(guān)系

第六步，此時t10為必要測試用例，輸出t10，并刪除t10滿足的需求r1，r7，r10（此步驟實際為H算法中滿足R1的用例約簡步驟），約簡后結(jié)果如下表12所示：

表12 第六步約簡后的測試用例和測試需求關(guān)系

第七步，從表12可見，t2已覆蓋剩余全部需求，輸出t2。算法結(jié)束。

結(jié)果顯示利用本算法得到精簡后的結(jié)果為｛t10，t2｝，為局部最優(yōu)解，約簡結(jié)果與CH算法相同。

然而在本實例的研究中，并沒有很好地體現(xiàn)新算法中的加入步驟與傳統(tǒng)H算法的完美結(jié)合所呈現(xiàn)出的算法優(yōu)越性，該實例僅僅在交替查找必要測試用例、刪除1-1冗余測試用例和刪除主導(dǎo)地位低的測試需求的步驟后就完成了測試用例優(yōu)化選擇全過程。為了進(jìn)一步體現(xiàn)本文提出的新算法與傳統(tǒng)啟發(fā)式算法的性能對比，下面選取了測試用例來說明算法的應(yīng)用和有效性,初始測試用例集和測試需求集合的關(guān)系見表13（引自文獻(xiàn)[5]）。

表13 初始測試用例集和測試需求集的關(guān)系9

利用本算法對表13進(jìn)行約簡的過程如下：

第一步，首先通過分析每個測試用例對測試需求集的滿足關(guān)系，發(fā)現(xiàn)不存在所有測試用例都能滿足的測試需求；

第二步，通過分析每個測試用例對測試需求集的滿足關(guān)系，發(fā)現(xiàn)無必要測試用例；

第三步，繼續(xù)查找當(dāng)前測試用例集中存在1-1冗余測試用例，對表刪除1-1冗余測試用例t4（Req(t4)Req(t5)），約簡后如表14所示：

表14 刪除1-1冗余測試用例t4后的測試用例和測試需求關(guān)系

第四步，此時表14中不再存在必要測試用例和1-1冗余測試用例，下面進(jìn)行需求約簡，約簡等價需求r2（r2≡r4），再刪除占主導(dǎo)地位低的測試需求r1，r3，r5，r6，r7，r10，r11，r12，r17，約簡結(jié)果如表15所示：

表15 需求約簡后的測試用例和測試需求關(guān)系

第五步，此時表中不存在必要測試用例、1-1冗余測試用例、等價需求以及占主導(dǎo)地位低的測試需求，對表執(zhí)行H1算法：

將測試需求分成R2，R3如下：

從R2的子集r4中優(yōu)先選取滿足最多測試需求的測試用例t2，此時滿足r4的測試用例有t2和t5，由于Req(t2)=Req(t5)=3，所以任意選擇輸出t2到最后的約簡結(jié)果中，同時刪除t2覆蓋的測試需求r4，r13，r15，更新測試用例和測試需求的二元關(guān)系，此時，約簡結(jié)果如表16所示：

表16 刪除t2后的測試用例和測試需求關(guān)系

再從R2的子集r9中優(yōu)先選取滿足最多測試需求的測試用例t1，此時滿足r9的測試用例有t1和t5，由于Req(t1)=4＞Req(t5)=2，所以選擇輸出t1到最后的約簡結(jié)果中，同時刪除t1覆蓋的測試需求r9，r14，r16，r19，更新測試用例和測試需求的二元關(guān)系，此時，約簡結(jié)果如表17所示：

表17 刪除t1后的測試用例和測試需求關(guān)系

從表17可見，t3已覆蓋剩余全部需求，輸出t3。算法結(jié)束。

因此，利用本算法得到的優(yōu)化代表集為｛t2，t1，t3｝。在該實例中，利用傳統(tǒng)啟發(fā)式算法得到的優(yōu)化代表集結(jié)果如下：G和GE選出的優(yōu)化代表集為{t5,t1,t2, t3(t6)}或者{t5,t1,t6,t7(t8)}；GRE算法得到的結(jié)果是{t5, t7,t6,t1}；傳統(tǒng)H算法得到的結(jié)果是{t1,t6,t2,t3}；CH算法得到的結(jié)果是{t1,t2,t3}。

上面的結(jié)果顯示，與傳統(tǒng)啟發(fā)式算法相比較，本算法能達(dá)到和CH算法同樣的約簡率，即得到的優(yōu)化代表集的用例個數(shù)最少。然而本文提出的改進(jìn)算法與CH算法相比，在測試需求數(shù)量較大、相互關(guān)系復(fù)雜、測試資源又緊張的情況下，計算開銷小很多，此點(diǎn)將在下一節(jié)算法分析中得到進(jìn)一步證明。本文提出的方法，首先優(yōu)化了測試需求，有利于減小計算開銷，獲得最小的測試用例集。

為了確保實驗數(shù)據(jù)比對的連貫性、進(jìn)一步明確本算法的有效性和其較傳統(tǒng)經(jīng)典啟發(fā)式算法的改進(jìn)效果，下面將本文用五種經(jīng)典傳統(tǒng)啟發(fā)式算法和本算法所做的所有實驗結(jié)果進(jìn)行總結(jié)對比。約簡結(jié)果如下表18所示。

表18 本算法與傳統(tǒng)經(jīng)典算法與的約簡結(jié)果對比

4.2 算法分析與評價根據(jù)前面的算法步驟及代碼描述，下面給出本算法的最壞時間復(fù)雜度：

為了進(jìn)一步對比本算法較其它算法優(yōu)越，下面將基于表8約簡的各種算法的約簡結(jié)果、最壞時間復(fù)雜度、覆蓋率COV，約簡率K的結(jié)果進(jìn)行歸納總結(jié)，如表19所示：

表19 基于表7的各種啟發(fā)式算法性能對比

從表19不難看出，本算法和CH算法具有相同的測試覆蓋率和約簡率，且這兩項性能指標(biāo)均優(yōu)于其它四種算法。此外，本算法的最壞時間復(fù)雜度比CH算法低，雖然略高于G、GE算法，但比其它算法都要低。

在實驗過程中，為進(jìn)一步求證不斷加大測試用例規(guī)模是否會對上述結(jié)論造成影響，本文做了大量算法演算，現(xiàn)將各算法分別對不同規(guī)模的用例集約簡后所付出的時間代價挪列如表20，同時根據(jù)該表繪制出了相應(yīng)的折現(xiàn)對比圖如圖1所示。

表20 各算法的時間復(fù)雜度結(jié)果比較

圖1 各算法的約簡測試用例集時間代價比較

綜上所述，改進(jìn)后的H算法可以生成最優(yōu)代表集，很大程度上提高了回歸測試效率，降低了測試成本，而且始終優(yōu)于其它幾種算法，CH算法約簡率雖高，但運(yùn)算開銷遠(yuǎn)遠(yuǎn)大于本算法。

5 結(jié)束語

本文分析了五種經(jīng)典傳統(tǒng)啟發(fā)式算法的特點(diǎn)、適用域、優(yōu)缺點(diǎn)及優(yōu)化原理，提出一種基于傳統(tǒng)H算法的改進(jìn)的回歸測試用例優(yōu)化選擇的新算法，該算法在明確H算法約簡細(xì)節(jié)的基礎(chǔ)上，加入交替查找必要測試用例、刪除1-1冗余測試用例和刪除主導(dǎo)地位低的測試需求等步驟，算法演進(jìn)和分析表明：從生成的測試用例集的大小和測試生成的時間消耗兩方面，新算法優(yōu)于已有的相關(guān)算法。

[1]游亮，盧炎生.測試用例集啟發(fā)式約簡算法分析與評價[J].計算機(jī)科學(xué)，2011，38(12):147-150,177.

[2]林木，戴月明.回歸測試中測試用例集優(yōu)化方法的研究[J].計算機(jī)工程與應(yīng)用,2011,47(11):54-56.

[3]王捷民,熊建國,宋瀚濤,等.互補(bǔ)策略的簡化測試用例集方法研究[J].哈爾濱工業(yè)大學(xué)學(xué)報,2007,39(11):1818-1821.

[4]陳偉,徐錫山.一種能得到優(yōu)化代表集的測試用例集極小化算法[J].計算機(jī)研究與發(fā)展,2006,43(z2):105-109.

[5]李克文,楊志霞.基于回歸測試模型的用例集的優(yōu)化方法研究[J].微計算機(jī)應(yīng)用,2008,29(10):7-11.

The Optimized Research of Regression Test Cases Based on Improved Traditional H Algorithm

CHENG Yaling,TAN Aiping,PENG Xianghua
（Hunan Industry Polytechnic,Changsha410208,Hunan）

Research on the optimized selection of regression test cases is to ensure the fine test coverage and the higher test efficiency.According to the nature and their own conditions of the Optimized Selection problems,aiming at the existing problems of the five kinds of classic traditional heuristic algorithm,this paper discussed how to improve the traditional H algorithm and obtain the local optimization selection of test cases.Meanwhile,the algorithm framework,code,structure and concrete realization process were given.Meanwhile,it made a comparison on the subsets of the total cost between the new improved H algorithm and the other five algorithms through a large number of algorithm analysis and cases study.The experimental results show that the proposed method can obtain the better subset than the traditional classic algorithms and some currently popular intelligent algorithm,and the feasibility of the algorithm were proved with results.

electric vehicles；smart distribution grid；planning；development

TP311.5

A

1671-5004（2015）04-0001-07

2015-3-7

湖南省教育廳科研項目“基于工作流的期刊在線投稿系統(tǒng)的設(shè)計與實現(xiàn)”（項目編號：12C1033）。

成亞玲(1981－)，女，回族，上海青浦市人，湖南工業(yè)職業(yè)技術(shù)學(xué)院講師、軟件設(shè)計師、工程碩士，研究方向：軟件工程、數(shù)字加密與圖像處理。

譚愛平（1979-），男，湖南攸縣人，湖南工業(yè)職業(yè)技術(shù)學(xué)院副教授，研究方向：計算機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)安全。

彭湘華（1985-），男，湖南株洲人，湖南工業(yè)職業(yè)技術(shù)學(xué)院講師、碩士，研究方向：數(shù)據(jù)挖掘，生物信息。