基于字典學習的軟件缺陷檢測算法

張蕾　朱義鑫　徐春

摘要：

針對目前存在的字典學習方法不能有效構造具有鑒別能力字典的問題，提出具有鑒別表示能力的字典學習算法，并將其應用于軟件缺陷檢測。首先，重新構建稀疏表示模型，通過在目標函數中設計字典鑒別項學習具有鑒別表示能力的字典，使某一類的字典對于本類的樣本具有較強的表示能力，對于異類樣本的表示效果則很差；其次，添加Fisher準則系數鑒別項，使得不同類的表示系數具有較好的鑒別能力；最后對設計的字典學習模型進行優化求解，以獲得具有強鑒別和稀疏表示能力的結構化字典。選擇經過預處理的NASA軟件缺陷數據集作為實驗數據，與主成分分析（PCA）、邏輯回歸、決策樹、支持向量機（SVM）和代表性的字典學習方法進行對比，結果表明所提出的具有鑒別表示能力的字典學習算法的準確率與Fmeasure值均有提高，能在改善分類器性能的基礎上提高檢測精度。

關鍵詞：

字典學習；稀疏表示；Fisher準則；軟件缺陷檢測；機器學習

中圖分類號：

TP399

文獻標志碼：A

Abstract：

Since the exsiting dictionary learning methods can not effectively construct discriminant structured dictionary， a discriminant dictionary learning method with discriminant and representative ability was proposed and applied in software defect detection. Firstly， sparse representation model was redesigned to train structured dictionary by adding the discriminant constraint term into the object function， which made the classdictionary have strong representation ability for the corresponding classsamples but poor representation ability for the irrelevant classsamples【and vice versa什么鬼，作者檢查確認. Secondly， the Fisher criterion discriminant term was added to make the representative coefficients have discriminant ability in different classes. Finally， the optimization of the designed dictionary learning model was solved to obtain strongly structured and sparsely representative dictionary. The NASA defect dataset was selected as the experiment data， and compared with Principal Component Analysis （PCA）， Logistics Regression （LR）， decision tree， Support Vector Machine （SVM） and the typical dictionary learning method， the accuracy and Fmeasure value of the proposed method were both increased. Experimental results indicate that the proposed method can increase detection accuracy with improving the classifier performance.

英文關鍵詞Key words：

dictionary learning； sparse representation； Fisher criterion； software defect detection； machine learning

0引言

隨著計算機信息科學的飛速發展，軟件技術已經滲透到科學、工業、經濟和文化的各個領域，對人類社會的進步和發展起著舉足輕重的作用，同時影響和改變著人們工作、學習和生活的方式[1]。一方面，軟件技術的發展和應用水平已經成為衡量一個國家科學技術實力的標志，但是另一方面，隨著軟件規模、復雜度、系統集成度的不斷上升，軟件中存在的缺陷問題大大影響了產品開發的質量和效率[2-3]，甚至歷史上一些由于軟件缺陷而造成的事故也頻頻發生，比如1962年

美國國家宇航局（National Aeronautics and Space Administration， NASA）馬里納1號空間探測器由于Fortran語言少寫了一個連字符造成火箭偏離，其損失約8000萬美元；20世紀80年代由于錯誤的軟件導致對癌癥患者的致命過量輻射事故；20世紀90年代丹麥機場行李處理系統的缺陷導致行李箱損壞，為此花費大量金錢及人力恢復正常運營等。

軟件缺陷[4-5]通常指計算機軟件或者代碼中能引起失效的錯誤的編碼。在軟件工程領域，合理地預測缺陷能夠有助于及時找出未被發現但是真實存在的缺陷以及缺陷分布[6]，因此不僅可以節約大量的成本，提高產品質量，還能夠客觀地評價測試結果，讓開發者合理地權衡潛在的預測風險和測試成本之間的關系，便于科學地進行軟件測試工作。雖然不同度量元的數據采集方法不同，但在預測算法中對不同的度量元并不區分處理，預測算法具有通用性。

軟件缺陷檢測技術[7]分為動態檢測和靜態檢測技術。前者主要靠研究人員通過統計分析、經驗研究等方式來考察軟件缺陷隨軟件周期的分布，一些軟件的可靠性模型便是基于這類技術；后者通過分析利用軟件的規模、復雜度、軟件缺陷的度量元等特征數據來預測軟件中潛在的缺陷。本文的研究內容針對后者，即靜態的軟件缺陷檢測技術。比如來源于NASA的著名軟件度量程序（Metric Data Program， MDP）[8]，其主要針對于軟件度量元數據的收集、組織、存儲等情況，這個公開項目已經成為軟件缺陷檢測領域經典的數據集。

1相關算法

目前，機器學習算法得到了飛速的發展，其中一些具有代表性的算法已被用于軟件缺陷檢測領域，比如支持向量機（Support Vector Machine，SVM）[9-10] 、分類回歸樹（Classification and Regression Tree， CART）[11]、人工神經網絡（Artificial Neural Network， ANN）[12]、主成分分析（Principal Component Analysis， PCA）[13-14]、聚類分析（Cluster Analysis， CA）[15-16]、Logistics回歸（Logistics Regression， LR）方法[17-18]等。

字典學習方法[19-20]實質上基于稀疏表示方法（Sparse Representation），其通過訓練樣本構造結構化的字典，使用學習得到的結構化字典對樣本進行線性編碼，然后利用編碼之后的重構誤差對樣本進行分類，其已被廣泛用在信號壓縮、圖像分類等領域。從目前來看，盡管經典的機器學習方法已經被廣泛用于軟件缺陷檢測領域，但是基于字典學習的方法仍未被利用。從本質上來看，軟件度量數據集中的數據依然可以看成是某種形式的信號，因此基于字典學習的算法完全可以應用在軟件缺陷檢測領域。

常規的字典學習算法不能有效利用數據集之中不同類樣本的鑒別性質，具體表現在不能有效構造具有鑒別性質的結構化字典。本文提出了一種基于鑒別字典學習（Discriminant Dictionary Learning， DDL）的軟件缺陷檢測方法，其通過在傳統的字典學習模型目標函數之中加入鑒別約束項來構造具有鑒別性質的字典原子以提高模型的分類性能。

2本文算法

傳統的字典學習模型沒有較好的鑒別能力，其僅簡單地考慮整體字典對于某個數據樣本的表示，而沒有考慮不同類字典之間的表示關系。本文對傳統的字典學習模型進行兩點改進：1）在字典學習模型中，整體字典對某一個樣本應該具有較強的表示能力，同時，如果單獨考慮這個樣本所在類的字典應該也對其具有較強的表示能力，而該類字典對其他類樣本則表示能力很差，因此通過引入鑒別約束項可以滿足此條件，以達到很好的鑒別性能；

2）字典學習的目的是通過求解表示系數對樣本進行表示，因此可以考慮使用字典對不同類樣本進行稀疏表示時，它們的表示系數之間應該具有較強的區分能力，從而進一步達到鑒別的目的。本文所提出的基于字典學習的軟件缺陷檢測流程如圖1所示。

3基于字典學習的軟件缺陷檢測算法

3.1稀疏表示分類器

稀疏表示最早在信號處理領域中得到應用。由于小波變換和傅里葉變換技術的發展，科研人員需要處理的數據維數越來越高，稀疏表示分類（Sparse Representation Classification， SRC）技術開始引起了研究人員的極大興趣，并逐步發展形成了一個獨立性的理論方法，并且推廣到了機器學習、圖像處理及模式識別等領域[21]。假設存在一個樣本集X={x1，x2，…，xN}∈Rm×n，其中xi表示X中的某一個樣本，根據稀疏表示理論xi可以通過樣本集X中的樣本以線性組合的形式進行表示：

4實驗分析

本文通過引入幾種重要的分類器性能指標進行實驗對比，并選擇來源于美國國家宇航局（NASA）的軟件度量程序（MDP）作為實驗數據。在實驗過程中，將選擇支持向量機（SVM）、決策樹（C4.5）、主成分分析（PCA）、Logistics回歸（LR）方法、具有代表性的字典學習方法DLSDP（Dictionary Learning based Software Defect Prediction）[25]這幾種算法作為對比算法。本文選擇Matlab R2011a作為實驗工具，實驗所用PC配置為Intel 酷睿i7 6700 CPU，32GB內存。

4.1數據集介紹

本文選擇來自NASA的MDP項目進行實驗。MDP項目是一個向全球公開的數據度量項目，任何用戶均能夠從NASA的官網下載其中的數據。MDP項目包含多個軟件缺陷數據集子集，本文選擇其中的JM1、CM1、KC1、MW1及PC1作為實驗對比數據集。以其中的JM1為例，JM1數據集始于某個地面預測系統的軟件項目，使用C++進行開發，共有10879個模塊、21個軟件度量屬性以及1維的是否為缺陷的標簽，其中21個屬性包含總代碼行數，McCabe的循環復雜度、基本復雜度、設計復雜度，Halstead程序的級別、容量、工作量、時間、長度等屬性。

4.2分類器性能評價指標

表1中定義了幾種分類的行為，其中正確預測為正類（True Positive， TP）表示在分類過程中實際為有缺陷的數據正確分類為有缺陷；錯誤預測為負類（False Negative， FN）表示實際為有缺陷的數據預測為無缺陷；錯誤預測為正類（False Positive， FP）表示實際為無缺陷的數據被預測為有缺陷，正確預測為負類（True Negative， TN）定義為無缺陷數據預測正確預測為無缺陷數據。

由于最終的檢測結果是判斷數據是否有缺陷，因此是一個兩類問題，僅僅通過分類準確率來評價一個算法的有效性是不夠全面的，因此在本文的實驗中引入這里說的名稱與下面定義介紹不一致，以下面的介紹為準，請確認召回率、錯誤接受率、查準率、準確率以及Fmeasure值較為全面地衡量分類算法的有效性。以下簡單介紹這幾種值的定義：

1）召回率：re=TP/（TP+FN）。召回率是一種重要的分類器性能衡量指標，因為在實際應用中需要重點考慮的是有缺陷的數據，其反映了被正確判定的缺陷樣本占總的缺陷樣本的比重，即衡量有缺陷樣本檢測的全面程度。

2）錯誤接受率：pf=FP/（FP+TN），其反映了分類結果中無缺陷數據被預測為有缺陷數據的比例。

3）查準率：pre=TP/（TP+FP），用來衡量檢測到有缺陷樣本的準確率。

4）準確率：acc=（TP+TN）/（TP+FN+FP+TN），用來衡量著所有正確分類的樣本占總樣本的比例。

從以上定義看出，一個好的分類器預測模型，希望能滿足較高的召回率、缺陷檢測準確率以及準確率，較低的錯誤接受率，尤其是查準率和召回率是兩類問題中比較重要的指標。然而，實際情況中，查準率和召回率之間往往難以同時都達到較高的值，需要在二者之間尋求權衡，因此需要折中考慮二者。本文引入Fmeasure值來考慮衡量準確率和召回率的調和平均數，其被定義為：

Fmeasure=2*β*re*pre/（re+β2pre）

（18）

在實驗中取β的值為1，即通常所說的F1measure值。其中re是召回率，pre是缺陷檢測準確率，另外定義pf表示為錯誤接受率，acc表示準確率。從以上定義顯然可以看出，所有的評估指標的取值范圍均在0～1。

4.3實驗結果及分析

在實驗過程中，對于SVM算法采用徑向基核，同時選擇懲罰因子C=1來分別進行實驗。對于本文提出的DDL模型，取迭代步長σ的值為0.1，λ1的值取0.01，λ2的值為0005。為了公平地進行實驗，在本文的實驗中每種算法最終選擇隨機進行20組交叉實驗驗證，以合理地進行算法對比，最終得到的re、pf、pre實驗結果如表2所示，acc以及F1measure如表3所示。

4.4實驗分析

從表2、3可以看出，與其他算法相比，本文提出的DDL算法最終能夠將F1measure提高0.03～0.26，而準確率能夠提高0.03～0.20，而召回率、查準率也有一定程度的改善。其主要原因主要是本文提出的字典學習模型具有較強的鑒別分類能力，對比其他幾種機器學習方法，字典學習模型本身又有較好的抗干擾能力。而PCA由于其是一種無監督的降維方法，沒有有效利用豐富的標簽信息，相對于其他集中算法效果最差；LR是一種模型較為簡單的回歸算法，模型本身不具有鑒別能力，同時從其自身的應該來看，算法泛化能力較差，因此實驗效果相對較差；C4.5其容易出現過度擬合的問題，而且其對連續性的字段難以作出準確的預測；對于SVM，其雖然擁有較強的泛化能力，但是需要選擇合適的核函數，而SVM本身也具有多種形式的模型，因此如何選擇合適的參數也是一個問題，同時SVM也沒有很強的鑒別分類能力。

值得一提的是本文選擇了DLSDP算法進行對比，可以發現，DLSDP也是一種字典學習方法，由于其在算法中主要使用代價敏感方法來解決類不平衡問題，因此所得到的Fmeasure值和本文的算法相比很接近；另一方面，由于其沒有考慮不同類字典的鑒別性質，因此在檢測精度上略差于本文算法。

5結語

為解決傳統的字典學習方法不能有效構造具有鑒別能力字典的問題，提出了一種新的基于鑒別字典學習的分類算法，并用于軟件缺陷檢測，即基于鑒別字典學習的軟件缺陷檢測算法。該算法首先通過添加鑒別表示項以突出不同類字典對不同類樣本的表示能力，其次添加Fisher準則系數鑒別項，使得不同類的表示系數具有較好的鑒別能力；然后通過迭代算法求解相應模型的目標函數，最后選擇在MDP數據集上進行實驗，獲得的實驗結果表明能夠在改善檢測性能的基礎上提高檢測精度。現實當中二分類經常面臨正負樣本不平衡的問題，在本文提出的算法中，可以通過引入代價敏感約束進一步提高算法的分類性能，考慮不同類樣本數目對分類造成的代價影響，本文的后續工作可以圍繞這項內容展開工作。

參考文獻：

[1]

BAGGEN R， CORREIA J P， SCHILL K， et al. Standardized code quality benchmarking for improving software maintainability [J]. Software Quality Journal， 2012， 20（2）： 287-307.

[2]

SHEPPERD M， SONG Q， SUN Z， et al. Data quality： some comments on the nasa software defect datasets [J]. IEEE Transactions on Software Engineering， 2013， 39（9）： 1208-1215.

[3]

MA Y， LUO G， ZENG X， et al. Transfer learning for crosscompany software defect prediction [J]. Information and Software Technology， 2012， 54（3）： 248-256.

[4]

WANG S， YAO X. Using class imbalance learning for software defect prediction [J]. IEEE Transactions on Reliability， 2013， 62（2）： 434-443.

[5]

SONG Q， JIA Z， SHEPPERD M， et al. A general software defectproneness prediction framework [J]. IEEE Transactions on Software Engineering， 2011， 37（3）： 356-370.