Abstract—Software often crashes. Once a crash happens, a crash
report could be sent to software developers for investigation upon
user permission. To facilitate efficient handling of crashes, crash
reports received by Microsoft’s Windows Error Reporting (WER)
system are organized into a set of “buckets”. Each bucket
contains duplicate crash reports that are deemed as
manifestations of the same bug. The bucket information is
important for prioritizing efforts to resolve crashing bugs. To
improve the accuracy of bucketing, we propose ReBucket, a
method for clustering crash reports based on call stack matching.
ReBucket measures the similarities of call stacks in crash reports
and then assigns the reports to appropriate buckets based on the
similarity values. We evaluate ReBucket using crash data
collected from five widely-used Microsoft products. The results
show that ReBucket achieves better overall performance than the
existing methods. In average, the F-measure obtained by
ReBucket is about 0.88.
Keywords: Crash reports, clustering, duplicate crash report
detection, call stack trace, WER
I. INTRODUCTION
A software crash is one of the most severe manifestations
of a defect (bug) in software, and is typically assigned a high
priority to be fixed. To facilitate debugging, many crash
reporting systems such as Windows Error Reporting [10],
Apple crash report [2], and Mozilla crash report [20] have been
deployed to automatically collect crash reports from users at
the time of crash.
Crash reports, which may be considered “telemetry data”,
can include information such as the crashed module’s name
and call stack traces. Such information is useful to software
developers trying to determine the cause of a crash [10, 23]. In
some cases, a large number of crash reports may arrive daily.
Many of these crash reports are actually caused by the same
bug and are therefore duplicate reports. To help developers
reduce debugging efforts, it is important to automatically
organize duplicate crash reports into one group.
In the Microsoft Windows Error Reporting (WER) system,
crash reports are organized according to “buckets”. Ideally,
each bucket contains crash reports that are caused by the same
bug. A number of heuristics are used to generate the buckets
[10]. Developers prioritize bug fixing efforts based on the
number of crash reports received by each bucket (i.e., the
number of hits). A bucket with a higher number of hits will be
investigated with higher priority compared with a bucket with a
lower number of hits. However, it is still not uncommon that
crashes caused by one bug spread to multiple buckets (the
“second bucket problem”) [10]. Also, WER may generate
many buckets that contain only one or a few number of crash
reports (the “long tail” problem). The existence of the second
bucket problem and the long tail problem reduces the
effectiveness of effort prioritization and problem diagnosis.
To improve the accuracy of bucketing, in this paper, we
propose ReBucket, a method for clustering crash reports based
on call stack similarities. To measure the similarity between
two call stacks, we propose a new similarity measure called the
Position Dependent Model (PDM). PDM computes the
similarity between two call stacks based on the number of
functions on two call stacks, the distance of those functions to
the top frame, and the offset distance between the matched
functions. In ReBucket, a training process is also designed to
tune the parameters required by PDM.
We evaluate ReBucket using crash data collected from five
widely-used Microsoft products. The results show that the
performance of ReBucket is promising. On average, the F-
measure achieved by our method is about 0.88. ReBucket also
achieves better overall results than the existing methods,
including the existing WER bucketing method.
We believe the proposed ReBucket method can help
prioritize debugging efforts and facilitate problem diagnosis.
We have worked closely with a Microsoft product team and
they helped review twenty crash report clusters we obtained by
using ReBucket and confirmed that 70% of them are very
meaningful clusters.
The contributions of this paper are as follows:
g120 We propose a new bucketing method, ReBucket, for
clustering duplicate crash reports.
g120 In ReBucket, we propose a new metric (Position
Dependent Model) for measuring similarity between two
call stacks.
g120 We evaluate our approach on five widely-used Microsoft
products.
The remainder of this paper is organized as follows: We
introduce the background information in Section II. Section III
describes the existing crash bucketing method used in
Microsoft and its limitations. Section IV describes our
proposed bucketing method ReBucket. Section V presents our
experimental design and Section VI shows the experimental
results. We discuss the application of ReBucket in practice in
Section VII and threats to validity in Section VIII. Section IX
surveys related work followed by Section X that concludes this
paper.
II. BACKGROUND
A. The Windows Error Reporting System
Although development teams spend much resource and
effort on software testing before releasing products, in reality,
released software still contains bugs [26]. Some bugs manifest
as crashes in the field.
Because of the wide deployment of Microsoft Windows
systems and the large number of Windows applications
including third-party applications, the volume of crash reports
becomes overwhelming. To automatically collect crash
information from the field, Microsoft deployed a distributed
system called Windows Error Reporting (WER) [10]. When a
crash happens on a client’s Windows platform, the WER
system collects the crash information (including
application/module name, application/module version, and the
call stack trace). The crash information is reported to a WER
server after user permission is obtained. The server then checks
the duplication of the crash report and classifies it into a bucket.
Each bucket is a collection of crash reports that are likely
caused by the same bug. A new bucket is created if the crash
report is considered a new one. Finally, WER automatically
generates bug reports for highly hit buckets and presents them
to developers.
Figure 1. An overview of crash reporting system
WER has proven its value to Microsoft development teams
[10]. During its ten years of operation, it has collected billions
of crash reports. These crash reports have helped developers
diagnose problems. For example, the Windows Vista team
found and fixed over 5,000 bugs isolated by WER in the beta
release of Vista alone.
B. Crash Call Stack
The call stack is part of crash information collected by
WER at the client side. It plays an important role in
understanding a crash. A call stack consists of a list of ordered
frames, which are recorded at the time of crash. A frame. in a
call stack consists of a module name and a function name,
representing a function call or procedure.
Table I shows an example of crash call stack. There are 7
frames in the call stack, with the most recently executed
function at the top and the least recently executed at the bottom.
The ordered sequence for each frame. indicates the invoking
relationship between frames. For example, the crashed function
at level 0 (QuickSort) is the top frame, which is invoked by the
function at level 1 (MyProgram::SearchRightPart).Often, one
bug could cause different crash stack traces because of the
different execution scenarios.
Table I. An example of crash call stack
Frame. Level Module Function
0 SORT.DLL QuickSort
1 FINDPOINT.DLL MyProgram::SearchRightPart
2 FINDPOINT.DLL MyProgram::DivideAndConquer
3 FINDPOINT.DLL MyProgram::SearchLeftPart
4 FINDPOINT.DLL MyProgram::DivideAndConquer
5 FINDPOINT.DLL FindPoint
6 MYPROGRAM.DLL MyMain
III. THE EXISTING BUCKETING METHOD IN WER
For widely used systems, developers could face a large
number of crash reports sent from users all over the world.
Many of these crash reports are actually caused by the same
bug and are therefore duplicates. To help developers reduce
debugging efforts, it is important to automatically organize
duplicate crash reports into one group after receiving a large
number of crash reports.
In WER, the process of organizing crash reports is named
Bucketing [10]. For each bucket, WER counts the occurrence
of crashes (i.e., the number of hits). Once the crash occurrence
for a bucket exceeds a threshold, a bug report will be generated
for this bucket and will be presented to developers. Developers
can also prioritize the bug fixing efforts based on the number of
crash reports received in each bucket. A bucket with a higher
number of hits will be investigated with higher priority
compared to a bucket with lower hits. Therefore, WER helps
focus the effort on the bugs that have a bigger impact on the
users.
WER has implemented more than 500 bucketing heuristics.
Some of the top heuristics include “L7: include offset of
crashing instruction in faulty module”, “L4: include faulty
module name”, “C14: Identify known faulty device”, and “C12:
Known out-of-date program” [10].
Ideally, the bucketing algorithm should organize all the
crash reports caused by the same bug into one unique bucket.
However, in some scenarios, the WER bucketing heuristics
may assign crash reports caused by the same bug to multiple
buckets (the “second-bucket” problem [10]). It is reported that
for products such as PowerPoint 2010, 30.6% reports are
assigned to a second bucket other than the primary bucket for a
bug [10]. In such cases, the accuracy of bucketing is hampered
because the bucket contains crash reports that are actually
caused by different bugs.
Our empirical studies also find that the existing WER
bucketing method can result in the “long tail” problem. That is,
it could produce a large number of small buckets (i.e., buckets
that contains a small number of crash reports). Experiences
have shown that a bug for a popular system can be always
encountered by many users. Therefore, the “long tail”
phenomenon indicates the existence of problematic buckets.
WER may assign crash reports caused by the same bug to some
“long tail” buckets due to the different manifestations of the
bug in different hardware and software settings. Figure 2
illustrates the “long tail” problem for the MS Publisher project
(release 12 RTM). Around 87.26% buckets contain only 20%
of the hits, while 12.7% buckets contain 80% of the hits. The
“long tail” phenomenon is a general case of the “one-hit
wonders” problem identified by the WER designers [10]). The
“one-hit wonders” are buckets that contain exactly one crash
report. In [10], the authors reported that for products such as
Outlook 2010, 10% buckets are “one-hit wonders”. The
existence of the “long tail” behavior. and its special case “one-
hit wonders” may cause misunderstanding of the severity of
crashes and thus wrong prioritization.
Distance to Crash Point for f4:4
Distance to Crash Point for f6':6
Alignment Offset between
f4 and f6' : 2
Matched Frame
Other Frame.
Figure 4. Illustration of call stack metrics
Figure 4 illustrates the above concepts. For both call stacks
C1 and C2, the crash point is at the top frame. The C1 functions
f0, f1 and f4 match the C2 functions f0’, f2’ and f6’, respectively.
For the f4 function in C1, its distance to the top frame. is 4. The
distance to the top frame. for f6’ in call stack C2 is 6. The
alignment offset between the two functions is measured by the
difference in their distances to the top frame. Since the distance
to the top frame. for f4 and f6’ is 4 and 6 respectively, the
alignment offset is 2.
2) The Position Dependent Model
Basically, if two call stacks belong to the same bug, they
are more likely to be similar. In this subsection, we introduce