基于偶然正確性概率的錯(cuò)誤定位技術(shù)*

周小莉,趙建華

(計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室(南京大學(xué)),江蘇 南京 210023)

1 引 言

軟件測(cè)試是保障軟件質(zhì)量的一種重要而有效的手段,而軟件的調(diào)試過(guò)程是測(cè)試中最耗時(shí)、最占據(jù)成本的任務(wù)之一.軟件調(diào)試過(guò)程中,錯(cuò)誤定位是最耗時(shí)和困難的一步[1].目前有許多自動(dòng)化的錯(cuò)誤定位技術(shù),其中,基于代碼覆蓋的錯(cuò)誤定位技術(shù)(coverage-based-faul-localization,簡(jiǎn)稱CBFL)是實(shí)際開(kāi)發(fā)中經(jīng)常使用的一種自動(dòng)化的錯(cuò)誤定位技術(shù)[2-4],該方法通過(guò)比較成功用例和失敗用例之間代碼覆蓋的差異,以對(duì)各語(yǔ)句的可疑度進(jìn)行計(jì)算并排序.然而,基于覆蓋的錯(cuò)誤定位技術(shù)的有效性受到了偶然正確性現(xiàn)象的副作用的影響.偶然正確性現(xiàn)象是指程序中包含錯(cuò)誤的語(yǔ)句被執(zhí)行到但仍通過(guò)了測(cè)試的現(xiàn)象.許多研究已經(jīng)證明偶然正確性現(xiàn)象是影響基于代碼覆蓋的錯(cuò)誤定位技術(shù)有效性的主要因素之一[5],并且是降低成功測(cè)試用例的錯(cuò)誤定位效能的最大影響因素[6].

不少研究工作都證明了偶然正確性現(xiàn)象在實(shí)際場(chǎng)景中是非常普遍的.偶然正確性現(xiàn)象的發(fā)生與如下兩方面的因素有關(guān):錯(cuò)誤語(yǔ)句能否產(chǎn)生錯(cuò)誤的中間結(jié)果以及錯(cuò)誤的中間結(jié)果能否傳遞程序輸出.在對(duì)西門子程序集的初步實(shí)驗(yàn)中,我們發(fā)現(xiàn)錯(cuò)誤語(yǔ)句產(chǎn)生錯(cuò)誤的中間結(jié)果的平均概率只有30%.而錯(cuò)誤的中間結(jié)果能否傳遞到程序輸出,與程序的信息流及其強(qiáng)度有關(guān)[7].在程序執(zhí)行過(guò)程中,如果在某一程序點(diǎn)觀測(cè)到的變量y的取值可以降低更早之前某一點(diǎn)上變量x取值的不確定性,則稱從x到y(tǒng)產(chǎn)生了一個(gè)信息流.例如,順序語(yǔ)句z=x+1;y=z/5 的執(zhí)行將產(chǎn)生從x到y(tǒng)的信息流,而語(yǔ)句z=x+1;z=5;y=z/5 的執(zhí)行將不產(chǎn)生從x到y(tǒng)的信息流.變量x和y之間的信息流強(qiáng)度表示已知y的取值的情況下變量x取值的不確定性的降低程度,信息流強(qiáng)度可在一定程度上反映變量取值之間的依賴程度.Masri 等人提出一種基于熵的方法來(lái)估量信息流強(qiáng)度,用熵對(duì)隨機(jī)變量的不確定性進(jìn)行量化,將變量x取值的不確定性與已知y取值時(shí)x的不確定性之間的差值作為x到y(tǒng)的信息流強(qiáng)度.偶然正確性現(xiàn)象是否發(fā)生,與錯(cuò)誤語(yǔ)句所產(chǎn)生的中間結(jié)果能否將錯(cuò)誤的中間狀態(tài)傳遞到程序輸出有關(guān).因此,如果錯(cuò)誤的中間結(jié)果與程序的輸出之間不存在信息流或者強(qiáng)度比較弱,則很可能會(huì)發(fā)生偶然正確性現(xiàn)象[8].Masri 和Podgurski等人[7]對(duì)實(shí)際場(chǎng)景中信息流強(qiáng)度的統(tǒng)計(jì)結(jié)果表明,弱信息流是非常普遍的,甚至其中大多數(shù)信息流強(qiáng)度為0,這個(gè)結(jié)果也驗(yàn)證了其他工作中偶然正確性現(xiàn)象在實(shí)際場(chǎng)景中普遍發(fā)生的實(shí)驗(yàn)結(jié)果.

面向工程控制領(lǐng)域的軟件(簡(jiǎn)稱工控軟件)被廣泛地用于各種制造業(yè)以及電力、交通等國(guó)家關(guān)鍵基礎(chǔ)設(shè)施,已成為國(guó)家安全戰(zhàn)略的重要組成,對(duì)生產(chǎn)效率和安全性都有較高的要求.工控軟件包含大量的控制過(guò)程,在執(zhí)行時(shí)變量間的關(guān)聯(lián)性不強(qiáng),導(dǎo)致其信息流強(qiáng)度弱,使得偶然正確性現(xiàn)象更加頻繁地出現(xiàn)在工控軟件,從而對(duì)工控軟件的錯(cuò)誤定位產(chǎn)生了不良影響.

為了消除偶然正確性現(xiàn)象對(duì)工控軟件等安全攸關(guān)軟件的錯(cuò)誤定位技術(shù)產(chǎn)生的影響,我們提出了一種基于偶然正確性概率的錯(cuò)誤定位技術(shù).該方法首先估算測(cè)試用例執(zhí)行時(shí)發(fā)生偶然正確性現(xiàn)象的概率(coincidental correctness probability,簡(jiǎn)稱CCP),然后基于偶然正確性概率對(duì)錯(cuò)誤定位技術(shù)中可疑度的計(jì)算方法進(jìn)行新的定義.本文采用了與我們以往工作[9]中類似的方法對(duì)偶然正確性概率進(jìn)行估算,估計(jì)了各語(yǔ)句的執(zhí)行實(shí)例對(duì)最終程序輸出的影響程度.基于估算得到的偶然正確性現(xiàn)象發(fā)生概率,本文重新定義了錯(cuò)誤定位中語(yǔ)句可疑度的度量方法,新的可疑度度量方法既考慮了代碼覆蓋,也考慮了偶然正確性現(xiàn)象對(duì)語(yǔ)句可疑度的影響.

本文第2 節(jié)介紹關(guān)于錯(cuò)誤定位技術(shù)和偶然正確性現(xiàn)象的基本概念.第3 節(jié)對(duì)偶然正確性現(xiàn)象如何影響錯(cuò)誤定位技術(shù)進(jìn)行討論,并介紹有關(guān)消除其副作用影響的相關(guān)工作.第4 節(jié)詳細(xì)介紹基于偶然正確性概率的錯(cuò)誤定位技術(shù),包括偶然正確性概率的估算方法及可疑度的計(jì)算方法.第5 節(jié)介紹實(shí)驗(yàn)工作,將基于偶然正確性概率的錯(cuò)誤定位技術(shù)與基于代碼覆蓋的錯(cuò)誤定位技術(shù)進(jìn)行對(duì)比.最后對(duì)本文工作進(jìn)行總結(jié).

2 基本概念

2.1 基于代碼覆蓋的錯(cuò)誤定位技術(shù)

基于代碼覆蓋的錯(cuò)誤定位技術(shù)是一種常用的自動(dòng)化錯(cuò)誤定位技術(shù),其目標(biāo)是發(fā)現(xiàn)被執(zhí)行的代碼中與錯(cuò)誤有相關(guān)性的代碼.該方法通過(guò)比較成功執(zhí)行的用例和失敗執(zhí)行的用例之間代碼覆蓋的差異來(lái)為發(fā)現(xiàn)錯(cuò)誤提供幫助.具有代表性的基于代碼覆蓋的錯(cuò)誤定位技術(shù)有χSlice[10]、CBI(cooperative bug isolation)[11]、Tarantula[12]、Jaccard[13]和Ochiai[14]等技術(shù).

基于代碼覆蓋的錯(cuò)誤定位技術(shù)收集程序執(zhí)行時(shí)的信息(包括語(yǔ)句執(zhí)行覆蓋信息和測(cè)試用例是否通過(guò)的信息),然后根據(jù)某種統(tǒng)計(jì)公式對(duì)各語(yǔ)句的可疑度進(jìn)行計(jì)算并排序.語(yǔ)句的可疑度高表示其包含錯(cuò)誤的可能性大,可疑度高的語(yǔ)句將被測(cè)試人員優(yōu)先檢查.基于代碼覆蓋進(jìn)行錯(cuò)誤定位的過(guò)程分為下面幾個(gè)步驟.

(1) 對(duì)程序進(jìn)行插樁,生成插樁后的可執(zhí)行程序.

(2) 在插樁后的程序上執(zhí)行測(cè)試用例集合,收集測(cè)試執(zhí)行時(shí)的信息.對(duì)于每個(gè)測(cè)試用例,標(biāo)記其是否通過(guò)測(cè)試,并獲取對(duì)應(yīng)的代碼覆蓋信息.在執(zhí)行測(cè)試用例時(shí),如果某條語(yǔ)句被至少執(zhí)行過(guò)1 次,則標(biāo)記該條語(yǔ)句被該測(cè)試用例所覆蓋.

(3) 通過(guò)統(tǒng)計(jì)代碼在成功和失敗用例中被覆蓋的比率來(lái)計(jì)算語(yǔ)句的可疑度,為測(cè)試人員提供一個(gè)需要被檢查的語(yǔ)句集合,這個(gè)語(yǔ)句集合被稱為語(yǔ)句檢查集.

(4) 測(cè)試人員依次判斷語(yǔ)句檢查集中的每條語(yǔ)句是否包含錯(cuò)誤.

這里,以Tarantula 方法為例展示對(duì)語(yǔ)句的可疑度進(jìn)行度量的方法.Tarantula 方法是一種非常經(jīng)典的錯(cuò)誤定位方法,它是由Jones 等人于2005 年提出來(lái)的[15],Tarantula 方法的主要思想是相對(duì)于被更多成功測(cè)試用例所覆蓋的程序元素,被更多失敗測(cè)試用例覆蓋的元素包含錯(cuò)誤的可能性更高.在失敗的測(cè)試用例中的覆蓋率越大,程序元素越可能包含錯(cuò)誤,可疑度越大.反之,程序元素在成功通過(guò)的測(cè)試用例中的覆蓋比例越大,越可能是正確的語(yǔ)句,可疑度越小.本文將程序元素限制為程序中的語(yǔ)句.Tarantula 將語(yǔ)句s的可疑度度量定義為

當(dāng)語(yǔ)句的可疑度相同時(shí),使用另外一個(gè)度量值Confidence 來(lái)對(duì)語(yǔ)句進(jìn)行排序:

計(jì)算出各語(yǔ)句的可疑度后,將語(yǔ)句按照可疑度取值從大到小進(jìn)行排序,依次審查,直到找到錯(cuò)誤語(yǔ)句為止.

Tarantula 技術(shù)取得了不錯(cuò)的錯(cuò)誤定位效果,并且成為后續(xù)研究中被廣泛使用和比較的技術(shù).隨后,Abreu 等人[13,14]提出了兩種不同的可疑度計(jì)算公式:Jaccard 和Ochiai.其中,Jaccard 的可疑度計(jì)算公式受到聚類分析的啟發(fā),Ochiai 的可疑度計(jì)算受到分子生物學(xué)的啟發(fā).Ochiai 方法的效果相比Tarantula 有一定的提升.此外,Wong 等人[16]提出一種隨著語(yǔ)句成功執(zhí)行次數(shù)增加,其對(duì)可疑度貢獻(xiàn)率逐漸減小的可疑度的計(jì)算方法.這種方法將語(yǔ)句成功執(zhí)行的次數(shù)劃分為3 個(gè)區(qū)間:[0,1]、[3,10]和[11,+∞].當(dāng)語(yǔ)句的執(zhí)行次數(shù)在區(qū)間[0,2]時(shí),語(yǔ)句執(zhí)行次數(shù)的貢獻(xiàn)率權(quán)重為1,區(qū)間[3,10]的貢獻(xiàn)率權(quán)重為0.1,區(qū)間[11,+∞]的貢獻(xiàn)率僅為0.001.除了上述可疑度計(jì)算公式以外,還存在許多不同的可疑度計(jì)算公式[17-19].

為了衡量錯(cuò)誤定位技術(shù)的有效性,可以用下面兩個(gè)指標(biāo)對(duì)其進(jìn)行評(píng)估.

(1) 安全性變化

安全性表示錯(cuò)誤代碼的相對(duì)可疑度.假設(shè)f是實(shí)際包含錯(cuò)誤的語(yǔ)句,使用score(f)表示根據(jù)錯(cuò)誤定位方法計(jì)算出的f的可疑度值,T是被用來(lái)進(jìn)行錯(cuò)誤定位的測(cè)試集合.將安全性定義為下面這個(gè)集合的大小[20].

由定義可知,S(T)是大于或等于score(f)的不同的可疑度取值的集合.分別用S(T)和S＇(T)表示基于偶然正確性概率的錯(cuò)誤定位技術(shù)和Tarantula 計(jì)算出的可疑度不低于score(f)的可疑度值的集合.如果|S(T)|＞|S＇(T)|,表明基于偶然正確性概率的技術(shù)提高了錯(cuò)誤定位的安全性;如果|S(T)|=|S＇(T)|,表明錯(cuò)誤定位的安全性保持不變;如果|S(T)|＜|S＇(T)|,表示基于偶然正確性的技術(shù)降低了錯(cuò)誤定位的安全性.

(2) 精確度變化

精確度代表定位到錯(cuò)誤語(yǔ)句所需的代碼檢查代價(jià).假設(shè)R為比錯(cuò)誤語(yǔ)句的可疑度高的語(yǔ)句的數(shù)目,R值越高,表明找到錯(cuò)誤語(yǔ)句的代價(jià)越大.反之,R值越低,找到錯(cuò)誤語(yǔ)句的代價(jià)越小.如果一種錯(cuò)誤定位技術(shù)使得R值變小了,則認(rèn)為該方法提高了精確度.精確度的變化可以用錯(cuò)誤語(yǔ)句的排名直觀地觀測(cè)到.

2.2 偶然正確性現(xiàn)象

對(duì)于基于代碼覆蓋的錯(cuò)誤定位技術(shù),如果一個(gè)測(cè)試用例執(zhí)行了包含錯(cuò)誤的語(yǔ)句,卻沒(méi)有產(chǎn)生錯(cuò)誤的程序輸出,此時(shí)這個(gè)用例對(duì)錯(cuò)誤定位沒(méi)有貢獻(xiàn),甚至對(duì)可疑度的計(jì)算產(chǎn)生負(fù)面的影響.這種錯(cuò)誤語(yǔ)句被執(zhí)行卻沒(méi)有產(chǎn)生錯(cuò)誤結(jié)果的現(xiàn)象稱為偶然正確性現(xiàn)象.

偶然正確性現(xiàn)象是指程序中發(fā)生了錯(cuò)誤但仍通過(guò)了測(cè)試的現(xiàn)象.最初,偶然正確性的概念是由Budd 和Angluin[21]提出來(lái)的.Masri 使用PIE(propagation-infection-execution,傳播-感染-執(zhí)行)模型對(duì)偶然正確性現(xiàn)象進(jìn)行了定義[20].Voas 于1992 年提出的PIE 模型[22]強(qiáng)調(diào)了程序缺陷的執(zhí)行并不是程序失效的充分條件,還需要滿足將錯(cuò)誤的中間狀態(tài)傳播到程序的輸出中.Ammman 和Offutt 提出的RIP(reachiability-infection-propagation,到達(dá)-感染-傳播)[23]模型中再次討論了這個(gè)問(wèn)題.Voas 指出當(dāng)且僅當(dāng)滿足下面3 個(gè)條件時(shí)錯(cuò)誤才會(huì)被觀測(cè)到.

執(zhí)行(execution),錯(cuò)誤代碼需要被執(zhí)行到;

感染(infection),執(zhí)行錯(cuò)誤代碼時(shí)必須觸發(fā)一個(gè)錯(cuò)誤的中間狀態(tài);

傳播(propagation),這個(gè)錯(cuò)誤的中間狀態(tài)必須能夠傳播到程序的輸出,使得我們能夠觀測(cè)到它與預(yù)期的輸出不一致,即失效.

Masri[8]將偶然正確性現(xiàn)象進(jìn)一步分類為強(qiáng)偶然正確性現(xiàn)象和弱偶然正確性現(xiàn)象.強(qiáng)偶然正確性現(xiàn)象發(fā)生在“執(zhí)行”和“感染”兩個(gè)條件被滿足而“傳播”條件沒(méi)有被滿足時(shí).若“執(zhí)行”條件被滿足而“傳播”條件沒(méi)有被滿足,則無(wú)論“感染”條件是否被滿足,都稱發(fā)生了弱偶然正確性現(xiàn)象.許多工作都證明了偶然正確性現(xiàn)象的普遍性[5,8,24],尤其弱偶然正確性現(xiàn)象的發(fā)生是非常頻繁的[8].

2.3 偶然正確性現(xiàn)象對(duì)錯(cuò)誤定位技術(shù)的影響

許多研究工作[5,6,24]都證明偶然正確性現(xiàn)象對(duì)錯(cuò)誤定位的有效性帶來(lái)了副作用影響.Denmat 等人[25]對(duì)經(jīng)典的基于代碼覆蓋的錯(cuò)誤定位技術(shù)Tarantula 的局限性進(jìn)行了研究,并表明要使其有效,必須滿足錯(cuò)誤語(yǔ)句的執(zhí)行在大多數(shù)情況下會(huì)導(dǎo)致程序出錯(cuò),即大多數(shù)程序的執(zhí)行中不會(huì)發(fā)生偶然正確性現(xiàn)象.Masri 等人[5]對(duì)降低基于代碼覆蓋的錯(cuò)誤定位技術(shù)有效性的因素進(jìn)行了實(shí)驗(yàn)性研究,結(jié)果表明,偶然正確性現(xiàn)象普遍存在,并且是影響基于覆蓋的錯(cuò)誤定位技術(shù)有效性的主要因素之一.另外,Lei 等人[6]對(duì)測(cè)試用例的錯(cuò)誤定位效能進(jìn)行了分析和總結(jié),證明偶然正確性現(xiàn)象是影響成功測(cè)試用例的錯(cuò)誤定位效能的最主要的因素.

Table 1 Suspiciousness metrics of three CBFL techniques表1 3 種基于覆蓋的錯(cuò)誤定位技術(shù)的可疑度計(jì)算公式

本文從偶然正確性現(xiàn)象對(duì)各語(yǔ)句的可疑度計(jì)算產(chǎn)生的具體影響的角度出發(fā),討論偶然正確性現(xiàn)象如何影響錯(cuò)誤定位技術(shù)的有效性.我們以Tarantula、Jaccard、Ochiai 這3 種流行的基于代碼覆蓋的錯(cuò)誤定位技術(shù)為例,分別比較考慮和忽略偶然正確性現(xiàn)象所計(jì)算出的可疑度.對(duì)于一個(gè)語(yǔ)句s,分別用s00、s01、s10、s11表示4 類測(cè)試集合的用例數(shù)目.

測(cè)試集合的這些屬性將用來(lái)計(jì)算語(yǔ)句的可疑度度量.在表1 中展示了Tarantula、Ochiai 和Jaccard 這3 種錯(cuò)誤定位技術(shù)的可疑度度量的計(jì)算公式.假設(shè)在測(cè)試集合中有n個(gè)測(cè)試用例發(fā)生了偶然正確性現(xiàn)象.這里,使用M(s)和M＇(s)分別來(lái)表示忽略和考慮偶然正確性現(xiàn)象的可疑度度量.

首先以Tarantula 為例來(lái)展示可疑度的計(jì)算.假設(shè)s是包含錯(cuò)誤的語(yǔ)句,在全部測(cè)試用例中有n個(gè)測(cè)試用例發(fā)生了偶然正確性現(xiàn)象,也就是說(shuō)有n個(gè)測(cè)試用例覆蓋了語(yǔ)句s但并沒(méi)有產(chǎn)生錯(cuò)誤的結(jié)果.這種情況下,M(s)的值被錯(cuò)誤地估計(jì)了,為了得到更精確的值,需要將n個(gè)測(cè)試用例從s10中去掉,新的可疑度度量M＇(s)的值為

顯然地,M＇(s)＞=M(s),也就是說(shuō),如果不考慮發(fā)生偶然正確性現(xiàn)象的測(cè)試用例將低估錯(cuò)誤語(yǔ)句s的可疑度.并且,隨著n的增大,M＇(s)的值也會(huì)相應(yīng)增大.也就是說(shuō),在估算語(yǔ)句s的可疑度時(shí),覆蓋語(yǔ)句s且因?yàn)榕既徽_性而通過(guò)測(cè)試的測(cè)試用例個(gè)數(shù)越多,則可疑度估算的誤差越大,從而對(duì)錯(cuò)誤定位的安全性和準(zhǔn)確性造成影響.因此,針對(duì)該語(yǔ)句的可疑度估算需要做出不同程度的修正,以得到能夠更加準(zhǔn)確地反映出語(yǔ)句中包含錯(cuò)誤的可疑度排序.

對(duì)于Ochiai 和Jaccard,可用相同的思路估計(jì)偶然正確性現(xiàn)象對(duì)可疑度的影響,需要將n個(gè)發(fā)生偶然正確性現(xiàn)象的測(cè)試用例從s10中抽出,以得到一個(gè)修正的可疑度度量值.對(duì)于Ochiai,考慮了偶然正確性現(xiàn)象的可疑度為

對(duì)于Jaccard,考慮偶然正確性現(xiàn)象的可疑度公式為

同樣地,對(duì)于Ochiai 和Jaccard,考慮了偶然正確性現(xiàn)象所估算的可疑度值也是大于或等于原本公式計(jì)算出的可疑度值.實(shí)際執(zhí)行中發(fā)生偶然正確性現(xiàn)象的測(cè)試用例越多,其可疑度估算的誤差也越大,因而對(duì)錯(cuò)誤語(yǔ)句的可疑度排序的準(zhǔn)確性產(chǎn)生影響.

3 偶然正確性現(xiàn)象的相關(guān)工作

Masri 等人[20]圍繞偶然正確性現(xiàn)象的定義、分類和產(chǎn)生原因進(jìn)行了研究,并對(duì)其在實(shí)際場(chǎng)景中出現(xiàn)的頻率進(jìn)行了實(shí)驗(yàn).Daran 等人[24]在對(duì)實(shí)際場(chǎng)景中出現(xiàn)的錯(cuò)誤進(jìn)行分析時(shí),也驗(yàn)證了偶然正確性現(xiàn)象的普遍性.

目前,偶然正確性現(xiàn)象的相關(guān)工作大多集中在錯(cuò)誤定位方向.Masri[5]、Yei[6]和Denmat[24]等人的研究工作都證明了偶然正確性現(xiàn)象是影響基于代碼覆蓋的錯(cuò)誤定位技術(shù)有效性的主要原因之一.隨后,許多研究工作試圖消除偶然正確性現(xiàn)象對(duì)錯(cuò)誤定位技術(shù)產(chǎn)生的副作用影響.這些工作通常使用兩種不同的策略消除偶然正確性的影響,第1 種策略是直接將發(fā)生偶然正確性現(xiàn)象的用例從測(cè)試集中刪除,另一種策略是將發(fā)生偶然正確性現(xiàn)象的用例歸類為失敗用例.其中,最大的挑戰(zhàn)是如何判斷測(cè)試過(guò)程中是否發(fā)生了偶然正確性現(xiàn)象.

Masri 等人[8,20]提出了多種識(shí)別發(fā)生偶然正確性的測(cè)試用例的方法,這些方法大多基于一個(gè)類似的思想,即發(fā)生偶然正確性現(xiàn)象的測(cè)試用例是與失敗用例有著相似行為的成功用例.Masri 等人[20]通過(guò)聚類分析來(lái)識(shí)別偶然正確性現(xiàn)象,其采用的聚類算法是K-均值聚類算法.首先,將測(cè)試用例使用歐式距離計(jì)算類間距離并進(jìn)行聚類,將原始測(cè)試集合聚類為兩個(gè)類簇.然后,選取包含更多的失敗用例的類簇,將該類簇中的成功用例識(shí)別為發(fā)生偶然正確性現(xiàn)象的用例.然后,Masri 在Tarantula 技術(shù)的基礎(chǔ)上,將發(fā)生偶然正確性現(xiàn)象的用例刪除后再進(jìn)行錯(cuò)誤定位.另外,Marsi 等人[8]還提出一種基于散點(diǎn)圖來(lái)識(shí)別偶然正確性用例的方法.這種方法將散點(diǎn)圖上兩個(gè)測(cè)試用例間直接的距離作為兩者的不同程度,將與執(zhí)行失敗的用例最接近的用例識(shí)別為偶然正確性用例.

基于與上述方法類似的思想,一些基于聚類的識(shí)別偶然正確性用例的方法被提出[26,27].陳振宇等人[23]提出了一種基于聚類分析的方法來(lái)消除偶然正確性現(xiàn)象對(duì)錯(cuò)誤定位技術(shù)的影響.Li 等人[27]提出了對(duì)謂詞信息進(jìn)行聚類分析來(lái)識(shí)別偶然正確性用例的方法.孫召倩等人[28]在聚類分析算法的基礎(chǔ)上引入了模糊概率算法,將一個(gè)成功測(cè)試用例是偶然正確性用例的概率設(shè)置為0 到1 之間的取值,降低了識(shí)別偶然正確性用例的誤報(bào)率和漏報(bào)率.此外,Wang 等人[29]使用帶上下文模式的覆蓋度重定義方法來(lái)消除偶然正確性現(xiàn)象對(duì)Tarantula 技術(shù)的影響.這種模式從程序的數(shù)據(jù)依賴和控制依賴關(guān)系的角度出發(fā),認(rèn)為如果錯(cuò)誤可以被發(fā)現(xiàn),那么一定有與之相匹配的上下文模式.Wang 等人總結(jié)了12 個(gè)上下文模式,可以對(duì)實(shí)際開(kāi)發(fā)中常見(jiàn)的13 種類型的錯(cuò)誤進(jìn)行匹配.然而,實(shí)際開(kāi)發(fā)場(chǎng)景中程序包含的錯(cuò)誤類型遠(yuǎn)不止13 種,因此這種方法具有一定的局限性.另外,張卓等人[30]提出了一種增強(qiáng)上下文的錯(cuò)誤定位方法,該方法關(guān)注失敗測(cè)試用例,通過(guò)動(dòng)態(tài)切片提取更精確的信息,縮小錯(cuò)誤搜索范圍,抑制了發(fā)生偶然正確性現(xiàn)象的成功用例對(duì)錯(cuò)誤定位結(jié)果產(chǎn)生負(fù)效應(yīng)的空間,間接地緩解了偶然正確性問(wèn)題.同時(shí),張卓等人也指出這種方法無(wú)法徹底消除偶然正確性現(xiàn)象的影響.

另外，偶然正確性現(xiàn)象在測(cè)試充分度和邊界值分析方面也引起了一些研究關(guān)注.基于代碼覆蓋的測(cè)試充分度是在測(cè)試中最常用的測(cè)試充分度準(zhǔn)則,然而代碼覆蓋和錯(cuò)誤發(fā)現(xiàn)之間并沒(méi)有很強(qiáng)的相關(guān)性.偶然正確性現(xiàn)象是導(dǎo)致代碼覆蓋無(wú)法準(zhǔn)確表示測(cè)試充分程度的主要原因之一.在以往的工作[9-31]中,我們提出了一種估算程序執(zhí)行時(shí)發(fā)生偶然正確性現(xiàn)象的概率的方法,并基于偶然正確性概率對(duì)測(cè)試充分度進(jìn)行衡量.相對(duì)于基于代碼覆蓋的測(cè)試充分度,基于偶然正確性概率的測(cè)試充分度與錯(cuò)誤發(fā)現(xiàn)之間有更強(qiáng)的相關(guān)性,更能準(zhǔn)確地反映測(cè)試的充分程度.偶然正確性現(xiàn)象對(duì)邊界值分析也產(chǎn)生了副面影響.Hierons[32]對(duì)發(fā)生偶然正確性現(xiàn)象的實(shí)例進(jìn)行了研究,并提出了一種生成不發(fā)生偶然正確性現(xiàn)象用例的方法.

4 基于偶然正確性概率的錯(cuò)誤定位技術(shù)

基于代碼覆蓋的錯(cuò)誤定位技術(shù)是通過(guò)語(yǔ)句在成功和失敗用例中被覆蓋的比率來(lái)對(duì)其可疑度進(jìn)行計(jì)算的.然而,這個(gè)比率的計(jì)算會(huì)因?yàn)榕既徽_性現(xiàn)象發(fā)生而產(chǎn)生誤差,需要根據(jù)偶然正確性現(xiàn)象對(duì)可疑度加以修正.

在以往工作[9]中,我們提出一種對(duì)測(cè)試用例執(zhí)行時(shí)發(fā)生偶然正確性的概率進(jìn)行估算的方法.基于偶然正確性現(xiàn)象的發(fā)生概率,本文將測(cè)試用例部分地分類為失敗用例和成功用例,從而對(duì)可疑度的計(jì)算進(jìn)行修正.下文首先介紹偶然正確性概率估算方法,然后詳細(xì)給出利用偶然正確性概率對(duì)可疑度進(jìn)行度量的方法.

4.1 偶然正確性概率的估算

偶然正確性概率的估算[9]是本文工作的基礎(chǔ),本文從代碼執(zhí)行過(guò)程中內(nèi)存空間變化的角度出發(fā),通過(guò)動(dòng)態(tài)的數(shù)據(jù)流和控制流兩個(gè)方面來(lái)估算程序執(zhí)行過(guò)程中發(fā)生偶然正確性的概率.程序的執(zhí)行過(guò)程可以看作這些語(yǔ)句實(shí)例對(duì)內(nèi)存空間中值進(jìn)行讀取、計(jì)算和寫入的過(guò)程.通常根據(jù)檢查程序輸出來(lái)判斷是否通過(guò)了測(cè)試,因此包含錯(cuò)誤的程序在一次執(zhí)行中發(fā)生偶然正確性概率可以看作在該錯(cuò)誤執(zhí)行后程序仍然產(chǎn)生正確輸出的概率.

偶然正確性現(xiàn)象發(fā)生在包含錯(cuò)誤的語(yǔ)句被執(zhí)行但是沒(méi)有產(chǎn)生錯(cuò)誤的中間值時(shí),或者錯(cuò)誤語(yǔ)句產(chǎn)生了錯(cuò)誤中間值卻沒(méi)有將錯(cuò)誤的中間狀態(tài)傳遞到輸出中的時(shí)候.錯(cuò)誤的中間值沒(méi)有被傳遞到輸出的原因是這個(gè)錯(cuò)誤中間值沒(méi)有被用來(lái)生成最終的輸出,或者錯(cuò)誤中間值在產(chǎn)生程序輸出前被掩蓋.這里的掩蓋可能是錯(cuò)誤的值被后續(xù)語(yǔ)句的賦值所直接覆蓋,也可能是參與運(yùn)算,卻偶然地產(chǎn)生了正確的運(yùn)算結(jié)果.例如,假設(shè)錯(cuò)誤語(yǔ)句s的執(zhí)行為變量x進(jìn)行了錯(cuò)誤的賦值,如果x與值為False 的操作數(shù)進(jìn)行并運(yùn)算,或者與值為0 的操作數(shù)進(jìn)行乘法運(yùn)算,此時(shí)運(yùn)算結(jié)果仍然是正確的,x中的錯(cuò)誤會(huì)被掩蓋.再比如,x被用于比較運(yùn)算中,雖然x的值是錯(cuò)誤的,但與正確的取值在同一區(qū)間,那么比較運(yùn)算的結(jié)果仍是正確的.

本文從運(yùn)算和控制流兩方面來(lái)估計(jì)錯(cuò)誤的中間狀態(tài)被傳播到程序輸出的概率.

(1) 運(yùn)算的影響

運(yùn)算的影響是估計(jì)錯(cuò)誤的中間結(jié)果被計(jì)算性使用時(shí)對(duì)運(yùn)算結(jié)果產(chǎn)生的影響.例如,當(dāng)錯(cuò)誤的中間值被用于賦值語(yǔ)句表達(dá)式、輸出語(yǔ)句或當(dāng)作函數(shù)調(diào)用的參數(shù)以及被用于索引表達(dá)式中時(shí),通常會(huì)得到錯(cuò)誤的運(yùn)算結(jié)果,但也仍然可能是正確的運(yùn)算結(jié)果,這也是偶然正確現(xiàn)象出現(xiàn)的原因之一.運(yùn)算結(jié)果的正確性與操作數(shù)的正確性和所參與的運(yùn)算有關(guān).如果操作數(shù)的取值都正確,那么運(yùn)算結(jié)果也一定是正確的;如果至少一個(gè)操作數(shù)是錯(cuò)誤的,那么運(yùn)算結(jié)果也很可能是錯(cuò)誤的.對(duì)于不同的運(yùn)算和操作數(shù)的取值,操作數(shù)對(duì)運(yùn)算結(jié)果正確性的影響程度也不同.對(duì)不同類型的運(yùn)算,本文通過(guò)為每個(gè)操作數(shù)都設(shè)定不同的影響因子來(lái)量化該操作數(shù)對(duì)運(yùn)算結(jié)果正確性的影響程度.運(yùn)算結(jié)果的正確性概率可以根據(jù)運(yùn)算的類型、操作數(shù)的正確性概率以及其當(dāng)前的取值進(jìn)行估計(jì).

(2) 控制流的影響

控制流的影響是指錯(cuò)誤的中間結(jié)果被判定性使用時(shí)所產(chǎn)生的影響.當(dāng)錯(cuò)誤的中間結(jié)果被用于分支語(yǔ)句的條件表達(dá)式時(shí),會(huì)導(dǎo)致程序錯(cuò)誤地執(zhí)行了某條路徑,被實(shí)際執(zhí)行的路徑上和應(yīng)該被執(zhí)行的路徑上的語(yǔ)句所改變的變量的值,其正確性都受到了影響.由于未被執(zhí)行的路徑信息難以獲取,這里只考慮被執(zhí)行的分支內(nèi)所涉及的內(nèi)存單元的正確性.對(duì)于一條語(yǔ)句實(shí)例s,為了估算控制流對(duì)其結(jié)果正確性概率的影響,我們首先找到影響s的所有控制表達(dá)式的執(zhí)行實(shí)例,然后根據(jù)這些表達(dá)式的正確性概率對(duì)s的結(jié)果的正確性概率進(jìn)行修正.

對(duì)于程序中的任意一個(gè)語(yǔ)句s,通過(guò)分析s的各個(gè)實(shí)例產(chǎn)生的中間結(jié)果直接或間接傳播到輸出的過(guò)程,可以估計(jì)出s的執(zhí)行對(duì)程序輸出的影響程度.這里,我們將程序輸出不受到s的執(zhí)行影響的概率定義為CCP(s,t),這一概率同時(shí)也是假定s中包含錯(cuò)誤的前提下此次執(zhí)行的輸出結(jié)果的正確性概率,即發(fā)生偶然正確性現(xiàn)象的概率.

對(duì)于一個(gè)測(cè)試用例,錯(cuò)誤所在的位置不同(即包含錯(cuò)誤的語(yǔ)句不同),其執(zhí)行時(shí)對(duì)程序輸出的影響程度也有所不同.因此,為了估計(jì)程序的一次執(zhí)行發(fā)生偶然正確性現(xiàn)象的情況,我們對(duì)每一條語(yǔ)句都進(jìn)行分析,估算它的執(zhí)行對(duì)程序輸出的影響.本文所使用的估算方法是針對(duì)每個(gè)測(cè)試用例和程序中每條語(yǔ)句進(jìn)行估算,可以比較精細(xì)地分析出偶然正確性現(xiàn)象發(fā)生的情況.

4.2 基于偶然正確性概率的可疑度計(jì)算方法

本文在Tarantula 的基礎(chǔ)上,根據(jù)偶然正確性概率對(duì)其可疑度的計(jì)算公式進(jìn)行修正,從而得到一個(gè)基于偶然正確性概率的可疑度度量方法.Tarantula 是一種非常經(jīng)典的基于代碼覆蓋的錯(cuò)誤定位技術(shù),在錯(cuò)誤定位相關(guān)研究中被廣泛使用和比較.同時(shí),其他消除偶然正確現(xiàn)象對(duì)錯(cuò)誤定位影響的相關(guān)研究工作[8,26,30]也都是在Tarantula的基礎(chǔ)上進(jìn)行修正的.本文提出對(duì)可疑度的修正方法同樣可以用于Jaccard 等基于代碼覆蓋的錯(cuò)誤定位技術(shù)上.

為了計(jì)算語(yǔ)句s的可疑度,Tarantula 方法根據(jù)測(cè)試用例是否覆蓋s以及是否通過(guò)測(cè)試將測(cè)試用例集合分成4 個(gè)互不相交的子集,用s00、s01、s10和s11分別表示這4 個(gè)集合的元素個(gè)數(shù).其中,s00表示未覆蓋語(yǔ)句s的成功測(cè)試用例的數(shù)目,s01表示未覆蓋s的失敗用例數(shù)目,s10表示覆蓋s的成功測(cè)試用例數(shù)目,s11表示覆蓋s的失敗測(cè)試用例數(shù)目.

本文提出的錯(cuò)誤定位技術(shù)不是將測(cè)試用例簡(jiǎn)單地歸入到上述某個(gè)集合中,而是根據(jù)偶然正確性概率按照一定比例將測(cè)試用例“部分”分配到上述集合中.這里,用f00(s,t)、f01(s,t)、f10(s,t)和f11(s,t)分別表示測(cè)試用例t被“部分”分配到這4 個(gè)子集中的值,則有,

這里,將s00、s01、s10和s11稱為FPValue變量,將f00(s,t)、f01(s,t)、f10(s,t)、f11(s,t)稱為FPValue增量函數(shù).對(duì)于語(yǔ)句s和測(cè)試用例t,首先估算出偶然正確性概率CCP(s,t),然后根據(jù)CCP(s,t)對(duì)FPValue增量函數(shù)進(jìn)行計(jì)算.這里的CCP(s,t)并不是測(cè)試用例t在實(shí)際執(zhí)行時(shí)發(fā)生偶然正確性現(xiàn)象的概率,而是在假設(shè)s包含錯(cuò)誤的情況下執(zhí)行t時(shí)發(fā)生偶然正確性現(xiàn)象的概率,即t執(zhí)行時(shí)程序輸出不受到s執(zhí)行時(shí)所產(chǎn)生的影響的概率.

基于代碼覆蓋的錯(cuò)誤定位技術(shù)認(rèn)為,如果語(yǔ)句被失敗用例覆蓋得越多、被成功用例覆蓋得越少,其可疑度就越高.這類技術(shù)有一個(gè)潛在的假設(shè):錯(cuò)誤語(yǔ)句被覆蓋時(shí)很可能會(huì)產(chǎn)生錯(cuò)誤的程序輸出,而錯(cuò)誤語(yǔ)句沒(méi)有被覆蓋時(shí)則很可能產(chǎn)生正確的輸出.當(dāng)語(yǔ)句s的執(zhí)行對(duì)t執(zhí)行時(shí)的程序輸出沒(méi)有任何影響時(shí),從錯(cuò)誤定位的角度考慮來(lái)看,相當(dāng)于s沒(méi)有被執(zhí)行到.表2 中給出了根據(jù)CCP(s,t)計(jì)算FPValue增量函數(shù)的方法,將測(cè)試用例分為4 種情況進(jìn)行分析.

(1) 如果t是覆蓋語(yǔ)句s的成功用例,語(yǔ)句s有CCP(s,t)的概率對(duì)程序的輸出不產(chǎn)生影響,因此,將該用例CCP(s,t)的概率分配到未覆蓋且成功用例集合中,1-CCP(s,t)的概率分配到覆蓋且成功用例集合中.

(2) 如果t是覆蓋s的失敗用例,此時(shí)用與第1 種情況類似的方法進(jìn)行分配.語(yǔ)句s有CCP(s,t)的概率不對(duì)程序的輸出產(chǎn)生影響,因此,將該用例以CCP(s,t)的概率分配到未覆蓋且失敗用例集合中,以1-CCP(s,t)的概率分配到覆蓋且失敗用例集合中.

(3) 如果t是未覆蓋語(yǔ)句s的失敗用例,則將其歸類到未覆蓋且失敗用例,即f01(s,t)=1,其他FPValues函數(shù)的值為0.

(4) 如果t是未覆蓋語(yǔ)句s的成功用例,則將其歸類為未覆蓋的失敗用例,即f00(s,t)=1,其他FPValues函數(shù)的值為0.

Table 2 The calculation of incremental functions of FPValues表2 FPValues 增量函數(shù)的計(jì)算

本文只考慮了前兩種情況下語(yǔ)句s的偶然正確性概率.其他兩者情況下,語(yǔ)句s的偶然正確性概率與錯(cuò)誤定位的關(guān)聯(lián)并不大,因此可疑度的計(jì)算方法與原始的Tarantula 方法相同.對(duì)于前兩種情況,在CCP(s,t)=0 這種極端情況下,如果t包含錯(cuò)誤,它的執(zhí)行一定會(huì)導(dǎo)致程序出錯(cuò),此時(shí),FPValues函數(shù)的計(jì)算方法將退化為Tarantula 中的計(jì)算方法.如果CCP(s,t)的值非常高,測(cè)試用例t對(duì)程序輸出的影響非常小,本文提出的方法傾向于將測(cè)試用例t更多地放入未被覆蓋的測(cè)試用例集合中.本文按照偶然正確性概率對(duì)測(cè)試用例重新劃分,從而消除了偶然正確性現(xiàn)象對(duì)可疑度計(jì)算的影響.

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

5.1.1 目標(biāo)程序和實(shí)驗(yàn)設(shè)計(jì)

西門子程序集被廣泛地應(yīng)用于評(píng)估各種測(cè)試技術(shù)有效性的實(shí)驗(yàn)工作上,也是偶然正確性現(xiàn)象相關(guān)工作[7-9,20]中經(jīng)常使用到的目標(biāo)程序.在實(shí)驗(yàn)中,本文從SIR 中獲取了西門子程序集的7 個(gè)合適大小的C 程序,其中包含了62 個(gè)錯(cuò)誤版本的程序,每個(gè)錯(cuò)誤版本程序中只包含1 個(gè)錯(cuò)誤.表3 提供了目標(biāo)程序的基本信息和配套的測(cè)試用例集合,包含了源程序代碼的大小、測(cè)試用例的數(shù)目以及失敗的測(cè)試用例的數(shù)目等信息.

Table 3 Subject programs表3 目標(biāo)程序

實(shí)驗(yàn)中將基于偶然正確性概率的錯(cuò)誤定位技術(shù)與Tarantula 技術(shù)進(jìn)行比較,統(tǒng)計(jì)其錯(cuò)誤定位結(jié)果安全性精確度的變化,并與相關(guān)工作[8]的結(jié)果進(jìn)行對(duì)比.對(duì)于每一個(gè)版本的程序,按照下面幾個(gè)步驟進(jìn)行實(shí)驗(yàn).

(1) 獲得預(yù)備信息

首先,根據(jù)執(zhí)行結(jié)果將測(cè)試用例集合分類為執(zhí)行成功和執(zhí)行失敗兩種用例.然后,找到并標(biāo)記包含錯(cuò)誤的語(yǔ)句.對(duì)于每一個(gè)測(cè)試用例,標(biāo)記是否覆蓋了包含錯(cuò)誤的語(yǔ)句.

(2) 估算偶然正確性概率

對(duì)于每一個(gè)語(yǔ)句s和每一個(gè)成功執(zhí)行的測(cè)試用例s,計(jì)算CCP(s,t)的值,即假設(shè)s為錯(cuò)誤語(yǔ)句時(shí)測(cè)試用例t因?yàn)榕既徽_性現(xiàn)象而被通過(guò)的概率.

(3) 計(jì)算可疑度

對(duì)于每一個(gè)語(yǔ)句,分別使用Tarantula 和基于偶然正確性概率及代碼覆蓋的錯(cuò)誤定位技術(shù)來(lái)計(jì)算可疑度.對(duì)于每個(gè)版本的程序,分別統(tǒng)計(jì)其錯(cuò)誤定位結(jié)果的安全性和準(zhǔn)確性的變化情況.

5.1.2 實(shí)驗(yàn)結(jié)果和分析

本文對(duì)目標(biāo)程序執(zhí)行時(shí)發(fā)生偶然正確性現(xiàn)象的頻率進(jìn)行了統(tǒng)計(jì),并將基于偶然正確性概率的錯(cuò)誤定位方法與Tarantula 的錯(cuò)誤定位結(jié)果的安全性和精確度進(jìn)行對(duì)比.

(1) 偶然正確性現(xiàn)象的發(fā)生頻率

在實(shí)驗(yàn)中將覆蓋了錯(cuò)誤語(yǔ)句的被通過(guò)用例歸類為偶然正確性用例.圖1 展示了偶然正確性用例的統(tǒng)計(jì)信息,圖中將錯(cuò)誤版本的程序按照原始程序進(jìn)行了分組顯示,其橫坐標(biāo)是原始程序,縱坐標(biāo)為這個(gè)程序的所有變種程序所對(duì)應(yīng)的測(cè)試集合中偶然正確性用例所占的平均比例,即偶然正確性現(xiàn)象出現(xiàn)的平均頻率.對(duì)于所有原始程序的錯(cuò)誤版本,其偶然正確性現(xiàn)象發(fā)生的平均頻率都超過(guò)20%,其中對(duì)于“schedule2”的變種程序,偶然正確性現(xiàn)象的平均概率甚至高達(dá)90%以上.對(duì)圖中的數(shù)據(jù)作進(jìn)一步的統(tǒng)計(jì)后發(fā)現(xiàn),偶然正確性現(xiàn)象在所有目標(biāo)程序執(zhí)行中出現(xiàn)的平均頻率為53%.很明顯地,偶然正確性現(xiàn)象在目標(biāo)程序中非常頻繁地出現(xiàn).

(2) 錯(cuò)誤定位結(jié)果的對(duì)比

在實(shí)驗(yàn)中,本文將基于偶然正確性概率的錯(cuò)誤定位方法與Tarantula 在錯(cuò)誤定位的安全性和精確度上進(jìn)行了對(duì)比.圖2 和圖3 展示了錯(cuò)誤定位的安全性和精確度的變化情況.圖2 中將所有錯(cuò)誤版本的程序按照原始程序進(jìn)行了分組顯示,圖中的橫坐標(biāo)是原始程序,縱坐標(biāo)為這個(gè)程序的所有變種的錯(cuò)誤版本中其錯(cuò)誤定位結(jié)果的安全性和精確度有所提高或保持不變的程序版本的比例.在圖3 中展示了關(guān)于精確度變化的更詳細(xì)的信息,其中,橫坐標(biāo)代表不同的程序版本,縱坐標(biāo)表示精確度的變化.從圖2 和圖3 中可以看出,基于偶然正確性概率的錯(cuò)誤定位技術(shù)在安全性和精確度上均得到了一定的提升.

(a) 安全性方面

從圖2 中可以看出,錯(cuò)誤定位的安全性被提升的程序版本比例在75%～100%之間.對(duì)圖上所有程序進(jìn)行綜合統(tǒng)計(jì)后發(fā)現(xiàn),對(duì)于95%的程序,其錯(cuò)誤定位的安全性都得到了提升,其他5%的程序(只有3 個(gè)程序版本)維持了原有的錯(cuò)誤定位的安全性指標(biāo),沒(méi)有任何程序的安全性被降低.這個(gè)實(shí)驗(yàn)結(jié)果表明,對(duì)于所有版本的程序,基于偶然正確性的錯(cuò)誤定位技術(shù)都提高或維持了錯(cuò)誤定位的安全性.

(b) 精確度方面

精確度表示搜索到錯(cuò)誤語(yǔ)句所付出的代價(jià),它是衡量錯(cuò)誤定位有效性的最重要的指標(biāo).如圖2 所示,錯(cuò)誤定位的精確度得到提升或者保持不變的程序所占的比例在66.67%～89.47%之間,其他程序的錯(cuò)誤定位的精確度被降低.如果考慮精確度不變的情況,那么,維持或者提升精確度的比例為66.67%～89.47%之間.對(duì)于所有版本的程序,其精確度變化的綜合結(jié)果是錯(cuò)誤定位的精確度平均被提升了3.77%.其中,對(duì)于77.42%的程序,基于偶然正確性概率的錯(cuò)誤定位技術(shù)得到了精確度的提升,其平均上升幅度為5.3%.對(duì)于19.35%的程序,錯(cuò)誤定位的精確度有所下降,其平均下降幅度為1.9%.對(duì)于另外3.22%的程序,其錯(cuò)誤定位的精確度保持不變.

Fig.1 Percentage of coincidental correctness tests圖1 發(fā)生偶然正確性現(xiàn)象的用例所占的比例

在實(shí)驗(yàn)中,實(shí)際執(zhí)行時(shí)發(fā)生偶然正確性概率高的程序在精確度上的表現(xiàn)相對(duì)優(yōu)于其他程序,這也說(shuō)明,我們的方法可以有效地消除偶然正確性現(xiàn)象對(duì)錯(cuò)誤定位的影響.發(fā)生偶然正確性現(xiàn)象頻率較低的程序在錯(cuò)誤定位精確度上的表現(xiàn)上略劣于其他程序,這是因?yàn)?消除偶然正確現(xiàn)象的影響對(duì)其定位結(jié)果的提升是有限的.另外,某些程序在精確度上被降低的原因可能與偶然正確現(xiàn)象概率的估算值與實(shí)際的差異有關(guān).

精確度相關(guān)的實(shí)驗(yàn)結(jié)果表明,對(duì)于大多數(shù)版本的程序,基于偶然正確性概率的錯(cuò)誤定位技術(shù)提高了出錯(cuò)語(yǔ)句在可疑語(yǔ)句序列中的排名,使得錯(cuò)誤可以更早地被測(cè)試人員所定位到.對(duì)于小部分版本的程序,出錯(cuò)語(yǔ)句的排序下降了,但其下降程度相對(duì)較小.總體而言,本文提出的錯(cuò)誤定位技術(shù)一定程度上提高了錯(cuò)誤定位的精確度.

Fig.2 Changes of safety and precision圖2 安全性和精確度的變化

Fig.3 Deatals of precision changes圖3 精確度變化的詳細(xì)信息

(c) 與相關(guān)工作的對(duì)比

在相關(guān)工作中,Masri 等人[8]提出了多種提高錯(cuò)誤定位技術(shù)有效性的技術(shù),并在西門子程序集中的18 個(gè)版本的程序上進(jìn)行了實(shí)驗(yàn).在這項(xiàng)工作中,達(dá)到最優(yōu)效果的技術(shù)(系數(shù)為0.8 的技術(shù)3)對(duì)于80%的程序提高了錯(cuò)誤定位的安全性,對(duì)于61%的程序提高了錯(cuò)誤定位的精確度.本文在實(shí)驗(yàn)中所選取的程序包含了文獻(xiàn)[8]的工作中所用的目標(biāo)程序,我們的方法提高了95%的程序定位結(jié)果的安全性,提高了77%的程序定位結(jié)果的精確度.相對(duì)于Masri 的方法,本文提出的方法在安全性和精確性上都有一定的優(yōu)勢(shì).

基于與Masri 工作[8]類似的思想,另有一些使用聚類方法來(lái)消除偶然正確性現(xiàn)象影響的研究.為了保證聚類分析的效果,這些工作選取了較大規(guī)模的程序進(jìn)行實(shí)驗(yàn),而沒(méi)有選取西門子中常用的小規(guī)模程序,與本文選取的目標(biāo)程序不同,所以不能直接與我們的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比.在這些基于聚類的工作中,Li 等人[30]的在錯(cuò)誤定位上的實(shí)驗(yàn)結(jié)果較優(yōu),這種方法對(duì)偶然正確現(xiàn)象識(shí)別的誤報(bào)率較低(平均值為4.85%),而漏報(bào)率較高(平均值為47.4%).Li 等人[30]在實(shí)驗(yàn)中用精確度變化來(lái)衡量錯(cuò)誤定位技術(shù)有效性的提升情況.他們通過(guò)對(duì)測(cè)試用例重新劃分的方法使得84.5%的程序的錯(cuò)誤定位的精確度得到提升或保持不變,其提升程度為6.15%,另外,15.5%的程序的定位結(jié)果的精確度降低,其降低程度為1.5%.其他基于聚類的方法也存在部分程序的定位結(jié)果變差的情況.這些基于聚類的方法與Masri 的工作有一定的相似性,其有效性很大程度上受到程序規(guī)模和測(cè)試集合大小的影響,如果目標(biāo)程序的規(guī)模過(guò)小,那么會(huì)導(dǎo)致程序執(zhí)行剖面的數(shù)據(jù)維度過(guò)小,使得測(cè)試用例之間的相似性過(guò)大,最終聚類算法難以分辨出測(cè)試用例之間的區(qū)別.如果測(cè)試集合太小,聚類分析得到的數(shù)據(jù)過(guò)少,也無(wú)法得到比較好的識(shí)別效果.

6 總結(jié)

偶然正確性現(xiàn)象是指包含錯(cuò)誤的語(yǔ)句被執(zhí)行卻產(chǎn)生了正確的程序輸出的現(xiàn)象,在程序執(zhí)行過(guò)程中普遍存在.偶然正確性現(xiàn)象被證明是影響錯(cuò)誤定位技術(shù)有效性的主要因素之一,因此亟需一種有效的方法消除偶然正確性現(xiàn)象對(duì)錯(cuò)誤定位技術(shù)的影響.以往的研究工作多數(shù)使用聚類等方法找到與失敗用例具有相似行為特征的用例,將其作為發(fā)生偶然正確性現(xiàn)象的用例從測(cè)試集合中刪除,或者將其歸類為失敗用例.與上述研究工作不同,本文關(guān)注錯(cuò)誤的值是如何產(chǎn)生并被傳播到程序的輸出中的,對(duì)在程序的執(zhí)行過(guò)程中各語(yǔ)句的執(zhí)行對(duì)程序輸出的影響程度進(jìn)行估計(jì),并基于這種估計(jì)對(duì)可疑度的度量方法進(jìn)行修正.與基于代碼覆蓋的錯(cuò)誤定位技術(shù)的對(duì)比實(shí)驗(yàn)也表明,本文提出的錯(cuò)誤定位技術(shù)提高或至少維持了錯(cuò)誤定位的安全性,并在一定程度上提高了錯(cuò)誤定位的精確度.對(duì)于工控軟件等偶然正確性現(xiàn)象頻繁發(fā)生的軟件,本文提出的錯(cuò)誤定位方法可以有效地消除偶然正確性現(xiàn)象帶來(lái)的副作用所產(chǎn)生的影響.本文根據(jù)偶然正確性概率對(duì)Tarantula 的可疑度計(jì)算方法進(jìn)行修正,這種方法同樣可用于Jaccard 等其他基于代碼覆蓋的錯(cuò)誤定位技術(shù).