黃晴雁,牟永敏,崔展齊,張志華
1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院,北京100101
2.北京信息科技大學(xué) 網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室,北京100101
軟件調(diào)試在軟件開發(fā)中扮演了極其重要的角色,而快速準(zhǔn)確地找到程序中的錯(cuò)誤是軟件調(diào)試的關(guān)鍵[1]。手工調(diào)試方法耗時(shí)耗力且效率低下,為了能夠高效準(zhǔn)確地定位軟件錯(cuò)誤的位置,研究人員提出了很多行之有效的自動(dòng)化軟件錯(cuò)誤定位方法。自動(dòng)化軟件錯(cuò)誤定位方法分為靜態(tài)分析和動(dòng)態(tài)分析兩類。靜態(tài)分析方法[2-3]不需運(yùn)行程序,通過(guò)分析程序的源代碼和結(jié)構(gòu)等信息定位到具體的錯(cuò)誤源;動(dòng)態(tài)分析方法[4]通過(guò)運(yùn)行程序分析測(cè)試用例的執(zhí)行軌跡以及運(yùn)行結(jié)果來(lái)輔助定位錯(cuò)誤位置。
動(dòng)態(tài)分析是自動(dòng)化軟件錯(cuò)誤定位研究的重點(diǎn),大致可以分為基于程序頻譜、基于依賴關(guān)系、基于數(shù)據(jù)挖掘以及基于程序切片的錯(cuò)誤定位等方法[3-6]。其中,基于程序頻譜的錯(cuò)誤定位是目前主流的研究思路[7],通過(guò)執(zhí)行大量測(cè)試用例得到程序?qū)嶓w覆蓋信息和執(zhí)行結(jié)果,使用統(tǒng)計(jì)學(xué)方法計(jì)算實(shí)體的可疑值,對(duì)具有單一錯(cuò)誤的程序表現(xiàn)出良好的定位效果。Jones 等[8]提出了Tarantula 可疑度計(jì)算公式,認(rèn)為被更多的失敗測(cè)試用例執(zhí)行到的實(shí)體,其含有錯(cuò)誤的可能性要高于其他實(shí)體。隨后,Abreu等[4]根據(jù)聚類分析提出了Jaccard 公式,受分子生物學(xué)啟發(fā)提出了Ochiai可疑度計(jì)算公式,提高了錯(cuò)誤定位的效果。Wong等[9]在Kulczynski系數(shù)的基礎(chǔ)上提出了DStar方法,實(shí)證研究中發(fā)現(xiàn)該方法的定位效果要優(yōu)于其他方法。
近年來(lái),基于搜索的軟件工程(Search Based Software Engineering,SBSE)逐漸被應(yīng)用于軟件錯(cuò)誤定位和錯(cuò)誤自動(dòng)修復(fù)領(lǐng)域[10-12]。SBSE 將傳統(tǒng)軟件工程問(wèn)題建模為組合優(yōu)化問(wèn)題,利用元啟發(fā)式搜索技術(shù)搜索求解?;诖?,張蓓等[13]提出了一種基于增強(qiáng)遺傳BP神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法,在效率和精確度上均有進(jìn)步。王贊等[14]提出了一種基于遺傳算法的多缺陷定位方法,對(duì)多缺陷定位問(wèn)題進(jìn)行建模,有效減少了人工交互。
目前,大多數(shù)的錯(cuò)誤定位方法針對(duì)語(yǔ)句級(jí)別,很少基于函數(shù)粒度進(jìn)行研究。語(yǔ)句級(jí)別的定位是一種細(xì)粒度的定位方法,可以將錯(cuò)誤定位到某一條語(yǔ)句。然而在實(shí)際軟件開發(fā)過(guò)程中,軟件錯(cuò)誤的發(fā)生大多是由于某個(gè)函數(shù)內(nèi)部的邏輯或語(yǔ)句順序出現(xiàn)錯(cuò)誤造成的。在粗粒度的函數(shù)級(jí)別上進(jìn)行錯(cuò)誤檢測(cè)定位比細(xì)粒度的語(yǔ)句級(jí)別更為合理有效。同時(shí),在程序較為復(fù)雜,并且存在多個(gè)錯(cuò)誤位置時(shí),基于搜索的軟件工程能夠提供良好的定位結(jié)果。而遺傳算法作為主流的搜索算法,具有很強(qiáng)的通用性、魯棒性和全局搜索能力。因此,本文提出一種基于遺傳算法的函數(shù)級(jí)別軟件錯(cuò)誤定位框架FGAFL,通過(guò)執(zhí)行測(cè)試用例得到函數(shù)級(jí)別的程序頻譜,借助基于搜索的軟件工程思想進(jìn)行建模,結(jié)合函數(shù)間的調(diào)用信息,利用遺傳算法搜索求解。
基于程序頻譜的錯(cuò)誤定位就是根據(jù)程序運(yùn)行的頻譜信息來(lái)統(tǒng)計(jì)程序中各個(gè)實(shí)體的可疑值并進(jìn)行排序,越可疑的實(shí)體含有錯(cuò)誤的可能性越大[15]。接下來(lái)對(duì)相關(guān)概念依次給出定義,并在之后的內(nèi)容中采用本節(jié)定義的符號(hào)概念。
定義1 測(cè)試用例集:T={t1,t2,…,tm}表示待測(cè)程序的m 個(gè)測(cè)試用例集合。其中ti表示第i 個(gè)測(cè)試用例。根據(jù)運(yùn)行結(jié)果將T 分為失敗測(cè)試用例集TF和成功測(cè)試用例集TP。
定義2 待測(cè)程序?qū)嶓w集:E={e1,e2,…,en}表示待測(cè)程序中包含n 個(gè)函數(shù)。其中ei表示程序中第i 個(gè)函數(shù)。
定義3 覆蓋矩陣:M=(Mij)表示測(cè)試用例集T 和程序?qū)嶓w集E 之間的覆蓋關(guān)系。 M 是一個(gè)由0和1構(gòu)成的m×n 階矩陣。當(dāng)Mij=1 時(shí),表示測(cè)試用例i 覆蓋了函數(shù)j,當(dāng)Mij=0 時(shí),表示測(cè)試用例i 未覆蓋函數(shù)j。MF=(Mij)是失敗測(cè)試用例覆蓋矩陣,包含失敗測(cè)試用例集TF的覆蓋信息;MP=(Mij)是成功測(cè)試用例覆蓋矩陣,包含成功測(cè)試用例集TP的覆蓋信息。
定義4 測(cè)試用例結(jié)果向量:R={r1,r2,…,rm}表示測(cè)試用例集中m 個(gè)測(cè)試用例的測(cè)試結(jié)果。其中ri表示第i 個(gè)測(cè)試用例的執(zhí)行結(jié)果,ri的取值為0或1,當(dāng)ri=1時(shí),表示第i 個(gè)測(cè)試用例執(zhí)行失敗,當(dāng)ri=0 時(shí),表示第i個(gè)測(cè)試用例執(zhí)行成功。
在錯(cuò)誤定位分析的過(guò)程中,文獻(xiàn)[16]提出了軟件錯(cuò)誤關(guān)聯(lián)的思想,即失效相關(guān)性。在此基礎(chǔ)上,本文認(rèn)為各個(gè)函數(shù)之間具有直接或間接的關(guān)聯(lián)關(guān)系,一個(gè)有錯(cuò)誤的函數(shù)往往會(huì)影響到與之關(guān)聯(lián)的函數(shù),對(duì)找到真正的錯(cuò)誤根源會(huì)造成一定的干擾。為了解決這一問(wèn)題,本文在函數(shù)調(diào)用路徑(Function Call Path,F(xiàn)CP)的基礎(chǔ)上進(jìn)行錯(cuò)誤定位,在一定程度上減少函數(shù)間的關(guān)聯(lián)對(duì)錯(cuò)誤定位造成的干擾。
以函數(shù)為基本單位,把程序的一次執(zhí)行軌跡描述為一條函數(shù)調(diào)用路徑,實(shí)際上是程序中基于函數(shù)調(diào)用并且結(jié)合數(shù)據(jù)流、控制流的一種函數(shù)執(zhí)行路徑的靜態(tài)描述集合[17]。下面給出函數(shù)調(diào)用路徑的相關(guān)定義。
定義5 函數(shù)調(diào)用路徑:W 是基于函數(shù)調(diào)用的一條完整的程序執(zhí)行路徑,表示為Wi={vi0,vi1,…,vim},路徑中的相鄰節(jié)點(diǎn)表示函數(shù)之間的調(diào)用或順序執(zhí)行關(guān)系。
整個(gè)程序的函數(shù)調(diào)用路徑的合集組成函數(shù)調(diào)用路徑圖,與函數(shù)調(diào)用圖不同的是函數(shù)調(diào)用路徑圖展示了函數(shù)之間的調(diào)用與順序執(zhí)行的關(guān)系,而函數(shù)調(diào)用圖僅分析了函數(shù)之間的調(diào)用關(guān)系,忽略了控制流、數(shù)據(jù)流等信息。函數(shù)調(diào)用圖與函數(shù)調(diào)用路徑圖的對(duì)比如圖1所示。
圖1中的源程序包括四個(gè)函數(shù):main、f1、f2、f3。其中main函數(shù)調(diào)用了f1、f2、f3三個(gè)函數(shù)。圖(a)中函數(shù)調(diào)用圖沒有考慮調(diào)用這些函數(shù)時(shí)的控制流信息,不能正確反映函數(shù)可能的執(zhí)行路徑,而圖(b)中函數(shù)調(diào)用圖可以更為準(zhǔn)確地反映出該程序中存在的函數(shù)執(zhí)行路徑,路徑1(main →f1→f2→end)和路徑2(main →f1→f3→end)。
遺傳算法(Genetic Algorithm,GA)是一類仿生型優(yōu)化算法,由Holland[18]于20 世紀(jì)70 年代提出。該算法模擬生物界“優(yōu)勝劣汰”的進(jìn)化過(guò)程,是目前主流的啟發(fā)式搜索算法之一?;谶z傳算法的技術(shù)已經(jīng)被用于解決函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域的問(wèn)題。
圖1 函數(shù)調(diào)用圖與函數(shù)調(diào)用路徑圖對(duì)比
遺傳算法的核心部分包括:(1)確定種群染色體編碼;(2)生成初始種群;(3)構(gòu)建適應(yīng)度函數(shù)以及評(píng)估個(gè)體適應(yīng)度;(4)利用遺傳操作算子實(shí)現(xiàn)進(jìn)化。其中,常用的編碼方法有二進(jìn)制編碼、實(shí)數(shù)編碼和符號(hào)編碼等,遺傳操作算子包括選擇算子(select operator)、交叉算子(crossover operator)以及變異算子(mutation operator)[19-20]。
在預(yù)處理階段,遺傳算法根據(jù)實(shí)際問(wèn)題的參數(shù)進(jìn)行編碼,組成染色體;其次,初始化一定規(guī)模的種群,由多個(gè)個(gè)體組成;然后,算法通過(guò)適應(yīng)度函數(shù)衡量每個(gè)個(gè)體的優(yōu)劣,采取選擇、交叉、變異等遺傳操作算子對(duì)種群進(jìn)行演化搜索,直到滿足終止條件;最后,輸出得到的最優(yōu)解。遺傳算法的執(zhí)行過(guò)程如圖2所示。
圖2 遺傳算法執(zhí)行過(guò)程
本文針對(duì)多錯(cuò)誤定位問(wèn)題提出FGAFL 框架,將軟件錯(cuò)誤定位的研究粒度提升到函數(shù)級(jí)別,同時(shí)提出新的適應(yīng)度函數(shù),將基于函數(shù)調(diào)用路徑得到的函數(shù)之間的關(guān)聯(lián)度作為適應(yīng)度函數(shù)的懲罰因子。FGAFL框架的主要研究?jī)?nèi)容包括三部分:一是對(duì)待測(cè)程序以及測(cè)試用例進(jìn)行預(yù)處理;二是利用遺傳算法搜索尋找最優(yōu)候選種群;三是根據(jù)得到的最優(yōu)解確定有錯(cuò)誤的函數(shù)。
在預(yù)處理階段,運(yùn)行測(cè)試用例得到每個(gè)測(cè)試用例對(duì)函數(shù)的覆蓋信息和運(yùn)行結(jié)果,構(gòu)建覆蓋矩陣和結(jié)果向量,同時(shí)分析靜態(tài)待測(cè)程序的函數(shù)調(diào)用路徑,量化函數(shù)之間的關(guān)聯(lián)關(guān)系;在遺傳算法搜索階段,采用二進(jìn)制編碼方式對(duì)問(wèn)題進(jìn)行參數(shù)編碼,構(gòu)建初始種群,使用選擇、交叉和變異三種算子對(duì)種群進(jìn)行操作,不斷進(jìn)行迭代演化,直到終止條件被滿足,得到最優(yōu)候選種群;在錯(cuò)誤定位階段,統(tǒng)計(jì)并分析得到的最優(yōu)候選種群,對(duì)應(yīng)到程序中具體的函數(shù),得到最終的函數(shù)可疑度排序。
圖3為FGAFL框架的整體流程。
圖3 整體流程圖
3.2.1 染色體編碼方式
本文采用二進(jìn)制編碼方式,將個(gè)體C 表示為一個(gè)二進(jìn)制向量C={c1,c2,…,cn}。其中n 為被測(cè)程序中可執(zhí)行函數(shù)的個(gè)數(shù),ci表示第i 個(gè)函數(shù)是否存在錯(cuò)誤。若ci=0,則該被測(cè)程序中第i 個(gè)函數(shù)被認(rèn)為不存在錯(cuò)誤;若ci=1,則該被測(cè)程序中第i 個(gè)函數(shù)被認(rèn)為存在錯(cuò)誤。
例如,有個(gè)體C={0,1,0,0,0,0,1,0,0,0},表示被測(cè)程序中有10個(gè)可執(zhí)行函數(shù),其中第2個(gè)函數(shù)和第7個(gè)函數(shù)被認(rèn)為存在錯(cuò)誤,其余函數(shù)不存在錯(cuò)誤。
3.2.2 函數(shù)關(guān)聯(lián)度計(jì)算
計(jì)算函數(shù)之間的關(guān)聯(lián)度有以下兩個(gè)步驟:首先,分析程序中的數(shù)據(jù)流和控制流的邏輯關(guān)系,得到函數(shù)調(diào)用路徑圖;其次,結(jié)合函數(shù)調(diào)用路徑圖和覆蓋矩陣、結(jié)果向量,分析并量化各函數(shù)間的關(guān)聯(lián)關(guān)系。
本文選擇Gini 指數(shù)作為量化函數(shù)調(diào)用序列中目標(biāo)函數(shù)與運(yùn)行結(jié)果之間聯(lián)系的指標(biāo)。一般來(lái)說(shuō),Gini指數(shù)用于衡量數(shù)據(jù)的不純度或者不確定性,Gini 指數(shù)越大,表示數(shù)據(jù)集的純度越小。舉例說(shuō)明(f1調(diào)用函數(shù)f2、f3),如表1所示。
表1 函數(shù)調(diào)用的關(guān)聯(lián)關(guān)系示例
表1中,第二行第二列表示覆蓋該調(diào)用序列f1→f2的失敗測(cè)試用例的個(gè)數(shù)為5,第三行第二列表示覆蓋該序列的成功測(cè)試用例的個(gè)數(shù)為35。計(jì)算Gini指數(shù)如下:
定義函數(shù)f1基于函數(shù)調(diào)用的關(guān)聯(lián)關(guān)系量化后的特征值為relation(f1),可以得到:
3.2.3 適應(yīng)度函數(shù)
在基于程序頻譜的軟件錯(cuò)誤定位中,Tarantula、Ochiai以及DStar等可疑度公式主要針對(duì)程序中含有一個(gè)錯(cuò)誤的情況。文獻(xiàn)[21]在Ochiai 公式的基礎(chǔ)上,提出了Multi-Ochiai公式作為遺傳算法中的適應(yīng)度函數(shù)。本文在此基礎(chǔ)上提出FMD*可疑度公式,表示為:
φ(C)是個(gè)體C 解釋失敗測(cè)試用例的能力,即若一個(gè)失敗測(cè)試用例經(jīng)過(guò)了個(gè)體C 中被認(rèn)為有錯(cuò)的函數(shù),則說(shuō)該個(gè)體可以解釋這一失敗測(cè)試用例。個(gè)體C 能解釋的失敗測(cè)試用例越多,則該個(gè)體越可疑。φ(C)可以表示為[14]:
在該公式中,函數(shù)λ(x)為示性函數(shù):
類似于φ(C),P(C)表示的是個(gè)體C 解釋成功測(cè)試用例的能力。若某個(gè)函數(shù)被越多的成功測(cè)試用例運(yùn)行覆蓋,則該函數(shù)有錯(cuò)的可能性越小,即個(gè)體C 的可疑度與該個(gè)體能解釋的成功測(cè)試用例的數(shù)量成反比。P(C)可以表示為:
Q(C)表示個(gè)體C 中被認(rèn)為有錯(cuò)的函數(shù)未被失敗測(cè)試用例覆蓋的情況。如果一個(gè)函數(shù)沒有被失敗測(cè)試用例運(yùn)行覆蓋,那么該函數(shù)有錯(cuò)的可能性較低。Q(C)表示為:
其中,μ(x)為另一個(gè)示性函數(shù):
該函數(shù)的含義為個(gè)體C 中被認(rèn)為有錯(cuò)的個(gè)體只要未被所有的失敗測(cè)試用例運(yùn)行覆蓋,就將μ(x)的值置為1。
影響因子R(C)表示了函數(shù)之間的調(diào)用關(guān)系,即為上一節(jié)中得到的對(duì)函數(shù)調(diào)用之間的關(guān)聯(lián)關(guān)系的量化。R(C)表示為:
該公式表示對(duì)個(gè)體C 中被認(rèn)為有錯(cuò)的函數(shù)計(jì)算函數(shù)調(diào)用關(guān)聯(lián)關(guān)系的特征值,并求和。
3.3.1 初始化種群
高質(zhì)量和多樣性的初始種群能夠提高遺傳算法的收斂速度以及最終結(jié)果的質(zhì)量,本文結(jié)合貪心算法Additional-Greedy(AG)[22]生成初始種群。生成初始種群P 的算法流程如下所示。
該方法的輸入包括失敗測(cè)試用例覆蓋矩陣MF以及種群的規(guī)模NP。對(duì)于有n 個(gè)函數(shù)的程序首先生成n個(gè)個(gè)體,同時(shí)每個(gè)個(gè)體只有一個(gè)函數(shù)被認(rèn)為有錯(cuò),且被認(rèn)為有錯(cuò)的函數(shù)位置不相同(即生成n 階單位矩陣),如圖4所示:
圖4 生成n 個(gè)個(gè)體
利用失敗測(cè)試用例覆蓋矩陣MF以及圖4 中生成的n 個(gè)個(gè)體,計(jì)算每個(gè)個(gè)體C 解釋失敗測(cè)試用例的能力。如果φ(C)=| TF|,說(shuō)明個(gè)體C 可以解釋所有的失敗測(cè)試用例。如果φ(C)<| TF|,則需要對(duì)個(gè)體C 表示的函數(shù)錯(cuò)誤分布情況進(jìn)行修正。利用AG 算法修改個(gè)體C的錯(cuò)誤分布情況,將C 中一個(gè)或多個(gè)為0的基因位變?yōu)?,增加個(gè)體中被認(rèn)為有錯(cuò)的函數(shù)個(gè)數(shù),使修正后的個(gè)體能夠解釋所有失敗測(cè)試用例。對(duì)個(gè)體進(jìn)行修正時(shí),需要滿足以下幾個(gè)條件:(1)優(yōu)先選擇能夠盡可能多地解釋失敗測(cè)試用例的函數(shù),將其位置變?yōu)?;(2)盡可能地選擇還未被認(rèn)為有錯(cuò)的函數(shù)進(jìn)行修改;(3)保證修改的函數(shù)個(gè)數(shù)盡可能地少。具體算法過(guò)程是:對(duì)于一個(gè)不能解釋全部測(cè)試用例的個(gè)體C 來(lái)說(shuō),選擇能夠解釋最多失敗測(cè)試用例的函數(shù)fx加入到個(gè)體C 中;將fx對(duì)應(yīng)的位置置為1 后,若個(gè)體C 能夠解釋所有失敗測(cè)試用例,則過(guò)程結(jié)束,若不能,則需要再選擇其他解釋失敗測(cè)試用例能力強(qiáng)的函數(shù)加入個(gè)體C ,直到該個(gè)體能夠解釋所有的失敗測(cè)試用例。
獲得一個(gè)有n 個(gè)個(gè)體的種群后,需要對(duì)種群的規(guī)模進(jìn)行調(diào)整。若n <NP,則隨機(jī)復(fù)制NP-n 個(gè)個(gè)體補(bǔ)充到初始種群中,使種群的規(guī)模達(dá)到預(yù)定的NP;若n >NP,則選擇適應(yīng)度值較高的NP個(gè)個(gè)體組成初始種群。
該初始種群生成算法只需挨個(gè)檢查圖4 中的n 個(gè)個(gè)體,判斷解釋失敗測(cè)試用例的能力即可。該算法在最壞情況下是n 個(gè)個(gè)體均不能解釋全部失敗測(cè)試用例,需要對(duì)所有個(gè)體進(jìn)行修正,時(shí)間復(fù)雜度為T(n)=O(n2);最好情況是均可以解釋全部失敗測(cè)試用例,不需要對(duì)其修正,時(shí)間復(fù)雜度為T(n)=O(n)。因此,該初始種群生成算法的時(shí)間復(fù)雜度為T(n)=O(n2)。
通過(guò)AG過(guò)程構(gòu)建初始種群:一是保證初始種群中的每個(gè)個(gè)體C 都能夠解釋所有失敗測(cè)試,具有較高的適應(yīng)度;二是使個(gè)體C 中被認(rèn)為有錯(cuò)的函數(shù)的數(shù)量盡可能少;三是使不同個(gè)體之間有不同的錯(cuò)誤分布情況,保證初始種群的多樣性。
3.3.2 遺傳算子
得到初始種群之后,需要利用遺傳操作算子迭代優(yōu)化,產(chǎn)生優(yōu)質(zhì)的個(gè)體組成新種群,主要包括選擇、交叉和變異三種遺傳算子。
(1)選擇算子
選擇算子(Selection Operator)模擬了自然界的自然選擇。適應(yīng)度高的個(gè)體能夠以較大的概率被選擇,直接遺傳到下一代或者進(jìn)行后續(xù)的交叉、變異操作。
本文將輪盤賭選擇策略作為選擇算子,基本思想是個(gè)體被選擇的概率與其適應(yīng)度函數(shù)的值成正比。假設(shè)種群大小為n,個(gè)體i 的適應(yīng)度為Fi,則i 被選中遺傳到下一代種群的概率為:
1771年10月間,葉卡德琳娜二世頒布了“關(guān)于廢除土爾扈特汗國(guó)的命令,同時(shí)取消了‘汗’和汗國(guó)總督的稱號(hào)”。(參見《卡爾梅克蘇維埃社會(huì)主義自治共和國(guó)史綱》)由于這項(xiàng)命令的實(shí)施,建立于伏爾加河流域一個(gè)半世紀(jì)的土爾扈特汗國(guó)已不復(fù)存在;
(2)交叉算子
交叉算子(Crossover Operator)通過(guò)交換兩個(gè)個(gè)體部分位置的信息,組合出新的個(gè)體遺傳到下一代種群。本文采用均勻交叉(Uniform Crossover)策略,使兩個(gè)父代個(gè)體的每對(duì)等位基因點(diǎn)都能夠以一定的概率Pcro進(jìn)行交換。
舉例說(shuō)明,選擇兩個(gè)個(gè)體被作為父代個(gè)體進(jìn)行交叉:
隨機(jī)生成一組屏蔽字Mask,與個(gè)體長(zhǎng)度等長(zhǎng)。對(duì)于其中的每一位mi,若mi=1,則父代個(gè)體對(duì)應(yīng)的基因位進(jìn)行交換,遺傳到子代個(gè)體;若mi=0,則子代個(gè)體分別繼承對(duì)應(yīng)的父代個(gè)體的基因值。以如下屏蔽字為例:
最后,經(jīng)過(guò)均勻交叉后得到子代的兩個(gè)個(gè)體為:
(3)變異算子
變異算子(Mutation Operator)是產(chǎn)生新個(gè)體的輔助方法,是指將個(gè)體中某些編碼位上的基因值,用該編碼位置的其他等位基因來(lái)替換。一般來(lái)說(shuō),變異概率Pmut的建議取值范圍為0.000 1~0.5。
針對(duì)本文的問(wèn)題,選擇較低的變異概率Pmut進(jìn)行變異。同時(shí),為了避免個(gè)體中的基因從0無(wú)限制地變異為1,設(shè)置參數(shù)para 控制個(gè)體中1的數(shù)量。當(dāng)個(gè)體中錯(cuò)誤的數(shù)量超過(guò)para 時(shí),個(gè)體中的基因不再?gòu)?變異為1,使得個(gè)體不再通過(guò)變異產(chǎn)生更多的錯(cuò)誤位置。
3.3.3 重插入與終止條件
在本方法中,設(shè)置迭代次數(shù)Ngen作為終止條件。在得到初始種群之后,迭代進(jìn)行遺傳算子運(yùn)算以及重插入操作,直到循環(huán)的次數(shù)達(dá)到Ngen,迭代得到最終的最優(yōu)候選種群,進(jìn)行下一步確定軟件錯(cuò)誤位置的操作。
經(jīng)過(guò)一系列遺傳操作算子的計(jì)算操作得到最優(yōu)候選種群之后,需要將得到的錯(cuò)誤分布種群轉(zhuǎn)換為對(duì)應(yīng)的函數(shù)可疑度的排名。若個(gè)體的適應(yīng)度值較高,說(shuō)明該個(gè)體代表的程序錯(cuò)誤分布較為可疑。首先,比較最優(yōu)候選錯(cuò)誤種群中每個(gè)個(gè)體的可疑度,按從高到低的順序進(jìn)行排列。然后,根據(jù)得到的有序排列的種群,統(tǒng)計(jì)所對(duì)應(yīng)的函數(shù)的可疑度情況。適應(yīng)度值排名越靠前的個(gè)體中,同一位置的函數(shù)被認(rèn)為含有錯(cuò)誤的次數(shù)越多,則該函數(shù)實(shí)際有錯(cuò)誤的可能性就越大。以如下最優(yōu)候選錯(cuò)誤分布種群為例:
上述種群中按個(gè)體的適應(yīng)度由高到低、從上往下排列,排序越靠前的個(gè)體中被認(rèn)為有錯(cuò)的函數(shù)的可疑度越大。在第一個(gè)個(gè)體中編號(hào)為2、6、9的函數(shù)被認(rèn)為有錯(cuò),同時(shí)參考種群中其他個(gè)體的分布情況,若分布情況相同,則隨機(jī)排序。該例中,編號(hào)為6的函數(shù)在前3個(gè)個(gè)體中均被認(rèn)為有錯(cuò),該函數(shù)的可疑度最高,其次為編號(hào)為2的函數(shù)。因此,通過(guò)該種群最終得到的函數(shù)可疑度排序?yàn)椋糴6,e2,e9,e1,e4,e3,e7,e5,e10,e8>。
為證明FGAFL 方法的有效性,分別針對(duì)單錯(cuò)誤和多錯(cuò)誤情況設(shè)計(jì)實(shí)驗(yàn)。
4.1.1 實(shí)驗(yàn)數(shù)據(jù)
本文選取來(lái)自SIR(http://sir.unl.edu/portal/index.php)網(wǎng)站的測(cè)試程序Siemens Suite作為實(shí)驗(yàn)數(shù)據(jù)。Siemens Suite被視為評(píng)估錯(cuò)誤定位技術(shù)有效性的典型數(shù)據(jù)[23],包含7個(gè)C語(yǔ)言程序,代碼行數(shù)最多有565行,可執(zhí)行代碼行數(shù)最多有203行,屬于小規(guī)模程序,分別是printtokens、printtokens2、replace、schedule、schedule2、tcas、totinfo。該測(cè)試套件中的每個(gè)程序都包含一個(gè)正確版本和多個(gè)錯(cuò)誤版本,且大多數(shù)的錯(cuò)誤版本中只有一個(gè)錯(cuò)誤,因此選擇在printtokens、replace、schedule 和tcas 程序中植入多個(gè)錯(cuò)誤,用于多錯(cuò)誤定位效果的驗(yàn)證。本文實(shí)驗(yàn)評(píng)測(cè)程序的主要信息如表2所示。
表2 Siemens Suite程序的主要信息
4.1.2 評(píng)測(cè)指標(biāo)
本文在Abreu 等人[4]提出的評(píng)測(cè)標(biāo)準(zhǔn)的基礎(chǔ)上將EXAM 作為評(píng)測(cè)指標(biāo),定義為發(fā)現(xiàn)程序中所有錯(cuò)誤時(shí)需檢查的代碼行數(shù)占總程序中代碼行數(shù)的百分比,具體公式為:
其中,exami表示檢測(cè)到第i 個(gè)錯(cuò)誤需要檢查的代碼行數(shù),n 表示程序中錯(cuò)誤總個(gè)數(shù),N 表示程序中總代碼行數(shù)。該評(píng)測(cè)指標(biāo)適用于單錯(cuò)誤定位和多錯(cuò)誤定位,當(dāng)EXAM用于評(píng)價(jià)單錯(cuò)誤定位問(wèn)題時(shí),可以表示為EXAM=exam/N×100%,即為發(fā)現(xiàn)程序中錯(cuò)誤需要檢查的代碼行數(shù)占總代碼行數(shù)的百分比。
本文實(shí)驗(yàn)內(nèi)容主要分為兩方面:一是驗(yàn)證在適應(yīng)度函數(shù)FMD*的指數(shù)(*)不同取值的情況下,F(xiàn)GAFL 方法的定位效果;二是將FGAFL方法與經(jīng)典方法進(jìn)行對(duì)比。
4.2.1 不同指數(shù)(*)的影響
在本節(jié)中,針對(duì)適應(yīng)度函數(shù)FMD*不同的指數(shù)(*)進(jìn)行實(shí)驗(yàn),*的取值范圍為1~30,增量為1,實(shí)驗(yàn)結(jié)果如圖5所示。
圖5 FGAFL在不同指數(shù)(*)數(shù)值下的錯(cuò)誤定位效果
從圖5 中可以觀察到,隨著指數(shù)(*)值逐漸增大,EXAM 值逐漸減小并最終趨于穩(wěn)定,即找到程序中的錯(cuò)誤需檢查的代碼量隨著指數(shù)(*)的增大而減少。同時(shí),在單錯(cuò)誤定位情況下的EXAM 比多錯(cuò)誤定位情況下更早地趨于穩(wěn)定。由此可以認(rèn)為,前期指數(shù)(*)增大對(duì)單錯(cuò)誤定位效果影響較大,可以較快地提高定位效果,而對(duì)于多錯(cuò)誤定位則需要指數(shù)(*)增大到一定程度才會(huì)較為明顯地提高定位效果。多錯(cuò)誤定位與單錯(cuò)誤定位不同的是,一般程序中的多個(gè)錯(cuò)誤會(huì)跨越多條語(yǔ)句或多個(gè)函數(shù),需依次檢查排名較為靠前的函數(shù),在確定第一個(gè)錯(cuò)誤的位置后仍需檢查后面的函數(shù),直到發(fā)現(xiàn)所有的錯(cuò)誤為止。而這些被檢查的函數(shù)中可能沒有錯(cuò)誤但依然被較多的失敗測(cè)試用例經(jīng)過(guò)或較少的失敗測(cè)試用例未經(jīng)過(guò),因此需要賦予φ(C)更多的權(quán)值才能較為明顯地提高定位準(zhǔn)確性。
4.2.2 與其他方法的對(duì)比實(shí)驗(yàn)
針對(duì)單錯(cuò)誤和多錯(cuò)誤程序進(jìn)行實(shí)驗(yàn),選取經(jīng)典的錯(cuò)誤定位方法Ochiai、Tarantula 和DStar2 進(jìn)行對(duì)比。這三種方法均是通過(guò)構(gòu)造可疑度公式,分析程序運(yùn)行時(shí)的覆蓋情況和運(yùn)行結(jié)果,得到程序中每一個(gè)實(shí)體有錯(cuò)誤的可能性(即可疑度)。
實(shí)驗(yàn)設(shè)置適應(yīng)度函數(shù)FMD*的指數(shù)(*)為2 和10,表示為FMD2、FMD10。實(shí)驗(yàn)結(jié)果如圖6所示。
圖6 對(duì)比實(shí)驗(yàn)結(jié)果
從圖6中可以看出,無(wú)論是單錯(cuò)誤定位還是多錯(cuò)誤定位,F(xiàn)GAFL(圖中表示為FMD2、FMD10)、Ochiai 和DStar2 方法均明顯優(yōu)于Tarantula。圖6(a)是針對(duì)單錯(cuò)誤定位得到的實(shí)驗(yàn)結(jié)果,F(xiàn)GAFL 的整體定位趨勢(shì)與其他方法類似,且在檢查程序中的語(yǔ)句為30%時(shí),F(xiàn)MD10能檢查出的錯(cuò)誤數(shù)更接近于100%,F(xiàn)MD2 的定位效果要略差于FMD10。針對(duì)多錯(cuò)誤定位得到的實(shí)驗(yàn)結(jié)果為圖6(b),可以看出FGAFL、DStar2 方法要明顯優(yōu)于Ochiai 和Tarantula 方法,F(xiàn)MD2 與DStar2 的定位效果類似,但是FMD2要早于DStar2檢查到全部錯(cuò)誤。從檢查的語(yǔ)句為40%開始,F(xiàn)MD10 的定位效果都要優(yōu)于其他方法。
另外,統(tǒng)計(jì)了FGAFL 方法與Ochiai、Tarantula 和DStar2方法在各程序版本上的平均執(zhí)行時(shí)間,經(jīng)多次實(shí)驗(yàn)取得平均值。這四種方法均需要執(zhí)行測(cè)試用例收集程序頻譜信息,因此只需關(guān)注錯(cuò)誤定位部分的執(zhí)行效率,如表3所示。其中Ochiai、Tarantula和DStar2方法只需計(jì)算程序中各個(gè)語(yǔ)句的可疑度即可,執(zhí)行時(shí)間較短,然而這三種方法在多錯(cuò)誤定位中效果不佳,且理論上應(yīng)多次運(yùn)行逐個(gè)定位。雖然執(zhí)行時(shí)間短,但需要花費(fèi)較多的人工時(shí)間去確定錯(cuò)誤的位置。本文提出的FGAFL方法需要通過(guò)遺傳算法迭代尋優(yōu),但是需要檢查的代碼量比較少,提高了人工檢查錯(cuò)誤的效率。
表3 執(zhí)行時(shí)間比較 s
本文基于函數(shù)調(diào)用路徑的知識(shí),在遺傳算法的基礎(chǔ)上提出了一種函數(shù)級(jí)別的軟件錯(cuò)誤定位方法,主要包括以下研究?jī)?nèi)容:
(1)將軟件錯(cuò)誤定位問(wèn)題轉(zhuǎn)化為一類組合優(yōu)化問(wèn)題,利用改進(jìn)的遺傳算法搜索求解,結(jié)合錯(cuò)誤定位的特點(diǎn)對(duì)生成初始種群的方法進(jìn)行優(yōu)化。
(2)結(jié)合函數(shù)調(diào)用路徑技術(shù),在已有的適應(yīng)度函數(shù)上進(jìn)行改進(jìn),提出新的適應(yīng)度函數(shù)FMD*,保證在搜索尋優(yōu)過(guò)程中可以有效地衡量個(gè)體優(yōu)劣。
(3)將函數(shù)作為錯(cuò)誤定位的研究粒度,可以有效地縮短個(gè)體的長(zhǎng)度,降低搜索空間的規(guī)模,提高搜索效率。
(4)選取Siemens Suite 作為實(shí)驗(yàn)數(shù)據(jù),設(shè)計(jì)評(píng)測(cè)指標(biāo)并進(jìn)行實(shí)驗(yàn),同時(shí)選擇經(jīng)典的錯(cuò)誤定位方法進(jìn)行定位效果的對(duì)比。實(shí)驗(yàn)結(jié)果表明,本文提出的方法FGAFL具有可行性和有效性,且有較高的精度和效率。
除此之外,在本文方法的基礎(chǔ)上仍有一些值得關(guān)注的問(wèn)題需要進(jìn)行后續(xù)的研究:
(1)嘗試將本文方法應(yīng)用到更大型的程序中進(jìn)行實(shí)驗(yàn),包括Linux 系統(tǒng)下運(yùn)行的程序以及不同語(yǔ)言的程序。
(2)為了進(jìn)一步提高本文方法的性能,嘗試將遺傳算法與其他搜索算法結(jié)合,或者選擇不同的搜索算法進(jìn)行實(shí)驗(yàn)。
(3)進(jìn)一步考慮將函數(shù)粒度的研究與語(yǔ)句粒度相結(jié)合,做到先定位到函數(shù)后定位到語(yǔ)句,對(duì)函數(shù)中的語(yǔ)句進(jìn)行可疑度排序,進(jìn)一步提高定位錯(cuò)誤的效率。