蔡燁挺 李唯實 毛曉光 喬建軍

摘 要基于程序譜的錯誤定位技術經由執(zhí)行成功和失敗測試用例來獲取測試用例的代碼覆蓋信息，并基于這些信息來識別程序的錯誤所在。然而，這些技術的有效性會受到巧合正確性的不利影響。所謂的巧合正確性，是指當程序即便執(zhí)行了錯誤處代碼，卻仍然能夠產生正確的輸出的情況。本文提出了一種基于聚類的策略，以提高基于程序譜的錯誤定位技術的有效性。這種策略基于相同聚類的測試用例擁有類似的行為的思想。因此，巧合正確測試用例不僅有很高的概率與失敗測試用例類似，而且也有很高的概率彼此類似。

【關鍵詞】基于程序譜的錯誤定位 巧合正確性 聚類分析 覆蓋矩陣重建

在軟件開發(fā)生命周期和過程中，軟件調試對提高軟件質量有著非常強大的作用。然而，調試通常需要花費大量的人力和時間，在調試的主要任務中，錯誤定位已被公認為最困難，最繁瑣，以及最耗時的步驟。為了減少調試的成本，很多研究人員把注意力放到了基于程序譜的錯誤定位（SFL）技術，該技術具有簡單、自動和高效率的優(yōu)點。

SFL通常會收集失敗以及成功的測試用例的執(zhí)行信息，用于構建程序譜。信息收集完畢后，SFL將可采用不同的統(tǒng)計公式來評估程序中代碼的可疑程度并且按照可疑程度對程序代碼進行排序。雖然SFL的有效性已得到證實，但仍然受到巧合正確性的影響，巧合正確是指在錯誤代碼被執(zhí)行時，程序仍然能產生正確的輸出的情況。SFL技術之所以受到巧合正確性的影響，根源在于SFL的基本思想，即在程序內主要由錯誤測試運行所執(zhí)行的代碼比那些由成功測試運行所執(zhí)行的代碼要更有可能是包含錯誤?；谠摾砟?，當出現大量巧合正確的測試用例時，錯誤代碼的可疑性將可能會低于主要由失敗測試運行執(zhí)行的程序代碼的可疑性，從而增加了發(fā)現錯誤的開銷。因此，排除巧合正確測試用例能夠安全地提高SFL的效率和準確性。然后，由于錯誤代碼的位置無法預知，很難識別所有通過測試用例中的巧合正確的測試用例。同時，用于識別巧合正確測試用例的策略也可能會排除掉很多其他測試用例。

1 研究背景及動機

1.1 背景

基于程序譜的錯誤定位是錯誤定位方法中最受歡迎的方法之一，并且因其簡便性及有效性受到了多方關注。該方法基于一個簡單的常識經驗：主要由失敗測試運行用例執(zhí)行的程序代碼更可能包含錯誤，而主要由通過成功測試用例所執(zhí)行的程序代碼包含錯誤的可能性更小。在SFL中，測試用例的動態(tài)執(zhí)行可以采用一個二進制序列進行表示，例如程序譜。在程序譜中每一比特對應一條程序代碼，其中1表示該代碼在本次運行中被執(zhí)行，而0表示該代碼未被執(zhí)行。

以往研究表明：巧合正確性對SFL的準確度的影響很大，巧合正確是指當錯誤代碼被執(zhí)行而程序仍能夠產生正確結果輸出的情況。W.Masri等人已經證明了巧合正確性會降低SFL的安全性。SFL的效率和準確性可以通過清理巧合正確的測試用例得到改善。然而，由于我們無法預知錯誤地點，很難識別出巧合正確測試用例。X. Wang等人提出了提出了情景模式以幫助覆蓋精細化，從而加強程序錯誤和錯誤語句的覆蓋之間的聯系。W. Masri等人主要專注于如何識別通過測試用例中更有可能包含有巧合性正確的子集。他們首先確定程序單元（cce）中有可能與巧合正確的測試用例相關的部分，然后將導致一些可疑cce為巧合正確的測試用例進行分類。Aritra通過比較測試用例之間的相似性來識別巧合正確的測試用例。為了削弱巧合正確性對SFL的影響，他對于那些與失敗測試用例相似的通過測試用例采用了兩種不同的策略—給予其低權重或將其排除。與Aritra的想法類似，Yi Miao等人同樣認為巧合正確的測試用例肯定與失敗測試用例有相似行為，他們將測試用例劃分聚類，并且將與失敗測試用例在同一聚類的通過測試用例加以標簽，作為識別出的巧合正確的測試用例（Ticc）。為了降低巧合正確性的不利影響，采用以下兩種方式來處理識別出的巧合正確的測試用例：將其刪除或重貼標簽。

1.2 研究動機

Yi Miao等人已說明在軟件測試中，巧合正確性是很常見的，并且通過排除巧合正確的測試用例，錯誤定位的準確度會得到提高，同時SFL的有效性可以得到改善。然而，由于錯誤單元的位置不可預知，幾乎不可能做到識別出所有巧合正確測試用例。在之前的研究中，排除巧合正確測試用例的策略可能會同時排除掉很大一部分其他成功測試用例。

在進行聚類分析后，具有相似程序譜的測試用例會被認為是具有相似行為，從而劃分至相同聚類。若我們認為巧合性正確測試用例的行為彼此類似，則我們同樣可以認為在所有聚類中包含巧合性正確測試用例的聚類在聚類中所占的百分比小于在所有測試用例中的巧合性正確測試用例所占的百分比?；谠摷僭O，基于聚類的策略可以用于降低巧合正確性問題，并且能夠提高SFL的有效性。

2 我們的方法

在本文中，我們提出了一種基于聚類的方法來削弱巧合正確性對錯誤定位技術的影響，該方法基于程序譜將測試用例進行聚類處理，使具有相似行為的測試用例被分組到同一聚類中，同時相互間差異很大的測試用例會被放置在不同的聚類中。我們的策略是：在使用SFL技術找尋程序錯誤時，開發(fā)人員可以采用以下步驟來提高SFL的有效性。

2.1 程序譜收集

在本文中，我們使用gcov來進行代碼插裝，并借此來收集代碼覆蓋信息。收集完成后，每個測試用例的執(zhí)行信息將由其程序譜表示：pi =，其中n表示給定程序中可執(zhí)行語句的數量，ej=1表示第j條語句在第i個測試用例的運行中被執(zhí)行，否則ei=0。

2.2 聚類分析

已收集測試用例的覆蓋信息即程序譜將作為聚類的對象。對象的數量與測試用例的數量相同。距離函數使用N維歐幾里得距離-因為其計算方便并且使用廣泛。

由于程序中可能存在太多的可執(zhí)行語句，測試用例的程序譜的維度可能會非常大，從而嚴重影響了聚類分析的時間。因此，我們使用動態(tài)基本塊（DBB）來降低單個對象的維度。一個DDB是程序中若干代碼的集合-這些代碼被測試組件中相同的測試用例所覆蓋，同一個DDB中的代碼在覆蓋矩陣中對應的行是完全相同的，因此，DDB的數量要遠小于statements的數量。通過使用DBB，我們可以將程序譜pi=轉化為新的程序譜pi= ，其中DBBi=1表示第i個DBB中的代碼全部被執(zhí)行。通常，m要遠遠小于n，所以使用新的程序譜進行聚類分析可以節(jié)約大量的時間。

由于其簡便和快速性，我們選擇了簡單K均值方式作為聚類算法。簡單K均值算法需要事先輸入聚類的數量作為參數。在本論文中，該參數是根據所選測試組中程序的DBB數量決定。假設n表示聚類的數量，則n = |DBB|*s，其中|DBB|指DBB的數量。

2.3 覆蓋矩陣重建

在聚類之后，測試用例依據其程序譜被劃分至不同的聚類。根據本文中提出的假設，我們將通過聚類的語句覆蓋信息重建覆蓋矩陣。根據聚類中包含測試用例的不同，我們將聚類劃分為Cf與Cp兩類，Cf是指包含失敗測試用例的聚類，而Cp則僅包含成功用例。對于不同種類的聚類，我們采用不同的策略來收集聚類程序譜：

Cf中的聚類： 由于成功測試用例與失敗測試用例一起被分類至Cf聚類中，將有很大可能是巧合正確的測試用例，我們將采用失敗測試用例的程序譜來構建整個聚類的程序譜：對于Cf中的第m個聚類，我們使用聚類程序譜cm=，其中si= i表示執(zhí)行第i個語句時cm中有i個失敗測試用例。

Cp中的聚類： Cp中的測試用例是巧合正確的可能性很小。對于Cp中的第j個聚類，我們采用聚類程序譜cj=，其中si=1表示聚類中至少有一個測試用例執(zhí)行第i個語句。

因此，通過連接所有聚類的程序譜，我們可以重建一個新的覆蓋矩陣，用于表現不同種類行為的代碼覆蓋信息。

2.4 錯誤定位

在重建新的覆蓋矩陣后，我們可以使用統(tǒng)計公式來計算程序代碼為錯誤的可疑程度。

由于我們的目的不是與各種錯誤定位技術進行比較，而是為了提高錯誤定位技術的準確度，我們選擇了 Ochiai、Jaccard、Hamming以及Optimalp這些參考文獻與我們的策略一起來對缺陷進行定位。正如XiaoyuanXie等人在參考文獻中所提到的，我們選擇的SFL技術可以代表其他的SFL技術。因此，我們有理由相信，只要我們的策略能夠提高上述5種技術的有效性，則其也將有益于其他SFL技術。

3 實驗與評估

3.1 實驗設置

在本論文中，我們選擇西門子程序組以及Space作為測試程序。西門子的程序組件中包含7個C程序，并且所有的程序均包含正確的版本，一定數量包含單一錯誤的錯誤版本，以及一個相關的測試集。Space 是由歐洲航天局最初編寫的，并且包含有38個錯誤版本。 所選擇程序的詳細信息見表1。 表格的第一列是程序的名稱。第二列中列出了外面實驗中所使用每個程序的錯誤版本數量。第三列說明了每個程序包含可執(zhí)行語句的數量（代碼行數）。第四列說明了每個程序中測試用例的數量。

此外，我們排除那些任何測試用例均不會檢測到異常的錯誤版本，以及那些修改了頭文件的錯誤版本，再忽略掉定義或聲明類型的錯誤版本。最終，實驗中使用了146種錯誤版本。

有兩種錯誤需要特別注意。第一種是一個錯誤由多個語句共同組成，我們假設對這些語句的任意一個進行檢查都能夠定位該錯誤。另外一種是與缺少的代碼相關的單一錯誤，我們假設開發(fā)者對缺少代碼的前后語句進行檢查均能發(fā)現缺少代碼的錯誤。

我們使用gcov（GNU call-coverage profiler）來收集程序中的語句覆蓋信息，然后通過Weka進行聚類分析。所有的實驗均使用配置有2.20 GHz英特爾（R）酷睿（TM）2雙核CPU、4 GB內存以及Ubuntu 10.04系統(tǒng)的電腦進行。

3.2 評估標準

SFL的準確度通常由在找到錯誤語句前所需檢查的語句數量所占百分比來評估。我們也采用這一概念，通過對比原始的SFL與我們策略的錯誤定位精度（簡稱Acc）來對我們的策略性能進行評估。Acc值越低表明性能越好。

為了進行更詳細的比較，我們使用相對改善（簡稱Imp）進行分析。Imp是對使用我們的策略與使用SFL找到所有的錯誤需要檢查的總語句數量進行比較。Imp值越低表明性能越好。

3.3 結果及分析

3.3.1 聚類數量的影響

在我們的論文中，聚類的數量n是一個影響我們策略的重要因素。在之前的部分，我們假設n = |DBB|*s是聚類的數量。

圖1呈現的是在不同s下我們的方法的Imp值。從圖1中可以看出，我們的策略可以改善SFL的性能，并且當s > =1.2時達到最佳。

3.3.2 精度的提高

圖2表明在我們選擇的所有錯誤版本中SFL與我們方法的Acc的比較。x軸表示被檢測可執(zhí)行語句的百分比。y軸表示錯誤版本的百分比。圖2中的任一點表示在檢查了百分之幾的代碼后，能夠找到百分之幾的錯誤版本中的錯誤。

如圖2所示，對于Optimalp公式，我們方法的曲線與其相關的SFL很接近。但是我們方法在采用其他SFL公式時，其曲線總是比只采用該公式的SFL技術曲線提升得更快，接近Optimalp的曲線。這表明了我們的方法明顯提高了所選類型SFL（不包括Optimalp）的準確度。

為了進一步的詳細比較，圖3說明了在每個程序中我們所采用的基于聚類的策略對于每種類型SFL的Imp值。x軸表示程序的名稱。y軸展現了特定種類SFL的Imp值。圖3中的表格列出了每個程序Imp的具體數值。

如圖3中所示，除了Optimalp，每個程序的Imp數值均小于100%。這表明我們的策略改善了所有程序SFL的有效性。以圖5中的Ochiai為例，在程序print_tokens2中最低Imp為58%，在程序program replace中最高Imp為98%。這說明我們的策略對于基于Ochiai 的定位技術在程序print_tokens2中獲得了最大的改善，在程序program replace中則改善得最少。此外，這還意味著在定位程序print_tokens2中的錯誤時，我們的方法需要檢測Ochiai所需檢測語句的58%，同時在定位程序program replace時，我們的方法需要檢測基于Ochiai 的定位技術所需檢測語句的98%。

然而，我們的策略也有失敗的時候。表2中列出了基于Ochiai 的定位技術得到的Imp值小于，等于以及大于100%時失敗版本的百分比。有10.9%的失敗版本的Imp大于100%，這表明我們的策略在此情況下未能改善其有效性。但總體而言，我們的策略仍然是有效的。

3.3.3 與排除策略對比

在之前關于巧合正確性問題的研究中，研究人員通常對識別出的巧合性正確測試用例采用排除策略。為了驗證我們的方法，將我們的方法與Masri的方法以及Yi Miao的方法進行比較。

Masri等人僅選擇了18個錯誤版本作為其主體程序，他們使用安全性變化和精度變化作為其評估指標。表3說明了對于他們選擇的18種錯誤版本，他們及我們方法的實驗結果。正如表3所示，我們的方法能夠更加有效的改善SFL的準確性。

圖4是我們選擇的119個錯誤版本（如圖2所示）中Yi Miao的方法與Ochiai的方法，以及我們的方法與Ochiai的方法的ACC的比較。如圖所示，我們方法的曲線始終要高于Yi Miao的方法。這表明了我們基于聚類的策略要優(yōu)于Yi Miao的排除策略。

3.4 對實驗有效性的影響

我們實驗有效性的不足之處可以概括如下：

首先，我們使用西門子的程序組件作為我們主體程序，該程序均為小型C程序，并且所有的錯誤均為手動輸入。為了降低這個不足之處，我們計劃在將來將我們的技術應用于更加大型的程序。

此外，在我們的程序中使用gcov記錄覆蓋信息，同時使用數據挖掘工具Weka進行聚類分析。這兩項方法均為成熟并且廣泛使用的方法。同時，在我們的研究中，由于其簡便和有效性，采用了簡單的K均值作為聚類算法。然而，在對失敗測試用例進行聚類時，過于集中或過于分散的情況，均會對結果產生不利影響。

4 結論及今后的工作

在本論文中，我們提出了一種基于聚類的策略以降低巧合正確性對SFL有效性的不利影響。為了提高SFL的有效性，為重建覆蓋舉證引入了兩種策略，即選擇Cf中的失敗測試用例的程序譜，以及獲取Cp中聚類的覆蓋信息。為了評估所提出的方法，我們進行了一項實驗。實驗結果表明，該實驗取得了預計理想情況結果相近似的結果。

在今后的工作中，我們準備進行更全面的實證研究，并探討一下問題：

（1）通過更多程序評估我們基于聚類的策略。

（2）尋求更好的聚類算法以適應本文中的情況。在我們的方法中，失敗的測試用例聚類要么過于集中，要么過于分散都會導致不好的結果。由于其簡便性，在我們的實驗中采用了K均值，事實上還有許多其他的聚類算法需要進行探討。

（3）對于多錯誤如何對我們的方法的影響進行實證研究，并探討如何應對此種情況以最小化其不利影響。

（4）探索我們策略失敗的原因。

作者簡介

蔡燁挺（1988-）男，國防科技大學計算機學院碩士。研究方向為軟件工程。

作者單位

1.國防科技大學計算機學院 湖南省長沙市 410073

2.北京信息技術研究所 北京市 100085