Reranking-based Crash Report Deduplication
H
H

Akira MorooI

Akiko Aizawa

Tokyo University of Science

I

Abstract

H

Takayuki Hamamoto

National Institute of Informatics
Crash report
Stack trace

1

Introduction

Modern software products such as web browsers havea large and complicated code base along with an increasing number of bugs. To fix these bugs efficiently, developers prioritize high-frequency bugs using crash reports: summaries of the status of the software execution upon its unexpected termination. Figure 1 portrays the structure. A crash
report includes a description, machine environment information, and a stack trace. A stack trace presents multiple
stack frames with indexes. A lower index denotes a newer
frame in the stack trace. An actual crash is caused in the #0
frame: the top frame. Therefore, a bug causing a crash istypically included in the frame near the top frame.
The information in stack traces is helpful for detecting
and fixing bugs. Therefore, software-development projects
collect such crash report from their users and cluster themaccording to the detected bugs. However, because of the numerous and diverse crash reports, clustering them manually
is infeasible. Many automated crash report deduplication
methods have been proposed to address this issue. However, most methods present performance issues because of
their high computational costs. As described herein, we
propose a reranking-based automated crash report clustering method. Reranking is a well-known technique for information retrieval where the ranking of initial search results
is re-ordered using another computationally more expensive
ranking function.
The contribution of this paper is that we introduce
reranking-based crash report deduplication for reduced
computational costs. This report is the first of the relevant
DOI reference number: 10.18293/SEKE2017-135#0 Frame
Address, Function，Module, etc.
#1 Frame
Address, Function，Module, etc.

…

Software projects collect and deduplicate vastly numerous crash reports from users to fix bugs efficiently. However,most existing automated methods have performance issues
during large-scale clustering. We propose a rerankingbased crash report clustering method. Our method is acombination of two earlier methods. By computing similarity used in ReBucket for the crash reports that are highly
similar to the query crash report, the method can processreports with throughput equal to that of PartyCrasher. We
also introduce an automatically generated dataset for crash
report clustering tasks. The evaluation revealed that our
method performs at high processing speed while maintaining high accuracy.

Description, Environment Info, etc.

Figure 1: Crash Report Structure.
literature to describe a study by which a reranking scheme
is shown to be effective in crash report deduplication.

2

Related Work

Existing methods for automatic crash report deduplication can be categorized into the following two types: Oneis based on the similarity of feedback from users written innatural language[1, 2]. The other is based on the similarityof stack traces. As described in this paper, we specificallyexamine the latter type because stack-trace-based methods
achieve higher accuracy than NLP-based methods.
Socorro1 is a crash report management system developedby Mozilla. In this system, a string called signature is generated for each crash report by applying several heuristic
rules to the stack trace. Then, the system classifies all reports with the same signature into the same group. Thissystem requires human elaboration for editing and updating
signature-generation rules.
Lerch and Mezini [3] introduced a method using a TFIDF-based full-text search engine. Campbell et al. [4]also used a full-text search engine and compared several
tokenization methods used for indexing. These methods
can achieve reasonable runtime performance for large-scale
clustering. However, the accuracy is often worse than that
achieved with other methods because the features used in
the search engines ignore the order of the frames.
Dhaliwal et al. [5] proposed a method using the Levenshtein distance as similarity between two stack traces. The
Levenshtein distance is used to measure the similarity of
two strings. This approach regards one frame as a character. Dang et al. [6] defined similarity between two stack
1 https://wiki.mozilla.org/SocorroReranking

Searching
Crash report
to be clustered: 𝑅0

Computing sim

Reordering

Sim of ReBucket: 𝑠𝑖𝑚#4

(

𝑅0

𝑠𝑖𝑚#4

𝑅0

,

𝑅#5

)

Result from search engine: 𝑹𝑹

higher 𝑠𝑖𝑚9:
𝑹𝑹 =

{

𝑅#$

𝑅#%

⋯

𝑅#&

}

Clustering

Harmonic Mean of𝑠𝑖𝑚#4 and 𝑠𝑖𝑚9: : 𝑠𝑖𝑚-&

𝑹𝑹 =

{

𝑅#$

𝑅#%

⋯

𝑅#&

{

𝑅#$ ′

𝑅0

𝑅#$ ′
Existing Cluster

higher 𝑠𝑖𝑚-&
𝑹𝑹 ′=

}

𝑅#$ ′ ≥ 𝑇-&

𝑅#% ′

⋯

𝑅#& ′

}

.
𝑅#$
< 𝑇-&

𝑅0
New Cluster

Figure 2: Overview of Proposed Method.

traces based on Position Dependent Model. Because these
distance-based methods can capture the features of stack
traces, they are useful for high-accuracy clustering but withhigh computational complexity.
As described in this paper, we use PartyCrasher [4] and
ReBucket [6] as baselines. PartyCrasher is implemented
as an open-source project2 . It is easily extensible. Amongthese methods, ReBucket achieved the highest reported accuracy: 0.88 F1-measure on average.

3

Methodology

The proposed method is a consolidation of two stateof-the-art deduplication methods: ReBucket [6] and PartyCrasher [4]. Figure 2 presents an overview of the method.
It comprises three modules: searching, reranking, and clustering. Given a pool of crash reports (already clustered) anda target crash report to be clustered, the search module uses
the target report as a search query. Thereby, it obtains an
initial ranking list of possibly similar crash reports. We follow the technique proposed in PartyCrasher [4] here, anduse a general-purpose search engine. Next, the reranking
module re-orders the initial results with the similarity function defined in ReBucket [6]. Finally, the clustering module
either selects a cluster from existing ones or generates a newcluster for the target crash report.
3.1

Searching

Let RQ be a crash report to be processed. Using a fulltext search engine, the system obtains the top M search
result RR = {RR1 , RR2 , . . . , RRM }. In [4], multiple tokenization methods for indexing are compared. Our system uses Camel, which achieved the highest accuracy. In
Camel, all frames in a stack trace are tokenized by space
separation and for each camel case. Symbols are deleted.
Hereinafter, we designate the stack trace of the crash report
2 https://github.com/naturalness/partycrasher

RX as CX .
Most full-text search engines use TF-IDF weight to rank
results. Term Frequency (TF) represents how many times acertain term appears in a document. Inverse Document Frequency (IDF) is the reciprocal of the number of occurrencesof a certain word in all documents. In our method, we use
the same normalization as the one used in Elasticsearch3 .
Letting W (Cq ) be a set of words in a stack trace Cq , tft,Cd
and idft,Cd be a value of DF and IDF of a word t in a stack
trace Cd , respectively, and denoting the word count in Cd
as ntCd , the similarity score used in PartyCrasher between
Cq and Cd is defined as
simP C (Cq , Cd ) =

∑

(

√

tft,Cd × idft × √t∈W (Cq )

1
ntCd

)
.
(1)

3.2

Reranking

In ReBucket [6], similarity is computed by emphasis on
the common frame position between two stack traces. Two
metrics are defined: distance to the top frame and alignment
offset. The distance to the top frame represents the distancefrom an arbitrary frame to the top frame in the same stack
trace. The alignment offset represents the difference of the
distance to the top frame between the frames that match intwo stack traces.
These metrics are based on the following insights: First,
an important frame has a smaller distance to the top frame.
Second, the alignment offset between matching frames issmaller for stack traces with higher similarity. Let fi and fj
respectively denote the i-th and the j-th frames of Cq and
Cd . Denoting distance to the top frame as min(i, j) andalignment offset as abs(i − j), the cost function cost(i, j)
3 https://www.elastic.co/products/elasticsearch

of fi and fj is defined as follows in ReBucket.
{
e−c∗min(i,j) e−o∗abs(i−j) if fi = fj′
cost(i, j) =(2)0otherwise
Therein, c and o are weighting parameters. With ReBucket,
similarity between stack traces Cq and Cd is defined as
Mm,nsimRB (Cq , Cd ) = ∑l
,
−cj
j=0 e

(3)

where m and n are at respective depths of Cq and Cd , andl = max(m, n). In addition, Mi,j is the optimal cost at
depth i, j calculated recursively using dynamic programming.
The computational cost is O(mn) in the above calculation. According to [7], about 90 % of crash reports can be
fixed by referring only to the top 10 frames. Therefore, we
use only the top 10 frames in our calculation.
The final similarity score between Cq and Cd we use forreranking is given as
simHM =
3.3

simRB · simP C.
α · simRB + (1 − α) · simP C(4)Clustering

Table 1: Dataset Information.

Launchpad
Firefox48

Project
UbuntuLaunchpad
MozillaFirefoxCrash
reports

Clusters

Version

Packages

15,293

3,824
727

N/A
from 48.0a1
to 48.0b99

816

36,752

1

we collected from Mozilla Firefox. Table 1 presents a summary of the datasets.
Launchpad is more reliable than Firefox48 because Launchpad contains clusters produced by hand,whereas the clusters of Firefox48 are automaticallyconstructed as shown below. Firefox48 differs from
Launchpad in that the dataset includes a single software package whereas Launchpad includes many different packages provided by Ubuntu’s package manager.
Many projects deal with a single product in their report systems. Therefore, we presume that our evaluation can be
more solid by introducing the Firefox48 dataset.
We followed [5] to create the dataset, which comprises
crash reports and corresponding bugs. A set of crash reports that link to the same bug form a cluster. We gathered
100 crash reports at most from each of the top 300 highfrequency clusters between ver. 48.0a1 and 48.0b99. Whenthe same bug is found to cause two crash clusters, theseclusters are grouped into a single cluster. Furthermore, we
extract stack traces and metadata from the crash reports.

In the same way as PartyCrasher, we compare the simi′, which has the highest similarity
larity of crash report RR1′
in RR , with the threshold THM . If it is greater than THM ,then RQ is clustered into the same cluster as RR1 . Otherwise, it is clustered into a new cluster because it is regarded
as a crash by the new type bug.
The computational overhead of the search engine in our
method is O(N logN ), which is negligible compared withthe computational cost of stack trace similarity. Therefore,
we compare the size of the distance matrix that requires
stack trace similarity calculation. ReBucket uses hierarchical agglomerative clustering (HAC) algorithm for crash
report clustering. This method requires O(N 2 ) because it
computes an N ×N distance matrix where N is the numberof total crash reports. In contrast, the clustering algorithm
used in the proposed method requires O(M N ), where M
is the number of search results. As with M ≪ N , the proposed method can reduce the computational cost comparedwith HAC.

Let BCubed precision be denoted as Bp and BCubed recall as Br. Bp represents how many reports in an estimatedcluster belong to the same cluster in ground truth. Br denotes how many reports in a cluster of grand truth belong
to the same estimated cluster. The quality of the generated
clusters is better when the values of Bp and Br are closer
to 1.0. Based on the Bp and Br, the BCubed F1-meature(BCF) is calculated as BCF = (2 · Bp · Br)/(Bp + Br). A
tradeoff exists between Bp and Br. Higher BCF indicateshigher accuracy[8].
The number of crash reports processed per unit of time
is taken as the performance criterion. ReBucket uses multiprocessing to calculate distance matrixes. Therefore, we
multiply the actual processing time by the number of processes.

4

4.3

Evaluation Experiment

In this section, we present evaluations of PartyCrasher,
ReBucket, and our proposed method from the perspectivesof accuracy and runtime performance.
4.1

DatasetWe use two datasets: Launchpad 4 , an existing dataset
from Ubuntu Launchpad, and Firefox48, a new dataset
4 https://archive.org/details/bugkets-2016-01-30

4.2

Evaluation Metrics

Determining Parameters

We determined optimal parameters using a subset fromthe first 20 % of the dataset. The rest are used for testing. The time cost of determining optimal parameters is notincluded in the performance results. Table 2 presents the
final values used in the evaluation. Both ReBucket and our
method require c and o in (2). TRB is a distance thresholdfor HAC in ReBucket. Moreover, α in (3), M , the size of
initial ranking list, and THM , the clustering parameter, areTable 2: Parameters used in the evaluation.
Launchpad
Firefox48

c
0.3
0.4

o
0.1
0.4

TRB
0.07
0.26

α
0.3
0.0

M
50
50

THM
11.0
2.0

Table 3: Evaluation Results of Accuracy.

PartyCrasher
ReBucket
Proposed

Launchpad
Bp
Br
BCF
0.723 0.671 0.696
0.775 0.515 0.618
0.807 0.626 0.705

Firefox48
Bp
Br
BCF
0.778 0.424 0.549
0.662 0.717 0.688
0.728 0.651 0.687

tiple packages are included in the dataset. The proposed
reranking scheme compensates the issue by filtering out unrelated candidates before applying ReBucket.
Table 4 presents performance evaluation results. Table
4 shows that the processing speed of the proposed method
is higher than that of ReBucket. In addition, our method
achieved almost equal performance to that of PartyCrasher.
Our method is almost 730 times faster.
To summarize, our results demonstrate that the proposed method has better runtime performance than ReBucket while maintaining accuracy.

5
Table 4: Performance Evaluation Results.

PartyCrasher
ReBucket
Proposed

Performance[Reports/s]
Launchpad Firefox48
2.500
4.663
0.004
0.021
2.922
4.022

used only for the proposed method. The number of used
processes of ReBucket is 60 because of limitation of theavailable computation resources. The parameters c, o, andTRB are robust and about 20 % of the searched combinations achieve over 90 % of the highest BCF. By contrast,α, M and THM are sensitive. Especially, we observe thatwhen M is too large, both accuracy and performance decrease.
4.4

Results

Table 3 presents accuracy evaluation results. The
proposed method achieved the highest BCF value forLaunchpad. Bp of our method is also the highest. In
addition, results show that ReBucket showed high accuracy
in terms of BCF because the Br of PartyCrasher drops to0.424. Moreover, the BCF value of the proposed method is
the same as that of ReBucket.
The difference in accuracy between Launchpad andFirefox48 can be attributed to the differences of thenumbers of packages: 816 for Launchpad and 1 forLaunchpad. It is likely that the same cluster includes reports from the same package in most cases. Results showthat ReBucket has a difficulty recognizing the difference
when the dataset includes multiple packages because it relies completely on frames in the stack traces.
To validate this point, we created a subset of
Launchpad using reports from only one package, ”nautilus.” Then, the BCF values of PartyCrasher, ReBucket,
and our method become 0.616, 0.662, and 0.666, correspondingly. With the subset, ReBucket achieves better performance than PartyCrasher, which is the opposite of theresult with the original Launchpad. Based on this result,
we conclude that ReBucket does not perform well if mul-Conclusion

As described in this paper, we propose an automated crash report deduplication method applying reranking against reports of the results obtained from the full-text
search engine. We also constructed a new dataset for crash
report clustering tasks from Mozilla Firefox. The evaluation results demonstrate that our method is equal to that of
ReBucket in terms of accuracy, but with faster performance.
Our current method uses statically tuned parameters witha subset. Manual merging or division of crash clusters is
assumed in real operations. In future studies, we expect toinvestigate a dynamic parameter tuning method using user
feedback for more stable accuracy.

References[1] P. Runeson, M. Alexandersson, and O. Nyholm, “Detection of duplicate defect reports using natural language processing,” in Proceedingsof the 29th International Conference on Software Engineering, 2007,
pp. 499–510.
[2] A. Alipour, A. Hindle, and E. Stroulia, “A contextual approach towards more accurate duplicate bug report detection,” in Proceedings ofthe 10th Working Conference on Mining Software Repositories, 2013,
pp. 183–192.
[3] J. Lerch and M. Mezini, “Finding duplicates of your yet unwritten
bug report,” in Proceedings of the 2013 17th European Conference on
Software Maintenance and Reengineering, 2013, pp. 69–78.
[4] J. C. Campbell, E. A. Santos, and A. Hindle, “The Unreasonable
Effectiveness of Traditional Information Retrieval in Crash Report
Deduplication,” in Proceedings of the 13th International Conferenceon Mining Software Repositories, 2016, pp. 269–280.
[5] T. Dhaliwal, F. Khomh, and Y. Zou, “Classifying Field Crash Reports
for Fixing Bugs: A Case Study of Mozilla Firefox,” in Proceedingsof the 2011 27th IEEE International Conference on Software Maintenance, 2011, pp. 333–342.
[6] Y. Dang, R. Wu, H. Zhang, D. Zhang, and P. Nobel, “ReBucket: A
Method for Clustering Duplicate Crash Reports Based on Call Stack
Similarity,” in Proceedings of the 34th International Conference on
Software Engineering, 2012, pp. 1084–1093.
[7] A. Schröter, N. Bettenburg, and R. Premraj, “Do stack traces help developers fix bugs?” in 2010 7th IEEE Working Conference on Mining
Software Repositories, 2010, pp. 118–121.
[8] E. Amigó, J. Gonzalo, J. Artiles, and F. Verdejo, “A Comparisonof Extrinsic Clustering Evaluation Metrics Based on Formal Constraints,” Inf. Retr., vol. 12, no. 4, pp. 461–486, 2009.