基于信息檢索的缺陷定位:問題、進展與挑戰?

郭肇強 , 周慧聰 , 劉釋然 , 李言輝 , 陳 林 , 周毓明 , 徐寶文

1(計算機軟件新技術國家重點實驗室(南京大學),江蘇 南京 210023)2(南京大學 計算機科學與技術系,江蘇 南京 210023)

軟件缺陷(software bug)是伴隨軟件產品整個生命周期的產物.特別對于大型軟件,由于其復雜的結構和眾多的開發者,缺陷不可避免地在開發過程中被引入.軟件缺陷的存在,極大地降低了軟件質量并且增加了軟件的維護成本,嚴重的缺陷可能會給企業造成經濟損失甚至對人的生命安全造成威脅.為了提升軟件的質量,軟件產品要在不斷更新換代或者版本更迭中對已經發現的缺陷進行清除.從歷史數據來看,對缺陷的清除工作消耗了接近一半的軟件開發和維護成本[1].因此,在學術界有大量的研究者致力于缺陷相關(包括但不限于缺陷預測[2,3]、缺陷定位[4,5]和缺陷修復[6]等)的研究.其中,非常重要并且耗費時間和精力的一個任務是對缺陷進行定位,即找出產生該缺陷的軟件實體(例如源文件).

當軟件中的缺陷被發現時,根據缺陷產生時的軟件狀況,用戶或者軟件系統會記錄缺陷相關的信息,并且生成一份半結構化的缺陷報告上傳到缺陷追蹤系統上[7].軟件維護人員對缺陷的修復工作始于閱讀缺陷報告,在理解缺陷的基礎上,他們從代碼庫中查找與缺陷報告描述內容相關的代碼實體進行審查,直至找出產生該缺陷的位置.值得注意的是:一個在實際開發項目通常包含成百上千甚至更多的源文件,手工從其中找出與缺陷相關的那極小部分代碼是十分困難的.為此,開發人員急需借助于缺陷自動定位工具來輔助他們查找產生缺陷位置.

為了幫助開發人員快速找到產生缺陷的位置,研究者們提出了多種自動化的缺陷定位(bug localization,簡稱BL)解決方法.現有的解決方法可以根據是否需要執行測試用例劃分為動態缺陷定位方法和靜態缺陷定位方法.其中,動態缺陷定位方法要運行被測程序來收集程序執行的動態信息(包括執行路徑和結果等),根據這些信息來定位缺陷語句在代碼中的可疑位置.這類方法的主流思路被稱為基于程序頻譜的缺陷定位[4].由于直接運行目標程序,這類方法通常可以在較細的粒度上對缺陷進行定位,但是需要消耗執行程序的時間和資源成本.因此,這類方法有助于對代碼進行調試.而靜態缺陷定位方法不需要直接運行被測程序,這類方法主要分析代碼和缺陷報告中的靜態信息(包括文本、代碼實體等),然后計算每個代碼實體(源文件)和報告中的靜態信息的相似度分值,最后根據得分將可疑的代碼實體推薦給開發者.靜態方法的優勢在于使用簡單,成本低廉(不需要運行代碼).同時,它的不足是定位粒度較粗糙,通常在文件或者方法級別對缺陷進行定位.可以看出,這類方法適用于幫助開發者快速找到缺陷報告所描述的問題的相關位置.

近年來,靜態缺陷定位研究工作的一類主流方法是基于信息檢索的缺陷定位(information retrieval based bug localization,簡稱IRBL).該領域目前的研究重點在于改良IRBL 方法和完善IRBL 的評價體系兩方面.截止2020 年3 月,已有20 多種(仍在增長)不同IRBL 方法和多種不同的評價指標被提出.從現有研究結果來看,IRBL方法在實驗評估中已經取得了較高的性能.然而,由于現實中不同項目代碼的結構和風格存在差異性,并且收到的缺陷報告內容質量參差不齊,目前的IRBL 方法仍然存在局限性,在現實的實踐應用中仍然面臨一些挑戰.

(1) 方法所用的特征由人工設計,對目標項目依賴高,在其他項目上遷移性能較差;

(2) 目前,這些方法僅在實驗評估中取得較好性能分數,但是由于各自實驗設置的差異性,開發者無法準確判斷哪一種方法最具有實用性.因此,這些方法在生產實踐中的表現結果未知;

(3) 現有方法僅僅給開發者推薦出與缺陷有關的代碼文件列表,沒有包含任何有助于定位的提示信息.

值得注意的是,目前學術界已有多份綜述性的工作[4,8-12]對缺陷定位領域的技術研究進行總結.這些工作對多種特定類型的缺陷定位技術進行了整理和歸納,包括基于程序頻譜的缺陷定位技術[4]、基于程序變異的缺陷定位技術[12]等.但是據我們所知,還沒有一項工作對IRBL 這種特定類型的缺陷定位方向進行總結(截止2020 年3 月).由于對IRBL 研究的論文體量已經較為龐大并且是一類熱門的研究方向,為了彌補這一空白,同時方便后續相關研究工作的進行,本文首次對近10 年來IRBL 的研究歷史進行回顧,對現有的成果進行分類介紹和總結,并在此基礎上指出該領域面臨的挑戰.

本文在第1 節概述主要的研究問題.第2 節說明本綜述的文獻檢索方式和文獻匯總信息.然后,分別在第3節和第4 節從模型改良和模型評估兩個方面介紹近年的研究進展.在第5 節分類別地介紹缺陷定位領域的其他研究方法.在第6 節分析IRBL 領域的研究所面臨的挑戰.最后,在第7 節總結本文的內容.

1 研究問題

1.1 IRBL概要介紹

信息檢索技術早期被用來在代碼中進行概念/特征定位(不同文獻中的術語略有差別:concept location[13-15],feature location[16-18]或者concern localization[19-22])任務,其目的是從代碼庫中找出與特定功能相關的代碼.后來演變為使用信息檢索技術對缺陷進行定位(IRBL),并成為目前主流的靜態缺陷定位研究方法.具體來說,程序中的特征是指能夠被開發者感知或者看見的功能,其中,那些想要被拋棄并且被移除的“功能”便可以看作是一種特殊的特征(即缺陷).特征定位是指從項目中找出具有指定特征的那部分源代碼.因此,對于要在程序中拋棄并移除的“功能”的定位,便逐步變成現有的基于信息檢索的缺陷定位.

IRBL 方法關注的對象是缺陷報告和軟件源碼.從技術角度看,IRBL 方法將缺陷定位任務看作是進行信息檢索(IR)的過程.Rao 等人[23]在2011 年總結了信息檢索領域的IR 術語與軟件工程領域在缺陷定位時所用術語的對照關系如表1 所示.據此,IRBL 任務執行過程可以描述如下:IRBL 模型將缺陷報告看作查詢(query),將報告中的文本進行分詞處理組成查詢語句.同時,將項目源碼看作文檔庫(documents),對每份源文件進行預處理,構造出一個語料庫.當收到缺陷報告時,從報告中構建查詢語句并在文檔庫中檢索(retrieval),根據查詢語句與每個文檔的相似度通過索引(index)將所有文檔降序排列后反饋給開發者.在結果列表中,包含缺陷的文件(buggy files)盡可能排列在靠前的位置.開發者按照列表順序對代碼進行審查,可以在花費較少的工作量的情況下找到有缺陷的源文件,從而加速缺陷定位的進程.

Table 1 Parallels between IR terminology and the more traditional SE terminology表1 IR 術語與傳統軟件工程術語的對照關系

IRBL 方法能夠獲得眾多研究者和軟件開發者的關注主要得益于這類方法在應用時具有以下兩點優勢.

(1) 外部依賴少[24-27].相比于動態定位,技術靜態技術不需要執行測試用例來觸發缺陷,并且不需要工作在可運行的目標軟件系統中,只需要從源代碼和缺陷報告中收集信息即可進行定位.因此,它們具備使用簡單的特點,從而可以應用于軟件開發或維護過程的任何階段;

(2) 計算成本低[24,27].IRBL 方法對源碼文檔的排序的主要依據是缺陷報告與文檔之間的文本相似度,這部分分值的計算對現在的機器來說是十分簡單,通常可以快速給出排序結果.因而這類方法具備反饋迅速的特點,所以在應用時的用戶體驗良好.而動態方法通常需要執行目標程序,實際響應時間和計算成本取決于目標程序的復雜程度.

1.2 IRBL方法流程

本小節對IRBL 方法的流程進行細致描述.綜合該領域的多個優秀的研究工作[24,25,28-32],IRBL 方法的流程主要包含建立語料庫、構建索引、抽取特征、構建查詢以及檢索排序這5 個基本步驟,如圖1 所示.

(1) 建立語料庫.對代碼庫中的每個源代碼文件的文本進行分詞,同時對分好的詞匯進行預處理,主要包括去除關鍵詞(例如“int”“public”等)、去除停用詞(例如“a”“the”等)、詞根還原(例如,“delegating”還原為“delegate”)、拆分復合詞(例如,“TypeDeclaration”分為“type”和“declaration”)等.處理完成之后,每個源文件對應一組詞匯,所有源文件構成了整個項目的語料庫;

(2) 構建索引.為語料庫中的所有源代碼文件構建索引,模型可以在后續步驟中根據索引信息找到指定文件,并對這些文件根據相似度得分進行排序;

(3) 抽取特征.從目標項目中抽取有利于缺陷定位的特征信息(例如版本歷史信息、堆棧信息等).這些特征信息會在第(5)步中集成到檢索模型用于優化排序結果;

(4) 構建查詢.IRBL 方法將缺陷報告當作一條查詢語句.使用步驟(1)中的方法對缺陷報告中的標題和描述進行數據預處理,可以獲得該缺陷報告對應的一組詞匯;

(5) 檢索和排序.使用一種IR 模型(例如VSM[28],LSI[33],SUM[23],LDA[34]等)進行建模,并利用步驟(3)中的特征優化模型,對建立好索引的語料庫計算查詢語句和每個源代碼文件之間的相似程度(例如文本相似度),然后按照相似度得分高低對這些源代碼文件進行降序排序.

經過上述5 個步驟,IRBL 模型會對每份缺陷報告輸出一份排序列表.需要說明的是:除非代碼版本更迭導致源文件內容更新,否則步驟(1)和步驟(2)通常只需要執行一次,而步驟(3)～步驟(5)在每次收到新的缺陷報告后都需要執行.

1.3 IRBL研究內容

目前,IRBL 領域的研究重點是模型改良和模型評估,以下分別從兩方面列出IRBL 研究面臨的主要挑戰并和對應的研究內容.具體內容將在第3 節和第4 節詳細介紹.

1.3.1 模型改良(見第3 節)

IR 模型最初是為檢索非結構化的自然語言文本設計的,因此適合處理純自然語言文本的應用.對于缺陷定位應用來說,不論是軟件庫中的代碼文件還是軟件平臺收到的缺陷報告,其中都包含著豐富的結構信息.當IR模型被直接應用到具有特定結構化信息的軟件代碼庫檢索時,會遇到來自以下兩方面挑戰.

(1) 有用特征使用不完全.對源代碼來說,有大量可以使用的附加特征(如提交歷史[32]、代碼結構[24,25,30,31]等)可以輔助定位缺陷.對缺陷報告來說,其中包含了標題(title)和描述(description)兩部分內容,每部分中包含的詞匯的權重是有差別的[35];

(2) 無用信息過濾不充分.源代碼中的關鍵字是一種干擾詞匯[24,28],例如關鍵字“public”,“class”和“int”等等.這類詞匯對于文本語義沒有任何幫助,并且幾乎會出現在所有的代碼文件中.代碼中的部分注釋組成另一類干擾詞匯,例如,代碼文件的許可證注釋(license comments)通常和文檔語義無關.這類詞匯會影響檢索模型的效果.

上述挑戰使得IRRL 模型的定位性能低下.為了解決上述挑戰,IRBL 領域研究的一個重點在于模型改良.即不斷對模型進行修改以提高其定位準確性.可行的探索方向是挑選較好的IR 模型;從各個角度分析代碼和缺陷報告的特征信息并將其集成到IR 模型中.現有研究人員已經挖掘出包括版本歷史、代碼結構、堆棧蹤跡等多種重要的特征信息(見圖1 中點劃線標明的特征工程路徑);提升缺陷報告的質量;使用深度學習技術自動提取特征等.

1.3.2 模型評估(見第4 節)

IRBL 方法的輸出結果是一個排序列表,因此在對這類方法進行性能評估時,使用的是常用的3 個排序指標Top@K,MRR,MAP.這些指標在評估純排序結果時是客觀公平和有效的,然而在實際使用過程中是否有效,不僅僅取決于排序結果,還與待排序的對象有關.在評估模型時主要有以下3 個方面挑戰.

(1) 評估指標不全面.單純的排序指標并不能得到全面的評價結果.例如:對于缺陷定位來說,開發人員要花費工作量在排序結果中依次審查代碼文件[36,37];

(2) 測試項目不充足.要取得可靠的評估結果,必須要在大量的項目上對模型進行評估.僅在個別項目上的評價結果,在更多項目上測試其泛化性能;

(3) 實驗過程不統一.為了對比不同方法的性能,需要在統一的實驗配置下進行實驗.然而在不同研究者的實驗設置中存在的差異,使得研究者很難得到真實客觀的對比結果.

上述挑戰使得IRBL 模型的良好表現只停留在實驗階段而無法在現實項目中被廣泛應用.為了解決上述挑戰,該領域的另一個研究重點是更加科學全面地評估IRBL 模型,即使用更加合理的評估指標[36]、更加豐富的數據集[26,38,39]和統一的實驗設置對模型進行評估.

2 文獻檢索

2.1 文獻篩選與檢索

IRBL 方法一直是缺陷定位領域的熱點研究問題.近年來,大量的研究工作集中在該領域,并不斷地對定位方法和評價體系進行改善.為了對該問題進行系統的分析、總結和比較,本文的參考文獻力圖覆蓋近10 年來與IRBL 相關的主要研究工作,同時包含缺陷定位領域的其他相關技術的主要文獻.具體來說,本文使用以下的步驟來進行相關文獻的檢索和篩選.

(1) 檢索目標:谷歌學術搜索引擎(Google scholar)、DBLP Computer Science Bibliography、ACM Digital Library、IEEE Xplore Digital Library 以及Springer Link Online Library 等論文數據庫.檢索內容主要包括軟件工程-系統軟件-程序設計語言方向的國際一流會議(ESEC/FSE,ICSE,ASE 等)和一流期刊(TSE,EMSE,IST 等)以及其他重要的會議和期刊如MSR,SIGIR,WCRE 等錄用的文章;

(2) 檢索關鍵詞:包括“bug localization”“locating bugs”“information retrieval”和“fault localization”等以及相近的主題關鍵詞如“text retrieval”;

(3) 檢索起止時間:2000 年～2019 年之間的文獻.需要說明的是:2010 年以前關于IRBL 的相關研究相對較少,所以重點關注2010 年及其之后的文獻;

(4) 文獻審查:首先對檢索出來的文獻進行人工篩選,去除不符合研究主題的文獻;然后檢查選中論文中的參考文獻列表以防遺漏掉未檢索到的文獻;最后,在第2.2 節中對所選文獻進行匯總.

2.2 歷史文獻的匯總

經過文獻的檢索與篩選,本文收集了基于信息檢索的缺陷定位領域中近10 年來的學術論文共82 篇.這些研究論文將會按照種類分別在第3 節和第4 節進行詳細介紹.對于其他種類的缺陷定位相關技術,我們在第5節中對其進行分類和介紹.

表2 列出了基于信息檢索技術的相關文獻的詳細列表.可以看出:在CCF 劃分的軟件工程領域A 類會議上有15 篇,期刊上有6 篇.這表明IRBL 研究是軟件工程領域一個比較活躍的研究方向.圖2 展示了10 年來IRBL領域的研究論文發表的數量分布情況.從圖中可以看出,該領域的逐年論文發表數量呈現出一個波動上升的趨勢.這說明對IRBL 這個領域正越來越受到研究者的重視.在2019 年,相關論文數量有所下降但仍然保持著較高的活躍度.

Table 2 List of related literature on IR-based bug localization researches表2 基于信息檢索的缺陷定位研究的相關文獻列表

3 IRBL 模型的改良

對IRBL 模型的改良研究在不同研究階段有不同的側重點.圖3 展示了基于信息檢索的缺陷定位方法從2010 年以來的模型改良趨勢和側重點.同時,我們在表3 中列出了現有的代表性的IRBL 模型匯總比較信息.根據對現有研究的匯總,我們得出IRBL 領域的研究側重點主要包含以下4 個方面.

(1) 更換檢索模型.早在2010 年及以前,由于IR 技術剛剛被應用到缺陷定位領域,研究者的研究重點是嘗試使用不同的IR 模型對缺陷定位任務進行建模來找出該領域比較合適的IR 模型(例如VSM,LDA,SUM,LSI 等);

(2) 使用特征分析.約從2011 年開始,研究者們發現,單純使用IR 模型定位缺陷的性能低下很難滿足實際的應用需求.研究者們發現:除了文本相似度之外,軟件中的其他特征也可以幫助定位缺陷.所以,這一階段的研究者們主要集中在挖掘軟件項目中與缺陷有關的特有特征(例如項目版本歷史、缺陷堆棧等),并結合使用這些特征和IR 模型來提升缺陷定位在測試項目上的性能;

(3) 進行查詢重構.作為查詢語句的缺陷報告是由不同的人員提交的,所以質量參差不齊.這些低質量的查詢導致很多IRBL 模型表現較差,因而在2013 年后出現一些研究者著重于對查詢進行重構,以改善現有IRBL 模型的查詢準確性;

(4) 應用深度學習.隨著深度學習技術的發展,從2017 年起,不少研究者開始嘗試使用深度學習模型(如卷積神經網絡CNN)對特征進行自動提取,然后結合信息檢索技術對缺陷進行定位.

Table 3 Summary of representative IR-based bug localization models表3 基于信息檢索的缺陷定位代表性模型匯總

Table 3 Summary of representative IR-based bug localization models (Continued)表3 基于信息檢索的缺陷定位代表性模型匯總(續)

3.1 更換檢索模型

在信息檢索領域有很多模型,其中最常見的包括向量空間模型(vector space model,簡稱VSM)[106]、潛在語義索引模型(latent semantic index,簡稱LSI)[107]、隱狄利克雷分布模型(latent Dirichlet allocation,簡稱LDA)[108]等等.經過多年研究,IRBL 領域的方法中所用的檢索模型已經涵蓋了上述所有以及其他更多的IR 模型.

3.1.1 VSM 模型

VSM 是將自然語言文檔庫轉化為一個字詞-文件矩陣的向量模型.矩陣的每一行代表一個單詞在不同文件中的權重值(可以通過TF.IDF[109]來表示),每一列代表一個文檔所對應的特征向量.在字詞矩陣的基礎上,我們可以很容易地通過向量距離計算來衡量不同文檔之間的相似性.因此,在IRBL 領域現有的方法中,VSM 和它的變體是使用最廣泛的IR 模型.

在現有的研究中,大約有超過半數的IRBL 方法[25,28,30-32,35,47,50,63,68,74,79,80,90,92]都使用VSM 模型來進行建模.以下是該模型的相關應用.

2009 年,Gay 等人[110]提出一個使用相關反饋(relevance feedback)機制的方法來提升概念定位的結果.在他們的方法中,最先明確使用VSM 模型來進行檢索.2012 年,Zhou 等人[28]指出,傳統VSM 模型更傾向于將長度較短的文檔排在前面,而已有研究表明,長度較大的文檔包含缺陷的可能更高.基于這點認識,他們對VSM 模型進行改進,提出了rVSM 模型,其中,將文檔長度作為一個權重參數.后續有多個研究工作(Wong 等人[30]、Rahman等人[103]、Youm[74]等)均是在rVSM 模型之上構建新的IRBL 方法.2014 年,Wang 等人[50]設計了基于搜索的引擎VSMcomposite,該引擎使用遺傳算法(GA)將各種不同的VSM 變體(即,向量元素的計算方式不同)模型進行組合,得到新的近似最優組合模型來進行缺陷定位.

3.1.2 LSI 模型

LSI 是一種實用的主題模型[107,111],它是在傳統的VSM 模型基礎上進行改良后得到的.LSI 利用奇異值分解(singular value decomposition,簡稱SVD)將詞匯和文本映射到一個新的空間來表示文檔矩陣之間的潛在語義關系.它的優勢是可以解決詞語中出現的同義詞和多義詞對結果的影響,這些詞匯是無法被VSM 模型識別處理的.然而,它的缺點是需要進行高階矩陣運算來計算查詢字段和每篇文檔的相似度,所以運行速度慢于VSM 模型.其次,在使用SVD 時需要假設數據的分布是正態分布,然而類似詞頻的統計數據往往不能符合這個條件.經過對文獻的整理,我們發現:在IRBL 領域LSI 是最早被用來進行特征/缺陷定位的IR 模型,并且只活躍在研究早期(2010 年以前).近年來,幾乎已經沒有方法使用LSI 作為IR 模型來進行缺陷定位.以下是該模型的相關應用.

2004 年,Marcus 等人[13]最先將LSI 模型應用到概念定位領域中.2006 年,Poshyvanyk 等人[16]將特征定位視為一個決策問題,他們使用LSI 模型和基于場景的事件概率排序兩種技術來強化定位結果.隨后,他們在2007 年又在LSI 模型基礎上提出了PROMESIR 模型[18]進行特征定位.同年,Liu 等人[17]將LSI 模型和代碼執行蹤跡以及代碼中的注釋和標識符信息相結合來提升定位性能.考慮到現有技術沒有使用到軟件倉庫的動態特性,Rao等人[87]在2015 年提出了一個可以隨著數據演化增量更新LSA 模型參數的定位框架.

3.1.3 LDA 模型

LDA 是一種生成式的統計主題模型,同時也是一種典型的詞袋模型.它將一篇文檔看成是詞語之間沒有先后順序和上下文關聯的一組詞語集合,文檔中的這些詞語屬于多個主題,并且每個詞語都由其中一個主題生成.LDA 模型在模塊化和可擴展方面強于LSI 模型.與此同時,它在基于主題模型的信息檢索應用上十分有效.在IRBL 領域里,LDA 模型也是在早期研究中就被應用到IRBL 領域中,并且在近年來仍有部分研究關注于改良LDA 模型.以下是該模型的相關應用.

2008 年,Lukins 等人[27]就明確提出使用LDA 模型檢索源代碼進行缺陷定位.在2010 年,他們再次使用LDA模型來構建IRBL 方法[3].他們得出結論,基于LDA 的缺陷定位方法的定位準確度與目標項目尺寸或者源代碼的穩定性沒有顯著關聯.因此,LDA 有廣泛的應用前景.在2011 年時,Nguyen 等人[49]提出了基于LDA 主題模型的新方法BugScout,使得缺陷定位效果有明顯提升.2018 年,Wang 等人[98]在他們的方法STMLocator 中使用了LDA 模型,并且利用代碼庫的歷史信息來進行有監督的學習,進一步發掘了LDA 模型的性能.

3.1.4 其他IR 模型

除了上述3 種主流的IR 模型之外,還有其他一些模型也被某些研究者用來進行缺陷定位.

2010 年,通過聚集和挖掘被相同位置共同引用的歷史缺陷報告,Chen 等人[85,112]提出一個有效的使用協同位置收縮(co-location shrinkage,簡稱CS)技術的支持向量機模型(CS-SVM)來檢索潛在的缺陷位置.2011 年,Rao等人[23]使用平滑一元模型(smoothed unigram model,簡稱SUM)進行缺陷定位工作.在他們的實驗結果中,SUM的缺陷定位性能比VSM,LSI 和LDA 都要優秀.2012 年,Sisman 等人[60]使用DFR 偏離隨機性(divergence from randomness,簡稱DFR)模型進行缺陷定位.該模型會根據文檔特征概率與純非判別隨機分布的差異,來評估文檔對查詢的恰當性.

除了手動構建IR 模型,還有一些研究使用了現成的信息檢索工具.例如,Saha 等人[24]在他們的方法BLUiR中使用了Indri[113],Kilinc 等人[90]和Rahman 等人[35]則使用Apache Luence 作為他們方法的檢索模型.

3.2 使用特征分析

直接應用IR 模型進行檢索很難得到令人滿意的結果,因此需要進一步進行特征分析來改良IRBL 模型.代碼庫和缺陷報告都不是由純自然語言組成的文本,它們具有一些領域相關的結構化信息和特征.對這些特征進行挖掘,可以在一定程度上提升檢索結果的準確性.綜合現有文獻的研究,我們發現對,代碼庫和缺陷報告提取的特征主要包括版本歷史、相似報告、代碼結構、堆棧蹤跡以及其他一些不常用的特征.本小節從提取特征的角度來介紹現有研究如何通過對特征進行細致地挖掘來提升定位模型的性能.

3.2.1 版本歷史

軟件項目在演化過程中會通過版本更迭來實現對項目的更新和完善(例如修復缺陷、添加新功能等),每一次變更都會向代碼庫中添加豐富的歷史信息(例如日志信息、文件變動信息等).與此同時,多數缺陷正是在代碼變動的過程中因為開發人員主觀疏忽或者是客觀設計不合理而被引入到項目中,所以分析版本這些歷史信息有利于為缺陷定位或者預測任務帶來一些提示性的幫助.在現有的IRBL 方法中,很多方法已經將版本歷史信息作為一個重要的特征組件來提升方法的性能.版本歷史特征的應用示例過程如圖4 所示.

2010 年,Chen 等人[85,112]利用歷史缺陷報告和歷史被修復的模塊信息為新收到的缺陷尋找可能的位置,其中特別利用了缺陷報告之間的共位置關系.在他們的方法中,如果兩個缺陷報告的修復模塊相同,那么認為這兩個缺陷報告有共位置關系.

2012 年,Sisman 等人[60]挖掘版本歷史時應用到以下兩點先驗知識:(1) 在短期內被多次提交的修改很可能會包含缺陷;(2) 歷史上包含缺陷的文件在之后版本中可能仍然有缺陷.其中,先驗知識(1)也被應用在Rahman等人[103]的方法中.相比前兩個方法,Wang 等人[31]和Youm 等人[74]考慮到新發現的缺陷通常是由最新的提交引入而非遠古提交,因此在他們的方法中,只考慮近期的版本歷史而完全丟棄距提交的新缺陷報告超過k天的版本歷史信息.

2013 年,Tantithamthavorn 等人[29]挖掘代碼文件之間的共同變更歷史信息調整現有方法BugLocator[28]的結果.挖掘步驟如下:首先找出先前所有被修復的文件,并根據其所屬的變更構建一個共同變更矩陣,矩陣中的元素代表兩個文件之間的共同變更一致性;然后,對BugLocator 生成的列表從共同變更矩陣尋找一致性較高的文件提升它們的排名.相比之下,共同變更歷史信息可以對原方法的結果產生顯著提升.

2016 年,Wen 等人[32]在產生缺陷之前版本歷史中,把每個變更塊(change hunk,包括變更行的內容、變更日志等)索引為一個文檔,并從這個文檔構建自然語言和代碼實體兩個語料庫.此外,提取每個源文件的缺陷修復歷史后計算一個加強得分,并將其用作指示源文件包含缺陷可疑度的另一個特征.他們的定位模型不僅可以在文件級別定位缺陷,同時首次提出在變更級別定位缺陷,即定位引入缺陷的變更.這可以幫助開發人員更容易找出產生缺陷的原因.

3.2.2 相似報告

相似缺陷報告是另一類重要的輔助特征.一個直觀的理解是:若兩個缺陷報告在描述上具有較高的相似度,那么這兩個報告所對應的缺陷文件有很大概率有重疊的部分甚至完全一致.在這個基礎上,可以先收集已經定位到產生缺陷位置(例如源文件)的相似缺陷報告,適當增加這些位置的可疑度分值,可以在一定程度上提升IRBL 結果的性能.相似報告特征的應用示例過程如圖5 所示.

2012 年,Zhou 等人[28]在他們的方法BugLocator 中使用到了相似缺陷報告特征.對于新收到缺陷報告,他們首先在rVSM 模型的基礎上計算出該缺陷與每個源文件的文本相似度分值;然后計算該報告與歷史上已經解決的缺陷報告之間的相似度;接著,對歷史上有缺陷的文件根據其對應的歷史缺陷報告進行加權,得到這部分文件的歷史特征分數;最后結合兩部分的分數,將所有文件倒序排列作為最終的推薦結果.

Zhou 等人使用相似缺陷報告特征的方法在后續多個研究工作中被應用.Saha 等人[24]在BLUiR 變體中、Wong[30]等人在BRTracer 變體中、Wang 等人在AmaLgam[31]和改良版AmaLgam+[80]中都以同樣的方式使用到了相似缺陷報告信息.2017 年,Youm 等人[74]在 BugLocator 的基礎上用到了歷史缺陷報告中的評論信息(comment)來強化定位方法.

3.2.3 堆棧蹤跡

堆棧蹤跡是缺陷產生時代碼執行的異常信息.這些信息是高度結構化的,其中包含了異常的類型(例如空指針異常和地址超界等)和出錯代碼所執行的路徑信息(例如代碼行、類名、方法名).因為缺陷所在的位置很可能在于這個出錯路徑上,所以堆棧信息對于開發人員手動進行缺陷定位是十分重要的.而在研究定位工具時,也可以通過提取堆棧中的信息(例如出錯的類名)進一步強化工具的定位準確度.

堆棧蹤跡特征的應用示例過程如圖6 所示.

2014 年,Moreno 等人[25]考慮將堆棧蹤跡信息應用到他們的方法Lobster 中.他們使用缺陷報告中的堆棧蹤跡和軟件源碼中的程序依賴圖來尋找在結構上相似的代碼元素.具體說:對于給定的堆棧蹤跡和代碼元素,他們之間的結構相似性被定義為堆棧蹤跡中元素和代碼中元素的最小距離.同年,Wong 等人[30]使用正則表達式從缺陷報告的堆棧中提取所有的文件名以及對應的方法.在得到一組可疑的文件集合后,將上述文件對應方法中直接使用到的類所對應的文件也加入到可疑文件集合,最后通過提高對這些文件在結果中的排名來改善定位結果.2017 年,Youm 等人[74]在他們的方法BLIA 中集成了Wong 等人對堆棧蹤跡的處理方法.

2016 年,Wang 等人[80]在他們的改良方法AmaLgam+使用了堆棧蹤跡特征.他們提出一個直觀假設:若某個類的引用距離堆棧頂部越近(出錯位置),那么這個引用所在的文件越可能包含該缺陷.因此,他們設計了一個堆棧分數來度量堆棧中出現的每個文件的可疑程度.對每缺陷報告中的堆棧,他們首先按序提取出所有文件名并進行去重處理,然后使用每個文件排名的倒數作為該文件與缺陷報告在堆棧上的可疑程度.

2018 年,Rahman 等人[35]利用堆棧蹤跡來重新查詢.他們從堆棧蹤跡中提取代碼實體(類名和方法名).根據執行順序構造出權重圖,并在圖上面應用PageRank 算法計算出每個代碼實體的權重來重新構造查詢語句.

3.2.4 代碼結構

項目中的源代碼是一種結構化文本,它的內容是由各種不同的代碼實體(例如類名、方法名等)組成.直接將它們看作自然語言文本處理會丟失其中的結構化信息,會導致定位結果準確率低下.合理利用這些結構特征,可以幫助進一步提升自動工具的準確性.代碼結構特征的應用示例過程如圖7 所示.

2013 年,Saha 等人[24]在設計模型時首先考慮到代碼結構特征.對于代碼庫來說,他們使用Eclipse JDT 解析源代碼的AST 樹,并提取其中的4 種代碼實體(類名、方法名、變量名和注釋)信息;對于缺陷報告,他們分別使用標題和描述構建兩種查詢.上述代碼實體和查詢共有8 種不同的組合方式,他們分別計算每種組合的分數,然后將所有組合的分數相加作為某個源文件的最終分數.最后,他們依據該分數向開發者推薦有缺陷的文件.

2016 年,Kilinc 等人[90]提出了BugCatcher 方法,該方法首先使用基礎的檢索方法對源代碼進行檢索獲得一個排序結果;然后,從代碼中提取類名、方法名和注釋分別建立索引,并且根據這3 類信息對首次結果進行重排;最后使用一種用到重新索引的縮小范圍技術計算最終結果.同年,Wen 等人[32]提出了Locus 方法.該方法對自然語言和代碼實體分別構建語料庫和查詢語句,將兩個查詢結果組合起來輸出變更塊(change hunk)的排序,并在此基礎上選出可以的文件或者變更.

2018 年,Dilshener 等人[79]提出一種不需要歷史信息,僅使用結構和堆棧信息的缺陷定位方法.同年,Swe 等人[99]將代碼結構細分為類名、方法名和變量名分別處理來避免代碼文件過大對結果帶來的影響.Rath 等人[97]研究了缺陷報告中的結構信息對IRBL 方法的影響.他們的結果表明:堆棧蹤跡會傾向于降低缺陷定位的性能,并且需要額外的處理.

3.2.5 其他特征

除了上述4 種被大量使用的特征之外,還有一些現有研究[30,74,79,80,103]挖掘了源代碼和缺陷報告中的其他隱藏的對缺陷定位有利特征.這些工作也在一定的場景下改進了IRBL 方法,并提升了它們的定位性能.

2014 年,Wong 等人[30]考慮到缺陷通常發生在源文件中的小部分代碼里,而某些源文件的尺寸很大,會嚴重降低VSM 模型的準確性,因此,他們將每個的源文件按照某一閾值(例如100 行代碼)分為若干大小相等片段,并在此基礎上計算每個片段與缺陷報告的相似性.然后,用得分最高的片段代表該文件.分段操作消除了文件大小對定位模型的影響.該特征在2017 年也被Youm 等人[74]應用在他們的方法BLIA 中.

在某些缺陷報告中會記錄代碼庫里出現的源文件名或者方法名等代碼實體信息,這些信息往往與缺陷關聯密切.因此,Rahman 等人[103](在2015 年)和Dilshener[79](在2018 年)在他們的定位方法中提高了這些出現在缺陷報告中的代碼實體所對應的源文件(或者源方法)所在的最終排序列表中的優先級來獲取更加可靠的結果.

2016 年,Wang 等人[80]提出了使用缺陷報告中的報告者信息來提升定位性能的方法AmaLgam+.他們的直觀理解是,一個報告者很可能去報告與相同/相似的代碼組件有關的缺陷.因此,當受到新的缺陷報告時,查看該報告者之前提交的缺陷報告和對應的包含缺陷的文件對于新缺陷的定位有幫助.

3.3 進行查詢重構

在一定程度上來說,由于大量研究已經對代碼庫和缺陷報告中的相關特征進行了比較充分的挖掘,很難再提取新的特征來改良IRBL 方法.研究者從改善查詢的角度提出了查詢重構(query reformulation,簡稱QR)的策略來提升性能.這類策略的一個優勢是獨立于IRBL 方法本身,可以作為一個預處理步驟集成到現有的IRBL 方法中,因此它的可移植性較好.查詢重構的應用場景如圖8 所示.開發者首先使用自動方法構建初始查詢并獲取一個結果列表.當他們在排名靠前的代碼中沒有找到缺陷時,就請求進行查詢重構重新獲取推薦結果.

需要重構的對象是用來構建查詢語句的缺陷報告,因此,對缺陷報告的組成部分及特征有全面的理解十分重要.在實際使用過程中,開發者也是需要根據初始查詢的反饋結果來決定是否需要使用查詢重構策略.因此,對缺陷報告的分析是進行查詢重構的前序工作.根據研究的前后承接關系,我們將這部分相關內容分為缺陷報告分析和查詢重構策略兩個部分來介紹.

3.3.1 缺陷報告分析

2008 年,Bettenburg 等人[70,114]對現實項目中(例如Apache)的開發者和用戶進行一項調研.他們發現,用戶提交的報告內容與開發者希望收到的信息之間不匹配.開發者想要得到的信息是復現步驟、錯誤堆棧和測試用例等,然而用戶很難提供這些信息.為了解決這個問題,他們提出一個原型工具CUEZILLA 來測量缺陷報告的質量,并且能夠向用戶推薦填寫缺陷的信息來提升報告質量.

2014 年,Kochhar 等人[48]總結了會影響缺陷定位有效性的潛在偏好:

1) 被錯誤分類的缺陷報告.被標記為缺陷的問題報告并非總是由缺陷引起,也包含了文檔更新、代碼重構等;

2) 已經可定位的缺陷報告.缺陷報告中可能已經指出了有缺陷的程序文件,沒有必要對這些報告使用缺陷定位工具;

3) 不正確的真實值.在修復缺陷的更新提交中被修改的文件中,可能并非所有文件都與這個缺陷有關.

他們的實驗結果表明,偏好(2)對IRBL 有效性有顯著影響,因此應當在后續研究中被糾正.

2018 年,Mills 等人[53]對缺陷報告進行調研,他們發現,缺陷報告中的大多數詞匯的確可以用來構建有效查詢語句,從而使得在沒有輔助查詢擴展的情況下,可以成功進行缺陷定位.在此基礎上,他們設計了一種遺傳算法(GA)來分析帶有和不帶有定位提示(localization hint,例如方法名)的缺陷報告文本,以獲得一個接近最優的查詢,該查詢提高了缺陷報告在IRBL 應用中的潛力.然而在同年,Lawrie 等人[52]研究了缺陷報告在IRBL 中的價值.他們指出:GA 算法存在作弊(cheats)問題,因為GA 算法根據查詢的性能評估值來產生優質的查詢.然而在現實場景中,一個查詢的性能評估值是未知的,因此不具備實用性.

2019 年,Rath 等人[84]著重分析了缺陷報告中結構化信息對IRBL 方法的影響.他們發現,缺陷報告中的堆棧蹤跡信息更傾向于對缺陷定位結果產生負面影響,因此對包含這類信息的報告需要特別處理.與此同時,相比于只包含自然語言的缺陷報告,那些包含源代碼信息的缺陷報告不僅可以提升BL 算法的性能,而且有助于開發人員更快找到缺陷位置.

3.3.2 查詢重構策略

2013 年,Sisman[61]首先將查詢重構策略應用到缺陷定位領域中.在不需要用戶提供額外的輸入信息的情況下,他們的QR 框架的工作原理是先進行一次初始查詢得到相關的軟件制品(artifact,例如文件)排名列表,然后從排名靠前的制品中抽取附加的詞匯來擴充查詢語句.

2017 年,Chaparro 等人在文獻[40,46]中將缺陷報告的內容詳細地劃分為 OB(observed behavior),EB(expected behavior),S2R(step to reproduce)這3 個部分,他們使用啟發式的規則識別和檢測這3 部分內容,并發現多數缺陷報告中缺少EB 和S2R 這兩部分內容.接著,他們在文獻[51]中進行對比實驗,發現使用OB 替代整個報告的內容來構造查詢語句,是一種簡單有效的方法來重構低質量的缺陷報告.在此基礎上,Chaparro 等人[73]在2019 年了擴大了實驗對象和數據集,發現使用OB 和報告標題的組合內容替代整份缺陷報告來定位能夠達到更好的效果.

2018 年,Rahman 等人[35,42]提出使用一種上下文感知的查詢重構方法BLZZARD.他們的重構方法對缺陷報告中的兩類重要信息——堆棧蹤跡和程序元素(例如類名、方法名等)分別構造蹤跡圖和文本圖模型,對這兩部分中的詞匯進行建模.在構造好的圖模型基礎上,使用PageRank 算法對圖中的詞匯進行加權,并根據權重來選取加入查詢語句的詞匯.

2019 年,Kim等人[102]提出目前最新的自動查詢重構方法.他們的方法包含3個組件:1) 缺陷報告擴展;2) 候選詞提取;3) 查詢擴展.首先,他們使用缺陷報告中的附件信息(attachment)擴展缺陷報告;然后,在提取候選詞時,通過將情感詞匯加入到停用詞表來將它們移除,并且使用偽相關反饋的方式從源碼中檢索文件并移除噪音文件;最后,他們對檢索到文件中的詞匯加權,并選擇權重較高的部分來擴展查詢語句.

3.4 應用深度學習

隨著深度學習技術的發展,近年來,研究者們將深度學習技術引入缺陷定位領域.相較于基于信息檢索的缺陷定位只考慮了缺陷報告和源代碼文本上的特征,基于深度學習的缺陷定位方法可以提取缺陷報告和源代碼文件更深層和更高維的抽象特征.這類方法可以減少人為設計特征的工作量,同時也提高了缺陷定位的準確率.

2017 年,Lam 等人[55]將深度神經網絡(DNN)與信息檢索技術中的rVSM 相結合進行缺陷定位.首先,他們使用rVSM 收集缺陷報告和源代碼文件之間文本相似性的特征;然后,他們用DNN 來學習缺陷報告中的術語,并將它們與源代碼中潛在不同的代碼字段關聯起來.實驗證明:深度神經網絡和信息檢索技術可以很好地相互補充,能夠實現比單個模型更高的缺陷定位精度.

2018 年,Xiao 等人[64]提出一個深度學習方法,在字符級別解釋缺陷報告,并使用語言模型來進行分析.該方法類似于機器翻譯,首先將缺陷報告和源代碼文件用字符表示,然后將結果傳入到CNN 模型中進行卷積操作,最后把CNN 的結果應用在基于RNN 的編碼器-解碼器中進行缺陷定位.

同年,Xiao 等人[96]使用卷積神經網絡和級聯森林對語義信息和結構特征建模.首先,采用具有多個過濾器的卷積神經網絡和具有多粒度掃描的隨機森林集合,從缺陷報告和源文件中提取詞向量的語義和結構特征;隨后從級聯森林進一步提取更深層次的特征,并觀察缺陷報告與源代碼文件之間的相關關系.

2019 年,Xiao 等人[77]提出使用詞嵌入和強化的卷積神經網絡來提升缺陷定位性能.他們使用詞嵌入來表示缺陷報告和源文件中保留語義信息的單詞,并使用不同的CNN 模型來提取它們的特征.Polisetty 等人[101]研究了基于深度學習的缺陷定位模型是否能夠滿足參與人員的需求,他們的結果表明:雖然深度學習模型比經典的機器學習模型表現得更好,但它們只能部分滿足研究者實驗中設定的采用標準.Huo 等人[69]提出了一種跨項目缺陷定位的深度遷移學習方法.使用他們所提出TRANP-CNN 方法,可以從源項目中提取出可轉移的語義特征,充分利用目標項目中的標記數據進行有效的跨項目缺陷定位.

3.5 小 結

本節從更換檢索模型、使用特征分析、進行查詢重構和應用深度學習這4 個方面詳細介紹了在改良IRBL模型近年的研究進展.下面簡述主要發現:

(1) 相比于其他IR 模型,VSM 作為一種簡單的IR 模型,能夠在IRBL 的研究中獲得較好的性能.因此,目前超過半數的IRBL 方法都使用VSM 或者VSM 的變體作為他們方法中IR 模型;

(2) 從代碼庫和缺陷報告中挖掘出的特征里,對提升缺陷定位方法性能十分有效的是版本歷史、相似報告、代碼結構和堆棧蹤跡這4 種特征,并在大量研究中被以不同的方式集成到他們的IRBL 方法中;

(3) 查詢重構是一種獨立于具體定位方法的優化策略,因此,它可以作為一個預處理步驟集成在任何現有的IRBL 方法中,具有很好的可移植性;

(4) 將深度學習模型應用到基于信息檢索的缺陷定位中,可以自動地從代碼和缺陷報告中提取特征.最新的研究顯示了深度學習模型在缺陷定位應用中十分有效.

4 IRBL 模型的評估

本節介紹IRBL 模型評估方向的研究進展,根據對現有文獻的分類,主要從模型比較、評價指標和實驗數據這3 個部分展開介紹.

4.1 模型比較

研究者在提出新的IRBL 方法時,會設計實驗來驗證新方法的有效性.然而通常的情況是,不同研究者在設計實驗時不能夠完全確保實驗的一致性(即:與基準方法使用的實驗設置是否一致,是否正確復現了基準方法)與合理性(即實驗設置是否存在問題).這些因素可能會使得實驗結果不能準確顯示新方法的真實性能,從而誤導后續的研究工作.

為了獲得比較真實客觀的實驗結果,一些研究工作致力于設置公平的實驗對已有定位方法或者IR 模型的效果進行比較和評估的實證研究,我們簡稱為模型比較研究.這類研究的好處在于以下3 個方面[89]:(1) 對研究者,幫助他們理解現有模型的優缺點和真實效果,并在此基礎上研究更有效的定位方法;(2) 對缺陷定位編程人員,幫助他們理解如何更好地使用現有方法來達到理想的定位結果;(3) 對缺陷報告者來說,幫助他們在提交缺陷報告時填寫對定位缺陷最有用的信息來加強缺陷定位的成功.

4.1.1 對不同參數性能的比較

2011 年,Thomas 等人[66]在超過8 000 個缺陷報告上實證調查了分類器參數(總共3 172 種參數設置)和不同分類器組合對缺陷定位的影響.他們主要得出兩個結論:(1) 分類器的參數設置對性能有顯著的影響;(2) 使用不同分類器組合的結果優于使用任意單獨的分類器.

2018 年,Tantithamthavorn 等人[76]研究了IR 分類器的配置參數對方法級別缺陷定位的性能和工作量的影響.他們的主要結論如下:(1) 即使在分類結果的排序性能相似的情況下,不同的參數對分類結果的工作量有十分顯著的影響;(2) 在方法級別表現較好的參數設置可以應用到文件級別,反之亦然.他們最后強調,在評估方法時應當考慮審查結果所花費工作量.

4.1.2 對不同模型性能的比較

2011 年,Wang 等人[19]在一個大型的Linux 內核數據集上比較了10 種不同IR 技術的關注點定位(concern localization)方法.他們的結果顯示:(1) 簡單的IR 模型(如VSM 和SUM)比復雜的模型(如LDA)定位效果要好;(2) 相同的IR 技術在不同系統上處理不同應用時的表現有差異;(3) 基于IR 的關注點定位技術在大型軟件系統中和小型軟件系統中一樣有效;(4) 現有的IR 技術在處理軟件語料庫時,效果差于處理自然語言的語料庫.

2015 年Alduailij 等人[89]使用統計推斷比較3 種文本模型(VSM,LSI,LDA)在方法級別缺陷定位時的性能.他們得出結論是,VSM 是比較好的模型.接著,他們研究了額外參數對VSM 性能的影響,包括方法長度、查詢長度、方法的文檔注釋以及缺陷報告中提及的產品名稱和組件名稱.他們發現,VSM 與大多數被測的參數正相關.

2018 年,Shi 等人[94]對混合缺陷定位方法(hybrid bug localization,即同時使用IR 相似度和附加特征的方法)進行研究.他們比較了8 種不同的LtR 技術在使用4 種歸一化方法時的性能表現.他們發現,LtR 的表現好于最新的BLUiR[24]和AmaLgam 方法[31].

4.1.3 對不同實驗方案的比較

一些研究者指出:在進行模型比較的實驗驗證過程中存在不合理的設置,這些不合理的設置會影響實驗結果的準確性.2018 年,Kim 等人[41]發現,現有研究的實驗數據集中包含一些non-buggy 文件(例如測試文件).他們指出:將這些文件包含在數據集中會影響現有技術的可靠性,所以在以后實驗方案中應當被去掉.根據他們在排除測試文件的數據集上的實驗結果,被多數研究者作為基準方法的BLUiR[24]的實際定位效果并沒有原文實驗中表現得那么好.Kim 等人[41]指出的不合理的實驗方案在得到認同,例如,Lee 等人[39]在他們的實證研究中排除了數據集中的測試文件.

4.2 評價指標

評價指標是度量方法有效性的重要依據.針對不同模型的輸出結果,研究者使用多種類型的指標對結果進行評價.本節從排序性能、分類性能和工作量這3 個角度介紹IRBL 領域的評價指標.

4.2.1 評估排序性能的指標

目前,大多數IRBL 領域的研究都將缺陷定位視為一個排序任務,對于給定的缺陷報告,定位方法會輸出一個根據其包含缺陷可能性從大到小排序的文件列表.因此,大量研究使用排序指標來評價IRBL 方法的性能.表4對排序性能評估指標的計算方法和使用情況進行了匯總.這些指標的具體含義如下.

(1) Top@K.表示對缺陷定位方法生成的推薦列表中前k個文件進行審查時缺陷定位方法定位成功的概率.特別地,給定一個待定位的缺陷報告,如果缺陷定位方法生成的推薦列表的前k個源代碼文件中至少有一個與給定的缺陷報告相關,則認為定位成功;

(2)MRR(mean reciprocal rank).測量的是缺陷定位方法定位到的首個與缺陷報告相關的源代碼文件在排序列表中的位置;

(3)MAP(mean average precision).測量的是缺陷定位方法定位到的所有與缺陷報告相關的源代碼文件在排序列表中的位置;

(4)E(effectiveness).表示在找到一個與缺陷報告相關的文件之前最少需要被開發者審查的源文件數目.

前 3 個指標的值越大,說明包含缺陷的文件在結果列表的位置越靠前,即方法的排序性能越好;而Effectiveness 的值越小,方法的性能越好.從表4 可以看出:其中,Top@K,MRR和MAP是應用最多的3 種指標,分別在40,38 和46 篇文獻中被用來評估IRBL 方法.

Table 4 Summary of evaluation metrics for IRBL models in terms of ranking performance表4 評價IRBL 模型的排序性能指標匯總

4.2.2 評估分類性能的指標

在信息檢索領域,另一類重要的指標是用來評價一種方法的分類性能.然而,由于IRBL 的輸出結果是一個序列,分類指標不能被直接用于對這些方法進行評價.現有部分研究[60-62,86]的做法是,設置一個排名閾值將該序列分成兩種類型,即:在排名之前的文件包含缺陷,反之不包含缺陷.

從二分類的角度來看,IRBL 方法的定位結果總共可以劃分為以下4 種可能情況.

· 對于一個被定位為包含該缺陷的文件,它的確包含該缺陷,這種結果屬于TP(true positive);

· 對于一個被定位為包含該缺陷的文件,它并不包含該缺陷,這種結果屬于FP(false positive);

· 對于一個被定位為沒有該缺陷的文件,它的確包含該缺陷,這種結果屬于FN(false negative);

· 對于一個被定位為沒有該缺陷的文件,它并不包含該缺陷,這種結果屬于TN(true negative).

現有的二分類評價指標是基于上述4 種情況的統計技術來計算的.表5 對這些分類性能評估指標的計算方法和使用情況進行了匯總.這些指標的具體含義如下.

(1) Precision(精度):在預測為有缺陷的文件中,有多少比例的文件真正與該缺陷相關;

(2) Recall(召回率):在所有與缺陷相關的文件中,有多少比例的文件被定位為與該缺陷相關;

(3)F1-score(調和平均值):精度和召回率的調和平均值,可以更加客觀地評價分類結果;

(4) Accuracy(準確率)[85]:在所有分類結果中,正確分類的文件(包括正確分為與缺陷相關和正確分為與缺陷無關的文件)占所有文件的比例;

(5) MCC(Matthews correlation coefficient,馬修斯相關系數)[82]:表示的是真實類別和預測類別的二元分類之間的相關系數.

這些指標的計算與設定的排名閾值有關,即:在排名閾值之前的文件被定為包含某缺陷,反之不包含該缺陷.因為在沒有閾值的情況下,任何結果是沒有意義的.例如,召回率都為1.0 而精度都為k/K(K是項目中所有文件的數目,k是其中包含缺陷的文件數目).在這些指標中使用最多的是精度和召回率,它們都在11 篇文獻中被使用過.

Table 5 Summary of evaluation metrics for IRBL models in terms of classification performance表5 評價IRBL 模型的分類性能指標匯總

4.2.3 評估工作量的指標

在缺陷定位領域,研究人員發現,上述性能評價指標不能完全滿足IRBL 方法在實際應用中的評估需求.由于開發人員需要花費有限的工作量(時間和資源)來對IRBL 方法推薦的結果進行人工審查.在此期間,能夠以較小工作量的找到缺陷所在位置才能夠說明一個方法的實際有效性.因此,研究者們從工作量感知(effort aware)的角度來對結果進行評價.

表6 中對工作量性能評估指標的計算方法和使用情況進行了匯總,其中大部分評估指標是Zhao 等人[36,37]在2015 年首先提出的,他們使用代碼行數來衡量一個文件在審查時所需花費的工作量.其具體含義如下.

(1) Effort@K:由Top@K派生而來,衡量了缺陷定位方法推薦對列表中前K個源代碼文件進行審查時,開發人員找到與缺陷報告相關的源代碼文件平均需要花費多少工作量;

(2) MAE(mean average effort):由MAP 派生而來,表示從推薦列表中找出所有與缺陷報告相關的源代碼文件時平均所需花費的工作量;

(3) MFE(mean first effort):由MRR 派生而來,表示從源代碼文件推薦列表中找到第一個與缺陷報告相關的源代碼文件平均所需要的工作量.它的值越小,表示在工作量感知下方法的性能越好.

Table 6 Summary of evaluation metrics for IRBL models in terms of effort-aware performance表6 評價IRBL 模型的工作量性能指標匯總

4.3 實驗數據

經過十幾年的發展,目前IRBL 領域已有較多研究者收集并且公開了它們的實驗數據集,這對于繼續在缺陷定位領域進行研究十分有利.表7 列出了IRBL 領域的公開可用數據集的匯總信息,包括數據集提供者、所使用的項目數和提供的缺陷報告數目等.

Table 7 Summary of experiments datasets for IR-based bug localization models表7 基于信息檢索的缺陷定位模型的數據集匯總

目前,IRBL 領域的數據集的收集和使用過程中仍存在一些問題需要得到重視.

(1) 項目語言偏向于Java.目前,絕大多數研究者提供的數據集中的實驗項目是由Java 開發的,其他語言開發的數據集相對較少并且沒有被大量引用.例如,Saha 等人[26]收集的C 語言項目和對Garnier 等人[38]收集的C#語言項目都僅在各自的研究中被使用.Java語言項目受到關注,這得益于Java語言的流行和相關項目的良好維護.現有研究可以在一定程度上說明目前的方法在對Java 項目進行缺陷定位時是有效的.然而,不同的語言在進行開發時有各自的特點,僅僅在一種語言的項目上實驗的結果不能直接應用到其他語言開發的項目之上.其有效性還需要進一步的實驗證實;

(2) 數據集質量各異.盡管數據集的收集過程都是按照Dallmeier 等人[115]提供的過程進行收集,但是具體操作過程會有一些差異,從而導致不同研究者收集的數據集存在一定到偏差,在這些數據上進行實驗得到的結果可能會對分析帶來誤差.因此,為了得到客觀公正的結果,需要花費更多的工作來審查數據集的質量來確保其準確性;

(3) 實驗驗證不充分.雖然已有較多的數據集,但是從統計信息來看,大多數研究者還是集中于使用個別數據集(例如Zhou 等人[28]和Ye 等人[47])來驗證他們的方法.一方面說明現有的多個數據集還未受到研究者的重視,其數據集的可靠性有待于進一步被驗證;另一方面表明,現有IRBL 方法僅在個別數據集上獲得好的性能,其泛化能力仍有待更多實驗數據的證實.

4.4 小 結

本節從模型比較、評價指標和實驗數據這3 個方面詳細介紹了在近年來對IRBL 方法進行評估的研究進展.下面簡述主要的發現:

(1) 在實際定位中要選擇合適的IRBL 方法,同時應當注意到,參數配置對結果的有效性的影響比較大.因此在應用具體IRBL 方法時,應當選擇適當的參數;

(2) 現有研究主要是評價IRBL 方法的排序性能和分類性能,多數研究并沒有從工作量感知的角度來評價他們的方法,導致現有的研究方法很難滿足實際應用的需求;

(3) 目前,已有不同研究者提供的規模較大的數據集供后人使用,但是仍存在一些問題,例如數據集偏向于Java 編寫的項目.此外,目前大多數研究仍只在少數數據集上測試它們的方法,無法確保其具有良好的泛化性能.

5 缺陷定位的相關研究工作

缺陷定位是一個涉及層面十分廣闊的領域,除了可以使用信息檢索技術實現軟件缺陷定位,還可以通過其他多種途徑定位軟件中的缺陷,例如基于程序頻譜的缺陷定位、基于程序變異的缺陷定位、基于多模態的缺陷定位等.本節中,對其他類型缺陷定位的相關工作進行簡要介紹.

5.1 基于程序頻譜的缺陷定位

基于程序頻譜的缺陷定位(spectrum-based fault localization,簡稱SFL)是一類重要的動態定位技術,該類方法在進定位缺陷時需要執行大量的測試用例,然后通過對測試用例的程序頻譜應用評估度量來定位錯誤語句.與基于信息檢索的方法相類似的,該方法根據度量公式計算程序組件的分數,并對它們進行排序.基于程序頻譜的定位效果依賴于程序頻譜的構造方式和度量指標.以下是部分相關研究工作.

2009 年,Rui 等人[116]對早期的用于分析程序頻譜的特定相似系數的性能進行了評估.實驗結果表明,用于分析程序譜的特定相似系數的優越性能在很大程度上與實驗的設計無關.此外,對于低質量的缺陷觀察和有限數量的測試用例,基于程序頻譜的缺陷定位已經獲得了近乎最佳的準確性.實驗也證明了基于程序頻譜的缺陷定位可以有效地應用于嵌入式軟件開發的環境中.

2010 年,Lee 等人[117]提出了一種利用頻率加權函數進行缺陷定位的方法.該方法考慮了每個測試用例執行的程序語句的頻率執行計數來進一步提高缺陷定位的性能.

2015 年,Naish 等人[88]發現,現有的遺傳規劃方法由于評估度量的巨大搜索空間變得緩慢而不可靠.因此,他們提出了一個“hyperbolic”度量的限定類,其中包含少量的數值參數,由此,遺傳規劃算法可以在大量的程序頻譜上可靠地發現有效度量,從而使程序組件排序更準確.

2019 年,Ribeiro 等人[118]使用數據流頻譜評估了10 個基于程序頻譜方法的排名指標的有效性和效率.該實驗證明:使用數據流頻譜進行分析,比使用控制流頻譜分析效果更好,最高有50%的缺陷位于排序列表的前15位.同年,Ma 等人[119]提出了一個統一的系統研究框架來評估和比較單缺陷和多缺陷情況下的基于程序頻譜的缺陷定位方法.該框架實現了一個通用向量模型來深入理解各種基于程序頻譜的缺陷定位方法.

5.2 基于變異分析的缺陷定位

基于程序變異的缺陷定位(mutation-based fault localization,簡稱MFL)是一種使用變異算子模擬人為錯誤來檢測未知錯誤的定位方法[12,120-124],根據變異體與被測程序的執行結果,利用公式來推算代碼語句的出錯可能性.通常來說,這類方法在語句級別生成變異體,從而能夠比較準確地定位出程序中有缺陷的語句.同時,由于需對大量程序變異體執行測試用例集,其執行開銷較大.以下是部分相關研究工作.

2015 年,Papadakis 等人[125]首次提出了基于變異分析的缺陷定位的概念.他們提出的方法利用各個變異體間的相似性來檢測缺陷:首先,使用變異算子為待測程序生成變異體;然后,對原程序和變異體執行測試用例并獲取執行結果;接著,對執行結果構建特征計算變異體包含缺陷的風險分數;最后,根據相同位置的變異體與原程序語句風險分數來預測可能包含缺陷語句的位置.

同年,為了能夠很好地處理真實世界中多語言程序的缺陷定位問題,Hong 等人[120]提出了一種基于變異的缺陷定位技術.該技術以目標程序的多語言源代碼和一組測試用例作為輸入,生成一個按照包含缺陷風險值排序的語句列表.為了計算每個語句的風險值,該技術首先通過系統地改變每個語句來生成原程序的不同變體;接著,根據語句發生特定變異后,測試結果變化情況來計算風險值.值得注意的是:為了提高對多語言程序缺陷定位的準確性,他們提出了適用于多語言程序的變異算子.

由于MFL 技術的計算開銷較大,Liu 等人[121,122]在2017 年提出了兩種變異約簡策略來降低MFL 技術的計算成本.

· 一種是面向語句的變異約簡策略[121],該策略首先用全套變異算子在失敗測試用例覆蓋的每個語句上產生變異,以確保能夠使用完整類別的變異算子;然后利用每個語句上的變異體抽樣策略,選擇使用特定百分比的變異體;

· 另一種是動態變異執行策略[122],該策略會確定優先執行的變異體和測試用例首先執行,避免進行無用的執行來降低計算開銷.

2018 年,Oliveira 等人[123]提出一種面向失敗測試的變異運行策略FTMES 來提高基于變異的缺陷定位的有效性,并且降低其所需的計算開銷.FTMES 只使用一組失敗的測試用例來執行變異,并且通過使用覆蓋率數據替換終止信息來避免執行已通過的測試用例.

5.3 基于多種模態的缺陷定位

很多方法只考慮了某一種類型的缺陷定位技術,比如:基于信息檢索的方法只考慮了缺陷報告中的文本信息及靜態特征;基于程序頻譜的方法只考慮動態的程序頻譜特征.很多研究者發現:同時結合兩種或以上類型的缺陷定位技術能夠發揮出各自的優勢,從而能夠獲得更好的缺陷定位效果.以下是部分相關研究工作.

2015 年,Le 等人[45]將多模態信息檢索與程序頻譜組合進行缺陷定位,并且自適應地創建了一個特定于某個缺陷的模型,以將特定的缺陷映射到它可能的位置.該方法同時考慮了缺陷報告中的文本描述和程序的頻譜信息,最后結合兩者的分析結果獲得可疑的術語或單詞,并且以此來判斷程序組件包含缺陷的可疑程度.

2017 年,Dao 等人[54]研究了代碼運行信息對基于信息檢索的缺陷定位的幫助.作者在文中比較了3 種目前流行的基于信息檢索的缺陷定位方法(BugLocator[28],BLUiR[24],AmaLgam[31])和3 種代碼運行信息(程序覆蓋、程序切片和程序頻譜).實驗證明,代碼的運行信息會很大改進基于信息檢索的缺陷定位方法.

2019 年,Hoang 等人[67]也發現了只考慮缺陷報告和只考慮執行跟蹤的方法的限制.他們提出了一種多模態缺陷定位方法,通過聯合使用缺陷報告和執行跟蹤來解決現有方法存在的問題.

5.4 基于新型應用的缺陷定位

目前,大多的IRBL 方法在進行缺陷定位時并沒有細致考慮到缺陷的類型,他們的研究是針對所有類型的缺陷而言.在現實應用中,進行缺陷定位要面臨不同的應用場景,此時,直接使用這些方法可能無法得到預期效果.因此,有部分研究開始在更加細分類別的缺陷上研究定位方法.

· 對軟件崩潰的定位.軟件崩潰開始研究一種特殊缺陷,這種缺陷經常發生在用戶使用軟件的過程中,它導致軟件無法正常工作而出現崩潰界面,因而嚴重影響用戶體驗.這類缺陷通常會由軟件后臺自動收集相應的崩潰信息提交給后臺服務器.Wu 等人通過挖掘這些崩潰信息,提出了CrashLocator[126]和ChangeLocator[127],分別在方法級別和變更級別定位這種缺陷.2020 年,Guo 等人[128]在ChangeLocator的基礎上對崩潰變更的特征進行選擇,他們發現:過濾后的特征,能夠用來構建更好的崩潰變更定位模型;

· 對Android 應用缺陷的定位.Android 應用與開源的桌面軟件有所不同,它們運行在手機操作系統之上,這類應用的歷史缺陷報告較少,并且沒有充足的詳細描述信息.因此,很難將現有的IRBL 方法直接用于對Android 應用進行缺陷定位.2019 年,Zhang 等人[100]基于提交信息,提出了一種適用于Android 應用的缺陷定位方法.

5.5 小 結

本節從程序頻譜、變異分析、多模態和新型應用這4 個方面簡要介紹了缺陷定位領域中其他相關研究.下面簡述主要的發現:

(1) 程序頻譜是主流的動態缺陷定位方法,其相關研究一直是缺陷定位領域的另一個熱點;

(2) 變異分析是一種有效的動態缺陷定位方法,目前多數研究主要致力于降低這類方法的計算成本;

(3) 多模態的缺陷定位方法可以結合多種定位技術的優點,近年來也逐漸受到研究者的重視;

(4) 缺陷定位的應用已經開始逐步細分到研究具體類型的缺陷,這種趨勢有利于更精細化地將缺陷定位技術應用到實踐中.

6 挑 戰

從現有文獻來看,IRBL 技術的相關研究已經取得了很好的成效,最新的定位方法已經能夠將定位性能提升到一個較高的層面.但是我們應當注意到,現有的研究技術在工業界中并沒有被廣泛應用[39],因為它還難以滿足實際軟件開發和維護過程的需求.本節從局限性、泛化性、準確性和實用性這4 個角度來介紹IRBL 領域的研究面臨著以下挑戰.

(1) 局限性.目前,對IRBL 方法的性能評估是基于該方法在一組缺陷報告上測試的平均性能值(例如MRR).這類評估指標可以在整體上對某個方法進行評價,但是有一點需要注意:在整體上具有較高的評估分數,不代表該方法在每個具體缺陷報告的推薦結果也令人滿意[73].對任何IRBL 方法來說,是不可能對所有的缺陷報告都給出最優排序結果的.在應用一種方法時,可能會遇到以下情況:對某些(可能僅僅一小部分)缺陷報告進行推薦時,該方法會將這些缺陷報告對應的源文件排在十分靠后的位置.對這樣的推薦結果,開發者按照列表順序從頭審查將會花費巨大的工作量.盡管這種推薦結果出現的次數較少,但是由于開發者不知道何時會遇到這種推薦,他們會傾向于不使用該方法.上述情況屬于一個IRBL 方法的應用局限性.能夠準確分析每個IRBL 方法的局限性十分關鍵,這可以在使用時規避上述情況的發生.現有研究的一個問題是局限性分析較少,導致開發者不能夠在恰當的場景下使用這些IRBL 方法,從而這些方法的最大優勢不能被充分利用,同時在使用時不能及時避免其劣勢;

(2) 泛化性.影響泛化性的因素有兩點.

1) 測試數據集稀少.雖然現在已有多個公開數據集,最近兩年提出的一部分IRBL 方法[41,64,65,79,94,99]仍僅僅在很少的測試項目(Zhou 等人[28]在2012 年提供的4 個項目)上進行了驗證.特別地,這些項目數據大多是是由Java 語言開發的,因此多數現有的實驗結果是適用于Java 項目的[35],但是在其他類型的項目上的性能表現未知,即IRBL 方法的泛化性能未知.由于存在這種不確定性,目前的方法很難受到開發人員的信任,并且他們也很難挑選出優秀的方法.因此,許多工作[25,31,80]指出,仍然需要在更多的項目上進行實驗來測試IRBL 方法的性能;

2) 人工設計特征.現有的IRBL 方法的特征選取和挖掘都是人工根據某一部分的缺陷數據進行設計的,用這種方式構建出的方法可以在可以一些數據上達到較好的效果.然而,遇到具有不同特征的數據,這些方法的定位能力便會降低,從而就表現為泛化性低下[68];

(3) 準確性.準確的實驗數據集是保證定位方法質量的重要依據.現有的數據集雖然都是按照Dallmeier等人[115]提供的方法進行收集的,但是不同的研究者在具體操作過程中會有細節上的差別[28,35,39,115],從而導致不同數據集的準確性受到影響.其中,一些重要的細節信息需要驗證,例如:與缺陷報告進行匹配的源代碼的版本是否為被修復前的版本[47];數據集中明顯不包含缺陷的部分(例如測試文件)應當被排除在推薦列表之外[39]等等.這些不完全統一的處理細節會嚴重影響方法測試結果的準確性,甚至產生互相矛盾的比較結果[66];

(4) 實用性.目前的IRBL 方法僅活躍在實驗研究階段,它們并沒有在工程實踐中大量應用[39].除了準確性和泛化性較低的因素之外,更重要的原因是這些定位方法(如BugLocator[28],BRTracer[30],Locus[32]等)只能夠提供給開發者建議性的缺陷文件列表,無法為開發人員修復缺陷提供更多的指導信息.在生產實踐中,開發人員需要完全依靠自己對代碼的理解來手動檢查,所以目前缺陷定位技術所提供的幫助很小,我們分析,這是導致它們的實用性很難滿足開發者的需要的另一個重要原因.

針對缺陷定位技術面臨的問題挑戰,我們從結果分析、實驗驗證和修復指導總結了以下幾方面可能將會成為進一步深入研究的重要方向.

(1) 結果分析.其中一個研究方向是在缺陷定位框架中應當具有偵測機制,對缺陷報告的特征進行檢測并進行分類,根據檢測結果,缺陷定位框架應當決定是使用他們提出IRBL 方法進行定位還是放棄對該報告的定位.這一過程的實現,有利于開發者充分發揮IRBL 方法在其擅長處理的缺陷報告中進行推薦的能力,并且避免他們給出低效的推薦結果.這種機制的建立,需要對IRBL 方法的定位結果進行分析,通過收集較差的推薦列表所對應的的缺陷報告,分析這些缺陷報告的特征,在應用時,遇到具備這類特征的缺陷報告就停止使用IRBL 方法,而是進行人工處理或者借助其他技術來幫助定位.除此之外,需要增多對IRBL 方法進行工作量感知[36,37]方面的性能評估分析;

(2) 實驗驗證.針對泛化性和準確性的挑戰問題,一個研究方向是增加科學準確對比實驗研究目前方法的有效性.主要包括兩個方面.

1) 收集全面精準的數據集.目前的研究所使用的數據集極其不統一,所以他們得出的結論具有片面性,不能代表其真實的性能.為基于信息檢索的缺陷定位研究收集更多的準確數據集,需要涵蓋各種語言的書寫的項目以及各個領域的項目,用來驗證方法的有效性和泛化性;

2) 設置科學的實驗流程和設置.目前的研究所用的實驗設置比較混亂,這也會影響實驗結果的準確性.因此,需要在科學統一的流程和設置下進行實驗.實驗設計要符合現實開發的場景,以確保其合理性;

(3) 修復指導.為了提高定位方法的實用性能,一個重要的研究方向便是對缺陷定位的結果提供修復指導提示信息.對于給定的推薦結果列表,開發人員只能按照順序從頭開始審查,這還是需要大量花費精力來理解缺陷.如果IRBL 方法能夠指出其中列表中的文件中哪些特征是與缺陷報告描述內容相符,這可以在很大程度上幫助開發人員快速理解缺陷,并順利進行后續的修復工作.

7 結束語

近年來,基于信息檢索的缺陷定位技術(IRBL)由于其具有外部依賴少、計算成本低的優勢,成為了缺陷定位領域的研究熱點.本文圍繞IRBL 方法的模型改良和模型評估兩大方面,對當前的研究工作進行了梳理和總結.基于當前的研究進展,本文總結了該領域面臨的主要挑戰并指出了未來可能的研究方向.主要工作總結如下:(1) 針對模型改良,本文從更換檢索模型、使用特征分析和進行查詢重構這3 個維度進行歸類和闡述;(2) 針對模型評估,本文從模型比較、評價指標和實驗數據這3 個維度總結該領域的評估現狀和存在的問題;(3) 本文從局限性、泛化性、準確性和實用性這4 個角度總結了當前IRBL 領域研究面臨的問題挑戰,并針對性地指出了未來的研究方向.

致謝感謝各位審稿專家提出的寶貴意見.