基于重子節點抽象語法樹的軟件缺陷預測

黃曉偉，范貴生，虞慧群，楊星光

（1.華東理工大學 計算機科學與工程系，上海 200237；2.上海市計算機軟件測評重點實驗室，上海 201112）

0 概述

在軟件項目開發過程中，軟件項目的最終可靠性是所有開發人員以及項目負責人都十分關注的。軟件缺陷是影響軟件項目可靠性的重要因素，一般通過減少軟件缺陷的引入以及修正已經存在的缺陷兩種方法來減少軟件缺陷。軟件項目的開發人員和測試人員通過構建軟件缺陷模式［1］，能夠利用積累的軟件缺陷數據提高軟件項目的可靠性。

軟件缺陷預測（Software Defect Prediction，SDP）［2-3］利用軟件開發過程存儲的歷史數據和測試人員對發現缺陷模塊的標注，通過構建機器學習分類器對新開發的軟件模塊進行分類預測，判斷該模塊是否存在缺陷。根據源數據項目與目標數據項目的差異，軟件缺陷預測可以進一步劃分為項目內缺陷預測（Within-Project Defect Prediction，WPDP）［4-5］、跨項目缺陷預測（Cross-Project Defect Prediction，CPDP）［4，6］、異構缺陷預測（Heterogeneous Defect Prediction，HDP）［7-8］。根據預測程序規模，程序包括函數級、文本級、變更級等預測粒度。

傳統缺陷預測方法根據項目源代碼的行數、復雜度、耦合度等提取描述源代碼的指標，利用構建的機器學習分類模型進行分類學習。但是，這些靜態代碼指標［9-10］只是代碼的宏觀描述，有缺陷代碼和無缺陷代碼很可能具有相同的代碼指標，使分類器無法區分。這些宏觀上無法區分的代碼，具有不同語義和結構信息，因此利用項目代碼的語義和結構信息能夠提高缺陷預測性能。抽象語法樹（Abstract Syntax Tree，AST）是以樹狀的形式表現編程語言的語法結構，樹上的每個節點都表示源代碼中的一種結構。目前，研究人員提出的基于AST 的DP-CNN［11］和DP-ARNN［12］方法僅使用了部分源代碼的語義和結構信息。

為利用AST 中的更多信息，本文提出一種基于重子（Heavy Son，HS）節點抽象語法樹的軟件缺陷預測方法HSAST。將程序源代碼的AST 進行序列化提取節點類型和值信息，根據節點輕重分類確定舍去節點時的優先級，并使用F1 值［13］和AUC 值［14］作為評測指標，同時將Apache 中的5 個項目作為實驗數據集。

1 相關工作

1.1 軟件缺陷預測數據集獲取

當軟件項目處于初級階段且存在歷史庫丟失或損壞等問題時，軟件項目需要的數據無法從自身項目的歷史庫中獲取，此時就需要借助其他的項目數據，屬于跨項目缺陷預測和異構缺陷預測。在跨項目缺陷預測和異構缺陷預測方面，研究人員一般通過遷移學習等方法解決了不同項目度量元分布不同的問題。倪超等［6］采用兩階段跨項目缺陷預測方法FeCTrA，先通過聚類篩選出源項目與目標項目具有高分布相似度的特征，再基于TrAdaBoost 方法選出源項目中與目標項目標注實例分布相似的實例進行預測。RYU 等［15］在遷移學習過程中，考慮到少量的目標項目標記會加重缺陷預測數據集的類不平衡問題，提出一種對遷移成本敏感的學習方法，將權重分配給訓練實例。BENNIN 等［16］通過減弱缺陷數據集的類不平衡程度來提升缺陷模型的預測精度并提出MAHKIL 方法。MAHKIL 方法是一種基于染色體理論的缺陷數據集采樣方法，利用兩個不同的缺陷樣本生成一個新實例，新實例繼承父親樣本的不同特征。

1.2 深度學習模型

傳統缺陷預測方法使用表示代碼宏觀信息和固有特征的度量元來描述代碼模塊。這些度量元由有經驗的開發人員、測試人員和研究人員設計提出，可能更切合總結特征時選擇的軟件項目。當這些度量元用來描述其他軟件項目時，部分指標與標簽沒有高度相關性，變成冗余信息，還可能影響預測模型的性能。因此，充分利用程序代碼的結構和語義信息，能夠使代碼模塊的表征更切合目標軟件。

AST 和控制流圖（Control Flow Graph，CFG）是當前常用的利用數據結構對程序代碼進行表示的方法。AST 是以樹狀形式表示軟件源代碼的語法結構，樹上的每個節點都表示源代碼中的一種結構。CFG 是以圖的形式表示軟件代碼中一個模塊在執行過程中的可能流向。LI 等［11］采用AST表示程序代碼，遍歷AST 時選擇具有特定類型的節點，通過字典映射并利用節點轉換向量構建向量組來描述整個程序代碼。通過卷積神經網絡（Convolutional Neural Networks，CNN）產生一個向量來表征整個程序代碼，這個向量具有類似度量元的功能。PAN 等［17］在卷積層后增加了dense 層和dropouts 層來減少模型過擬合問題。FAN 等［12］提出一種基于注意力的循環神經網絡缺陷預測（DP-ARNN）模型來構建代碼表征向量，該模型通過注意力機制對前后節點的關聯信息進行有效利用。VIET 等［18］通過編譯程序代碼獲得的匯編指令構造CFG，使用基于有向圖的卷積神經網絡（DGCNNs）構建代碼表征向量。上述方法根據深度優先遍歷獲得AST 節點，并且僅選取特定類型的節點。這可能使不相關的節點被視為有關聯的節點，導致不正確的缺陷預測。因此，在本文方法中將使用輕重鏈來區分節點在樹中的位置，并僅以輕重程度作為條件來選擇需要的節點。

2 基于重子節點的抽象語法樹缺陷預測

本文提出的HSAST 方法首先將AST 中的每個節點進行標記，在節點數超過預設的代碼描述向量組時，根據標記的優先級選擇被舍棄的節點，然后使用深度學習方法將向量組轉換為代碼模塊的表征向量，以此進行精確的軟件缺陷預測。圖1 給出了HSAST 的總體框架。首先將程序模塊的源代碼解析為AST；然后根據子樹的大小對節點進行標記，根據節點標記和節點包含的信息從AST 中獲取節點序列；之后通過字典映射和詞嵌入方法將節點序列編碼為多維向量，這些向量會作為深度神經網絡的輸入，通過深度神經網絡完成代碼模塊的結構和語義學習；最后將學習獲得的代碼模塊表征向量輸入到邏輯回歸分類器中進行分類完成缺陷預測。

圖1 基于重子節點抽象語法樹的缺陷預測框架Fig.1 Defect prediction framework via heavy son node-based abstract syntax tree

2.1 源代碼解析

神經網絡模型無法將完整的文本信息直接轉換成描述文本信息的向量，需要合適的方法將計算機代碼先轉換成神經網絡模型能夠運用的實數向量數據，再通過深度學習網絡進行學習。根據已有研究，研究人員使用AST 來表示一段程序，這種數據結構能夠很好地反映代碼模塊的結構和語義信息。在本文實驗中，將使用一個名為javalang 的開源Python包來完成代碼模塊的解析任務，通過https：//github.com/c2nes/javalang 獲取，能夠將Java 源代碼解析成對應的AST。

根據DP-CNN方法［11］和javalang的源代碼文件tree.py，有3 種類型的AST 節點含有代碼模塊的語義信息，具體為：1）方法調用的節點；2）聲明的節點，包括方法聲明、構造函數聲明和類聲明等；3）引用的包、參數定義等。其他結構信息主要包括控制流節點（分支、循環、異常引發、捕獲等）以及類的起始與終止、聲明的起始等表示代碼模塊結構的信息。

首先，對于AST 中不含代碼語義信息的節點，本文選擇一段特殊的字符串$null$作為第一部分表示該節點不包含文本信息，并記錄描述節點類型的字符串作為描述節點值的第二部分。然后，對于AST中包含代碼語義信息的節點，提取節點的名稱或節點對應的值作為第一部分，記錄描述節點類型的字符串作為第二部分，結合兩者對節點進行描述。最后，按照規則將每個代碼模塊的AST 轉換為向量，此時向量是AST 標記字符串的組合，無法直接作為深度學習網絡的輸入。本文在標記字符串與整數之間建立映射字典表，先計算每個標記的出現頻率，再根據標記頻率進行排序，使出現頻率高的標記位于字典表前端。在完成映射后，為避免向量過于稀疏，選擇合適的向量長度。對于小于指定長度的向量，將通過填充0 來增加長度。對于長度大于指定長度的向量，將通過基于重子節點的標記按規則舍去部分長度，直到向量長度與指定長度相等。

2.2 基于重子節點的AST 編碼和類不平衡處理

HSAST 方法采用樹鏈剖分思路將樹分割成多個部分，具體定義如下：

定義1重子節點為在所有子節點中以該節點為根的子樹規模（即樹的節點數目）最大的節點。以重子節點為根的子樹為重子樹。

定義2輕子（Light Son，LS）節點為除了重子節點外的其他子節點。以輕子節點為根的子樹為輕子樹。

算法1 描述了將AST 分割成重子節點和輕子節點的過程。輸入是AST 的節點nodei和節點對應的下標nexti。輸出是以節點為根的子樹大小sizei和該節點的重子節點soni。

算法1重子節點分割算法

在將代碼模塊解析成AST 的過程中，包含源代碼中更多文本信息和控制流信息的部分在AST 中形成的子樹更大，同時這一部分更有可能形成缺陷。若舍去代碼模塊中出現頻率低的標記字符串，則有可能會舍去重子樹中具有特異點的標記。因此，保留具有更多信息的重子樹，從信息較少的輕子樹開始舍去能提高模型預測性能。

算法2 描述了重子樹的選擇過程。輸入是AST的節點nodei和節點對應的下標nexti、節點的重子節點soni和序列化向量的最大長度MaxSize。輸出是序列化后的向量V。采用嵌入到網絡中的詞作為可訓練的單詞字典，將標記轉換為高維向量。

算法2重子數選擇算法

在一個軟件項目的正常生命周期中，無缺陷的模塊總是多于有缺陷的模塊，因此在預測模型數據集時，無缺陷樣本往往多于有缺陷樣本。如果直接使用未處理過的源數據集進行訓練，則結果將偏向多數類，即更容易將目標軟件模塊視為無缺陷的樣本。在類不平衡問題上，研究人員進行了大量研究［19-20］并取得了一定的研究成果。為進行更有效的對比，本文使用過采樣方法［12］處理類不平衡問題，從有缺陷樣本中隨機復制訓練樣本，生成類平衡的訓練數據集。

2.3 基于深度學習模型的軟件缺陷預測

本文采用3 種深度學習模型提取代碼模塊中的結構和語義信息：1）循環神經網絡（Recurrent Neural Network，RNN）模型，利用雙向長短期記憶（Bi-directional Long Short-Term Memory，Bi-LSTM）網絡對代碼模塊的信息進行學習，能夠獲取源代碼的上下文信息；2）基于注意力機制的循環神經網絡（Attention-based RNN，ARNN）模型，在Bi-LSTM 的基礎上加入注意力層，能夠突出對預測結果更具影響的關鍵信息；3）CNN 模型，對程序代碼模塊信息先進行局部感知，再在更高層次對局部進行綜合操作，從而得到全局信息。

軟件缺陷的預測主要分為4 個部分：1）詞嵌入層，將處理后的AST 數字標記向量轉換成固定長度的高維實數向量；2）信息抓取，通過深度學習模型獲取輸入序列中的關鍵信息；3）代碼表征，將提取到的特征進行綜合形成表示代碼模塊特征的向量；4）輸出層，根據表征向量輸出缺陷預測結果。

3 實驗驗證

通過實驗對HSAST 方法進行有效性驗證，從多個角度分析HSAST 方法的性能優劣。介紹實驗過程中采用的數據集、性能評價指標以及實驗流程和參數設定，選擇Keras、Tensorflow 以 及Sklearn 構建深度學習模型，運行于配置為Windows 10 操作系統、i7-6700HQ 2.60 GHz處理器、16GB內存的計算機上。

3.1 研究問題

HSAST 方法需在具有一定歷史標記數據的目標項目中完成預測任務，從源代碼中提取代碼模塊的結構和語義信息，利用AST 中的節點類型和值信息來構建代碼表征向量。為驗證HSAST 方法的有效性，提出以下2 個研究問題：

1）RQ1。將HSAST方法與采用DFS［12］搜索并根據字典頻率舍去節點的處理方法（簡稱為DFS 方法）進行性能分析與對比。

2）RQ2。將不同深度學習模型下的HSAST 方法性能進行對比與分析。

3.2 實驗數據

采用Apache 開源項目中的5 個開源Java 項目，每個項目都包含兩個版本。Java 項目數據集是專門用于軟件工程研究的公開數據集，被大量研究人員認可和使用，提供了每個文件的類名、靜態度量元以及缺陷標簽。使用公開數據集可確保實驗所用項目的歷史數據標記是被廣泛認可的。表1 給出了Java項目數據集信息。使用每個項目中版本號靠前的版本作為訓練數據集，版本號靠后的版本作為測試數據集。在使用訓練數據集進行模型訓練時，隨機選擇其中的70% 作為訓練集，剩下的30% 作為驗證集。

表1 Java 項目數據集信息Table 1 Dataset information of Java project

3.3 評測指標

在進行樣本預測后，根據樣本有無缺陷的實際情況和預測結果可以產生4 種預測結果：實際有缺陷的樣本被預測為有缺陷，即TTP；實際無缺陷的樣本被預測為無缺陷，即TTN；實際無缺陷的樣本被預測為有缺陷，即FFP；實際有缺陷的樣本被預測為無缺陷，即FFN。基于這4 種預測結果，得到查準率（P）和查全率（R）這兩個基礎的評測指標。

查準率也稱為正確率，指預測結果為有缺陷樣本中，實際有缺陷樣本的比例，計算公式如下：

查全率也稱為召回率，指所有實際有缺陷的樣本中，被預測為有缺陷樣本的比例，計算公式如下：

單獨通過一個指標對模型進行測評是不夠準確的，比如模型將所有測試樣例都預測為有缺陷樣本，那么該模型能夠得到100%的查全率，但是其查準率較低。為更綜合地評價HSAST 方法，將F1 值（F）和AUC 值也作為評測指標。F1 值是查準率與查全率的調和平均值，計算公式如下：

AUC 被定義為ROC 曲線下與坐標軸圍成的面積，該面積的數值不會大于1。AUC 值越接近1，檢測方法的真實性越高。

3.4 實驗結果

在以下3 種深度學習模型的基礎上利用HSAST和DFS 方法進行缺陷預測：

1）RNN。使用基于LSTM 單元的雙向循環神經網絡來捕獲和提取代碼模塊中的結構和語義信息后，進行軟件缺陷預測。

2）ARNN。在Bi-LSTM 的基礎上加入注意力層提取對預測結果更具影響的關鍵信息后，進行軟件缺陷預測。

3）CNN。通過文本序列卷積的方式提取代碼模塊中局部和全局信息后，進行軟件缺陷預測。

采用HSAST 和DFS 方法生成模型輸入，使用相同參數進行模型訓練。具體而言，CNN 設置10 個長度為5 的過濾器，全連接層的隱藏節點數為100。RNN 與ARNN 設置LSTM 節點數為16、第一層隱藏節點數為16、第二層隱藏節點數為8。每個樣本形成的向量以固定長度（2 000）輸入到模型中，所有模型的詞嵌入層將數字向量轉換成維度為30 的高維向量。表2 和表3 給出了模型在5 個項目下的運行結果，顯示了同一項目中兩種方法在相同深度學習網絡下的比較統計數據，其中，粗體顯示了每個項目的最佳預測結果，最后一行顯示了兩種方法對5 個項目預測結果的平均值。表4 給出了HSAST 與DFS方法在5 個項目下的時間成本對比結果。

表2 基于HSAST 和DFS 方法的深度學習模型F1 值比較Table 2 Comparison of F1 values of deep learning models based on HSAST and DFS methods

表3 基于HSAST和DFS方法的深度學習模型AUC值比較Table 3 Comparison of AUC values of deep learning models based on HSAST and DFS methods

表4 HSAST 與DFS 方法的時間成本比較Table 4 Comparison of time cost between HSAST and DFS methods s

3.5 實驗結果分析

3.5.1 針對RQ1 的結果分析

利用3 種深度學習模型（CNN、RNN 和ARNN）進行分析與比較，證明了HSAST 方法優于DFS 方法不是使用特定深度學習模型出現的偶然情況。使用表1 中列出的這些項目進行實驗，每個項目采用兩個版本，版本靠前的作為訓練數據集用于訓練預測模型，版本靠后的作為測試數據集用于評估模型性能。

表2 列出了分別采用HSAST 和DFS 方法的3 種深度學習模型在每個項目上的F1 值。以Camel 為例，采用HSAST方法處理AST，ARNN、RNN 和CNN 分別取得的F1 值為0.531、0.517 和0.554；采用DFS處理AST時，ARNN、RNN 和CNN分別了取得的F1 值為0.506、0.494 和0.519。顯然，在3 個深度學習模型上，HSAST 方法均比DFS 方法表現更好。由表2 的最后一行可以看出，HSAST 方法在F1 平均值方面也比DFS 方法表現更好，在ARNN 上平均提升約3%。這些結果表明了基于HSAST 方法的深度學習缺陷預測模型具有更好的預測性能。

表3 列出了每個項目的AUC 值。HSAST 方法同樣在大部分項目上比DFS 方法表現更好。總體而言，HSAST 方法在使用ARNN 深度學習模型時具有最佳性能，而基于其他深度學習模型時，與DFS 方法具有相近的性能。由表3 的最后一行可以看出，HSAST 方法在AUC 平均值方面也比DFS 方法表現更好，在ARNN 上平均提升約4%。

從表4 可以看出，HSAST 方法比DFS 方法平均多花費了55 倍的時間成本，主要在Xalan 和Poi 項目上花費了更多的時間成本。HSAST 方法相比DFS方法在語法樹結構重構以及節點所在樹的位置識別上花費了更多的時間成本，該成本受樹的大小即項目源代碼的文件大小影響。

實驗模型的主要差別在于通過深度學習方法提取代碼模塊信息前的數據處理階段。HSAST 方法對AST 的所有節點進行處理，并優先保留可能具有更多特征信息的重子樹，但HSAST 方法也保留了更多的冗余信息，這些信息會干擾分類器的分類結果，在實驗結果上表現為：在個別項目上DFS 方法具有比HSAST 方法更優的性能。基于上文分析得出以下結論：采用深度學習模型捕獲代碼模塊的隱藏信息，再進行項目內軟件缺陷預測時，HSAST 方法優于DFS 方法。

3.5.2 針對RQ2 的結果分析

為分析HSAST 對不同深度學習模型的影響程度，采用ARNN、RNN 和CNN 深度學習模型來捕獲和提取代碼模塊中的信息。深度學習網絡采用同一個數據處理結果作為輸入，并轉換成相同維度的高維向量進行特征學習。

從表2 和表3 可以看出，CNN 深度學習模型在F1 指標下性能最佳，ARNN 深度學習模型在AUC 指標下性能最佳。這些結果說明了在需要綜合考慮查準率和查全率的場景下，提取節點序列局部特征的CNN 深度學習模型具有更好的性能，而相對實際應用場景，捕獲上下文信息的ARNN 深度學習模型具有更好的性能，因為ARNN 深度學習模型具有略低于CNN 深度學習模型的F1 指標結果和略高于CNN深度學習模型的AUC 指標結果。

4 結束語

本文提出基于重子節點的抽象語法樹軟件缺陷預測方法，利用AST 中的語義和結構信息，通過字典映射和詞嵌入方法將程序源代碼的AST 轉換為高維數字向量，并將結果輸入ARNN 和CNN 深度學習模型中提取代碼表征向量。實驗結果表明，該方法保留了更多代碼模塊中的結構和語義信息，并通過深度學習模型提取關鍵特征，提高了缺陷預測性能。后續將設計基于AST 的樹形結構，拼接代碼模塊靜態度量元，進一步提高軟件缺陷預測性能。