基于高階變異的多錯(cuò)誤定位實(shí)證研究①

婁 琨,尚 穎,王海峰

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

1 引言

錯(cuò)誤定位是識(shí)別程序執(zhí)行過(guò)程中導(dǎo)致程序失敗的元素的過(guò)程[1].在軟件調(diào)試的眾多活動(dòng)中,錯(cuò)誤定位是其中最復(fù)雜耗時(shí)的活動(dòng)之一,尤其在大規(guī)模復(fù)雜程序中.為了減小定位錯(cuò)誤位置的人工成本,研究人員提出了眾多錯(cuò)誤定位方法,例如基于切片的方法[2],基于頻譜的方法[3,4],基于變異的方法等[5].

在眾多自動(dòng)化錯(cuò)誤定位方法中,基于頻譜的錯(cuò)誤定位(Spectrum-Based Fault Localization,SBFL)方法[3,4,6]是一種被廣泛應(yīng)用的方法.SBFL 考慮到程序元素的二元覆蓋矩陣,但局限于其錯(cuò)誤定位精度不高.目前的研究顯示基于變異的錯(cuò)誤定位方法比最新的基于頻譜的方法有更高的錯(cuò)誤定位精度[7,8].MBFL是一種基于變異測(cè)試[7]的方法[9].截止目前,MBFL 分為兩種技術(shù):Metallaxis-FL[5]和MUSE[9].研究表明[10,11],Metallaxis-FL的錯(cuò)誤定位效率和效果都要優(yōu)于MUSE,因此本文選擇Metallaxis-FL 作為MBFL 原始方法.

在MBFL 中,將一個(gè)程序p通過(guò)簡(jiǎn)單的語(yǔ)法變化生成一系列錯(cuò)誤程序p'(也就是變異體),生成變異體的規(guī)則被稱為變異算子.根據(jù)變異算子使用的次數(shù),變異體可以分成兩類:一階變異體(First-Order-Mutants,FOMs)和高階變異體(Higher-Order-Mutants,HOMs),其中FOMs是只使用一次變異算子生成,HOMs 則是通過(guò)多次使用變異算子生成[12].

在之前的MBFL 研究中,只有FOMs 用于定位單錯(cuò)誤程序[5,13].但Xue 等[14]發(fā)現(xiàn)定位多錯(cuò)誤更有困難,耗時(shí)且成本巨大,同時(shí)多錯(cuò)誤之間存在錯(cuò)誤干擾現(xiàn)象,導(dǎo)致現(xiàn)有錯(cuò)誤定位技術(shù)的定位效果較差.另一方面,Offutt 等[15]發(fā)現(xiàn)殺死HOMs是否能檢測(cè)出復(fù)雜錯(cuò)誤是不確定的.為填補(bǔ)這項(xiàng)研究?jī)?nèi)容,我們進(jìn)行了一項(xiàng)大規(guī)模的實(shí)證研究,研究HOMs是否能提升錯(cuò)誤定位的精度,同時(shí)分析不同類別的HOMs 與多錯(cuò)誤之間的關(guān)系.

本文中,我們著力研究FOMs和HOMs 在多錯(cuò)誤上的表現(xiàn).然后我們將HOMs 分成三類研究不同HOMs分類的錯(cuò)誤定位效果.在我們的實(shí)驗(yàn)設(shè)置中,首先應(yīng)用Agrawal 等[16]提出的變異算子生成FOMs,然后根據(jù)FOMs 構(gòu)建HOMs.特別地,針對(duì)多錯(cuò)誤定位場(chǎng)景,我們組合63 個(gè)單錯(cuò)誤程序生成100 個(gè)多錯(cuò)誤程序,錯(cuò)誤個(gè)數(shù)從2 個(gè)至5 個(gè).最后,我們將HOMs 分成3 類用于比較不同類別HOMs的表現(xiàn).

2 背景與動(dòng)機(jī)

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

基于變異的錯(cuò)誤定位技術(shù)是一種基于變異分析[8]的錯(cuò)誤定位方法.變異分析通過(guò)對(duì)被測(cè)程序進(jìn)行簡(jiǎn)單的語(yǔ)義改變,生成與原始程序不同的版本.這些人為植入錯(cuò)誤的程序被稱為變異體.生成變異體的規(guī)則被稱為變異算子.本文采用Agrawal 等[16]提出的C 語(yǔ)言的變異算子.

在變異分析中,依據(jù)變異體和原始程序不同的輸出,使用變異體來(lái)評(píng)估測(cè)試用例的質(zhì)量.如果一個(gè)測(cè)試用例的執(zhí)行結(jié)果不同于原始程序的結(jié)果,那么這個(gè)變異體就被殺死,記為killed 或detected,反之稱這些變異體沒(méi)有被殺死,即not killed 或live.

傳統(tǒng)基于變異的錯(cuò)誤定位技術(shù)主要包含以下4 個(gè)步驟:

(1)獲得失敗測(cè)試用例覆蓋的語(yǔ)句:將測(cè)試用例T執(zhí)行被測(cè)程序P,獲得覆蓋信息和執(zhí)行結(jié)果(pass 或fail).然后測(cè)試用例就可以區(qū)分為通過(guò)測(cè)試用例集合Tp和失敗測(cè)試用例集合Tf.被失敗測(cè)試用例覆蓋的語(yǔ)句集合記為covf.

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

(3)計(jì)算程序語(yǔ)句懷疑度:變異體的懷疑度可以用不同的MBFL 公式計(jì)算得到,這些公式都基于以下4 個(gè)參數(shù):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列舉了3 個(gè)研究人員常用的懷疑度計(jì)算公式(Ochiai[17],Tarantula[18],Dstar[19]).本文的實(shí)驗(yàn)中使用Ochiai 作為MBFL 公式,因?yàn)槠湓贛BFL 研究中被廣泛使用[5,9],且效果好于其他公式[13].計(jì)算完變異體的懷疑度,將某條語(yǔ)句對(duì)應(yīng)的變異體集合的懷疑度最大值賦值為該條語(yǔ)句的懷疑度.

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

表1 常用懷疑度公式

基于上述過(guò)程的描述,我們可以發(fā)現(xiàn)MBFL是基于“大部分失敗測(cè)試用例殺死的變異體與程序錯(cuò)誤有關(guān)”假設(shè)的研究工作,其理論基礎(chǔ)是基于以下兩類假設(shè)[20]:(1)將變異體視為是原被測(cè)程序的一種潛在修復(fù);(2)將變異體視為原被測(cè)錯(cuò)誤程序的近似版本.變異體執(zhí)行測(cè)試用例后的狀態(tài)有兩種:殺死(killed)和未殺死(not killed).其中,殺死狀態(tài)分為:被失敗測(cè)試用例殺死(akf)和被通過(guò)測(cè)試用例殺死(akp).在被失敗測(cè)試用例殺死的變異體,存在兩種情況:(1)變異體的狀態(tài)從失敗變成通過(guò),即程序被修復(fù);(2)變異體仍然為失敗,但輸出與原始程序不同.這兩種情況都有助于揭示錯(cuò)誤位置,第一種程序修復(fù)的情況,可以依據(jù)變異的位置來(lái)確定程序錯(cuò)誤的位置.第二種情況,變異體的輸出與原始程序不同,其有可能是對(duì)錯(cuò)誤位置變異而造成的輸出不同,此變異體的行為特征與錯(cuò)誤程序更加相似.另一方面,被通過(guò)測(cè)試用例殺死的變異體,其更可能是對(duì)正確語(yǔ)句進(jìn)行變異,造成輸出與原始程序不同.并且,Moon 等[9]的研究發(fā)現(xiàn),錯(cuò)誤語(yǔ)句生成的變異體在失敗測(cè)試用例下更容易通過(guò),而正確語(yǔ)句生成的變異體在通過(guò)測(cè)試用例下更容易失敗.

同時(shí),從表1變異體懷疑度公式中可以看出,變異體的懷疑度值與akf呈正相關(guān)關(guān)系,與akp呈負(fù)相關(guān)關(guān)系.本文通過(guò)計(jì)算變異體m在測(cè)試用例上akf與akp的差值來(lái)度量該變異體對(duì)錯(cuò)誤定位的影響程度,即貢獻(xiàn)度C(Contribution):

其中,T表示測(cè)試用例集,P表示被測(cè)程序.C(T,P,m)越高表示該變異體的貢獻(xiàn)度越高.

同理,對(duì)變異體集合M的平均貢獻(xiàn)度AC(Average Contribution)的計(jì)算公式為:

其中,|M|表示集合中變異體的數(shù)量.

目前研究人員對(duì)FOMs和HOMs 之間的關(guān)系進(jìn)行了研究.如Gopinath 等[21]的研究表明許多HOMs 與它們組成的FOMs 在語(yǔ)義上是不同的.然而,Langdon等[22]的研究表明被測(cè)試用例殺死的HOMs 數(shù)量高于殺死FOMs的數(shù)量,因此HOMs 相對(duì)于FOMs,更容易被測(cè)試用例檢出.

在早期的研究中,Offutt 等[15]指出:殺死n階變異體是否意味著我們可以檢出復(fù)雜錯(cuò)誤還有待確定.為了回答這個(gè)問(wèn)題,我們是第一個(gè)進(jìn)行關(guān)于比較FOMs和HOMs 在定位程序錯(cuò)誤上的控制實(shí)驗(yàn)的.

2.2 研究動(dòng)機(jī)

在先前的研究中,大部分MBFL 技術(shù)基于單錯(cuò)誤假設(shè)[5,9,13,23].然而,實(shí)證研究表明[24],單個(gè)程序失敗往往是由系統(tǒng)中的多個(gè)故障觸發(fā)的.Digiuseppe和Jones 發(fā)現(xiàn),多個(gè)錯(cuò)誤對(duì)錯(cuò)誤定位的精度有負(fù)面影響[25].

此外,Offutt的研究結(jié)果認(rèn)為,殺死n階變異體是否可以檢測(cè)到復(fù)雜的錯(cuò)誤還有待確定[15].在Debory和Wong的研究中[26],他們發(fā)現(xiàn)他們所提出的策略不能修復(fù)同一個(gè)程序中的多個(gè)錯(cuò)誤,是因?yàn)樗麄冎豢紤]了FOMs.換句話說(shuō),采用HOMs 來(lái)定位或修復(fù)程序中的多個(gè)缺陷是一種潛在可行的方法.因此,本文主要通過(guò)實(shí)證研究HOMs 在單錯(cuò)誤和多錯(cuò)誤程序上的定位效果,并分析多錯(cuò)誤與HOMs 之間的關(guān)系.

(1)HOMs 分類

依據(jù)變異體在程序中的不同變異位置,我們將HOMs分成3 類.為便于理解這3 類變異體,我們采用帶有兩個(gè)錯(cuò)誤(f1和f2)的程序p作為例子.首先,我們HOMf1為變異了錯(cuò)誤語(yǔ)句f1的HOMs 集合且HOMf1∈HOMs;HOMf2變異了錯(cuò)誤語(yǔ)句f2的HOMs 集合且HOMf2∈HOMs.

其次,如圖1所示,我們將HOMs 分為以下3 類:

類A:準(zhǔn)確高階變異體(Accurate HOMs).即,同時(shí)在錯(cuò)誤語(yǔ)句f1和f2 上變異生成的HOMs.(HOMf1∩HOMf2).

類B:部分準(zhǔn)確高階變異體(Partially accurate HOMs).即,只在錯(cuò)誤語(yǔ)句f1 或f2 上變異生成的HOMs.(HOMf1HOMf2)∪(HOMf2HOMf1)

類C:不準(zhǔn)確高階變異體(Inaccurate HOMs).即,在其他語(yǔ)句上變異生成的HOMs.(HOMs(HOMf1∪HOMf2)

上述3 種HOMs 反映出不同HOMs的生成方法.我們推測(cè)這3 類HOMs 在錯(cuò)誤定位上有不同的表現(xiàn).基于這種推測(cè),我們進(jìn)行了一次大規(guī)模的實(shí)證研究來(lái)分析3 類HOMs的特性.

(2)MBFL 例子

為進(jìn)一步說(shuō)明我們的研究動(dòng)機(jī),我們使用圖2中的例子來(lái)說(shuō)明FOMs和HOMs 如何在MBFL 上使用.

在圖2中,從左到右,第1 列為被測(cè)程序的源代碼,其中語(yǔ)句s4和s11為錯(cuò)誤語(yǔ)句.第2 列為對(duì)應(yīng)語(yǔ)句生成的變異體集合,第3 列劃分為6 部分,分別是6 個(gè)測(cè)試用例在變異體上的執(zhí)行信息,其中“1”表示測(cè)試用例殺死對(duì)應(yīng)的變異體,“0”表示測(cè)試用例沒(méi)有殺死對(duì)應(yīng)的變異體,第4和第5 列表示計(jì)算得到的變異體懷疑度和語(yǔ)句懷疑度,最后一列表示對(duì)應(yīng)語(yǔ)句的排名.在這個(gè)例子中,每一個(gè)變異體的懷疑度都是用Ochiai 公式計(jì)算的.在圖2中有兩個(gè)給出的結(jié)果,一個(gè)是FOMs的結(jié)果,另一個(gè)是HOMs的結(jié)果.

圖1 HOMs 分類

圖2 MBFL 例子

使用FOMs 進(jìn)行錯(cuò)誤定位.假設(shè)MBFL 技術(shù)在失敗測(cè)試用例覆蓋的每條語(yǔ)句只生成兩個(gè)變異體,該程序下共生成14 個(gè)FOMs(列“FOMs”所示).MBFL 首先利用測(cè)試用例的殺死信息計(jì)算FOMs的懷疑度(列“FOMs 懷疑度”所示).接下來(lái),同一語(yǔ)句生成的變異體中,取最大的懷疑度記為該語(yǔ)句的懷疑度.最后,在“排名”列中,MBFL 將錯(cuò)誤語(yǔ)句s4和s11都排在第3 位.

使用HOMs 進(jìn)行錯(cuò)誤定位.我們首先利用來(lái)自不同語(yǔ)句的兩個(gè)FOMs 構(gòu)造HOMs,最后生成3 類共14 條HOMs(列“HOMs”所示).計(jì)算得到的HOMs 懷疑度如列“HOMs 懷疑度”所示.接著,為保證公平性,我們通過(guò)計(jì)算語(yǔ)句相關(guān)HOMs 懷疑度的均值作為該語(yǔ)句的懷疑度.以語(yǔ)句s1為例子,與s1相關(guān)的HOMs 有3 個(gè)(HOM6,HOM11和HOM13),其對(duì)應(yīng)的懷疑度分別為1.00,0.41,和1.00.因此,計(jì)算得到的語(yǔ)句s1的懷疑度為Sus(s1)=(1.00+0.41+1.00)/3=0.80.最終,使用HOMs計(jì)算得到的語(yǔ)句懷疑度如列“語(yǔ)句懷疑度”所示.最終,HOMs 將錯(cuò)誤語(yǔ)句s4和s11分別排在第3 名和第2 名.

基于上述的例子,我們可以發(fā)現(xiàn)FOMs 將兩條錯(cuò)誤語(yǔ)句排在前五名,然而HOMs 將錯(cuò)誤語(yǔ)句排在前三名,表明HOMs 在這個(gè)例子中有更好的錯(cuò)誤定位效果.更進(jìn)一步,在高階變異錯(cuò)誤定位中,三類變異體對(duì)錯(cuò)誤定位有不同的貢獻(xiàn),結(jié)合式(2),準(zhǔn)確HOMs的平均貢獻(xiàn)度為:

部分準(zhǔn)確HOMs的平均貢獻(xiàn)度為:

不準(zhǔn)確HOMs的平均貢獻(xiàn)度為：

從以上結(jié)果可以看出,準(zhǔn)確HOMs的平均貢獻(xiàn)度等于部分準(zhǔn)確HOMs,不準(zhǔn)確HOMs的平均貢獻(xiàn)度最低.據(jù)我們所知,本文首次研究FOMs和HOMs 在多錯(cuò)誤程序上的定位效果.更進(jìn)一步,我們研究了三類HOMs的錯(cuò)誤定位效果并分析其差異.

3 實(shí)驗(yàn)設(shè)計(jì)

本章討論實(shí)驗(yàn)中使用的程序和實(shí)驗(yàn)設(shè)計(jì)流程,用以解決提出的研究問(wèn)題.圖3中顯示了實(shí)驗(yàn)研究設(shè)計(jì)流程.下面將依次介紹設(shè)計(jì)流程的每個(gè)部分.

圖3 實(shí)驗(yàn)設(shè)計(jì)流程

3.1 實(shí)驗(yàn)程序

本文選擇了錯(cuò)誤定位領(lǐng)域常用的軟件基準(zhǔn)程序庫(kù)(Subject Infrastructure Repository,SIR)[27]中的5 個(gè)程序作為實(shí)驗(yàn)對(duì)象,分別為printtokens2,schedule2,totinfo,tcas和sed.這些程序均為開源的C 程序,其中前4 個(gè)程序來(lái)自西門子套件(Siemens Suite),sed是大型的真實(shí)錯(cuò)誤程序.實(shí)驗(yàn)中使用的錯(cuò)誤版本和測(cè)試用例均可在SIR 庫(kù)中下載.這些程序在高階變異測(cè)試領(lǐng)域中廣泛使用[12,28-30],同時(shí)也經(jīng)常應(yīng)用在錯(cuò)誤定位等相關(guān)的研究中[18,19,23,26].因此我們認(rèn)為本文測(cè)試數(shù)據(jù)集所得出的結(jié)論具有一定的普適性.

表2列出了基準(zhǔn)程序的具體信息,包括程序名稱,程序所有的版本數(shù)量和實(shí)驗(yàn)中使用的數(shù)量,程序的平均代碼行以及FOMs和HOMs的數(shù)量.其中,FOMs 列的“生成的數(shù)量”子列表示對(duì)應(yīng)程序生成的FOMs 總數(shù),而“使用”子列表示實(shí)驗(yàn)中實(shí)際運(yùn)行的FOMs 總數(shù).本文共選擇了63 個(gè)單錯(cuò)誤版本程序作為實(shí)驗(yàn)對(duì)象,部分版本因?yàn)殄e(cuò)誤語(yǔ)句無(wú)法生成有效變異體而導(dǎo)致測(cè)試用例無(wú)法檢測(cè)出該版本的錯(cuò)誤,或因?yàn)閳?zhí)行過(guò)程中出現(xiàn)異常,無(wú)法收集到完整的執(zhí)行信息.

表2 實(shí)驗(yàn)基準(zhǔn)程序及變異體信息

3.2 生成變異體

為了研究FOMs和HOMs 在單錯(cuò)誤和多錯(cuò)誤程序中的表現(xiàn),實(shí)驗(yàn)首先需要生成FOMs和HOMs.在這個(gè)步驟中,我們收集被失敗測(cè)試用例覆蓋的程序語(yǔ)句,通過(guò)變異算子植入錯(cuò)誤到這些語(yǔ)句,進(jìn)而生成相應(yīng)的變異體.表3列出了Agrawal 等[16]提出的10 種經(jīng)典C 語(yǔ)言變異算子.

表3 經(jīng)典C 語(yǔ)言變異算子

對(duì)于生成FOMs,我們對(duì)fail 測(cè)試用例覆蓋的每條語(yǔ)句使用所有變異算子進(jìn)行變異,每次只對(duì)一條語(yǔ)句變異,最終生成161 218 個(gè)FOMs.表2“FOMs”列的“(使用)”子列中列出了每個(gè)程序所使用的FOMs數(shù)量.

對(duì)于生成高階變異體,在已有高階變異測(cè)試的研究中,對(duì)變異體階數(shù)的研究有所不同,有關(guān)注于階數(shù)較低(2 至4 階)的研究[15,28,29,31],也有關(guān)注階數(shù)較高(2 至15 階)的研究[12,32-35].本文首次考慮將高階變異體應(yīng)用于多錯(cuò)誤定位,然而在實(shí)際程序中錯(cuò)誤數(shù)量是不可知的,因此結(jié)合前人的研究成果,我們選擇生成2 至7 階的變異體來(lái)模擬多錯(cuò)誤情況.在此基礎(chǔ)上,為了進(jìn)一步探究不同變異位置的高階變異體與錯(cuò)誤定位的關(guān)系,我們依據(jù)不同的變異位置對(duì)變異體進(jìn)行了劃分,并通過(guò)理論和實(shí)驗(yàn)分析發(fā)現(xiàn)錯(cuò)誤語(yǔ)句處生成的變異體(如準(zhǔn)確HOMs和部分準(zhǔn)確HOMs)具有更優(yōu)的錯(cuò)誤定位效果.另一方面,考慮到MBFL 巨大的執(zhí)行開銷,我們選擇生成每階HOMs的數(shù)量與FOMs 數(shù)量相同來(lái)減少HOMs的數(shù)量.假設(shè)生成1000 個(gè)FOMs,然后2 階變異體和3 階變異體的數(shù)量也是1000;因此最終生成的HOMs為6000.在我們的實(shí)驗(yàn)中,采用一階變異算子FOP 構(gòu)建HOMs.具體來(lái)說(shuō),首先隨機(jī)選擇k條失敗測(cè)試用例覆蓋的語(yǔ)句,然后對(duì)每條選擇的語(yǔ)句,隨機(jī)選擇一個(gè)與其相對(duì)應(yīng)的一階變異算子,最終生成一個(gè)k階變異體.實(shí)驗(yàn)共生成967 308 個(gè)HOMs,其中實(shí)際使用的數(shù)量如表2所示(“HOMs”列的“(使用)”子列).

3.3 構(gòu)建多錯(cuò)誤定位場(chǎng)景

為了構(gòu)建實(shí)驗(yàn)中的多錯(cuò)誤定位場(chǎng)景,我們通過(guò)隨機(jī)組合SIR 庫(kù)中的原始單錯(cuò)誤程序獲得多錯(cuò)誤程序.每個(gè)多錯(cuò)誤程序中的錯(cuò)誤數(shù)量是2 到5 個(gè).最終生成100 個(gè)版本的多錯(cuò)誤程序.最后,依據(jù)多錯(cuò)誤程序生成的變異體,運(yùn)行變異體收集測(cè)試結(jié)果用于效果分析.

3.4 評(píng)估MBFL的效果

為了評(píng)估FOMs和HOMs 在MBFL 中的定位效果,我們使用了3 種研究人員常用的評(píng)估指標(biāo)[36-39].

(1)EXAM:EXAM[36,37]是錯(cuò)誤定位領(lǐng)域廣泛使用的評(píng)價(jià)指標(biāo)之一,用于評(píng)估開發(fā)人員找到準(zhǔn)確錯(cuò)誤位置之前需要檢查的程序?qū)嶓w的比例,因此EXAM值越小表明對(duì)應(yīng)的錯(cuò)誤定位效果越好[36,37].EXAM的公式定義如下:

式(6)中,分子是錯(cuò)誤語(yǔ)句的排名,分母是需要檢查的程序語(yǔ)句數(shù)量的總和.rank的計(jì)算公式為:

式(7)中,i表示懷疑度值大于錯(cuò)誤語(yǔ)句的正確語(yǔ)句的數(shù)量,j表示懷疑度值等于錯(cuò)誤語(yǔ)句的正確語(yǔ)句的數(shù)量.為更接近真實(shí)定位場(chǎng)景,我們選擇第i+1 位排名與第i+j位排名的平均作為錯(cuò)誤語(yǔ)句的排名.

(2)Top-N:Top-N 用于評(píng)估排名前N個(gè)程序候選元素中,能定位到真實(shí)錯(cuò)誤的個(gè)數(shù)[38].在Kochhar 等的研究發(fā)現(xiàn),73.58%的開發(fā)者只檢查排名前5的程 序元素,并且?guī)缀跛械拈_發(fā)者認(rèn)為檢查排名前10的程序元素是可接受的上限[39].因此,參考之前的研究[36,38],我們將N設(shè)定為1,3,5.同時(shí),假設(shè)兩條語(yǔ)句有相同的懷疑度,我們同樣計(jì)算這些語(yǔ)句排名的平均值(如式(7)所示).Top-N 越大表明對(duì)應(yīng)的錯(cuò)誤定位技術(shù)越好.

(3)MAP:MAP (Mean Average Precision)是信息檢索領(lǐng)域用于評(píng)估語(yǔ)句排序質(zhì)量的指標(biāo),是所有錯(cuò)誤平均精度的平均值[40].AP(Average Precision)的計(jì)算公式如下:

式(8)中,i是程序語(yǔ)句的排名,M是排名列表中語(yǔ)句的總數(shù),pos(i)是布爾函數(shù),pos(i)=1 表示第i條語(yǔ)句是錯(cuò)誤的,反之pos(i)=0 表示第i條語(yǔ)句是正確的.P(i)是每個(gè)排名i的定位精度.

MAP是錯(cuò)誤集合的AP的平均值,MAP 越大表明對(duì)應(yīng)的錯(cuò)誤定位技術(shù)越好.

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

4.1 研究問(wèn)題

為了評(píng)估HOMs是否能提高錯(cuò)誤定位的精度,本文從錯(cuò)誤定位精度角度出發(fā),提出如下研究問(wèn)題:

(1)RQ1:與FOMs 相比,不同階數(shù)的HOMs的多錯(cuò)誤定位精度如何？

(2)RQ2:與FOMs 相比,不同類型的HOMs的多錯(cuò)誤定位精度如何？

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

為探究RQ1,我們首先針對(duì)多錯(cuò)誤程序生成一階HOMs,然后運(yùn)行這些變異體計(jì)算得到每個(gè)程序?qū)?yīng)的EXAM,Top-N和MAP.本文使用Metallaxis-FL為原始MBFL 對(duì)照組,并生成2 階到7 階的HOMs.

圖4中展示了MBFL 使用FOMs和不同階的HOMs的錯(cuò)誤檢查比例.x軸表示代碼檢查比例,y軸表示不同程序所有錯(cuò)誤版本查找到的累積錯(cuò)誤比例,對(duì)應(yīng)的曲線越接近y軸表明對(duì)應(yīng)的變異體的檢測(cè)錯(cuò)誤數(shù)量越多,因此對(duì)應(yīng)的變異體錯(cuò)誤定位效果更好.

圖4 FOMs 與不同階 HOMs的代碼檢查比例比較

從圖4(a)中可以看出,7-HOMs 檢測(cè)20%的程序代碼能檢測(cè)到68%的錯(cuò)誤,而FOMs 只能檢測(cè)到55%的錯(cuò)誤.同理,在schedule2,totinfo和sed 上可以看出,HOMs 檢測(cè)更少的代碼能檢測(cè)到更多的錯(cuò)誤,但在tcas 程序上FOMs的檢測(cè)效果優(yōu)于HOMs.

從Top-1,Top-3,Top-5 指標(biāo)來(lái)看,FOMs 在2 錯(cuò)誤程序上的定位效果比HOMs 更好,而HOMs 在3 錯(cuò)誤和5 錯(cuò)誤程序上的表現(xiàn)比FOMs 更好.表4中顯示了FOMs和HOMs 在多錯(cuò)誤程序定位場(chǎng)景下排在前1,3,5 位錯(cuò)誤的數(shù)量.圖中包括4 種錯(cuò)誤數(shù)量的程序統(tǒng)計(jì)結(jié)果.對(duì)2 錯(cuò)誤程序,FOMs和各階高階變異體都將19 個(gè)錯(cuò)誤排在第一名.除了7-HOMs,FOMs 比其他階數(shù)的HOMs的Top-3,Top-5 要更高.對(duì)3 錯(cuò)誤程序,3-HOMs比FOMs和其他階數(shù)的變異體在Top-3和Top-5 上更高.同時(shí)FOMs 在4 錯(cuò)誤程序中,Top-3和Top-5 上的表現(xiàn)略優(yōu)于HOMs.最后,在5 錯(cuò)誤程序上,FOMs、6-HOMs和7-HOMs的Top-1 值最高,而6-HOMs和3-HOMs 分別在Top-3和Top-5 上表現(xiàn)最好.

從MAP 指標(biāo)來(lái)看,FOMs 在4 錯(cuò)誤程序上表現(xiàn)最優(yōu),在其他錯(cuò)誤程序上與HOMs 有相近的表現(xiàn).從表5可以看出,FOMs 在4 錯(cuò)誤程序上的MAP 均值最高.在其他錯(cuò)誤程序上與HOMs 有相近的表現(xiàn),例如3 錯(cuò)誤程序FOMs的MAP 均值與4 階到7 階的變異體的MAP 均值相同.

綜上可以看出,HOMs 在一些程序上的檢錯(cuò)能力優(yōu)于FOMs.同時(shí),FOMs 在2 錯(cuò)誤和4 錯(cuò)誤程序上的定位效果較好,而HOMs 在3 錯(cuò)誤和5 錯(cuò)誤程序上的效果更好.HOMs 在3 錯(cuò)誤和4 錯(cuò)誤程序上有更大的Top-N 值,并且在一些階數(shù)的HOMs 下,計(jì)算的MAP均值都要高于FOMs.

表4 FOMs和不同階HOMs的TOP-N 值比較

表5 FOMs和不同階HOMs的平均MAP 值比較

由于FOMs 只使用一次變異算子生成而HOMs 使用多次變異算子生成.因此在對(duì)同一個(gè)程序變異生成等量變異體時(shí),HOMs 有更大的概率變異到錯(cuò)誤語(yǔ)句,從而增大變異體被殺死的概率,相應(yīng)akf值也會(huì)更高,則變異體懷疑度也越高,最終計(jì)算的語(yǔ)句懷疑度也越高,其定位效果也更優(yōu)(如圖4(a),圖4(c),圖4(e);表4“3 錯(cuò)誤”行,“5 錯(cuò)誤”行;表5“3 錯(cuò)誤”行,“5 錯(cuò)誤”行).但如果HOMs 中更多變異體是對(duì)正確語(yǔ)句變異生成的,那么相應(yīng)的akp值會(huì)更高,計(jì)算的語(yǔ)句懷疑度值也更高,錯(cuò)誤定位效果將更差.(如圖4(d);表4“2 錯(cuò)誤”行,“4 錯(cuò)誤”行;表5“2 錯(cuò)誤”行,“4 錯(cuò)誤”行).綜合比較可以得出HOMs 在一定程度上能提高多錯(cuò)誤定位的效果.

為探究RQ2,我們首先收集多錯(cuò)誤程序所有版本下3 類HOMs的EXAM 值,然后分別計(jì)算Top-N和MAP 指標(biāo).為了便于展示,我們將3 類HOMs 分別表示為“Accurate”(準(zhǔn)確HOMs),“Part-accurate”(部分準(zhǔn)確HOMs)和“Inaccurate”(不準(zhǔn)確HOMs).圖5表示MBFL 使用FOMs和3 類HOMs 在不同程序上所有版本的錯(cuò)誤檢查比例.從圖5(a)-圖5(c)中可以看出Accurate HOMs 與FOMs 有相近的表現(xiàn),并且Accurate HOMs的檢測(cè)效果優(yōu)于FOMs.而在tcas和sed (圖5(d)、圖5(e))程序上,Part-accurate的檢測(cè)效果更好,檢查更少量的代碼而找到更多的錯(cuò)誤.同時(shí)在所有程序上,Inaccurate的檢測(cè)效果最差.

圖5 FOMs 與不同類 HOMs 代碼檢查比例比較

從Top-N 指標(biāo)來(lái)看,準(zhǔn)確HOMs 比FOMs和另外兩類變異體能將更多錯(cuò)誤排在前1,3,5 名.表6中顯示,在2 錯(cuò)誤程序上,準(zhǔn)確變異體與FOMs 能夠排列相同數(shù)量的錯(cuò)誤在Top-1,Top-3和Top-5,而在其他錯(cuò)誤程序版本中,準(zhǔn)確HOMs的Top-N 指標(biāo)均為最大.同時(shí)可以發(fā)現(xiàn),部分準(zhǔn)確HOMs 在4 錯(cuò)誤和5 錯(cuò)誤程序上,有更高的Top-5 值.然而不準(zhǔn)確HOMs的表現(xiàn)最差.

從MAP 指標(biāo)來(lái)看,準(zhǔn)確HOMs的表現(xiàn)同樣優(yōu)于FOMs,部分準(zhǔn)確和不準(zhǔn)確HOMs.表7中準(zhǔn)確HOMs 與FOMs 在2 錯(cuò)誤程序下有相同MAP 平均值,而在3,4,5錯(cuò)誤程序下,準(zhǔn)確HOMs 仍然比另外兩類變異體的定位效果好,其MAP 平均值分別為0.0017,0.0009,和0.0008.

綜上所述我們可以發(fā)現(xiàn),準(zhǔn)確HOMs的錯(cuò)誤定位精度高于FOMs、部分準(zhǔn)確HOMs和不準(zhǔn)確HOMs.在一些情況下,部分準(zhǔn)確HOMs 有更好的定位效果,但普遍情況下不準(zhǔn)確HOMs的表現(xiàn)都很差.

表6 FOMs和不同類HOMs的Top-N 值比較

表7 FOMs和不同類HOMs的MAP 值比較

三類HOMs 由于其不同的生成機(jī)制,造成最終定位效果的差異.首先,準(zhǔn)確HOMs 準(zhǔn)確變異錯(cuò)誤語(yǔ)句,并且對(duì)正確語(yǔ)句不作任何變異,幾乎能夠被所有的失敗測(cè)試用例殺死而不被通過(guò)測(cè)試用例殺死,其akf值高且akp值低,因此最終計(jì)算的錯(cuò)誤語(yǔ)句的懷疑度值會(huì)高,其定位效果也就更優(yōu)(如圖5,表6,表7).其次,部分準(zhǔn)確HOMs 同時(shí)對(duì)錯(cuò)誤語(yǔ)句和正確語(yǔ)句變異,會(huì)被部分失敗測(cè)試用例和正確測(cè)試用例殺死.其定位效果取決于被失敗測(cè)試用例殺死的比例,比例較高則定位精度高,比例較低則定位精度低.因此部分準(zhǔn)確HOMs的定位效果存在波動(dòng)(如圖5,表6“5 錯(cuò)誤”行,表7).最后,不準(zhǔn)確HOMs 只變異正確語(yǔ)句,不對(duì)錯(cuò)誤語(yǔ)句進(jìn)行變異,那么其更容易被正確測(cè)試用例殺死且不易被失敗測(cè)試用例殺死,計(jì)算的錯(cuò)誤語(yǔ)句的懷疑度較低,定位效果也就最差(如圖5,表6,表7).因此生成一些特定的HOMs,比如準(zhǔn)確HOMs,能有效提升多錯(cuò)誤定位的精度.

5 結(jié)論與展望

為探究HOMs是否能提升多錯(cuò)誤程序定位,本文進(jìn)行了大規(guī)模的實(shí)證研究.研究結(jié)果發(fā)現(xiàn),HOMs 在3 錯(cuò)誤和5 錯(cuò)誤程序上,有更高的錯(cuò)誤定位精度.根據(jù)不同的變異位置,我們將HOMs 分成3 類.我們發(fā)現(xiàn)準(zhǔn)確HOMs 比FOMs和其他兩類變異體有更好的多錯(cuò)誤定位效果.因此,HOMs 在一定程序上能夠提升多錯(cuò)誤程序定位,并建議研究人員設(shè)計(jì)方法生成更有效的變異體,比如準(zhǔn)確HOMs.在后續(xù)的研究中,作者將研究新的策略用于選擇有效提升多錯(cuò)誤定位精度的變異體.同時(shí)考慮擴(kuò)大實(shí)驗(yàn)數(shù)據(jù)集來(lái)驗(yàn)證HOMs 對(duì)錯(cuò)誤定位的影響.