面向MBFL的測試用例約減策略①

杜 彬,賀 杰,王海峰,劉 勇

(北京化工大學(xué) 信息科學(xué)與技術(shù)學(xué)院,北京 100029)

1 引言

軟件已經(jīng)成為現(xiàn)代生活中的重要組成部分,并在醫(yī)學(xué)、航天學(xué)和原子能等方面發(fā)揮著重要的作用.在軟件的開發(fā)和維護(hù)中,軟件調(diào)試是一項成本昂貴且復(fù)雜耗時的工作[1].軟件調(diào)試包括軟件檢測、錯誤定位和錯誤修復(fù)[2].其中,錯誤定位旨在自動識別軟件缺陷模塊,是提高軟件調(diào)試效率的最有效手段之一.

近年來,研究人員在軟件自動化錯誤定位領(lǐng)域上花費巨大的精力,用于降低軟件調(diào)試過程中人力財力的消耗[1,3].其中,基于頻譜的錯誤定位方法是一種被廣泛應(yīng)用的錯誤定位方法[4,5].基于頻譜的錯誤定位方法通過執(zhí)行測試用例獲得覆蓋信息和執(zhí)行結(jié)果信息來計算程序?qū)嶓w中含有錯誤的概率,然后依據(jù)概率大小生成懷疑度表來定位錯誤.但該方法未考慮程序控制流對程序的影響,并且未能處理偶然正確測試用例,使得錯誤定位的有效性受到影響.此外,基于頻譜的錯誤定位方法依賴于測試用例在程序?qū)嶓w上的覆蓋信息,所有同一基本塊的語句會共享相同的覆蓋信息,計算得到的排名也會相同,因此需要檢查更多的程序?qū)嶓w才能檢測到錯誤[6],導(dǎo)致其定位精度降低.為了解決上述問題,研究人員提出了基于變異的錯誤定位方法來協(xié)助錯誤定位.基于變異的錯誤定位方法是一種基于變異分析的方法[7],擁有較高的錯誤定位精度.依據(jù)對變異體的分析角度,基于變異的錯誤定位方法分為兩種,Metallax-fl[8]和MUSE[9].Metallax-fl 采用變異分析的思想,將變異體視為被測程序的相似版本[8]；MUSE 結(jié)合了變異分析,將變異體視為被測程序的部分修復(fù)[9].Pearson 等的研究表明,Metallax-fl 在錯誤定位精度和效率方面都優(yōu)于MUSE[10].

基于變異的錯誤定位方法雖然有較高的錯誤定位精度,但伴隨巨大的執(zhí)行開銷[11].因此研究人員著力于降低其執(zhí)行開銷,主要從3 個方面進(jìn)行：(1)減少變異體的數(shù)量；(2)減少測試用例的數(shù)量；(3)優(yōu)化執(zhí)行過程.Mathur 等提出的SELECTIVE 策略通過選擇部分變異算子來替代原始的變異算子集合,從而減少生成的變異體數(shù)量[12].另一方面,SAMPLING 方法通過從變異體集合中抽取部分變異體來減少變異體的數(shù)量[11].從測試用例角度,de Oliveira 等提出了FTMES,該方法只采用失敗測試用例執(zhí)行變異體,用通過測試用例的覆蓋信息作為變異殺死信息來減少測試用例的執(zhí)行開銷[13].優(yōu)化執(zhí)行過程方面,Liu 等提出的DMES 策略通過動態(tài)優(yōu)化變異體和測試用例的執(zhí)行來提升MBFL 的效率[14].

由于MBFL 執(zhí)行開銷約減策略中,約減測試用例角度的研究工作很少,并受Yoo 等的工作啟發(fā)[15],測試用例在程序測試過程中含有不同的信息或作用,本文提出一種基于信息熵的測試用例約減策略,IETCR,利用信息熵理論對通過測試用例進(jìn)行排名,最終選擇部分檢錯能力強(qiáng)的通過測試用例和所有失敗測試用例,從而減小MBFL 的執(zhí)行開銷.進(jìn)一步的實驗證明該策略能有效降低MBFL 開銷,而且沒有明顯降低錯誤定位精度.

2 相關(guān)背景

2.1 基于變異的錯誤定位技術(shù)

基于變異的錯誤定位技術(shù)是一種基于變異分析的錯誤定位方法.變異分析的概念由Demillo 等首先提出,通過對被測程序的源代碼進(jìn)行微小的改變[16],然后生成錯誤程序,也就是變異體[17].生成變異體的規(guī)則被稱為變異算子[18].在變異分析的過程中,如果一個變異體的執(zhí)行結(jié)果不同于原始程序的結(jié)果,那么這個變異體被殺死,記為killed 或distinguished,反之則為not killed 或alive.

基于變異的錯誤定位技術(shù)的提出,建立在變異體的行為和部分含真實錯誤的被測程序的表現(xiàn)極為相似這一基礎(chǔ)上[1],變異體與測試用例集錯誤檢測有很強(qiáng)的聯(lián)系.基于變異的錯誤定位技術(shù)主要包含以下4 個步驟：

(1)獲得被失敗測試用例覆蓋的語句：將測試用例T執(zhí)行被測程序P,獲得覆蓋信息和執(zhí)行結(jié)果(pass 或fail).然后將測試用例劃分為通過測試用例集合Tp和失敗測試用例集合Tf.結(jié)合覆蓋信息可獲得被失敗測試用例覆蓋的語句集合,用Covf表示[19].

(2)生成和執(zhí)行變異體：采用不同變異算子,對失敗測試用例覆蓋的語句植入錯誤生成變異體.對某一條語句s,使用不同變異算子會生成不同的變異體,變異體集合記為M(s).然后測試用例執(zhí)行所有的變異體,依據(jù)執(zhí)行結(jié)果,Tk為殺死變異體的測試用例集合,Tn為未殺死變異體的測試用例集合.

(3)計算程序語句懷疑度：變異體的懷疑度根據(jù)以下4 個參數(shù)計算得到：anp=|Tn∩Tp|,akp=|Tk∩Tp|,anf=|Tn∩Tf|,akf=|Tk∩Tf|.其中,anp表示通過測試用例中未殺死變異體的數(shù)量,akp表示通過測試用例中殺死變異體的數(shù)量,anf表示失敗測試用例中未殺死變異體的數(shù)量,akf表示失敗測試用例中殺死變異體的數(shù)量.表1列舉了5 個研究人員常用的懷疑度計算公式.計算出變異體的懷疑度,將某條語句對應(yīng)的變異體集合的懷疑度最大值賦值為該條語句的懷疑度.

表1 常用懷疑度計算公式

(4)生成錯誤定位報告：依據(jù)程序語句懷疑度的大小,降序排列生成程序語句排名表.開發(fā)人員可以根據(jù)排名表從上至下查找并修正程序錯誤.

2.2 MBFL 的開銷約減策略

基于變異的錯誤定位技術(shù)在已有的研究工作中表現(xiàn)出較高的錯誤定位精度,但伴隨著巨大的時間開銷,為了提升該技術(shù)的效率,研究人員從3 個方面提出了優(yōu)化策略：

(1)減少變異體的數(shù)量：這項策略旨在減少變異體數(shù)量,因為更少的變異體被執(zhí)行,那么變異執(zhí)行開銷相應(yīng)也就減小.從減少變異算子的角度,Papadakis 等提出一種變異算子約減策略SELECTIVE,該策略針對變異算子定義了特別的“充分準(zhǔn)則”[16].依照準(zhǔn)則,一些更“充分”的變異算子會被保留下來用于生成變異體,其余貢獻(xiàn)值更小的則被忽略,從而減少變異體的數(shù)量.從直接減少變異體的角度,SAMPLING 策略隨機(jī)從全體變異體集合中抽取固定比例的變異體用于執(zhí)行測試用例[8].Liu 等提出的SOME 策略從語句層面對變異體進(jìn)行抽樣[25].

(2)減少測試用例的數(shù)量：該策略通過減少測試用例在變異體上的執(zhí)行數(shù)量來減少執(zhí)行開銷.de Oliveira等提出了FTMES,用通過測試用例的覆蓋信息代替其變異體殺死信息,對變異體只執(zhí)行失敗測試用例,進(jìn)而約減了變異體執(zhí)行通過測試用例的開銷[13].由于通過測試用例對錯誤定位仍然具有一定的價值,FTMES策略會造成定位精度的損失.

(3)優(yōu)化執(zhí)行過程：該策略通過優(yōu)化變異體和測試用例的執(zhí)行過程來減少開銷.Liu 等提出一項動態(tài)變異體執(zhí)行優(yōu)化策略DMES,其包括兩種優(yōu)化方案,變異體執(zhí)行優(yōu)化MEO 和測試用例執(zhí)行優(yōu)化TEO[14].DMES使用了變異體全集和測試用例全集,因此可以結(jié)合其他策略,進(jìn)一步約減MBFL 的執(zhí)行開銷.

本文提出的IETCR 策略,是一種減少測試用例執(zhí)行的策略.該策略與FTMES 的研究角度相同,但FTMES對變異體只執(zhí)行了失敗測試用例,忽略了通過測試用例,而IETCR 策略同時保留了通過和失敗測試用例,進(jìn)而減少了錯誤定位精度的損失.

3 基于信息熵的測試用例約減策略

測試用例集中每個測試用例的檢錯能力不同,且測試用例間存在冗余,檢錯能力強(qiáng)的測試用例能提高被測程序中錯誤語句,降低非錯誤語句在懷疑度表中的排名；反之,檢錯能力弱的測試用例則降低錯誤語句,提高非錯誤語句在懷疑度表中的排名.因此,為了減少MBFL 執(zhí)行的測試用例個數(shù),提高運行效率,應(yīng)該選擇檢錯能力強(qiáng)的測試用例,去除檢錯能力弱的測試用例.本文使用信息熵作為測試用例檢錯能力的衡量指標(biāo),并據(jù)此提出了一種基于信息熵的測試用例約減方法IETCR (Information Entropy based Test Case Reduction).該方法選擇全部失敗的測試用例和少量有價值的通過測試用例進(jìn)行錯誤定位,減少了測試用例的數(shù)量,同時保證了測試用例集的質(zhì)量,不會造成明顯的錯誤定位精度損失.

3.1 測試用例的信息熵

信息熵是指信息中排除了冗余后的平均信息量,由信息論之父Shannon 提出[26].任何信息都存在冗余,冗余大小與信息中每個符號的出現(xiàn)概率(不確定性)有關(guān),出現(xiàn)的概率大,不確定性小；反之不確定性大.令不確定函數(shù)為F,概率為P,從上述信息熵的定義可知,不確定函數(shù)F是概率P的減函數(shù),兩個獨立符號所產(chǎn)生的不確定性應(yīng)該等于各自的不確定性之和,如式(1)所示：

若信源符號有n種取值,U={u1,u2,···,un},對應(yīng)的概率P={p1,p2,···,pn},則信源的信息熵如式(2)所示：

錯誤定位是一個依據(jù)測試用例提供的執(zhí)行結(jié)果信息,消除軟件中錯誤語句不確定性的過程,該過程中的信息量可以用信息熵表示.依據(jù)上述信息熵的基本概念,在錯誤定位的過程中,被測程序program={s1,s2,···,sm}由m條語句組成,假設(shè)其中只有一條語句包含錯誤,且每條語句是否為錯誤語句不確定,則被測程序即可作為信源,程序中每條語句對應(yīng)信息中的每個符號,語句是錯誤語句的概率為信息中對應(yīng)符號出現(xiàn)的概率,因此,錯誤定位過程中的信息量可用信息熵衡量,信息熵越小,表明軟件中錯誤語句的不確定性越??；反之不確定性越大.

測試用例的檢錯能力可以用引入該測試用例后,錯誤定位過程中信息熵的下降程度衡量.錯誤定位的過程中,依據(jù)測試用例執(zhí)行結(jié)果提供的信息來確定錯誤語句出現(xiàn)的位置,消除軟件中錯誤語句的不確定性,因此,一個測試用例的性能就可以用引入該測試用例后,錯誤定位過程信息熵的下降程度來衡量.執(zhí)行測試用例后,錯誤定位過程信息熵下降的程度大,表明該測試用例能很好地區(qū)分被測程序中的錯誤語句和其他語句；反之則說明這一測試用例不能有效區(qū)分被測程序中的語句,執(zhí)行該測試用例對錯誤定位的結(jié)果貢獻(xiàn)不大.基于這一思路,可以按照檢錯能力對測試用例進(jìn)行排序,在錯誤定位的過程中只選擇排名靠前,性能優(yōu)異的測試用例執(zhí)行,從而減少執(zhí)行的測試用例數(shù)量,降低錯誤定位過程中的執(zhí)行開銷.

使用歸一化后的語句懷疑度值估計語句為錯誤語句的概率,進(jìn)而計算測試用例的信息熵.SBFL 方法執(zhí)行開銷小,只需測試用例的執(zhí)行結(jié)果和覆蓋信息即可計算被測程序語句的懷疑度值,因此,可以使用歸一化后的語句懷疑度值表示該語句是否為錯誤語句的概率.具體而言,給定包含m條語句的被測程序program={s1,s2,···,sm} 和包含n個測試用例的測試用例集T={t1,t2,···,tn},移除測試用例ti后的測試用例集用Tremove?i={t1,···,ti?1,ti+1,···,tn} 表示,S us(s|Tremove?i)表示使用測試用例集Tremove?i計算得到的語句si的懷疑度值,P(si|Tremove?i)表示該語句為錯誤語句的概率,如式(3)所示：

計算出每個語句為錯誤語句的概率,就可計算出錯誤定位過程中整個測試用例集的信息熵,如式(4)所示：

移除指定測試用例前后,信息熵的差值即為該測試用例的信息熵,計算過程如式(5)所示.H(ti)越小,說明執(zhí)行測試用例ti后,錯誤定位過程的信息熵越低,錯誤語句的不確定性越小,錯誤定位結(jié)果越好,該測試用例應(yīng)該被保留；反之該測試用例應(yīng)該被移除.

依據(jù)信息熵理論,可以將測試用例集中每個測試用例的檢錯能力進(jìn)行量化,為測試用例的約減提供重要信息.將測試用例按照信息熵從小到大排序,得到測試用例執(zhí)行序列,排在序列前端的測試用例能更加有效地區(qū)分被測程序中的錯誤語句和其他語句,因此被優(yōu)先執(zhí)行.

3.2 IETCR 方法框架

IETCR 使用信息熵衡量測試用例的檢錯能力,選擇全部失敗的測試用例和少量有價值的通過測試用例進(jìn)行錯誤定位,減少了執(zhí)行的測試用例數(shù)量,同時保證整個測試用例集的質(zhì)量,具體執(zhí)行框架如圖1所示.

圖1 IETCR 方法框架

圖1中,IETCR 分為4 個階段,第一階段為測試用例執(zhí)行階段,被測程序執(zhí)行測試用例集,測試用例的語句覆蓋信息和執(zhí)行結(jié)果信息被收集；第二階段為測試用例約減階段,依據(jù)第一階段獲得的測試用例執(zhí)行結(jié)果信息,將測試用例集分成通過的測試用例(passed test cases)和失敗的測試用例(failed test cases)兩部分.對于執(zhí)行通過的測試用例,計算每個測試用例的信息熵,并按信息熵從小到大排列成一個執(zhí)行序列；對于執(zhí)行失敗的測試用例,則全部加入到下一階段的測試用例執(zhí)行序列中.從排好序的通過測試用例序列中選擇與失敗測試用例個數(shù)相同的通過測試用例加入下一階段的測試用例執(zhí)行序列中,作為第三階段變異體執(zhí)行的測試用例集；第三階段為變異體生成和執(zhí)行階段,依據(jù)變異算子定義的規(guī)則,對被失敗測試用例所覆蓋的語句植入故障,生成大量的變異體,每一個變異體都要執(zhí)行第二階段選擇出來的測試用例集,并記錄變異體在測試用例上的執(zhí)行結(jié)果信息；第四階段為懷疑度表生成階段,首先依據(jù)第三階段得到的變異體執(zhí)行信息,選擇合適的懷疑度公式,計算每個變異體的懷疑度值,然后再依據(jù)變異體的懷疑度值計算可疑語句的懷疑度值,最后將可疑語句按懷疑度值從大到小排序,即可得到故障程序的懷疑度表.開發(fā)者按照懷疑度表中的順序依次檢查源代碼,直到準(zhǔn)確定位程序中的故障.

IETCR 方法的有效性取決于每個通過測試用例的信息熵,信息熵計算的越準(zhǔn)確,使用IETCR 方法所取得的效果越好.最新提出的SBFL 懷疑度公式是Dstar,試驗結(jié)果表明,Dstar 公式在定位單錯誤和多錯誤時都具有高于其他懷疑度公式的錯誤定位精度[23].因此,本文使用Dstar 公式計算測試用例的信息熵.具體算法如算法1 所示.

算法1.基于信息熵的測試用例約減輸入：被測程序P,測試用例集T輸出：約減后的測試用例集合reducedTestCaseSet 1.Cov,R ← execute(P,T)；2.for all s in P do 3.Sus(s)；4.failed,passed ← split(T,R)；5.failedNum ← size(failed)；?6.entropySet ←；7. H(T) ← getEntropy(T)；8.for test case t in passed do Tremove?i Tremove?i 9.H() ← getEntropy()；Tremove?i 10.entropySet ← H(T) - H()；11.end for 12.reducedTestCaseSet ← failed；13.sorted(entropySet)；14.reducedTestCaseSet ← select(entropySet,failedNum)；15.return reducedTestCaseSet；

算法1 描述了使用IETCR 方法進(jìn)行測試用例約減的偽代碼,算法的輸入是被測程序P和對應(yīng)的測試用例集T,輸出為約減后的測試用例集合reduced-TestCaseSet.IETCR 首先獲取測試用例的語句覆蓋信息Cov和測試用例的執(zhí)行結(jié)果R,并使用這些執(zhí)行信息計算出被測程序中語句的懷疑度值(1～3 行),接著依據(jù)測試用例的執(zhí)行結(jié)果,將測試用例分為失敗的測試用例和通過的測試用例,并且記錄失敗測試用例的數(shù)量,初始化EntropySet,以便之后測試用例的選擇(4～6 行),計算出T的信息熵(7 行),最后對Tp中的每一個測試用例,計算其信息熵并加入到EntropySet(8～11 行),至此,測試用例信息熵的計算完成,接下來依據(jù)信息熵選擇要執(zhí)行的測試用例.先將failed加入到reducedTestCaseSet(12 行),然后對EntropySet中通過的測試用例按信息熵從小到大排序(13 行),依次將前failedNum個測試用例加入到reducedTestCaseSet并返回(14～15 行),到此整個算法結(jié)束.

3.3 IETCR 方法示例

結(jié)合具體示例,對算法1 中的關(guān)鍵步驟(8～14 行)進(jìn)行詳細(xì)介紹.在表2中,從左往右,第一列為被測程序的源碼,接下來的6 列分別為6 個測試用例及其覆蓋被測程序的信息,其中“1”表示覆蓋,“0”表示不覆蓋,最后一列為使用懷疑度公式Dstar 計算出的語句懷疑度值.倒數(shù)第二行為測試用例的執(zhí)行結(jié)果信息,倒數(shù)第一行是使用公式Dstar 計算得到的通過測試用例的信息熵.在上表中,按信息熵從小到大排序后的測試用例執(zhí)行序列為Tp={t1,t6,t3,t4},選擇與失敗測試用例相同數(shù)量的通過測試用例執(zhí)行,因此,約減后的測試用例序列為TR={t1,t2,t5,t6}.

表2 被測程序及其測試用例覆蓋信息

表3描述了示例被測程序生成的變異體及在測試用例上的執(zhí)行信息.從左到右,第1 列為被測程序的源代碼,第2 列為對應(yīng)語句生成的變異體集合,第3 列劃分為6 部分,分別是6 個測試用例在變異體上的執(zhí)行信息,其中“1”表示測試用例殺死對應(yīng)的變異體,“0”表示測試用例沒有殺死對應(yīng)的變異體,最后一列分為兩部分,“original”表示使用原始MBFL 方法,變異體對應(yīng)的懷疑度值,‘IETCR’表示使用IETCR 方法,變異體對應(yīng)的懷疑度值,加粗部分為對應(yīng)語句生成的變異體中懷疑度值的最大值.

表3 被測程序變異體及其執(zhí)行結(jié)果信息

在上述示例中,IETCR 方法只執(zhí)行了4 個測試用例,降低了33.3%的執(zhí)行開銷,同時沒有任何精度損失.具體而言,首先使用SBFL 技術(shù)和懷疑度公式Dstar計算被測程序中語句的懷疑度值,然后依據(jù)式(5)計算出每個通過測試用例的信息熵,以測試用例t1為例,當(dāng)執(zhí)行全部的測試用例時H(T)=3.700439717995333,將t1從測試用例集中移除,此時測試用例的信息熵H(Tremove?1)=3.7004397179680146,因此,t1消除的信息熵H(t1)=2.73e-11.同理,t3,t4,t6消除的信息熵分別為3.91e-10,3.91e-10,2.73e-11.根據(jù)上述測試用例的信息熵,IETCR 方法選擇其中信息熵最低的兩個測試用例t1和t6加入執(zhí)行序列,對于t3和t4將不在執(zhí)行.執(zhí)行測試用例t1,t2,t5,t6,使用測試用例在變異體上的執(zhí)行信息計算對應(yīng)變異體的懷疑度值,如表3IETCR 列所示.與原始MBFL 相比,使用IETCR 方法計算出的語句懷疑度值沒有發(fā)生變化,錯誤語句3 排在懷疑度表的首位,被優(yōu)先檢查.在上述示例中,與原始MBFL 相比,IETCR 少執(zhí)行了 2 ×35=70次MTP,降低了33.3%的執(zhí)行開銷,而且沒有任何精度損失.

4 實驗評估

4.1 研究問題

為了評估IETCR 方法的有效性,本文從錯誤定位精度和約減率兩方面出發(fā),提出如下研究問題.

RQ1：與原始MBFL 方法以及其他測試用例約減方法FTMES,SAMP 30%相比,IETCR 方法的約減率如何?

RQ2：與原始MBFL 方法以及其他測試用例約減方法FTMES,SAMP 30%相比,IETCR 方法的錯誤定位精度如何?

RQ3：IETCR 方法的影響因素和額外執(zhí)行開銷有哪些?

4.2 實驗對象與環(huán)境配置

針對以上研究問題,本文選擇了錯誤定位領(lǐng)域常用的軟件基準(zhǔn)程序庫(Software-artifact Infrastructure Repository,SIR)[27]中的6 個程序作為實驗對象,分別為printtokens,schedule,totinfo,tcas,sed,grep.這些程序均為開源的C 程序.以上程序共包含了117 個錯誤版本,部分版本錯誤語句無法植入故障生成有效變異體,因此測試用例無法檢測出該版本中的錯誤,或者執(zhí)行過程中出現(xiàn)異常,無法搜集到完整的執(zhí)行信息.在本文中,選擇了其中100 個錯誤版本程序作為實驗對象.表4列出了具體信息.在進(jìn)行實驗時,使用Gcov[28]搜集測試用例的語句覆蓋信息,利用軟件測試領(lǐng)域中廣泛使用的變異測試工具Proteum/IM2.0[29]來對被測程序語句進(jìn)行變異,獲取變異體相關(guān)信息.所有的實驗都運行在Linux (系統(tǒng)版本 3.10.0-957.c17.x86-64,CPU Intel(R) Gold 6240 @2.60 GHz 18 cores)系統(tǒng)下.

表4 實驗基準(zhǔn)程序相關(guān)信息

4.3 評估指標(biāo)

對于錯誤定位精度,本文使用EXAM Score[16]和TOP-N%[30,31]衡量,同時使用秩和檢驗分析測試用例約減方法與原始MBFL 之間是否存在顯著性差異.EXAM Score 是錯誤定位領(lǐng)域廣泛使用的評價指標(biāo)之一,使用發(fā)現(xiàn)錯誤語句時,檢查的語句數(shù)量占需要檢查的語句總數(shù)量的百分比來表示,因此,EXAM Score 值越小,表明錯誤定位精度越高,具體如式(6)所示.式(6)中Rank表示錯誤語句的排名,Number表示被檢查語句的數(shù)量.在實際的錯誤定位中,很多語句具有相同的懷疑度值,這就導(dǎo)致了它們在懷疑度表中具有相同的排名,在最理想的情況下,實際錯誤語句被第一個檢查,在最糟糕的情況下,實際錯誤語句被最后一個檢查.對于懷疑度相同的語句,本文使用它們的平均排名來計算錯誤定位精度.

TOP-N%表示檢查N%的代碼時,能定位被測程序中錯誤的百分比,用來衡量錯誤定位方法能否準(zhǔn)確定位被測程序中的部分錯誤.在錯誤定位過程中,能精確定位小部分錯誤比模糊定位大部分錯誤更有實用意義.秩和檢驗是一種非參數(shù)檢驗,不依賴于總體分布的具體形式,本文用來分析兩種錯誤定位方法的錯誤定位精度之間是否存在顯著性差異[32].

本文使用MTP (Mutant-Test-Pair)執(zhí)行次數(shù)衡量方法的執(zhí)行開銷,通過約減率評估對應(yīng)方法降低MBFL執(zhí)行開銷的程度.使用MTP 次數(shù)作為錯誤定位方法執(zhí)行開銷的衡量指標(biāo),評估的準(zhǔn)確度不受具體實現(xiàn)與使用環(huán)境的影響[33].約減率是指對應(yīng)方法減少的MTP 次數(shù)所占的百分比,約減率越大,方法降低MBFL 執(zhí)行開銷的程度越大.

對于RQ1,RQ2,RQ3 中的問題,實驗使用表1中的5 個懷疑度公式,通過原始MBFL,SAMP 30%,FTMES等方法,對表4中6 個程序共100 個版本進(jìn)行錯誤定位,統(tǒng)計每個版本的EXAM Score,方法運行時間和執(zhí)行的MTP 次數(shù).為了保證對比效果,對于SAMP 30%方法,同時重復(fù)試驗50 次,消除隨機(jī)抽樣對本組試驗的影響.

4.4 實驗結(jié)果

4.4.1 約減效率

為了探究RQ1,本文選擇了測試用例約減方法SAMP 30%,FTMES 和原始MBFL 作為對照組,使用表1中的5 個懷疑度公式,分別統(tǒng)計它們在上述6 個程序100 個版本中定位錯誤所執(zhí)行的MTP 次數(shù),試驗結(jié)果示例如圖2,是上述6 個程序中的printtokens,在柱狀圖中,X 軸代表對應(yīng)程序中的版本號,Y 軸代表執(zhí)行的MTP次數(shù),每一列包含4 部分,從下往上依次是IETCR,FTMES,SAMP 30%和原始MBFL,分別用黑色,深灰,淺灰和白色表示.所有程序結(jié)果如圖3所示.

圖2 MBFL 約減方法的執(zhí)行開銷示例 (printtokens)

圖3 MBFL 約減方法的執(zhí)行開銷

圖3中,大多數(shù)情況下,黑色部分明顯小于白色部分,特別是在被測程序tcas 中,表明與原始MBFL 相比,IETCR 方法可以顯著降低執(zhí)行開銷.圖中深灰部分所占的比例最小,說明在以上3 種方法中,FTMES 定位錯誤執(zhí)行的MTP 次數(shù)最少.

為了更準(zhǔn)確地進(jìn)行比較,表5列出了IETCR,FTMES,SAMP 30%在實驗程序中的平均約減率.

表5 IETCR,FTMES,SAMP 30%方法的約減率(%)

如表5所示,IETCR 方法的約減率(71.0%)介于FTMES(82.8%) 和SAMP 30%(70.0%) 方法之間,FTMES 方法的約減率最高.其原因是,FTMES 只執(zhí)行了失敗的測試用例,而本文提出的方法IETCR 不僅執(zhí)行了失敗的測試用例,還執(zhí)行了同等數(shù)量的通過測試用例.由于同時執(zhí)行了少量有價值的通過測試用例,IETCR 方法的錯誤定位精度優(yōu)于FTMES 方法,具體比較見4.4.2 節(jié).

4.4.2 方法的錯誤定位精度

為了探究RQ2,本文選擇了原始MBFL,測試用例約減方法FTMES,SAMP 30%作為對照組,同時使用表1中的5 個懷疑度公式,統(tǒng)計它們在上述實驗程序中的EXAM Score,試驗結(jié)果如圖4所示.圖4共包含5 部分,對應(yīng)5 個不同的MBFL 懷疑度公式.在每個子圖中,X 軸表示不同的測試用例約減方法,Y 軸表示對應(yīng)方法的EXAM Score,子圖中每一個類似小提琴的部分都表示一種測試用例約減方法在上述實驗程序上的錯誤定位精度分布,其中,外部形狀為核密度估計,內(nèi)部白色的點是中位數(shù),黑色盒型的范圍是下四分位點到上四分位點.對應(yīng)方法的錯誤定位精度分布在Y 軸較低位置的寬度越寬,較高位置的寬度越窄,表示對應(yīng)的方法定位錯誤需要檢查的語句越少,錯誤定位精度越高.

在圖4的全部5 個懷疑度公式中,本文提出的方法IETCR 幾乎與原始MBFL 具有相同的數(shù)據(jù)分布,與其他方法相比,IETCR 方法EXAM Score 的分布更接近原始MBFL.因此,與原始MBFL 相比,IETCR 沒有明顯降低錯誤定位精度,并且明顯優(yōu)于其他測試用例約減方法SAMP 30% 和FTMES.對于SAMP 30%,FTMES 方法而言,錯誤定位效果較好的是SAMP 30%,FTMES 次之.

為了更加精確地比較IETCR 方法的定位效果,表6分別列出了原始MBFL,IETCR,SAMP(30%)方法的EXAM Score 值在不同檢查比例下所占的百分比,即TOPN%值.從表6中的數(shù)據(jù)可觀察到,使用IETCR 方法的錯誤定位精度幾乎等同于原始MBFL 技術(shù),優(yōu)于現(xiàn)有方法FTMES 和SAMP 30%.具體而言,以第3 行前兩列<1%,0.31>為例,表示使用懷疑度公式Jaccard(JA)對所有版本檢查1%的代碼時,原始MBFL 方法可以定位其中31%的錯誤,加粗部分表示使用對應(yīng)懷疑度公式和檢查比例,原始MBFL,IETCR,SAMP 30%方法定位錯誤百分比的最大值.使用全部懷疑度公式,對所有版本檢查1%的代碼,IETCR 方法定位到的錯誤所占比例為：0.29(JA),0.29(OC),0.27(OP),0.02(TA),0.28(DS),原始MBFL 能夠定位到的錯誤比例為：0.31(JA),0.31(OC),0.27(OP),0.05(TA),0.30(DS),與原始MBFL 方法相比,IETCR 定位錯誤的百分比減少程度不超過3%,并且明顯優(yōu)于FTMES 和SAMP 30%方法,進(jìn)一步說明IETCR 方法能夠精準(zhǔn)定位被測程序中的錯誤,具有一定的實用價值,在錯誤定位領(lǐng)域,能精確定位少量錯誤,比模糊定位大量錯誤更具有實用意義.表中使用Jaccard(JA)公式檢查10%,15%,50%,60%的代碼時,IETCR 方法定位錯誤的比例高于原始MBFL,在錯誤定位精度方面有了一定提升.

圖4 MBFL 約減方法錯誤定位精度比較

表6 MBFL,IETCR,FTMES,SAMP 30%錯誤定位精度比較

為了分析IETCR 方法與原始MBFL,FTMES,SAMP 30%方法之間是否存在顯著性差異,本文在置信度為95% 的水平下對上述方法進(jìn)行了秩和檢驗(Wilcoxon signed-rank test),試驗結(jié)果如表7所示.表中包括5 個懷疑度公式,每個對應(yīng)的值包括兩部分,第一部分為對應(yīng)方法在所有被測程序中EXAM Score 的平均值,括號中的值為對應(yīng)方法與IETCR 方法秩和檢驗的P-Values 值.加粗部分對應(yīng)的P-Values 值大于0.05,表示對應(yīng)方法與原始MBFL 之間沒有存在顯著差異.依據(jù)表中數(shù)據(jù),IETCR 方法與原始MBFL 之間不存在顯著性差異,與FTMES,SAMP 30%方法(Tarantula 公式除外)之間存在顯著性差異

表7 顯著性分析

4.4.3 方法的影響因素

為探討RQ3,本文從計算測試用例信息熵的懷疑度公式和信息熵的計算過程出發(fā),討論IETCR 的影響因素和額外開銷.

本節(jié)首先研究不同SBFL 公式的定位效果,并選擇性能最優(yōu)的懷疑度公式用于IETCR 方法中測試用例信息熵的計算.實驗使用5 種不同的SBFL 公式,對上述實驗程序中的錯誤進(jìn)行定位,實驗結(jié)果如表8所示.表8列出了不同SBFL 公式的EXAM Score 值在不同檢查比例下所占的百分比,其中加粗部分表示使用對應(yīng)懷疑度公式和檢查比例,SBFL 公式定位錯誤百分比的最大值.從表中數(shù)據(jù)可知,所有檢查比例中,使用Dstar(DS)公式均能定位最多的錯誤,說明在上述SBFL 公式中,Dstar(DS)的性能最優(yōu).因此,本文使用Dstar 公式計算測試用例的信息熵.

表8 SBFL 方法錯誤定位精度比較

本節(jié)其次討論IETCR 的額外時間開銷.本文統(tǒng)計了該方法在實驗程序上計算信息熵的時間開銷,如圖5所示.在圖5中,橫坐標(biāo)表示不同的實驗程序,縱坐標(biāo)表示執(zhí)行時間,單位是秒,圖中每一部分表示IETCR方法在對應(yīng)實驗程序上計算全部通過測試用例的信息熵所花費時間的分布情況,其中包括5 個數(shù)值點,從下到上依次為最小值,下四分位數(shù),中位數(shù),上四分位數(shù),最大值.

由圖5可知,IETCR 方法在6 個程序上測試用例的信息熵計算時間范圍為20～800 s,其中執(zhí)行時間最少的程序是totinfo,最大的程序是printtokens,有3 個程序的平均執(zhí)行時間少于200 s,相比IETCR 方法約減的變異體執(zhí)行開銷,這些額外執(zhí)行時間是可以忽略不計的.因此,IETCR 有更好的約減效果,同時伴隨著少量測試用例信息熵的計算開銷.

圖5 IETCR 方法額外執(zhí)行開銷

5 結(jié)論與展望

為了降低基于變異的錯誤定位技術(shù)的執(zhí)行開銷,本文從測試用例角度,提出了一種基于信息熵的測試用例約減策略IETCR,利用信息熵理論對通過測試用例進(jìn)行排序,選擇執(zhí)行部分檢錯能力強(qiáng)的通過測試用例和所有失敗測試用例,有效減少了測試用例的數(shù)量,同時保證了測試用例集的質(zhì)量.實驗結(jié)果表明,IETCR方法能夠約減56.3%～88.6%的執(zhí)行開銷,而錯誤定位精度與原始MBFL 技術(shù)沒有顯著性差異.在后續(xù)的研究中,作者將考慮擴(kuò)大數(shù)據(jù)集來驗證方法的有效性,并結(jié)合基于機(jī)器學(xué)習(xí)的變異體執(zhí)行結(jié)果預(yù)測方法,在不執(zhí)行變異體的前提下預(yù)測其被測試用例殺死與否的結(jié)果,更進(jìn)一步減少MBFL 技術(shù)的執(zhí)行開銷.