\section{Conclusion}
\label{sec:conc}
While spectrum based bug localization is an extensively studied research area, studying buggy code in association with code naturalness (thus unnaturalness) is relatively new. In this work, we introduced the notion of code entropy as captured by statistical language model in \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace to make the overall bug localization more robust, and proposed an effective way of integrating entropy with \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace suspicious scores. We implemented our concept in a prototype called EnSpec\xspace. Our experimental results with EnSpec\xspace show that code entropy is positively correlated with the buggy lines executed by the failing test cases. Our results also demonstrate that EnSpec\xspace, when configured to use both  entropy and \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace, outperforms the configuration that uses only various \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace as features. EnSpec\xspace can also be leveraged for detecting bugs in cross-project setting for relatively new projects, where project bug database and evolutionary history is not strong enough.

Our future direction includes  leveraging EnSpec\xspace to repair buggy program line more effectively, and improving EnSpec\xspace further by incorporating language model which captures not only the syntactic structure but also code semantic structure.

\section{Introduction}
\label{sec:intro}

Localizing bugs is an important, time consuming, and expensive process, especially for a system at-scale. Automatic bug localization can play an important role in saving developers' time in debugging, and thus, may help developers fixing more bugs in a limited time. Using various statistical and program analysis approaches, these bug localization techniques automatically identify suspicious code elements that are highly likely to contain bugs. Developers then manually examine these suspicious code to pinpoint the bugs.

Existing bug localization techniques can be broadly classified into two categories: i) test coverage-based dynamic approaches~\cite{jones2005tarantula,abreu2009practical,zeller2002simplifying,cleve2005locating,liblit2005scalable,liu2005sober}, and ii) pattern-based~\cite{copeland2005pmd,findbugs, Engler:2001:SOSP,Chelf:2002:Paste} or information retrieval-based (IR) static approaches~\cite{rao2011retrieval,zhou2012should,saha2013improving,ye2014learning}. Dynamic approaches first run all the test cases, and then analyze the program statements covered by passing\xspace and failing\xspace test cases. For example, spectrum based bug localization (\hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace), a popular dynamic bug localization technique, prioritizes the program elements for debugging that are executed more by failing\xspace test cases than by passing\xspace test cases. In contrast, static approaches do not run any test cases. Rather, it searches for some previously known buggy patterns in source code or looks for buggy files based on bug reports.

Both of these bug localization approaches have their own set of advantages and disadvantages. For instance, static methods are often imprecise or inaccurate. On the other hand, the accuracy of dynamic approaches is highly dependent on the quality (code coverage, \hbox{\emph{etc.}}\xspace) of the test suite. In real world projects, most of the test suite may not have enough code coverage to locate bugs efficiently. Therefore, in many cases, developers do not get the full benefit of bug localization techniques~\cite{johnson2013don} and have to significantly rely on manual effort and prior experiences.

Besides static and dynamic properties of a program, it has also been observed that how developers write code is also important for code quality~\cite{hellendoorn2015will}.  Real-world software that are developed by regular programmers tend to be highly repetitive and predictable~\cite{gabel2010study}. Hindle \hbox{\emph{et al.}}\xspace was the first to show that such repetitiveness can be successfully captured by a statistical language model~\cite{hindle2012naturalness}. They called this property as {\it naturalness} of code and measured it by standard information theory metric {\it entropy}. The less entropy a code snippet exhibits, the more the code is natural. Inspired by this phenomena, Ray \hbox{\emph{et al.}}\xspace~\cite{ray2016naturalness} investigated if there is any correlation between buggy code and entropy. They observed that buggy codes are in general less natural, \hbox{\emph{i.e.}}\xspace they have higher entropy than non-buggy code.

In this paper, our key intuition is that, since the high entropic code tends to be buggy~\cite{ray2016naturalness,campbell2014syntax,wang2016bugram}, code entropy can be an effective orthogonal source of information to \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace to improve the overall accuracy of bug localization. This notion seems to be plausible since from a set of suspicious code, as reported by a  standard \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace technique, experienced programmers often intuitively identify the actual bugs because buggy code elements are usually a bit unnatural than rest of the corpus. If entropy can improve \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace, it would be particularly useful when a test suite is not strong enough to discriminate buggy lines or when the suspicious scores of many lines are the same. Furthermore, to realize this hybrid approach, we only need source code (no other external meta-source), which is always available to the developers.

To this end, we introduce EnSpec\xspace, that automatically calculates the entropy for each program line and combines with a state-of-the-art \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace using a machine learning technique to return a ranked list of suspicious lines for investigation.
Here, we studied bug localization at line granularity to ensure maximum benefit to the developers, although locating bugs in method and file-granularity is also possible. We performed an extensive evaluation of EnSpec\xspace on two popular publicly available bug-dataset: Defects4J\xspace~\cite{just2014defects4j} and ManyBugs\xspace~\cite{le2015manybugs} written in Java and C respectively. In total, we studied more than 500 bugs (3,715 buggy lines) bugs, around 4M LOC from 10 projects.

Overall, our findings corroborate our hypothesis that entropy can indeed improve bug localization capability of spectrum based bug localization technique. We further evaluate EnSpec\xspace for both C and Java projects showing that the tool is not programming language dependent. In particular, our results show that:

\begin{itemize}
\item Entropy score, as captured by statistical language models, can significantly improve bug localization capability of standard \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace technique.

\item Entropy score also boosts \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace in cross-project bug localization settings.
\end{itemize}

In summary, we make the following contributions in this paper:

\begin{enumerate}
\item We introduce the notion of entropy in spectrum based bug localization.

\item We present EnSpec\xspace that effectively combine entropy score with the suspicious score of spectrum based bug localization using a machine learning technique.

\item We provide an extensive evaluation of EnSpec\xspace on two publicly available benchmarks that demonstrates the effectiveness of our approach.
\end{enumerate}

\section*{Acknowledgment}

\balance
\bibliographystyle{abbrv}

\section{Study Method
\label{sec:method}

In this section, we describe the dataset we studied and the analysis methods we used to answer our research
questions.

\subsection{Study Subject}
\label{subsec:study_subject}

We used two publicly available bug dataset: Defects4J\xspace~\cite{just2014defects4j} and
ManyBugs\xspace~\cite{le2015manybugs} (see Table~\ref{tab:ssubj}).  Defects4J\xspace dataset contains $5$ open source projects with $321$K lines of code, $357$ reproducible bugs, and $20$K total number of tests. All the Defects4J\xspace projects are written in Java. We also studied $5$ projects from ManyBugs\xspace benchmark dataset~\cite{le2015manybugs}. These are medium to large open source C projects, with total $4459$K lines of code, $160$ reproducible bugs, and $9262$ total test cases. In both datasets, each bug is associated with a buggy and its corresponding fix program versions. There are some failing test cases that reproduce the bugs in the buggy versions, while after the fixes all the test cases pass. The dataset also provides APIs for instrumentation and recording program execution traces.

\input{tables/dataset}

\subsection{Data Collection}
\label{subsec:dc}

Here we describe how we identified the buggy lines in a buggy program version.

{\em Annotating buggy program statements.} We compared each buggy program version with its corresponding fixed version; the lines that are deleted or modified in the buggy version are annotated as buggy program statements. To
get the differences between two program versions, we used Defects4J\xspace APIs for Defects4J\xspace dataset.~\sk{How did you get differences of ManyBugs\xspace dataset?}

We notice that some bugs in Defects4J\xspace dataset\sk{what about ManyBugs\xspace?} are caused due to the error of omission\textemdash tests fail due to missing features/functionalities in the buggy version. Fixing these bugs do not require deleting or modifying program statements in the buggy version, but adding new lines in the fixed version. In such cases, we cannot trivially annotate any of the existing lines in the buggy version as `buggy.' We filter out such bugs from further consideration, as our goal in this work to locate existing buggy lines, as opposed to detecting error of omission.~\ripon{Ripon, I do not think we need to cite example, as it is trivial. What do you think?} Table~\ref{tab:ssubj} shows the total number of buggy lines per each Defects4J\xspace project.

Obviously, this is a very small number to work on. So we searched on those project evolution history for more bugs. We adopted the similar strategy described in \textit{Ray et al.}\cite{ray2016naturalness} First, we searched project repository for bug fix commit messages based on special keywords in commit messages. As described in Mockus ~\hbox{\emph{et al.}}\xspace~\cite{mockus2000identifying}, we searched commit messages containing error related keywords such as `error', `bug', `fix', `issue', `mistake', `flaw', `defect' etc. Lines changed or deleted on those commits are marked as buggy. Then the commits those had introduced these buggy lines are located. then using `git blame' with `--reverse' option, those lines are located in the nearest snapshot of the originating commit. ~\sk{Elaborate this.} From project evolution history, we found other bugs to train our model on. And total number of buggy lines found are also shown in table \ref{tbl:buggy_lines}.

Another approach is very popular in literature, which injects faults in the software system for testing \cite{gunneflo1989evaluation,segall1995fiat}. But in our model, we heavily rely on the naturalness of the code. And, injected code will violate the hypotheses of code being natural. So, we did not adopt that approach.

\subsubsection{Data Filtering}
\label{subsec:data_filtering}
We are dealing with fault localization. We know there are faults because, some of the test cases failed. There are some lines in a project which is not even been touched by any of the failing test cases. So we exclude those lines from consideration.
Obviously, some of the buggy lines from project evolution are excluded. The reason for that is, although we have sufficient failing test cases for all of the bugs given by defects4j, we do not have sufficient test cases to identify all the buggy lines identified from the project evolution. ~\sk{Is it also done for manybugs dataset.}
Number of buggy lines after this filtering is shown in table \ref{tbl:after_filtering}
\begin{table}[h]
\centering
\begin{tabular}{c|c|c}
Project name		&	\#Total Lines &  \#Buggy Lines\\
\hline
\hline
jfree-\textbf{Chart}		&	2311 & 30\\
Commons-\textbf{Lang}		&	29525 & 249\\
\textbf{Closure}-compiler	&	4504 & 134\\
Commons-\textbf{Math}		& 	2793 & 577\\
Joda-\textbf{Time}			&	588 & 46\\
\hline
Total		&	39721 & 1035\\
\end{tabular}
\caption{Number of lines to be considered and number of buggy lines}
\label{tbl:after_filtering}
\end{table}

\subsection{Methodology}
\label{subsec:method}

\subsubsection{Program Spectra Generation}
\label{subsec:program_spectra}

First, we extracted the Test Classes and Test methods from the Project Source codes. Then, we run our test cases and recorded the execution trace of different passing and failing test cases. We also recorded the passing status of the corresponding test case.

From there we calculated line 4 values$(e_p, e_f, n_p, n_f)$ described in Section \ref{sec:intro}. With these 4 values, we generated 25 ranking matrices in the state of the art described in \textit{Xuan et al.} \cite{xuan2014learning}. We used these 25 ranking metrics as our considered features. These values are referred to as Spectrum based features in the context of this report.

\subsubsection{Entropy Generation}
\label{sebsec:entropy_gen}
For generating entropy we adopted the \textit{\$-gram} model proposed by \textit{Tu et al.}\cite{tu2014localness}. For every line in source code we, calculated $3$ entropy values. Those are:
\begin{itemize}
\item \textbf{Forward Entropy $(E_f)$}: This entropy is calculated by parsing the file from begin to end, \textit{i.e.} considering the token sequence as it is in the source file.
\item \textbf{Backward Entropy $(E_b)$}: This entropy is calculated by parsing the file in reverse order, \textit{i.e.} considering the token sequence from end to the begin of file.
\item \textbf{Average Entropy $(E_a)$}: This entropy value is calculated as the average of $E_f$ and $E_b$.
\end{itemize}
We used these 3 values as our feature for algorithm. In this report, we refer to this values as \textit{Entropy based features}.

Inspired by the approach described at Li ~\hbox{\emph{et al.}}\xspace~\cite{li2007mcrank}, we annotated all lines in our train dataset with a relevance score of being buggy. Intuitively, this score should by higher for the actual buggy lines. To maintain clarity, we maintained one relevance score for all the buggy lines and one score for non-buggy lines. Let $R_b$ be the relevance score of buggy lines, and $R_g$ be the relevance score for good lines.
We chose $R_b$ and $R_g$ such that $R_b > R_g$.
Impact of assigning different scores for buggy and/or non-buggy lines is beyond the scope of this research.

We represent each line $l_i$ in the training code corpus as a tuple, $<Sp_i,En_i,R_i>$, where $SP_i$ are the spectrum based suspiciousness scores, $EN_i$ are the Entropy scores, and $R_i \in \{R_b, R_g\}$ is the relavenace score.Themn, we pass the whole corpus to a learning machine, which learns the probability distribution $P(R_i|Sp_i,En_i)$ of the relevance scores given the feature values. While the model is in test phase, for each line $L_i$ in test corpus, we compute supiciousness score based on equation ~\ref{eqn:proba_suspiciousness_score}
\begin{equation}
\label{eqn:proba_suspiciousness_score}
\begin{split}
Susp_{L_i} = f(R_b) &* P(R_b|Sp_{L_i},En_{L_i})\\
&+ f(R_g) * P(R_b|Sp_{L_i},En_{L_i})
\end{split}
\end{equation}
Here, $f(R_i)$ is monotonically increasing function. To keep things simple, we used identity function \textit{i.e.} $f(R_b) = R_b$ and $f(R_g) = R_g$, which is of course monotonically increasing function. Choosing this identity function will transform equation ~\ref{eqn:proba_suspiciousness_score} into
\begin{equation}
\label{eqn:expected_value_suspiciousness}
\begin{split}
Susp_{L_i} &= \sum_{R_i \in \{R_b, R_g\}}{R_i * P(R_i|Sp_{L_i},En_{L_i})} \\
&= \mathbb{E}[R_i|Sp_{L_i}, En_{L_i}]
\end{split}
\end{equation}
This is the expected relevance score for a line being buggy. We evaluated our approach based on this score.
\subsection{Evaluation Metric}
\label{sunsec:evaluation_metric}
Todo: Add description of evaluation metric.

\subsection{Random Forest Algorithm}
\label{subsec:randomforest}
Random Forest(RF) is an ensemble learning technique developed by Breiman(2001)\cite{breiman2001random} based on a combination of a large set of decision trees. Each tree is trained by selecting a random set of variables and a random sample from the training dataset (\textit{i.e.}, the different spectrum scores and/or entropies by \$-gram model). In addition to learning the discrimination function for classification task, RF also learns class conditional probability distribution of train dataset. Additionally, RF algorithm learns the importances for different features for discrimination. In this work, we leveraged the  feature importance(i.e. importances of different \textit{suspiciousness} scores and \textit{entropy} based features)  and class conditional probability distribution learned by RF algorithms. As described by Provost \hbox{\emph{et al.}}\xspace~\cite{provost2003tree}, we used the class conditional probability estimation of a test program line as the suspiciousness score.

\subsection{Training}
\label{subsec:training}
Having the pre-processing described in section \ref{subsec:program_spectra},\ref{subsec:bug_annot},and\ref{subsec:data_filtering} done, we train our model using simplified Random Forest Algorithm, where we learn the relative importances of the features to classify the data into buggy and non-buggy version, and also we learned the class conditional probability distribution of the training data.
\section{Proposed Approach
\label{sec:method}

\begin{figure*}[!htpb]
\centering
\includegraphics[width=\textwidth]{schema.png}
\caption{\textbf{\small EnSpec\xspace Workflow}}
\label{fig:schema}
\end{figure*}
\vspace{15pt}

In this section, we describe our tool, EnSpec\xspace. An overview of our approach is shown in Figure~\ref{fig:schema}. The goal of EnSpec\xspace is to localize bugs using a hybrid bug localization technique: a combination of dynamic spectrum based bug localization (\hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace) and static natural language model based defect prediction (LM\xspace).  EnSpec\xspace takes two sets of code corpus as input\textemdash training and testing set. Next, EnSpec\xspace works in following four steps:
{\em Step-1.} EnSpec\xspace collects entropy score per code element based on a language model for each input project.
{\em Step-2.} For each project version in the training and test corpus,  EnSpec\xspace records test coverage and collects various \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace based suspiciousness scores per code element.
{\em Step-3.}  In this step, EnSpec\xspace learns from the training data, how the suspiciousness scores and entropy collected in above two steps relate to buggy/non-buggy classes and learns feature weight. In Section~\ref{subsec:dc}, we describe the data collection phase in more detail: how we annotate each code element as buggy/non-buggy.
{\em Step-4.} Based on the learned feature-weight, EnSpec\xspace assigns a suspiciousness score of each code element in the test corpus. The suspiciousness score depicts the probability of a code element to be buggy.
Finally, the output of EnSpec\xspace is a ranked list of code elements based on their decreasing suspiciousness score.

In theory, EnSpec\xspace should work on code elements at any granularity\textemdash line, method, file, etc. In this paper, we use EnSpec\xspace to localize bugs at a line granularity. In the following section, we describe these steps in details.

\subsection*{Step-1:~Generating entropy using LM\xspace}

For generating entropy per program line, we adopted the \$gram\xspace language model proposed by Tu \hbox{\emph{et al.}}\xspace~\cite{tu2014localness}. For every line in source code we calculated following three entropy values:

1.~{Forward Entropy $(E_f)$}: Entropy value of a token is calculated based on the probability of seeing the token given its prefix token sequences.  We calculate this entropy by parsing the file from beginning to end, \hbox{\emph{i.e.}}\xspace considering the token sequences as it is in the source file.

2.~{Backward Entropy $(E_b)$}:  Entropy value of a token is calculated based on the probability of seeing the token given its suffix token sequences. We calculate this entropy by parsing the file in reverse order, \hbox{\emph{i.e.}}\xspace from end to beginning.

3.~{Average Entropy $(E_a)$}: This entropy value is calculated as the average of $E_f$ and $E_b$.

We use these three values as our LM\xspace based features. We further normalized these values based on their AST type, as shown in Equation~\ref{eqZscore}. We refer these three normalized entropy values as \textit{entropy related features} in the rest of the paper.

\input{rankings}

\subsection*{Step-2:~Extracting suspiciousness score using \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace techniques.}
For all the input project versions, we first instrument the source code to record program execution traces, or coverage data. Both Defects4J\xspace and ManyBugs\xspace dataset provide APIs for collecting such coverage data. Then, to collect the execution traces, we extract the test classes and test methods from the project source code and run the test cases. We record the execution traces for each test case with its passing/failing status. These test spectra characterize the program's behavior across executions by summarizing how frequently each source code line was executed for passing and
failing tests. Now for each line we  calculate 4 values $(e_p, e_f, n_p, n_f)$, as described in Section~\ref{sec:prelim}. Next, using these 4 values, we generate 25 suspiciousness scores, as  described by Xuan \hbox{\emph{et al.}}\xspace~\cite{xuan2014learning}. We use these 25 scores(see Table~\ref{tbl:rank_metrics}) as our \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace features.

The next two steps implement the training and testing phase of a classifier based on buggy and non-buggy program lines. We adapted Li~\hbox{\emph{et al.}}\xspace's learning to rank algorithm for this purpose~\cite{li2007mcrank}.

\subsection*{Step-3:~Training Phase}
 Given a set of buggy and non-buggy lines, EnSpec\xspace learns the relation  between \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace and entropy related features on the bugginess of program lines.

First, all lines in the training dataset were annotated with a relevance score of bugginess: $R_b$ for each buggy line, and $R_g$ for each non-buggy line, where $R_b > R_g$.  Thus, each line $l$ in the training code corpus is represented as a tuple, $\langle Sp_l, En_l, R_l \rangle$, where $Sp_l$ is a set of \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace features, $En_l$ is a set of entropy related features, and $R_l \in \{R_b, R_g\}$ is the bug-relevance score.
Then, we pass the whole corpus to a  machine learner, which learns the probability distribution $P(R_l|Sp_l,En_l)$ of the relevance scores given the feature values.

\subsection*{Step-4:~Testing Phase}

In testing phase, for each line $l$ in the test corpus, we compute a suspiciousness score ($susp$) based on equation ~\ref{eqn:proba_suspiciousness_score}.

\begin{equation}
\label{eqn:proba_suspiciousness_score}
\begin{split}
susp_{l} = f(R_b) &* P(R_b|Sp_{l},En_{l})\\
&+ f(R_g) * P(R_b|Sp_{l},En_{l})
\end{split}
\end{equation}

Here, $f(R_b)$ and $f(R_g)$ are monotonically increasing functions. To keep things simple, we used identity function, \hbox{\emph{i.e.}}\xspace, $f(R_b) = R_b$ and $f(R_g) = R_g$, which is monotonic as well. This transforms equation ~\ref{eqn:proba_suspiciousness_score} into:

\begin{equation}
\label{eqn:expected_value_suspiciousness}
\begin{split}
susp_{l} &= \sum_{R_l \in \{R_b, R_g\}}{R_l * P(R_l|Sp_{l},En_{l})} \\
&= \mathbb{E}[R_l|Sp_{l}, En_{l}]
\end{split}
\end{equation}

We use ensemble~\cite{dietterich2002ensemble} of $M$ different models trained on randomly sampled subset of original dataset. Each model $M_k$ computes a suspiciousness score $susp_{l}^{k}$,  based on the expected relevance score of equation~\ref{eqn:expected_value_suspiciousness}. Our final hybrid suspiciousness score is calculated by equation~\ref{eqn:ensemble}:

\begin{equation}
\label{eqn:ensemble}
HySusp_{l} = \frac{1}{M}\sum_{k=1}^{M}{susp_{l}^k}
\end{equation}

EnSpec\xspace outputs a ranked list of source code lines based on the decreasing order of hybrid suspiciousness score (HySusp), line with highest suspiciousness tops the list.

\section{Experimental Setup}
\label{sec:experiment}

In this section, we describe how we setup our experiment to evaluate EnSpec\xspace. In particular, we describe the subject systems, how we collect data, evaluation metric, and research questions to evaluate EnSpec\xspace.

\input{dataset}

\subsection{Study Subject}
\label{subsec:study_subject}

We used two publicly available bug dataset: Defects4J\xspace~\cite{just2014defects4j} and
ManyBugs\xspace~\cite{le2015manybugs} (see Table~\ref{tab:ssubj}).  Defects4J\xspace dataset contains $5$ open source projects with $321$K lines of code, $357$ reproducible bugs, and $20$K total number of tests. All the Defects4J\xspace projects are written in Java. We also studied $5$ projects from ManyBugs\xspace benchmark dataset~\cite{le2015manybugs}. These are medium to large open source C projects, with total $4459$K lines of code, $160$ reproducible bugs, and $9262$ total test cases. In both datasets, each bug is associated with a buggy and its corresponding fix program versions. There are some failing test cases that reproduce the bugs in the buggy versions, while after the fixes all the test cases pass. The dataset also provides APIs for instrumentation and recording program execution traces.

\subsection{Data Collection}
\label{subsec:dc}

Here we describe how we identified the buggy program statements. We followed two techniques as described below:

\rom{1}.~\textit{Buggy lines retrieved from original dataset.} We compared each buggy program version with its corresponding fixed version; the lines that are deleted or modified in the buggy version are annotated as buggy program statements. To
get the differences between two program versions, we used Defects4J\xspace APIs for Defects4J\xspace dataset. For every snapshot, ManyBugs\xspace dataset provides {\tt diff} of different files changed during the fix revision. We directly used those {\tt diff} files.

We notice that some bugs are caused due to the error of omission\textemdash tests fail due to missing features/functionalities in the buggy version. Fixing these bugs do not require deleting or modifying program statements in the buggy version, but adding new lines in the fixed version. In such cases, we cannot trivially annotate any of the existing lines in the buggy version as `buggy.' We filter out such bugs from further consideration, as our goal in this work to locate existing buggy lines, as opposed to detecting error of omission. Table~\ref{tab:ssubj} shows the total number of buggy lines per project in the original dataset.

\begin{figure}[!htpb]
  \centering
  \includegraphics[width=0.9\columnwidth]{evobug}
  \caption{{\small{\bf Evolutionary bug data retrieval: vertical dashed lines correspond to buggy project versions under investigation, each triangle represents project commit (c0$\ldots$c3). For every bug-fix commit (\hbox{\emph{e.g.,}}\xspace c2), as identified by keyword search,  we first git-blame the buggy lines to identify the original bug-introducing commit (\hbox{\emph{e.g.,}}\xspace c0) and then map them to the corresponding project versions.}(Adopted from Ray \hbox{\emph{et al.}}\xspace~\cite{ray2016naturalness})}}
  \label{fig:evolution}
\end{figure}

\rom{2}.~\textit{Buggy lines retrieved from project evolution.}
As shown in Table~\ref{tab:ssubj}, the percentage of buggy lines \hbox{\emph{w.r.t.}}\xspace the total lines of code in Defects4J\xspace dataset is very small (0.07\%). Such unbalanced data of  buggy vs.~non-buggy lines poses a threat to the efficiency of any classification probelm~\cite{japkowicz2002class,chawla2004editorial}. To reduce such imbalance and thus increase the effectiveness of \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace, previous work injects artificial bugs in the software system under tests~\cite{gunneflo1989evaluation,segall1995fiat}. However, since the motivation of this research comes from the findings that bugs are {\em unnatural}~\cite{ray2016naturalness}, artificially introducing bugs like our predecessors may question our conclusions. To overcome this problem, we injected bugs that developers introduced in the source code in reality\textemdash we collected such bugs from project evolutionary history.

We adopted the similar strategy described in Ray \hbox{\emph{et al.}}\xspace~\cite{ray2016naturalness}. First, we identified bug-fix commits by searching a project's commit logs using bug-fix related keywords: `error', `bug', `fix', `issue', `mistake', `flaw', and `defect', following the methodology described by Mockus~\hbox{\emph{et al.}}\xspace~\cite{mockus2000identifying}.  Lines modified or deleted on those big-fix commits are marked as buggy. Then we identified the original commits that introduce these bugs using SZZ algorithm~\cite{sliwerski2005changes}. Next, we used {\tt git blame} with {\tt --reverse}  option to locate those buggy lines in the buggy program version under investigation. Figure~\ref{fig:evolution} illustrates this process.

Using this method, we found $1541$ additional buggy lines across all the versions of five Defects4J\xspace projects. Thus, in total, in this dataset, we studied $1761$ buggy lines, as shown in~\ref{tab:ssubj}.

\subsection{Evaluation Metric}
\label{sunsec:evaluation_metric}
\begin{figure}
\includegraphics[width=0.9\linewidth]{aucec}
\caption{{\small{\bf  Example Cost Effectiveness (CE) curve for bug localization. Baseline shows CE while inspecting random program elements.
At optimal CE, 100\% of bugs are found when all the buggy program elemnets are  inspected first. A real CE falls somewhere in between baseline and optimal.}}}
\label{aucec_explain}
\end{figure}

To evaluate the bug localization capability of EnSpec\xspace, we adopted commonly used non-parametric measure from literature: Cost Effectiveness (CE) metric originally proposed by Arisholm~\hbox{\emph{et al.}}\xspace~\cite{arisholm2010systematic} to investigate defects in telecom softwares. The main assumption behind this metric is, cost behind bug localization is the inspection effort\textemdash the number of Program Element (PE) needs to be inspected before locating the bug,  and the payoff is the percentage of bugs found. A Cost-Effectiveness(CE) curve shows percentage of inspected PE in {\it x-axis} and percentage of bugs found in {\it y-axis}.

If bugs are uniformly distributed in the source code,
by randomly inspecting $n\%$ of source PE, one might expect to find $n\%$ bugs.
The corresponding CE curve will be a straight line with $slope~\text{=}~1$ (see Figure~\ref{aucec_explain}). This is our baseline. Any ranking metric assigns suspiciousness score to each PE for bug localization. Then, PEs are inspected based on the decreasing order of suspiciousness score. An optimal ranking metric would assign scores in a way that all buggy PEs are ranked prior to the non-buggy PEs. So, inspecting top PEs would cover 100\% of the bugs.  For any real bug localization techniques, \hbox{\emph{e.g.,}}\xspace Tarantula~\cite{jones2005tarantula}, Multric~\cite{xuan2014learning} etc., CE curve falls in between baseline and optimal.

AUCEC, the area of under the CE curve is a quantitative measurement describing how good a model is to find the bugs. Baseline AUCEC (random AUCEC) is 0.5. Optimal AUCEC would be very close to 1.00.  This AUCEC metric is a non-parametric metric similar to the ROC curve and does not depend on bug distribution~\cite{ray2016naturalness}, thus becomes standard in bug-localization literature~\cite{d2010extensive}. Higher AUCEC signifies higher prioritization of buggy lines over non-buggy lines and hence a better model.  For example, for the optimal CE, 100\% source program elements should not have to be inspected to find all the bugs; thus, optimal exhibits higher AUCEC than the baseline (see Figure~\ref{aucec_explain}). This intuition is the basis of our evaluation metric.

\subsection{Implementation of EnSpec\xspace}
\label{subsec:impl}

We implemented EnSpec\xspace's learning to rank technique as described in Step 3 \& 4 of Section~\ref{sec:method} using two approaches. First, we used RankBoost~\cite{freund2003efficient} algorithm. RankBoost algorithm uses boosting ensemble technique to learn model parameter for ranking training instances. At each iteration, it learns one weak ranker and then re-weights the training data. At the final stage, it combines all the weak rankers to assign scores to the test data. This algorithm is used in the past by Xuan \hbox{\emph{et al.}}\xspace~\cite{xuan2014learning} for implementing \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace at method level bug localization. Though there are many competitive approaches to implement \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace, Xuan \hbox{\emph{et al.}}\xspace report the best results till date. Thus, we adapted their approach in EnSpec\xspace to locate bugs at line granularity. We used RankBoost implementation of standard {\bf {\it RankLib}}~\cite{ranklib} library for this purpose. There are two configurable parameters: $\beta$ (initial ranking metric) and $\gamma$ (number of neighbor). Following Xuan \hbox{\emph{et al.}}\xspace, we set these two parameter values to Tarantula and 10 respectively. Table~\ref{tbl:compare_rankboost} shows the result.

In the second approach, we used Random Forest Algorithm (RF) to implement the proposed learning to rank technique.
Random Forest is an ensemble learning technique developed by Breiman~\cite{breiman2001random} based on a combination of a large set of decision trees. Each tree is trained by selecting a random set of features from a random data sample selected from the training corpus. In our case, the algorithm, therefore, chooses some \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace and/or entropy related features randomly in training phase (step 3).  RF then learns conditional probability distribution of the chosen features \hbox{\emph{w.r.t.}}\xspace the bugginess of each line in the training dataset. In addition, RF learns the importances for different features for discrimination.
During training, the model learns $M$ decision trees and corresponding probability distribution. In the testing phase, {\it suspiciousness} scores from each of the learned model, and calculate final {\it suspiciousness} score based on equation~\ref{eqn:ensemble}. For implementation, we used standard python {\tt scikit-learn} package~\cite{sklearn_api}.

\input{comparison}

We compare the performance of the above two approaches using AUCEC$_{100}$ score. For the comparison purpose, we only used \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace related features (\hbox{\emph{i.e.}}\xspace did not include entropy scores), since we first wanted to measure how the two approaches perform in traditional \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace setting. Table~\ref{tbl:compare_rankboost} reports the result. For all of the studied projects, except Wireshark, Random Forest is performing better. Thus, we carried out rest of our experiments using Random Forest based implementation, since this gives the best \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace performance at line level, even when we compare against state of the art Xuan \hbox{\emph{et al.}}\xspace's technique.

\subsection{Research Questions}
\label{sec:rq}

To evaluate EnSpec\xspace, we investigate whether a good language model (LM\xspace) that captures naturalness (hence unnaturalness) of a code element can improve spectrum based testing. Previously, Ray \hbox{\emph{et al.}}\xspace~\cite{ray2016naturalness} and Wang \hbox{\emph{et al.}}\xspace~\cite{wang2016bugram} demonstrated that unnaturalness of code elements (measured in terms of entropy) correlate with bugginess. Thus, LM\xspace can help in bug localization in a static setting. In contrast, \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace is a dynamic approach that relies on the fact that code elements that are covered by more negative test cases are more bug-prone. Therefore, to understand the effectiveness of EnSpec\xspace, we will investigate whether the combination of the two can improve bug-localization as a whole.

Since LM\xspace based bug-localization approach says that more entropic code is more bug prone, and \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace says that code element covered by more negative test cases are more prone to bugs, to make the combined approach work, the difference between entropies of the buggy and non-buggy lines should be significant for the negative test spectra. Thus, to understand the potential of entropy,  we start our investigation with the following research question:

\RQ{rq1}{How is entropy associated with bugginess for different types of test spectra?}

If the answer to the above question is affirmative for failing test spectra,  entropy can be used along with \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace for bug-prediction.  For every code element, \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace provides suspiciousness scores, and  LM\xspace predicts its uncertainty in terms of entropy. Thus, one may expect that among the lines with higher suspiciousness score, more entropic lines are even more likely to be buggy. We, therefore, investigate whether entropy can help improving the bug prediction capability of EnSpec\xspace over \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace.

\RQ{rq2}{Can entropy improve \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace's bug-localization capability?}

To build a good LM\xspace based bug localization technique, we need a large code corpus with adequate bug history; this is often challenging for smaller projects. A similar problem arises for history based defect prediction models\textemdash for newer projects enough history is usually not available to build a good model. In such case, researchers, in general, rely on the evolutionary history of other projects~\cite{zimmermann2009cross}. To mitigate the threat of using our proposed approach for smaller code base, we leverage such cross-project defect prediction strategy. We investigate, whether a language model trained on different projects can still improve \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace's performance.

\RQ{rq3}{What is the effect of entropy on \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace's bug localization capability in a cross-project setting?}

\section{Motivating Example}
\label{sec:motivation}
In this section, we present a real-world example that motivated us to incorporate the \Comment{Natural Language Property} {\it naturalness} property of code  (i.e. {\it entropy} based features) in \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace to overcome a key limitation of \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace.

The main limitation of testing based bug\xspace localization approaches, such as \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace, is that the quality of their results highly depend on the quality of test cases. If the passing test cases have low code coverage, an \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace tool may return a large number of program elements with high suspiciousness score, most of which are false positives. However, generating an adequate test suite is incredibly difficult. Therefore, in many cases \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace performs poorly.

\begin{table}[h]
\begin{tabular}{p{0.9\textwidth}}

\scriptsize {\tt{--- /Closure/89/buggy/src/com/google/javascript/jscomp/}}
\scriptsize {\tt{GlobalNamespace.java}}\\
\scriptsize {\tt{+++ /Closure/89/fix/src/com/google/javascript/jscomp/}}
\scriptsize {\tt{GlobalNamespace.java}}
\lstinputlisting[ language=java]{example.java}\\
\end{tabular}
\caption{Effectiveness of entropy based features to improve \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace}
\label{tbl:motivating_example}
\end{table}
\vspace{20pt}

\Comment{For example, on a test run, a trained model is tested with 3731 lines of which 10 lines are actual bug. Test result shows that 9 of those 10 buggy lines are placed relatively higher position in the ranklist when we incorporated {\it Entropy} based features.}

Table~\ref{tbl:motivating_example} presents a patch that fixed a bug in Closure compiler\xspace (Defects4J bug\xspace ID: 89). The buggy line, marked in~\Red{red}, was never used in the existing corpus before. Hence, the line was unnatural to a LM\xspace with a high entropy score of $7.36$. When developer fixed the bug (see~\dkgreen{green} line), the code becomes more natural with a reduced entropy score of $1.15$. A traditional state-of-the art \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace technique
placed the buggy line at 57$^{th}$ position, while EnSpec\xspace using both {\it entropy} and {\it spectrum} based features, placed the line at 12$^{th}$ position in the ranked list of suspicious lines. This shows that entropy of code, as derived from LM\xspace, can play an important role to improve the ranking of the actual buggy\xspace lines.

\Comment{When using only \ripon{nth and nth} position respectively. However, we observe that the code surrounding buggy lines is dealing with \texttt{maxMiddleIndex} while the buggy lines are dealing with \texttt{minMiddleIndex}, which is unnatural. After fixing the bug by replacing \textit{minMiddleIndex} by \textit{maxMiddleIndex}, that unnaturalness is gone, which supports the findings of Ray \hbox{\emph{et al.}}\xspace~\cite{}.}

\Comment{\ripon{I did not find the argument of unnaturalness in the above paragraph very convincing. Isn't it the reason that if minMiddleIndex is there, it breaks a pattern that is present elsewhere in the program?}}

\Comment{The example above is a code snippet from Project Chart bug number 7. In our experiment, using only \textit{spectrum} based features cannot detect this fault, but when we incorporated \textit{entropy} based features, this fault is identified. In any testing based fault localization, defecting faults highly depends on the test cases. If test cases are insufficient to cover all possible execution path, testing cannot guarantee detecting all bugs. Generating such high performance test suite is also incredibly difficult. We firmly believe this is the case for this reason.
But, as we can see in the code surrounding lines of the buggy version of the code is dealing with \textit{maxMiddleIndex} while the buggy lines are dealing with \textit{minMiddleIndex}, which  is quite unnatural. And the fix of that bug also supports our intuition. the bug is fixed by replacing \textit{minMiddleIndex} by \textit{maxMiddleIndex} in line $297$}

\Comment{On the other hand, there there Another example from Project Math where the bug cannot be identified by the \textit{entropy} based features but can be identified by \textit{spectrum} based features.}

\Comment{On the other hand, the main limitation of entropy-based metric is that although source code elements are repetitive, there are exceptions. Therefore, in case a bug fix does not follow the repetitious pattern, the buggy lines may not be ranked high enough. Figure~\ref{example:math_only_spectrum} presents such an example. In this case, \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace may help entropy-based localization.

\begin{figure}[h]
\includegraphics[width=0.5\textwidth]{images/math_only_spectrum.png}
\caption{Entropy cannot but spectrum based features can detect this bug\xspace}
\label{example:math_only_spectrum}
\end{figure}

\Comment{We believe this \textit{return new VectorialPointValuePair(point, objective)} is fairly common in code corpus, so, the entropy based features has failed to identify this. But, this buggy code also defies the software requirement and hence lets the test cases to fail. }}

\section{Preliminaries}
\label{sec:prelim}
In this section, we discuss the preliminaries and backgrounds of our work.

\subsection{Spectrum-based Bug\xspace Localization}
\label{subsec:spectrum}

Given a buggy\xspace code-base with at least one bug\xspace reproducing test case, a spectrum-based bug\xspace localization technique (\hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace) ranks the code elements under investigation (e.g., files/classes, functions/methods, blocks, or statements) based on the execution  traces of passing and failing test cases. Therefore, in this approach, first the subject program is instrumented at an appropriate granularity to collect the execution trace of each test case ({\it test spectra}). The basic intuition behind \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace is that the more a code element appears in failing traces (but not in passing traces), the more suspicious the element to be buggy\xspace.

\input{metric}

More specifically, for a given program element $e$, \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace records how many test cases execute and do not execute $e$, and computes the following four metrics: the number of (i) tests passed ($e_p$) and (ii) tests failed ($e_f$) that executed $e$, and the number of (iii) tests passed ($n_p$) and (iv) tests failed ($n_f$) that did not execute $e$.
A suspiciousness score is calculated is calculated as a function of these four metric: $S = Func(e_p,e_f,n_p,n_f)$, as shown in Table~\ref{tab:spectra}.
The table also presents two widely used suspiciousness score measure: Tarantula and Ochai. \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace ranks the program elements in a decreasing order of suspiciousness and presents to the developers for further investigation to fix the bug~\cite{xuan2014learning}. These scores also help to repair program automatically~\cite{le2012representations}.

\subsection{Language Models}

Although real-world software programs are often large and complex, the program constructs (such as tokens) are repetitive, and thus provide useful predictable statistical property~\cite{Hindle:2012:ICSE, Raychev:2014:PLDI, Tu:2014:FSE, Franks:2015:ICSE}. These statistical properties of code resemble natural languages, and thus, natural language models can be leveraged for software engineering tasks.

\textbf{Cache based N-gram Model (\$gram\xspace):} Hindle \hbox{\emph{et al.}}\xspace introduced n-gram model for software code~\cite{hindle2012naturalness}, which is essentially an extension of n-gram language model used in natural language processing tasks based on the \textit{Markov independence assumption}~\cite{brown1992class_ngram}.  If a sequence, $s$ consists of $m$ tokens ($a_1 a_2 a_3 ... a_m$), according to the \textit{Full Markov Model}, the probability, $p(s)$, of that sequence is given in Equation~\ref{eqMkvModel}
\begin{equation}
\label{eqMkvModel}
\small
p(s) = p(a_1)p(a_2|a_1)p(a_3|a_1a_2) ... p(a_m|a_1a_2...a_{m-1})
\end{equation}

\textit{N-gram model} is a simplification of full Markov model based on the assumption that every token is dependent on previous $n-1$ token, where $n$ is a model parameter. Essentially with $n=\infty$, the model converges to the full Markov model. Since, actual probabilities are very difficult to find, researchers often use empirical probabilities to represent actual probabilities, which is highly dependent on the training data. Initially, the probability of a token or any n-gram which is not seen in the corpus will be \textit{zero} resulting the total probability to be \textit{zero}. To overcome this problem Hindle \hbox{\emph{et al.}}\xspace~\cite{hindle2012naturalness} also adopted smoothing techniques from natural language processing literature.

Tu \hbox{\emph{et al.}}\xspace~\cite{tu2014localness} further improved the above model based on the observation that source code tends to be highly localized, \hbox{\emph{i.e.}}\xspace  particular token sequences may occur often within a single file or within particular classes or functions. They proposed a \$gram\xspace model that introduces an additional cache\textemdash list of n-grams curated from local context and used them in addition to a global n-gram model. They also defined the entropy of a code sequence $S$ by language model $M$ by Equation~\ref{eqLocalModel}:

\begin{equation}
\label{eqLocalModel}
\small
H_M(S) = -\frac{1}{N}\log_2p_M(S) = -\frac{1}{N}\sum\limits_{i=1}^{N}\log_2P(t_i|h)
\end{equation}

\textbf{Language model to predict buggy code:} Ray \hbox{\emph{et al.}}\xspace~\cite{ray2016naturalness} demonstrated that there is a strong negative correlation between code being buggy and the naturalness of code. When a simple \$gram\xspace model is trained on previous versions of project source code and applied to calculate naturalness of code snippet, buggy codes are shown to exhibit higher unnaturalness than the non-buggy codes. They introduced a syntax-sensitive entropy model to measure naturalness of code. In their investigation, they found that some token types such as packages, methods, variable names are less frequent, and hence high entropic than others. They normalized the entropy score and derived a Z-score with line-type information from the program's Abstract Syntax Tree (AST). The Z-score is defined as:

\begin{equation}
\label{eqZscore}
\small
\$gram+type\xspace = \frac{entropy_{line}-\mu_{type}}{SD_{type}}
\end{equation}

In Equation~\ref{eqZscore}, $\mu_{type}$ is the mean \$gram\xspace model entropy of a given line type, and $SD_{type}$ is the standard deviation of that line type. This Z-score gives the syntax-sensitive entropy. They reported that, buggy lines of codes are usually unnatural and highly entropic. With further investigation, they also found that, when developers fixed those buggy lines of codes, the entropy of the code decreased. In this work, we used state of the art \$gram\xspace model along with syntax-sensitive entropy model.

\section{Related Work}
\label{sec:related}
Automatic bug\xspace localization has been an active research area over two decades. Existing techniques can be broadly classified into two broad categories: i) static and ii) dynamic approaches.

{\bf Static approaches} primarily rely on program source code. There are mainly two kinds of static approaches: a) program analysis based approaches, and  b) information retrieval (IR) based approaches. Program analysis based approaches  detect bugs by identifying well-known buggy patterns that frequently happened in practice. Therefore, although these approaches are effective in preventing bugs by enforcing good programming practices, they generally cannot detect functional bugs. {FindBugs}~\cite{ayewah2008using} is a popular example in this category. On the other hand, IR-based approaches, given a bug report, generally rank source code files based on the textual similarity between source code and the bug report so that potential buggy files ranked high in the ranked-list. These approaches are generally fast but identify bugs at coarse grained level.	 BugLocator~\cite{zhou2012should}, BLUiR~\cite{saha2013improving} are some of the examples in this category.

There is a new line of work that recently started based on statistical modeling and machine learning. Wang et al.\cite{wang2016automatically} proposed a Deep Belief Network based approached to detect file level defects. Wang et al.\cite{wang2016bugram} used n-gram language model to generate a list of probable bugs.

{\bf Dynamic approaches} generally rely on the execution traces of test cases. \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace is a dynamic fault localization technique that leverages program spectra\textemdash program paths executed by passed and failed test cases~\cite{reps1997use} to compute a suspiciousness score of each program element. We have described \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace in detail in Section~\ref{subsec:spectrum}.
Several metrics have been proposed in the literature to calculate the suspiciousness score. For example, Jones \hbox{\emph{et al.}}\xspace presented Tarantula~\cite{jones2005tarantula} based on the fact that program elements executed by failed test cases are more likely to bug\xspace than the elements not executed by them (see Table~\ref{tab:spectra}). Jaccard and Ochiai are some of the well known variants of this approach proposed by Abreu \hbox{\emph{et al.}}\xspace~\cite{abreu2007ochiai_and_jaccard}. Xie \hbox{\emph{et al.}}\xspace proposed five ranking metrics by theoretical analysis and four other metrics based on genetic algorithms~\cite{xie2013theoretical}. Later, Lucia \hbox{\emph{et al.}}\xspace did a comprehensive study of the different ranking metrics and showed that no ranking metric is unanimously best~\cite{lucia2014extended}. \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace approaches can identify bugs at fine-grained level.

Xuan \hbox{\emph{et al.}}\xspace~\cite{xuan2014learning} proposed an approach to combine multiple ranking metrics. They adopted neighborhood based strategy to reduce the imbalance ratio of buggy and non-buggy program entities. For their algorithm, they need an initial metric to define the neighborhood. They sort the data based on an initial ranking metric. The filtered $\beta$ non-faulty entities before and after a faulty entity. After that, they applied state of the art "Learning to Rank" algorithms to combine all 25 suspiciousness scores. Their dependence on an initial ranking metric might cause a bias towards that metric. In contrast, to be unbiased to any of the metric, we considered all the data and applied state of the art random under-sampling\cite{batista2004study} technique.

Gong \hbox{\emph{et al.}}\xspace~\cite{gong2012interactive} proposed a feedback based fault localization system, which uses user feedback to improve performance. Pytlik \hbox{\emph{et al.}}\xspace~\cite{pytlik2003automated} proposed the fault localization system using the likely invariant. Le et al.\cite{b2016learning} also proposed an approach similar to Pytlic et al. with a larger invariant set. Unlike this work, they experimented on method level fault localization system. Sahoo et al. extended Pytlik et al's work. Their work is on test case generation and also they adopted backward slicing to reduce the number of program element to be considered.

{\bf Multi-modal techniques} generally combine two or more model of bug\xspace localization to improve the accuracy further. Le et al.~\cite{le2015information} proposed a multi-modal technique for bug localization that basically combines the IR and spectrum based bug localization together. Their technique needs three artifacts: i) a bug report, ii) program source code, and iii) a set of test cases having at least a fault reproducing test case. Their technique first rank the source code methods based on the textual similarity between bug report and source code methods. Then using program spectra, they rank the source code lines and also identifies a list of suspicious words associated with the bug. Finally they combine these scores using a probabilistic model which is trained on a set of previously fixed bugs. Based on an empirical evaluation on 157 real bugs from four software systems, their model outperforms a state-of-the-art IR-based bug localization technique, a state-of-the-art spectrum-based bug localization technique, and three state-of-the-art multi-modal feature location methods that are adapted for bug localization.

The proposed approach in this paper is also multi-modal in nature. However, instead of combining IR-based textual similarity score,inspired by Ray et al.'s\cite{ray2016naturalness} finding that the buggy codes are unnatural, and thus entropy of a buggy source code is naturally high, we combine source code entropy with program spectra to improve bug localization. To our knowledge, no one leveraged the localness of code and test spectrum together to locate faults. The advantage of our approach is that we do not need any bug report which may not be available for development bugs. Therefore, our approach is complementary to Le et al's approach.

\section{Result}
\label{sec:result}
\setcounter{RQCounter}{0}

In this section, we answer the research questions introduced in~\ref{sec:rq}. Our investigation starts with whether the buggy lines in failing test spectrum are more entropic than non-buggy lines. Note that, all the buggy and non-buggy lines are annotated using the strategy described in~\ref{subsec:dc}.

\input{rq1}
\input{rq2}
\input{rq3}

\section{Threats to Validity}
\label{sec:threats}

Efficiency of EnSpec\xspace depends on the availabity of previous bugs on which the model will be trained. To minimize this threat, we demonstrated that EnSpec\xspace works well in cross-project setting.

EnSpec\xspace is also dependent on the adequecy of the test suite. If there are not enough failing test cases, performance of \hbox{${\cal S}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal B}\hspace{-0.01in}{\cal L}$}\xspace may get hurt, and hence EnSpec\xspace's performance will also be worse. However, since EnSpec\xspace is a hybrid approach, it does not solely depend on test suites. The LM\xspace based part will still be able to locate bugs since the latter does not require anything but source code.

 Further, to annotate buggy lines, we rely on the publicly available bug-dataset and some evolutionary bugs. It can be possible there are other bugs lying in the code corpus that are polluting our results. However, at any given point of time it is impossible to know the presence of all the bugs in a software.

 Finally, to minimize threats due to external validity, we evaluated EnSpec\xspace on 10 projects for 2 languages: C and Java. This proves, EnSpec\xspace is not restricted to any particular programming language.