范書平，萬 里，姚念民，張 巖，馬寶英

（1.牡丹江師范學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江牡丹江 157012；2.天津大學(xué)智能與計(jì)算學(xué)部，天津 300350；3.大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧大連 116024；4.宿遷學(xué)院信息工程學(xué)院，江蘇宿遷 223800；5.牡丹江醫(yī)學(xué)院衛(wèi)生管理學(xué)院，黑龍江牡丹江 157011）

1 引言

回歸測(cè)試是指修改了舊代碼后重新進(jìn)行測(cè)試，以確認(rèn)修改沒有引入新的錯(cuò)誤或?qū)е缕渌a產(chǎn)生錯(cuò)誤［1］.據(jù)估計(jì)，回歸測(cè)試在整個(gè)軟件測(cè)試預(yù)算中約占80%［2］.為了降低回歸測(cè)試的成本，近些年國內(nèi)外學(xué)者對(duì)高效自動(dòng)化的回歸測(cè)試技術(shù)展開了深入的研究，測(cè)試用例排序技術(shù)（Test Case Prioritization，TCP）［3］是目前研究的熱點(diǎn)之一.測(cè)試用例排序技術(shù)在不減少測(cè)試用例數(shù)量的情況下，按照某種準(zhǔn)則對(duì)測(cè)試用例進(jìn)行排序，使得有較高優(yōu)先級(jí)的測(cè)試用例優(yōu)先執(zhí)行［4］，該技術(shù)可以有效減少回歸測(cè)試工作量［5］，其目標(biāo)是更早揭示程序中的缺陷，從而降低回歸測(cè)試的成本.

目前，許多學(xué)者研究了多種性能指標(biāo)和技術(shù)來實(shí)現(xiàn)回歸測(cè)試用例的優(yōu)先排序，以最大化回歸測(cè)試的有效性.Fang 等人［6］研究修改的條件/分支覆蓋測(cè)試用例排序方法；Chen 等人［7］考慮用半監(jiān)督學(xué)習(xí)改進(jìn)聚類過程，并應(yīng)用程序切片技術(shù)進(jìn)行用例的排序；Noor 等人［8］則提出了基于歷史故障數(shù)據(jù)的排序方法，該方法考慮了測(cè)試用例之間的相似性；潘偉豐等人［9］提出了一種基于復(fù)雜軟件網(wǎng)絡(luò)的回歸測(cè)試用例優(yōu)先級(jí)排序方法，該方法評(píng)價(jià)類的測(cè)試重要性，同時(shí)結(jié)合測(cè)試用例的覆蓋信息，對(duì)測(cè)試用例進(jìn)行排序；張衛(wèi)祥等人［10］應(yīng)用遺傳算法，石宇楠等人［11］應(yīng)用協(xié)同進(jìn)化算法，Nayak 等人［12］應(yīng)用粒子群算法分別實(shí)現(xiàn)了測(cè)試用例的排序.多數(shù)TCP技術(shù)使用結(jié)構(gòu)覆蓋作為衡量測(cè)試用例優(yōu)先級(jí)的指標(biāo)［12，13］，Mukherjee 等人［1］對(duì)2001—2018 年的90 篇關(guān)于測(cè)試用例排序的學(xué)術(shù)論文進(jìn)行了研究，結(jié)果表明基于覆蓋信息的排序技術(shù)應(yīng)用得最為廣泛，這類技術(shù)的目標(biāo)［14］是盡可能早地實(shí)現(xiàn)代碼覆蓋.

貪心算法是解決測(cè)試用例排序問題的常用算法［11］，包括total 策略與additional 策略.Rothermel 等人［15］最早提出了面向覆蓋的TCP技術(shù)，并應(yīng)用這兩種策略設(shè)計(jì)了不同的排序方法，結(jié)果表明所提方法能有效提高測(cè)試用例的缺陷檢測(cè)率.作為該工作的延伸，Elbaum等人［16］則將測(cè)試用例排序劃分為功能級(jí)技術(shù)、語句級(jí)技術(shù)的排序方法，在方法中引入節(jié)約系數(shù)，將平均缺陷檢測(cè)百分比（Average Percentage of Fault Detected，APFD）轉(zhuǎn)換為效益模型.Hao 等人［17］應(yīng)用了集成線性規(guī)劃，提出了基于最優(yōu)覆蓋的優(yōu)先級(jí)排序技術(shù)，研究表明，與基于貪心算法的TCP 技術(shù)相比，所提出的排序技術(shù)在缺陷檢測(cè)率或執(zhí)行時(shí)間上沒有明顯弱勢(shì).張娜等人［18］則提出基于多目標(biāo)優(yōu)化的TCP 方法，有效縮短了軟件測(cè)試時(shí)間.Jiang等人［19］提出了基于覆蓋率的ART技術(shù)，其目的是盡可能地?cái)U(kuò)展代碼覆蓋空間.陳夢(mèng)云等人［20］則在基于覆蓋的total 策略與additional 策略中引入了圈復(fù)雜度，實(shí)現(xiàn)了測(cè)試用例優(yōu)先級(jí)，提高了錯(cuò)誤檢測(cè)的有效性.

在基于分支覆蓋的測(cè)試用例排序技術(shù)中，典型的total 策略總是將覆蓋分支最多的候選用例加入到已排序序列中，而additional 策略則選擇覆蓋新分支最多的用例［15，21］.也有TCP 技術(shù)根據(jù)用例的輸出覆蓋程序切片情況，給在相關(guān)切片中覆蓋更多語句與分支的用例分配更高的權(quán)重［22］.Mahdieh 等人［23］則在代碼覆蓋（包含語句和分支單元）的基礎(chǔ)上，應(yīng)用神經(jīng)網(wǎng)絡(luò)進(jìn)行缺陷預(yù)測(cè)，以評(píng)估代碼單元的故障傾向性.Huang 等人［24］結(jié)合代碼覆蓋與組合覆蓋提出了一種新的覆蓋準(zhǔn)則，將該覆蓋準(zhǔn)則應(yīng)用于測(cè)試用例排序中，并通過與兩種貪心策略進(jìn)行對(duì)比，驗(yàn)證了所提方法的有效性.此外，F(xiàn)ang 等人［21］在測(cè)試用例運(yùn)行程序后，根據(jù)各用例覆蓋程序?qū)嶓w的有序序列計(jì)算用例間的相似性，提出了面向語句和分支覆蓋準(zhǔn)則的測(cè)試用例排序技術(shù)，提高了排序用例的缺陷檢測(cè)能力.

上述測(cè)試用例排序方法往往只考慮單一用例對(duì)測(cè)試目標(biāo)的重要程度，并未有效利用已排序用例覆蓋程序真假分支的均衡情況.這種不均衡性導(dǎo)致用例覆蓋程序分支的偏離影響會(huì)更大，尤其對(duì)于大型復(fù)雜程序，分支或者循環(huán)結(jié)構(gòu)較多，這種偏離程度尤為突出.然而，在測(cè)試用例排序中考慮用例對(duì)程序代碼測(cè)試均衡的研究還很少并且不夠深入.

本文的主要貢獻(xiàn)如下：

（1）在測(cè)試用例排序技術(shù)中引入用例覆蓋程序各分支的偏離程度；

（2）應(yīng)用測(cè)試用例覆蓋程序新分支情況與用例覆蓋程序分支的偏離程度來計(jì)算候選用例的權(quán)重，并據(jù)此選擇關(guān)鍵用例進(jìn)行排序；

（3）提出了基于關(guān)鍵用例獲取的排序算法來有效解決測(cè)試用例排序問題；

（4）將所提出的方法應(yīng)用于典型程序，驗(yàn)證了方法的有效性.

2 基本概念

為了便于闡述，下面給出幾個(gè)基本概念.

2.1 測(cè)試用例排序

測(cè)試用例排序問題可以定義［20］為給定測(cè)試套件T，T中所有測(cè)試用例排序的集合O，以及從O到實(shí)數(shù)集映射函數(shù)f；測(cè)試用例排序的目標(biāo)為找到一個(gè)序列子集o∈O，滿足?o′∈O,f(o)≥f(o′).其中，f函數(shù)的作用是度量測(cè)試用例排序的有效性，為了提高給定測(cè)試套件的缺陷檢測(cè)率，f函數(shù)通常為平均缺陷檢測(cè)百分比（APFD）函數(shù)，其取值范圍為［0，1］，APFD 值越大，缺陷檢測(cè)率越高.

2.2 sigmoid函數(shù)

sigmoid 是一種激活函數(shù)，該函數(shù)常用作二分類的概率以及輸出神經(jīng)元，應(yīng)用它可以把一個(gè)實(shí)數(shù)映射到區(qū)間（0，1），該函數(shù)的定義為

2.3 基于覆蓋的測(cè)試用例排序技術(shù)

基于覆蓋的測(cè)試用例排序方法通常將源代碼劃分為層次結(jié)構(gòu)單元，例如包、文件、方法和語句，并定義這些單元的覆蓋率，單元覆蓋率［23］可以描述如下.

假設(shè)已經(jīng)將被測(cè)程序的源代碼劃分為多個(gè)單元，U={u1,u2,…,um}.對(duì)于每個(gè)測(cè)試用例tk與代碼單元uj，Cover(k,j)表示測(cè)試用例tk是否覆蓋單元uj，如果被測(cè)代碼的單元是語句，則覆蓋范圍為0 或1.用n(n＞0)表示代碼單元的數(shù)量，通常將測(cè)試用例tk的總覆蓋范圍Cover(k)定義為

2.4 用例偏離度

已排序用例與候選用例tk運(yùn)行被測(cè)程序后，覆蓋程序中第w個(gè)分支節(jié)點(diǎn)真假分支的用例數(shù)目的差異，稱為用例tk對(duì)第w個(gè)分支節(jié)點(diǎn)的用例偏離度（簡稱為用例偏離度），表示為BPkw，見3.1.3節(jié)中的式（7）.

2.5 關(guān)鍵用例

測(cè)試用例運(yùn)行程序后，每次從候選用例中選擇用例進(jìn)行排序時(shí)，根據(jù)候選用例覆蓋程序新分支數(shù)量以及用例偏離度，按照3.1.4 節(jié)中的式（8）計(jì)算各候選用例權(quán)重，得到權(quán)重最大的候選用例定義為關(guān)鍵用例.

3 基于關(guān)鍵用例獲取的測(cè)試用例排序方法

3.1 關(guān)鍵用例的獲取

為了便于分析，本文將循環(huán)節(jié)點(diǎn)按照循環(huán)體執(zhí)行或者不執(zhí)行轉(zhuǎn)化為含有兩個(gè)分支的情況，而switch語句本身也可以轉(zhuǎn)換為雙分支結(jié)構(gòu)，為此，以下討論中將分支節(jié)點(diǎn)與循環(huán)節(jié)點(diǎn)統(tǒng)稱為分支節(jié)點(diǎn)，且僅考慮一個(gè)分支節(jié)點(diǎn)有兩個(gè)分支的情況.

3.1.1 建立用例覆蓋分支矩陣

首先，根據(jù)測(cè)試用例覆蓋程序各分支節(jié)點(diǎn)真假分支情況，建立測(cè)試用例覆蓋分支矩陣.假設(shè)當(dāng)前測(cè)試套件中含m(m＞0)個(gè)測(cè)試用例，被測(cè)程序含n個(gè)分支節(jié)點(diǎn)，對(duì)應(yīng)有2n個(gè)分支節(jié)點(diǎn)的真假分支，通過統(tǒng)計(jì)第w(1 ≤w≤n)個(gè)分支節(jié)點(diǎn)的真分支bwT與假分支bwF的被測(cè)試用例ti(1 ≤i≤m)的覆蓋情況，得到用例覆蓋分支矩陣，記為covm(2n)，矩陣中的行代表測(cè)試用例ti覆蓋各分支節(jié)點(diǎn)的真假分支的情況，矩陣中的奇數(shù)列表示各測(cè)試用例覆蓋各分支節(jié)點(diǎn)的真分支的情況，矩陣中的偶數(shù)列則代表不同的測(cè)試用例覆蓋各分支節(jié)點(diǎn)的假分支的情況，covm(2n)表示為

其中，當(dāng)j為奇數(shù)時(shí)，

3.1.2 記錄已排序用例覆蓋程序分支情況

假設(shè)當(dāng)前已排序用例總數(shù)為m′(0 ＜m′≤m)，根據(jù)3.1.1 小節(jié)中建立的用例覆蓋分支矩陣covm(2n)，計(jì)算覆蓋第w個(gè)分支節(jié)點(diǎn)真分支、假分支的已排序用例數(shù)目，分別記為sumwT與sumwF.則可以將sumwT表示為

式（3）表明，覆蓋第w個(gè)分支節(jié)點(diǎn)真分支的已排序用例數(shù)目，可以通過對(duì)矩陣cov 的第(1～m′)行中的第(2w-1)列元素求和得到.同理，可以將sumwF表示為

式（4）表明，覆蓋第w個(gè)分支節(jié)點(diǎn)假分支的用例數(shù)目通過對(duì)矩陣cov的第(1～m′)行中第2w列元素求和得到.

3.1.3 計(jì)算候選用例的用例偏離度

為了考查候選用例tk是否能有效改善用例覆蓋程序分支的均衡性，本文通過計(jì)算該候選用例排序后的用例偏離度來實(shí)現(xiàn).候選用例tk排序后，將覆蓋第w個(gè)分支節(jié)點(diǎn)真分支與假分支的用例數(shù)目分別記為與，則可以表示為

同理，覆蓋第w個(gè)分支節(jié)點(diǎn)假分支的用例數(shù)目可以表示為

則tk排序后覆蓋第w個(gè)分支節(jié)點(diǎn)真假分支用例數(shù)目的差異可以表示為為了便于計(jì)算，本文通過應(yīng)用Sigmoid 函數(shù)（見式（1）），將該值規(guī)范化為（0，1）區(qū)間內(nèi)的值，并將規(guī)范化后的差異性記為候選用例tk對(duì)第w個(gè)分支節(jié)點(diǎn)的用例偏離度BPkw，該值表示為

由式（7）可知，BPkw∈(0,1)所定義的用例偏離度實(shí)際上反應(yīng)了用例tk排序后覆蓋第w個(gè)分支節(jié)點(diǎn)的用例覆蓋其真假分支的差異情況.若BPkw較大，則說明覆蓋第w個(gè)分支節(jié)點(diǎn)真假分支的用例差異較大，說明覆蓋該分支節(jié)點(diǎn)真假分支的用例偏離程度較大；反之，若BPkw的取值較小，說明覆蓋該分支節(jié)點(diǎn)真假分支的用例差異小.不難得出，用例偏離度BPkw越小越好.

3.1.4 計(jì)算候選用例的權(quán)重

在候選用例tk權(quán)重的計(jì)算中，綜合考慮用例偏離度及覆蓋新分支的情況.根據(jù)式（7），進(jìn)一步計(jì)算tk排序后所有分支節(jié)點(diǎn)的用例偏離情況，并將式（2）單元覆蓋率中的代碼單元uj表示為分支節(jié)點(diǎn)的真假分支，用Cover(k)表示tk覆蓋新分支的數(shù)目，則可以將候選用例tk的權(quán)重表示為

其中，Cover(k)∈[0,n].

從式（8）可以看出，候選用例權(quán)重的計(jì)算綜合考慮了候選用例偏離度及覆蓋新分支的能力，候選用例tk覆蓋的新分支越多，tk排序后用例偏離度越小，則該用例的權(quán)重越大.此外，若某一候選用例tk雖然不能覆蓋新分支，但是排序后能有效改善用例偏離度，這樣的候選用例權(quán)重也較高，并會(huì)優(yōu)先加入到排序序列中.

3.2 基于關(guān)鍵用例獲取的測(cè)試用例排序算法

本文算法步驟如算法1 所示.該算法的基本思想是：首先插樁被測(cè)程序，并對(duì)算法的控制參數(shù)賦值，測(cè)試用例運(yùn)行被測(cè)程序，從中選擇覆蓋程序語句最多的用例作為第一個(gè)已排序用例；然后根據(jù)用例覆蓋程序各分支情況，建立用例覆蓋分支矩陣，并據(jù)此得到用例偏離度及候選用例覆蓋分支情況，進(jìn)而獲取關(guān)鍵用例進(jìn)行排序，直到所有用例均已排序.

4 實(shí)驗(yàn)

實(shí)驗(yàn)中所有程序均用C 語言編寫，仿真環(huán)境為VC++6.0.選擇的實(shí)驗(yàn)程序包括space 程序、tot_info 程序、replace 程序、flex 程序與sed 程序［1］.并從space 程序、flex 程序與sed 程序中各選擇兩個(gè)函數(shù)進(jìn)行實(shí)驗(yàn).表1中列出了實(shí)驗(yàn)中各程序參數(shù)的設(shè)置情況，包括選擇的程序代碼行數(shù)（LOC）、插入缺陷數(shù)目（Faults）以及用例規(guī)模（Test Cases）.對(duì)比方法包括：根據(jù)程序?qū)嶓w相對(duì)執(zhí)行次數(shù)，通過計(jì)算用例間距離的基于語句覆蓋或分支覆蓋的排序技術(shù)［21］，將這兩種方法分別記為SED 與BED，選擇的第三種對(duì)比方法為典型的Additional算法，記為AGA，該方法按照候選用例覆蓋新語句情況選擇用例進(jìn)行排序［25］.

表1 程序說明

4.1 需要驗(yàn)證的問題與評(píng)價(jià)指標(biāo)

問題1所提的測(cè)試用例排序方法的時(shí)間效率如何？

本文應(yīng)用多次實(shí)驗(yàn)中算法的平均運(yùn)行時(shí)間AT 來衡量算法的時(shí)間有效性［26］，如式（9）所示，其中Ti(1 ≤i≤total)表示第i次實(shí)驗(yàn)算法的運(yùn)行時(shí)間，total表示總實(shí)驗(yàn)次數(shù)，可知AT值越小，算法的時(shí)間有效性越好.

問題2所提方法的缺陷檢測(cè)有效性如何？

通過考查不同排序方法檢測(cè)出各缺陷時(shí)需要執(zhí)行的測(cè)試用例情況，來比較不同方法的缺陷檢測(cè)性能，以驗(yàn)證所提方法的有效性.

問題3所提方法的缺陷檢測(cè)效率如何？

用平均缺陷檢測(cè)百分比APFD 來驗(yàn)證所提方法的缺陷檢測(cè)效率，如式（10）所示，其中m′與num 分別表示測(cè)試套件包含的測(cè)試用例數(shù)和測(cè)試用例可檢測(cè)出的缺陷數(shù)，TFi(1 ≤i≤m′)表示第i個(gè)缺陷第一次被檢測(cè)出的測(cè)試用例在排序后的測(cè)試用例集中的次序編號(hào).

問題4所提方法的測(cè)試用例排序序列對(duì)程序分支覆蓋均衡性如何？

本文比較了不同方法得到用例排序序列的TB 值，該值表示了每個(gè)排序用例對(duì)各程序分支覆蓋的平均均衡程度，計(jì)算方法見式（11）.假設(shè)排序后得到的序列為t1,t2,…,tm′，公式中BPkw表示在用例排序過程中找到的各關(guān)鍵用例tk對(duì)第w個(gè)分支節(jié)點(diǎn)的用例偏離度.

4.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果如表2、圖1、圖2所示.

圖1 測(cè)試用例檢測(cè)缺陷情況

圖2 不同方法的APFD值

4.2.1 運(yùn)行時(shí)間的比較

從表2中運(yùn)行時(shí)間上看，AGA方法的運(yùn)行時(shí)間明顯少于其他方法，原因是AGA 方法按照各排序用例的語句覆蓋情況排序用例，計(jì)算量小，但也因此導(dǎo)致覆蓋相同數(shù)目缺陷執(zhí)行的用例比其他方法多；而本文方法的運(yùn)行時(shí)間除略高于AGA 方法外，明顯少于BED 方法與SED 方法的運(yùn)行時(shí)間，這是因?yàn)閼?yīng)用BED 方法與SED方法，在用例排序時(shí)需要根據(jù)程序?qū)嶓w執(zhí)行次數(shù)反復(fù)計(jì)算用例之間的編輯距離，計(jì)算量大.從表2 中也可以看出，除了replace 程序外，針對(duì)其他被測(cè)程序，SED 方法的運(yùn)行時(shí)間比BED 方法更長；而本文方法在用例排序中僅需要計(jì)算候選用例排序后的用例偏離度與覆蓋新分支數(shù)目，計(jì)算量明顯少于BED 方法與SED 方法，這也驗(yàn)證了問題1.與BED 方法與SED 方法相比，應(yīng)用本文方法的運(yùn)行時(shí)間較少，能有效降低軟件測(cè)試代價(jià).

4.2.2 缺陷檢測(cè)有效性的比較

為了比較不同方法的缺陷檢測(cè)性能，針對(duì)不同被測(cè)程序，比較了四種方法檢測(cè)全部缺陷需要執(zhí)行的用例百分比情況，如表2所示.從表2中可以看出，與其他三種方法相比，應(yīng)用本文提出的方法檢測(cè)全部缺陷時(shí)需要執(zhí)行的用例更少，也就是說，在相同的實(shí)驗(yàn)條件下，應(yīng)用本文方法需要更少的用例即能檢測(cè)出程序中的所有缺陷.

表2 運(yùn)行時(shí)間與用例數(shù)目的對(duì)比

為了進(jìn)一步說明本文提出的方法的有效性，實(shí)驗(yàn)中比較了各排序方法隨著缺陷數(shù)目的增加測(cè)試用例的執(zhí)行情況，實(shí)驗(yàn)結(jié)果如圖1所示.從圖1中不難看出，對(duì)于不同被測(cè)程序的六種情況，與BED 方法、SED 方法和AGA 方法相比，應(yīng)用本文方法排序的用例能更早檢測(cè)出程序中的缺陷；從總體上看，隨著測(cè)試用例的增加，各種方法檢測(cè)的缺陷也越來越多，除了圖1（a）中個(gè)別缺陷檢測(cè)上本文方法使用了比其他方法更多的用例外，其他情況下本文方法檢測(cè)到的各缺陷執(zhí)行的用例數(shù)目比其他三種方法少.從圖1（a）中被測(cè)程序的執(zhí)行結(jié)果來看，對(duì)于個(gè)別缺陷，應(yīng)用本文方法需要執(zhí)行的用例略多于BED 方法，這是因?yàn)楸粶y(cè)程序space（fixgrid）含有的分支結(jié)構(gòu)較多，BED 方法在用例排序中考慮了候選用例的分支覆蓋情況，因此如果測(cè)試用例覆蓋了缺陷所在分支就容易檢測(cè)出這類缺陷，因此，在這種情況下，BED 方法比本文方法、SED 方法和AGA 方法更早檢測(cè)出了這些缺陷，針對(duì)其他缺陷，本文方法明顯優(yōu)于BED 方法、SED 方法與AGA 方法.從總體上看，與其他方法相比，對(duì)于不同的被測(cè)程序，在執(zhí)行相同的用例情況下，應(yīng)用本文方法檢測(cè)的缺陷數(shù)目更多，這也驗(yàn)證了問題2，與BED 方法、SED 方法與AGA 方法相比，本文的測(cè)試用例排序方法更有效.

圖2 中對(duì)比了不同方法的APFD.針對(duì)不同的測(cè)試用例規(guī)模、不同的被測(cè)程序，本文方法的APFD 值要高于其他三種方法.這是因?yàn)楸疚姆椒ㄔ谶x擇關(guān)鍵用例進(jìn)行排序時(shí)考慮了候選用例的用例偏離度與覆蓋新分支情況，使得所選擇的用例要么能覆蓋已選擇用例未覆蓋的新分支，要么能夠降低用例偏離度，即能有效減少覆蓋各分支節(jié)點(diǎn)真假分支的用例差異，使得排序的用例更均衡的覆蓋程序分支，尤其是對(duì)于難以檢測(cè)到的缺陷，本文方法通過更快速地達(dá)到分支覆蓋的均衡，來提高程序中缺陷的檢測(cè)效率.總體上看，BED方法優(yōu)于SED 方法與AGA 方法，這也驗(yàn)證了問題3，本文方法不僅能有效地進(jìn)行缺陷檢測(cè)，更能提高測(cè)試用例缺陷檢測(cè)的效率.

4.2.3 覆蓋程序分支均衡情況的比較

針對(duì)不同被測(cè)程序比較了TB 值，實(shí)驗(yàn)結(jié)果如表3所示.從覆蓋程序分支均衡情況上看，針對(duì)不同實(shí)驗(yàn)設(shè)置，應(yīng)用本文方法得到的實(shí)驗(yàn)結(jié)果比其他3 種方法的TB 值均要高，這也驗(yàn)證了問題4，本文方法得到的排序序列能更均衡地覆蓋程序分支.這是因?yàn)楸疚姆椒ㄔ跍y(cè)試用例排序過程中考慮了候選用例覆蓋程序分支的均衡情況.同時(shí)，對(duì)于不同被測(cè)程序，AGA方法的TB值要高于BED 方法與SED 方法，這是因?yàn)?，?yīng)用AGA 方法在排序過程中每次達(dá)到代碼覆蓋要求后，將重置代碼為未覆蓋并重新執(zhí)行該算法，導(dǎo)致排序的用例更均衡覆蓋程序分支.

表3 覆蓋程序分支均衡性的對(duì)比

5 結(jié)論

測(cè)試用例排序是回歸測(cè)試研究的重要內(nèi)容.本文提出了一種基于關(guān)鍵用例獲取的測(cè)試用例排序方法，在測(cè)試用例運(yùn)行被測(cè)程序后，根據(jù)覆蓋程序各分支用例的偏離情況，計(jì)算候選測(cè)試用例的分支偏離度，并考慮候選用例覆蓋新分支情況，據(jù)此對(duì)用例進(jìn)行排序.本文方法提高了軟件缺陷的檢測(cè)能力與用例排序的效率，但本文方法僅應(yīng)用于規(guī)模有限的被測(cè)程序，下一步研究的工作重點(diǎn)是在規(guī)模更大的工業(yè)程序中應(yīng)用本文方法，以進(jìn)一步驗(yàn)證該方法的有效性.