Re: [gsoc] syscall/libc fuzzer proposal

[Mateusz Kocielski <m.kocielski%gmail.com@localhost>]

2010/3/20 Thor Lancelot Simon <tls%panix.com@localhost>:
> What is the benefit of this when compared to existing static-analysis
> tools such as Coverity Scan, splint, or the Clang static analyzer?  Will
> this cover any cases they don't?  If so, which ones?

Undecidability is the limit for static-analysis. Consider following program:

*bzzzz*
$ cat splint.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv)
{
        int i;
        char blah[10];
        memset(blah, 0, sizeof(blah));
        if ( argc > 1 )
                i = atoi(argv[1]);
        else
                i = 0;
        printf("%d - %c\n", i, blah[i]);
        return 0;
}
$ splint splint.c
Splint 3.1.2 --- 07 Sep 2009
Finished checking --- no warnings
$ ./splint 99
99 - 1
*bzzzz*

Static analysis used in splint is not strong enough to uncover bug.
For sure there exists static analysis which is able to find this bug,
but it might be a good subject for PhD thesis. :)

We will put splint.c through our translator and receive something like
this (assert is just an example, additional lines has got //T
comments):

*bzzzz*
$ cat translated.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

int main(int argc, char **argv)
{
        int j; // T
        int i;
        char blah[10];
        memset(blah, 0, sizeof(blah));
        if ( argc > 1 )
                i = atoi(argv[1]);
        else
                i = 0;  
        j = i; // T
        assert ( j >= 0 && j < 10 ); // T
        printf("%d - %c", i, blah[j]);
        return 0;
}
$ ./translated 99
translated: translated.c:20: main: Assertion `j >= 0 && j < 10' failed.
Przerwane (Aborted)
*bzzzz*

My example is a bit tendentious and trivial, but it shows that
transforming programs by adding there
assertions/bound-checkers/whatever can support fuzz testing to uncover
some bugs.

-- 
Mateusz Kocielski