can't find the bug in FourIndependentBranchesTest

[kcc]

Hi,

I've tried Ankou on https://github.com/llvm/llvm-project/blob/master/compiler-rt/test/fuzzer/FourIndependentBranchesTest.cpp and failed to make Ankou find the bug
(unless I provide a very close corpus element).

Am I doing something wrong?
From the Ankou paper I expected that it would shine on this kind of puzzles.

My steps:

# Edit FourIndependentBranchesTest.cpp to replace exit(1) with abort()
afl-gcc -c ~/llvm-project/compiler-rt/lib/fuzzer/standalone/StandaloneFuzzTargetMain.c
afl-g++   ~/llvm-project/compiler-rt/test/fuzzer/FourIndependentBranchesTest.cpp StandaloneFuzzT
argetMain.o 
rm -rf in out
mkdir in out
echo x > in/x

AFL_SKIP_CPUFREQ=1 afl-fuzz -i in -o out ./a.out @@
# AFL doesn't find the bug in ~5 minutes
echo FUZB > in/y  # input similar to the buggy one
AFL_SKIP_CPUFREQ=1 afl-fuzz -i in -o out ./a.out @@
# AFL finds the bug in a few seconds. 

rm in/y                                                             
                                                                                                                                                     
../Ankou -app ./a.out -args "@@" -i in -o out  
                                                                                                                                                                                                                  
Target: a.out                                                                                                                                                                                                     
round number: 632 (10m32s)                                                                                                                                                                                        
len(seedPts) = 9 - throughput: 1.76e+03                                                                                                                                                                           
total unique crashes: 0 - hangs: 1                                                                                                                                                                                
#edges: 24 (0.04%)                                                                                                                                                                                                
                  
<Ankou doesn't find the bug in 10+ minutes>

echo FUZB > in/y  # input similar to the buggy one
../Ankou -app ./a.out -args "@@" -i in -o out  
                                                                                                                                                                                                                  
Target: a.out                                                                                                                                                                                                     
round number: 26 (26s)                                                                                                                                                                                            
len(seedPts) = 12 - throughput: 1.62e+03                                                                                                                                                                          
total unique crashes: 1 - hangs: 1                                                                                                                                                                                
#edges: 25 (0.04%)                                                                                                                                                                                                
<Ankou finds the bug in 20 seconds>                      

 

[Jiliac]

Hello :-)

Thanks for looking closer at Ankou!

A typical fuzzer is likely to find an input passing each individual branch, but won't distinguish between inputs passing two or more branches. In theory, it's true Ankou should be able to distinguish between these inputs. I understand this was your intuition?

However, Ankou wasn't implemented with this kind of target in mind. The PCA operation is quite costly and we wanted to make sure it is worth doing. The reason you are not getting the expected result is that, for this kind of small program, the PCA is never going to be used so Ankou won't be able to distinguish the different branches. Actually, for a program of this size, the PCA is not necessary because the space is small (5 branches/dimensions).

More in details, there are two steps to pass before Ankou can identify a component/dimension as worthy to be used:

1. At first, Ankou starts as a simple branch coverage based grey-box fuzzer. Then, after some time, when the number of seeds converges and if there are enough seeds, the PCA "phase" is activated. In your examples, the PCA phase is never activated, so Ankou just keeps using branch coverage.

2. Even if we would force Ankou to pass into the PCA phase, a unique branch is unlikely to be identified as a dimension worthy enough to project all executed test cases on.

[kcc]

Thanks for the clarification!
Yes, my intuition was that Ankou's algorithm should crack this case in a second.
You are right in that it's too small to be a meaningful benchmark though.

I was playing with this and similar bigger puzzles trying to make libFuzzer solve them.
Right now libFuzzer solves it quickly with value profiling, but I hoped to find a better/alternative solution. I have a quick & dirty prototype of Ankou-style corpus management that solves these puzzles easily. The hard task is to make it scale, as you well know :)