Software QA FYI - SQAFYI

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/

Finding Bugs is Easy