基于隨機森林算法的函數(shù)缺陷定位

李倩倩, 牟永敏*, 趙曉永

(1.北京信息科技大學網絡文化與數(shù)字傳播北京市重點實驗室, 北京 100101； 2.北京信息科技大學信息管理學院, 北京 100192)

軟件軟件缺陷定位[1](software fault location)是指當軟件發(fā)生失效時,程序人員通過分析源碼找到引發(fā)該失效的缺陷代碼的行為。研究表明,軟件的發(fā)展和維護的過程中,軟件調試則占整個過程中的50%～80%[2],缺陷定位則是整個調試過程中成本較高的重要階段。傳統(tǒng)的缺陷定位通常由開發(fā)人員通過運行失敗的測試用例并手動設置斷點的方式尋找程序中缺陷的位置,然而這種方式未能夠充分利用測試用例執(zhí)行行為和執(zhí)行結果的信息[3]。

近些年來,研究人員從不同的角度進行深入的研究并取得了階段性的進展。Wang等[4]則通過識別關鍵謂詞來定位出錯誤的位置,然而此種方法需要大量的測試用例；為了降低程序之間的依賴關系對于缺陷定位的影響,借助于基于程序切片的缺陷定位方法(program slicing based fault localization,PSFL),Zhang等[5]提出了3種動態(tài)切片技術：全預處理、無預處理和有限預處理,同時其針對Java程序設計出了一種動態(tài)切片工具Jslice；基于模型診斷的方法[6-7](model-based diagnosis,MBD)通過構建合適的程序模型同時使用邏輯推導的方式推理出故障的位置,由Abreu等[8]提出了基于程序頻譜的缺陷定位技術(program spectrum based fault localization, SFL),則采用的是分析成功測試用例和失敗測試用例在語句和語句塊上的覆蓋信息,這是目前一種比較主流的動態(tài)定位方法,在傳統(tǒng)的SFL算法中,Wong等[9]通過修改Kulczynski系數(shù)提出了一種基于相似系數(shù)的DStar懷疑率計算公式；黃晴雁等[10]通過分析執(zhí)行信息與執(zhí)行結果之間的關系,提出了基于條件概率的缺陷定位方法CPStar,取得了良好的定位效果；考慮到SFL技術沒有充分解析代碼之間的依賴關系,文萬志等[11]在缺陷定位中引入程序切片和統(tǒng)計學方法,隨后又提出了層次切片譜,將不同的層次間的依賴關系應用與缺陷定位中,曹鶴齡等[12]則將動態(tài)切片和關聯(lián)分析相結合,構建混合頻譜矩陣,這兩種方法使得定位的精度得到了提升,然而該過程相較于SFL算法來說中消耗了大量的時間和空間資源;宗芳芳等[13]則采用分而治之的思想,將MBD和SFL算法相結合,分別定位出函數(shù)級別和語句級別的缺陷,然而該方法的模型構建和定位方式過于復雜,在實際的應用場景中仍然有所欠缺。通過分析近些年來諸多學者的改進方法,本文提出一種基于隨機森林算法的函數(shù)缺陷定位策略,通過使用機器學習算法,將該缺陷定位問題轉化為分類問題,同時以各個屬性在模型中的貢獻度作為為函數(shù)缺陷的概率估計,實驗證明,在缺陷定位到函數(shù)方面,準確度有了顯著提高。

1 準備工作

針對缺陷程序,動態(tài)的傳入多個測試用例從而獲得各個測試用例在執(zhí)行過程中的函數(shù)調用信息,將函數(shù)的執(zhí)行信息進行統(tǒng)計作為數(shù)據(jù)集的特征,執(zhí)行結果作為label,運用隨機森林算法計算出各個函數(shù)的可疑度,同時生成可疑函數(shù)候選集并進行檢測。

函數(shù)的調用序列是指程序在特定的輸入下函數(shù)之間調用關系的全信息[14],主要提取的為函數(shù)間的調用關系以及函數(shù)之間的調用次數(shù)。

定義1成功測試用例集與失敗測試用例集。假設：

T={t1,t2,…,tn}

(1)

為待測程序P的測試套件,總共有n個測試用例。對于每一個測試用例:

tj=(Ij,Oj)

(2)

(3)

失敗測試用例Tf可以表示為

(4)

測試用例的執(zhí)行結果用單位向量e表示,當tj∈Tp時,ej=0;否則當tj∈Tf時,ej=1。

定義2函數(shù)調用序列。假設程序P中的函數(shù)為M={F1,F2，…，F(xiàn)m},則程序P在測試集tj上的動態(tài)函數(shù)調用序S(P,tj)為

S(P,tj)={|Fs,Fe∈M,n∈N*}

(5)

式(5)中：Fs代表調用函數(shù)；Fe表示被調用函數(shù)；n表示該序列的調用次數(shù)。

定義3二元組。將函數(shù)調用圖G抽象定位為一個二元組(V,E),其中V是頂點的組合,即為各個函數(shù)的名稱的集合,E為邊的集合,表示函數(shù)之間的調用關系,用有序數(shù)組對(x,y)表示。

定義4鄰接表。對圖G中的每個定點建立一個鄰接關系單鏈表,第i個單鏈表中的節(jié)點表示以Vi為起點的弧。即所有從頂點Vi出發(fā)的邊所指向的節(jié)點均在該條單鏈表中,從而可找到任意節(jié)點出度和入度信息。

通過對于函數(shù)調用信息進行提取從而獲得需要的特征,即各個函數(shù)的出度入度信息,并將該數(shù)值進行線性變換,從而形成矩陣A,其中aij表示第i個測試用例在第j個函數(shù)上的覆蓋情況,所以(A,e)則是需要分析的初始數(shù)據(jù)集。

2 算法設計

在實際的生產環(huán)境中,由于缺陷函數(shù)在程序的比重較輕,由此導致測試用例在執(zhí)行時正負樣本不均衡,在進行模型訓練時會導致結果更多的偏向正樣本。采用合成少數(shù)類過采樣技術[15](synthetic minority over-sampling technique,SMOTE)獲取來保證樣本的正負樣本達到最佳比例,而后采用隨機森林算法進行分類模型的訓練并計算出特征重要性從而獲得各個函數(shù)缺陷可疑度的排序。

2.1 SMOTE算法

針對不平衡數(shù)據(jù)集的處理通常包含代價敏感方法和采樣方法[16]。然而代價敏感方法中的錯誤代價難以精確的估計。采樣方法分為欠采樣和過采樣兩種,其中欠采樣方法通過刪除部分多樣本數(shù)據(jù)來使得數(shù)據(jù)達到平衡,這種方式從而導致樣本的數(shù)據(jù)的丟失,所以選擇過采樣SMOTE方法。

SMOTE算法的主要思想是對少數(shù)類別樣本進行分析,根據(jù)少數(shù)類別樣本人工合成新樣本添加到數(shù)據(jù)集中,具體流程如下：對于少數(shù)類樣本中的每一個x,即(A,e)中的失敗測試用例,以歐式距離為標準計算其到少數(shù)樣本集Smin中所有樣本的距離,得到其k近鄰；根據(jù)樣本不平衡比例設置一個采樣比例確定采樣倍率N,對每一個少數(shù)類樣本x從其k近鄰中隨機選擇若干個樣本xn,則新樣本為

xnew=x+rand(0,1)*|x-xn|

(6)

圖1所示為使用SMOTE算法生成數(shù)據(jù)的效果。

圖1 數(shù)據(jù)集前后對比

圖2 RF算法流程

2.2 隨機森林算法

由于不平衡的數(shù)據(jù)經過過采樣變?yōu)槠胶鈹?shù)據(jù)后,容易出先過擬合的現(xiàn)象,同時單個分類器存在性能提升的瓶頸問題,所以選擇集成學習(ensemble learning)[17]來提高模型準確率和泛化的能力。隨機森林算法[18]是一種基于決策樹(decision tree, DF)的集成學習方法,解決了決策樹的性能瓶頸問題,對于噪聲和異常值有較好的容忍性。決策樹的構造算法是分類與回歸樹(classification and regression tree,CART)。由函數(shù)的覆蓋情況與程序的執(zhí)行情況構成了初始數(shù)據(jù)集,由此將缺陷定位問題轉化為了一個二分類問題。具體的算法流程如圖2所示。

特征重要性反應了其對于預測結果的影響程度,由于研究問題屬于一個二分類問題,所以特征重要性直接反映了其對于label屬性的貢獻程度——函數(shù)存在缺陷的可能性,本文的數(shù)據(jù)集屬性為各個函數(shù)的調用與被調用信息,由此屬性的特征重要性轉化為該函數(shù)為缺陷程序的概率。

采用基于袋外數(shù)據(jù)的分類準確度來衡量每個屬性的特征重要性[19]。

該算法具體步驟如下。

算法1：FDLRF算法

輸入：覆蓋矩陣(A,e)

輸出：各個屬性的特征重要性L(函數(shù)可疑序列)

(*少數(shù)類樣本T,使用SMOTE算法生成樣本數(shù)量N%,鄰居數(shù)目k*)

步驟1 將樣本進行賦值y←e,X←A,同時獲得重新采用的樣本X_smo,y_smo ← SMOTE(T,N,K),

步驟3 fori=1,2,…,L

步驟3.1:從每個樣本的特征維度M中選擇m個特征子集,調用算法2,每次樹進行分裂時,從m個特征中選擇最優(yōu),構建一棵決策樹Ti

End for

步驟4 用L棵決策樹對測試集X進行預測,得到

T1(X),T2(X),…，TL(X),以投票方式得到樣本的類別標簽

步驟5 統(tǒng)計計算出每個特征的特征貢獻度

(7)

算法2：Decision Tree 生成算法

輸入：覆蓋矩陣(A,e)

屬性集M={m1,m2,m3，…，md}

輸出：一棵決策樹T

步驟1 將上步中獲得數(shù)據(jù)作為訓練數(shù)據(jù)集D,計算現(xiàn)有特征的基尼指數(shù),對每一個特征M的可能取值mi計算其在“1”,“0”下分割為D1、D2下的基尼指數(shù)

步驟2 根據(jù)特征B以及其所有可能切分點,計算出最優(yōu)特征及最優(yōu)切分點,由此生成兩個子節(jié)點,將訓練數(shù)據(jù)集進行分配

步驟3 重復算法1、算法2的步驟,直至滿足停止條件為止

(*停止條件是節(jié)點中的樣本個數(shù)少于預定閾值,或者樣本集中的基尼系數(shù)小于預定閾值,或者沒有更多特征)

步驟4 生成決策樹T

3 實驗分析

3.1 實驗數(shù)據(jù)集

使用經典的Siemens數(shù)據(jù)集進行實驗,該數(shù)據(jù)集下載地址為SIR,表1為其信息的具體介紹,包括實驗對象名稱、功能描述、代碼行數(shù)、每個對象的錯誤版本數(shù),以及測試用例的個數(shù)。實驗以函數(shù)數(shù)量,代碼行數(shù)最多的replace數(shù)據(jù)集為例進行論證。

通過動態(tài)運行測試用例對程序進行追蹤,動態(tài)獲取函數(shù)的調用序列主要使用的C語言的代碼追蹤工具pvtrace[14],該工具依賴于gcc編譯器的hook機制,在函數(shù)的入口和出口打上“標簽”從而獲取“調用者”函數(shù)符號地址信息并保存到文件中,然后通過addr2line根據(jù)給定的地址從可執(zhí)行文件中找出對應的“函數(shù)名”最后生成dot文件,使用graphviz展示某一測試用例執(zhí)行缺陷程序時函數(shù)調用情況，如圖3所示。

表1 西門子數(shù)據(jù)集信息

圖3 函數(shù)調用圖

通過分析函數(shù)在測試用例執(zhí)行過程中的動態(tài)信息,以各個函數(shù)名作為特征屬性,各個方法的出入度信息作為屬性值,由此獲得待分析的數(shù)據(jù)集部分情況，如表2所示。

表2 數(shù)據(jù)集信息

3.2 模型參數(shù)

由于不平衡樣本學下旨在提高少數(shù)類樣本的分類性能,選擇集成學習算法——隨機森林進行訓練,評價指標選擇在評價不平衡數(shù)據(jù)集中專用指標G-mean,其定義如下：

(8)

式(8)中：FN(false negative)表示被判定為負樣本,事實上為正樣本；FP(false positive)表示被判定為正樣本,事實為負樣本；TN(true negative)被判定為負樣本,事實上也是負樣本；TP(true positive)被判定為正樣本,事實上也是證樣本。

通過對SMOTE算法進行網格搜索,對采樣比例進行測試,指定近鄰的個數(shù)k_neighbors為5[15],隨機子空間設置為10[20],在不同的比率下進行采樣,由此獲得最佳的采樣比率為1∶8,即生成失敗測試用例：成功測試用例=1∶8的數(shù)據(jù)集,如圖4所示。

圖4 不同過采樣比例模型得分

RF算法中決策樹的N_tree取值范圍{50,100,200,500,1 000,1 500,2 000}[21]為獲得分類器和過采樣器的最佳效果,利用網格搜索的方式對RF進行調參,使用十次十折交叉驗證的平均值作為最終性能度量結果,最終確定迭代次數(shù)為1 500次,CART樹劃分時的標準使用基尼指數(shù),RF劃分時最大的特征數(shù)為log2N，其中N表示該數(shù)據(jù)集的總特征數(shù),使用袋外數(shù)據(jù)作為測試數(shù)據(jù)集,由此獲得各個函數(shù)的特征重要性值,并對同名函數(shù)出入度信息做累加處理,即為該函數(shù)存在缺陷概率。

3.3 實驗結果分析

由于本次實驗的定位粒度為函數(shù)級別,所以本次的對比實驗選擇的是同樣以函數(shù)為粒度進行缺陷定位的經典算法Combine、Upper[22],近年來宗芳芳等[13]提出的基于程序頻譜和模型診斷的二次定位(double-times-locating,DTL)表現(xiàn)良好,所以將其在函數(shù)粒度上的定位也作為對比實驗,同時對比自身算法不使用SMOTE算法(NO-SMOTE)的效果。

采用EXAM指標,即定位出缺陷函數(shù)需要檢查的函數(shù)占總函數(shù)的百分比,作為本次實驗的評價標準,實驗結果如表3所示。

表3中顯示了replace數(shù)據(jù)集中的31個缺陷版本的程序,通過將Combine、Upper、DTL,以及不使用SMOTE算法的FDLRE與本文算法進行對比,可以發(fā)現(xiàn)在29個版本(2個版本均未檢測出)中均優(yōu)于其他算法的工13個(灰色單元格),其中本文方法可一次定位到缺陷函數(shù)的個數(shù)為11個,占全部缺陷函數(shù)的38%；FDLRF優(yōu)于Combine的共17個版本,優(yōu)于Upper的共18個版本,優(yōu)于DTL的共15個版本,優(yōu)于NO-SMOTE的共20個版本。

對于版本中V12出現(xiàn)原因是,該錯誤并未出現(xiàn)在函數(shù)中,而是在全局變量的聲明里,由此導致無法準確定位出缺陷的位置,版本V32出現(xiàn)的原因是該函數(shù)并未有故障的測試用例經過,從而無法精準定位。

對表3中的數(shù)據(jù)進行可視化處理,生成圖5,同時對數(shù)據(jù)進行統(tǒng)計分析生成表4。在圖5、表4中可以看出，除了所提出的FDLRF算法外,其他算法均出現(xiàn)了離群點,所有算法的EXAM最優(yōu)值均為0.047 62,而在最劣值中Upper算法和FDLRF+SMOTE算法表現(xiàn)良好,在平均數(shù)和方差上,Upper算法優(yōu)于其他3種算法。

表3 定位到缺陷函數(shù)占總函數(shù)的比值

圖5 缺陷定位結果比較

表4 統(tǒng)計結果對比

為了證明實驗的有效性,統(tǒng)計每一種方法的平均有效值,將實驗對象進行擴展,驗證西門套件中的其他6個數(shù)據(jù)集,以實驗的平均結果作為展示，如圖6所示。由圖6可以看出，F(xiàn)DLRF算法呈現(xiàn)出來最快的收斂速度,Upper算法次之,同時,本文方法在檢測10%的代碼可以定位出50%的缺陷,檢測40%代碼可以定位出大約90%的故障。同時可以發(fā)現(xiàn),在未使用SMOTE算法時,算法的收斂速度較慢,其原因可能是正負樣本不均衡,導致實驗結果偏向于正向樣本導致。通過以上角度的對比分析表明,本文方法有較好的表現(xiàn)與實用價值。

圖6 不同方法有效值對比

4 結論

提出了基于隨機森林算法的函數(shù)缺陷定位方法FDLRF,通過動態(tài)收集函數(shù)的調用信息,建立特征矩陣。將缺陷檢測問題轉化為分類問題,利用SMOTE算法對數(shù)據(jù)進行重采樣從而獲得均衡數(shù)據(jù),從而使用隨機森林算法對數(shù)據(jù)進行分類預測,以基尼指數(shù)作為計算特征重要性的標準,即每個屬性對于label屬性的貢獻度,將該標準作為每個函數(shù)出現(xiàn)缺陷的概率從而獲得函數(shù)缺陷可疑序列。通過在以EXAM作為評價標準,同時在第3節(jié)4個方面進行對比,展示了FDLRF算法的良好表現(xiàn)。

雖然經過研究表明本文算法有較好的定位效果,但該算法統(tǒng)計函數(shù)的調用的全信息,所以對于測試用例有較高的依賴性,失敗測試用例覆蓋信息較少,使得數(shù)據(jù)在進行分類預測結果具有傾向性,如何保證實驗樣本均衡同時涵蓋更多的失敗測試用例信息尤為重要；其次實驗建立在測試用例均為正確的基礎之上,這無形之中增加了局限性；最后Siemens程序包是序列化程序,在并發(fā)性程序的檢測上可能面臨更多的問題。