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:
- Structural Extraction: The parser identifies high-level control-flow statements (e.g.,
if,while,for) while treating irrelevant features, such asstructdefinitions or complex declarations, as terminal "wildcards." - 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