彭 玲 劉振宇 彭 敏

(南華大學(xué)計(jì)算機(jī)學(xué)院 湖南 衡陽 421000)

0 引 言

隨著互聯(lián)網(wǎng)和計(jì)算機(jī)行業(yè)的飛速發(fā)展，程序的規(guī)模也隨之?dāng)U大，愈加復(fù)雜，保證程序的安全性已經(jīng)成為提高程序質(zhì)量極其重要的因素之一。但是，在程序的開發(fā)與維護(hù)中常常會(huì)出現(xiàn)人為或邏輯的錯(cuò)誤，從而導(dǎo)致出現(xiàn)程序失效的概率提高[1-2]。所以程序調(diào)試與整個(gè)程序開發(fā)周期并行進(jìn)行，在程序開發(fā)和維護(hù)中極其重要，而程序缺陷定位又是其最重要和最耗時(shí)的工作之一。因此，準(zhǔn)確定位缺陷位置，能有效地減少開發(fā)過程中的錯(cuò)誤，提高程序的高可靠性和降低維護(hù)成本。

多年來，為了提高程序缺陷定位的效率，中外學(xué)者對(duì)自動(dòng)化程序缺陷定位提出了多種方法，大致分為三類：基于切片、基于程序頻譜和基于狀態(tài)修改?；诔绦蚯衅?slicing-based)[3-5]缺陷定位方法：程序切片，即縮小被測(cè)程序范圍，主要是構(gòu)建一個(gè)被測(cè)程序內(nèi)可能造成程序失效的語句的集合，盡可能縮小查找范圍，提高調(diào)試效率。該類方法適用在規(guī)模較大的程序上，因?yàn)樾枰治龀绦虻囊蕾囮P(guān)系，所以過程復(fù)雜，對(duì)程序員的代碼理解能力要求較高，且處理后的代碼量一般還是很大，仍需進(jìn)一步簡(jiǎn)化?；诔绦蝾l譜(spectrum-based)缺陷定位方法主要是在被測(cè)程序上執(zhí)行其特定的測(cè)試用例集并統(tǒng)計(jì)失敗測(cè)試用例和成功測(cè)試用例的覆蓋信息[6]，可以是程序中不同的元素的覆蓋信息，例如可執(zhí)行語句或程序塊[7]、函數(shù)[8]和執(zhí)行路徑[9]，然后根據(jù)預(yù)先定義的可疑度計(jì)算公式計(jì)算每條語句的可疑度，然后根據(jù)可疑度大小，由大到小尋找缺陷語句。該類方法相較于程序切片方法復(fù)雜度低，工作人員可根據(jù)排序后的結(jié)果，從可疑度最大的語句開始調(diào)試，調(diào)試效率提升。但是該方法沒有考慮語句間的依賴關(guān)系，并且會(huì)受到偶然成功的測(cè)試用例的影響。基于程序狀態(tài)(state-based)[10-11]缺陷定位方法首先對(duì)比成功測(cè)試用例和失敗測(cè)試用例執(zhí)行過程中的運(yùn)行狀態(tài)的差異，再按照不同規(guī)則對(duì)失敗測(cè)試用例的運(yùn)行狀態(tài)進(jìn)行修改，最后根據(jù)修改后得到的測(cè)試結(jié)果來定位缺陷語句。該方法復(fù)雜度較低，但是僅適用于很小范圍的缺陷類型。

除上述三種方法外，近年來，國(guó)內(nèi)外學(xué)者提出了將神經(jīng)網(wǎng)絡(luò)應(yīng)用于程序測(cè)試的缺陷定位領(lǐng)域。Wong等[12]提出了一種基于RBF神經(jīng)網(wǎng)絡(luò)的程序錯(cuò)誤定位方法。秦興生等[13]提出了利用神經(jīng)網(wǎng)絡(luò)集成的程序故障預(yù)測(cè)方法。張柯等[14]提出了基于增強(qiáng)徑向函數(shù)神經(jīng)網(wǎng)絡(luò)的程序錯(cuò)誤定位方法。Zheng等[15]提出將深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network,DNN)應(yīng)用于程序缺陷定位方面。一系列的研究成果表明基于機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的程序缺陷定位模型相較于傳統(tǒng)程序缺陷定位模型，定位缺陷的有效性有所提升，并降低了程序調(diào)試成本，但是神經(jīng)網(wǎng)絡(luò)中各種參數(shù)的設(shè)置會(huì)直接影響其定位效果，一般都由經(jīng)驗(yàn)去人工選擇參數(shù)，不僅費(fèi)時(shí)費(fèi)力，且效率低。

本文將遺傳算法有效的全局隨機(jī)搜索能力、L2正則化防止模型過擬合與深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)復(fù)雜非線性能力結(jié)合起來，提出一種基于GL2-DNN模型的靜態(tài)程序缺陷定位算法。建立GL2-DNN缺陷定位模型，使用遺傳算法自動(dòng)選擇最優(yōu)參數(shù)，將測(cè)試用例集運(yùn)行時(shí)的語句覆蓋信息作為該模型的訓(xùn)練數(shù)據(jù)集，構(gòu)建虛擬測(cè)試集，輸出語句的可疑度值，然后根據(jù)可疑度大小，由大到小排序確定定位，調(diào)試錯(cuò)誤。與Ochiai、Jaccard、Tarantula、RBFN和BPN五種缺陷定位算法的定位效率進(jìn)行比較，結(jié)果表明本文的方法更能有效定位程序缺陷。

1 遺傳算法+L2正則項(xiàng)優(yōu)化深度神經(jīng)網(wǎng)絡(luò)(GL2-DNN)

1.1 DNN的基本結(jié)構(gòu)

神經(jīng)網(wǎng)絡(luò)技術(shù)起初被稱為感知機(jī)(perceptron)，擁有輸入層、一個(gè)隱藏層和輸出層。輸入向量通過隱藏層達(dá)到輸出層，在輸出層得到結(jié)果。但單層感知機(jī)不具備學(xué)習(xí)復(fù)雜非線性關(guān)系的能力，直到二十世紀(jì)八十年代出現(xiàn)多層感知機(jī)(multilayer perceptron)才克服這個(gè)缺點(diǎn)。Hinton等[16]提出了深度神經(jīng)網(wǎng)絡(luò)算法(DNN)，將神經(jīng)網(wǎng)絡(luò)隱藏層層數(shù)加到多層，神經(jīng)網(wǎng)絡(luò)真正意義上有了“深度”。神經(jīng)網(wǎng)絡(luò)基于單層感知機(jī)，而DNN具有更多的隱藏層數(shù)，在處理多維數(shù)據(jù)時(shí)，與單層感知機(jī)相比，具備學(xué)習(xí)復(fù)雜非線性關(guān)系的能力，進(jìn)一步挖掘數(shù)據(jù)特征之間的聯(lián)系以及各特征與結(jié)果之間的聯(lián)系。

圖1 DNN基本結(jié)構(gòu)

1.2 GL2-DNN模型

本文將遺傳算法有效的全局隨機(jī)搜索能力[19]、L2正則化防止模型過擬合與深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)復(fù)雜非線性能力結(jié)合起來，降低DNN中各參數(shù)對(duì)DNN模型性能的影響，提高模型性能，實(shí)現(xiàn)對(duì)模型空間的限制，從而提升模型的泛化能力，避免陷入局部最優(yōu)和收斂速度慢。

圖2 GL2-DNN模型訓(xùn)練流程

GL2-DNN模型訓(xùn)練流程：

(1) 設(shè)置種群數(shù)目和優(yōu)化變量：獲得遺傳初始種群N，即將DNN中的各隱藏層神經(jīng)元數(shù)量nl(0

(2) 通過實(shí)數(shù)編碼的方式給遺傳算法初始種群進(jìn)行編碼，每個(gè)編碼串即每個(gè)染色體包含了設(shè)定的所有優(yōu)化目標(biāo)，其中nl∈[1,300]，η∈[0.000 01,0.05]，epoch∈[1,100]，λ∈[0.000 1,0.5]。

(1)

(4) 由于tournament selection算法不需要對(duì)所有適應(yīng)度值進(jìn)行排序處理，對(duì)比輪盤賭法擁有更小的復(fù)雜度，易并行化處理，因此將其作為選擇算子的選擇策略，選擇當(dāng)前種族群中較好的個(gè)體作為父代，將染色體傳給下一代。

(5) 使用洗牌交叉算法，在交叉之前，利用隨機(jī)排序random.shuffle函數(shù)在父代中進(jìn)行洗牌操作，若產(chǎn)生的隨機(jī)數(shù)小于所給的交叉率大小，則進(jìn)行交叉變換。

(6) 在變異算子中，若產(chǎn)生的隨機(jī)數(shù)小于所給的變異率，則進(jìn)行變異。各隱藏層神經(jīng)元的個(gè)數(shù)nl(0

c.epoch=abs(c.epoch+random.randint(-10,10)

(2)

c.η=abs(c.η+random.uniform(-0.005,0.005)))

(3)

c.λ=abs(c.λ+random.uniform(-0.005,0.005)))

(4)

c.nl=abs(c.nl+random.randint(-20,20)))

(5)

(7) 將經(jīng)過遺傳算法篩選出來的最優(yōu)個(gè)體作為DNN模型各隱藏層神經(jīng)元數(shù)目nl(0

(6)

(7)

(10) 在交叉熵?fù)p失函數(shù)后加上L2正則項(xiàng)，抑制權(quán)重系數(shù)過大，其計(jì)算公式表示為：

(8)

(9)

(12) 將更新后的權(quán)重作為下一輪訓(xùn)練的網(wǎng)絡(luò)連接權(quán)重，返回第(8)步，直到達(dá)到理想狀態(tài)或者達(dá)到設(shè)定的訓(xùn)練周期數(shù)。

2 基于GL2-DNN的缺陷定位算法

2.1 程序缺陷定位問題描述

假設(shè)程序P有m條可執(zhí)行語句，sj為每條可執(zhí)行語句的標(biāo)號(hào)(j∈[1,m])。為P制定n組測(cè)試用例，組成測(cè)試用例集合T，每組測(cè)試用例記為ti,ri為程序P在第i組測(cè)試用例上運(yùn)行后的狀態(tài)值，若實(shí)際輸出值與期望輸出值不符，ri則為1，ti為失敗測(cè)試用例，反之ri則為0，ti為成功測(cè)試用例。C為程序P在測(cè)試用集T上運(yùn)行時(shí)的可執(zhí)行語句覆蓋信息。程序缺陷定位根據(jù)測(cè)試用例在程序上運(yùn)行，收集其覆蓋信息及測(cè)試用例狀態(tài)，然后使用模型分析并進(jìn)行缺陷定位。所以在程序缺陷定位方法中，一組測(cè)試用例應(yīng)該含有輸入、預(yù)期輸出、語句覆蓋信息及狀態(tài)值。

人工智能（Artificial Intelligence）是當(dāng)今時(shí)代最熱門、最搶眼的技術(shù)詞匯，已經(jīng)激起了一場(chǎng)新的技術(shù)革新浪潮。將人工智能技術(shù)結(jié)合到酒店業(yè)，我們可以將酒店系統(tǒng)采集到客戶的所有信息數(shù)據(jù)上傳到云端，在云端大數(shù)據(jù)分析工具 （大數(shù)據(jù)分析技術(shù)可以快速對(duì)大量的數(shù)據(jù)進(jìn)行相關(guān)性分析）的幫助下對(duì)采集的客人信息結(jié)合歷史數(shù)據(jù)進(jìn)行精準(zhǔn)分析和畫像[13]。

2.2 基于GL2-DNN的缺陷定位算法流程

假設(shè)存在一個(gè)錯(cuò)誤但能正常運(yùn)行的程序P，該程序有8條可執(zhí)行語句，其中S={s1,s2,s3,s4,s5,s6,s7,s8}，s1為缺陷語句。針對(duì)程序P的測(cè)試用例集T={t1,t2,t3,t4,t5,t6,t7,t8}，以及各組測(cè)試用例的語句覆蓋信息和狀態(tài)，如表1所示。

表1 程序?qū)嵗齈及其覆蓋信息

續(xù)表1

如圖3所示，基于GL2-DNN的缺陷定位算法流程如下：

圖3 GL2-DNN缺陷定位算法流程

(1) 把源程序在測(cè)試用例集上運(yùn)行，獲取每個(gè)測(cè)試用例的語句覆蓋信息及狀態(tài)值，集合成信息表，作為GL2-DNN缺陷定位模型的訓(xùn)練數(shù)據(jù)集。例如，在表1中t1的語句覆蓋信息為c11=(1,1,0,1,0,1,1,1)，狀態(tài)值r1=0。

(2) 建立GL2-DNN缺陷定位模型。模型隱藏層層數(shù)經(jīng)實(shí)驗(yàn)對(duì)比后確定，輸入層神經(jīng)元的個(gè)數(shù)等于源程序的可執(zhí)行語句數(shù)，將測(cè)試用例的語句覆蓋信息Ci=(ci1,ci2,…,cim)作為模型輸入，狀態(tài)值ri當(dāng)作對(duì)比標(biāo)簽，來計(jì)算權(quán)重誤差。以表1為實(shí)例，有8組輸入數(shù)據(jù)，每組輸入數(shù)據(jù)中包含了8個(gè)特征值，即8個(gè)輸入神經(jīng)元，每組輸入數(shù)據(jù)有其相應(yīng)的對(duì)比標(biāo)簽，如第一組輸入數(shù)據(jù)為c1=(1,1,0,1,0,1,1,1)，其對(duì)比標(biāo)簽為r1=0。

(3) 訓(xùn)練GL2-DNN缺陷定位模型。通過迭代訓(xùn)練，直到達(dá)到迭代滿足結(jié)束訓(xùn)練條件為止。GL2-DNN缺陷定位模型訓(xùn)練過程如圖4所示。

圖4 GL2-DNN缺陷定位模型訓(xùn)練

(4) 模型訓(xùn)練完成后，設(shè)計(jì)一組虛擬測(cè)試用例，虛擬測(cè)試用例個(gè)數(shù)與源程序的可執(zhí)行語句數(shù)相等，且每個(gè)虛擬測(cè)試用例依次僅覆蓋一條語句，即為m×m的單位矩陣[20]，如式(10)所示。

(10)

(5) 將虛擬測(cè)試用例數(shù)據(jù)作為已訓(xùn)練好的模型的輸入，依次輸出每個(gè)虛擬測(cè)試用例的預(yù)測(cè)結(jié)果fi(i∈[1,m])。將預(yù)測(cè)結(jié)果fi視為對(duì)應(yīng)可執(zhí)行語句的出錯(cuò)可疑度,如f1為源程序中s1的出錯(cuò)可疑度值。表1程序?qū)嵗齈的模型輸出結(jié)果如表2所示。

表2 程序?qū)嵗齈模型輸出結(jié)果

(6) 將預(yù)測(cè)結(jié)果f1,f2,…,fm進(jìn)行降序排列，測(cè)試人員從高往低進(jìn)行缺陷語句定位，若可疑度越高，則該語句越優(yōu)先被檢查。例如根據(jù)表2，將程序?qū)嵗齈的可執(zhí)行語句進(jìn)行排序，則為s1s5s8s3s4s2s7s6，缺陷語句s1可疑度值最大，則測(cè)試人員可以優(yōu)先檢測(cè)s1，進(jìn)行調(diào)試修改，從而提高定位效率，降低時(shí)間成本。

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

使用測(cè)試數(shù)據(jù)集Siemens Suite[21]作為本文實(shí)驗(yàn)的研究對(duì)象，該數(shù)據(jù)集可從Software-artifact Infrastructure Repository(SIR)獲得。Siemens Suite是由西門子公司發(fā)布并常用于程序缺陷定位領(lǐng)域研究的測(cè)試套件[22]，其中包含了七個(gè)中小型程序，每個(gè)子程序中包含了其正確版本、相應(yīng)的若干錯(cuò)誤版本及若干的測(cè)試用例，如表3所示。

表3 Siemens Suite

大多數(shù)的錯(cuò)誤版本的錯(cuò)誤存在于單行代碼中，少數(shù)錯(cuò)誤版本中的錯(cuò)誤會(huì)跨越多行，如tcas程序中的錯(cuò)誤版本v31、v32和v33。Siemens Suite數(shù)據(jù)集中共有132個(gè)錯(cuò)誤版本，在本文實(shí)驗(yàn)中只應(yīng)用了120個(gè)錯(cuò)誤版本，排除掉了12個(gè)錯(cuò)誤版本：(1) 沒有失敗測(cè)試用例：replace程序v32、schedule2程序v9；(2) 頭文件包含錯(cuò)誤，主程序文件不包含：print_tokens程序v4、v6，tcas程序的v13、v14、v36、v38，tot_info程序v6、v10、v19、v21。

實(shí)驗(yàn)主要包括四個(gè)階段：第一個(gè)階段是數(shù)據(jù)預(yù)處理，主要是信息采集、程序特征提取、正確版本與錯(cuò)誤版本對(duì)比獲取狀態(tài)值，整合數(shù)據(jù)；第二個(gè)階段將第一階段整合的數(shù)據(jù)作為GL2-DNN模型的輸入與對(duì)比標(biāo)簽，訓(xùn)練模型，經(jīng)過多次實(shí)驗(yàn)對(duì)比，GL2-DNN模型的隱藏層數(shù)為5時(shí)，定位效果最好；第三階段將虛擬測(cè)試用例集作為已確定最佳層數(shù)并已訓(xùn)練好的GL2-DNN模型的輸入，進(jìn)行語句可疑度預(yù)測(cè)，輸出語句可疑度值；第四階段是根據(jù)訓(xùn)練好的GL2-DNN模型輸出的預(yù)測(cè)值對(duì)可疑語句進(jìn)行降序排列、定位缺陷語句并計(jì)算定位效率等。為了驗(yàn)證GL2-DNN程序缺陷定位模型的良好性能，選取了文獻(xiàn)[14，23]中Ochiai、Jaccard、Tarantula、RBFN、BPN等程序缺陷定位方法與之進(jìn)行定位效率比較。

本文采用與文獻(xiàn)[23]類似的評(píng)估指標(biāo)，即以代碼檢查率ρ作為程序缺陷定位方法有效性的評(píng)估指標(biāo)，公式為：

(11)

式中：ρ表示在找到缺陷語句之前所需要查找語句的比例，ρ越小，代表定位效率越高；F表示源程序中可執(zhí)行語句總數(shù)；f表示找到程序缺陷需要檢查的語句數(shù)目，即缺陷語句的可疑度排名。當(dāng)ρ相同，即在查找相同語句數(shù)量的情況下，能定位的錯(cuò)誤版本數(shù)越多，則代表程序缺陷定位算法越有效，定位效率越高。圖5比較了GL2-DNN、Ochiai、Jaccard、Tarantula、RBFN和BPN六種缺陷定位算法在同一代碼檢查率的情況下，已定位的錯(cuò)誤版本比例，x軸表示代碼檢查率，y軸表示已定位了的錯(cuò)誤版本數(shù)占總錯(cuò)誤版本數(shù)的比例。

圖5 六種程序缺陷定位算法代碼檢查率比較

可以看出，代碼檢查率在[0,0.1]區(qū)間上時(shí)，GL2-DNN的定位錯(cuò)誤版本比例為0.24，略高于Ochiai、Jaccard、RBFN和BPN，但在(0.1，0.2)區(qū)間上時(shí)，RBFN的定位錯(cuò)誤版本比例高于GL2-DNN，如在代碼檢查率為0.15時(shí)，RBFN的定位錯(cuò)誤版本比例為0.58，GL2-DNN為0.43。除此之后，GL2-DNN的定位錯(cuò)誤版本比例均高于Ochiai、Jaccard、Tarantula、RBFN和BPN，且在代碼檢查率為0.75時(shí)，已定位錯(cuò)誤版本比例接近100%，代表使用GL2-DNN算法定位缺陷時(shí)，只需查找75%的語句，便可找出所有錯(cuò)誤版本的缺陷語句，而Ochiai、Jaccard、Tarantula、RBFN和BPN則需要查找90%及以上。由此可看出在整體區(qū)間上的實(shí)驗(yàn)結(jié)果GL2-DNN算法定位程序缺陷比其他算法更有效。

代碼檢查率是從整體去比較算法的定位效率，為了進(jìn)一步驗(yàn)證GL2-DNN缺陷定位算法的有效性，還需進(jìn)一步進(jìn)行細(xì)節(jié)比較，則引入標(biāo)準(zhǔn)Imp百分比[14]，表示在已定位到單個(gè)程序所有錯(cuò)誤版本的錯(cuò)誤情況下，已查找的可執(zhí)行語句總和占所有錯(cuò)誤版本可執(zhí)行語句總和的百分比，也可理解為在單個(gè)程序集上的平均代碼檢查率的平均值。Imp百分比越小，則定位效率越高，時(shí)間成本越低。在測(cè)試數(shù)據(jù)集Siemens Suite上分別使用六種程序缺陷定位算法的Imp百分比如圖6所示，可看出，在print_tokens2程序中，定位效率最好的是Ochiai算法，Imp百分比為20.3%，略高于GL2-DNN算法。但在print_tokens、schedule、schedule2、replace、tcas、tot_info程序中，GL2-DNN算法的Imp百分比均低于其他六種算法，尤其在schedule2程序中，GL2-DNN算法定位效率表現(xiàn)最好，Imp百分比遠(yuǎn)遠(yuǎn)低于其他六種算法，其平均差為29.48%。因此，從圖6整體可看出，在單個(gè)子程序集中，GL2-DNN缺陷定位算法雖然在單個(gè)程序中的缺陷定位效率不是最優(yōu)，但是在多數(shù)子程序中表現(xiàn)最優(yōu)。

圖6 六種程序缺陷定位算法Imp值比較

經(jīng)以上實(shí)驗(yàn)對(duì)比結(jié)果可知，GL2-DNN缺陷定位算法可以有效地減少代碼檢查率，便能定位到缺陷，提高了定位精確度，且比其他算法更穩(wěn)定，沒有出現(xiàn)較大極差。

4 結(jié) 語

本文將遺傳算法、L2正則化與深度神經(jīng)網(wǎng)絡(luò)相結(jié)合，提出一種基于GL2-DNN的靜態(tài)程序缺陷定位算法,相較于現(xiàn)有的基于神經(jīng)網(wǎng)絡(luò)程序缺陷定位算法來說，可以自主選擇最優(yōu)參數(shù)，提高定位準(zhǔn)確度，降低時(shí)間成本。雖然對(duì)于復(fù)雜程序問題而言，其時(shí)間復(fù)雜度上升，但提高了精確度，且該模型對(duì)特征工程要求相對(duì)較低，優(yōu)化過程獨(dú)立于預(yù)測(cè)過程，一旦獲取最優(yōu)超參數(shù)，便可縮短模型的訓(xùn)練和預(yù)測(cè)時(shí)間。

實(shí)驗(yàn)表明，該算法與Ochiai、Jaccard、Tarantula、RBFN和BPN五種缺陷定位算法相比較，定位效率與準(zhǔn)確率均有所提升，且代碼檢查率降低了約15百分點(diǎn)。

雖然該算法的實(shí)驗(yàn)結(jié)果良好，但仍然存在不足：(1) 由于本文著重考慮消除相似測(cè)試用例對(duì)于定位結(jié)果的影響，所以對(duì)于程序語句和變量的依賴性對(duì)其定位結(jié)果產(chǎn)生的影響考慮不足；(2) 數(shù)據(jù)集Siemens Suite大多為單一缺陷，所以本文在多錯(cuò)誤互相之間的關(guān)系上考慮不足，現(xiàn)實(shí)中的程序缺陷并不單一且關(guān)系復(fù)雜；(3) 未考慮測(cè)試用例的優(yōu)化選取，未驗(yàn)證測(cè)試用例的選取對(duì)定位效率的影響；(4) 以測(cè)試數(shù)據(jù)集Siemens Suite實(shí)驗(yàn)樣本，未在其他平臺(tái)進(jìn)行實(shí)驗(yàn)，未驗(yàn)證其跨平臺(tái)性。

未來將針對(duì)該算法的不足進(jìn)行進(jìn)一步研究。主要有幾個(gè)方面：將研究焦點(diǎn)定位于多缺陷定位，滿足多故障程序定位的需求；進(jìn)行測(cè)試用例優(yōu)化，以提高缺陷定位效率；選擇更大的程序集進(jìn)行實(shí)驗(yàn)，擴(kuò)展缺陷種類。