何海江

(長(zhǎng)沙學(xué)院計(jì)算機(jī)工程與應(yīng)用數(shù)學(xué)學(xué)院,湖南 長(zhǎng)沙 410022)

1 引言

調(diào)試和測(cè)試是軟件生命周期中的重要活動(dòng)，這其間，開(kāi)發(fā)人員為移除軟件故障，耗時(shí)且費(fèi)力。軟件出現(xiàn)故障，首要任務(wù)是找到導(dǎo)致出錯(cuò)的代碼。代碼審查和靜態(tài)檢查固然是有效的故障定位方法，但前者人工耗費(fèi)大，后者難以發(fā)現(xiàn)深層次的邏輯錯(cuò)誤。VS Code、IDEA和Eclipse等開(kāi)發(fā)平臺(tái)提供的斷點(diǎn)調(diào)試方法，不能確定代碼檢查順序，完全依賴(lài)程序員的編程經(jīng)驗(yàn)來(lái)查找錯(cuò)誤。因此，人們開(kāi)始研究自動(dòng)化的軟件錯(cuò)誤定位[1,2]技術(shù),其中基于程序譜的軟件錯(cuò)誤定位SBFL(Spectrum-Based Fault Localization)技術(shù)最受關(guān)注?，F(xiàn)代軟件的規(guī)模越來(lái)越大，而CPU、內(nèi)存等資源始終受到限制，SBFL這一類(lèi)輕量級(jí)方法更有實(shí)用價(jià)值。

SBFL可應(yīng)用于文件、類(lèi)、方法(函數(shù))、代碼片段、語(yǔ)句(代碼行)和謂詞等程序?qū)嶓w。本文聚焦于語(yǔ)句級(jí)故障定位，只討論相關(guān)技術(shù)。人們提出了許多SBFL方法[2]，然而，這些方法在定位故障語(yǔ)句時(shí)，僅考察語(yǔ)句覆蓋結(jié)果和測(cè)試用例通過(guò)與否，故而其性能受到限制。為克服這一缺陷，一系列結(jié)合程序譜、代碼靜態(tài)特征、代碼動(dòng)態(tài)特征的搜索方法[3]得到發(fā)展。然而，這些方法要么獲取程序特征的代價(jià)大，要么只在方法級(jí)、類(lèi)級(jí)和文件級(jí)上驗(yàn)證性能。

為了能輕量地定位到故障語(yǔ)句，本文提出了一種語(yǔ)句級(jí)軟件錯(cuò)誤定位的排序?qū)W習(xí)方法。在表征語(yǔ)句時(shí)，除語(yǔ)句的SBFL可疑度值外，還選擇了3類(lèi)輕量級(jí)特征：(1)局部變量數(shù)、邏輯操作符數(shù)和函數(shù)調(diào)用數(shù)等語(yǔ)句靜態(tài)屬性；(2)結(jié)構(gòu)化類(lèi)別;(3)變量譜。在排序?qū)W習(xí)過(guò)程中，使用跨項(xiàng)目的方式訓(xùn)練排序模型。數(shù)據(jù)集包含使用Java、C和C++ 編程語(yǔ)言開(kāi)發(fā)的22個(gè)項(xiàng)目，包括753個(gè)帶故障的版本，故障語(yǔ)句全部來(lái)源于程序員實(shí)際的編程活動(dòng)，項(xiàng)目規(guī)模有大有小，版本所含錯(cuò)誤個(gè)數(shù)有多有少。實(shí)驗(yàn)結(jié)果表明，將SBFL可疑度值分別與3類(lèi)語(yǔ)句特征結(jié)合后，即使與表現(xiàn)最佳的SBFL方法相比，新方法都能大幅度減少待排查的語(yǔ)句。3類(lèi)輕量級(jí)特征中，尤以語(yǔ)句靜態(tài)屬性最能改善錯(cuò)誤定位模型的性能。同時(shí)也發(fā)現(xiàn)，一些在小規(guī)模數(shù)據(jù)集或者人工注入故障版本上得到驗(yàn)證的SBFL方法，表現(xiàn)并不好。

2 基于程序譜的軟件錯(cuò)誤定位

基于程序譜的軟件錯(cuò)誤定位技術(shù)僅需收集2類(lèi)信息：(1)測(cè)試用例的執(zhí)行結(jié)果：成功或失??；(2)程序運(yùn)行時(shí)，是否覆蓋語(yǔ)句。形式上，每條可執(zhí)行語(yǔ)句的運(yùn)行特征可用四元組〈aep,aef,anp,anf〉表示。對(duì)程序的每一條語(yǔ)句，aep和aef分別表示測(cè)試用例覆蓋它并且程序運(yùn)行結(jié)果成功或失敗的數(shù)目；anp和anf則分別表示測(cè)試用例未覆蓋它并且程序運(yùn)行結(jié)果成功或失敗的個(gè)數(shù)。

SBFL方法將程序譜轉(zhuǎn)換成不同的語(yǔ)句可疑度計(jì)算公式(簡(jiǎn)稱(chēng)為SBFL公式)。SBFL公式可看作映射函數(shù)，將特征向量映射成一個(gè)實(shí)數(shù)值(可疑度值)。當(dāng)故障發(fā)生時(shí)，依據(jù)這些映射函數(shù)逐一計(jì)算可執(zhí)行語(yǔ)句的可疑度值，將語(yǔ)句按照可疑度從大到小排序。排查故障代碼時(shí)，從順序表頂端開(kāi)始逐一排查語(yǔ)句，直到發(fā)現(xiàn)錯(cuò)誤代碼。

DStar2[4]、GP02[5]、GP10[5]、GP13[5]、Tarantula[6]、Ochiai[6]、NaishO[7](即Naish1[8])、NaishOp[7](即Naish2[8])、Wong1[9]、Wong2[9]、Wong3[9]、SBI、Overlap、RussellRao、Jaccard、Dice、Zoltar、M2、Goodman、Anderberg、Kulczynski1、Kulczynski2和Ample，都是研究人員提出的SBFL公式。SBI公式在文獻(xiàn)[10]中有相應(yīng)的描述；從Overlap到Ample，這11個(gè)公式在文獻(xiàn)[7，8]中有相應(yīng)的描述。

Tarantula、Zoltar、Kulczynski2、RusselRao、Ochiai、Ample、M2、Jaccard 和Anderberg，這9個(gè)SBFL公式的值都處于0～1，其余14個(gè)SBFL公式的值可歸一化到[0,1]。例如式(1)是Overlap公式常規(guī)的計(jì)算方法，其值區(qū)間為[0,+∞)，經(jīng)過(guò)式(2)的歸一化處理后，其值區(qū)間為[0,1]。

(1)

(2)

Lucia 等人[11]對(duì)比了將近40 種SBFL,發(fā)現(xiàn)Ochiai公式的故障定位能力相對(duì)突出，任何一種SBFL方法都無(wú)法在多數(shù)項(xiàng)目(程序)中超過(guò)其它方法。Pearson等人[12]在6個(gè)項(xiàng)目、323個(gè)版本的實(shí)際故障數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)也證實(shí)了這一點(diǎn)。

3 基于搜索的軟件錯(cuò)誤定位

特定的項(xiàng)目，受軟件規(guī)模、測(cè)試套件、單個(gè)或多個(gè)故障、編程語(yǔ)言等因素的影響，可能出錯(cuò)方式與其它項(xiàng)目迥異。以表征語(yǔ)句可疑度的SBFL公式為特征集，機(jī)器學(xué)習(xí)技術(shù)可為項(xiàng)目搜索到對(duì)應(yīng)的最優(yōu)故障代碼判別模型。MULTRIC(MULtiple ranking meTRICs for fault localization)[13]組合25個(gè)SBFL公式，LTR-sbfl[14]將非故障語(yǔ)句與故障語(yǔ)句兩兩組合成復(fù)合樣本，再由排序?qū)W習(xí)算法訓(xùn)練映射函數(shù)。然而，這些方法和傳統(tǒng)的SBFL方法相似，可疑度只依賴(lài)于測(cè)試用例執(zhí)行結(jié)果和程序?qū)嶓w覆蓋信息，錯(cuò)誤定位效果受到嚴(yán)重制約。若要提升性能，程序邏輯復(fù)雜度、故障語(yǔ)句類(lèi)型和測(cè)試用例集等因素都應(yīng)該考慮。由此，研究人員拓寬思路，引入表征軟件的其它視角的數(shù)據(jù)，開(kāi)發(fā)了許多基于搜索的軟件錯(cuò)誤定位方法[3]。

這些搜索技術(shù)的特征，除SBFL公式外，還包括：多個(gè)變異技術(shù)、源代碼復(fù)雜度和文本相似性特征[10]，方法存在時(shí)長(zhǎng)、程序元素改變頻率等代碼變化測(cè)度[15]，函數(shù)級(jí)代碼復(fù)雜度[16]，長(zhǎng)短期記憶網(wǎng)絡(luò)自動(dòng)化學(xué)習(xí)代碼的語(yǔ)義特征[17]，項(xiàng)目開(kāi)發(fā)報(bào)告形成的歷史譜[18]，語(yǔ)句類(lèi)別[19]和測(cè)試用例的全部覆蓋信息[20]。PRINCE(PRecise machINe-learning-based fault loCalization tEchnique)和CombineFL[21,22]綜合多類(lèi)特征，集成SBFL、變異測(cè)度、切片、棧跟蹤、謂詞變化、代碼復(fù)雜度、故障報(bào)告和開(kāi)發(fā)歷史，比較這些靜態(tài)特征和動(dòng)態(tài)特征對(duì)排序?qū)W習(xí)算法訓(xùn)練模型的影響程度。但是，這些方法多用于文件級(jí)、類(lèi)級(jí)和方法級(jí)(函數(shù)級(jí))故障定位，大部分方法的語(yǔ)句級(jí)特征獲取代價(jià)大。

4 集成靜態(tài)屬性和程序譜的方法

調(diào)試時(shí)，程序員需要定位到故障語(yǔ)句，不能僅限于類(lèi)或方法。自動(dòng)化程序軟件修復(fù)[1]這類(lèi)應(yīng)用也只能運(yùn)用語(yǔ)句級(jí)故障定位技術(shù)。同時(shí)，為使得技術(shù)能應(yīng)用到代碼量具有一定規(guī)模的工業(yè)軟件，本文聚焦于語(yǔ)句級(jí)的輕量方法，要求代碼特征及可疑度值的計(jì)算代價(jià)極小。受到搜索式軟件錯(cuò)誤定位和軟件復(fù)雜性度量研究工作[23]的啟發(fā)，本文提出了一種集成程序譜和代碼行靜態(tài)屬性的排序?qū)W習(xí)方法，由線(xiàn)性排序支持向量機(jī)構(gòu)造語(yǔ)句級(jí)的錯(cuò)誤定位模型。語(yǔ)句的其它輕量特征：結(jié)構(gòu)化類(lèi)別和變量譜，也能夠方便地集成到搜索算法中。

程序譜特征來(lái)源包括文獻(xiàn)[13]的25個(gè)SBFL公式，再加上近年來(lái)被多次比較的一些SBFL公式。設(shè)定程序只包含單個(gè)故障，文獻(xiàn)[8]從理論上證明了6組SBFL公式具有等價(jià)性質(zhì),因此移除了幾個(gè)公式，最終選擇第2節(jié)列出的23個(gè)SBFL公式為排序?qū)W習(xí)的程序譜特征。為加快學(xué)習(xí)算法收斂速度，將這些SBFL的可疑度值歸一化到[0,1]。

結(jié)構(gòu)復(fù)雜的代碼中更容易隱藏錯(cuò)誤。因此，本文將如表1所示的4種語(yǔ)句類(lèi)別作為表征語(yǔ)句的特征，特征值為0或者1。為簡(jiǎn)化問(wèn)題，并不執(zhí)行重疊計(jì)數(shù)，任一語(yǔ)句只屬于某一類(lèi)，若循環(huán)(或return)語(yǔ)句包含條件判斷，判其為循環(huán)(或return)語(yǔ)句。

Table 1 Structural types of statements

文獻(xiàn)[19]也用到了語(yǔ)句類(lèi)別，與本文做法有2點(diǎn)不同：(1)劃分的類(lèi)別不同;(2)類(lèi)別被處理為一個(gè)實(shí)值，與單個(gè)SBFL可疑度值加權(quán)相加。

除程序譜、語(yǔ)句的結(jié)構(gòu)化類(lèi)別外，本文提出的基于排序?qū)W習(xí)的輕量方法，還可以集成語(yǔ)句靜態(tài)屬性、變量譜等特征。

4.1 程序語(yǔ)句的靜態(tài)屬性

一般來(lái)說(shuō)，越復(fù)雜的程序語(yǔ)句(代碼行)，其導(dǎo)致軟件出現(xiàn)故障的概率越大。代碼復(fù)雜度與軟件質(zhì)量屬性緊密聯(lián)系，可分為內(nèi)在復(fù)雜度和外在復(fù)雜度，軟件的內(nèi)在復(fù)雜度容易獲取，外在復(fù)雜度獲取代價(jià)大[23]。軟件工程領(lǐng)域的代碼復(fù)雜度研究成果繁多，常見(jiàn)的有代碼行數(shù)、圈復(fù)雜度、類(lèi)繼承層次、模塊扇入扇出、程序運(yùn)行時(shí)間和可執(zhí)行模塊大小等。目前，還沒(méi)有出現(xiàn)以語(yǔ)句為單位的代碼復(fù)雜性測(cè)度，而本文的目標(biāo)是定位到故障語(yǔ)句，因此設(shè)計(jì)了如表2所示的語(yǔ)句內(nèi)在靜態(tài)屬性來(lái)表征語(yǔ)句復(fù)雜度。

Table 2 Static attributes for statement complexity

文獻(xiàn)[10,15]都使用方法內(nèi)參數(shù)數(shù)目和方法內(nèi)類(lèi)屬性數(shù)目作為特征，前者還統(tǒng)計(jì)了方法內(nèi)的運(yùn)算符個(gè)數(shù)。位于同一方法中的語(yǔ)句并不能被方法級(jí)(或者類(lèi)級(jí))復(fù)雜度區(qū)分開(kāi)來(lái)，因此本文在語(yǔ)句上計(jì)算此類(lèi)代碼復(fù)雜度。一般來(lái)說(shuō)，邏輯運(yùn)算符相比其它運(yùn)算符，給語(yǔ)句帶來(lái)更大的復(fù)雜度，因此本文拆分了運(yùn)算符種類(lèi)。無(wú)論全局變量，還是類(lèi)屬性，影響的程序功能點(diǎn)要多于方法參數(shù)，而方法參數(shù)影響的程序功能點(diǎn)又多于局部變量，將變量分成3種類(lèi)型，更能提高語(yǔ)句復(fù)雜性的辨識(shí)度。至于語(yǔ)句塊內(nèi)定義的局部變量，并不明顯增加代碼的認(rèn)知障礙，故而排除在外。

對(duì)于序號(hào)1～4的特征，同名變量不重復(fù)計(jì)數(shù)；序號(hào)5的邏輯運(yùn)算符限于&&、||和!，序號(hào)6不統(tǒng)計(jì)賦值運(yùn)算符。不屬于方法(函數(shù))的語(yǔ)句，其序號(hào)1和2的特征值皆為0。C程序的語(yǔ)句只有全局變量，沒(méi)有類(lèi)的屬性。長(zhǎng)注釋的相應(yīng)代碼應(yīng)進(jìn)行更多檢查。若語(yǔ)句屬于以下復(fù)合語(yǔ)句：assert、synchronized、do while、while、switch、throw、try catch、if、for，則其嵌套層次加1；其它情形，嵌套層次不變。嵌套層次會(huì)遞歸計(jì)算。

如某個(gè)類(lèi)的方法annotation有如下10行代碼：

1 floatannotation(Configconfig,Typetype,floatr){

2 floatdesc=0,ac=0;/*(2,0,0,0,0,0,0,0,0,0,1)*/

3for(inti=0;i<10;i++){/*(0,0,0,0,0,2,0,1,0,0,0)*/

4desc+=cevf(config,r);/*(1,2,0,1,0,0,1,0,0,0,1)*/

5if((desc>100&&desc<200)‖

6 (desc>r&&ac

7ac=devf(type);/*(1,1,0,1,0,0,2,0,0,0,1)*/

8 }

9returndesc+ac-pfVoc;/*(2,0,1,0,0,2,0,0,0,1,0)*/

10 }

該方法有參數(shù)config、type和r，有頂層局部變量desc和ac(注意，第3行的i是定義在for語(yǔ)句塊的局部變量)，pfVoc為方法所屬類(lèi)的屬性，cevf和devf是方法(函數(shù))名稱(chēng)，則對(duì)應(yīng)行的特征向量可從注釋中觀察到，11維特征向量中前7維屬于語(yǔ)句靜態(tài)屬性(所列未包含注釋字符數(shù))，后4維屬于語(yǔ)句結(jié)構(gòu)化類(lèi)別。例如，第5、6行屬于同一條語(yǔ)句，有2個(gè)頂層局部變量，2種關(guān)系運(yùn)算符(&&和‖)，2種其它運(yùn)算符(<和>)，屬于條件語(yǔ)句，是for語(yǔ)句的從句，所以它的特征向量為：(2,1,0,0,2,2,1,0,1,0,0)。

歸一化處理時(shí)，序號(hào)1～3的特征除以20，而序號(hào)4～7的特征除以10。

就作者所知，用于錯(cuò)誤定位的語(yǔ)句級(jí)輕量特征，除語(yǔ)句類(lèi)別[19]和變量譜[24]外，只有PRINCE的3個(gè)特征[21]：(1)語(yǔ)句的字符數(shù)；(2)運(yùn)算符個(gè)數(shù)；(3)加權(quán)變量數(shù)。這3個(gè)特征同樣屬于語(yǔ)句級(jí)靜態(tài)屬性。在PRINCE中，運(yùn)算符包括10類(lèi)：算術(shù)、邏輯、關(guān)系、位、指針、數(shù)組[]、賦值、復(fù)合賦值、sizeof、函數(shù)調(diào)用()；變量的權(quán)分為3類(lèi)，基本數(shù)據(jù)類(lèi)型的權(quán)為1，數(shù)組類(lèi)型的權(quán)為數(shù)組元素個(gè)數(shù)，struct和class的權(quán)為其所有屬性的權(quán)的累加值。為了與本文方法比較，將上述3個(gè)特征簡(jiǎn)稱(chēng)為PRINCE[21]特征。本文的實(shí)驗(yàn)數(shù)據(jù)有C++程序，許多項(xiàng)目采用新的Java、C++語(yǔ)法規(guī)則，基于這2個(gè)原因，本文采用微調(diào)方式計(jì)算PRINCE特征值。在計(jì)算操作符數(shù)時(shí)，除文獻(xiàn)[21]統(tǒng)計(jì)的10類(lèi)運(yùn)算符外，另加入源代碼解析工具能夠統(tǒng)計(jì)的其它運(yùn)算符。在計(jì)算加權(quán)變量數(shù)時(shí)，3類(lèi)數(shù)據(jù)類(lèi)型的權(quán)統(tǒng)一為1，因?yàn)橹羔槨ap、set、list等數(shù)據(jù)類(lèi)型的元素個(gè)數(shù)獲取代價(jià)非常大。文獻(xiàn)[21]作者也承認(rèn)，他們無(wú)法統(tǒng)計(jì)這些數(shù)據(jù)類(lèi)型的元素個(gè)數(shù)。Java和C++類(lèi)的對(duì)象屬性值自然也難以累加。

4.2 變量譜特征

變量?jī)H限于全局變量、類(lèi)屬性、方法參數(shù)和頂層局部變量。變量譜定義為變量所屬語(yǔ)句程序譜的平均值，表3是一個(gè)簡(jiǎn)單例子。

Table 3 Example of variable spectrum

某個(gè)類(lèi)有方法ma和mb，attr是類(lèi)的屬性。方法ma有3條可執(zhí)行語(yǔ)句(ma1,ma2和ma3)，頂層局部變量為loca，參數(shù)為pa。方法mb有2條可執(zhí)行語(yǔ)句(mb1和mb2)，頂層局部變量為locb。測(cè)試套件有5個(gè)測(cè)試用例，3個(gè)成功，2個(gè)失敗。依定義，變量loca在語(yǔ)句ma1、ma2、ma3出現(xiàn)過(guò)，其譜等于〈(2+3+1)/3,(1+1+2)/3,(1+2)/3,(1+1)/3〉=〈2,1.33,1,0.67〉。同理，locb的譜等于〈2,0.5,1,1.5〉，attr的譜等于〈1.5,1,1.5,1〉,pa只在ma1中出現(xiàn)，其變量譜等于ma1的程序譜〈2,1,1,1〉。

得到變量譜集合后，選擇語(yǔ)句內(nèi)最大可能引入故障的變量譜經(jīng)歸一化處理后當(dāng)作語(yǔ)句的變量譜特征(4維向量)，算法1描述了詳細(xì)步驟。

算法1計(jì)算語(yǔ)句的變量譜特征

輸入：Aep,Aef,Anp,Anf：語(yǔ)句的程序譜四元組；

VARS：語(yǔ)句的變量集合;

FT,PT：測(cè)試套件失敗、成功測(cè)試用例數(shù)。

輸出：變量譜特征。

fori=1 to|VARS|

EFi=Aef[VARSi]/FT;

EPi=Aep[VARSi]/PT;

NPi=Anp[VARSi]/(Anp[VARSi]+Anf[VARSi]);

NFi=Anf[VARSi]/(Anp[VARSi]+Anf[VARSi]);

VARS排序結(jié)果賦值給L，排序依據(jù)為：EF降序優(yōu)先，EP升序次之，NP降序再次之，NF升序最次之;

var←L的首個(gè)元素;

returnEF[var],EP[var],NP[var],NF[var];

經(jīng)算法1處理后，表3中4個(gè)變量依變量譜排序后，L={loca,attr,pa,locb}，var=loca。因此，取loca的譜歸一化向量為語(yǔ)句ma1、ma2和ma3的變量譜特征，取attr的譜歸一化向量為語(yǔ)句mb2的變量譜特征。在計(jì)算語(yǔ)句的靜態(tài)屬性時(shí)，已經(jīng)存儲(chǔ)了各語(yǔ)句的變量信息，加之變量譜可由語(yǔ)句的程序譜轉(zhuǎn)換，無(wú)須額外負(fù)擔(dān)，因此，語(yǔ)句的變量譜特征計(jì)算代價(jià)極小。

Kim等人[24]首先提出了變量譜，將SBFL公式的程序譜用變量譜替換，計(jì)算可疑度后定位軟件錯(cuò)誤。與此不同的是，本文將變量譜作為表征語(yǔ)句的特征。

4.3 排序?qū)W習(xí)軟件錯(cuò)誤定位模型

排序?qū)W習(xí)算法選用LibLinear的線(xiàn)性RankSVM，適合大規(guī)模樣本和特征的數(shù)據(jù)集[25]。令PS為訓(xùn)練集，其元素由同一版本成對(duì)的故障語(yǔ)句與非故障語(yǔ)句構(gòu)成(xi和xj)。RankSVM的優(yōu)化目標(biāo)[25]如式(3)所示：

(3)

其中,w是樣本(語(yǔ)句)的權(quán)向量，也就是RankSVM學(xué)習(xí)到的錯(cuò)誤定位模型，C是模型的平衡因子。非故障語(yǔ)句判為錯(cuò)誤語(yǔ)句，或者錯(cuò)誤語(yǔ)句判為非故障語(yǔ)句，模型盡力減小這些誤判引起的誤差實(shí)數(shù)值，另外模型還必須保持泛化性，兩者的平衡由C來(lái)調(diào)節(jié)。令某條語(yǔ)句的特征向量為x，則該語(yǔ)句的可疑度值等于w*x，*為內(nèi)積運(yùn)算。語(yǔ)句的w*x值越大，表示其包含故障的可能性更大。特征集除程序譜外，另包含語(yǔ)句靜態(tài)屬性，則x的維數(shù)等于23+8；另包含語(yǔ)句類(lèi)別，則x的維數(shù)等于23+4；另包含變量譜，則x的維數(shù)為23+4。

為驗(yàn)證本文方法的有效性，采用跨項(xiàng)目的方式構(gòu)造錯(cuò)誤定位模型。將項(xiàng)目按比例劃分為訓(xùn)練集、驗(yàn)證集和測(cè)試集，同一項(xiàng)目的所有版本同時(shí)分配到某個(gè)子集。不同項(xiàng)目的可執(zhí)行語(yǔ)句數(shù)大不相同，構(gòu)造訓(xùn)練集時(shí)，從所有版本中統(tǒng)一取β條語(yǔ)句。構(gòu)造驗(yàn)證集和測(cè)試集時(shí)，收集的所有可執(zhí)行語(yǔ)句都被納入。

RankSVM的優(yōu)化目標(biāo)無(wú)法最小化錯(cuò)誤定位評(píng)價(jià)指標(biāo)，利用排序模型的平衡因子C和驗(yàn)證集來(lái)調(diào)整錯(cuò)誤定位性能誤差。算法2描述了搜索最優(yōu)錯(cuò)誤定位模型的過(guò)程。

算法2搜索最優(yōu)錯(cuò)誤定位模型

輸入：錯(cuò)誤定位評(píng)價(jià)指標(biāo)EXCHK；項(xiàng)目集合PRJS；項(xiàng)目版本納入訓(xùn)練集的語(yǔ)句條數(shù)β；平衡因子C；平衡因子搜索次數(shù)γ。

輸出：最優(yōu)錯(cuò)誤定位模型BestW。

將PRJS按比例隨機(jī)劃分訓(xùn)練集、驗(yàn)證集和測(cè)試集;

TRAIN←從訓(xùn)練集每個(gè)版本中抽取β條可執(zhí)行語(yǔ)句;

VALID←從驗(yàn)證集抽取所有可執(zhí)行語(yǔ)句;

TEST←從測(cè)試集抽取所有可執(zhí)行語(yǔ)句;

EXCHKmin=1;//1是最大值

BestW=0,C=1;

forj=1 toγ

W←learn model inTRAIN;

EXCHKnow←compute byWonVALID;

ifEXCHKnow

EXCHKmin=EXCHKnow;

BestW=W;

C=C/2;

returnBestW;

/*基于BestW計(jì)算當(dāng)前測(cè)試集的性能*/

5 實(shí)驗(yàn)結(jié)果及分析

所有實(shí)驗(yàn)在一臺(tái)配置為Intel Core i7-8700 3.2 GHz CPU和16 GB 物理內(nèi)存的計(jì)算機(jī)上完成，操作系統(tǒng)是Windows 10。

無(wú)論是包含單個(gè)故障的版本，還是多故障的版本，本文都采用EXAM來(lái)度量其錯(cuò)誤定位性能，其定義如式(4)所示：

EXAM=

(4)

當(dāng)有多條語(yǔ)句可疑度值相等時(shí)，最理想的情況下，檢查其中一條語(yǔ)句就定位到故障，稱(chēng)為最優(yōu)策略；最壞的情況下，所有語(yǔ)句都檢查完后才找到故障，此時(shí)性能記為EXAMworst；平均策略的性能EXAMavg為最優(yōu)策略和最壞策略的平均值。

實(shí)驗(yàn)參數(shù)的設(shè)置，采用以下策略：針對(duì)算法2，參數(shù)β=100，γ=30;線(xiàn)性RankSVM的參數(shù)全部取默認(rèn)值。實(shí)驗(yàn)共有22個(gè)項(xiàng)目，按5∶3∶3的比例隨機(jī)劃分為訓(xùn)練集、驗(yàn)證集和測(cè)試集，任意項(xiàng)目的所有版本只能處于同一子集內(nèi)。參數(shù)β過(guò)小，模型適應(yīng)性差，β過(guò)大，模型將擬合規(guī)模大的項(xiàng)目，絕大多數(shù)版本至少有100條可執(zhí)行語(yǔ)句，故而設(shè)β=100。訓(xùn)練集選取可執(zhí)行語(yǔ)句時(shí)，先取所有故障語(yǔ)句，再取故障語(yǔ)句的近鄰，不足的部分，隨機(jī)從其它類(lèi)(C++、Java)或者函數(shù)(C程序)中選取。參數(shù)γ的取值可參考文獻(xiàn)[25]。為減小訓(xùn)練集、驗(yàn)證集和測(cè)試集劃分的隨機(jī)性影響，算法2重復(fù)執(zhí)行500次，后文實(shí)驗(yàn)數(shù)據(jù)是500次結(jié)果的平均值。

5.1 實(shí)驗(yàn)數(shù)據(jù)集及語(yǔ)句特征計(jì)算

實(shí)驗(yàn)數(shù)據(jù)集來(lái)自于SIR、Pairika OpenCV、Defects4j和Bears。SIR軟件項(xiàng)目基礎(chǔ)資源庫(kù)是軟件錯(cuò)誤定位領(lǐng)域知名的基準(zhǔn)測(cè)試集[26]，實(shí)驗(yàn)收集了實(shí)際故障的C語(yǔ)言項(xiàng)目space，有29個(gè)錯(cuò)誤版本。OpenCV是一個(gè)輕量、高效、跨平臺(tái)的計(jì)算機(jī)視覺(jué)和機(jī)器學(xué)習(xí)軟件庫(kù)。Pairika從OpenCV的7個(gè)模塊中提取而得[27]，它超過(guò)49×104行代碼和11 129個(gè)測(cè)試用例，被構(gòu)造為C++程序的故障診斷基準(zhǔn)數(shù)據(jù)集。實(shí)驗(yàn)收集了OpenCV 331和OpenCV 340，共19個(gè)錯(cuò)誤版本，所有錯(cuò)誤皆為實(shí)際故障。Defects4j是軟件測(cè)試領(lǐng)域廣泛采用的基準(zhǔn)數(shù)據(jù)集[28]，其網(wǎng)站當(dāng)前為2.0版本，實(shí)驗(yàn)收集了16個(gè)Java項(xiàng)目：Chart、Cli、Closure、Codec、Collections、Compress、JacksonCore、Gson、Csv、Databind、JacksonXml、Jsoup、JxPath、Lang、Math和Time，這些項(xiàng)目共有641個(gè)錯(cuò)誤版本，所有錯(cuò)誤皆為實(shí)際故障。通過(guò)持續(xù)集成的手段識(shí)別故障版本和修正版本，Bears[29]為自動(dòng)化修復(fù)程序社區(qū)建立的一個(gè)基準(zhǔn)數(shù)據(jù)集。實(shí)驗(yàn)收集了3個(gè)Java項(xiàng)目：FasterXML、traccar和AutoCar，共有64個(gè)錯(cuò)誤版本，所有故障語(yǔ)句皆來(lái)源于實(shí)際編程。

在VirtualBox v6.1和Ubuntu 18.04環(huán)境下，執(zhí)行SIR、Defects4j和Bears的測(cè)試用例，獲得語(yǔ)句的程序譜。使用Gcov采集SIR的C程序的代碼行覆蓋數(shù)據(jù)。使用Cobertura采集Defects4j和Bears的Java程序的代碼行覆蓋數(shù)據(jù)。Pairika的測(cè)試用例執(zhí)行結(jié)果在Windows 10環(huán)境下獲取，使用開(kāi)源軟件OpenCppCoverage采集代碼行覆蓋數(shù)據(jù)。

有少部分代碼中多條可執(zhí)行語(yǔ)句排在一行，此時(shí)取可疑度最大值作為整行代碼的可疑度值。很多故障代碼屬于缺失型，修正版里添加了正確語(yǔ)句，此時(shí)無(wú)法獲取這些缺失語(yǔ)句的程序譜，本文實(shí)驗(yàn)采用以下簡(jiǎn)單做法：如果缺失語(yǔ)句后有代碼，則以其后一行指代故障；否則，以缺失語(yǔ)句前一行代碼指代故障。

Pairika、Defects4j和Bears的類(lèi)非常多，為減少收集程序譜的時(shí)間，每個(gè)版本只記錄最多30個(gè)文件的代碼行覆蓋數(shù)據(jù)。具體策略包括2個(gè)步驟：首先執(zhí)行一遍所有測(cè)試用例，統(tǒng)計(jì)每個(gè)文件的被覆蓋行數(shù)目；后續(xù)選擇文件時(shí)，先加入帶故障的文件，不足部分，優(yōu)先挑選被覆蓋行數(shù)最多的文件。

在語(yǔ)句特征的采集與計(jì)算過(guò)程中，本文使用Eclipse的抽象語(yǔ)法樹(shù)Parser解析源代碼。在解析C程序和C++程序時(shí)，調(diào)用了CDT組件，解析Java程序時(shí)則調(diào)用了JDT組件。

5.2 本文方法與傳統(tǒng)SBFL方法及基于SBFL的搜索方法對(duì)比

為驗(yàn)證語(yǔ)句靜態(tài)屬性對(duì)錯(cuò)誤定位模型的影響，定義特征集僅限23個(gè)SBFL公式的方法為Ranksbfl，集成程序譜和表2代碼行靜態(tài)屬性的方法為Rankscpx+。表4對(duì)比了各故障定位方法在753個(gè)版本上的平均性能，最小值加粗表示。

對(duì)排序?qū)W習(xí)算法來(lái)說(shuō)，EXAMworst以最壞策略為算法優(yōu)化目標(biāo)計(jì)算而得，EXAMavg以平均策略為算法優(yōu)化目標(biāo)計(jì)算而得。Ranksbfl和Rankscpx+的EXAM值如此，如非特別說(shuō)明，后文其它排序?qū)W習(xí)算法的EXAM值亦如此。

以往小數(shù)據(jù)集或者人工注入故障數(shù)據(jù)集的部分研究成果并不受支持。如NaishO表現(xiàn)并不好，Wong2和Wong3更是糟糕?？傮w來(lái)看，比較23個(gè)傳統(tǒng)SBFL方法，Dice、Jaccard、Anderberg、Goodman和Ochiai表現(xiàn)優(yōu)異，Kulczynski1、Tarantula、Kulczynski2、Zoltar和DStar2也很不錯(cuò)。從表4可看出，相比表現(xiàn)最好的SBFL，Ranksbfl都有足夠的競(jìng)爭(zhēng)力。特征集加入語(yǔ)句靜態(tài)屬性后，Rankscpx+性能顯著提高,EXAMavg減少了37.1%(SBFL的Ochiai最優(yōu))，EXAMworst減少了22.6%(Ochiai最優(yōu))。

Table 4 Comparison of EXAM among sereval fault localization methods

表5列出了Rankscpx+與項(xiàng)目表現(xiàn)最佳的SBFL的性能比較。最佳SBFL列，未帶加號(hào)表明多個(gè)SBFL同時(shí)取得最佳效果，帶加號(hào)則只有一個(gè)SBFL取得最優(yōu)性能，加號(hào)后是該SBFL的名稱(chēng)。

針對(duì)單個(gè)項(xiàng)目比較EXAMworst，除項(xiàng)目space、FastXML和Collections外，Rankscpx+都要比最優(yōu)SBFL性能高；而以EXAMavg為評(píng)估標(biāo)準(zhǔn)，則Rankscpx+也在13個(gè)項(xiàng)目上勝出。不同編程語(yǔ)言的語(yǔ)句，特征計(jì)算方式有差別。數(shù)據(jù)集只有一個(gè)C項(xiàng)目space，它拉低了Rankscpx+的性能。

這些項(xiàng)目的編程語(yǔ)言、測(cè)試用例數(shù)目、可執(zhí)行語(yǔ)句規(guī)模和故障類(lèi)型等都大相徑庭，在驗(yàn)證集上獲得最優(yōu)的模型，在測(cè)試集上的性能并非最佳。表6的結(jié)果顯示，分別以最壞策略和平均策略為優(yōu)化目標(biāo)，Ranksbfl的性能差別不大,Rankscpx+的性能更是接近。這也提示我們，增加合適的特征，從更多角度表征語(yǔ)句，錯(cuò)誤定位模型的性能還會(huì)提升。

5.3 結(jié)構(gòu)化類(lèi)別、變量譜和語(yǔ)句靜態(tài)屬性對(duì)比

相比于傳統(tǒng)SBFL方法，以及基于SBFL的搜索方法Ranksbfl，Rankscpx+的性能提升明顯。將Rankscpx+的特征子集由語(yǔ)句靜態(tài)屬性替換為語(yǔ)句

Table 5 Performance comparison on a single project

Table 6 Comparison of fault localization methods by two strategies

結(jié)構(gòu)化類(lèi)別(簡(jiǎn)稱(chēng)語(yǔ)句類(lèi)別)、變量譜后，或者將語(yǔ)句類(lèi)別和變量譜加入到Rankscpx+的特征集，表7展示了這些算法的性能。另外,RankPRINCE指集成23個(gè)SBFL公式和3個(gè)PRINCE特征的方法。

語(yǔ)句的3類(lèi)輕量特征對(duì)錯(cuò)誤定位模型性能都有幫助，語(yǔ)句靜態(tài)屬性表現(xiàn)最優(yōu)，語(yǔ)句類(lèi)別次之，變量譜再次之。從表7可觀察到，變量譜的作用并不突出，集成SBFL和變量譜后，Rank+svs的EXAMavg值甚至比Ranksbfl的還差。3類(lèi)輕量特征對(duì)

Table 7 Effect of three kinds of features on fault localization methods performance

語(yǔ)句內(nèi)在復(fù)雜度的貢獻(xiàn)作用存在負(fù)相關(guān)因素，導(dǎo)致特征集加上語(yǔ)句類(lèi)別、變量譜后，Rankscpx+性能反而下降。即便集成SBFL、語(yǔ)句復(fù)雜度、語(yǔ)句類(lèi)別和變量譜，Rank+ctv的性能還不如Rankscpx+的?；蛟S這些特征拆得更細(xì)，能降低這種不利影響。相比RankPRINCE，Rankscpx+的特征集更豐富，性能也提高不少。

6 時(shí)間復(fù)雜度

語(yǔ)句的特征獲取時(shí)間復(fù)雜度低。表8是幾個(gè)具規(guī)模代表性項(xiàng)目的時(shí)間開(kāi)銷(xiāo)，項(xiàng)目時(shí)間是其所有版本的平均值，單位為ms。在對(duì)應(yīng)時(shí)間內(nèi)，完成3項(xiàng)任務(wù)：解析源代碼、計(jì)算語(yǔ)句特征向量和存儲(chǔ)特征到文件。即使是OpenCV331這樣規(guī)模的程序，獲取特征的時(shí)間也不到1 s。

Table 8 Time overhead of feature acquisition

排序?qū)W習(xí)最優(yōu)模型的求解時(shí)間開(kāi)銷(xiāo)也不大，表9是3個(gè)算法以EXAMworst為優(yōu)化目標(biāo)的錯(cuò)誤定位模型搜索時(shí)間，單位為s。對(duì)應(yīng)時(shí)間內(nèi)，完成3項(xiàng)任務(wù)：讀入特征集、劃分訓(xùn)練集/驗(yàn)證集/測(cè)試集和求解最優(yōu)錯(cuò)誤定位模型。算法的時(shí)間為500次求解過(guò)程的平均值。

最優(yōu)錯(cuò)誤定位模型的訓(xùn)練在調(diào)試活動(dòng)前完成。語(yǔ)句可疑度值的計(jì)算開(kāi)銷(xiāo)僅限于特征獲取和模型特征與權(quán)向量線(xiàn)性?xún)?nèi)積運(yùn)算，后者時(shí)間可忽略不計(jì)。因此，本文方法夠輕量，能夠?qū)崟r(shí)地推薦可能出故障的語(yǔ)句序列。

Table 9 Time cost of solving the optimal model

7 結(jié)束語(yǔ)

數(shù)據(jù)集由22個(gè)項(xiàng)目組成，代碼用3種流行的編程語(yǔ)言開(kāi)發(fā)，各項(xiàng)目的故障并非人工注入，而是在實(shí)際開(kāi)發(fā)項(xiàng)目時(shí)產(chǎn)生的，錯(cuò)誤定位模型由跨項(xiàng)目形式訓(xùn)練而得?；诔绦蜃V的搜索方法能幫助開(kāi)發(fā)人員、自動(dòng)修復(fù)軟件并定位到故障語(yǔ)句，然而，源代碼固有的故障相關(guān)信息被忽略，如何挖掘語(yǔ)句靜態(tài)屬性，研究提升錯(cuò)誤定位性能的算法很有意義。本文設(shè)計(jì)了語(yǔ)句級(jí)代碼復(fù)雜度的特征集。實(shí)驗(yàn)結(jié)果表明，集成程序譜和語(yǔ)句的這些靜態(tài)屬性后，通過(guò)排序?qū)W習(xí)算法獲得的錯(cuò)誤定位模型，能顯著減少待排查的語(yǔ)句數(shù)目。語(yǔ)句其它2類(lèi)輕量特征：結(jié)構(gòu)化類(lèi)別和變量譜，有助于改善SBFL搜索方法的性能，但比語(yǔ)句靜態(tài)屬性遜色不少，與其組合后，顯現(xiàn)負(fù)面作用。實(shí)驗(yàn)還發(fā)現(xiàn)，一些在小數(shù)據(jù)集或者人工注入故障數(shù)據(jù)集上的結(jié)論并不成立。

實(shí)驗(yàn)數(shù)據(jù)集的項(xiàng)目大小不一，編程語(yǔ)言各異，故障類(lèi)型多樣，這些因素都制約了錯(cuò)誤定位方法性能。擴(kuò)充數(shù)據(jù)集，增加表達(dá)語(yǔ)句復(fù)雜性的靜態(tài)屬性，都是后續(xù)研究工作的重要內(nèi)容。