基于mRMR算法的learning-to-rank錯誤定位

李天舒　舒挺　ANGWECH KEVIN

摘 要： 基于learning-to-rank技術構建頻譜錯誤定位模型，從而實現高效的程序錯誤定位是當前的研究熱點。然而，針對不同的程序和錯誤類型，如何生成有效的程序頻譜特征集來訓練錯誤定位模型，成為了極具挑戰的問題。針對該問題，應用mRMR算法生成程序頻譜特征集，提出一種learning-to-rank的錯誤定位新方法。該方法應用基因編程自動生成備選可疑度公式集，并利用mRMR算法從中選取一組公式子集，該子集中的可疑度公式具有與程序錯誤高相關且彼此之間低相關的特性。利用此可疑度公式子集結合程序頻譜計算特征值輸入機器學習算法，從而構造錯誤定位模型。實驗結果表明，新方法不僅能夠提高基于learning-to-rank錯誤定位的效率，也優于Naish1、Tarantula等傳統SBFL方法。

關鍵詞： 錯誤定位; mRMR算法; 基因編程; 排序學習

文章編號： 2095-2163（2021）07-0066-08中圖分類號：TP311文獻標志碼： A

learning-to-rank fault localization based on Mrmr

LI Tianshu， SHU Ting， ANGWECH KEVIN

（School of Informatics Science and Technology， Zhejiang Sci-Tech University，? Hangzhou 310018， China）

【Abstract】It is a current research hotspot to build a efficient fault localization model based on learning-to-rank technique. However， for different programs and fault types， how to generate an effective spectrum feature set to build the fault localization model has become a very challenging problem. In response to this problem， the mRMR is used to generate spectrum feature set， and a new learning-to-rank fault localization method is proposed. LTRmR uses genetic programming to automatically generate a set of alternate suspiciousness formulas， the suspiciousness formulas in this subset have the characteristics of high correlation with program faults and low correlation with each other. Suspiciousness formula subset combined with the spectrum is used to calculate the feature value input into the machine learning algorithm， thereby constructing a fault localization model. Experimental results show that the new method can not only improve the efficiency of learning-to-rank fault localization， but also outperform SBFL methods such as Naish1 and Tarantula.

【Key words】fault localization; mRMR; genetic programming; learning-to-rank

0 引 言

現如今軟件結構日趨復雜，導致軟件出錯的概率也越來越高。近年來，由于軟件出錯而造成的重大事故也時有發生。2018年3月，蘋果公司高級工程師Walter Huang在一起因特斯拉自動駕駛系統出錯而造成的事故中不幸離世，引發全美關注[1]。因此，如何保證軟件的高可靠性已成為吸引各方矚目的一個重要問題。通常，軟件調試工作都是人工設置斷點進而分析錯誤位置，需要花費大量時間和精力。而錯誤定位是軟件調試中的關鍵步驟之一，研究表明，錯誤定位成為近年來國內外學術界研究的熱點問題。

目前，學者們提出了許多自動化的方法用于錯誤定位研究，致力于提高軟件錯誤定位的效率。基于程序切片的錯誤定位[2]、基于程序頻譜的錯誤定位[3]和基于模型檢測的錯誤定位[4-5]都是主流的錯誤定位技術，其中，基于頻譜的錯誤定位方法（Spectrum-Based Fault Localization，SBFL）是目前最有效的定位方法之一。簡而言之，SBFL是通過對比程序在不同顆粒度（語句、謂詞、分支、基本塊）下成功執行和失敗執行的覆蓋信息來確定可疑代碼的位置。首先執行測試用例并收集測試用例執行結果和覆蓋信息，然后使用可疑度公式計算每條語句的可疑度值，可疑度值越高，代表這條語句是錯誤語句的可能性就越高。其中，可疑度公式是SBFL技術的核心。然而，單個可疑度公式只適合定位某種類型的程序結構和錯誤，并不具備普適性。

learning-to-rank是一種解決排序問題的技術[6]，近年來在自然語言、信息檢索等領域應用較為廣泛。利用learning-to-rank技術構建錯誤定位模型進行錯誤定位可進一步提高錯誤定位的精度。Kim等人[7]提出PRINCE錯誤定位框架，通過對待測程序提取程序靜態特征（文件、函數和語句的依賴性和復雜性）和程序動態特征（可疑度公式），結合learn-to-rank技術并應用支持向量機算法構造錯誤定位模型，該方法經實驗驗證可顯著提高錯誤定位效率。研究表明，擅長定位同類型程序或錯誤的技術之間具有高相關性[8]。目前大多數的研究在構建錯誤定位模型特征集時只是將相關信息、相關技術簡單集成，并沒有考慮這些程序信息或錯誤定位技術之間的相關性。然而，將彼此低相關性的錯誤定位技術集成起來往往能夠為錯誤定位模型提供不同方面的信息，從而提高錯誤定位的效率。

本文以錯誤定位模型的特征選取為出發點，開展深入研究，提出一種基于最大相關最小冗余算法（Max-Relevance and Min-Redundancy，mRMR）的learning-to-rank錯誤定位方法（Learning To Rank Fault Localization Based on mRMR，LTRmR）。首先將程序頻譜作為基因編程算法的輸入生成可疑度公式，再通過mRMR算法選取若干能夠準確識別程序錯誤且彼此之間低相關的可疑度公式構建模型特征集，最后經過訓練獲得錯誤定位模型。由于LTRmR融合了基因編程和learning-to-rank技術的優勢，錯誤定位的效率與性能將得到提升。

1 研究背景

1.1 SBFL方法

SBFL依賴于測試用例覆蓋信息計算語句可疑度分數，根據可疑語句排序列表從上到下排查程序錯誤。SBFL由2個重要成分構成：程序頻譜和可疑度公式。程序頻譜即反映程序運行軌跡不同方面信息的四元組數據（aef，aep，anf，anp）。其中，aef和aep分別表示在失敗和成功的測試中語句執行的次數;anf和anp分別表示在失敗和成功的測試中語句未執行的次數。目前已被提出的可疑度公式有很多，如Ochiai、Tarantula、Jaccard等，其中大多數公式皆由經驗直覺或引自其他領域設計而成。經實例驗證，很難通過傳統SBFL技術進一步提高錯誤定位效率。XIE等人[9]提出新的理論框架并分析了30個可疑度公式的定位效率，但只證明了其中5個公式在理論框架基礎上具有最優性。研究人員發現，利用基因編程所設計的可疑度公式能夠提高其對不同類型錯誤的適應性，Yoo[10]使用基因編程設計可疑度公式并證明其效率始終優于傳統公式。由此可見，傳統公式不僅設計起來費時費力，而且具有很大的局限性，效率很難提高。

1.2 learning-to-rank錯誤定位

learn-to-rank也稱為排序學習，是一種有監督的將機器學習技術應用在排序問題的學習方法，通過先驗并且帶有標注的樣本訓練模型解決排序問題。在Zou等人[8]的研究中，通過集成不同錯誤定位技術進行錯誤定位，包括SBFL技術、基于變異的錯誤定位技術、動態切片技術等。除上述研究外，Xuan等人[11]將25個可疑度公式組合并應用learn-to-rank技術完成錯誤定位，實驗結果證明該方法能夠更快地定位程序錯誤。但是，上述研究只考慮選取何種特征構建錯誤定位模型，卻忽略了特征間相關性對模型性能的影響。事實上，如果在特征集中存在冗余特征，會對錯誤定位模型的定準性產生負面效果。

2 LTRmR方法

LTRmR設計流程如圖1所示。由圖1可知，LTRmR構建錯誤定位模型共分3個階段：基于基因編程的特征生成、基于mRMR算法的特征集構造、錯誤定位模型訓練。在特征生成階段，使用基因編程技術實現可疑度公式自動化生成。第二階段基于mRMR算法選取可疑度公式構造特征集，最后根據頻譜輸入和特征集訓練錯誤定位模型，用于被測程序可疑語句的可疑度值計算和排序。LTRmR輸入為程序頻譜和語句標簽，錯誤語句位置已知，在語句標簽中，錯誤語句標記為1，正確語句標記為0;輸出為按可疑度值排序的程序語句列表，語句排名越高，該條語句導致程序出錯可能性越大。

2.1 基于基因編程的特征生成

本文使用基因編程技術設計可疑度公式（GP-evolved），其目的是使用可疑度公式組合學習錯誤定位模型。算法通過交叉和變異等操作逐代演化出越來越優秀的種群，新一代的種群通常比上一代種群更加適應于環境。程序停止的條件是某單獨個體達到預設的適應度值或者進化的代數達到預設參數值。在內存中，種群個體以樹形結構表示，樹的終端節點是操作數，非終端節點是運算符，如圖2所示。

基因編程算法參數和GP運算符參見表1和表2[10]。

適應度函數直接影響到基因編程算法的收斂速度以及能否找到最優解，以及最終結果與初始問題期望輸出之間的匹配程度。因此，適應度函數至關重要。本文適應度函數可寫作如下形式：

其中，t是可疑度公式;b是錯誤語句;p是包含錯誤語句b的程序。

2.2 基于mRMR算法的特征集構造

作為錯誤定位模型構建過程中最核心的部分，如何選取可疑度公式構造模型特征集決定了能否提高模型對程序錯誤的預測準確性。本文通過集成學習可疑度公式構建錯誤定位模型，為了獲得更好的模型錯誤定位能力，使用mRMR算法[12]作為可疑度公式選擇算法。mRMR算法旨在原始特征集中找到與目標輸出相關性最高，而特征彼此之間相關性最低的一組特征子集。mRMR算法選取可疑度公式過程具體如下：

（1）根據不同可疑度公式計算程序語句可疑度值。

（2）將可疑度值作為算法輸入，計算可疑度公式與語句標簽之間的互信息值I（xi ; c），并基于式（2）計算互信息值平均值D（S，c）：

其中，xi為特征集S中第i個可疑度公式。

（3）計算公式間最小冗余值R。其對應數學公式為：

（4）選取互信息值大于等于D值的m個可疑度公式，即選出與標簽c相關性最高的m個公式。

（5）剔除其中互信息值大于R值的公式，此步驟保證特征集中可疑度公式彼此之間相關性最低。

（6）剔除后公式數量不足m，基于式（4）使用增量搜索的方法在剩余公式中繼續挑選，直到特征集中的可疑度公式數量滿足m值。其對應數學公式為：

其中，m值為特征集數量預設值。

2.3 錯誤定位模型訓練

LTRmR是一個從選取的可疑度公式中學習錯誤定位模型的完整框架。在訓練階段，使用一組程序頻譜和語句標簽作為輸入數據，由特征集構造特征值，輸入機器學習算法學習錯誤定位模型。

本文使用隨機森林和支持向量機算法訓練模型，算法基于0.21.3版本scikit-learn機器學習工具包[13]實現，并使用交叉驗證方法評估錯誤定位模型性能。對于Defects4J和SIR數據集不同的訓練數據，模型分別使用留一驗證法和k折交叉驗證法完成訓練任務。其中，k值設置為10。錯誤定位模型構造完成后，其功能相當于可疑度公式，讀取待測程序頻譜數據，經過計算可疑度值將程序語句降序排列，生成可疑語句排序列表，從上到下依次排查錯誤。

3 實驗

3.1 實驗研究問題

本文實驗基于以下研究問題進行設計。

（1）RQ1：LTRmR能否提高learning-to-rank錯誤定位精度？

此研究問題是評估本文創新工作的重要參考，通過mRMR算法構造一組與語句標簽相關性最大，且彼此低相關的特征公式設置對比實驗，驗證LTRmR方法有效性。

（2）RQ2：LTRmR和傳統SBFL公式應用learning-to-rank技術相比表現如何？

此研究問題進一步評估LTRmR的有效性。考慮2種不同的特征集：

①由傳統SBFL公式所組成的特征集。

②由GP-evolved公式所組成的特征集。

另一方面，（1）中公式未做任何處理，僅簡單組合而成。（2）中公式應用mRMR算法選取，將公式間相關性作為組合考慮因素。

（3）RQ3：LTRmR和傳統SBFL公式相比定位效果如何？

此研究問題評估了LTRmR與傳統SBFL公式的錯誤定位表現，同時評估learning-to-rank技術對傳統錯誤定位方法效率提升所提供的幫助。

3.2 實驗對象

Defects4J[14]是一個基于Java的大型開源故障數據集，其故障均來自于現實中開源代碼中的實際故障。每個故障都有一個測試套件，并保證該測試套件中至少有一個測試用例可以觸發該故障。實驗使用其中包括5個Java程序的357個故障，具體信息見表3。

SIR數據集是軟件錯誤定位領域中較為流行的開源數據集存儲庫之一，實驗使用4個來自SIR數據集的程序，共92個人工故障，見表4。

3.3 評價指標

（1）Accuracy標準。acc@n度量標準計算在語句可疑度排名列表中前n個位置內成功定位的錯誤數量。本文選擇1、3、5、10作為acc@n中的n值。

（2）EXAM指標。EXAM指標是被廣泛使用的用來評估錯誤定位效率的指標[15]。其值為在可疑語句排序列表中找到第一個錯誤之前所檢查的語句數占程序語句總數的百分比。顯然，該指標的值越小表示定位效果越好。

3.4 實驗設置

本文所有實驗均在Intel Core i7-4700MQ CPU，2.40 GHz，內存為4 GB，Microsoft Windows 10操作系統的計算機上完成，其中基因編程算法基于pyevolve框架實現。為驗證LTRmR有效性，設置2組對比實驗。第一組對比實驗使用15個傳統SBFL公式作為特征集訓練錯誤定位模型，具體公式參見表5。第二組對比實驗使用GP-evolved公式構成特征集，其可疑度公式選取策略為隨機選擇，為避免隨機性影響實驗結果的準確性，在第二組實驗中共設置30個可疑度公式特征集，每個特征集從3 000個備選可疑度公式中隨機選取15個公式。在評估實驗結果時，將30組結果的平均值作為第二組實驗最終結果。

實驗將評估LTRmR與2組對比實驗的錯誤定位效率，并將實驗結果進行對比。圖表中分別使用“max”和“random”代表第一、二組實驗，另分別使用“r”和“s”代表隨機森林和支持向量機兩種建模算法。例如，“LTRmR_s”指使用支持向量機算法建模的LTRmR。

4 實驗結果分析

4.1 RQ1

圖3和圖4顯示SBFL公式與LTRmR在5個Defects4J多錯誤程序和4個SIR多錯誤程序的錯誤定位效果。x軸表示已檢查代碼比例，y軸表示錯誤的檢出比例。可以發現，LTRmR曲線總體位于random曲線上方，證明LTRmR對learning-to-rank錯誤定位的效率有明顯提高。研究時通過隨機選取可疑度公式集成學習錯誤定位模型代表目前大多數learning-to-rank錯誤定位方法，通過隨機集成特征所構造的特征集并未考慮特征間相關性。容易發現，經過LTRmR對特征集進行去冗余處理后，其效率明顯增高。acc@n評價標準實驗結果見表6。從表6實驗數據得知，LTRmR對于random在top-10位置所檢出的錯誤數量平均提高20.3%和7.6%，分別基于Defects5J和SIR數據集。由此可見，應用mRMR算法處理錯誤定位模型的特征集，對于提高錯誤定位模型性能有顯著效果。

為了進一步說明問題，計算了在可疑語句排名列表中第一個錯誤在被測程序的所有版本中的平均排名。例如，在Defects4J數據集的Closure程序中，共有133個版本。首先統計GP13公式在每個版本中所找到的第一個錯誤的排名，再計算所有版本排名的平均值，通過計算，GP13在所有版本中定位首個錯誤的平均排名是357.99。實驗中統計了來自Defects4J的5個程序和SIR的4個程序的第一個錯誤由不同錯誤定位技術所得到的平均排名，然后將所得結果與LTRmR比較，建立箱形圖，如圖5所示。每個箱型圖上方和下方的橫線分別表示第一個錯誤在所有版本中的最高排名和最低排名，箱子的頂部和底部分別表示上4分位數和下4分位數，箱子內的橫線表示中位數，紅點表示異常值。從圖5可以觀察得到，LTRmR的穩定性優于其他錯誤定位技術，且中位數最低，這表明，在跨項目的多錯誤版本中LTRmR總能更快地定位到錯誤。

4.2 RQ2

圖3和圖4中最上方3條線分別表示LTRmR與2組對比實驗的EXAM指標表現。從這些圖中可以發現，LTRmR曲線處于所有曲線之上，表明在相同代碼檢查比例下，LTRmR能夠找到更多的錯誤。同樣地，檢出相同比例的程序錯誤，LTRmR只需要檢查更少的代碼。研究通過3種不同的組合策略驗證了LTRmR的有效性，“max”中公式均為領域中應用廣泛的SBFL公式，相比于特征成員更平民化的LTRmR，效率明顯略低。相比技術本身，決定錯誤定位模型定位效率很重要的因素便是特征公式之間的相關性，在保持與目標輸出高度相關性的前提下，可疑度公式之間相關性越低，越能為錯誤定位提供不同方面的信息，起到增益效果。單純地將公式組合在一起雖然能夠提高定位效率，但是只能驗證learning to rank技術的有效性，并沒有考慮不同技術之間的內在關系。從圖4能夠發現，在特征集不變的情況下，使用隨機森林算法所構建的錯誤定位模型往往能夠更快地定位到錯誤，圖4（a）中“LTRmR_r”找出全部錯誤所需檢查的代碼比例大約為20%，而圖4（b）中“LTRmR_s”找到全部錯誤則需要檢查大約40%的代碼。另一方面，使用單個SBFL公式進行錯誤定位，最快能找到全部錯誤的公式是GP13，GP13在代碼檢查率達到10%時能夠成功定位超過80%的錯誤。

表6詳細闡述了LTRmR和其他SBFL方法在acc@n指標上的表現。從表6可以發現，在top-10前，“LTRmR_r”和“LTRmR_s”分別成功定位Defects4J數據集中257個和263個錯誤以及SIR數據集中的46個和45個錯誤。容易發現，在表5所示公式中，只有Kulczynski、Kulczynski2、Ochiai以及GP13能在top-10位置前定位的錯誤比例高于50%，并分別定位189、192、183和183個錯誤。結果表明，LTRmR比傳統方法更具有性能優勢，效率更高。

4.3 RQ3

根據圖2和圖3的結果可以觀察得出，LTRmR曲線，即LTRmR_r和LTRmR_s總體上位于其他曲線上方，表明LTRmR在相同的代碼檢查量下，可以定位到更多錯誤。即使在代碼檢查比例大于60%之后，會偶爾出現LTRmR曲線低于其他公式曲線的情況，也仍然可以肯定LTRmR的有效性。一個很重要的原因是，在真實開發環境中，只有在代碼檢查百分比很低的時候定位到錯誤，錯誤定位工作才是有意義的。

由表6可知，GP13和Naish2在前10檢查位置中分別成功定位Defects4J共計357個錯誤中的183和153個錯誤。對于SIR基準數據集的錯誤，GP13和Naish2分別可以定位36和35個錯誤。通過比較以上數據可以得到，GP13比其他SBFL公式定位效率更高。LTRmR在top-10前最多能夠定位263個故障，較GP13相比，LTRmR的錯誤檢出率提高了43.7%。通過表中數據發現，LTRmR比單獨使用SBFL公式錯誤定位的準確性高，錯誤定位效率也有顯著提高。

5 結束語

本文提出一種結合基因編程和mRMR算法的頻譜特征生成和選擇方法LTRmR，研究了在357個實際錯誤和92個人工錯誤上的定位性能，并通過實驗對比評估了15個SBFL公式的錯誤定位效率。LTRmR首先通過基因編程生成可疑度公式，然后使用mRMR算法選取公式并生成算法模型特征集，最終構建排序模型進行錯誤定位。經實驗結果驗證，在集成多種SBFL技術進行錯誤定位時，各特征成員之間的相關性高低對最終的定位效果有顯著影響。從實驗結果發現，LTRmR不僅能夠提高learning-to-rank錯誤定位方法的效率，其性能也優于傳統SBFL公式，錯誤定位能力和效率有一定提升。

在未來的工作中，研究將對LTRmR進行有效改進，使其滿足不同顆粒度級別錯誤定位技術需求。

參考文獻

[1]LIN Rui， MA Liang， ZHANG Wei. An interview study exploring Tesla drivers' behavioural adaptation[J]. Applied ergonomics， 2018， 72： 37-47.

[2]ZHANG Zhuo， LEI Yan， TAN Qingping， et al. Deep learning-based fault localization with contextual information[J]. IEICE Transactions on Information and Systems， 2017， 100（12）： 3027-3031.

[3]ZHANG Mengshi， LI Xia， ZHANG Lingming， et al. Boosting spectrum-based fault localization using pagerank[C]// Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis. California， United States： ACM， 2017： 261-272.

[4]舒挺， 黃明獻， 丁佐華， 等. 基于條件概率模型的缺陷定位方法[J]. 軟件學報， 2018， 29（6）： 1756-1769.

[5]姚弋， 謝曉鳴， 劉書涵， 等. 考慮缺陷關聯模型的軟件優化測試策略[J]. 浙江理工大學學報（自然科學版）， 2016， 35（1）： 78-83.

[6]LE T D B， LO D， Le GOUES C， et al. A learning-to-rank based fault localization approach using likely invariants[C]// Proceedings of the 25th International Symposium on Software Testing and Analysis. Saarbrücken， Germany：ACM， 2016： 177-188.

[7]KIM Y， MUN S， YOO S， et al. Precise learn-to-rank fault localization using dynamic and static features of target programs[J]. ACM Transactions on Software Engineering and Methodology （TOSEM）， 2019， 28（4）： 1-34.

[8]ZOU Daming， LIANG Jingjing， XIONG Yingfei， et al. An empirical study of fault localization families and their combinations[J]. IEEE Transactions on Software Engineering， 2019，47（2）：332-347.

[9]XIE Xiaoyuan， CHEN T Y， KUO F-C， et al. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization[J]. ACM Transactions on Software Engineering and Methodology （TOSEM）， 2013， 22（4）： 1-40.

[10]YOO S. Evolving human competitive spectra-based fault localisation techniques[M]//FRASER G， TEIXEIRA de SOUZA J T. Search based software engineering. SSBSE 2012. Lecture Notes in Computer Science. Berlin， Heidelberg：Springer， 2012，7515： 244-258.

[11]XUAN Jifeng， MONPERRUS M. Learning to combine multiple ranking metrics for fault localization[C]// 2014 IEEE International Conference on Software Maintenance and Evolution. Victoria， BC， Canada：IEEE， 2014： 191-200.

[12]PENG Hanchuan， LONG Fuhui， DING C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy[J]. IEEE Transactions on pattern analysis and machine intelligence， 2005， 27（8）： 1226-1238.

[13]PEDREGOSA F， VAROQUAUX G， GRAMFORT A， et al. Scikit-learn： Machine learning in Python[J]. the Journal of machine Learning research， 2011， 12： 2825-2830.

[14]JUST R， JALALI D， ERNST M D. Defects4J： A database of existing faults to enable controlled testing studies for Java programs[C]// Proceedings of the 2014 International Symposium on Software Testing and Analysis. ， San Jose， CA， USA ：ACM， 2014： 437-440.

[15]JIANG Bo， CHAN W K， TSE T H. On practical adequate test suites for integrated test case prioritization and fault localization[C]// 2011 11th International Conference on Quality Software. Madrid， Spain：IEEE， 2011： 21-30.

基金項目： 浙江省自然科學基金（LY17F020033）; 國家自然科學基金（ 61101111， 61572441） 。

作者簡介： 李天舒（1994-），男，碩士研究生，主要研究方向：軟件測試; 舒 挺（1979-），男，博士，副教授，主要研究方向：計算機網絡協議、軟件測試、移動電子商務系統開發等; ANGWECH KEVIN（1989-），女，碩士研究生，主要研究方向：軟件測試。

通訊作者： 舒 挺Email：shuting@zstu.edu.cn

收稿日期： 2021-03-27