C-Reduce

C-Reduce is a tool which takes a large C or C++ program that has a property of interest (such as triggering a compiler bug) and automatically produces a much smaller C/C++ program that has the same property. It is intended for use by people who discover and report bugs in compilers and other tools that process C/C++ code.

Publications and Presentations

Test-Case Reduction for C Compiler Bugs. John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang.
In Proceedings of 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2012), Beijing, China, June 2012.
slides from John's talk at PLDI 2012

Design

C-Reduce is structured as a fixpoint computation that calls a collection of plugins. It is these plugins that actually transform the test case that is being reduced. C-Reduce is thus very easy to improve and extend. In particular, we believe it would be quite easy to add passes for reducing other programming languages.

Source Code

C-Reduce 2.0.1, released in June 2012, is the current version
the current development version of C-Reduce is on Github

Installing C-Reduce

Please see our INSTALL file.

C-Reduce has been tested on MacOS X, FreeBSD, and several versions of Linux.

Precompiled clang_delta Binaries

(Experimental.) As described in the INSTALL instructions, compiling C-Reduce and its clang_delta tool requires one to install appropriate versions of LLVM and Clang. For those who do not want to compile clang_delta themselves, we offer binaries compiled for selected platforms:

clang_delta for C-Reduce 2.0.0, compiled for Ubuntu 12.04, x86-64

Note that the above files do not contain the creduce driver script, which is currently found in the source-code distributions only. We are exploring better ways to provide complete, precompiled distributions of C-Reduce in the near future.

Using C-Reduce

Run:

creduce ./test1.sh file.c

Where file.c is a C compilation unit that you wish to reduce and test1.sh is a shell script that returns 0 if a partially reduced C program (a "variant") is interesting and non-zero otherwise. The test script takes no arguments; it should be hard-coded to refer to the same C file that is passed as an argument to C-Reduce.

For more details, please see Using C-Reduce.

Related Tools

Delta is an excellent test-case reducer that inspired us to create C-Reduce. Delta is easier to install than C-Reduce and also it is not as domain-specific. On the other hand, C-Reduce generally produces outputs that are considerably smaller than Delta's.
Csmith is a random C program generator that has been used to find a large number of compiler bugs. The requirement to reduce Csmith programs that trigger compiler bugs was the reason we created C-Reduce.
We built two more reducers—Seq-Reduce and Fast-Reduce—that are described in our PLDI paper, but for which we have not written documentation. The former can be downloaded as part of the Csmith sources; the latter is not yet available but will be soon. We recommend that people use C-Reduce instead of these other tools.

Current Projects

We are:

Continuing to improve C++ support. If you find C-Reduce to not work very well for reducing C++ programs, please send us a note including a test case.
Making C-Reduce run faster.
Making C-Reduce support obfuscation as well a reduction. Our goal is for users to be able to start with a proprietary or classified piece of code, reduce it, and end up with output that can be declassified or that does not need to be considered to be proprietary.

Future Projects

If there is demand we might:

Add support for reducing inputs in languages other than C and C++.
Parallelize C-Reduce.
Support reducing a collection of files (C-Reduce currently attacks a single compilation unit at a time).

If you would find these (or other) features useful, please let us know.

Feedback

If you find C-Reduce to be useful, please let us know. If it does not work, please let us know about that too. There are two mailing lists:

creduce-dev@flux.utah.edu for general discussion on C-Reduce [subscribe] [list info] [archive]
creduce-bugs@flux.utah.edu for reporting bugs in C-Reduce [list info] [archive]