Randomly generated programs are popular for testing compilers and program analysis tools, with hundreds of bugs in real-world C compilers found by random testing. However, existing random program generators may generate large amounts of dead code (computations whose result is never used). This leaves relatively little code to exercise a target compiler's more complex optimizations. To address this shortcoming, we introduce liveness-driven random program generation. In this approach the random program is constructed bottom-up, guided by a simultaneous structural data-flow analysis to ensure that the generator never generates dead code. The algorithm is implemented as a plugin for the Frama-C framework. We evaluate it in comparison to Csmith, the standard random C program generator. Our tool generates programs that compile to more machine code with a more complex instruction mix.
The best-known random program generator is Csmith @cite_15 , based on an earlier system called randprog @cite_13 @cite_9 . Csmith generates complete, self-contained programs that take all their input from initialized global variables and compute an output consisting of a hash over the values of all global variables at the end of execution. The generator is designed to only generate programs with well-defined semantics: Operations that may be undefined in C, such as overflowing signed integer arithmetic, are guarded by conditionals that exclude undefined cases (these guards can be disabled, and we disabled them for the experiments reported above). Like , Csmith performs data-flow analysis during generation, although the details differ due to the differing design goals. Csmith's forward analysis computes points-to facts and uses them for safety checks. If the checks fail, Csmith backtracks, deleting code it generated until a safe state is reached again. In contrast, 's data-flow analysis only deals with liveness, and never backtracks: Full liveness of variables in loops is ensured by construction. Csmith generates a larger subset of C than current or currently planned versions of , including unstructured control flow and less restricted use of pointers.
@cite_9 @cite_15 @cite_13
2098456636 2096698236
Compilers should be correct. To improve the quality of C compilers, we created Csmith, a randomized test-case generation tool, and spent three years using it to find compiler bugs. During this period we reported more than 325 previously unknown bugs to compiler developers. Every compiler we tested was found to crash and also to silently generate wrong code when presented with valid input. In this paper we present our compiler-testing tool and the results of our bug-hunting study. Our first contribution is to advance the state of the art in compiler testing. Unlike previous tools, Csmith generates programs that cover a large subset of C while avoiding the undefined and unspecified behaviors that would destroy its ability to automatically find wrong-code bugs. Our second contribution is a collection of qualitative and quantitative results about the bugs we have found in open-source C compilers. C's volatile qualifier is intended to provide a reliable link between operations at the source-code level and operations at the memory-system level. We tested thirteen production-quality C compilers and, for each, found situations in which the compiler generated incorrect code for accessing volatile variables. This result is disturbing because it implies that embedded software and operating systems---both typically coded in C, both being bases for many mission-critical and safety-critical applications, and both relying on the correct translation of volatiles---may be being miscompiled. Our contribution is centered on a novel technique for finding volatile bugs and a novel technique for working around them. First, we present access summary testing: an efficient, practical, and automatic way to detect code-generation errors related to the volatile qualifier. We have found a number of compiler bugs by performing access summary testing on randomly generated C programs. Some of these bugs have been confirmed and fixed by compiler developers. Second, we present and evaluate a workaround for the compiler defects we discovered. In 96 of the cases in which one of our randomly generated programs is miscompiled, we can cause the faulty C compiler to produce correctly behaving code by applying a straightforward source-level transformation to the test program.