|
Finding Bugs is Easy
By: David Hovemeyer and William Pugh
ABSTRACT
Many techniques have been developed over the years to automatically
find bugs in software. Often, these techniques
rely on formal methods and sophisticated program analysis.
While these techniques are valuable, they can be difficult to
apply, and they aren’t always effective in finding real bugs.
Bug patterns are code idioms that are often errors. We have
implemented automatic detectors for a variety of bug patterns
found in Java programs. In this paper, we describe
how we have used bug pattern detectors to find real bugs in
several real-world Java applications and libraries. We have
found that the effort required to implement a bug pattern
detector tends to be low, and that even extremely simple
detectors find bugs in real applications.
From our experience applying bug pattern detectors to real
programs, we have drawn several interesting conclusions.
First, we have found that even well tested code written
by experts contains a surprising number of obvious bugs.
Second, Java (and similar languages) have many language
features and APIs which are prone to misuse. Finally, that
simple automatic techniques can be effective at countering
the impact of both ordinary mistakes and misunderstood
language features.
1. INTRODUCTION
Few people who develop or use software will need to be
convinced that bugs are a serious problem. Much recent research
(e.g., [7, 14, 16, 28, 3, 6, 26, 17, 13]) has been devoted
to developing techniques to automatically find bugs in software.
Many of these techniques use sophisticated analyses
and powerful formalisms.
Our approach to finding bugs is different: we have concentrated
on using simple, broad techniques rather than
focused, narrow techniques. The principle underlying our
work is that we start by looking at actual bugs in real code,
and then develop ways to find similar bugs. Our goal has
been to better understand what kind of bugs exist in software,
rather than advancing the state of the art in program
analysis. From this work, we have reached some interesting
and sometimes unexpected conclusions.
First, no type of bug has been so “dumb” or “obvious” that
we have failed to find examples of it in real code. Every bug
detector we have ever implemented has found real bugs. We
have been continually suprised by the obviousness of the
bugs found using our detectors, even in production applications
and libraries.
Second, because of the sheer complexity of modern objectoriented
languages like Java, the potential for misuse of language
features and APIs is enormous. From our experience
we have concluded that even experienced developers have
significant gaps in their knowledge which result in bugs.
Third, that automatic bug detection tools can serve an important
role in raising the awareness of developers about
subtle correctness issues. So, in addition to finding existing
bugs, they can help prevent future bugs.
In this paper we will describe some of the bug detection techniques
we have used, and present empirical results showing
the effectiveness of these techniques on real programs. We
will also show examples of bugs we have found to help illustrate
how and why bugs are introduced into software,
and why commonly used quality assurance practices such as
testing and code reviews miss many important bugs.
The structure of the rest of the paper is as follows. In Section
2, we discuss the general problem of using automatic
techniques to find bugs in software, and describe a tool,
called FindBugs, which uses bug pattern detectors to inspect
software for potential bugs. In Section 3, we briefly describe
the implementation of our tool and some of its features. In
Section 4, we evaluate the effectiveness of our bug pattern
detectors on several real programs. In Section 5, we offer
observations from our experiences and some of our users’
experiences putting bug pattern detection into practice. In
Section 6, we describe related work. In Section 7 we offer
some conclusions, and describe possibilities for future work.
2. TECHNIQUES FOR FINDING BUGS
There are many possible ways to find bugs in software. Dynamic
techniques, such as testing and assertions, rely on the
runtime behavior of a program. As such, they are limited to finding bugs in the program paths that are actually executed.
In contrast, static techniques can explore abstractions
of all possible program behaviors, and thus are not
limited by the quality of test cases in order to be effective.
Static techniques range in their complexity and their ability
to identify or eliminate bugs. The most effective (and complex)
static technique for eliminating bugs is a formal proof
of correctness. While the existence of a correctness proof is
the best guarantee that the program does not contain bugs,
the difficulty in constructing such a proof is prohibitive for
most programs. Partial verification techniques have been
proposed. These techniques prove that some desired property
of a program holds for all possible executions. Such
techniques may be complete or incomplete; if incomplete,
then the analysis may be unable to prove that the desired
property holds for some correct programs. Finally, unsound
techniques can identify “probable” bugs, but may produce
false positives and false negatives.
We have implemented a static analysis tool, called Find-
Bugs, that detects instances of bug patterns in Java programs.
Bug patterns are code idioms that are likely to
be errors. We have implemented (unsound) detectors for
a variety of common bug patterns, and used them to find
a significant number of bugs in real-world applications and
libraries. In this section we describe the bug patterns we
detect, and how we implemented and refined detectors for
those patterns.
2.1 Bug Patterns
Bug patterns are error-prone coding practices that arise from
the use of erroneous design patterns, misunderstanding of
language semantics, or simple and common mistakes. As
developers, we tend to believe that any bugs in our code
must be subtle, unique and require sophisticated tools to
uncover. However, our experience has shown that while subtle
and unique bugs exist, there are also many errors, even
in production code, that are blatant, well-understood, and
easy to find if you know what to look for. Finding these
errors does not require sophisticated or expensive forms of
analysis or instrumentation. Many of these errors can be
found with trivial static examination, using what we refer
to as a bug pattern detector.
Bug pattern detectors are not judged by whether they are
“right” or “wrong” in any formal correctness point of view.
Rather, they are either effective or ineffective at finding real
bugs in real software. Useful bug pattern detectors can only
be developed in tandem with continual application and evaluation
of their usefulness in finding bugs in software artifacts.
The bug patterns we look for have come from a wide range of
sources. Many of the bug patterns are suggested by Java semantics.
A simple example is that it is generally an error to
dereference a null pointer. A number of books ([1, 27, 5, 19,
9]) describe potential Java coding pitfalls. Several of the bug
patterns we implemented in FindBugs were observed in student
projects in an undergraduate advanced programming
course at the University of Maryland. We have implemented
detectors for several bug patterns suggested by users of our
analysis tool. In general, bug patterns are found through the
process of software development, through the simple observation
that bugs often have common characteristics. Whenever
a bug is fixed, it is worth looking for other places in
the code where a similar bug might be lurking. Bug pattern
detectors put this idea into practice.
Full article...
Other Resource
... to read more articles, visit http://sqa.fyicenter.com/art/
|