The Quest Compiler Tester

Quest generates C code that can uncover bugs in a C compiler. The generated code passes complex arguments between functions and thus tests the translation of function calls. This part of a compiler is hard to test with real-world code because complex functions calls are rare. Not totally surprising, Quest uncovered bugs in production-quality compilers. As such, Quest is most interesting for compiler writers.

Below is a test case generated by Quest. It declares complex types and passes values of that type to a function. The function uses assertions to check that values are received correctly. Likewise, the function returns a value which is checked by the caller. If the compiler's calling convention is buggy, executing the test case will result in an assertion failure.

static double b9 = 96927.18;
static struct bt0 { float b0; double b1; int b2; signed b3:10; int b4; double b5; }
    b10 = {20038.31, 24833.79, 2062266516, 292, 922971318, 10058.10};
static union bt1 { float b6; unsigned short int b7; unsigned long int b8; } 
    b11 = {82793.36};
static unsigned char *b12 = (unsigned char *) 1337037880U;
static float b13[1] = {82195.76};

double callee_b0f(struct bt0 bp4, union bt1 bp5, unsigned char *bp6, float bp7[1])
{
    QUEST_ASSERT(b10.b0 == bp4.b0);
    QUEST_ASSERT(b10.b1 == bp4.b1);
    QUEST_ASSERT(b10.b2 == bp4.b2);
    QUEST_ASSERT(b10.b3 == bp4.b3);
    QUEST_ASSERT(b10.b4 == bp4.b4);
    QUEST_ASSERT(b10.b5 == bp4.b5);
    QUEST_ASSERT(b11.b6 == bp5.b6);
    QUEST_ASSERT(b12 == bp6);
    QUEST_ASSERT(b13[0] == bp7[0]);
    return b9;
}

static void caller_b1f()
{
    double b14; 

    b14 = callee_b0f(b10, b11, b12, b13);
    QUEST_ASSERT(b9 == b14);
}

Generating test cases using Quest is easy: no specification of any kind is necessary. Just let Quest generate code, compile it, and see what happens. It is as easy as the following few lines of Shell code:

while true; do
  quest -test gcc > bug.c
   gcc -o bug bug.c || break
    ./bug || break
done

If the generated code detects a bug it emits a message to standard out and returns a positive exit code. This causes the break command to exit the loop.

The generation of test cases is controlled by the built-in scripting language Lua. A user may modify the provided test-case generators and add new ones. Test cases are built from generators which can be combined in an algebraic fashion.

Using Lua it is easy to provide a customized generator, for example a generator that does not use floating-point arguments and does not use var args or unions. This helps to generate code for embedded systems.

Quest can split test cases into two files such that the files may be compiled with different compilers. This permits to test the interoperability of compilers.

Download

Source Code

Quest is implemented in Objective Caml and compiles on Unix systems. It comes with a configure script and a ManualPage. The source (source:trunk) code is available via subversion:

svn checkout http://quest-tester.googlecode.com/svn/trunk/ quest

The source is a Noweb literate program. However, you don't need literate programming tools to compile it unless you intend to work on the source code. On Debian Noweb is available as package nowebm.

Binaries

Objective Caml can generate binaries for most common platforms, including Linux, Mac OS X, and Windows. Please contact me if you need a binary.

Documentation

Quest comes with a ManualPage that explains its usage. Quest is driven by a built-in interpreter for the language Lua; a manual for Lua 2.5 is included in the distribution (source:trunk/doc/lua-2.5.pdf). A paper Random Testing of C Calling Conventions explains why and how Quest works. It was presented at AADEBUG 2005.

Some Bugs Found in GCC

Copyright

Quest is released under a BSD-style license that is part of the ManualPage. Note that Quest includes some software that is licensed under other (more permissive) licenses.

Author

Christian Lindig <lindig at cs.uni-sb.de>, http://www.st.cs.uni-sb.de/~lindig/