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

張 蓓，張樹東

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

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

張 蓓，張樹東

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

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

錯誤定位；GA-BP神經(jīng)網(wǎng)絡；正交實驗設計

0 引言

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

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

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

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

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

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

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

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

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

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

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

圖2 EGA-BPN流程圖

EGA-BPN模型訓練過程如下：

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

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

(1)

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

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

X=[X1,X2,…Xm]

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

2 基于EGA-BPN的軟件錯誤定位算法

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

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

表1 獲取語句覆蓋信息實例

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

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

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

(8)

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

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

4 總結(jié)與展望

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

[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)絡[M].北京: 高等教育出版社, 2009.

[13] 張 柯, 張德平, 汪 帥. 基于增強徑向基函數(shù)神經(jīng)網(wǎng)絡的錯誤定位方法[J]. 計算機應用研究,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-)女，碩士研究生，主要從事軟件測試方向的研究。

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

1671-4598(2017)03-0123-03

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

TP3

A