基于程序譜的錯(cuò)誤定位技術(shù)的研究

蔡燁挺 李唯實(shí) 毛曉光 喬建軍

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

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

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

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

1 研究背景及動(dòng)機(jī)

1.1 背景

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

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

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

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

在進(jìn)行聚類分析后，具有相似程序譜的測(cè)試用例會(huì)被認(rèn)為是具有相似行為，從而劃分至相同聚類。若我們認(rèn)為巧合性正確測(cè)試用例的行為彼此類似，則我們同樣可以認(rèn)為在所有聚類中包含巧合性正確測(cè)試用例的聚類在聚類中所占的百分比小于在所有測(cè)試用例中的巧合性正確測(cè)試用例所占的百分比。基于該假設(shè)，基于聚類的策略可以用于降低巧合正確性問(wèn)題，并且能夠提高SFL的有效性。

2 我們的方法

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

2.1 程序譜收集

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

2.2 聚類分析

已收集測(cè)試用例的覆蓋信息即程序譜將作為聚類的對(duì)象。對(duì)象的數(shù)量與測(cè)試用例的數(shù)量相同。距離函數(shù)使用N維歐幾里得距離-因?yàn)槠溆?jì)算方便并且使用廣泛。

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

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

2.3 覆蓋矩陣重建

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

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

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

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

2.4 錯(cuò)誤定位

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

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

3.2 評(píng)估標(biāo)準(zhǔn)

SFL的準(zhǔn)確度通常由在找到錯(cuò)誤語(yǔ)句前所需檢查的語(yǔ)句數(shù)量所占百分比來(lái)評(píng)估。我們也采用這一概念，通過(guò)對(duì)比原始的SFL與我們策略的錯(cuò)誤定位精度（簡(jiǎn)稱Acc）來(lái)對(duì)我們的策略性能進(jìn)行評(píng)估。Acc值越低表明性能越好。

為了進(jìn)行更詳細(xì)的比較，我們使用相對(duì)改善（簡(jiǎn)稱Imp）進(jìn)行分析。Imp是對(duì)使用我們的策略與使用SFL找到所有的錯(cuò)誤需要檢查的總語(yǔ)句數(shù)量進(jìn)行比較。Imp值越低表明性能越好。

3.3 結(jié)果及分析

3.3.1 聚類數(shù)量的影響

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

圖1呈現(xiàn)的是在不同s下我們的方法的Imp值。從圖1中可以看出，我們的策略可以改善SFL的性能，并且當(dāng)s > =1.2時(shí)達(dá)到最佳。

3.3.2 精度的提高

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

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

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

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

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

3.3.3 與排除策略對(duì)比

在之前關(guān)于巧合正確性問(wèn)題的研究中，研究人員通常對(duì)識(shí)別出的巧合性正確測(cè)試用例采用排除策略。為了驗(yàn)證我們的方法，將我們的方法與Masri的方法以及Yi Miao的方法進(jìn)行比較。

Masri等人僅選擇了18個(gè)錯(cuò)誤版本作為其主體程序，他們使用安全性變化和精度變化作為其評(píng)估指標(biāo)。表3說(shuō)明了對(duì)于他們選擇的18種錯(cuò)誤版本，他們及我們方法的實(shí)驗(yàn)結(jié)果。正如表3所示，我們的方法能夠更加有效的改善SFL的準(zhǔn)確性。

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

3.4 對(duì)實(shí)驗(yàn)有效性的影響

我們實(shí)驗(yàn)有效性的不足之處可以概括如下：

首先，我們使用西門子的程序組件作為我們主體程序，該程序均為小型C程序，并且所有的錯(cuò)誤均為手動(dòng)輸入。為了降低這個(gè)不足之處，我們計(jì)劃在將來(lái)將我們的技術(shù)應(yīng)用于更加大型的程序。

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

4 結(jié)論及今后的工作

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

在今后的工作中，我們準(zhǔn)備進(jìn)行更全面的實(shí)證研究，并探討一下問(wèn)題：

（1）通過(guò)更多程序評(píng)估我們基于聚類的策略。

（2）尋求更好的聚類算法以適應(yīng)本文中的情況。在我們的方法中，失敗的測(cè)試用例聚類要么過(guò)于集中，要么過(guò)于分散都會(huì)導(dǎo)致不好的結(jié)果。由于其簡(jiǎn)便性，在我們的實(shí)驗(yàn)中采用了K均值，事實(shí)上還有許多其他的聚類算法需要進(jìn)行探討。

（3）對(duì)于多錯(cuò)誤如何對(duì)我們的方法的影響進(jìn)行實(shí)證研究，并探討如何應(yīng)對(duì)此種情況以最小化其不利影響。

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

作者簡(jiǎn)介

蔡燁挺（1988-）男，國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院碩士。研究方向?yàn)檐浖こ獭?/p>

作者單位

1.國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院 湖南省長(zhǎng)沙市 410073

2.北京信息技術(shù)研究所 北京市 100085