Inferring project-specific bug patterns for detecting sibling bugs

Guangtai Liang, Qianxiang Wang, Tao Xie, Hong MeiESEC/SIGSOFT FSE 2013 · DOI

TL;DR

This paper introduces a novel approach to detect "sibling bugs" – related bugs that share a common, project-specific pattern. By inferring these project-specific bug patterns (PSBPs) from existing bug fixes, their tool, Sibling-Bug Detector (SBD), can identify previously missed bugs, demonstrating significant complementarity to existing static analysis tools.

What Problem Does This Paper Address?

Traditional static bug detection tools rely on generic bug patterns, often derived from common library usage. However, many bugs arise from patterns specific to a particular project's codebase and its unique object instantiations. Existing tools often fail to catch these "project-specific bug patterns" (PSBPs). When a bug fix addresses only a subset of these related sibling bugs, it results in an incomplete fix, leaving other similar bugs lurking in the code. This paper tackles the challenge of identifying and detecting these overlooked sibling bugs by learning from past fixes.

Methods

The core of the proposed approach is the Sibling-Bug Detector (SBD), which operates in two main phases:

  1. Project-Specific Bug Pattern (PSBP) Inference:
    • Bug-Pattern Templates: The system starts with predefined templates for common bug types (e.g., Null Pointer Exceptions - NPEs, resource leaks). These templates consist of "featured statements" (code changes indicative of a fix) and "usage scenarios" (modeled as Finite State Automata) describing correct and incorrect object usage.
  2. Featured-Statement Identification: Given a fix revision, SBD identifies code changes that match the featured statements in the templates.
  3. Focused-Path Extraction: It then extracts and slices program paths related to the identified featured statements and the "focused object" (the object involved in the bug).
  4. Pattern Generation: By analyzing how the focused object's state transitions along these paths and comparing it to the template's usage scenarios, SBD determines if a bug was indeed fixed. If so, it generates a concrete PSBP by instantiating the template with the project-specific object and its problematic usage.
  5. Sibling-Bug Detection:
    • Program Analysis: SBD performs a flow-sensitive, inter-procedural dataflow analysis on the target project.
  6. PSBP Matching: It matches the inferred PSBPs against the program's control-flow graphs (CFGs) and tracks the usage states of focused objects.
  7. Warning Generation: If an object is found to be in a "buggy" state at the end of a path according to an inferred PSBP, SBD reports a sibling-bug warning.

Datasets

The evaluation was performed on seven popular, well-maintained open-source projects: Lucene, Tomcat, ANT, James, Maven, Xerces, and POI. For evaluation, 50 NPE fix revisions and 50 resource-leak fix revisions were randomly selected from these projects.

Key Insights and Ideas

  • Learning from Fixes: The most significant insight is the power of leveraging existing bug fixes to infer project-specific bug patterns. This shifts from a purely generic pattern-matching approach to a more context-aware, project-tailored analysis.
  • Sibling Bugs are Common: The research highlights that incomplete fixes are prevalent, leading to numerous sibling bugs that traditional tools miss.
  • PSBPs are Crucial: Project-specific bug patterns are essential for accurately detecting bugs that are deeply embedded in a project's unique coding style and object interactions.
  • Complementarity: SBD's strength lies in its ability to find bugs that existing popular tools like FindBugs and PMD miss, suggesting it's a valuable addition to the static analysis toolkit.

Key Results

  • SBD identified a total of 108 sibling-bug warnings across the seven projects.
  • Of these, 19 warnings were already fixed in subsequent historical revisions, confirming their validity.
  • 44 new bug issues were reported to project communities, with 37 of these confirmed or fixed by developers.
  • Overall, at least 58.3% of SBD warnings were confirmed as true bugs.
  • In a comparison with FindBugs and PMD, SBD detected 63 true warnings that these tools collectively missed 58 of (only 5 and 8 respectively were detected by FindBugs and PMD). This demonstrates SBD's high complementarity.

Limitations and Future Work

  • Bug Type Specificity: The current implementation focuses on NPEs and resource leaks. Extending SBD to other bug types (e.g., data races, deadlocks, buffer overflows) is a key area for future work.
  • Bug-Pattern Template Notation: The Finite State Automata (FSA) used for usage scenarios are currently limited to bugs involving a single object. Future work aims to extend this notation to handle bugs involving multiple interacting objects.
  • Template Completeness: The predefined bug-pattern templates are based on manual summarization and may not be exhaustive.
  • External Validity: The representativeness of the selected subject projects and the generalizability of the approach to other bug types are acknowledged threats.
  • Construct Validity: The definition of a "true" warning (based on developer fixes) might be influenced by simple or redundant fixes.

The authors plan to extend SBD to more bug types and improve the bug-pattern template specification notation.

Summary updated

BibTeX
@inproceedings{liang2013inferring,
  author = {Guangtai Liang and Qianxiang Wang and Tao Xie and Hong Mei},
  title = {{Inferring project-specific bug patterns for detecting sibling bugs}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2013},
  doi = {10.1145/2491411.2491422},
}

Loading related content...

Figure