Finding bugs is easy
Published 23 October 2004
David Hovemeyer, William Pugh
Citations775
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is found that even well tested code written by experts contains a surprising number of obvious bugs and that simple automatic techniques can be effective at countering the impact of both ordinary mistakes and misunderstood language features.
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.
Keywords
Computer Science
Extended static checking for Java
1,339 Citations2002Cormac Flanagan, K. Rustan M. Leino +4 more
The Extended Static Checker for Java (ESC/Java) is introduced, an experimental compile-time program checker that finds common programming errors and provides programmers with a simple annotation language with which programmer design decisions can be expressed formally.
IEEE Transactions on Software EngineeringDynamically discovering likely program invariants to support program evolution
1,039 Citations2001Michael D. Ernst, Jake Cockrell +2 more
The S <scp>LAM</scp> project
919 Citations2002Thomas Ball, Sriram K. Rajamani
This work has successfully applied the SLAM toolkit to Windows XP device drivers, to both validate behavior and find defects in their usage of kernel APIs.
An empirical study of operating systems errors
718 Citations2001Andy Chou, Junfeng Yang +3 more
A study of operating system errors found by automatic, static, compiler analysis applied to the Linux and OpenBSD kernels found that device drivers have error rates up to three to seven times higher than the rest of the kernel.
Tracking down software bugs using automatic anomaly detection
607 Citations2002Sudheendra Hangal, Monica S. Lam
The DIDUCE system for Java programs is implemented and applied and suggests that detecting and checking program invariants dynamically is a simple and effective methodology for debugging many different kinds of program errors across a wide variety of application domains.
ESP
544 Citations2002Manuvir Das, Sorin Lerner +1 more
This paper presents a new algorithm for partial program verification that runs in polynomial time and space, and shows that property simulation scales to large programs and is accurate enough to verify meaningful properties.
Defense Technical Information Center (DTIC)Checking system rules using system-specific, programmer-written compiler extensions
543 Citations2000Dawson Engler, Benjamin Chelf +2 more
Software Practice and ExperienceA static analyzer for finding dynamic programming errors
508 Citations2000William R. Bush, Jonathan D. Pincus +1 more
A compile‐time analyzer that detects dynamic errors in large, real‐world programs, and provides valuable contextual information to the programmer who needs to understand and repair the defects.
Efficient and precise datarace detection for multithreaded object-oriented programs
440 Citations2002Jong-Deok Choi, Keun‐Woo Lee +4 more
This work presents a novel approach to dynamic datarace detection for multithreaded object-oriented programs that results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise.
ACM SIGPLAN NoticesFinding bugs is easy
391 Citations2004David Hovemeyer, William Pugh
It is 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.
Flow-sensitive type qualifiers
377 Citations2002Jeffrey S. Foster, Tachio Terauchi +1 more
An efficient constraint-based inference algorithm is obtained that integrates flow-insensitive alias analysis, effect inference, and ideas from linear type systems to support strong updates.
Detecting format string vulnerabilities with type qualifiers
359 Citations2001Umesh Shankar, Kunal Talwar +2 more
A system and language for building system-specific, static analyses
352 Citations2002Seth Hallem, Benjamin Chelf +2 more
A flexible, easy-to-use extension language for specifying analyses and an efficent algorithm for executing these extensions, which believe is an effective framework for deploying new bug-finding analyses quickly and easily.
A Comparison of Bug Finding Tools for Java
275 Citations2005Nick Rutar, Christian Butiu Almazan +1 more
This paper applies five bug finding tools, specifically Bandera, ESC/Java 2, FindBugs, JLint, and PMD, to a variety of Java programs, and proposes a meta-tool that combines the output of the tools together, looking for particular lines of code, methods, and classes that many tools warn about.
Lint, a C Program Checker
266 Citations1978S. C. Johnson, Murray Hill
This document discusses the use of lint, gives an overview of the implementa- tion, and gives some hints on the writing of machine independent C code.
A theory of type qualifiers
263 Citations1999Jeffrey S. Foster, Manuel Fähndrich +1 more
A framework for adding type qualifiers to a language that extends standard type rules to model the flow of qualifiers through a program, where each qualifier or set of qualifiers comes with additional rules that capture its semantics.
Effective Java Programming Language Guide
244 Citations2001Joshua Bloch
LCLint
233 Citations1994David Evans, John V. Guttag +2 more
An efficient and flexible tool that accepts as input programs (written in ANSI C) and various levels of formal specification and using this information, LCLint reports inconsistencies between a program and its specification.
Using programmer-written compiler extensions to catch security holes
204 Citations2005Ken Ashcraft, Dawson Engler
ASTLOG: a language for examining abstract syntax trees
120 Citations1997Roger F. Crew
A Prolog variant is developed that avoids the overhead of translating the source syntactic structures into the form of a Prolog database, thus retaining an important feature without entailing that the database be dynamically extensible as the usual implementation does.
Applying static analysis to large-scale, multi-threaded Java programs
82 Citations2002Cyrille Artho, Armin Biere
Applying Jlint2 to various large software packages, including commercial packages from Trilogy, found 12 faults, two of which related to multi-threading, and the statistical analysis proves that these extensions are relevant and useful.
Double-Checked Locking An Optimization Pattern for Efficiently Initializing and Accessing Thread-safe Objects
51 Citations1998Douglas C. Schmidt, Tim Harrison
First MondayThe International Children's Digital Library: Description and analysis of first use
51 Citations2003Allison Druin, Benjamin B. Bederson +11 more
The first version of the International Children's Digital Library is presented and an initial analysis of the first seven weeks of the ICDL's public use on the Web is presented.
Parametric regular path queries
49 Citations2004Yanhong A. Liu, Tom Rothamel +3 more
The paper describes the specification, design, analysis, and implementation of algorithms and data structures for efficiently solving existential and universal parametric regular path queries, and investigates the efficiency tradeoffs between different formulations of queries.
Finding Concurrency Bugs in Java
37 Citations2004David Hovemeyer
Simple analysis techniques that are effective at finding concurrency errors in real programs are described and evidence that threads and concurrency are widely misused in Java is provided, even in programs written by experienced programmers is provided.
Using redundancies to find errors
36 Citations2002Yichen Xie, Dawson Engler
Bug Patterns in Java
28 Citations2002Eric E. Allen
"Bug Patterns in Java" presents a methodology for diagnosing and debugging computer programs, and argues that testing and debugging, while often conflated, are properly considered to be distinct tasks.
Bitter Java
17 Citations2002Bruce Tate
Bitter Java illustrates common pitfalls of Java programming though code examples; it then presents refactored code and explains why the new solutions are safe and how to recognize when you are lost and get back on the right path.
MJ - A System for Constructing Bug-Finding Analyses for Java
11 Citations2003Godmar Back, Dawson Engler
This work has implemented and tested several extensions in MJ for both general and application-specific rules, and its checkers have found dozens of bugs in some widely-deployed and mature software systems.
