Network-Clustered Multi-Modal Bug Localization
Thong Hoang Richard J. Oentaryo Tien-Duy B. Le David Lo






























































CodeOut
defnDefinition
propProperty


showcomments
showcommentstrue
showcomments
 
 


𝑐𝑜𝑛𝑓

packed_enum

  
  
  


packed_itemize

  
  
  


++












theoremTheorem
definitionDefinition



8.5in
11.0in
















Network-Clustered Multi-Modal Bug Localization
    Tien-Duy B. Le, Thong Hoang, Richard J. Oentaryo, and David Lo

	School of Information Systems 

	Singapore Management University

{btdle.2012,vdthoang.2016,roentaryo,davidlo}@smu.edu.sg

    
===============================================================================================================================================================================================




Developers often spend much effort and resources to debug a program. To help the developers debug, numerous information retrieval (IR)-based and spectrum-based bug localization techniques have been devised. IR-based techniques process textual information in bug reports, while spectrum-based techniques process program spectra (i.e., a record of which program elements are executed for each test case). While both techniques ultimately generate a ranked list of program elements that likely contain a bug, they only consider one source of information—either bug reports or program spectra—which is not optimal. In light of this deficiency, this paper presents a new approach dubbed Network-clustered Multi-modal Bug Localization (NetML), which utilizes multi-modal information from both bug reports and program spectra to localize bugs. NetML facilitates an effective bug localization by carrying out a joint optimization of bug localization error and clustering of both bug reports and program elements (i.e., methods). The clustering is achieved through the incorporation of network Lasso regularization, which incentivizes the model parameters of similar bug reports and similar program elements to be close together.  To estimate the model parameters of both bug reports and methods, NetML employs an adaptive learning procedure based on Newton method that updates the parameters on a per-feature basis. Extensive experiments on 355 real bugs from seven software systems have been conducted to benchmark NetML against various state-of-the-art localization methods. The results show that NetML surpasses the best-performing baseline by 31.82%, 22.35%, 19.72%, and 19.24%, in terms of the number of bugs successfully localized when a developer inspects the top 1, 5, and 10 methods and Mean Average Precision (MAP), respectively.

























§ INTRODUCTION



§ INTRODUCTION



Debugging bug reports, which often come in high volume <cit.>, has proved to be a difficult task that takes much resources and time <cit.>. Various techniques have been devised to help developers locate buggy program elements from their symptoms. These symptoms could be in the form of description of a bug experienced by a user, or a failing test case. These techniques—often collectively referred to as bug (or fault) localization—analyze the symptoms of a bug and produce a list of program elements ranked based on their likelihood to contain the bug. In general, a program element can be defined at three levels of granularity, i.e., source file level, method/function level, and line of code level.



 §.§ The Need for Multi-modal Bug Localization



Existing bug localization techniques broadly fall into two major categories: information retrieval (IR)-based techniques <cit.>, and spectrum-based bug localization techniques <cit.>. The IR-based bug localization techniques typically analyze textual descriptions contained in bug reports and identifier names and comments in source code files. They then return a ranked list of program elements (typically program files) that are the most similar to the bug textual description. The spectrum-based bug localization techniques typically analyze program spectra that corresponds to program elements that are executed by failing and successful execution traces. Likewise, they return a ranked list of program elements (typically program blocks or statements) that are executed more often in the failing rather than correct traces.




The above-mentioned approaches, however, only consider one kind of symptom or one source of information, i.e., only bug reports or only execution traces. This is a limiting factor since hints of the location of a bug may be spread in both bug report and execution traces; and some hints may only appear in one but not the other. In this work, we put forward a bug localization approach that addresses the deficiency of existing methods by jointly utilizing both bug reports and execution traces. We refer to this approach as multi-modal bug localization, as we need to consider multiple modes of inputs (i.e., bug reports and program spectra). Such an approach fits well to developers' debugging activities as illustrated by the following scenarios:


	
  * Developer D is working on a bug report that is submitted to Bugzilla. One of the first tasks that he needs to do is to replicate the bug based on the description in the report. If the bug can be successfully replicated, he will proceed to the debugging step; otherwise, he will mark the bug report as “WORKSFORME” and will not continue further <cit.>. After D replicates the bug, he has one or a few failing execution traces. He also has a set of regression tests that he can run to get successful execution traces. Thus, after the replication process, D has both the textual description of the bug and a program spectra that characterizes the bug. With this, D can proceed to use multi-modal bug localization.
	
  * Developer D runs a regression test suite and some test cases fail. Based on his experience, D has some idea why the test cases fail. D can create a textual document describing the bug. At the end of this step, D has both program spectra and textual bug description, and can proceed to use multi-modal bug localization which will leverage not only the program spectra but also D's domain knowledge to locate the bug.













































































































It is worth noting that our work focuses on localizing a bug to the method that contains it. Historically, most IR-based bug localization techniques aim at finding buggy files <cit.>, while most spectrum-based techniques find buggy lines <cit.>. Localization at the method level can be a good tradeoff. That is, a method is not as big as a file, but it often contains sufficient context needed to help developers understand a bug. On the other hand, by just looking at a line of code, developers often cannot determine whether it is the location of the bug or understand the bug well enough to fix it <cit.>. Admittedly, if the methods are long, a finer granularity (e.g., basic blocks) may be preferred. Nevertheless, a recent study by Kochhar et al. <cit.> highlights that out of the 386 practitioners they surveyed, the majority indicates method-level as the preferred granularity.











 §.§ Proposed Approach




In this paper, we present a new approach called the Network-clustered Multi-modal Bug Localization (NetML), which works based on three main intuitions:


	
  * Firstly, it is recognized that a large variety of bugs exist, and different bugs need different treatments <cit.>. A bug report written by a developer provides unique description of a bug. Thus, different bugs require separate model parameters to capture their individual characteristics. Similarly, different program elements (or methods in this work) are of different nature, and should be characterized by separate model parameters.
	
	
  * A recent study by Parnin and Orso <cit.> also showed that some words are more useful in localizing bugs, and suggested that “future research could also investigate ways to automatically suggest or highlight terms that might be related to a failure”. Our NetML provides such capability by incorporating method suspiciousness feature, which allows us to automatically highlight suspicious terms and use them to localize bugs.
	
	
  * We also observe that bugs and program elements are not completely independent, and some bug reports (or methods) may be more similar to certain bug reports (or methods) than to others. As such, similar bugs (or methods) should have model parameters that are close together. This enforcement of clustering of model parameters would enable similar bug reports (or methods) to share information and reinforce one another. 




The first two intuitions have been captured in our recent work—dubbed Adaptive Multi-Modal Bug Localization (AML) <cit.>—which we extend in this paper. In particular, AML already incorporates the ideas of adaptively computing separate model parameters for each bug report, and of computing the method suspiciousness feature[To understand the concept of feature and model parameters, we can draw an analogy to a linear model y = ∑_i w_i x_i. A feature refers to the (independent) input variable x_i, while a model parameter refers to the weight coefficient w_i for each feature x_i. In this case, the model parameters w_i need to be learned/estimated from data.].


However, the current AML approach exhibits two main shortcomings. Firstly, AML only has the concept of model parameters for bug reports, but not for program elements (or methods). As such, it is not able to capture  variation in the inherent characteristics of different program elements (methods), which may limit its effectiveness in localizing a bug. Secondly, the model parameters of each bug report are learned independently of those of other bug reports. As a result, AML is unable to take advantage of the clustering/similarity traits of different bug reports in the localization process.



	
	
	
	


































































The proposed NetML method addresses these shortcomings by performing joint optimization of localization loss function and clustering of both bug reports and methods. Specifically, it generalizes AML in two important ways:


	
  * NetML provides a richer model that has two sets of (model) parameters—one for bug reports and the other for methods. The addition of the method parameters (in contrast to AML that has only bug report parameters) provides NetML with a higher degree of freedom to characterize the different variety of bug reports and methods more accurately.
	
	
  * NetML incorporates network Lasso regularization <cit.> into its parameter learning procedure, which enforces similar bug reports (and methods) to have similar (or even identical) model parameters. This clustering enforcement would allow similar bug reports (or methods) to reach a consensus on the model parameters, leading to a simpler “policy” for bug localization. This enables the models of bug reports (or methods) to complement and borrow strength from one another. In turn, this would improve robustness and generalization performance on new/unseen bug reports.


It is noteworthy that, deviating from the conventional network Lasso <cit.> which deals with only a single network (graph), we impose regularization over two networks, i.e., bug report similarity and method similarity graphs. This allows us to achieve simultaneous clustering of both bug reports and methods, and exploit their similarity traits so as to achieve a more effective bug localization.








To illustrate how the network Lasso regularization in NetML can benefit bug localization, Fig.  <ref> shows two bug reports from Apache-Ant <cit.> project, namely Bug 30798 and Bug 43969. These two bug reports describe issues with the “showoutput” option for Apache Ant's JUnit task and the corresponding bugs both reside in the  method of the  file. Bug 30798 mentions the names of a few source code files and one of them is the name of the buggy file (i.e., ), while no such hint is included in Bug 43969. AML manages to successfully localize the buggy method for Bug 30798, by ranking it high in the returned ranked list. However, due to the limited information in Bug 43969, it is not able to do the same for it. Upon a closer investigation, we can see that Bug 30798 and Bug 43969 are similar, since they share a number of common word tokens (i.e., “JUnit”, “text”, “output”, etc.). The network Lasso regularization is able to take advantage of this similarity by enforcing similar bug reports to have similar model parameters. In such way, NetML leverages the similarity of Bug 30798 and Bug 43969 to guide/reinforce the prediction for Bug 43969, which leads to successful localization for both bugs.






























 §.§ Contributions





To evaluate the efficacy of the NetML approach, we conducted experiments using a dataset of 355 real bugs from seven medium to large software systems: Ant, AspectJ, Lang, Lucene, Math, Rhino, and Time. All real bug reports and real test cases were collected from these systems. The test cases were run to generate program spectra. We compare NetML with our previous AML method. Additionally, we evaluate our approach against a wide range of state-of-the-art approaches, including two multi-modal feature localization techniques (i.e., PROMESIR <cit.>, DIT^A and DIT^B <cit.>), four spectrum-based bug localization techniques (<cit.>), and an IR-based bug localization technique (i.e., LR^A and LR^B <cit.>). We use two well-known evaluation metrics to estimate the performance of our approach: number of bugs localized by inspecting the top N program elements (Top N) and mean average precision (MAP). 

Note that Top N and MAP have been widely used in past bug localization studies,
e.g., <cit.>.




Our experiment results demonstrate that, among the 355 bugs, NetML can successfully localize 116, 219, and 255 bugs when developers only inspect the Top 1, Top 5, and Top 10 methods in the lists that NetML produces, respectively. These constitute 31.82%, 22.35%, 19.72%, and 19.24% improvements over AML (which is the second best method in our benchmark), in terms of Top 1, Top 5 , Top 10, and MAP results respectively.












We summarize the key contributions of this paper below:



  * We present a novel multi-modal bug localization method that adaptively learns two sets of model parameters that characterize each bug report and method, respectively. We are also the first to incorporate the network Lasso regularization on both bug report and method similarity networks, which facilitates an effective joint optimization of bug localization quality and clustering of both bug reports and methods.  

  * We develop an adaptive learning procedure based on Newton update to jointly update the model parameters of bug reports and methods on a per-feature basis. The procedure is based on the formulation of strict convex loss function, which provides a theoretical guarantee that any minimum found will be globally optimal. 

  * We have extensively evaluated NetML on a dataset of 355 real bugs from seven software systems using real bug reports and test cases. Our statistical significance tests reveal that NetML improves upon state-of-the-art bug localization approaches by a substantial margin.



	










 §.§ Paper Organization



The remainder of this paper is organized as follows. In Section <ref>, we present background information on IR-based and spectrum-based bug localization approaches. Section <ref> elaborates the proposed NetML in greater details. In Section <ref>, we present our dataset, evaluation metrics, and experiment results. Section <ref> then provides a qualitative study of the NetML results, followed by discussions on potential threats to the validity of our study in Section <ref>.  Section <ref> provides an overview of key related works. We finally conclude this paper and discuss future works in Section <ref>.





§ BACKGROUND



§ BACKGROUND



In this section, we present some background material on IR-based and spectrum-based bug localization.







 §.§ IR-Based Bug Localization

 

IR-based bug localization techniques consider an input bug report (i.e., the text in the summary and description of the bug report as a query, and program elements in a code base as documents, and employ IR techniques to sort the program elements based on their relevance with the query. The intuition behind these techniques is that program elements sharing many common words with the input bug report are likely to be relevant to the bug. By using text retrieval models, IR-based bug localization computes the similarities between various program elements and the input bug report. Then, program elements are sorted in descending order of their textual similarities to the bug report, and sent to developers for manual inspection.























All IR-based bug localization techniques need to extract textual contents from source code files and preprocess textual contents (either from bug reports or source code files). First, comments and identifier names are extracted from source code files. These can be extracted by employing a simple parser. In this work, we use JDT <cit.> to recover the comments and identifier names from source code. Next, after the textual contents from source code and bug reports are obtained, we need to preprocess them. The purpose of text preprocessing is to standardize words in source code and bug reports. There are three main steps: text normalization, stopword removal, and stemming:


	
  * Text normalization breaks an identifier into its constituent words (tokens), following camel casing convention. Following the work by Saha et al. <cit.>, we also keep the original identifier names.
	
  * Stopword removal removes punctuation marks, special symbols, number literals, and common stopwords <cit.>. It also removes programming keywords such as 𝑖𝑓, 𝑓𝑜𝑟, 𝑤ℎ𝑖𝑙𝑒, etc., which usually appear too frequently to be useful to differentiate between documents.
	
  * Stemming simplifies English words into their root forms. For example, ”processed“, ”processing“, and ”processes“ are all simplified to ”process“. This increases the chance of a query and a document to share some common words. We use the popular Porter Stemming algorithm <cit.>.




Numerous IR techniques have been employed for bug localization. We highlight a popular IR technique namely Vector Space Model (VSM). In VSM, queries and documents are represented as vectors of weights, where each weight corresponds to a term. The value of each weight is usually the term frequency—inverse document frequency (TF-IDF) <cit.> of the corresponding word. Term frequency refers to the number of times a word appears in a document. Inverse document frequency refers to the number of documents in a corpus (i.e., a collection of documents) that contain the word. The higher the term frequency and inverse document frequency of a word, the more important the word would be. In this work, given a document d and a corpus C, we compute the TF-IDF weight of a word w as follows:

    weight(w,d)    = TF-IDF(w,d,C) 
       = log(f(w,d)+1) ×log|C|/|d_i∈ C : w ∈ d_i |

where f(w,d) is the number of times w appears in d.































After computing a vector of weights for the query and each document in the corpus, we calculate the cosine similarity of the query and document vectors. The cosine similarity between query q and document d is given by:

    𝑠𝑖𝑚(q,d) = ∑_w∈ (q⋂ d)𝑤𝑒𝑖𝑔ℎ𝑡(w,q) ×𝑤𝑒𝑖𝑔ℎ𝑡(w,d)/√(∑_w∈ q𝑤𝑒𝑖𝑔ℎ𝑡(w,q)^2)×√(∑_w∈ d𝑤𝑒𝑖𝑔ℎ𝑡(w,d)^2)

where w∈ (q⋂ d) means word w appears both in the query q and document d. Also, 𝑤𝑒𝑖𝑔ℎ𝑡(w,q) refers to the weight of word w in the query q's vector. Similarly, 𝑤𝑒𝑖𝑔ℎ𝑡(w,d) refers to the weight of word w in the document d's vector.













 §.§ Spectrum-Based Bug Localization
 


Spectrum-based bug localization (SBBL)—also known as spectrum-based fault localization (SBFL)—takes as input a faulty program and two sets of test cases. One is a set of failed test cases, and the other one is a set of passed test cases. SBBL then instruments the target program, and records program spectra that are collected when the set of failed and passed test cases are run on the instrumented program. Each of the collected program spectrum contains information of program elements that are executed by a test case. Various tools can be used to collect program spectra as a set of test cases are run. In this work, we use Cobertura <cit.>.



Based on this spectra, SBBL typically computes some raw statistics for every program element. Tables <ref> and <ref> summarize some raw statistics that can be computed for a program element e, given a program spectra p. These statistics are the counts of unsuccessful (i.e., failed), and successful (i.e., passed) test cases that execute or do not execute e. If a successful test case executes program element e, then we increase n_s(e, p) by one unit. Similarly, if an unsuccessful test case executes program element e, then we increase n_f(e, p) by one unit. SBBL uses these statistics to calculate the suspiciousness scores of each program element. The higher the suspiciousness score, the more likely the corresponding program element is the faulty element. After the suspiciousness scores of all program elements are computed, program elements are then sorted in descending order of their suspiciousness scores, and sent to developers for manual inspection.




Different SBBL techniques have used different formulas to calculate the suspiciousness scores. Among these techniques, Tarantula is a popular one <cit.>. Using the notation in Table <ref>, the following is the formula that Tarantula uses to compute the suspiciousness score of program element e, given program spectra p:

    Tarantula(e, p)=n_f(e, p)/n_f(p)/n_f(e, p)/n_f(p)+n_s(e, p)/n_s(p)

The main idea of Tarantula is that program elements that are executed by failed test cases are more likely to be faulty than those that are not executed. Thus, Tarantula assigns a non-zero score to program element e that has n_f(e, p) > 0. 





§ PROPOSED APPROACH



§ PROPOSED FRAMEWORK




An overview of our NetML framework is given in Fig. <ref> (enclosed in the dashed box). 
NetML takes as input a new bug report, the program spectra corresponding to it, and a method corpus. It also takes as input historical bug reports that have been localized before. For each historical bug report, we have its corresponding program spectra and ground truth labels. If a method contains a root cause of the bug, it is labeled as faulty, otherwise it is labeled as non-faulty. Given these inputs, NetML eventually produces a list of methods, ranked based on their likelihood to contain the root cause of the new bug report.





NetML has three main components, namely: feature extraction, graph construction, and integrator. The feature extraction component serves to extract multi-modal input features that quantify different perspectives on the degree of relevancy between a bug report and a method. Note that this is in a similar spirit to <cit.>. Meanwhile, the graph construction component computes the similarity graphs among the bug reports (𝒢_B) and methods (𝒢_M).

Finally, the integrator component is the heart of NetML and constitutes the primary contribution of this work. It integrates both input features and similarity graph information in order to produce a ranked list of methods based on their relevancy score. In particular, the integrator performs adaptive learning that aims at jointly minimizing the bug localization errors and fostering clustering of the model parameters of similar bug reports and/or methods.

In Sections <ref> and <ref>, we first elaborate the feature extraction and graph construction components respectively. We then describe the NetML integrator component in greater details in Sections <ref>–<ref>, including the formulation of our new integrator model as well as the corresponding objective function and adaptive learning procedure. 







 §.§ Feature Extraction




The first component of the NetML framework is the feature extraction module, which generates features 𝐗 = { x_b,m.j} to be fed as inputs to the NetML integrator (see  Fig. <ref>). In line with our earlier AML work <cit.>, for each bug report–method pair (b,m), we compute a feature vector x⃗_b,m  that consists of three elements:

    x⃗_b,m = [ NetML^Text_b,m, NetML^Spectra_b, m, NetML^SuspWord_b,m]

The three features are elaborated in turn below.



NetML^Text_b,m makes use of the TF-IDF method <cit.> to estimate the similarity between methods and bug reports. In particular, given a method m and a bug report b, NetML^Text_b,m computes the cosine similarity between the TF-IDF representation of the bug report text and that of the method codes, which is akin to the IR-based bug localization method (cf. Section <ref>). That is, NetML^Text_b,m is given by:

    NetML^Text_b,m = sim(b,m)

where sim(b,m) is the cosine similarity as defined in (<ref>).


NetML^Spectra_b, m processes only the program spectra information using a spectrum-based bug localization technique described in Section <ref>. Given a program spectra p corresponding to bug report b and a method m, NetML^Spectra_b, m gives a score that quantifies how suspicious  m is given p. By default, NetML^Spectra_b, m uses the Tarantula method as described in Section <ref> (cf. equation (<ref>)):

    NetML^Spectra_b, m = Tarantula(m, p)



Finally, NetML^SuspWord_b,m processes both bug reports and program spectra, and computes the suspiciousness scores of words to rank different methods. It breaks a method into its constituent words, computes the suspiciousness scores of these words, and then aggregates these scores back in order to arrive at the suspiciousness score of the method. Given a bug report b, a program spectra p, and a method m in a corpus C, NetML^SuspWord_b,m measures how suspicious m is considering b and p,  as follows: 

    NetML^SuspWord_b,m = NetML^Spectra_b, m×
       ∑_w∈ b ∩ mSSTFIDF(w,p,b,C)×SSTFIDF(w,p,m,C)/√(∑_w ∈ bSSTFIDF(w,p,b,C)^2)×√(∑_w ∈ mSSTFIDF(w,p,m,C)^2)

where 

SSTFIDF(w,p,b,C) is the weight of a word w in document (i.e., bug report or method) d with corpus C given program spectra p:

    SSTFIDF(w,p,d,C) =    SS_word(w,p)×ln(f(w,d)+1) 
       ×ln|C|/|d_i∈ C : w ∈ d_i |

where SS_word(w,p) is the suspiciousness score of a word w:

    SS_word(w,p)    = |EF(w,p)|/|p.FAIL|/|EF(w,p)|/|p.FAIL|+|ES(w,p)|/|p.SUCCESS|

In the above equation, EF(w,p) is the set of execution traces in p.FAIL that contain a method in which the word w appears, while ES(w,p) is the set of execution traces in p.SUCCESS that contain a method in which the word w appears. Further details of all these components can be found in <cit.>.




























































 §.§ Graph Construction



The second component of the NetML framework is the graph construction module, which serves to compute the similarity graphs among bug reports and methods, to be used in the K-nearest neighbor retrieval as well as the network Lasso regularization. In this work, we define the bug report similarity graph 𝒢_B as comprising edge weights that reflect the textual similarity between two bug reports. For a pair of bug reports b and b', we define the edge weight e_b.b' as follows:

    e_b,b' = sim(b, b')

where sim(b,b') is the cosine similarity between the TF-IDF weights of the textual descriptions of b and b', as per (<ref>).


Similarly, the method similarity graph 𝒢_M comprises a set of edge weights e_m,m' that reflect the textual similarity between two methods m and m'. This is given by:

    e_m,m' = sim(m, m')

where sim(b,b') is the cosine similarity between the TF-IDF representations of the source codes of m and m'.




 §.§ Integrator Model





The new integrator model proposed in this work characterizes the relevancy of a method m to a given bug report b as an interaction between two types of model parameters, namely:  bug report parameters u⃗_b = [u_b,1, …, u_b,j, …, u_b,J] and  method parameters v⃗_m = [v_m,1, …, v_m,j, …, v_m,J], where J is the total number of features. Note that J = 3 in this case, i.e., NetML^Text_b,m, NetML^Spectra_b, m, NetML^SuspWord_b,m. More specifically, the integrator model computes the relevancy score f̂_b,m as follows: 




    f̂_b,m = f̂(x⃗_b,m, u⃗_b, v⃗_m) = ∑_j = 1^J (u_b,j + v_m,j) x_b,m,j

where x⃗_b,m = [x_b,m,1, …, x_b,m,j, …, x_b,m,J] is the feature vector corresponding to a bug report–method pair (b, m).

It is worth mentioning that the above model constitutes a generalization of the AML integrator model that we previously developed <cit.>. In AML, the final relevancy score is computed based solely on the  bug report parameters, and this set of parameters is shared by all methods for a given bug report. On the other hand, the NetML integrator model accounts for not only the  bug report parameters but also the  method parameters. The addition of the latter parameters provides a greater degree of freedom/flexibility in quantifying the contribution of different methods to the localization of a given bug report.



























 §.§ Objective Function





Based on the above model formulation, we devise an objective function that guides the learning process of our integrator model. Specifically, we consider a joint optimization of bug localization quality and clustering of similar bug reports and methods, expressed by the loss function ℒ:

    ℒ   = ℒ_Entropy + ℒ_Ridge + ℒ_NetLasso

This consists of three components:

    ℒ_Entropy =     -∑_b ∈ℬ∑_m ∈ℳ w_b,m[y_b,mln(σ(f̂_b,m)) . 
        + . (1 - y_b,m) ln(1- σ(f̂_b,m)) ] 
    ℒ_Ridge =    α/2∑_j=1^J[∑_b ∈ℬ u_b,j^2 + ∑_m ∈ℳ v_m,j^2 ] 
    ℒ_NetLasso =    β/2∑_j=1^J[ ∑_(b, b') ∈𝒢^B^ e_b, b' (u_b,j - u_b', j)^2 . 
        + . ∑_(m, m') ∈𝒢^M^ e_m, m' (u_m,j - u_m', j)^2 ]

where ℬ and ℳ are the sets of bug reports and methods respectively, y_b,m is a binary label that indicates whether method m is relevant to bug report b (y_b,m = 1) or not (y_b,m = 0), and σ(f̂_b,m) = 1/1 + exp(-f̂_b,m) is the logistic function <cit.>. Also, w_b,m denotes the instance weight of a bug report–method pair (b,m), while e_b,b' and e_m,m' are the edge weights reflecting the degree of similarity between two bug reports b and b', and two methods m and m', respectively. Finally, α > 0 and β > 0 are the user-defined parameters that control the strength of the ridge and network Lasso regularization, respectively.

Note that ℒ_Entropy refers to the so-called cross-entropy loss <cit.>, which provides an error measure of the bug localization process. Here ℒ_Entropy can be interpreted as the discrepancy between the probability distribution of the predictive model f̂_b,m and that of the true label y_b,m <cit.>. We also introduce the instance weight[An instance refers to a specific bug report–method pair (b,m)] w_b,m in (<ref>) to cater for the extremely skewed distribution of the relevant vs. irrelevant methods for a given bug report, which is a major challenge in bug localization process. That is, the number of relevant (faulty) methods is much smaller than that of irrelevant (non-faulty) ones. To address this, we configure w_b,m in such a way that imposes a greater penalty for relevant instances being incorrectly predicted/classified than that for irrelevant ones. Specifically, we set w_b,m as:

    w_b,m =
    1/N_faulty,        if  y_b,m = 1
    1/N - N_non-faulty,    if  y_b,m = 0

where N is the total number of instances observed in the historical data, and N_faulty is the number of faulty instances.

Meanwhile, the ridge regularization ℒ_Ridge serves to penalize large values of the model parameters <cit.>, which in turn helps mitigate the risk of data overfitting. From a probabilistic perspective, this corresponds to the Gaussian prior distribution for the model parameters u_b,j and v_m,j, with zero mean and inverse variance of α <cit.>. Finally, ℒ_NetLasso refers to the network Lasso regularization <cit.>, which enforces clustering of the model parameters of bug reports and methods. The intuition is straightforward—the more similar two bug reports or two methods are (as quantified by e_b,b' and e_m,m'), the closer their model parameters u⃗_b and v⃗_m should be. This combination of ℒ_Entropy, ℒ_Ridge and ℒ_NetLasso facilitates a robust model that can simultaneously optimize the bug localization quality and cluster the model parameters of similar bug reports and methods.

Next, in order to minimize the joint loss ℒ, we employ a Newton method <cit.> that is derived from a second-order Taylor series expansion of the loss function ℒ:

    ℒ(θ) = ℒ(θ_0) + ▿ℒ(θ_0) (θ - θ_0) + ▿^2 ℒ(θ_0)/2 (θ - θ_0)^2

The minima of ℒ can be obtained by taking the partial derivative of ℒ(θ) and equating it to zero:

    0    = ▿ℒ(θ_0) + ▿^2 ℒ(θ_0) (θ - θ_0) 
    θ   = θ_0 - ▿ℒ(θ_0)/▿^2 ℒ(θ_0)

If we take θ_0 as the old estimate of u_b,j or v_m,j, this leads to the following update formulae:

    u_b,j   ← u_b,j - ▿ℒ(u_b,j) /▿^2 ℒ(u_b,j) 
    
    v_m,j   ← v_m,j - ▿ℒ(v_m,j) /▿^2 ℒ(v_m,j)


In turn, we need to compute the first and second derivatives of each model parameter u_b,j and v_m,j. For the  bug report parameter u_b,j, the first and second derivatives are respectively given by:

    ▿ℒ(u_b,j)    = ∑_m ∈ℳ[ w_b,m (σ(f̂_b,m) - y_b,m) x_b,m,j] 
       + α u_b,j + β∑_b'[ e_b,b'( u_b,j - u_b',j) ] 
    ▿^2 ℒ(u_b,j)    = ∑_m ∈ℳ[ w_b,mσ(f̂_b,m) ( 1 - σ(f̂_b,m) ) x_b,m,j^2 ] 
       + α + β∑_b' e_b,b'

Similarly, we can compute the first and second derivatives w.r.t each  method parameter v_m,j as:

    ▿ℒ(v_m,j)    = ∑_b ∈ℬ[ w_b,m (σ(f̂_b,m) - y_b,m) x_b,m,j] 
        + α v_m,j + β∑_m'[ e_m,m'( v_m,j - v_m',j) ] 
    ▿^2 ℒ(v_m,j)    = ∑_b ∈ℬ[ w_b,mσ(f̂_b,m) ( 1 - σ(f̂_b,m)) x_b,m,j^2 ] 
        + α + β∑_m' e_m,m'


[!ht]
	
	Adaptive learning of the NetML integrator
	























Finally, the update formula for u_b,j can be obtained by substituting equation (<ref>) and (<ref>) into equation (<ref>). Likewise, we can substitute (<ref>) and (<ref>) into (<ref>) to arrive at the update formula for v_m,j. To learn the model parameters, we use a Newton method that updates the parameters on a per-feature j basis. This will be elaborated in Section <ref>.




 §.§ Adaptive Learning



Algorithm <ref> summarizes the adaptive learning procedure of the NetML integrator for computing the relevancy scores of a new bug report (i.e., a new query) to different methods (i.e., documents). Given a new bug report b^*, the set of K relevant bug reports ℬ_K in the historical data,  the set of all methods ℳ, and the similarity graphs 𝒢_B and 𝒢_M, the learning procedure appends b^* into ℬ_K and then updates the model parameters on a per-feature basis. That is, for each feature j, it performs Newton updates on the  bug report parameters u_b,j (steps 14–16) and  method parameters v_m,j (steps 23–25), in accordance with equations (<ref>) and (<ref>) respectively. The key idea here is to alternatingly update the parameter for one feature while keeping the parameters of the remaining features fixed. The procedure is repeated until a maximum iteration T_max is reached. Afterwards, the final prediction score f̂_b^*,m of the new bug report b^* for each method m is computed via equation (<ref>).

Note that the selection of relevant bug report set B_K is based on the K-nearest neighbor retrieval from the bug report similarity graph 𝒢_B, as follows:

    ℬ_K = Top_K( { e_b^*, b|∀ b ≠ b^* } )

where Top_K is a function that returns bug reports with the highest similarity e_b^*, b to the query bug report b^*. The calculation of the similarity graphs is based on the VSM model and will be further described in Section <ref>.

It is also worth mentioning that the magnitude of the Newton update is downscaled by an adaptive learning rate η (where 0 < η≤ 1). We introduce this scaling factor as a way to address the problem of overshooting in Newton method <cit.>, whereby the update ▿ℒ(u_b,j) /▿^2 ℒ(u_b,j) or ▿ℒ(v_m,j) /▿^2 ℒ(v_m,j) is overestimated—possibly by many orders of magnitude. This may lead to oscillations and sometimes divergence in the loss function. To alleviate this issue, we compare the loss function ℒ before and after a Newton iteration (step 30), and then adjust η accordingly depending on whether ℒ increases or not. If it increases, then we reduce η by half in order to dampen the update magnitude; otherwise, the value of η gets doubled, up to a maximum limit of 1.

For computational efficiency, we precompute the constant terms q_b = ∑_b' e_b,b' and q_m = ∑_m' e_m,m' before the Newton iterations begins. Additionally, during each Newton iteration, we have separate loops to compute the terms ∑_b' e_b,b' u_b',j (step 11) and ∑_m' e_m,m' v_m',j (step 20) for each feature j, prior to updating u_b,j and v_m,j. The purpose is to make sure that, during the parameter updates (steps 14 and 23), the computation of ∑_b' e_b,b' u_b',j in equation (<ref>) and ∑_m' e_m,m' v_m',j in equation (<ref>) is based on the old parameter values from the previous iteration, and not affected by the ordering of b or m in the update loops.





We additionally highlight that the loss function ℒ is strictly convex. This provides a nice theoretical guarantee that there is only one unique minimum in the loss function surface, and this minimum is globally optimal <cit.>. The convexity trait can be proven by looking at the curvatures (i.e., second derivatives) with respect to the  bug report and method parameters, as per equations (<ref>) and (<ref>) respectively. Clearly, since 0 ≤σ(f̂_b,m) ≤ 1, w_b,m, x_b,m,j^2, e_b,b' and e_m,m' are non-negative, while α and β are positive, the curvatures will be positive. The positive curvatures correspond to the so-called positive definite Hessian matrix—a well-known property of a strictly convex function <cit.>.










§ EXPERIMENTS 



§ EXPERIMENTS 



In this section, we first describe the datasets and evaluation settings used in our experiments. We then present a list of research questions we want to address, and accordingly elaborate our experiment results. 





 §.§ Dataset




To evaluate our approach, we use a dataset of 355 bugs from seven popular software projects. The seven projects are Ant <cit.>, AspectJ <cit.>, Lang <cit.>, Lucene <cit.>, Math <cit.>, Rhino <cit.>, and Time <cit.>. All seven projects are medium-large scale and implemented in Java. Ant, AspectJ, and Lucene contain more than 300 KLOC. Math, Rhino, and Time contains almost 100 KLOC, while Lang only contains more than 50 KLOC. Ant, Lang, Lucene, and Math projects use Jira as the issue tracking system, from which we retrieve their bug reports. Bissyande et al. found that in Jira bugs are generally well linked to commits that fix them <cit.>. AspectJ and Rhino uses Bugzilla whereas Time uses Github as the issues tracking system, from which we collect their bug reports. Table <ref> presents an overview of the seven projects considered in our study.





















The 116 bugs from Ant, Lucene, and Rhino were collected by ourselves, following the procedure used in <cit.>. For each bug, we collected the pre-fix version, post-fix version, a set of successful test cases, and at least one failing test case. A failing test case is often included as an attachment to a bug report or committed along with the fix in the post-fix version. When a developer receives a bug report, he/she first needs to replicate the error described in the report <cit.>. In this process, he is creating a failing test case. Unfortunately, not all test cases are documented and saved in the version control systems. The 41 AspectJ bugs are from the iBugs dataset which was collected by Dallmeier and Zimmermann <cit.>. Each bug in the iBugs dataset comes with the code before the fix (pre-fix version), the code after the fix (post-fix version), and a set of test cases. The iBugs dataset contains more than 41 AspectJ bugs, but not all of them come with failing test cases. Test cases provided in the iBugs dataset are obtained from the various versions of the regression test suite that comes with AspectJ. We collected the remaining 198 bugs from Lang, Math, and Time from Defects4J benchmark <cit.>, a database of real, isolated, reproducible software faults from real-world open-source Java projects. The three projects include a large number of test cases, and there exists at least one failing test case per bug. Defects4J also contains two other projects, namely JFreechart and Closure-Compiler. We omit these projects since we are unable to fully collect all their bug reports. 






















































 §.§ Evaluation Metrics and Settings



To assess the effectiveness of a bug localization method, we employ two key metrics, namely: Top N and mean average precision (MAP). They are respectively described below:


	
  * Top N: Given a bug report, if one of its corresponding faulty methods is in the top-N results, we consider that the bug is successfully localized. The Top N score of a bug localization method is the number of bugs it can successfully localize <cit.>.
	
  * Mean Average Precision (MAP): MAP is an IR metric to evaluate ranking approaches <cit.>, and is computed by taking the mean of the average precision scores across all bug reports. The average precision of a single bug report is computed as:
	
    AP = ∑_k=1^MP(k) × pos(k)/∑_k=1^M pos(k)

	where k is a rank in the returned ranked methods, M is the number of ranked methods, and pos(k) indicates whether the k^th method is faulty or not. Here P(k) is the precision at a given top k methods, which is computed as follows:
	
    P(k)=#faulty methods in the top k/k.

Note that the MAP scores of existing bug localization methods are typically low <cit.>.




















Our evaluation procedure is based on 10-fold cross validation (CV). That is, for each project, we divide the bug reports into ten (mutually exclusive) sets. Then, for each fold, we take 1 set as new bug report queries (i.e., testing set) and treat the remaining 9 sets as historical bug reports (i.e., training set). We repeat this 10 times, and then collate the results to get the aggregated Top N and MAP scores.
	
In all our experiments, the hyper-parameters of the NetML method were configured as follows. Firstly, the regularization parameters α and β were chosen by performing 10 fold cross validation on the training set. Next, the maximum number of iterations T_max was fixed to 30. We use K=10 as default value for the number of nearest neighbors. Note that the NetML parameters K and T_max follow the settings used in AML <cit.>, so as to ensure fair comparisons. All experiments were conducted on an Intel(R) Xeon 2.9GHz server running a Linux operating system.

In order to assess whether NetML substantially outperforms other bug localization methods, we apply Wilcoxon signed-rank test <cit.>; it is a non-parametric statistical significance test for comparing two related or matched samples, whereby the population cannot be assumed to be normally distributed. The Wilcoxon test was applied to two types of metric (i.e., Top N and MAP). For every evaluation metric, we collated the 10-fold results of a bug localization technique across the four software projects (i.e., AspectJ, Ant, Lucene, and Rhino) and then performed the Wilcoxon test to compare the collated results of different techniques. For this test, our null hypothesis is that NetML performs worse than or equal to the other method, and so we used one-sided/tail p-value to validate this hypothesis. Moreover, we also apply the Benjamini-Hochberg (BH) <cit.> procedure to control the effect of multiple comparisons. If the p-value is sufficiently small (say, below a significance level of 0.05), we can confidently reject the null hypothesis and conclude that NetML is significantly better than the other method.



 §.§ Research Questions



Our empirical study seeks to answer several research questions (RQ), as described in the following subsections.



  §.§.§ RQ1: How Effective is NetML Compared to Other State-of-the-Art Techniques?




We compare out NetML approach with its predecessor, i.e., AML <cit.>, and several other state-of-the-art techniques. Previously, Le et al. proposed Savant <cit.>, a state-of-the-art bug localization approach that employs a learning-to-rank <cit.> strategy, using likely invariant diffs and suspiciousness scores as features. Ochiai <cit.> and Dstar <cit.> are well-known statistical formulas to detect suspicious locations for bug localization without requiring any prior information on program structure or semantics. PROMESIR <cit.>, SITIR <cit.>, and several variants developed by Dit et al. <cit.> were state-of-the-art multi-modal feature location techniques. Among the variants proposed by Dit et al. <cit.>, the best performing ones were IR_LSIDyn_binWM_HITS(h,bin)^bottom and  IR_LSIDyn_binWM_HITS(h,freq)^bottom. In this paper, we refer to these variants as DIT^A and DIT^B respectively. Dit et al. had shown that these two variants outperform SITIR, and so we exclude SITIR from our study. We also compare NetML with a state-of-the-art IR-based bug localization method named LR <cit.>, and a state-of-the-art spectrum-based bug localization method named MULTRIC <cit.>. Note that, unlike PROMESIR, DIT^A, DIT^B, and MULTRIC which locate buggy methods, LR locates buggy files. Thus, we convert the list of files that LR produces into a list of methods by using two heuristics: (1) to return methods in a file in the same order that they appear in the file; and (2) to return methods based on their similarity to the input bug report as computed using a VSM model. We refer to the two variants of LR as LR^A and LR^B respectively.



For all the above-mentioned techniques, we used the same parameters and settings as described in the respective papers, with the following exceptions that we justify. For DIT^A and DIT^B, the threshold used to filter methods using HITS was decided “such that at least one gold set method remained in the results for 66% of the [bugs]” <cit.>. In this paper, since we used 10-fold CV, rather than using 66% of all bugs, we used all bugs in the training data (i.e., 90% of all bugs) to tune the threshold. For PROMESIR, we also used 10-fold CV and applied a brute force approach to tune PROMESIR's component weights using a step of 0.05.









  §.§.§ RQ2: Do Feature Components of NetML Contribute toward Its Overall Performance?




To answer this question, we conducted an ablation test by dropping one feature component (i.e., NetML^Text, NetML^SuspWord, or NetML^Spectra) one-at-a-time and evaluating the performance. In the process, we created three variants of NetML: All^-Text, All^-SuspWord , and  All^-Spectra. That is, we excluded Text, SuspWord, and Spectra from all feature components, respectively (see also Fig. <ref>). We used the default value of K=10, and applied the NetML adaptive learning procedure (i.e., Algorithm <ref>) to tune the model parameters of these variants. As our baseline, we performed the same ablation test to the feature components of the AML method (i.e., AML^Text, AML^SuspWord, or AML^Spectra).











  §.§.§ RQ3: How Effective is the NetML Integrator?


Instead of using the NetML integrator component (see Section <ref>), one may consider using a standard machine learning algorithm, such as the learning-to-rank method, to combine the scores produced by the three feature components. Indeed, state-of-the-art IR-based and spectrum-based bug localization techniques such as LR and MULTRIC are based on the learning-to-rank method. As such, we conduct an experiment to compare our NetML integrator model with an off-the-shelf learning-to-rank model called SVM^rank <cit.>, which was also used by LR <cit.>. To do so, we simply replace the NetML integrator model in Fig. <ref> with SVM^rank, and then compare the resulting performances. For completeness, we also compare our NetML integrator with the integrator model used by the AML algorithm.

C[1]>p#1
L[1]>p#1












  §.§.§ RQ4: What is the Effect of Varying the Number of Neighbors K on the Performance of NetML?


The most important parameter in our NetML approach is the number of nearest neighbors K (while the regularization parameters α and β were chosen via cross-validation—see Section <ref>). By default, we set the number of neighbors to K=10, but the effect of varying this value is unclear. To answer this research question, we vary the value of K and investigate its effects on the performance of NetML. In particular, we wish to investigate if the performance remains relatively stable with varying values of K. For each K value, we also compare the performance of NetML against its predecessor (i.e., AML) using the same value.













  §.§.§ RQ5: How Effective is NetML in Cross-Project Bug Localization?




To evaluate the robustness of our approach, we also conducted an empirical study on cross-project bug localization. That is, we first use a source project as training data to build a bug localization model, and then employ the model to predict a method that likely contains a bug in a (different) target project <cit.>. In this study, we compare NetML with its predecessor (i.e., AML) <cit.>, Savant <cit.>, Ochiai <cit.> and Dstar <cit.>. 
We use the same evaluation metrics as per Section <ref> to assess the effectiveness of the different techniques. 
To configure the hyper-parameters of NetML, we adopt the same parameter tuning procedure as described in Section <ref>. Meanwhile, the hyper-parameters of the remaining localization techniques follow the parameter settings stated in their respective papers. We also apply Wilcoxon signed-rank test with the BH procedure to verify if NetML performs substantially better than the other techniques.






 §.§ Results



This section presents our experiment results and discussion in relation to the research questions raised in Section <ref>.



  §.§.§ RQ1: Comparisons of NetML with Other Techniques

















































































Tables <ref> and <ref> show the Top N results of NetML as well as the other baseline methods including AML. Out of the 355 bugs, NetML is able to successfully localize 116, 219, and 255 bugs when the developers inspect the Top 1, Top 5, and Top 10 methods respectively. This implies that NetML can successfully localize 31.82%, 22.35%, and 19.72% more bugs than the best baseline (i.e., AML) by examining the Top 1, Top 5, and Top 10 methods respectively. For more details on the Top N results for each software project, please see Tables <ref> and <ref> in the Appendix.

Note that we encountered java.lang.UnsupportedClassVersionError when running Savant for AspectJ bugs. These AspectJ bugs are from iBugs dataset <cit.>. We have investigated and found that according to iBugs's documentation[ https://www.st.cs.uni-saarland.de/ibugs/], the AspectJ's faulty versions work with Java Virtual Machine (JVM) version 1.4. However, Savant employs Daikon <cit.> which requires Java 7 or later[ http://plse.cs.washington.edu/daikon/download/doc/daikon.html]. Therefore, we exclude AspectJ's bugs from the experiments 

for Savant.

















Table <ref> shows the MAP score of NetML along with those of the state-of-the-art multi-modal localization methods. Averaging across the seven projects, NetML achieves an overall MAP score of 0.347, which outperforms all the other baselines. In particular, NetML improves the average MAP of AML, Savant, Ochiai, Dstar, PROMESIR, DIT^A, DIT^B, LR^A, LR^B, and MULTRIC by 19.24%, 32.44%, 151.45%, 204.39%, 57.01%, 166.92%, 62.15%, 339.24%, 76.14% and 43.98% respectively. Considering the individual projects, NetML remains the best performing approach in terms of MAP. That is, NetML achieves MAP scores of 0.270, 0.219, 0.638, 0.290, 0.358, 0.302, and 0.354 for the Ant, AspectJ, Lang, Lucene, Math, Rhino, and Time projects respectively. With respect to the best performing baseline (i.e., AML), these respectively constitute of 15.38%, 17.11%, 17.71%, 2.11%, 40.39%, 24.28%, and 20.41% improvements.









We finally performed the Wilcoxon test to compare the Top N and MAP results of different techniques. As we are unable run Savant on AspectJ, we omit this project and run the Wilcoxon test on the results collated over the remaining six software projects for each metric (i.e., Top 1, Top 5, Top 10, and MAP). Table <ref> presents the p-values for the four metrics, evaluated at the significance levels of 0.05 and 0.01. The results show that NetML significantly outperforms AML on all the four metrics. Compared to the remaining techniques, NetML also performs significantly better in terms of Top 1, Top 5, Top 10 methods and MAP. Altogether, these results demonstrate the efficacy of the proposed NetML approach.



































































  §.§.§ RQ2: Contribution of Feature Components






Table <ref> summarizes the results of our ablation test on both NetML and AML, each comparing the full model and three reduced variants (i.e., All^-Text, All^-Spectra and All^-SuspWord). It is evident that, for both NetML and AML,  the full model always performs better than the reduced variants. This suggests that each feature component plays an important role, and omitting one of them may greatly affect the modelling performance. Among the three variants, it can be seen that All^-SuspWord yields the smallest Top 1, Top 5, Top 10, and MAP scores for both NetML and AML. This suggests that the SuspWord feature component is more important than the other two (i.e., Text and Spectra).

Furthermore, comparing the results of NetML and AML, we can also observe that the former always gives a better, or at least equal, result than the latter. This suggests that the model parameterization using two sets of model parameters (instead of one in AML), along with the objective function formulation that jointly optimizes bug localization error and fosters clustering of similar bug reports and methods, contribute to a better overall performance of NetML.















  §.§.§ RQ3: Comparisons among Integrator Models




Table <ref> compares the performance of the NetML integrator model with that of the AML integrator and SVM^rank. We can observe that for all projects (i.e., AspectJ, Ant, Lucene, and Rhino) and metrics, the NetML integrator outperforms both the AML integrator and SVM^rank. With respect to SVM^rank, NetML achieves 39.76%, 25.15%, 20.28%, and 24.37% improvements, in terms of Top 1, Top 5, Top 10 and MAP scores across the four software projects, respectively. This can again be attributed to our NetML approach taking advantage of two sets of model parameters and performing a joint optimization of bug localization error and clustering of similar bug reports and methods.

We also conducted the Wilcoxon test to examine whether the improvements over the AML integrator and SVM^rank are statistically significant. The resulting p-values are summarized in Table <ref>. As before, the NetML integrator significantly outperforms the AML integrator in terms of Top 1, Top 5, Top 10, and MAP scores. Moreover, the NetML integrator is significantly better than SVM^rank in all evaluation metrics (i.e., Top 1, Top 5, Top 10, and MAP). All in all, these justify the effectiveness of our NetML integrator component.













































  §.§.§ RQ4: Effect of Varying Number of Neighbors


























To address this research question, we varied the number of nearest neighbors from K=5 to all bug reports in the training set (i.e., K=∞) for both NetML and AML. The results are shown in Table <ref>. We can see that, as we increase K, the performance of both multi-modal techniques improves until a certain point (i.e., K=15), and decreases beyond that. This suggests that including more neighbors can improve performance to some extent. However, an overly large number of neighbors may lead to an increased level of noise (i.e., the number of irrelevant neighbors), resulting in a degraded performance. Nevertheless, the differences in the Top N and MAP scores are fairly marginal, which justifies the robustness of our NetML approach. Looking at Table <ref>, it is also clear that NetML consistently outperforms AML for all K values (i.e., from K=5 to K=∞).
































  §.§.§ RQ5: How Effective is NetML in Cross-Project Bug Localization?




































































































Table <ref> shows the overall performance of NetML and the baseline methods (i.e., AML, Savant, Ochiai, and Dstar) for the cross-project setting, in terms of the Top N and MAP scores respectively. 

Ochiai and Dstar are unsupervised learning methods, which do not depend on training labels. In this case, they give the same result for both cross-project and within-project settings. Hence, we reuse their results in Table <ref>.
For the remaining techniques (i.e., NetML, AML, and Savant), we use a source project that has the best MAP score for a target project. The results show that NetML outperforms the best baseline (i.e., AML) by 27.59%, 19.85%, and 15.88% in terms of the Top 1, Top 5, and Top 10 methods, respectively. In terms of MAP, NetML outperforms AML, Savant, Ochiai, and Dstar by 25.29%, 63.91%, 91.23%, and 57.97% respectively. For more details on the Top N results for each pair of source and target projects, please see Tables <ref> and <ref> in the Appendix.

We also perform Wilcoxon test to compare the overall results of the different techniques in the cross-project setting. Table <ref> shows the p-values for different evaluation metrics (i.e., Top 1, Top 5, Top 10, and MAP) and pairs of techniques. The results indicate that NetML significantly outperforms all the baseline techniques (i.e., AML, Savant, Ochiai, and Dstar) for all the four metrics, thus demonstrating the superior performance of NetML in cross-project setting.








  
















§ RESULTS ANALYSIS AND DISCUSSION



In this section, we present a detailed analysis of the results obtained in Section <ref>. Firstly, we present some examples to understand the scenarios in which NetML would perform well or poorly in Section <ref> and Section <ref>, respectively. Section <ref> subsequently presents an analysis on how NetML can improve the MAP performance.

















































































































































































































































































































































 §.§ Successful Cases




We first present two examples of successful bug localization, with the goal of showing how NetML can take advantage of two types of similarity: 1) similarity among bug reports, and 2) similarity among methods. 





Bug report similarity. Our first example involves Bug 30798[<https://bz.apache.org/bugzilla/show_bug.cgi?id=30798>] and Bug 43969[<https://bz.apache.org/bugzilla/show_bug.cgi?id=43969>] from project Ant – see Fig. <ref>. It has been briefly described in Section 1. NetML can outperform AML in identifying the buggy method of Bug 43969 by taking advantage of similarity among bug reports. To confirm that indeed these two bug reports are similar, we can apply the Vector Space Model (VSM) <cit.>. We represent each bug report as a TF-IDF vector <cit.>, and then compute the cosine similarity between the TF-IDF vector of Bug 30798 and that of the remaining bug reports. We find that Bug 43969 is ranked at position #3. Likewise, we compute the cosine similarity between Bug 43969 and the other bug reports. Here, Bug 30798 is ranked at position #5. This shows that Bug 30798 and Bug 43969 are indeed very similar. AML assumes that the bug reports are independent and, owing to the lack of information on the textual description of Bug 43969, it fails to localize the faulty method. In contrast, we found that NetML learns similar model parameters (i.e., u⃗_b) for the two bug reports, and exploits this to compensate for the insufficient information when localizing Bug 43969.

Additionally, we find that none of the other baselines perform as well as NetML. Savant can localize the faulty method of Bug 30798 in its top-10 list, but it fails to do so for Bug 43969. For the other baselines (i.e., Ochiai, Dstar, PROMESIR, DIT^A, DIT^B, LR^A, LR^B, and MULTRIC), none of them is able to localize the faulty method for both bug reports. Among them, the two best performers (i.e., Ochiai and Dstar) give a high suspiciousness score to the faulty method, but there are more than 100 methods sharing this score.



































Method similarity. Fig. <ref> presents the description of Bug 31389[<https://bz.apache.org/bugzilla/show_bug.cgi?id=31389>] in project Ant. The bug resides in the  and  methods of . NetML is able to localize both methods at positions #1 and #9 respectively, all within the top 10 list. Meanwhile, AML is able to put the  method in the top 10 list, but it ranks the  method at position #17. Ochiai, Dstar, PROMESIR and MULTRIC localize the  method in the top 10 list, but they fail to put the  into the top 10 list. The other baselines give low relevancy scores to the two methods, and exclude them from the top 10 list.

As with the previous example, we try to analyze this further by computing the cosine similarity of the TF-IDF representation of the methods' source code. Specifically, we compute the cosine similarity between  and remaining methods. The result shows that the  method is ranked at position #4. Looking at the content of these two methods, it can again be seen that they share many common word tokens (e.g., “elementName”, etc.). Accordingly, NetML would enforce the corresponding method parameters to be similar. As such, NetML manages to successfully to localize the  method at position #9. In contrast, AML assumes that the methods are independent, and thus fails to leverage the strength of similar methods to localize the  method.




























































































































































































































































































To see how typical the successful cases are in our dataset, we randomly select

75 out of 183 successful cases, in which NetML manages to localize a faulty method within the top 10 list whereas the other baseline methods (i.e., AML, Savant, Ochiai, Dstar, PROMESIR, DIT^A, DIT^B, LR^A, LR^B, and MULTRIC) 
fail to do so. Among these cases, in total, we find that 63 successful cases, which constitute the majority (84%) of our samples, are similar to the first (17 cases) and second (46 cases) examples we presented earlier.






 §.§ Unsuccessful Cases






Next, we present two examples whereby NetML fails to localize a bug. These examples serve to provide an understanding of cases in which NetML may not perform well.








Bug report similarity. We first consider Bug 338[<https://issues.apache.org/jira/browse/MATH-338>] and Bug 358[<https://issues.apache.org/jira/browse/MATH-358>] from project Math shown in Fig. <ref>. The faulty method for these two bug reports is the  method in . Interestingly, Ochiai and Dstar manage to localize this faulty method for these two bug reports within the top 10 list. On the other hand, NetML, AML, and Savant fail to localize the faulty  method for Bug 358. Specifically, NetML, AML, and Savant rank the faulty method at positions #14, #19, and #23 respectively. MULTRIC assigns a high suspiciousness score to the  method for both Bug 338 and Bug 358. However, there are around 30 methods sharing this score. Also note that the remaining baselines (i.e., PROMESIR, DIT^A, DIT^B, LR^A, and LR^B) fail to localize the faulty method for both bug reports.

Similar to Section <ref>, we calculate the cosine similarity between Bug 338 and the remaining bug reports. We found that Bug 358 is ranked at position #53, suggesting that the two bug reports are dissimilar. As such, there is less incentive for NetML to leverage the strength of common words shared by the two bug reports, which potentially explains why it fails to localize the faulty method for Bug 358. This also suggests that, when the data contain bug reports that are largely dissimilar (i.e., share very few common word tokens), our NetML approach may not work as well as some spectrum-based fault localization techniques such as Ochiai and Dstar.














Method similarity. Fig. <ref> shows the descriptions of Bug 30962[<https://bz.apache.org/bugzilla/show_bug.cgi?id=30962>] in project Ant. The bug is associated with two faulty methods, i.e.,  and  in  . We find that Ochiai and Dstar successfully localize these two methods in the top 10 list. NetML and AML are able to localize the  method within the top 10 list. However, they fail to localize the faulty  method for Bug 30962. In particular, NetML and AML place the  method at positions #17 and #15 respectively. The remaining techniques (i.e., Savant, PROMESIR, DIT^A, DIT^B, LR^A, LR^B) fail to localize these two methods in the top 10 list.

To better understand this, we again compute the cosine similarity between the  method and the remaining methods in project Ant. In this case, the  method is ranked at position #478. This suggests that these two methods have low proximity, which gives less incentive for NetML to utilize their common words in the localization of the  method. It also suggests that, when the data contain methods that are mostly dissimilar, spectrum-based fault localization techniques (e.g., Ochiai and Dstar) may perform better than NetML.



To again evaluate how typical the unsuccessful cases are in seven projects, we randomly select 75 (out of 80) unsuccessful cases whereby NetML fails to localize a faulty method within the top 10 list, but one of the baseline method (i.e., AML, Savant, Ochiai, Dstar, PROMESIR, DIT^A, DIT^B, LR^A, LR^B, and MULTRIC) succeed. Among them, in total, we discover that 70 unsuccessful cases, which constitute 93% of our samples, are similar to the first (21 cases) and second (49 cases) unsuccessful examples presented earlier.













































 §.§ Improved vs. Deteriorated Bug Reports
























To understand how the MAP results improve due to NetML, following Chaparro et al. <cit.>, we perform a finer-grained analysis in terms of the number of bug reports improved/deteriorated and the expected magnitude of improvement/deterioration. We compare our approach against the best baseline method (i.e., AML). A bug report is improved if the rank of the top faulty method produced by NetML is better than the rank of the top faulty method produced by AML. On the other hand, a bug report is deteriorated if the rank of the top faulty method produced by NetML is worse than that produced by AML. Otherwise, a bug report is unchanged. Ideally, we wish to have a higher number of improved bug reports than that of deteriorated bug reports. To measure the relative magnitude of improvement or deterioration for each bug report, we adopt the approach described in <cit.>. In particular, for improved and deteriorated bug reports, we compute the expected average precision (AP) difference E[Δ AP] and expected rank difference E[Δ Rank] as follows:



    E[Δ AP] = 1|ℬ|∑_b=1^ℬ (AP_b^NetML - AP_b^AML)



    E[Δ Rank] = 1|ℬ|∑_b=1^ℬ (Rank_b^AML - Rank_b^NetML)


where |ℬ| is the number of bug reports, AP_b^NetML and AP_b^AML are the average precision produced by NetML and AML for bug report b, and Rank_b^NetML and Rank_b^AML are the rank produced by NetML and AML, respectively. Intuitively, if NetML is better than AML, we expect the E[Δ AP] and E[Δ Rank] for improved bug reports to be larger than those of deteriorated bug reports.

Table <ref> shows the number of improved, deteriorated, and unchanged bug reports in our seven projects. Additionally, Table <ref> presents the E[Δ AP] and E[Δ Rank] for improved and deteriorated cases of different projects. 
The results show that the number of improved bug reports is indeed higher than the number of deteriorated bug reports for all different projects.
It is also evident that the overall E[Δ AP] and E[Δ Rank] of improved bug reports are higher than those of deteriorated bug reports. This implies that MAP improvement comes from improvements across the boards and not due to a few outlier bug reports or projects. 














































































































§ THREATS TO VALIDITY



This section presents a number of threats that may potentially impact the validity of our study.



 §.§ Number of Failed Test Cases and Its Impact


In our experiments with 355 bugs, most of the bugs were found to come with few failed test cases (average = 2.155). We have investigated if the number of failed test cases impacts the effectiveness of our approach. To this end, we computed the differences between the average number of failed test cases for bugs that are successfully localized at Top-N positions (N = 1,5,10) and bugs that are not successfully localized. We found that the differences are small (-0.362 to 0.055 test cases). These indicate that the number of test cases does not impact the effectiveness of our approach significantly and typically 1 to 3 failed test cases are sufficient for our approach to be effective.



 §.§ Threats to Internal Validity


Threats to internal validity relate to implementation and dataset errors. We have checked our implementations and datasets. However, there could still be errors that we do not notice. Threats to external validity relate to the generalizability of our findings. In this work, we have analyzed 355 real bugs from seven medium-large software systems. In the future, we plan to reduce the threats to external validity by investigating more real bugs from additional software systems, written in various programming languages. 






 







§ RELATED WORK



§ RELATED WORK



In this section, we highlight a number of research studies that are closely related to our work.













 §.§ Multi-Modal Feature Location
 

Multi-modal feature location takes as input a feature description and a program spectra, and finds program elements that implement the corresponding feature. There are several multi-modal feature location techniques proposed in the literature <cit.>.

Poshyvanyk et al. proposed an approach named PROMESIR that computes weighted sums of scores returned by an IR-based feature location solution (LSI <cit.>) and a spectrum-based solution (Tarantula <cit.>), and rank program elements based on their corresponding weighted sums <cit.>. Then, Liu et al. proposed an approach named SITIR which filters program elements returned by an IR-based feature location solution (LSI <cit.>) if they are not executed in a failing execution trace <cit.>. Later, Dit et al. used HITS, a popular algorithm that ranks the importance of nodes in a graph, to filter program elements returned by SITIR <cit.>.

Several variants are described in their paper and the best performing ones are IR_LSIDyn_binWM_HITS(h,bin)^bottom and  IR_LSIDyn_binWM_HITS(h,freq)^bottom. We refer to these two as DIT^A and DIT^B, respectively. They have showed that these variants outperform SITIR, though they have never been compared with PROMESIR.

In this work, we compare our proposed approach against PROMESIR, DIT^A and DIT^B. We show that our approach outperforms all of them on all datasets.



 §.§ IR-Based Bug Localization
 

Various IR-based bug localization approaches that employ information retrieval techniques to calculate the similarity between a bug report and a program element (e.g., a method or a source code file) have been proposed <cit.>. 

Lukins et al. used a topic modeling algorithm named Latent Dirichlet Allocation (LDA) for bug localization <cit.>. Then, Rao and Kak evaluated the use of many standard IR methods for bug localization including VSM and Smoothed Unigram Model (SUM) <cit.>. In the IR community, VSM has a long history, proposed four decades ago by Salton et al. <cit.> and followed by many other IR methods including SUM and LDA, which address the limitations of VSM.



More recently, a number of approaches which consider information aside from text in bug reports to better locate bugs were proposed. Sisman and Kak proposed a version history-aware bug localization method that considers past buggy files to predict the likelihood of a file to be buggy and uses this likelihood along with VSM to localize bugs <cit.>. Around the same time, Zhou et al. <cit.> proposed an approach named BugLocator that includes a specialized VSM (named rVSM) and considers the similarities among bug reports to localize bugs. Next, Saha et al. <cit.> developed an approach that considers the structure of source code files and bug reports and employs structured retrieval for bug localization, and it outperforms BugLocator. Wang and Lo proposed an approach that integrates the approaches by Sisman and Kak, Zhou et al. and Saha et al. for more effective bug localization <cit.>. Most recently, Ye et al. devised an approach named LR that combines multiple ranking features using learning-to-rank to localize bugs, and these features include surface lexical similarity, API-enriched lexical similarity, collaborative filtering, class name similarity, bug fix recency, and bug fix frequency <cit.>.






 




All these approaches can be used as the AML^Text component of our approach. In this work, we experiment with a basic IR technique namely VSM. Our goal is to show that even with the most basic IR-based bug localization component, we can outperform existing approaches including the state-of-the-art IR-based approach by Ye et al. <cit.>.



 §.§ Spectrum-Based Bug Localization
 

Various spectrum-based bug localization approaches have been proposed <cit.>. These approaches analyze a program spectra which is a record of program elements that are executed in failed and successful executions, and generate a ranked list of program elements. Many of these approaches propose various formulas that can be used to compute the suspiciousness of a program element given the number of times it appears in failing and successful executions.


Jones and Harrold proposed Tarantula that uses a suspiciousness score formula to rank program elements <cit.>. Later, Abreu et al. proposed another suspiciousness formula called Ochiai <cit.>, which outperforms Tarantula. Then, Lucia et al. investigated 40 different association measures and highlighted that some of them including Klosgen and Information Gain are promising for spectrum-based bug localization <cit.>. Recently, Xie et al. conducted a theoretical analysis and found that several families of suspiciousness score formulas outperform other families <cit.>. Next, Yoo proposed to use genetic programming to generate new suspiciousness score formulas that can perform better than many human designed formulas <cit.>. Subsequently, Xie et al. theoretically compared the performance of the formulas produced by genetic programming and identified the best performing ones <cit.>. Most recently, Xuan and Monperrus combined 25 different suspiciousness score formulas into a composite formula using their proposed algorithm named MULTRIC, which performs its task by making use of an off-the-shelf learning-to-rank algorithm named RankBoost <cit.>. MULTRIC has been shown to outperform the best performing formulas studied by Xie et al. <cit.> and the best performing formula constructed by genetic programming <cit.>.






















Wong et al. <cit.> provided a comprehensive literature review of a large number of spectrum-fault localization techniques, and pointed out avenues for future work. 
Perez et al. <cit.> proposed DUU, a new metric for evaluating the diagnosability of a test-suite when applying spectrum-based fault localization approaches. 
Sohn et al. <cit.> presented FLUCCs, a fault localization technique that learns to rank program elements based on existing spectrum-fault localization techniques and source code metrics such as age, code churn, and complexity. Li et al. <cit.> proposed TraPT, another learning-to-rank approach that transforms programs and test outputs/messages in order to localize faults effectively. 


Pearson et al. <cit.> highlighted that results found by evaluating spectrum-based and mutation-based fault localization techniques on artificial faults are significantly different than when they are evaluated on real faults. They thus recommended that fault localization techniques should be evaluated using real faults. Moreover, they introduced several new variants of a mutation-based fault localization technique that also use coverage information (in addition to mutation information). The best variant outperforms Dstar by 2-6% and 3-6% considering the Top 5 and Top 10 results respectively.

Many of the above mentioned approaches that compute suspiciousness scores of program elements can be used in the AML^Spectra component of our proposed approach. In this work, we experiment with a popular spectrum-based fault localization technique namely Tarantula, published a decade ago, which is also used by PROMESIR <cit.>. Our goal is to show that even with a basic spectrum-based bug localization component, we can outperform existing approaches including the state-of-the-art spectrum-based approaches.





 §.§ Other Related Studies
 

There are many studies that compose multiple methods together to achieve better performance. For example, Kocaguneli et al. <cit.> combined several single software effort estimation models to create more powerful multi-model ensembles. Also, Rahman et al. <cit.> used static bug-finding to improve the performance of statistical defect prediction (and vice versa). Le et al. <cit.> proposed SpecForge that combines different automaton based specification miners using  model fission and model fusion in order to create a more effective specification miner.
Kellogg et al. <cit.> presents N-Prog that combines static bug detection and test case generation to avoid unnecessary human effort. In particular, N-Prog produces no false alarms, by construction, since its output alarm is either a new test case or a bug in a program.








§ CONCLUSION AND FUTURE WORK
 


§ CONCLUSION AND FUTURE WORK



In this paper, we put forward a novel multi-modal bug localization approach  named Network-clustered Multi-modal Bug Localization (NetML). Deviating from the contemporary multi-modal localization approaches, NetML is able to achieve an effective bug localization through the interplay of two sets of model parameters characterizing both bug reports and methods. It also features an adaptive learning procedure that stems from a strictly convex objective function formulation, thereby provides a sound theoretical guarantee on the uniqueness of the optimal solution.

We have extensively evaluated NetML on 355 real bugs from seven different software projects (i.e., Ant, AspectJ, Lang, Lucene, Math, Rhino, and Time). Among the 355 bugs, NetML is able to successfully localize 116, 219, and 255 bugs when developers inspect the Top 1, Top 5, and Top 10 methods, respectively. Compared to the best performing baseline (i.e., AML), NetML can successfully localize 31.82%, 22.35%, and 19.72% more bugs when developers inspect the Top 1, Top 5, and Top 10 methods, respectively. Furthermore, in terms of MAP, NetML outperforms the other baselines by 19.24%. Based on the Wilcoxon signed-rank test using BH procedure, we show that the results of NetML are significantly better across the seven projects, in terms of Top 1, Top 5, Top 10, and MAP scores.

Although NetML offers a powerful bug localization approach, there remains room for improvement. For example, the current approach as well as the IR-based techniques capture both bug reports and program elements (method) using a simple bag-of-words (e.g., TF-IDF) representation, ignoring the inherent structure within the source codes of a program, such as function call and/or data dependencies. 

In the future, we wish to consider a richer set of structural information within a program element, which carries additional semantics beyond the lexical terms. In particular, we would like to leverage both program structure information and lexical source code to localize potential bugs. We also plan to develop a more sophisticated technique, e.g., based on deep learning <cit.>, to automatically learn the feature representation of bug reports and program elements.














Dataset and Codes. The codes and data for NetML are now available at <https://github.com/JHoangSMU/NetML>.
























IEEEtranS





