原 子 于莉莉 劉 超

(北京航空航天大學 計算機學院，北京100191)

軟件缺陷是危害軟件質量、增加組織成本、延緩軟件開發(fā)進度的重要因素.由于質量保證資源的有限，高效地發(fā)現(xiàn)和修復缺陷一直是軟件工程領域的研究重點.為幫助軟件人員有效分配測試和審查資源，軟件工程領域的研究者提出兩種策略［1］:①在缺陷存在于軟件系統(tǒng)之后，識別缺陷可能存在的區(qū)域;②在缺陷即將引入軟件系統(tǒng)時，識別引入缺陷的軟件變更.第②種策略的優(yōu)勢在于:一是在缺陷引入時給出警告，從而幫助軟件人員更加及時地分配資源，發(fā)現(xiàn)缺陷;二是通過分析引入缺陷的變更所具有的特征，從而幫助研究者理解缺陷引入的根源.

針對第②種策略，研究者提出了不同粒度的引入缺陷變更識別方法.文獻［1］關注于事務粒度引入缺陷變更的識別.基于文本分類思想，首先將事務變更表示為變更發(fā)生前后兩個軟件版本所對應詞向量之差，然后作為分類實例訓練分類器，對新的事務變更進行識別.文獻［2］關注于文件粒度變更的識別，除了將文件粒度變更所涉及的詞作為特征之外，還選用了一系列刻畫源文件復雜度和歷史活躍性的度量作為輔助特征.相比于文獻［1］，文獻［2］的方法不但降低了識別的粒度，并通過構建更加直觀的特征集增強了方法的可理解性.

在2012年的軟件工程預測模型會議上，專家指出，考慮軟件工程實踐的成本因素，細粒度的識別和預測將成為未來軟件工程預測方法關注的重點.盡管文獻［2］的方法將識別粒度降低到了文件級別變更，但是文件級變更常涉及多處語句修改.尤其在文件規(guī)模較大，內部結構較復雜時，這種文件內多處修改的現(xiàn)象更為常見.這種情況下，即使識別出了引入缺陷的文件變更，仍然需要軟件人員逐一審查所有發(fā)生修改的文件語句，才能找到引入缺陷的位置.為進一步降低人力成本，本文提出更細粒度(語句層級)的引入缺陷變更識別方法.該方法從細粒度變更發(fā)生的場景(時間、地點、內容、意圖以及人員)出發(fā)構建特征集，將細粒度軟件變更作為實例構建分類器.相比于文獻［1-2］，本文的主要貢獻包括兩個方面:①通過還原細粒度變更發(fā)生的場景，描述引入缺陷的變更的特征，增強了識別方法的可理解性;②通過降低識別粒度，節(jié)省了軟件開發(fā)過程中人工審查的成本.

1 基本概念

1.1 細粒度軟件變更

假設源文件d的第i個修正版本對應一棵抽象語法樹Ti=〈N，P〉，其中N代表語法樹中代碼實體節(jié)點的集合，P代表代碼實體之間的父子關系集合.將對語法樹Ti的一次節(jié)點插入、刪除、移動或者更新定義為一個編輯操作，每個編輯操作都代表著一次細粒度軟件變更［3］，簡稱SCC.由于操作是基于語法樹實體節(jié)點進行的，因此細粒度軟件變更可以精確至語句層級.

1.2 引入缺陷細粒度軟件變更

如果細粒度軟件變更會引發(fā)缺陷并在后續(xù)開發(fā)過程中觸發(fā)代碼修復操作，那么定義此次細粒度軟件變更為引入缺陷的細粒度軟件變更.

圖1是細粒度軟件變更示意圖，圖中共包含3個細粒度軟件變更，其中if語句插入屬于引入缺陷的細粒度軟件變更.

圖1 細粒度軟件變更Fig.1 Fine-grained software changes

1.3 識別任務

給定一組細粒度軟件變更，將其形式化表示為 C={SCC1，SCC2，…，SCCn}.?i∈{1，2，…，n}，SCCi用一組特征 F={f1，f2，…，fm}來表征.通過學習C構建分類器L.對一個新的細粒度軟件變更SCCn+1，依據(jù)其特征對其所屬類別進行識別，形式化表示為

其中l(wèi)代表SCCn+1的類別標簽，即是否為引入缺陷的細粒度變更.

2 引入缺陷細粒度軟件變更識別

引入缺陷細粒度變更識別方法主要包含兩個重要部分:特征集和分類器.本節(jié)詳細介紹這兩部分.

2.1 特征集

本文通過還原細粒度軟件變更發(fā)生的場景來描述其特征，關注變更發(fā)生的時間、地點、內容、意圖和人員5個方面.如圖2所示，每個方面代表一個特征集，每個特征集涉及多個因素.

圖2 特征集Fig.2 Feature sets

2.1.1 時間

軟件變更是由人操縱的活動，由于自身或外界因素，人的工作質量在不同的時段并不相同.Eyolfson等人［4］在分析Linux內核的軟件歷史庫時發(fā)現(xiàn)，從午夜至凌晨發(fā)生的變更，更易引入缺陷.此外，Sliwerski等人［5］指出，每周五發(fā)生的變更具有較高的引入缺陷的風險.基于前人的發(fā)現(xiàn)，本文選用了兩個刻畫時間的因素，即一周內的天和一天的鐘點，反映了軟件人員的工作周期.

2.1.2 地點

本文將發(fā)生細粒度變更的源文件作為變更地點，它反映了變更所處的上下文環(huán)境.源文件的規(guī)模，內部結構復雜程度，同其他源文件的交互關系復雜程度，領域功能的多樣性，以及歷史上的穩(wěn)定性都會影響細粒度變更引入缺陷的風險.

1)代碼行數(shù):源文件的代碼行數(shù)過多，會影響可讀性從而增加軟件人員的理解難度.不透徹的程序理解往往是軟件變更引入缺陷的原因.

2)Halstead復雜度［6］:通過源文件算子和算域的數(shù)量來反映代碼內部操作的復雜程度.Halstead復雜度越高，代碼的內部實現(xiàn)越復雜，正確理解和變更它的難度也越大.

3)McCabe復雜度［7］:通過源文件函數(shù)中線性獨立路徑數(shù)目來反映代碼內部的控制流結構復雜程度.McCabe復雜度越高，說明源文件內的選擇和判斷邏輯越復雜，變更引入缺陷的風險越大.

4)軟件依賴圖復雜度:軟件開發(fā)是一項復雜的任務，軟件模塊之間常具有復雜的依賴關系，因此在未充分理解軟件整體結構的情況下對軟件模塊進行更改，經常會引入缺陷.近年來，研究者們開始關注軟件模塊之間的依賴關系對缺陷分布規(guī)律的影響［8］.本文將軟件系統(tǒng)抽象為依賴圖G=〈V，E〉，其中V代表節(jié)點(即源文件)集合，E代表邊(源文件之間的關系)集合.源文件之間的關系指的是通過源文件中的類和接口所建立的繼承、關聯(lián)、依賴或實現(xiàn)關系.本文選用節(jié)點在依賴圖中的出入度作為描述源文件和軟件系統(tǒng)中其他文件之間依賴關系復雜程度的度量.

5)語義主題多樣性:涉及多種領域功能的源文件，其實現(xiàn)邏輯通常較為繁雜，對其進行變更引入缺陷的風險也較大.反映領域功能的信息存在于源文件的自然語言(如程序實體名稱、程序注釋等)之中.本文通過挖掘源文件中的自然語言語義主題，定義了一種描述源文件領域功能多樣性的度量.由于源文件多個版本存在嚴重的信息冗余，直接針對軟件歷史庫中的多版本源文件進行語義挖掘會面臨推斷結果不準確的問題［9］.因此本文采用針對源文件相鄰版本間編輯文件的主題挖掘方法來消除文本信息冗余.

假設軟件系統(tǒng)中蘊含主題為T={t1，t2，…，，細粒度變更SCCi發(fā)生在軟件系統(tǒng)的第u個版本的第v個源文件中，將其所對應的軟件歷史表示為 H={V1，V2，…，Vu-1}，源文件表示為duv.duv和前一個版本比較得到增加和刪除兩個編輯文件，簡寫為，x∈{a，d}.針對歷史上所有編輯文件運用LDA Gibbs抽樣算法進行主題推斷，從而得到，x∈{a，d}的主題分布

信息檢索領域研究者使用信息熵來度量文本語義主題的多樣性［10］.本文也采用信息熵計算方法，根據(jù)θduv和式(4)計算出duv的語義主題多樣性:

6)歷史活躍度:在軟件開發(fā)歷史上被頻繁修改的源文件，其包含缺陷和未來再次發(fā)生修改的概率要明顯高于歷史上較為穩(wěn)定的源文件［11］.本文假設對歷史上較為活躍的源文件實施修改更容易引發(fā)缺陷.為了描述源文件的歷史活躍度，本文選用歷史變更次數(shù)、修復缺陷次數(shù)及歷史上參與變更該源文件的軟件人員個數(shù)這3種度量.

2.1.3 內容

變更內容本身的語法語義難度對變更質量有著直接的影響.本文通過3個因素描述變更內容.

1)變更類型:細粒度變更由于完成的抽象語法樹操作特點不同，引入缺陷的概率也不同.Pan等人［12］指出，涉及程序邏輯或方法接口的修改(如條件表達式的更改或方法參數(shù)的增刪)引入缺陷風險較大.Fluri等人［3］針對抽象語法樹操作特點將細粒度變更系統(tǒng)地分為48種類型，包括條件表達式更新，方法參數(shù)插入等.本文依據(jù)該分類法將變更類型作為描述變更內容的特征.

2)變更實體類型:Pan等人［12］還發(fā)現(xiàn)，針對某些語法實體(如if條件語句、switch語句以及while循環(huán)語句)的變更，引入缺陷的概率較高.Fluri等人對抽象語法樹實體也進行了分類(共104種).基于他們的工作，本文將變更所操縱的語法實體類型也作為描述變更內容的一個特征.

3)語義主題缺陷傾向性:細粒度變更內容，除了用語法樹特征來刻畫外，還需通過其涉及的領域功能來描述.Chen等人［13］指出，實現(xiàn)簡單領域功能(如數(shù)據(jù)庫操作)的代碼片斷包含缺陷的概率顯著小于實現(xiàn)復雜領域功能(如分析器)的代碼片斷.本文假設變更所涉及的領域功能不同，引入缺陷的概率也不同.本文提出語義主題缺陷傾向性度量來刻畫變更所涉及的領域功能特征.

為細粒度軟件變更 SCCi，i=1，2，…，n 所對應的軟件歷史 H={V1，V2，…，Vu-1}中的每一個編輯文件，x ∈ {a，d}，p ∈ {1，2，…，u-1}，定義缺陷感染率度量，即

2.1.4 意圖

變更是為了某種目的而實施的活動，如增加新功能、重構或者修復缺陷等.Mockus等人［14］提出了分類和識別變更意圖的方法.此外他們在研究商業(yè)軟件變更風險因素時發(fā)現(xiàn)，變更意圖影響變更質量.Hassan等人［15］針對開源軟件提出了變更意圖分類方法.借鑒已有研究成果，本文將細粒度變更意圖分為缺陷修復、增加新功能和代碼改進3類.軟件的變更意圖蘊藏在軟件庫的變更描述信息中.不同變更，其描述信息篇幅也不相同.通常較為復雜的變更，其描述信息也較為詳盡.因此將變更描述信息容量也作為因素之一.總的來說，描述變更意圖的因素包括:

1)意圖類型;

2)描述變更意圖的語句數(shù)量;

3)描述變更意圖的詞的數(shù)量.

2.1.5 人員

軟件人員是細粒度變更的實施者，他們的開發(fā)經驗和專業(yè)技能直接影響著變更的質量.本文定義兩種度量來描述變更人員的經驗特征.

1)項目經驗:修改整個軟件系統(tǒng)的次數(shù).

2)源文件經驗:修改該源文件的次數(shù).

2.2 分 類 器

本文選擇了3種機器學習分類器來進行訓練和識別，即K近鄰、裝袋以及隨機森林.這3種分類器被廣泛用于缺陷預測模型的構建［1，16］.

1)K近鄰:屬于一種基于實例的學習或懶學習分類器，它依據(jù)特征空間中與待分類實例最相近的實例集中的實例標簽做出分類決策.

2)裝袋:屬于一種組裝學習分類器，主要用來改進統(tǒng)計分類和回歸算法的穩(wěn)定性和準確性.它還通過降低方差來避免學習過程中的過擬合.

3)隨機森林:是一種結合裝袋思想與隨機特征選擇思想的組裝學習分類器.它通過降低不同決策樹之間的關聯(lián)度改進了裝袋分類器.隨機森林分類器被證明在含有噪聲和類分布不均衡的數(shù)據(jù)集上具有較好的分類效果［17］.

3 實驗和評估

3.1 數(shù)據(jù)集和數(shù)據(jù)收集

為驗證識別方法的有效性，本文在6個真實軟件系統(tǒng)上開展實驗，分別是 Eclipse(簡稱為Ecl)，Argouml(簡稱為 Arg)，Columba(簡稱為Col)，JBoss(簡稱為 JBo)，Scarab(簡稱為 Sca)和Struts(簡稱為Str).表1列出了系統(tǒng)的詳細信息，包括實驗所選擇的軟件修正版本區(qū)間、發(fā)生在該區(qū)間內的細粒度變更總數(shù)、引入缺陷的細粒度變更百分比以及軟件系統(tǒng)的應用類型.為了和事務粒度以及文件粒度識別方法進行比較，本文所選擇的修正版本區(qū)間和文獻［1-2］保持一致.

表1 數(shù)據(jù)描述Table 1 Description of datasets

本文采用程序靜態(tài)分析和自然語言語義分析相結合的方法完成細粒度變更特征的抽取和類標簽構建.圖3描述了數(shù)據(jù)收集過程.其中用來刻畫時間、人員、意圖以及地點中的歷史活躍度的特征通過分析軟件歷史庫的提交日志直接抽取.變更地點中的Halstead復雜度、McCabe復雜度、依賴圖復雜度以及變更內容中的細粒度變更類型和實體類型需要通過靜態(tài)分析技術來抽取.為提高每個版本依賴圖構建的效率，本文提出一種不確定性程序靜態(tài)分析算法實現(xiàn)增量圖構建.語義主題多樣性和語義主題缺陷傾向性需要通過挖掘源代碼文件的自然語言語義信息來抽取.此外還需要為細粒度變更打上類別標簽(即是否為引入缺陷的變更).本文采用多版本語句追蹤改進了經典的變更實例標簽構建SZZ算法［5］，從而實現(xiàn)了精確至語句層級的細粒度變更的標簽構建.

圖3 數(shù)據(jù)收集過程Fig.3 Data collection process

3.2 性能和特征分析

3.2.1 分類器性能分析

本文采用10折交叉驗證評估方法來評估所提出的細粒度識別方法在3種不同類型分類器上的性能.表2列出了3種分類器經過10次10折交叉驗證所得到的平均識別性能.為了測試不同分類器識別性能的差異，本文采用了t檢驗法.

表2 各分類算法的識別性能比較Table 2 Performance comparison of classifiers

經過檢驗發(fā)現(xiàn)，采用不同分類器得到的識別性能不同.隨機森林分類器的性能顯著優(yōu)于另外兩種分類器，K近鄰分類器在大多數(shù)系統(tǒng)上的識別性能顯著優(yōu)于裝袋分類器(p＜0.01).由于軟件歷史庫中所記錄的數(shù)據(jù)并不是絕對完整和準確的，現(xiàn)有的庫挖掘技術手段也存在不足，因此實驗數(shù)據(jù)集中常存在噪聲.經研究證實，隨機森林相比于其他分類器，對數(shù)據(jù)噪聲具有更強的魯棒性［17］.因此隨機森林在本文的實驗中具有最為突出的識別性能.

從表1中可以看出，不同的軟件系統(tǒng)，引入缺陷的細粒度變更百分比也不同.文獻［2］在研究文件粒度變更時指出，引入缺陷變更的百分比對文件變更識別方法的性能具有一定的影響.本文分析了引入缺陷的細粒度變更百分比對本文方法性能的影響.通過表3列出的Pearson相關性分析結果發(fā)現(xiàn)，這種影響在本文提出的方法中要明顯弱于文獻［2］中針對文件粒度變更的方法，說明本文方法對于不同系統(tǒng)引入缺陷變更比例的差異具有更好的魯棒性.

表3 引入缺陷細粒度變更百分比與識別性能的相關性Table 3 Correlation between percentage of defect-introducing SCCs and performance of identification

3.2.2 特征分析

本文遵循以下兩個步驟驗證特征集中每個因素的識別性能:①僅使用該因素訓練分類器;②從特征全集中僅移除該因素訓練分類器.這里也采用10折交叉驗證法得到識別性能.

圖4顯示了各因素在6個軟件系統(tǒng)中的平均識別性能.從圖中可以看出，移去主題缺陷傾向性因素對整體識別性能的影響最大.變更地點中的語義主題多樣性和Halstead復雜度兩個因素具有最好的識別性能，刻畫變更內容的主題缺陷傾向性和刻畫變更人員的項目經驗因素次之.意圖類型和一周內的天是性能最差的兩個因素.為了進一步驗證各因素在不同項目間性能表現(xiàn)的一致性，本文為每個軟件系統(tǒng)建立因素識別性能向量，然后將6個系統(tǒng)所對應的6個向量兩兩進行Spearman相關性分析.從表4看出，相關性值在0.78～0.91之間，且均顯著(p＜0.05).

圖4 各因素的識別性能Fig.4 Identification performances of features

表4 不同軟件系統(tǒng)間各因素識別性能Spearman相關性Table 4 Spearman correlations between identification performances of features in different projects

由此表明，特征集的各因素在不同軟件系統(tǒng)中的表現(xiàn)較為一致，這一發(fā)現(xiàn)暗示了進一步研究跨項目的引入缺陷細粒度變更識別的可能性.通過特征分析，可以幫助研究者更好地理解軟件開發(fā)過程中缺陷引入的根源.

3.3 成本有效性分析

近年來，在比較不同粒度的分類和預測方法時，軟件工程領域的研究者常采用成本有效性評估策略［16］.該策略將花費的軟件工程活動成本考慮在方法的評估中，比精確度和召回率更加客觀可信［16］.圖5顯示了投入20%人力成本時，本文的細粒度方法(SCC-IM)、文獻［2］中的文件粒度識別方法(File-IM)以及文獻［1］中的事務粒度識別方法(Trans-IM)能夠發(fā)現(xiàn)的引入缺陷細粒度源代碼變更百分比.由于實驗含隨機化成分，因此將每個方法在6個項目上各運行100次.經曼惠特尼U檢驗得出，本文方法可識別平均79%的引入缺陷細粒度變更，顯著優(yōu)于文件和事務粒度識別方法(p＜0.01).

圖5 成本有效性箱線圖Fig.5 Cost-effectiveness box-plots of the three identification methods

4 結論

本文基于機器學習分類思想，提出了一種引入缺陷的細粒度軟件變更識別方法，該方法主要由特征集和分類器兩部分構成.

本文從時間、地點、內容、意圖以及人員5個方面入手構建特征集.通過特征分析實驗發(fā)現(xiàn)，變更地點中的語義主題多樣性和Halstead復雜度兩個因素具有最好的識別性能，刻畫變更內容的主題缺陷傾向性和刻畫變更人員的項目經驗因素次之.此外特征集的各因素在不同軟件系統(tǒng)中的表現(xiàn)較為一致.

本文選擇了缺陷預測領域常用的3種分類器(即K近鄰、裝袋以及隨機森林)來進行訓練和識別.通過分類器性能分析發(fā)現(xiàn)，隨機森林分類器由于對數(shù)據(jù)噪聲具有更強的魯棒性，其性能顯著優(yōu)于另外兩種分類器.

為了驗證本文提出的細粒度識別方法在節(jié)省人力成本方面的有效性，本文開展了成本有效性分析實驗.通過實驗得出，本文方法在投入20%人力成本時，能夠識別平均79%的引入缺陷細粒度變更，顯著優(yōu)于文件和事務粒度識別方法.

由于現(xiàn)有的庫挖掘手段制約，在數(shù)據(jù)收集過程中引入了噪聲，研究噪聲對識別效果的影響并開發(fā)降噪方法是未來工作的重點.

References)

［1］ Aversano L，Cerulo L，Grosso C D.Learning from bug-introducing changes to prevent fault prone code［C］//Penta M D.9th International Workshop on Principles of Software Evolution.New York:ACM，2007:19-26

［2］ Kim S，Whitehead E J，Zhang Y.Classifying software changes:clean or buggy?［J］.IEEE Transactions on Software Engineering，2008，34(2):181-196

［3］ Fluri B，Würsch M，Pinzger M，et al.Change distilling:tree differencing for fine-grained source code change extraction［J］.IEEE Transactions on Software Engineering，2007，33(11):725-743

［4］ Eyolfson J，Tan L，Lam P.Do time of day and developer experience affect commit bugginess?［C］//Deursen A.Proceedings of the 8th Working Conference on Mining Software Repositories.Piscataway，NJ:IEEE，2011:153-162

［5］ Sliwerski J，Zimmermann T，Zeller A.When do changes induce fixes?［J］.ACM Sigsoft Software Engineering Notes，2005，30(4):1-5

［6］ Halstead M H.Elements of software science［M］.Amsterdam:Elsevier North-Holland Press，1977:26-28

［7］ McCabe T J.A complexity measure［J］.IEEE Transactions on Software Engineering，1976，2(4):308-320

［8］ Zimmermann T，Nagappan N.Predicting defects with program dependencies［C］//Mens T.2009 3rd International Symposium on Empirical Software Engineering and Measurement.Piscataway，NJ:IEEE，2009:435-438

［9］ Thomas S W，Adams B，Hassan A E，et al.Modeling the evolution of topics in source code histories［C］//Deursen A.Proceedings of the 8th working conference on Mining Software Repositories.Piscataway，NJ:IEEE，2011:173-182

［10］ Yan R，Huang C，Tang J，et al.To better stand on the shoulder of giants［C］//Boughida K.Proceedings of the 12th ACM/IEEE-CS Joint Conference on Digital Libraries.New York:ACM，2012:51-60

［11］ Graves T L，Karr A F，Marron J S，et al.Predicting fault incidence using software change history［J］.IEEE Transactions on Software Engineering，2000，26(7):653-661

［12］ Pan K，Kim S，Whitehead E J.Toward an understanding of bug fix patterns［J］.Empirical Software Engineering，2009，14(3):286-315

［13］ Chen T H，Thomas S W，Nagappan M，et al.Explaining software defects using topic models［C］//Lanza M.Proceedings of the 9th IEEE Working Conference on Mining Software Repositories.Piscataway，NJ:IEEE，2012:189-198

［14］ Mockus A，Votta L G.Identifying reasons for software change using historic databases［C］//Fadini B.2000 IEEE Interantional Conference on Software Maintenance.Piscataway，NJ:IEEE，2000:120-130

［15］ Hassan A E.Automated classification of change messages in open source projects［C］//Wainwright R L.23rd Annual ACM Symposium on Applied Computing.New York:ACM，2008:837-841

［16］ Hata H，Mizuno O，Kikuno T.Bug prediction based on finegrained module histories［C］//Glinz M.Proceedings of the 34th International Conference on Software Engineering.Piscataway，NJ:IEEE，2008:837-841

［17］ Khoshgoftaar T M，Golawala M，Hulse J V.An empirical study of learning from imbalanced data using random forest［C］//Avouris N.Proceedings of the 19th International Conference on Tools with Artificial Intelligence.Piscataway，NJ:IEEE，2007:310-317