Using DeepState makes graybox concolic much less effective.

[agroce]

The ICSE paper's example works great as a simple C program, but when I try to fuzz the same logic using DeepState (https://github.com/trailofbits/deepstate), it doesn't work. Graybox concolic testing of DeepState examples doesn't seem to work well, and produces surprisingly few interesting paths.

https://github.com/agroce/tryeclipser has some versions of the code. vulnmix avoids DeepState's more complex parsing of an input file, or need to set CLI arguments, and just reads eclipser.input but Eclipser still doesn't find the vulnerability with that approach.

Any ideas what's going on? Obviously with DeepState the time from program start until interesting things start happening based on input is much, much, longer. Be nice to work out what's going on, and if it can be fixed -- we'd love to have Eclipser as a DeepState backend, the approach is very nice, and results are impressive.

root@a621890e86cf:~/tryeclipser# dotnet ~/Eclipser/build/Eclipser.dll fuzz -p ./vulnmix --timelimit 60 --src file --fixfilepath eclipser.input
Fuzz target: /root/tryeclipser/vulnmix
Time: 60 sec
[00:00:00:00] Forkserver for coverage tracer : 95622
[00:00:00:00] Forkserver for branch tracer : 95624
[00:00:00:00] Fuzzing starts
[00:00:00:00] [*] Found by grey-box concolic (655 new nodes) : ("AAAAAAAA") File[0]=( e1* ...7bytes... (0) (Right))
[00:00:00:07] # of seeds before minimization : 2
[00:00:00:07] [*] (Redundant seed) : ("AAAAAAAA") File[0]=( ...8bytes... (0) (Right))
[00:00:00:07] Total 1 redundant seeds found
^C
root@a621890e86cf:~/tryeclipser# dotnet ~/Eclipser/build/Eclipser.dll fuzz -p ./vulnorig --timelimit 60 --src file --fixfilepath eclipser.input --initarg "eclipser.input"
Fuzz target: /root/tryeclipser/vulnorig
Time: 60 sec
[00:00:00:00] Forkserver for coverage tracer : 10992
[00:00:00:00] Forkserver for branch tracer : 10994
[00:00:00:00] Fuzzing starts
[00:00:00:00] [*] Found by grey-box concolic (225 new nodes) : ("eclipser.input") File[0]=( 34! 3d! ...6bytes... (0) (Right))
[00:00:00:00] Found crash seed : ("eclipser.input") File[0]=( 34! 3d! 00 00 42! 61! 64! 21! (4) (Right))
[00:00:00:00] [*] Found by grey-box concolic (598 new nodes) : ("eclipser.input") File[0]=( 34! 3d! 00 00 42! 61! 64! 21! (4) (Right))
[00:00:00:03] # of seeds before minimization : 2
[00:00:00:03] Total 0 redundant seeds found

[agroce]

(we already added a helpful interface to use DeepState with Eclipser -- it "works" just not very effectively)

deepstate-eclipser <deepstate executable> --timeout <secs> --output_test_dir <output> will run Eclipser with length 8192 input file (DeepState's max input size), right choice of CL arguments, target file, etc., and decode the test cases into DeepState usable-form

[agroce]

I should also note that Eclipser is far from useless, it looks like, even with this. I'm still confirming and comparing results (the original runs were on Mac OS, and I'm running Eclipser in a docker so it's actually facing a big performance penalty) but it looks like Eclipser may beat the libFuzzer results for red black tree fuzzing with DeepState: https://blog.trailofbits.com/2019/01/22/fuzzing-an-api-with-deepstate-part-2

[agroce]

(not to mention libFuzzer is doing in-process fuzzing with compiler-based fast instrumentation, and Eclipser is running the executable with QEMU, so it's really running way fewer tests, likely orders of magnitude)

[agroce]

Actually, never mind: there is a serious problem, and it is making Eclipser not useful with DeepState. I had forgotten to prune the mutants by whether they compile. Eclipser is generating only 5 or so tests for the red black tree, only within the first few seconds of a 1 hour run, and they only kill 38% of mutants, vs. 60%+ for libFuzzer generated corpus

[agroce]

given that's a little bad for even a brute force fuzzer, I am thinking something may be going wrong with the instrumentation/detection of new paths

[jchoi2022]

Hi, I looked into DeepState framework and tried to figure out what is going on.

The problem is that Eclipser currently does not support fuzzing programs with fork(). Eclipser examines the sequence of branch distances to solve linear branches (more details are given in the ICSE paper). Therefore, if multiple processes are executed, this branch distances spawned from different processes will mix up, and grey-box concolic testing will not work as intended. To avoid such mix-up, Eclipser currently abandons child process and just follow parent process when fork() is called. A more principled solution for this problem is to store each processes' sequence of branch distance into separate files. However, this will take some engineering effort.

To circumvent this problem, I fixed https://github.com/trailofbits/deepstate/blob/master/src/lib/DeepState.c#L48 to declare variable 'fork' as false, and recompiled DeepState.

After that, I could confirm that Eclipser could successfully find a crash from 'vulnmix' binary with command dotnet build/Eclipser.dll fuzz -p ./vulnmix --timelimit 10 --src file --fixfilepath eclipser.input. Also, I tested 'vuln' binary with command deepstate-eclipser --output_test_dir out --timeout 10 --seeds ./input --verbose 0 ./vuln and it worked fine, too.

I also tried to run red-black tree library testing in https://github.com/agroce/rb_tree_demo, but in my environment, Eclipser fails to initialize fork server when I used deepstate-eclipser --output_test_dir out --timeout 10 --seeds ./input --verbose 0 ./ds_rb. Am I giving some wrong arguments to 'deepstate-eclipser' or 'ds_rb'? Or should Eclipser work correctly with this command?

[agroce]

Jaeseung, DeepState has a no-fork option, let me see if that works here...

[agroce]

The RB tree is failing for you because you have to remove the sanitizers from the Makefile. Eclipser seems to fail on (at least some) code compiled with ANY sanitizer.

[agroce]

Is the sanitizer thing a known issue? I can check how universal it is...

[agroce]

Hmm. Running everything no-fork is definitely helpful, but also not letting it find the simple example in just a few seconds as it does without DeepState, for me.

[agroce]

What seeds did you use for 'vuln-- I can't get it to fail with either it or vulnMix, though it generates many more tests now with--no_fork`

[agroce]

ok, it does seem to find it, just DeepState doesn't say crashes are crashes quite correctly with --no_fork maybe :)

[agroce]

Fixed DeepState to work with Eclipser correctly, and to properly crash in no-fork mode.