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

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

1 引言

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

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

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

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

2 相關(guān)背景

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

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

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

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

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

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

表1 常用懷疑度計(jì)算公式

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

2.2 MBFL 的開(kāi)銷約減策略

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

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

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

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

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

3 基于信息熵的測(cè)試用例約減策略

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

3.1 測(cè)試用例的信息熵

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

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

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

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

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

計(jì)算出每個(gè)語(yǔ)句為錯(cuò)誤語(yǔ)句的概率,就可計(jì)算出錯(cuò)誤定位過(guò)程中整個(gè)測(cè)試用例集的信息熵,如式(4)所示：

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

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

3.2 IETCR 方法框架

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

圖1 IETCR 方法框架

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

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

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

3.3 IETCR 方法示例

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

表2 被測(cè)程序及其測(cè)試用例覆蓋信息

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

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

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

4 實(shí)驗(yàn)評(píng)估

4.1 研究問(wèn)題

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

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

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

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

4.2 實(shí)驗(yàn)對(duì)象與環(huán)境配置

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

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

4.3 評(píng)估指標(biāo)

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

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

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

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

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 約減效率

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

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

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

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

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

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

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

4.4.2 方法的錯(cuò)誤定位精度

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

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

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

圖4 MBFL 約減方法錯(cuò)誤定位精度比較

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

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

表7 顯著性分析

4.4.3 方法的影響因素

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

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

表8 SBFL 方法錯(cuò)誤定位精度比較

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

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

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

5 結(jié)論與展望

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