Static analyzers are intended to find bugs in code, and to show that certain kinds of bugs don’t exist. However, static analyzers are themselves large, complicated programs, leading to a “who watches the watchmen” problem. Pascal Cuoq, one of the people behind the excellent Frama-C analyzer, took it upon himself to run the fuzz-fix cycle for Frama-C and Csmith all the way to its fixpoint — where no bugs can be found.
Fuzz testing relies on knowing some invariants for the system under test; often, this is just the trivial “program shouldn’t crash.” Luckily, for compiler testing we can do much better and Pascal did some hacking to turn Frama-C into a (relatively) efficient interpreter for C programs, making it possible to compare Frama-C’s interpretation of a program against regular C compilers.
The aspect of this exercise that I found most interesting was that Frama-C found some nasty bugs in Csmith at the same time that Csmith was finding problems in Frama-C. You might say that Csmith fuzzed itself, but without Frama-C’s deep inspection of the generated programs’ behavior, we couldn’t see the bugs. Recall that Csmith’s key guarantee is that its output is well-defined by the C standard. Frama-C found five bugs where we failed to provide that guarantee.
The bugs found in Frama-C are listed here and more details can be found in a short paper that we (but mainly Pascal) wrote. We hypothesize that random testing would reveal a similar set of issues in other static analysis tools for C. If these tools are being used as part of safety arguments for critical systems, somebody should do this fuzzing.
4 responses to “Randomly Testing a Static Analyzer”
A link to see only the bugs in Frama-C related to Csmith testing:
http://j.mp/csmithbugs
Quick off-topic question:
A tool named “clang_delta” is now called
from c_delta.pl. Is clang_delta available
for download somewhere?
Whoops– fixed in the article, thanks Pascal!
Hi Octoploid- Sorry about that! I’ll commit a fix in a minute that makes c_delta auto-detect whether clang_delta is available.
clang_delta is new and experimental, but works well already. Let me see what I can do to get it out there. Its in our internal SVN now, maybe we should just move it to github.