基于遺傳算法的函數(shù)級(jí)別軟件錯(cuò)誤定位

黃晴雁，牟永敏，崔展齊，張志華

1.北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京100101

2.北京信息科技大學(xué) 網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室，北京100101

1 引言

軟件調(diào)試在軟件開(kāi)發(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í)際軟件開(kāi)發(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)用信息，利用遺傳算法搜索求解。

2 相關(guān)概念與技術(shù)

2.1 軟件錯(cuò)誤定位

基于程序頻譜的錯(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í)行成功。

2.2 函數(shù)調(diào)用路徑

在錯(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)用圖沒(méi)有考慮調(diào)用這些函數(shù)時(shí)的控制流信息，不能正確反映函數(shù)可能的執(zhí)行路徑，而圖（b）中函數(shù)調(diào)用圖可以更為準(zhǔn)確地反映出該程序中存在的函數(shù)執(zhí)行路徑，路徑1(main →f1→f2→end)和路徑2(main →f1→f3→end)。

2.3 遺傳算法

遺傳算法（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所示。

3 錯(cuò)誤定位方法FGAFL

3.1 方法框架

圖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 預(yù)處理過(guò)程

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ù)沒(méi)有被失敗測(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 遺傳算法獲得最優(yōu)種群

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(mén)(n)=O(n2)；最好情況是均可以解釋全部失敗測(cè)試用例，不需要對(duì)其修正，時(shí)間復(fù)雜度為T(mén)(n)=O(n)。因此，該初始種群生成算法的時(shí)間復(fù)雜度為T(mén)(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ù)的交叉、變異操作。

本文將輪盤(pán)賭選擇策略作為選擇算子，基本思想是個(gè)體被選擇的概率與其適應(yīng)度函數(shù)的值成正比。假設(shè)種群大小為n，個(gè)體i 的適應(yīng)度為Fi，則i 被選中遺傳到下一代種群的概率為：

1771年10月間，葉卡德琳娜二世頒布了“關(guān)于廢除土爾扈特汗國(guó)的命令，同時(shí)取消了‘汗’和汗國(guó)總督的稱號(hào)”。(參見(jiàn)《卡爾梅克蘇維埃社會(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ò)誤位置的操作。

3.4 確定錯(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＞。

4 實(shí)驗(yàn)評(píng)測(cè)

為證明FGAFL 方法的有效性，分別針對(duì)單錯(cuò)誤和多錯(cuò)誤情況設(shè)計(jì)實(shí)驗(yàn)。

4.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)測(cè)指標(biāo)

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ù)的百分比。

4.2 實(shí)驗(yàn)內(nèi)容與結(jié)果

本文實(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ù)中可能沒(méi)有錯(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%開(kāi)始，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

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

本文基于函數(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ò)誤的效率。