Recommending Relevant Classes for Bug Reports using
Multi-objective Search
Raﬁ Almhana∗ , Wiem Mkaouer∗ , Marouane Kessentini∗ , Ali Ouni‡∗

Computer and Information Science Department
University of Michigan, Dearborn, MI, USA
ﬁrstname@umich.edu‡

Graduate School of Information Science and Technology
Osaka University, Osaka, Japan
ali@ist.osaka-u.ac.jp

ABSTRACT
Developers may follow a tedious process to ﬁnd the causeof a bug based on code reviews and reproducing the abnormal behavior. In this paper, we propose an automatedapproach to ﬁnding and ranking potential classes with therespect to the probability of containing a bug based on a bug
report description. Our approach ﬁnds a good balance between minimizing the number of recommended classes andmaximizing the relevance of the proposed solution using a
multi-objective optimization algorithm. The relevance of therecommended classes (solution) is estimated based on theuse of the history of changes and bug-ﬁxing, and the lexical
similarity between the bug report description and the API
documentation. We evaluated our system on 6 open sourceJava projects, using the version of the project before ﬁxing the bug of many bug reports. The experimental results
show that the search-based approach signiﬁcantly outperforms three state-of-the-art methods in recommending relevant ﬁles for bug reports. In particular, our multi-objective
approach is able to successfully locate the true buggy methods within the top 10 recommendations for over 87% of the
bug reports.

CCS Concepts•Software and its engineering → Search-based software engineering;

Keywords
Search-based software engineering; bug reports; multi-objective
optimization; software maintenance.

1.

INTRODUCTION

A software bug is a coding error that may cause abnormal
behaviors and incorrect results when executing the system[6]. After identifying an unexpected behavior of the software project, a user or developer will report it in a document, called a bug report [3]. Thus, a bug report should
Permission to make digital or hard copies of all or part of this work for personal or
Permissionuse
to is
make
digitalor hardof thatall orcopies
part ofpersonal orclassroom
grantedwithout
fee copies
providedarethisnot work
madeforor distributedclassroomis grantedadvantage
without fee
providedthat copies
arenoticenot madeor distributed
for
proﬁt oruse
commercial
andthat copies
bear thisand thefull citafor
profitorcommercial
advantage
andthat
copiesbear
thisnoticeandthefullcitationtion on the ﬁrst page. Copyrights for components of this work owned by others
thanon the first page. Copyrights for components of this work owned by others than ACM
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or remust be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
publish,to servers
post on orserversor to redistributelists, requires
prior speciﬁc
permission
to post on
to redistributeto lists, torequiresprior specificpermission
and/or a
and/ora fee. Request
permissions
from permissions@acm.org.
fee. Request
permissions
from Permissions@acm.org.

ASE ’16 September
Singapore, 3–7,
SingaporeASE’16,2016, Singapore, Singapore

cc 2016
ISBN
123-4567-24-567/08/06. . . $15.00
2016ACM.
ACM.
978-1-4503-3845-5/16/09...$15.00

http://dx.doi.org/10.1145/2970276.2970344
DOI:
10.475/123 4

286

provide useful information to identify and ﬁx the bug. The
number of these bug reports can be large. For example,
MOZILLA had received more than 420,000 bug reports [4].
These reports are important for managers and developers
during their daily development and maintenance activities[11].
A developer always uses a bug report to reproduce theabnormal behavior to ﬁnd the origin of the bug. However,the poor quality of bug reports can make this process tedious and time-consuming due to missing information. To
ﬁnd the cause of a bug, developers are not only using their
domain knowledge to investigate the bug report, but interact with peer developers to collect additional information.
An eﬃcient automated approach for locating and ranking
important code fragments for a speciﬁc bug report may leadto improving the productivity of developers by reducing thetime to ﬁnd the cause of a bug [11]. Most of the existingstudies are mainly based on lexical matching scores between
the statements of bug reports and the name of code elements
in software systems [23]. However, there is a signiﬁcant difference between the natural language used in bug reports
and the programming language which limits the eﬃciencyof existing approaches.
In this work, we start from the following observations.
First, API documentation of the classes and methods canbe more useful than the name of code elements or comments
to estimate the similarity between code fragments and bug
reports. Second, classes associated to previously ﬁxed bug
reports may be relevant also to the current report if thesepreviously bug reports are similar to a current bug report.
Third, a code fragment that was ﬁxed recently is more likely
to still contain bugs than another class that was last ﬁxed
long time ago. Fourth, a class that has been frequently ﬁxed,
tend to be fault-prone and may cause more than one abnormal behavior in the future. Finally, the recommendation ofa large number of classes to inspect may make the process
of ﬁnding the cause of a bug time-consuming.
To consider the above observations, we propose a comprehensive approach for bugs localization based on bug reports
description. To this end, we propose, for the ﬁrst time, touse a multi-objective optimization algorithm [7] to ﬁnd abalance between maximizing lexical and history-based similarity, and minimizing the number of recommended classes.
The problem is formulated as a search for the best combination and sequence of classes from all the classes of the systemthat optimize as much as possible the above two conﬂicting
objectives.
We have executed an extensive empirical evaluation of 6

large open-source software projects with more than 22,000
bug reports in total based on an existing benchmark [26].
The results on the before-ﬁx versions show that our systemoutperforms, on average, three state-of-the-art approaches
not based on search techniques [26, 16, 28]. In particular,
our search-based approach is able to successfully locate thetrue buggy methods within the top 10 recommendations forover 87% of the bug reports.
The primary contributions of this paper can be summarized as follows:• To the best of our knowledge and based on recent surveys [14], the paper proposes the ﬁrst search-based
software engineering approach to address the problem
of ﬁnding relevant code fragments for bug reports. The
approach combines the use of lexical and history basedsimilarity measures to locate and rank relevant codefragments for bug reports while minimizing the number of recommended classes.
• The paper reports the results of an empirical study
with an implementation of our multi-objective approach.
The obtained results provide evidence to support theclaim that our proposal is more eﬃcient, on average,
than existing techniques [16, 26, 28] based on a benchmark of 6 open source systems. We also compared theresults of our multi-objective approach with a monoobjective formulation to make sure that our objectives
are conﬂicting.
The remainder of this paper is as follows: Section 2 isdedicated for the related work. Section 3 describes the proposed approach and the search algorithm. An evaluation of
the approach and its results are explained in Section 4 while
Section 5 further discusses the obtained results. Section 6
describes the threats to validity related to our experiments.
Finally, concluding remarks and future work are provided in
Section 7.

2.

RELATED WORKIn this section, we survey diﬀerent studies related to theareas of bug localization and search-based software engineering.

2.1

Bug Localization

The problem of bug localization can be considered as searching the source of a bug given its description. To address thisproblem, the majority of existing studies is based on the use
Information-Retrieval (IR) techniques through the detectionof textual and semantic similarities between a newly given
report and source code entities [23]. Several IR techniques
have been investigated, namely the Latent Semantic Indexing (LSI) [9], Latent Dirichlet Allocation (LDA) [5] and the
Vector Space Model (VSM) [21]. In addition, hybrid models
extracted from these IRs techniques to tackle the problemof bug localization were proposed [26].
We summarize, in the following, the diﬀerent tools andapproaches proposed in the literature based on the above
IR techniques. BugScout [16] is a topic-based approach using LDA to analyze the bug related information (description, comments, external links, etc.) to detect the source ofa bug and duplicated bug reports. The main limitation of
BugScout is the dependency of the results on the keywords

287

entered by the user. DebugAdvisor’s [2] is a bug investigation system that takes as input a bug report in terms of text
queries then uses them to mine existing ﬁxed bug repository and generate a graph of possible reports. However,DebugAdvisor accuracy depends on the accuracy of the report’s description and its accuracy when describing the bug
and its related code entities.
BugLocator [28] combines several similarity scores fromprevious bug reports for bug localization. It generates a
VSM model to extract suspect source ﬁles for a given bug
report. Then, BugLocator mines previously ﬁxed bug reports along with related ﬁles involved to rank suspect codefragments. The main issue raised in this work is the proneness of the weight density to the noise in the large ﬁles. To
overcome this limitation, [25] added segmentation and stacktrace analysis to improve the performance of the BugLocator
approach. The limitation of this extension is that execution
traces are not necessarily available in bug repositories.
BLUiR [20] has been proposed also to compare a bug
report to the structure of source ﬁles. It decomposes reports into summaries and then uses the structural retrieval
to calculate similarities between these tokenized elements
and source code ones to rank source code ﬁles. Saha etal. [19] extended BLUiR to consider similar reports information, similarly to BugLocator as an additional similarity
score. DHbPd [18] incorporated code change information
for bug localization. The main idea is to consider recently
changed source code elements as potential candidates for
hosting a bug.
Ye et al. [26] has modeled the similarity between bug reports and source code through several characteristics thatare captured through the use of 6 similarity features that
describe the projects domain knowledge. The combinationof these measures is fed to a ranking heuristic called learningto-rank. The ranking model returns the top candidate source
ﬁles to investigate for a given bug report. The main originality of their work is the use of projects API description andauto-generated documentation as one of the features to utilize to reduce the lexical gap between the human description
and the source code.
In [27], Ye et al. extended their previous work by extending their ranking features utilized by learning-to-rankfrom 6 to 19. Besides the existing surface lexical similarity,
API-based lexical similarity, collaborative ﬁltering, code elements naming similarity, ﬁxed bugs frequency, they included
other source code characteristics that can be extracted fromthe projects such as summaries, naming conventions, interclass dependencies etc. Although taking these features into
account has given better results in terms of better ﬁles ranking, such information may not be available in all projects andsometimes it may be outdated and that may deteriorate thelocalizations accuracy.
We propose, in this paper, a more comprehensive approach to address the problem of bugs localization from different perspectives as detailed in the next sections.

2.2

Search-Based Software Engineering

Search-Based Software Engineering (SBSE) uses a computational search approach to solve optimization problems insoftware engineering [13]. Once a software engineering task
is framed as a search problem, by deﬁning it in terms of solution representation, ﬁtness function, and solution change
operators, there is a multitude of search algorithms that can

Source code and API specificationsof the program to be inspected
The description of the bug report(s)The history of the applied changes
in previous releases
A list of previous bug reports

sequence of ranked classes that maximizes the relevance tothe bug report and minimizes the number of recommended
classes. In the following, we describe an overview of NSGAII, the solution representation, a formal formulation of thetwo objectives to optimize and the change operators.

Finding relevant classes for bug
reports using NSGA-II
Objective 1: Maximize the relevanceBest sequence ofof recommended classes
classes to inspect
Objective 2: Minimize the number ofrecommended classes.

3.2

Figure 1: Approach Overview.
be applied to solve that problem.
Many search-based software testing techniques have been
proposed for test cases generation [17], mutation testing [15],regression testing [22] and testability transformation. However, the problem of bugs localization was not addressed before using SBSE. The closest problem addressed using SBSE
techniques is the bugs prioritization problem [8]. A monoobjective genetic algorithm was proposed to ﬁnd the best sequence of bugs resolution that maximizes the relevance andimportance of the bugs to ﬁx while minimizing the cost. The
main limitation of this work is the use of a mono-objective
technique that aggregates two conﬂicting objectives. In thenext section, we describe our formulation of bug localization
as a multi-objective problem.

3.

MULTI-OBJECTIVE FORMULATION

We ﬁrst present an overview of our multi-objective approach to identify and prioritize relevant code fragments(e.g. classes) for bug reports, and then we describe the details of our multi-objective formulation.

3.1

Approach Overview

Our approach aims at exploring a large search space toﬁnd relevant classes, to inspect by developers, given a description of a bug report. The search space is determined
not only by the number of possible class combinations to recommend, but also by the order in which they are proposedto the programmer. In fact, bug reports may require theinspection of more than one class to identify and ﬁx bugs.
A heuristic-based optimization method is proposed basedon two main conﬂicting objectives. The ﬁrst objective is thecorrectness function that includes two sub-functions: 1.a)
maximizing the Lexical similarity between recommended classes
and the description of the bug report (including the API andname of code elements similarity), and 1.b) maximizing thehistory-based function score that includes the number of arecommended classes that have been ﬁxed in the past, recent changes introduced by the developers to these classes
and similarities with previous bug reports. The second objective is to minimize the number of classes to recommend.
It is clear that these two objectives are conﬂicting sincemaximizing the relevance of recommended classes may leads
to a lower precision and thus increases the number of recommended classes. Thus, we consider, in this paper, the taskof localizing bugs as a multi-objective optimization problem
using the non-dominated sorting genetic algorithm (NSGAII) [7]. The proposed algorithm will explore a large search
space of a combinatorial number of combinations of classes
to recommend.
The general structure of our approach is sketched in Figure 1. It takes as input the source code of the program to beinspected, the API speciﬁcations of the classes of the system,
the description of the bug report and a list of previous bug
reports and the history of the applied changes in previous
releases. Our approach generates as output a near-optimal

288

NSGA-IIIn this paper, we adapted one of the widely used multiobjective algorithms called NSGA-II [7]. NSGA-II is a powerful search method stimulated by natural selection that is
inspired by the theory of Darwin. Hence, the basic ideaof NSGA-II is to make a population of candidate solutions
evolve toward the near-optimal solution in order to solve a
multi-objective optimization problem. NSGA-II is designed
to ﬁnd a set of optimal solutions, called non-dominated solutions, also Pareto set. A non-dominated solution is theone which provides a suitable compromise between all objectives without degrading any of them. As described in Algorithm 1, the ﬁrst step in NSGA-II is to create randomly a
population P0 of individuals encoded using a speciﬁc representation (line 1). Then, a child population Q0 is generated
from the population of parents P0 using genetic operatorssuch as crossover and mutation (line 2). Both populations
are merged into an initial population R0 of size N (line 5).
As a consequence, NSGA-II starts by generating an initial
population based on a speciﬁc representation that will be
discussed later, using the exhaustive list of classes from thesystem to inspect given as input as mentioned in the previous section. Thus, this population stands of a set solutions represented as sequences of classes to inspect, which
are randomly selected and ordered, for a speciﬁc bug report
description taken as input.
Algorithm 1 High level pseudo code for NSGA-II
1: Create an initial population P0
2: Create an oﬀspring population Q0
3: t = 0
4: while stopping criteria not reached do
5: Rt = Pt ∪ Qt
6: F = fast-non-dominated-sort(Rt )7: Pt+1 = ∅ and i = 1
8: while | Pt+1 | + | Fi | N do
9:
Apply crowding-distance-assignment(Fi )10:
Pt+1 = Pt+1 ∪ Fi
11:
i=i+1
12: end while
13: Sort(Fi , ≺ n)
14: Pt+1 = Pt+1 ∪ Fi [N − | Pt+1 |]15: Qt+1 = create-new-pop(Pt+1 )16: t = t+1
17: end while
The whole population that contains N individuals (solutions) is sorted using the dominance principle into several
fronts (line 6). The dominance level becomes the basis ofa selection of individual solutions for the next generation.
Fronts are added successively until the parent population
Pt+1 is ﬁlled with N solutions (line 8). When NSGA-II
has to cut oﬀ a front Fi and select a subset of individual
solutions with the same dominance level, it relies on thecrowding distance to make the selection (line 9). This front
Fi to be split, is sorted in descending order (line 13), and theﬁrst (N-|Pt+1|) elements of Fi are chosen (line 14). Thena new population Qt+1 is created using selection, crossoverand mutation (line 15). This process will be repeated untilreaching the last iteration according to stop criteria (line 4).
The following three subsections describe more precisely
our adaption of NSGA-II to the model change detection
problem.

3.3

Solution Approach

3.3.1

Solution representation

To represent a candidate solution (individual), we used avector representation. Each dimension of the vector represents a class to recommend for a speciﬁc bug report. Thus,a solution is deﬁned as a sequence of classes to recommend
for inspection by the developer to locate the bug.
When created, the order of recommended classes corresponds to their positions in the vector. The classes to recommend are dependent since a bug can be located in diﬀerent
classes. In addition, the goal is to recommend a minimum
set of classes while maximizing the correctness objective.

StackRenderer CompositeRenderer

Figure 4: A code fragment from the class StackRenderer.
from the names of variables, classes, methods, parameters,
types, etc. We used the Camel Case Splitter to perform the
Tokenization for preprocessing the identiﬁers [10].
During the tokenization process, we used a standard information retrieval stop words to eliminate irrelevant information such as punctuation, numbers, etc. In addition, thewords are reduced to their stem based on a Porter stemmer. This operation reduces the deviation between related
words such as designing and designer to the same stem design. Then, the cosine similarity measure is used to compare
between the description of a bug report and the source code.
Equation 2 calculates the cosine similarity between two
actors. Each actor is represented as an n dimensional vector, where each dimension corresponds to a vocabulary term.
The cosine of the angle between two vectors is considered as
an indicator of similarity. Using cosine similarity, the conceptual similarity between two actors: c1 and c2 is determined as follows:

TrimUtilFigure 2: Simpliﬁed Example of a Solution Representation.

Bug ID: 378535
Summary: “Close All" and “Close Others" menu
options available when right clicking on tab in
PartStack when no part is closeable.
Description: If I create a PartStack that contains
multiple parts but none of the parts are closeable,
when I right click on any of the tabs I get menu
options for “Close All“ and “Close Others".
Selection of either of the menu options doesn't cause
any tabs to be closed since none of the tabs can beclosed.
Reported: 2012-05-04 14:03

Figure 3: An Eclipse Bug Report Example1 (ID 378535)→→
Sim(c1 , c2 ) = Cos(−
c1 , −c2 ) =nFigure 2 describes a simpliﬁed solution generated to ﬁnd
possible relevant classes for the bug report of Figure 3 thatshows an example of a bug report from the Eclipse project(ID 378535)1 . This bug report describes a defect about incorrect menu options for parts that are not closeable. The
solution consists of a sequence of three classes to inspect
extracted from the Eclipse project.

3.3.2

= 

(1)

The lexical-based similarity (LS) consists of an averageof two functions. The ﬁrst function is based on a cosine
similarity [24] between the description of a bug report andthe source code. We used the whole content of a source codeﬁle (the code and comments). The vocabulary was extracted1n

(wi,1 × wi,2 )(wi,1 )2 ×

n

i=1

∈ [0, 1]

(2)

(wi,2 )2→
where −
c1 = (w1,1 , ..., wn,1 ) is the term vector correspond→
c2 = (w1,2 , ..., wn,2 ) is the term vector
ing to actor c1 and −corresponding to c2 . The weights wi,j is computed using information retrieval based techniques such as the Term Frequency - Inverse Term Frequency (TF-IDF) method. The
ﬁrst lexical simialrity function is then deﬁned as the sum of
the of the cosine similarity scores between a description of a
bug report and the source code of each the suggested classes
divided by the total number of recommended classes.
As described in Figures 4 and 5, the description of the
bug report example includes several similar words with oneof the recommended classes to inspect, the class StackRenderer. Thus, the cosine similarity function applied between
the source code of that class and the description of the bug
report will detect such similarities. However, the only useof this similarity function may not be enough.
In fact, the text of a bug report is, in general, expressedin a natural language however the large part of the content

Fitness functions

LS + HS
2

i=1

i=1

Correctness objective: This objective is deﬁned as the average of two functions: lexical-based similarity (LS) andhistory-based similarity (HS). Thus, we formally deﬁne thisfunction as:
f1 =

−
→
→
c1 . −c2−→→
 c1  ×  −c2 

https://bugs.eclipse.org/bugs/show bug.cgi?id=378535

289

API Specifications:

3.3.3

API Specification of MUIElement:

In a search algorithm, the variation operators play the
key role of moving within the search space with the aim ofdriving the search towards better solutions. We used theprinciple of the Roulette wheel [12] to select individuals formutation and crossover. The probability to select an individual for crossover and mutation is directly proportional to
its relative ﬁtness in the population. In each iteration, we
select half of the population in iteration i. These selected individuals will give birth to another half of the population of
new individuals in iteration i+1 using a crossover operator.
Therefore, two parent individuals are selected, and a few dimensions (recommended classes) picked on each one. The
one point crossover operator allows creating two oﬀspring
P1 and P2 from the two selected parents P1 and P2 . It is deﬁned as follows: a random position, k, is selected. The ﬁrst kclasses of P1 become the ﬁrst k elements of P1 . Similarly, theﬁrst k operations of P2 become the ﬁrst k operations of P2 .
Our crossover operator could create a child that contains
redundant recommended classes. In order to resolve thisproblem, for each obtained child, we verify whether there
are redundant classes or not. In case of redundancy, we replace the redundant classes by randomly chosen ones fromthe system without causing another redundancy.
The mutation operator can be applied to pairs of dimensions of the vector selected randomly. Given a selected solution, the mutation operator ﬁrst randomly selects one or
many pairs of dimensions of the vector. Then, for each selected pair, the dimensions, which correspond to classes, aredeleted or replaced by new classes. We used the same repair
operator, described previously, to eliminate redundancy.

Description: A representation of the model object 'UI Label'. This is a mix in that will be used
for UI Elements that are capable of showing label information in the GUI (e.g. Parts, Menus /Toolbars, Perspectives, ...). The following features are supported: Label, Icon URI, Tooltip ...

Figure 5: API Speciﬁcation of the interface MUIElement.
of a source code is described in a programming language.
Thus, the similarity score between a bug report description
and a source code will be higher in case of an extensive useof comments in the code or if the bug report clearly uses
the names of code elements. To address this challenge, we
propose to use an additional lexical similarity function.
The second lexical function is based on the use of cosine
similarity between the bug report description and the API
speciﬁcation of each method of a recommended buggy class.
Thus, it is deﬁned as the sum of the maximum of the cosine
similarity scores between a description of a bug report andeach of the methods composing the suggested class divided
by the total number of recommended classes.
As described in Figure 5, the class StackRenderer includes
a variable uiElement having as a type MUIElement. Figure
5 shows the API speciﬁcation of the MUIElement interface
that includes diﬀerent terms such as parts and menus that
also exists in the bug report description of Figure 4. Thus,
the lexical similarity between the API speciﬁcation and thedescription of a bug report may also help to better identify
relevant buggy classes.
The second component of the correctness objective is thehistory-based similarity. This measure is an average of threefunctions. The ﬁrst function counts the number of times thata class was ﬁxed to eliminate bugs based on the history of
bug reports. In fact, a class that was ﬁxed several times has
a high probability of being a buggy class and includes new
bugs. Formally, this function, normalized between [0,1] isdeﬁned as:Size(S)N bF ixedBugs(report, ci )
i=1
(3)
H1 =
Size(S) ∗ M ax(N bF ixedBugs(report, c))

4.

H2 =

i=1

1
report.date−last(report,ci )+1Size(S)

4.1

Cbr
Size(S)

Research Questions

In our study, we assess the performance of our approachby ﬁnding out whether it could identify the most relevant
classes to inspect for bug reports. Our study aims at addressing the following research questions outlined below. We
also explain how our experiments are designed to addressthese questions. The main question to answer is to what extent the proposed approach can propose meaningful bug localization solutions based on the description of a bug report.
To this end, we deﬁned the following research questions:(4)

The third function evaluates the consistency between therecommended classes based on previous bug reports. The
classes that are recommended together for similar previous
bug reports have a high probability to include a bug evolving most of them. To this end, this function calculates ﬁrst
the cardinality, Cbr, of the largest intersection set of classes
between the solution S and the sets of classes recommended
for each of previous bug reports. Then, this measure is normalized as follows:
H3 =EVALUATION

In order to evaluate our approach for recommending relevant classes to inspect for bug reports, we conducted a setof experiments based on diﬀerent versions of 6 open source
systems. Each experiment is repeated 30 times, and the obtained results are subsequently statistically analyzed withthe aim to compare our NSGA-II proposal with a variety
of existing approaches not based on heuristic search [26, 16,28] and a mono-objective formulation. In this section, we
present our research questions and thenThe second function checks if a recommended class wasrecently changed or ﬁxed. In fact, a class that was modiﬁed recently has a higher probability of containing a bug.
Thus, the function compares between the date of the bug
report and the last date where the recommended class was
modiﬁed. If a suggested class was modiﬁed on the same dayof the bug report then the value of this function is 1. We
deﬁne this normalized function, normalized in the range of[0, 1] as following:Size(S)Change operators• RQ1. (Eﬃciency) To what extent can the proposed
approach identify relevant classes to localize bugs basedon bug reports description?
• RQ2. (Comparison to search techniques) How does
the proposed multi-objective approach based on NSGAII perform compared to random search and a monoobjective approach?

(5)

290

• RQ3. (Comparison to state-of-the-art) How does ourapproach perform compared to existing bugs localization techniques not based on heuristic search?

• Tomcat implements several Java EE speciﬁcations.
• AspectJ is an aspect-oriented programming (AOP)
extension created for the Java programming language.

To answer RQ1, we validate the proposed multi-objective
technique on six medium to large-size open-source systems,
as detailed in the next section, to evaluate the correctnessof the recommended classes to inspect for a bug report. To
this end, we used the following evaluation metrics:• Birt provides reporting and business intelligence capabilities.
• SWT is a graphical widget toolkit.
• JDT provides a set of tool plug-ins for Eclipse.

• Precision@k denotes the number of correct recommended ﬁles in the top k of recommended ﬁles by thesolution divided by the minimum number of ﬁles to inspect, in the ranked recommendations list, to localize
the bug.

Table 1 shows the diﬀerent statistics of the analyzed systems including the time range of the bug reports, the numberof bug reports, the size, the number of APIs, and the numberof ﬁxed classes per bug report.
The total number of collected bug reports and associatedclasses is more than 22,000 bug reports for the six open
source systems. All these projects are using BugZilla tracking system and GIT as a version control system. To avoid
using a ﬁxed code revision, we associated a before-ﬁxed version of the system to each bug report. Therefore, for eachbug report, the version of the software package just before
the ﬁx was committed was used in our validation.
Based on the collected data, we created two sets: one forthe training data and the other for the test data. The bug
reports for each system were sorted chronologically based on
the time dimension. The sorted bug reports are then split
into 10 folds with equal sizes, where fold1 contains the mostrecent bug reports and the last fold fold10 contains the oldest
ones. In addition, the oldest fold is split into 70% training(history of bug reports) and 30% validation. The approachis trained on foldi+1 and tested on foldi , for all i from 1 to
9. The best recommended solution is then compared withexpected solution of classes that contain the bug.

• Recall@k denotes the number of correct recommended
ﬁles in the top k of recommended ﬁles by the solution
divided by the total number of expected ﬁles to berecommended that contain the bug.
• Accuracy@k measures the percentage of bug reports
for which at least one correct recommendation was provided in the top k ranked classes.
To answer RQ2, we compared, using the above metrics,
the performance of NSGA-II with random search and a monoobjective genetic algorithm aggregating all the objectives
into one objective with equal weight. If Random Searchoutperforms a guided search method thus, we can conclude
that our problem formulation is not adequate. It is important also to determine if our objectives are conﬂicting andoutperforms a mono-objective technique. The comparison
between a multi-objective technique with a mono-objective
one is not straightforward. The ﬁrst one returns a set ofnon-dominated solutions while the second one returns a single optimal solution. To this end, for we choose the nearest
solution to the Knee point [7] (i.e., the vector composed of
the best objective values among the population members) as
a candidate solution to be compared with the single solution
returned by the mono-objective algorithm.
To answer RQ3, we compared our multi-objective approachto diﬀerent existing techniques not based on heuristic search:
1. BugScout [16] identiﬁes relevant classes based on the useof Latent Dirichlet Allocation measure [5]; 2. BugLocator[28] ranks classes using both textual and structural similarity.3. Learning-to-rank (LR) [26] technique ranks classes
using a machine learning technique to learn from the history of previous bug reports. In addition, we compared ourwork with two additional baselines. The ﬁrst one is basedon the only use of the lexical measure (LS) to rank classes
and the second one is based on the only use of the history
measure (HS). These two baselines may justify or not theneed of considering complementary information from boththe lexical and history similarities in our multi-objective formulation.
In the next section, we describe the diﬀerent projects andthe 10-fold cross-validation used in our experiments.

4.2

4.3

Parameters Tuning and statistical tests

Since metaheuristic algorithms are stochastic optimizers,
they can provide diﬀerent results for the same problem instance from one run to another. For this reason, our experimental study is performed based on 30 independent simulation runs for each problem instance and the obtained results
are statistically analyzed by using the Friedman test with
a 95% conﬁdence level (α = 5%) [1]. The Friedman test
is a non-parametric statistical test useful for multiple pairwise comparisons. The latter veriﬁes the null hypothesis
H0 that the obtained results of the diﬀerent algorithms are
samples from continuous distributions with equal medians,
as against the alternative that they are not, H1 . The p-valueof the Friedman test corresponds to the probability of rejecting the null hypothesis H0 while it is true (type I error). A
p-value that is less than or equal to α (≤ 0.05) means that
we accept H1 and we reject H0 . However, a p-value thatis strictly greater than α (> 0.05) means the opposite. In
this way, we could decide whether the superior performanceof NSGA-II to one of each of the other algorithms (or the
opposite) is statistically signiﬁcant or just a random result.
The Friedman test allows verifying whether the results
are statistically diﬀerent or not. However, it does not give
any idea about the diﬀerence in magnitude. To this end,
we used the Vargha and Delaneys A statistics which is a
non-parametric eﬀect size measure. In our context, given
the diﬀerent performance metrics (such as Precision and Recall), the A statistics measures the probability that running
an algorithm B1 (NSGA-II) yields better performance than

Software Projects and Experimental Setting

As described in Table 1, we used a benchmark datasetsfor six open-source systems [26].
• Eclipse UI is the user interface of the Eclipse development framework.

291

Project# Bug reports

Eclipse UI
Birt
JDT
AspectJ
Tomcat
SWT

6495
4178
6274
593
1056
4151

Table 1: Studied Projects# ﬁles in the project
Time
# API
(average per version)
10/2001-01/2014
1314
3454
06/2005-12/2013
957
6841
10/2001-01/2014
1329
8184
03/2002-01/2014
544439
07/2002-01/2014
389
1552
02/2002-01/2014
161
2056

Table 2: Median Precision@k, Recall@k and Accuracy@k on
30 independent runs. The results were statistically signiﬁcant on 51 independent runs using the Friedman test with a
95% conﬁdence level (α < 5%).

running another algorithm B2 (such as GA). If the two algorithms are equivalent, then A = 0.5.
An often-omitted aspect in metaheuristic search is thetuning of algorithm parameters. In fact, parameter setting inﬂuences signiﬁcantly the performance of a search algorithm on a particular problem. For this reason, for eachsearch algorithm and each system, we performed a set ofexperiments using several population sizes: 10, 20, 30, 40
and 50. The stopping criterion was set to 100,000 ﬁtness
evaluations for all search algorithms in order to ensure fairness of comparison. We used a high number of evaluations
as a stopping criterion since our approach requires involves
multiple objectives. Each algorithm was executed 30 times
with each conﬁguration and then the comparison between
the conﬁgurations was performed based on diﬀerent metrics
described previously using the Friedman test. The otherparameters values were ﬁxed by trial and error and are as
follows: (1) crossover probability = 0.4; mutation probability = 0.2 where the probability of gene modiﬁcation is 0.1.

4.4
4.4.1

# ﬁxed ﬁles/classes per bug report(median)
2
1
2
2
1
3

k
NSGA-II
5
10
15
20

89
82
74
68

Bug
Scout
76
71
63
48

Precision@k
Bug
LR LS
Locator
78
81
69
74
76
61
69
72
57
51
58
48

Bug
Scout
59
64
69
74

Recall@k
Bug
LR
Locator
62
64
67
72
72
79
80
83

Bug
Scout
41
62
74
79

Accuracy@k
Bug
LR LS
Locator
44
49
37
69
71
56
78
82
68
82
86
74

k
NSGA-II
5
10
15
20

72
81
87
94

k
NSGA-II

Results
5
10
15
20

Results for RQ1

The results of Table 2 and Figures 6 to 8 conﬁrm the eﬃciency of our multi-objective approach to identify the most
relevant classes for bug reports that include the bugs on the 6
open source systems. Table 2 shows the average precision@k
results of our multi-objective technique on the diﬀerent six
systems, with k ranging from 5 to 20. For example, mostof the recommended classes to inspect in the top 5 (k=5)
are relevant with a precision of 89%. The lowest precision
is around 70% for k=20 which is still could be considered
acceptable since most of the bug reports do not have many
classes to inspect. In terms of recall, Table 2 conﬁrms thatthe majority of the expected classes to recommend are located in the top 20 (k=20) with an average recall score of
94%. An average of more than 72% of classes recommended
in the top5 cover the expected buggy classes.
The average accuracy@k results on the diﬀerent six systems are described in Table 2 showing that an average of
68%, 86%, 94% and 97% are achieved for k = 5, 10, 15
and 20 respectively. These results conﬁrm that if we recommend only 10 classes to programmers, we can make correct
recommendations for 86% of the thousands of collected bug
reports for every system.
Figures 6 to 8 summarize the results of the precision@10,
recall@10 and accuracy@10 for every of the studied systems.
The obtained results clearly show that most of the buggy
classes were recommended correctly by our multi-objective
approach in the top 10 with a minimum precision of 78% for
AspectJ, a minimum recall of 79% for Eclipse and a minimum accuracy of 82% for Eclipse as well. Thus, we noticed
that our technique does not have a bias towards the eval-

68
86
94
97

HS

RS

GA

71
64
58
51

34
29
33
24

71
61
55
53

LS

HS

RS

GA

54
60
65
70

56
62
67
72

27
31
26
24

54
62
69
76

HS

RS

GA

34
59
72
77

29
24
31
33

38
59
79
77

uated system. As described in Figures 6-8, in all systems,
we had almost similar average scores of precision, recall andaccuracy. All these results based on the diﬀerent measures
were statistically signiﬁcant on 30 independent runs using
the Friedman test with a 95% conﬁdence level (α < 5%).
To answer RQ1, the obtained results on the six open
source systems using the diﬀerent evaluation metrics of precision, recall and accuracy clearly validate the hypotheses
that our multi-objective approach can recommend eﬃciently
relevant buggy classes to inspect for each bug report.

4.4.2

Results for RQ2

Concerning RQ2, Table 2 and Figures 6 to 10 conﬁrm that
NSGA-II is better than random search and the three monoobjective formulations (LS, HS and GA) based on the three
metrics of precision, recall and accuracy on all the 6 systems.
Three mono-objective formulations were implemented:
1. with an equal aggregation of both objectives (GA);
2. a mono-objective algorithm with the only objective of
lexical similarity (LS); and3. a mono-objective algorithm with the only objective of
history similarity (HS).
The average accuracy, precision and recall values of random search (RS) on the six systems are lower than 35% as292

described in Table 2. This can be explained by the hugesearch space to explore to identify the best order of classes
to inspect for bugs localization. The performance of thethree mono-objective algorithms was much better than random search but lower than our multi-objective formulation.
The aggregation of both objectives into one objective generates better results on all the six systems than the two otheralgorithms considering each objective separately. Thus, aninteresting observation is the clear complementary between
the history-based similarity function and the lexical-based
measure. In fact, we found that the buggy classes that are
not detected by one of the two algorithms were identiﬁedby the other algorithm. The average precision, recall andaccuracy of each of the two algorithms (LH and HS) was
between 67% and 72% but the aggregation of both objectives into one in our multi-objective formulation improve a
lot the obtained results. In addition, since NSGA-II outperforms the mono-objective GA then it is clear that thetwo objectives of correctness/relevance and the number ofrecommended classes are conﬂicting.
All these results were statistically signiﬁcant on 30 independent runs using the Friedman test with a 95% conﬁdence
level (α < 5%). We have also found the following resultsof the Vargha Delaney A {12} statistic : a) On large andmedium scale systems (Birt, JDT, Eclipse UI and AspectJ )NSGA-II is better than all the other algorithms based on all
the performance metrics with an A eﬀect size higher than
0.93; b) On small scale systems (Tomcat, SWT), NSGA-II
is better than all the other algorithms with a an A eﬀect size
higher than 0.96.
We conclude that there is empirical evidence that ourmulti-objective formulation surpasses the performance of random search and mono-objective approaches thus our formulation is adequate (this answers RQ2).

Figure 6: Average Precision@k of NSGA-II, BugScout, BugLocator, LR, LS, HS, RS and GA on the diﬀerent systems
for 30 independent runs. .

4.4.3

Results for RQ3

Since it is not suﬃcient to compare our approach with only
search-based algorithms, we compared the performance of
NSGA-II with three diﬀerent bugs localization techniques
not based on heuristic search [26, 16, 28]. Table 2 andFigures 6 to 8 present the precision@k, recall@k and accuracy@k results for the 3 implemented methods, with k ranging from 5 to 20. NSGA- II achieves better results, on average, than the other three methods on all six projects. For
example, our approach achieved, on average, Precision@kof 90%, 84%, 73% and 69% are achieved for k= 5, 10, 15
and 20 respectively as described in Table 2. In comparison, BugLocator achieved an average Precision@k of 68%.
BugScout and LR achieved an average Precision@k of 66%
and 72%, respectively. Similar observations are also valid
for the recall@k and accuracy@k.
Based on the results of Figures 6 to 8 Birt and Tomcat
are two projects where LR performs close to the NSGA-II
approach. For many bug reports in Birt, most of the buggy
classes are those that have been frequently ﬁxed in previous
bug reports which explain the relatively high performanceobtained by LR and NSGA-II. Since the bug ﬁxing information is exploited by both the NSGA-II approach and LR, it
is expected that they obtain the best performance results.
To answer RQ3, the obtained results on the six open
source system using the diﬀerent evaluation metrics of precision, recall and accuracy clearly validate the hypotheses
that our multi-objective approach outperforms several bugs

Figure 7: Average Recall@k of NSGA-II, BugScout, BugLocator, LR, LS, HS, RS and GA on the diﬀerent systems for
30 independent runs.

Figure 8: Average Accuracy@k of NSGA-II, BugScout, BugLocator, LR, LS, HS, RS and GA on the diﬀerent systems
for 30 independent runs.

293

6.

We explore, in this section, the factors that can bias ourempirical study. These factors can be classiﬁed in three categories: construct internal and external validity. Constructvalidity concerns the relation between the theory and the observation. Internal validity concerns possible bias with theresults obtained by our proposal. Finally, external validity
is related to the generalization of observed results outside
the sample instances used in the experiment.
In our experiments, construct validity threats are related
to the absence of similar work that uses search-based techniques for bug’s localization. For that reason, we compared
our proposal with diﬀerent mono-objective formulations tocheck the need for a multi-objective approach. A constructthreat can also be related to the corpus of manually localized bugs for every bug report. A limitation related to ourexperiments is the diﬃculty to set the thresholds for some ofthe parameters of Bug Locator. In fact, we used the default
thresholds used by the authors that can have an impact on
the quality of the generated results.
We take into consideration the internal threats to validity in the use of stochastic algorithms since our experimental
study is performed based on 30 independent simulation runs
for each problem instance, and the obtained results are statistically analyzed by using the statistical test with a 95%
conﬁdence level (α = 5%). The parameter tuning of thediﬀerent optimization algorithms used in our experiments
creates another internal threat that we need to evaluate in
our future work by additional experiments to evaluate theimpact of the parameters on the quality of the results.
External validity refers to the generalization of our ﬁndings. In this study, we performed our experiments on six
diﬀerent widely-used open-source systems belonging to different domains and with diﬀerent sizes. However, we cannot
assert that our results can be generalized to other applications, other programming languages, and to other practitioners.

Figure 9: Impact of the data training size (folds) on thethree metrics based on the JDT project.

Figure 10: Average execution time (in minutes) of NSGAII, on the diﬀerent systems for 30 independent runs on thediﬀerent systems.
localization techniques not based on heuristic search.

5.

THREATS TO VALIDITYDISCUSSIONS

Impact of Data Size. To evaluate the impact of increasing the size of the data used (history of previous bug
reports and changes), we executed a scenario on the JDTproject in which we increased the size of the dataset incrementally fold by fold until we include all the 9 folds inthe dataset. It is clear from Figure 9 that for all the three
metrics of Precision@k, Recall@k and Accuracy@k that increasing the size of the previous bug reports do not improve
all the three metrics. This can be explained by the fact thatrecent bug reports and history of changes are the most important part of the data. The obtained results conﬁrm alsothat our multi-objective approach did not require a large setof data to generate good results in terms of ﬁnding possible
buggy classes for bug reports.
Execution time. We executed our multi-objective algorithm on a desktop computer with CPU Intel(R) Core(TM)i7 3.2 GHz and 20G RAM. Figure 10 presents the execution
time performance of our approach. The average execution
time on the diﬀerent systems was around 18 minutes. The
highest execution time was observed on the JDT systemwith 23 minutes and the lowest one was around 11 minutes
for SWT. We believe that the execution is reasonable sincebugs localization is not a real-time problem. We also foundthat the execution time is related to the number of ﬁles toparse and the history of bug reports.

7.

CONCLUSION AND FUTURE WORK

We propose, in this paper, an automated approach to localize and rank potential relevant classes for bug reports.
Our approach ﬁnds a trade-oﬀ between minimizing the number of recommended classes and maximizing the correctnessof the proposed solution using a multi-objective optimization algorithm. The correctness of the recommended classes
is estimated based on the use of the history of changes andbug-ﬁxing, and the lexical similarity between the bug report
description and the API documentation. We have executed
extensive empirical evaluations on 6 large open-source software projects with more than 22,000 bug reports in total
based on an existing benchmark. The results on the beforeﬁx versions show that our system outperforms, on average,
three state-of-the-art approaches not based on search techniques [16, 26, 28]. In particular, our search-based approachis able to successfully locate the true buggy methods within
the top 10 recommendations for over 87% of the bug reports.
As part of our future work, we plan to evaluate our multiobjective approach on further projects in other diﬀerent programming languages. In addition, we will extend our work
to address the problem of the software bugs management
and prioritization using multi-objective search techniques.

294

8.

REFERENCES

software engineering. Empirical Software Engineering,18(3):594–623, 2013.
[16] A. T. Nguyen, T. T. Nguyen, J. Al-Kofahi, H. V.
Nguyen, and T. N. Nguyen. A topic-based approachfor narrowing the search space of buggy ﬁles from a
bug report. In IEEE/ACM International Conference
on Automated Software Engineering (ASE), pages
263–272, 2011.
[17] A. Núñez, M. G. Merayo, R. M. Hierons, andM. Núñez. Using genetic algorithms to generate test
sequences for complex timed systems. Soft Computing,17(2):301–315, 2013.
[18] S. Rao and A. Kak. Retrieval from software libraries
for bug localization: a comparative study of genericand composite text models. In 8th Working
Conference on Mining Software Repositories, pages
43–52, 2011.
[19] R. K. Saha, J. Lawall, S. Khurshid, and D. E. Perry.
On the eﬀectiveness of information retrieval based bug
localization for c programs. In ICSME, pages 161–170,
2014.
[20] R. K. Saha, M. Lease, S. Khurshid, and D. E. Perry.
Improving bug localization using structured
information retrieval. In IEEE/ACM International
Conference on Automated Software Engineering(ASE), pages 345–355, 2013.
[21] G. Salton, A. Wong, and C.-S. Yang. A vector spacemodel for automatic indexing. Communications of theACM, 18(11):613–620, 1975.
[22] J. Shelburg, M. Kessentini, and D. R. Tauritz.
Regression testing for model transformations: A
multi-objective approach. In International Symposium
on Search Based Software Engineering, pages 209–223.
Springer, 2013.
[23] C. Sun, D. Lo, X. Wang, J. Jiang, and S.-C. Khoo. A
discriminative model approach for accurate duplicate
bug report retrieval. In 32nd ACM/IEEEInternational Conference on Software
Engineering-Volume 1, pages 45–54. ACM, 2010.
[24] P.-N. Tan et al. Introduction to data mining. Pearson
Education India, 2006.
[25] C.-P. Wong, Y. Xiong, H. Zhang, D. Hao, L. Zhang,and H. Mei. Boosting bug-report-oriented fault
localization with segmentation and stack-trace
analysis. In ICSME, pages 181–190. Citeseer, 2014.
[26] X. Ye, R. Bunescu, and C. Liu. Learning to rank
relevant ﬁles for bug reports using domain knowledge.
In 22nd ACM SIGSOFT International Symposium on
Foundations of Software Engineering, pages 689–699.
ACM, 2014.
[27] X. Ye, R. Bunescu, and C. Liu. Mapping bug reports
to relevant ﬁles: A ranking model, a ﬁne-grained
benchmark, and feature evaluation. IEEE
Transactions on Software Engineering, 42(4):379–402,
2016.
[28] J. Zhou, H. Zhang, and D. Lo. Where should the bugs
be ﬁxed? more accurate information retrieval-based
bug localization based on bug reports. In 34th
International Conference on Software Engineering(ICSE), pages 14–24. IEEE, 2012.

[1] A. Arcuri and G. Fraser. Parameter tuning or default
values? an empirical investigation in search-based[2] B. Ashok, J. Joy, H. Liang, S. K. Rajamani,
G. Srinivasa, and V. Vangala. Debugadvisor: arecommender system for debugging. In 7th joint
meeting of the European software engineering
conference and the ACM SIGSOFT symposium on
The foundations of software engineering, pages
373–382. ACM, 2009.
[3] N. Bettenburg, S. Just, A. Schröter, C. Weiss,
R. Premraj, and T. Zimmermann. What makes a good
bug report? In 16th ACM SIGSOFT International
Symposium on Foundations of software engineering,
pages 308–318. ACM, 2008.
[4] N. Bettenburg, R. Premraj, T. Zimmermann, andS. Kim. Duplicate bug reports considered harmfulâĂe
really? In International Conference on Software
maintenance (ICSM), pages 337–345, 2008.
[5] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent
dirichlet allocation. Journal of machine Learning
research, 3(Jan):993–1022, 2003.
[6] B. Bruegge and A. H. Dutoit. Object-Oriented
Software Engineering Using UML, Patterns andJava-(Required). Prentice Hall, 2004.
[7] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A
fast and elitist multiobjective genetic algorithm:
Nsga-ii. IEEE transactions on evolutionary
computation, 6(2):182–197, 2002.
[8] D. Dreyton, A. A. Araújo, A. Dantas, Á. Freitas, and
J. Souza. Search-based bug report prioritization for
kate editor bugs repository. In International
Symposium on Search Based Software Engineering,
pages 295–300. Springer, 2015.
[9] S. T. Dumais. Latent semantic analysis. Annual review
of information science and technology, 38(1):188–230,
2004.
[10] E. Enslen, E. Hill, L. Pollock, and K. Vijay-Shanker.
Mining source code to automatically split identiﬁers
for software analysis. In International Working
Conference on Mining Software Repositories, pages
71–80. IEEE, 2009.
[11] M. Fischer, M. Pinzger, and H. Gall. Analyzing andrelating bug report data for feature tracking. In
WCRE, volume 3, page 90, 2003.
[12] D. E. Goldberg and K. Deb. A comparative analysis of
selection schemes used in genetic algorithms.
Foundations of genetic algorithms, 1:69–93, 1991.
[13] M. Harman and B. F. Jones. Search-based software
engineering. Information and software Technology,
43(14):833–839, 2001.
[14] M. Harman, S. A. Mansouri, and Y. Zhang.
Search-based software engineering: Trends, techniques
and applications. ACM Computing Surveys (CSUR),
45(1):11, 2012.
[15] C. Henard, M. Papadakis, and Y. Le Traon.
Mutation-based generation of software product line
test conﬁgurations. In International Symposium on
Search Based Software Engineering, pages 92–106.
Springer, 2014.

295