基于GL2-DNN的面向語句覆蓋的程序缺陷定位方法

彭 玲 劉振宇 彭 敏

(南華大學計算機學院 湖南 衡陽 421000)

0 引 言

隨著互聯網和計算機行業的飛速發展，程序的規模也隨之擴大，愈加復雜，保證程序的安全性已經成為提高程序質量極其重要的因素之一。但是，在程序的開發與維護中常常會出現人為或邏輯的錯誤，從而導致出現程序失效的概率提高[1-2]。所以程序調試與整個程序開發周期并行進行，在程序開發和維護中極其重要，而程序缺陷定位又是其最重要和最耗時的工作之一。因此，準確定位缺陷位置，能有效地減少開發過程中的錯誤，提高程序的高可靠性和降低維護成本。

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

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

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

1 遺傳算法+L2正則項優化深度神經網絡(GL2-DNN)

1.1 DNN的基本結構

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

圖1 DNN基本結構

1.2 GL2-DNN模型

本文將遺傳算法有效的全局隨機搜索能力[19]、L2正則化防止模型過擬合與深度神經網絡學習復雜非線性能力結合起來，降低DNN中各參數對DNN模型性能的影響，提高模型性能，實現對模型空間的限制，從而提升模型的泛化能力，避免陷入局部最優和收斂速度慢。

圖2 GL2-DNN模型訓練流程

GL2-DNN模型訓練流程：

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

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

(1)

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

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

(6) 在變異算子中，若產生的隨機數小于所給的變異率，則進行變異。各隱藏層神經元的個數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) 將經過遺傳算法篩選出來的最優個體作為DNN模型各隱藏層神經元數目nl(0

(6)

(7)

(10) 在交叉熵損失函數后加上L2正則項，抑制權重系數過大，其計算公式表示為：

(8)

(9)

(12) 將更新后的權重作為下一輪訓練的網絡連接權重，返回第(8)步，直到達到理想狀態或者達到設定的訓練周期數。

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

2.1 程序缺陷定位問題描述

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

人工智能（Artificial Intelligence）是當今時代最熱門、最搶眼的技術詞匯，已經激起了一場新的技術革新浪潮。將人工智能技術結合到酒店業，我們可以將酒店系統采集到客戶的所有信息數據上傳到云端，在云端大數據分析工具 （大數據分析技術可以快速對大量的數據進行相關性分析）的幫助下對采集的客人信息結合歷史數據進行精準分析和畫像[13]。

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

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

表1 程序實例P及其覆蓋信息

續表1

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

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

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

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

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

圖4 GL2-DNN缺陷定位模型訓練

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

(10)

(5) 將虛擬測試用例數據作為已訓練好的模型的輸入，依次輸出每個虛擬測試用例的預測結果fi(i∈[1,m])。將預測結果fi視為對應可執行語句的出錯可疑度,如f1為源程序中s1的出錯可疑度值。表1程序實例P的模型輸出結果如表2所示。

表2 程序實例P模型輸出結果

(6) 將預測結果f1,f2,…,fm進行降序排列，測試人員從高往低進行缺陷語句定位，若可疑度越高，則該語句越優先被檢查。例如根據表2，將程序實例P的可執行語句進行排序，則為s1s5s8s3s4s2s7s6，缺陷語句s1可疑度值最大，則測試人員可以優先檢測s1，進行調試修改，從而提高定位效率，降低時間成本。

3 實驗與結果分析

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

表3 Siemens Suite

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

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

本文采用與文獻[23]類似的評估指標，即以代碼檢查率ρ作為程序缺陷定位方法有效性的評估指標，公式為：

(11)

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

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

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

代碼檢查率是從整體去比較算法的定位效率，為了進一步驗證GL2-DNN缺陷定位算法的有效性，還需進一步進行細節比較，則引入標準Imp百分比[14]，表示在已定位到單個程序所有錯誤版本的錯誤情況下，已查找的可執行語句總和占所有錯誤版本可執行語句總和的百分比，也可理解為在單個程序集上的平均代碼檢查率的平均值。Imp百分比越小，則定位效率越高，時間成本越低。在測試數據集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算法定位效率表現最好，Imp百分比遠遠低于其他六種算法，其平均差為29.48%。因此，從圖6整體可看出，在單個子程序集中，GL2-DNN缺陷定位算法雖然在單個程序中的缺陷定位效率不是最優，但是在多數子程序中表現最優。

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

經以上實驗對比結果可知，GL2-DNN缺陷定位算法可以有效地減少代碼檢查率，便能定位到缺陷，提高了定位精確度，且比其他算法更穩定，沒有出現較大極差。

4 結 語

本文將遺傳算法、L2正則化與深度神經網絡相結合，提出一種基于GL2-DNN的靜態程序缺陷定位算法,相較于現有的基于神經網絡程序缺陷定位算法來說，可以自主選擇最優參數，提高定位準確度，降低時間成本。雖然對于復雜程序問題而言，其時間復雜度上升，但提高了精確度，且該模型對特征工程要求相對較低，優化過程獨立于預測過程，一旦獲取最優超參數，便可縮短模型的訓練和預測時間。

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

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

未來將針對該算法的不足進行進一步研究。主要有幾個方面：將研究焦點定位于多缺陷定位，滿足多故障程序定位的需求；進行測試用例優化，以提高缺陷定位效率；選擇更大的程序集進行實驗，擴展缺陷種類。