XCheck: a Simple, Effective and Extensible Bug Finder using micro-grammar

Hanwen Zhu, Junyoung Jang, Xujie SiarXiv 2021 · arXiv · OpenReview

Abstract

Static analysis tools for large-scale software often struggle with the trade-off between precision and complexity. Traditional whitebox methods suffer from path explosion, while blackbox methods require extensive test generation. XCheck introduces a "cheap-and-effective" alternative by utilizing micro-grammars to parse only the bug-relevant portions of source code. By abstracting away language-specific complexities, XCheck provides a portable, lightweight framework capable of identifying logical errors and null-pointer dereferences across C, C++, and Java. Evaluation on the Linux kernel, OpenJDK, and LLVM demonstrates that XCheck can find real-world bugs and correct errors in previous research with only a few hundred lines of code.

1. Introduction

Finding bugs in massive software systems remains a significant challenge in software engineering. Existing approaches generally fall into two categories: whitebox testing (e.g., symbolic execution) and blackbox testing (e.g., fuzzing). Whitebox methods are computationally expensive due to the need for precise semantic modeling, while blackbox methods require complex environments to execute generated test cases. Both are typically tied to specific programming languages, requiring significant effort to port to new environments.

XCheck addresses these limitations by adopting a "micro-grammar" approach. Instead of attempting to understand the full syntax and semantics of a language, XCheck focuses on high-level patterns common across multiple languages. This allows for a tool that is simple, fast, and easily extensible.

2. Methodology: The Power of Micro-Grammars

XCheck is implemented in Haskell using the Parsec library. Its core innovation lies in the use of a partial Abstract Syntax Tree (AST) based on micro-grammars—a concept that prioritizes parsing only the structures necessary for bug detection.

2.1 Two-Step Parsing

The framework employs a two-step parsing process to handle code efficiently:

  1. Structural Extraction: The parser identifies high-level control-flow statements (e.g., if, while, for) while treating irrelevant features, such as struct definitions or complex declarations, as terminal "wildcards."
  2. Logic Refinement: A secondary expression parser targets these wildcards to extract the specific logic where bugs are likely to reside.

This sliding-window technique allows XCheck to skip unparseable or irrelevant code blocks, making it resilient to the idiosyncrasies of different compiler frontends.

2.2 Composable Checkers

XCheck includes four initial checkers designed to identify common error patterns:

  • Redundant Logical Conditions: Identifying tautologies or contradictions in logic.
  • Redundant Branches: Detecting code paths that can never be executed or are identical to others.
  • Suspicious Loop Conditions: Finding errors such as loops that increment a counter but check against an incorrect boundary.
  • Null Pointer Dereferencing: Tracking pointer usage to find potential crashes.

3. Evaluation

To test the effectiveness and portability of XCheck, the authors applied it to three major open-source projects:

  • Linux 5.15 (C): A massive codebase with complex pointer arithmetic and low-level logic.
  • OpenJDK 8 (Java): A high-level object-oriented environment.
  • LLVM 3.5.1 (C++): A complex system utilizing modern C++ features.

Porting the tool between these languages proved remarkably simple. For instance, adapting the null-pointer checker from C++ to Java required only changing the dereference token from -> to ..

4. Results and Insights

XCheck successfully identified real-world bugs in both OpenJDK (CipherCore.java) and LLVM (InstCombineAddSub.cpp). Beyond finding new bugs, XCheck served as a valuable tool for replication.

A notable result occurred during the analysis of the Linux kernel's object.c. A previous 2016 study using a proprietary micro-grammar tool had flagged a specific line as a bug. However, XCheck did not flag it. Manual verification confirmed that XCheck was correct: the variable in question (state->work) was reassigned before the null check, a detail the previous tool had missed. This highlights XCheck’s superior logic tracking despite its minimal codebase.

5. Conclusion and Future Work

XCheck demonstrates that effective static analysis does not require massive, language-specific infrastructure. By focusing on micro-grammars, the tool achieves high portability and speed with only a few hundred lines of Haskell code.

While currently optimized for C-style languages, future work will focus on expanding XCheck’s reach to structurally different languages like Python. The authors also plan to implement more sophisticated checkers and refine the sliding-window parsing technique to further improve robustness.

Summary updated

BibTeX
@misc{zhu2021xcheck,
  author = {Hanwen Zhu and Junyoung Jang and Xujie Si},
  title = {{XCheck: a Simple, Effective and Extensible Bug Finder using micro-grammar}},
  year = {2021},
  eprint = {2112.08010},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.08010},
}
Figure