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

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

1 引言

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

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

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

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

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

本文的主要貢獻如下：

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

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

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

（4）將所提出的方法應用于典型程序，驗證了方法的有效性.

2 基本概念

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

2.1 測試用例排序

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

2.2 sigmoid函數(shù)

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

2.3 基于覆蓋的測試用例排序技術

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

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

2.4 用例偏離度

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

2.5 關鍵用例

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

3 基于關鍵用例獲取的測試用例排序方法

3.1 關鍵用例的獲取

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

3.1.1 建立用例覆蓋分支矩陣

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

其中，當j為奇數(shù)時，

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

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

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

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

3.1.3 計算候選用例的用例偏離度

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

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

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

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

3.1.4 計算候選用例的權重

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

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

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

3.2 基于關鍵用例獲取的測試用例排序算法

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

4 實驗

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

表1 程序說明

4.1 需要驗證的問題與評價指標

問題1所提的測試用例排序方法的時間效率如何？

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

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

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

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

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

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

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

4.2 實驗結果及分析

實驗結果如表2、圖1、圖2所示.

圖1 測試用例檢測缺陷情況

圖2 不同方法的APFD值

4.2.1 運行時間的比較

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

4.2.2 缺陷檢測有效性的比較

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

表2 運行時間與用例數(shù)目的對比

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

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

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

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

表3 覆蓋程序分支均衡性的對比

5 結論

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