Flux Research Group / School of Computing

Test-Case Reduction for C Compiler Bugs

John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang

Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) 2012.

DOI: 10.1145/2254064.2254104

Award paper.

areas
Languages, Software Testing

abstract

To report a compiler bug, one must often find a small test case that triggers the bug.  The existing approach to automated test-case reduction, delta debugging, works by removing substrings of the original input; the result is a concatenation of substrings that delta cannot remove.  We have found this approach less than ideal for reducing C programs because it typically yields test cases that are too large or even invalid (relying on undefined behavior).  To obtain small and valid test cases consistently, we designed and implemented three new, domain-specific test-case reducers.  The best of these is based on a novel framework in which a generic fixpoint computation invokes modular transformations that perform reduction operations.  This reducer produces outputs that are, on average, more than 25 times smaller than those produced by our other reducers or by the existing reducer that is most commonly used by compiler developers.  We conclude that effective program reduction requires more than straightforward delta debugging.