基于偶然正確性概率的錯誤定位技術*

周小莉,趙建華

(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)

1 引 言

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

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

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

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

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

2 基本概念

2.1 基于代碼覆蓋的錯誤定位技術

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

基于代碼覆蓋的錯誤定位技術收集程序執行時的信息(包括語句執行覆蓋信息和測試用例是否通過的信息),然后根據某種統計公式對各語句的可疑度進行計算并排序.語句的可疑度高表示其包含錯誤的可能性大,可疑度高的語句將被測試人員優先檢查.基于代碼覆蓋進行錯誤定位的過程分為下面幾個步驟.

(1) 對程序進行插樁,生成插樁后的可執行程序.

(2) 在插樁后的程序上執行測試用例集合,收集測試執行時的信息.對于每個測試用例,標記其是否通過測試,并獲取對應的代碼覆蓋信息.在執行測試用例時,如果某條語句被至少執行過1 次,則標記該條語句被該測試用例所覆蓋.

(3) 通過統計代碼在成功和失敗用例中被覆蓋的比率來計算語句的可疑度,為測試人員提供一個需要被檢查的語句集合,這個語句集合被稱為語句檢查集.

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

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

當語句的可疑度相同時,使用另外一個度量值Confidence 來對語句進行排序:

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

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

為了衡量錯誤定位技術的有效性,可以用下面兩個指標對其進行評估.

(1) 安全性變化

安全性表示錯誤代碼的相對可疑度.假設f是實際包含錯誤的語句,使用score(f)表示根據錯誤定位方法計算出的f的可疑度值,T是被用來進行錯誤定位的測試集合.將安全性定義為下面這個集合的大小[20].

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

(2) 精確度變化

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

2.2 偶然正確性現象

對于基于代碼覆蓋的錯誤定位技術,如果一個測試用例執行了包含錯誤的語句,卻沒有產生錯誤的程序輸出,此時這個用例對錯誤定位沒有貢獻,甚至對可疑度的計算產生負面的影響.這種錯誤語句被執行卻沒有產生錯誤結果的現象稱為偶然正確性現象.

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

執行(execution),錯誤代碼需要被執行到;

感染(infection),執行錯誤代碼時必須觸發一個錯誤的中間狀態;

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

Masri[8]將偶然正確性現象進一步分類為強偶然正確性現象和弱偶然正確性現象.強偶然正確性現象發生在“執行”和“感染”兩個條件被滿足而“傳播”條件沒有被滿足時.若“執行”條件被滿足而“傳播”條件沒有被滿足,則無論“感染”條件是否被滿足,都稱發生了弱偶然正確性現象.許多工作都證明了偶然正確性現象的普遍性[5,8,24],尤其弱偶然正確性現象的發生是非常頻繁的[8].

2.3 偶然正確性現象對錯誤定位技術的影響

許多研究工作[5,6,24]都證明偶然正確性現象對錯誤定位的有效性帶來了副作用影響.Denmat 等人[25]對經典的基于代碼覆蓋的錯誤定位技術Tarantula 的局限性進行了研究,并表明要使其有效,必須滿足錯誤語句的執行在大多數情況下會導致程序出錯,即大多數程序的執行中不會發生偶然正確性現象.Masri 等人[5]對降低基于代碼覆蓋的錯誤定位技術有效性的因素進行了實驗性研究,結果表明,偶然正確性現象普遍存在,并且是影響基于覆蓋的錯誤定位技術有效性的主要因素之一.另外,Lei 等人[6]對測試用例的錯誤定位效能進行了分析和總結,證明偶然正確性現象是影響成功測試用例的錯誤定位效能的最主要的因素.

Table 1 Suspiciousness metrics of three CBFL techniques表1 3 種基于覆蓋的錯誤定位技術的可疑度計算公式

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

測試集合的這些屬性將用來計算語句的可疑度度量.在表1 中展示了Tarantula、Ochiai 和Jaccard 這3 種錯誤定位技術的可疑度度量的計算公式.假設在測試集合中有n個測試用例發生了偶然正確性現象.這里,使用M(s)和M＇(s)分別來表示忽略和考慮偶然正確性現象的可疑度度量.

首先以Tarantula 為例來展示可疑度的計算.假設s是包含錯誤的語句,在全部測試用例中有n個測試用例發生了偶然正確性現象,也就是說有n個測試用例覆蓋了語句s但并沒有產生錯誤的結果.這種情況下,M(s)的值被錯誤地估計了,為了得到更精確的值,需要將n個測試用例從s10中去掉,新的可疑度度量M＇(s)的值為

顯然地,M＇(s)＞=M(s),也就是說,如果不考慮發生偶然正確性現象的測試用例將低估錯誤語句s的可疑度.并且,隨著n的增大,M＇(s)的值也會相應增大.也就是說,在估算語句s的可疑度時,覆蓋語句s且因為偶然正確性而通過測試的測試用例個數越多,則可疑度估算的誤差越大,從而對錯誤定位的安全性和準確性造成影響.因此,針對該語句的可疑度估算需要做出不同程度的修正,以得到能夠更加準確地反映出語句中包含錯誤的可疑度排序.

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

對于Jaccard,考慮偶然正確性現象的可疑度公式為

同樣地,對于Ochiai 和Jaccard,考慮了偶然正確性現象所估算的可疑度值也是大于或等于原本公式計算出的可疑度值.實際執行中發生偶然正確性現象的測試用例越多,其可疑度估算的誤差也越大,因而對錯誤語句的可疑度排序的準確性產生影響.

3 偶然正確性現象的相關工作

Masri 等人[20]圍繞偶然正確性現象的定義、分類和產生原因進行了研究,并對其在實際場景中出現的頻率進行了實驗.Daran 等人[24]在對實際場景中出現的錯誤進行分析時,也驗證了偶然正確性現象的普遍性.

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

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

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

另外，偶然正確性現象在測試充分度和邊界值分析方面也引起了一些研究關注.基于代碼覆蓋的測試充分度是在測試中最常用的測試充分度準則,然而代碼覆蓋和錯誤發現之間并沒有很強的相關性.偶然正確性現象是導致代碼覆蓋無法準確表示測試充分程度的主要原因之一.在以往的工作[9-31]中,我們提出了一種估算程序執行時發生偶然正確性現象的概率的方法,并基于偶然正確性概率對測試充分度進行衡量.相對于基于代碼覆蓋的測試充分度,基于偶然正確性概率的測試充分度與錯誤發現之間有更強的相關性,更能準確地反映測試的充分程度.偶然正確性現象對邊界值分析也產生了副面影響.Hierons[32]對發生偶然正確性現象的實例進行了研究,并提出了一種生成不發生偶然正確性現象用例的方法.

4 基于偶然正確性概率的錯誤定位技術

基于代碼覆蓋的錯誤定位技術是通過語句在成功和失敗用例中被覆蓋的比率來對其可疑度進行計算的.然而,這個比率的計算會因為偶然正確性現象發生而產生誤差,需要根據偶然正確性現象對可疑度加以修正.

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

4.1 偶然正確性概率的估算

偶然正確性概率的估算[9]是本文工作的基礎,本文從代碼執行過程中內存空間變化的角度出發,通過動態的數據流和控制流兩個方面來估算程序執行過程中發生偶然正確性的概率.程序的執行過程可以看作這些語句實例對內存空間中值進行讀取、計算和寫入的過程.通常根據檢查程序輸出來判斷是否通過了測試,因此包含錯誤的程序在一次執行中發生偶然正確性概率可以看作在該錯誤執行后程序仍然產生正確輸出的概率.

偶然正確性現象發生在包含錯誤的語句被執行但是沒有產生錯誤的中間值時,或者錯誤語句產生了錯誤中間值卻沒有將錯誤的中間狀態傳遞到輸出中的時候.錯誤的中間值沒有被傳遞到輸出的原因是這個錯誤中間值沒有被用來生成最終的輸出,或者錯誤中間值在產生程序輸出前被掩蓋.這里的掩蓋可能是錯誤的值被后續語句的賦值所直接覆蓋,也可能是參與運算,卻偶然地產生了正確的運算結果.例如,假設錯誤語句s的執行為變量x進行了錯誤的賦值,如果x與值為False 的操作數進行并運算,或者與值為0 的操作數進行乘法運算,此時運算結果仍然是正確的,x中的錯誤會被掩蓋.再比如,x被用于比較運算中,雖然x的值是錯誤的,但與正確的取值在同一區間,那么比較運算的結果仍是正確的.

本文從運算和控制流兩方面來估計錯誤的中間狀態被傳播到程序輸出的概率.

(1) 運算的影響

運算的影響是估計錯誤的中間結果被計算性使用時對運算結果產生的影響.例如,當錯誤的中間值被用于賦值語句表達式、輸出語句或當作函數調用的參數以及被用于索引表達式中時,通常會得到錯誤的運算結果,但也仍然可能是正確的運算結果,這也是偶然正確現象出現的原因之一.運算結果的正確性與操作數的正確性和所參與的運算有關.如果操作數的取值都正確,那么運算結果也一定是正確的;如果至少一個操作數是錯誤的,那么運算結果也很可能是錯誤的.對于不同的運算和操作數的取值,操作數對運算結果正確性的影響程度也不同.對不同類型的運算,本文通過為每個操作數都設定不同的影響因子來量化該操作數對運算結果正確性的影響程度.運算結果的正確性概率可以根據運算的類型、操作數的正確性概率以及其當前的取值進行估計.

(2) 控制流的影響

控制流的影響是指錯誤的中間結果被判定性使用時所產生的影響.當錯誤的中間結果被用于分支語句的條件表達式時,會導致程序錯誤地執行了某條路徑,被實際執行的路徑上和應該被執行的路徑上的語句所改變的變量的值,其正確性都受到了影響.由于未被執行的路徑信息難以獲取,這里只考慮被執行的分支內所涉及的內存單元的正確性.對于一條語句實例s,為了估算控制流對其結果正確性概率的影響,我們首先找到影響s的所有控制表達式的執行實例,然后根據這些表達式的正確性概率對s的結果的正確性概率進行修正.

對于程序中的任意一個語句s,通過分析s的各個實例產生的中間結果直接或間接傳播到輸出的過程,可以估計出s的執行對程序輸出的影響程度.這里,我們將程序輸出不受到s的執行影響的概率定義為CCP(s,t),這一概率同時也是假定s中包含錯誤的前提下此次執行的輸出結果的正確性概率,即發生偶然正確性現象的概率.

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

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

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

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

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

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

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

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

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

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

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

Table 2 The calculation of incremental functions of FPValues表2 FPValues 增量函數的計算

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

5 實驗評估

5.1.1 目標程序和實驗設計

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

Table 3 Subject programs表3 目標程序

實驗中將基于偶然正確性概率的錯誤定位技術與Tarantula 技術進行比較,統計其錯誤定位結果安全性精確度的變化,并與相關工作[8]的結果進行對比.對于每一個版本的程序,按照下面幾個步驟進行實驗.

(1) 獲得預備信息

首先,根據執行結果將測試用例集合分類為執行成功和執行失敗兩種用例.然后,找到并標記包含錯誤的語句.對于每一個測試用例,標記是否覆蓋了包含錯誤的語句.

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

對于每一個語句s和每一個成功執行的測試用例s,計算CCP(s,t)的值,即假設s為錯誤語句時測試用例t因為偶然正確性現象而被通過的概率.

(3) 計算可疑度

對于每一個語句,分別使用Tarantula 和基于偶然正確性概率及代碼覆蓋的錯誤定位技術來計算可疑度.對于每個版本的程序,分別統計其錯誤定位結果的安全性和準確性的變化情況.

5.1.2 實驗結果和分析

本文對目標程序執行時發生偶然正確性現象的頻率進行了統計,并將基于偶然正確性概率的錯誤定位方法與Tarantula 的錯誤定位結果的安全性和精確度進行對比.

(1) 偶然正確性現象的發生頻率

在實驗中將覆蓋了錯誤語句的被通過用例歸類為偶然正確性用例.圖1 展示了偶然正確性用例的統計信息,圖中將錯誤版本的程序按照原始程序進行了分組顯示,其橫坐標是原始程序,縱坐標為這個程序的所有變種程序所對應的測試集合中偶然正確性用例所占的平均比例,即偶然正確性現象出現的平均頻率.對于所有原始程序的錯誤版本,其偶然正確性現象發生的平均頻率都超過20%,其中對于“schedule2”的變種程序,偶然正確性現象的平均概率甚至高達90%以上.對圖中的數據作進一步的統計后發現,偶然正確性現象在所有目標程序執行中出現的平均頻率為53%.很明顯地,偶然正確性現象在目標程序中非常頻繁地出現.

(2) 錯誤定位結果的對比

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

(a) 安全性方面

從圖2 中可以看出,錯誤定位的安全性被提升的程序版本比例在75%～100%之間.對圖上所有程序進行綜合統計后發現,對于95%的程序,其錯誤定位的安全性都得到了提升,其他5%的程序(只有3 個程序版本)維持了原有的錯誤定位的安全性指標,沒有任何程序的安全性被降低.這個實驗結果表明,對于所有版本的程序,基于偶然正確性的錯誤定位技術都提高或維持了錯誤定位的安全性.

(b) 精確度方面

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

Fig.1 Percentage of coincidental correctness tests圖1 發生偶然正確性現象的用例所占的比例

在實驗中,實際執行時發生偶然正確性概率高的程序在精確度上的表現相對優于其他程序,這也說明,我們的方法可以有效地消除偶然正確性現象對錯誤定位的影響.發生偶然正確性現象頻率較低的程序在錯誤定位精確度上的表現上略劣于其他程序,這是因為,消除偶然正確現象的影響對其定位結果的提升是有限的.另外,某些程序在精確度上被降低的原因可能與偶然正確現象概率的估算值與實際的差異有關.

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

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

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

(c) 與相關工作的對比

在相關工作中,Masri 等人[8]提出了多種提高錯誤定位技術有效性的技術,并在西門子程序集中的18 個版本的程序上進行了實驗.在這項工作中,達到最優效果的技術(系數為0.8 的技術3)對于80%的程序提高了錯誤定位的安全性,對于61%的程序提高了錯誤定位的精確度.本文在實驗中所選取的程序包含了文獻[8]的工作中所用的目標程序,我們的方法提高了95%的程序定位結果的安全性,提高了77%的程序定位結果的精確度.相對于Masri 的方法,本文提出的方法在安全性和精確性上都有一定的優勢.

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

6 總結

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