張 蓓，張樹(shù)東

(首都師范大學(xué) 信息工程學(xué)院，北京 100048)

基于增強(qiáng)GA-BP神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法

張 蓓，張樹(shù)東

(首都師范大學(xué) 信息工程學(xué)院，北京 100048)

在軟件開(kāi)發(fā)和后期維護(hù)的過(guò)程中，進(jìn)行軟件調(diào)試來(lái)定位錯(cuò)誤并修正錯(cuò)誤是其中最復(fù)雜且成本最大的一部分；文章針對(duì)現(xiàn)有基于神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法中的權(quán)值和閾值設(shè)定不方便、魯棒性差等問(wèn)題，結(jié)合正交實(shí)驗(yàn)設(shè)計(jì)思想和遺傳算法(Genetic Algorithm)，提出了一種基于增強(qiáng)遺傳BP神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法；并將其同基于GA-BP神經(jīng)網(wǎng)絡(luò)的和基于BP神經(jīng)網(wǎng)絡(luò)的定位方法都在MATLAB上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)來(lái)源西門(mén)子測(cè)試集，從結(jié)果上看，基于增強(qiáng)GA-BP神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法在定位錯(cuò)誤的效率和精確度上都有一些進(jìn)步。

錯(cuò)誤定位；GA-BP神經(jīng)網(wǎng)絡(luò)；正交實(shí)驗(yàn)設(shè)計(jì)

0 引言

隨著時(shí)代的進(jìn)步，計(jì)算機(jī)正滲入社會(huì)的各個(gè)角落，逐步改變著我們的生活，手機(jī)、電腦等電子產(chǎn)品使人與人之間的距離變短，就算相隔千里都變成了一根網(wǎng)線(xiàn)的距離；在冰箱、空調(diào)、電視等家電上安裝的智能控制系統(tǒng)使這些電器變得更加“聽(tīng)話(huà)”；物聯(lián)網(wǎng)、智能社區(qū)、智慧城市等技術(shù)的發(fā)展使人類(lèi)的生活變得更加信息化、智能化。然而，計(jì)算機(jī)技術(shù)的發(fā)展不僅能帶來(lái)便利快捷的一面，還會(huì)產(chǎn)生不好的影響，例如黑客利用網(wǎng)站的漏洞來(lái)攻擊某些網(wǎng)站，妨礙網(wǎng)站的正常運(yùn)營(yíng)或者獲取用戶(hù)資料來(lái)進(jìn)行一些非法活動(dòng)；游戲代碼存在漏洞，會(huì)造成一些外掛軟件的產(chǎn)生，從而造成一個(gè)不公平的游戲環(huán)境，損害游戲玩家的利益。所以，改進(jìn)軟件可靠性迫在眉睫。

為了提高軟件的質(zhì)量，就必須盡可能多地找到軟件中存在的問(wèn)題，才能解決問(wèn)題，而發(fā)現(xiàn)問(wèn)題是其中最難的一個(gè)環(huán)節(jié)。在傳統(tǒng)的錯(cuò)誤定位方法中，都是靠工作人員手工調(diào)試代碼來(lái)找出錯(cuò)誤的所在位置，主要方法是在代碼中設(shè)置斷點(diǎn)或者插入某一段測(cè)試程序，跟蹤程序運(yùn)行步驟，根據(jù)程序運(yùn)行狀態(tài)是否正常，捕捉到的中間值是否同預(yù)期相符合來(lái)進(jìn)行錯(cuò)誤定位，這種方式不僅花費(fèi)時(shí)間多、效率低下，還很枯燥乏味，還可能在代碼中注入其他語(yǔ)句，造成不可預(yù)知的影響。如果能實(shí)現(xiàn)自動(dòng)化錯(cuò)誤定位，就能將工作人員從繁瑣的工作中解放出來(lái)，提高軟件調(diào)試效率，降低軟件開(kāi)發(fā)成本。

近幾年，中外學(xué)者對(duì)軟件錯(cuò)誤定位的自動(dòng)化做了各種研究，成果豐富，根據(jù)原理不同可以大致分為基于切片、基于程序光譜和基于狀態(tài)修改的錯(cuò)誤定位方法。

基于程序切片(slicing-based)[1-3]的錯(cuò)誤定位方法：程序切片，顧名思義，就是縮小范圍，該方法的主要思想是構(gòu)建一個(gè)程序中可能同錯(cuò)誤輸出有關(guān)的代碼的集合，包括兩個(gè)內(nèi)容：錯(cuò)誤所在的語(yǔ)句和同錯(cuò)誤語(yǔ)句相關(guān)的，可供工作人員理解程序的調(diào)試上下文，盡可能的縮小可疑語(yǔ)句存在的范圍，減少需要檢測(cè)的代碼行數(shù)，提高軟件調(diào)試的效率。這種方法可適用于規(guī)模較大程序的測(cè)試，但是由于需要事先對(duì)程序進(jìn)行依賴(lài)關(guān)系分析，過(guò)程復(fù)雜，需要耗費(fèi)大量資源，而且往往處理后的代碼量還是很大，冗余度很高，需要做進(jìn)一步的簡(jiǎn)化。

基于程序光譜(spectrum-based)的錯(cuò)誤定位方法：程序光譜是指在程序執(zhí)行測(cè)試用例過(guò)程中統(tǒng)計(jì)的信息[4]?？梢酝ㄟ^(guò)在程序中定位不同的元素，例如可執(zhí)行語(yǔ)句或語(yǔ)句塊[5]、謂詞[6]、方法[7]、信息流路徑[8]，來(lái)獲取不同的程序光譜，這個(gè)方法的主要思想是利用成功執(zhí)行案例的程序光譜信息同失敗執(zhí)行案例的程序光譜信息之間的差異來(lái)定位錯(cuò)誤，基于統(tǒng)計(jì)數(shù)據(jù)或者各種數(shù)學(xué)計(jì)算方法獲得程序中的每個(gè)元素的可疑度并排序，排名越靠前，可疑度越高，該元素越可能出現(xiàn)錯(cuò)誤。這種方法的復(fù)雜度低，并且工作人員可以直接根據(jù)語(yǔ)句的可疑度的不同，從可疑度最大的語(yǔ)句開(kāi)始排查，從而能更快的定能錯(cuò)誤，但是它沒(méi)有分析程序元素間的關(guān)系，并且結(jié)果容易受到某些特殊性質(zhì)的測(cè)試數(shù)據(jù)的干擾。

基于程序狀態(tài)(state-based)[9-10]的錯(cuò)誤定位方法：基于程序狀態(tài)的錯(cuò)誤定位方法的中心思想是首先統(tǒng)計(jì)正確測(cè)試用例執(zhí)行過(guò)程中的運(yùn)行狀態(tài)和故障測(cè)試用例執(zhí)行過(guò)程中的運(yùn)行狀態(tài)，將兩者作對(duì)比得出差異結(jié)果，再按照不同的規(guī)則對(duì)失敗測(cè)試用例的運(yùn)行狀態(tài)進(jìn)行修改，根據(jù)修改后得出的測(cè)試結(jié)果來(lái)找出錯(cuò)誤所在關(guān)鍵語(yǔ)句的位置。這種方法的復(fù)雜度低，且能有效減少需要被檢測(cè)的運(yùn)行狀態(tài)的數(shù)量，效率高，但是能定位的錯(cuò)誤的類(lèi)型很少。

除了傳統(tǒng)的錯(cuò)誤定位方法外，近些年，國(guó)內(nèi)外有些學(xué)者提出了將神經(jīng)網(wǎng)絡(luò)應(yīng)用于軟件錯(cuò)誤定位領(lǐng)域中，例如在2009年，Wong等提出的基于BP神經(jīng)網(wǎng)絡(luò)的錯(cuò)誤定位算法[11]。由于神經(jīng)網(wǎng)絡(luò)算法中含有大量的參數(shù)，這些參數(shù)數(shù)值的設(shè)置對(duì)錯(cuò)誤定位的最終結(jié)果的準(zhǔn)確度有很大的影響。本文基于這些算法，融合遺傳算法思想(Genetic Algorithm)和正交試驗(yàn)設(shè)計(jì)的思想(Orthogonal Experimental Design, OED)，提出了一種新的軟件錯(cuò)誤定位方法——基于增強(qiáng)遺傳算法和BP神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位方法EGA-BPN,利用遺傳算法來(lái)計(jì)算BP神經(jīng)網(wǎng)絡(luò)參數(shù)的最初設(shè)定值，并且采用正交試驗(yàn)設(shè)計(jì)方法來(lái)調(diào)整EGA-BPN中的參數(shù)值，使EGA-BPN的更適用于錯(cuò)誤定位。

1 增強(qiáng)GA-BP神經(jīng)網(wǎng)絡(luò)模型(EGA-BPN)

BP神經(jīng)網(wǎng)絡(luò)(Back Propagation)分為輸入層、隱含層和輸出層，結(jié)構(gòu)如圖1所示，其中隱含層可能是一層，也有可能是多層，每一層中都含有神經(jīng)元，神經(jīng)元的數(shù)量不固定，大多數(shù)情況下只能通過(guò)嘗試的方法來(lái)確定[12]，它對(duì)于非線(xiàn)性或者其他更復(fù)雜的關(guān)系的識(shí)別需要訓(xùn)練很多的次數(shù)，而且無(wú)法排除局部極小點(diǎn)，算法時(shí)間消耗大。針對(duì)BP神經(jīng)網(wǎng)絡(luò)的這些缺點(diǎn)，國(guó)內(nèi)外學(xué)者做了很多研究，其中一種改進(jìn)方法是利用遺傳算法能“優(yōu)勝劣汰，適者生存”的能力克服BP神經(jīng)網(wǎng)絡(luò)算法的缺陷和不足，從而進(jìn)行一定的優(yōu)化升級(jí)。

圖1 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

EGA-BPN的主要思想是用GA來(lái)處理神經(jīng)網(wǎng)絡(luò)各層之間的連接權(quán)重和閾值，篩選出其中的最佳個(gè)體，即誤差最小的一組，將其作為神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值的最初設(shè)定值，將輸入值代入神經(jīng)網(wǎng)絡(luò)后，用網(wǎng)絡(luò)的預(yù)測(cè)結(jié)果同預(yù)期輸出值作比較，根據(jù)誤差繼續(xù)利用OED調(diào)整網(wǎng)絡(luò)參數(shù)值，再重新執(zhí)行直到神經(jīng)網(wǎng)絡(luò)訓(xùn)練完成。將測(cè)試數(shù)據(jù)作為網(wǎng)絡(luò)輸入，并對(duì)輸出結(jié)果分析總結(jié)。圖2是EGA-BPN模型執(zhí)行流程圖：

圖2 EGA-BPN流程圖

EGA-BPN模型訓(xùn)練過(guò)程如下：

1)首個(gè)任務(wù)是編碼來(lái)獲得遺傳初始種群，每個(gè)編碼串也就是每個(gè)染色體包含了神經(jīng)網(wǎng)絡(luò)各層之間的連接權(quán)值和閾值，通過(guò)隨機(jī)函數(shù)產(chǎn)生N個(gè)。

2)確定神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，分別計(jì)算染色體的基因遺傳給后代的可能性，也就是其適應(yīng)性值F，F(xiàn)是根據(jù)第i個(gè)訓(xùn)練數(shù)據(jù)經(jīng)網(wǎng)絡(luò)處理的訓(xùn)練預(yù)測(cè)值yi同其期望輸出值oi之間的誤差來(lái)定義的，為了使結(jié)果更精確和易于判斷，通常采用誤差的絕對(duì)值來(lái)作為判斷依據(jù)，適應(yīng)值越大的染色體，其基因遺傳下去的可能就越大，F(xiàn)的計(jì)算公式如下：

(1)

其中:n為網(wǎng)絡(luò)輸出節(jié)點(diǎn)數(shù)，k為系數(shù)。對(duì)染色體進(jìn)行交叉、變異操作，將經(jīng)過(guò)層層篩選得出最終個(gè)體作為神經(jīng)網(wǎng)絡(luò)權(quán)值和閾值的最初設(shè)定值。

3)設(shè)神經(jīng)網(wǎng)絡(luò)的輸入層、隱含層、輸出層的節(jié)點(diǎn)數(shù)量分別為m、p和q，三層神經(jīng)元之間的連接權(quán)值分別是wij和vjk，隱含層閾值為αi，輸出層閾值為βk，確定學(xué)習(xí)參數(shù)以及神經(jīng)元激勵(lì)函數(shù)f(x)，該函數(shù)一般用sigmoid傳遞函數(shù)。將網(wǎng)絡(luò)輸入數(shù)據(jù)用矩陣表示為：

X=[X1,X2,…Xm]

(2)

4)隱含層輸出Y可以由輸入向量X、wij和αi計(jì)算得出，具體公式如下：

(3)

5)輸出層結(jié)果Z可以由Y、vjk和βk計(jì)算得出，具體公式如下：

(4)

6)若神經(jīng)元Xi的期望輸出值是Ok，那么可以根據(jù)如下均方誤差函數(shù)公式求出誤差E：

(5)

7)將誤差E同預(yù)設(shè)值作對(duì)比，如果小于預(yù)設(shè)值或者訓(xùn)練次數(shù)已達(dá)到預(yù)設(shè)次數(shù)，則代表訓(xùn)練完畢，反之，要按照如下公式進(jìn)行誤差修正：

(6)

其中:n表示網(wǎng)絡(luò)的訓(xùn)練次數(shù)，Δwij和Δvik分別表示權(quán)值閾值的修正值，公式如下：

(7)

8)在公式(7)中，σ和σ′表示學(xué)習(xí)參數(shù)，結(jié)合OED來(lái)調(diào)整學(xué)習(xí)參數(shù)的值[13]。將修正后的參數(shù)作為新的網(wǎng)絡(luò)連接權(quán)值和閾值，返回第(3)步，直到達(dá)到理想狀態(tài)或者訓(xùn)練次數(shù)達(dá)到設(shè)定值。

2 基于EGA-BPN的軟件錯(cuò)誤定位算法

基于EGA-BPN的軟件錯(cuò)誤定位算法流程如下：

1)獲得程序執(zhí)行信息。對(duì)于一個(gè)存在錯(cuò)誤并且能正常執(zhí)行的程序P，例如表1中兩數(shù)相加求和程序[14]，有9條語(yǔ)句，按照語(yǔ)句順序?qū)⑵渚幪?hào)為S1、S2……S9，其中存在錯(cuò)誤語(yǔ)句S3。對(duì)于一個(gè)測(cè)試用例tk=，其中，ink表示其輸入信息；outk表示其輸出信息；Ck表示其程序覆蓋信息，在tk運(yùn)行過(guò)程中，執(zhí)行了語(yǔ)句Si，則將Ck中標(biāo)識(shí)該語(yǔ)句的覆蓋標(biāo)識(shí)符Cki設(shè)為1，否則設(shè)為0；flag是程序執(zhí)行結(jié)果標(biāo)識(shí)符，如果outk等于ink期望輸出值，那么測(cè)試用例tk執(zhí)行成功，將其flag的值設(shè)為0，反之outk不等于ink期望輸出值，那么tk執(zhí)行失敗，將其flag的值設(shè)為1。對(duì)于一些規(guī)模較大的程序，很難實(shí)現(xiàn)按照語(yǔ)句的順序來(lái)得到測(cè)試用例的覆蓋信息，可以更換程序元素，換成謂詞、方法等，減少神經(jīng)網(wǎng)絡(luò)處理的數(shù)據(jù)量，提高錯(cuò)誤定位效率。

表1 獲取語(yǔ)句覆蓋信息實(shí)例

2)編碼神經(jīng)網(wǎng)絡(luò)各層之間的權(quán)值閾值，形成遺傳算法的進(jìn)化初始種群，利用交叉、變異算子計(jì)算適應(yīng)度最高的染色體，遺傳給下一代，挑選出最優(yōu)個(gè)體，最終得出的結(jié)果就是BP神經(jīng)網(wǎng)絡(luò)參數(shù)的最初設(shè)定值；

3)接下來(lái)就是訓(xùn)練神經(jīng)網(wǎng)絡(luò)，將測(cè)試用例tk的程序覆蓋信息Ck=作為訓(xùn)練神經(jīng)網(wǎng)絡(luò)的輸入層神經(jīng)單元，表1中的實(shí)例，訓(xùn)練數(shù)據(jù)有8組，每組有9個(gè)輸入神經(jīng)元。再利用三層之間的連接參數(shù)按照一定的公式對(duì)輸入數(shù)據(jù)進(jìn)行一系列的計(jì)算，得到輸出值，將實(shí)際輸出值同期望輸出值flag作比較，得出誤差，如果誤差值大于設(shè)定誤差值，則利用OED調(diào)整參數(shù)值。循環(huán)這個(gè)過(guò)程，直到誤差值小于等于設(shè)定誤差值或者循環(huán)次數(shù)已經(jīng)超出最大循環(huán)值，循環(huán)停止，神經(jīng)網(wǎng)絡(luò)訓(xùn)練完成。

4)一旦神經(jīng)網(wǎng)絡(luò)訓(xùn)練完成，就在輸入數(shù)據(jù)和輸出數(shù)據(jù)之間建立了良好的計(jì)算網(wǎng)絡(luò)，用一組虛擬測(cè)試用例v1,v2,…,vm，每一個(gè)測(cè)試用例vi依次覆蓋一條語(yǔ)句si，測(cè)試用例的覆蓋信息是Cv1,Cv1,…,Cvm，用矩陣的形式表示如下[15]：

(8)

將虛擬測(cè)試用例數(shù)據(jù)賦值給網(wǎng)絡(luò)的輸入層，預(yù)測(cè)結(jié)果為f1,f2,…,fm。fi的值越靠近0，那么表示該測(cè)試用例vi運(yùn)行結(jié)果很可能成功，其覆蓋語(yǔ)句si出錯(cuò)的可能性較小，反之fi的值越靠近1，那么表示vi的運(yùn)行結(jié)果很可能失敗，si也可能存在錯(cuò)誤，所以可以將輸出結(jié)果f1,f1,…fm,看成覆蓋語(yǔ)句s1,s2,…sm,的錯(cuò)誤可疑率，可疑率越大的語(yǔ)句，出錯(cuò)概率越高，需要被檢查的優(yōu)先級(jí)也要提前。

5)將神經(jīng)網(wǎng)絡(luò)的輸出結(jié)果，即語(yǔ)句的錯(cuò)誤可疑率按序進(jìn)行排列，給工作人員提供參考，工作人員可以直接從可疑率最大的語(yǔ)句進(jìn)行錯(cuò)誤排查，從而節(jié)省了很多時(shí)間，提高工作效率。

3 實(shí)驗(yàn)結(jié)果與分析

EGA-BPN算法的實(shí)驗(yàn)需要測(cè)試用例的4個(gè)元素：輸入數(shù)據(jù)、輸出數(shù)據(jù)、覆蓋信息和運(yùn)行結(jié)果標(biāo)識(shí)符。如果測(cè)試程序語(yǔ)句量較大，首先要對(duì)程序分塊，將塊作為實(shí)驗(yàn)最小單位，再執(zhí)行測(cè)試用例，生成覆蓋文件，對(duì)覆蓋文件進(jìn)行過(guò)濾、分離、抽取等操作，得到測(cè)試用例的覆蓋信息，最后將系統(tǒng)運(yùn)行得到的輸出數(shù)據(jù)同預(yù)期值進(jìn)行比對(duì)，得出運(yùn)行結(jié)果標(biāo)識(shí)符，最后將這些信息進(jìn)行整合，歸納，篩選，得出類(lèi)似表1的數(shù)據(jù)文件，將其作為EGA-BPN的輸入數(shù)據(jù)，賦值給之前已經(jīng)訓(xùn)練完成的神經(jīng)網(wǎng)絡(luò)，將網(wǎng)絡(luò)的預(yù)測(cè)結(jié)果按序排列，排名越靠前的代碼塊越需要被檢查是否有錯(cuò)誤。將表1中的示例程序按照EGA-BPN算法計(jì)算出的結(jié)果如下：

表2 示例執(zhí)行結(jié)果

按照表2的數(shù)據(jù)我們看出，錯(cuò)誤存在的語(yǔ)句S3的可疑度數(shù)值最大，最可能出現(xiàn)錯(cuò)誤。為了進(jìn)一步論證本文方法的有效性，引入了此西門(mén)子套件集(Siemens suit)作為進(jìn)一步實(shí)驗(yàn)的數(shù)據(jù)來(lái)源，西門(mén)子套件集是由Software-artifact Infrastructure Repository(SIR)[16]提供，大部分由C語(yǔ)言編寫(xiě)，每個(gè)程序都有正確版本、錯(cuò)誤版本和測(cè)試用例，并且錯(cuò)誤都是由人工添加進(jìn)程序的，有語(yǔ)句賦值錯(cuò)誤、謂詞錯(cuò)誤等，錯(cuò)誤類(lèi)型都和實(shí)際工程中可能發(fā)生的類(lèi)型相似。但是，并不是套件集所有的錯(cuò)誤版本都適合本次實(shí)驗(yàn)，例如print_tokens的錯(cuò)誤版本4的錯(cuò)誤語(yǔ)句存在于頭文件中，不能統(tǒng)計(jì)錯(cuò)誤語(yǔ)句的覆蓋信息；例如replace的錯(cuò)誤版本27和錯(cuò)誤版本32，在執(zhí)行測(cè)試用例過(guò)程中會(huì)發(fā)生錯(cuò)誤，從而會(huì)產(chǎn)生程序異常終止，不能得出輸出結(jié)果數(shù)據(jù)。

為了檢驗(yàn)算法的有效性，引入定位有效率作為評(píng)價(jià)指標(biāo)，算法的定位有效率是指在定位錯(cuò)誤過(guò)程中所花的精力，也就是檢測(cè)出錯(cuò)誤百分比同已檢測(cè)代碼百分比的比值，假設(shè)A算法和B算法同樣檢測(cè)出了55%的錯(cuò)誤，但是A算法已檢測(cè)代碼占總代碼的30%，而B(niǎo)算法已檢測(cè)代碼占同代碼的50%，那么顯然，A算法的定位有效率的值小于B算法的定位有效率的值，A算法的計(jì)算效率比B算法的計(jì)算效率更高，性能更優(yōu)。圖3展示了EGA-BPN同GA-BPN和BPN的定位有效率的比較。

圖3 EGA-BPN、GA-BPN、BPN的定位有效率比較

根據(jù)圖3數(shù)據(jù)，我們可以看出，在已檢測(cè)同樣的代碼數(shù)的情況下，EGA-BPN能定位更多的錯(cuò)誤，同樣，在定位同樣多錯(cuò)誤的情況下，EGA-BPN只需檢測(cè)更少量的代碼，相比較而言，EGA-BPN具有更高的效率和精確度。

4 總結(jié)與展望

本文將遺傳算法、BP神經(jīng)網(wǎng)絡(luò)和正交試驗(yàn)設(shè)計(jì)融合，應(yīng)用于錯(cuò)誤定位領(lǐng)域，提出了增強(qiáng)GA-BP神經(jīng)網(wǎng)絡(luò)的軟件錯(cuò)誤定位算法，實(shí)驗(yàn)證明，該算法在定位錯(cuò)誤的效率和精確度方面確實(shí)比GA-BPN和BPN具有一定的提高。雖然該錯(cuò)誤定位算法取得了良好的實(shí)驗(yàn)結(jié)果，但是該算法還存在很多不足，例如：實(shí)驗(yàn)結(jié)果只是給出了錯(cuò)誤語(yǔ)句的可疑度排名，還需要工作人員逐一排查，手動(dòng)修改錯(cuò)誤并再次執(zhí)行程序以確認(rèn)錯(cuò)誤是否已修改；另外，神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)的準(zhǔn)確性同訓(xùn)練數(shù)據(jù)有較大關(guān)系，訓(xùn)練數(shù)據(jù)越多，預(yù)測(cè)結(jié)果相對(duì)來(lái)說(shuō)就更準(zhǔn)確，但是在實(shí)際工程中，由于程序結(jié)構(gòu)或者邏輯都比較復(fù)雜，獲得程序的測(cè)試用例、覆蓋信息、執(zhí)行結(jié)果等信息需要耗費(fèi)大量的時(shí)間，會(huì)降低測(cè)試效率。這些不足在后續(xù)研究中會(huì)繼續(xù)優(yōu)化改進(jìn)。

[1] Sterling C D, Olsson R A. Automated bug isolation via program chipping[J]. Software: Practice and Experience, 2007, 37(10): 1061-1086.

[2] Zhang X, Gupta N, Gupta R. Locating faulty code by multiple points slicing[J]. Software: Practice and Experience, 2007, 37(9): 935-961.

[3] Wong W E, Qi Y. Effective program debugging based on execution slices and inter-block data dependency[J]. Journal of Systems and Software, 2006, 79(7): 891-903.

[4] Abreu R, Zoeteweij P, Van Gemund A J C. On the accuracy of spectrum-based fault localization[C]. Testing: Academic and Industrial Conference Practice and Research Techniques Mutation, 2007: 89-98.

[5] Jones J A, Harrold M J, Stasko J. Visualization of test information to assist fault localization[C]. Proceedings of the 24th international conference on Software engineering, ACM, 2002: 467-477.

[6] Masri W. Fault localization based on information flow coverage[J]. Software Testing: Verification and Reliability, 2010, 20(2): 121-147.

[7] Murtaza S S, Madhavji N, Gittens M, et al. Diagnosing new faults using mutants and prior faults (NIER track)[C]. IEEE 33rd International Conference on Software Engineering, 2011: 960-963.

[8] Yu K, Lin M, Gao Q, et al. Locating faults using multiple spectra-specific models[C].Proceedings of the 2011 ACM Symposium on Applied Computing, 2011: 1404-1410.

[9] Zhang X, GuPta N, GuPta T.LocatingFaultsthroughAutomatedPredicate Switching[C].Inthe28thInternational Conference onSoftwareEngineering(ICSE.06),May2006:272-281.

[10] Cleve H, Zeller A.Locating Causes of Program Failures[C].In the 27thInternational Conference on Software Engineering(ICSE.05),2005:342-351.

[11] Wong W E, Qi Y. BP neural network-based effective fault localization[J]. International Journal of Software Engineering and Knowledge Engineering, 2009,19(4):573-597.

[12] 史忠值. 神經(jīng)網(wǎng)絡(luò)[M].北京: 高等教育出版社, 2009.

[13] 張 柯, 張德平, 汪 帥. 基于增強(qiáng)徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)的錯(cuò)誤定位方法[J]. 計(jì)算機(jī)應(yīng)用研究,2015, 3.

[14] Eric Wong W, VidrohaDebroy and et al. The DStar Method for Effective Software Fault Localization[J]. IEEE Transactions on Reliability, 2014, 63(1): 290-308.

[15] Wong W E, Debroy V, Thuraisingham B and et al. RBF Neural Network-based fault location[J]. Technical report UTDCS-20-10, 2010.

[16] SIR, http://sir.unl.edu/portal/index/php[EB/OL].

Fault Localization Method Based on Enhanced GA-BP Neural Network

Zhang Bei，Zhang Shudong

(College of Information Engineering, Capital Normal University, Beijing 100048, China)

In the process of software development and maintenance, software debugging is the most complicated and the most expensive part. During the period of traditional software debugging, programmers have to locate mistakes by browsing codes, this is a time-consuming and laborious work. There has been a great need for fault localization techniques that can help guide programmers to the locations of faults. In recent years, automated software fault localization technology has attracted many scholars’ attention, various approaches have been proposed. In this paper, a technique named EGA-BPN is proposed which can propose suspicious locations for fault localization automatically without requiring any prior information of program structure or semantics. EGA-BPN is a software fault localization method based on enhanced Genetic Algorithm-Back Propagation neural network. Firstly, through processing running traces of the program, covering information of test cases are converted as the training samples of neural network; secondly, the data are input into neural network in training orderly, the initial weights of neural network are computed by GA, then test matrix is calculated by the neural network to count the suspiciousness of each statement, and using orthogonal experimental design to adjust the parameters of neural networks; finally, the fault is located at the statements with higher suspicious value. Through experiment on the proposed method and GA-BPN and BPN were compared, the results show that the enhanced GA-BP neural network-based fault localization technology has certain validity.

software fault localization; GA-BP neural network; orthogonal experimental design

2016-01-18；

2016-02-26。

張 蓓(1992-)女，碩士研究生，主要從事軟件測(cè)試方向的研究。

張樹(shù)東(1969-)男，教授，博士，主要從事計(jì)算機(jī)網(wǎng)絡(luò)和分布式計(jì)算等方向的研究。

1671-4598(2017)03-0123-03

10.16526/j.cnki.11-4762/tp.2017.03.034

TP3

A