On Wed, May 04, 2016 at 01:01:06PM -0700, Michal Zalewski wrote:
> > For each of these, a-b, or abs(a-b), could be considered a measure of
> > how close the branch was to going the other way. In fact it might make
> > also sense to instrument the comparisons themselves rather than the
> > branches, i.e. all the LLVM IR icmp and maybe fcmp instructions.
> >
> > So, if each case where abs(a-b) was smaller (maybe also larger, for
> > overflows?) than ever seen before would be considered a new path, the
> > search would hopefully gravitate towards taking the other branch.
>
> Yep, there's probably a lot more we could do in LLVM mode. Another
> option is just doing __AFL_WATCH() style sampling of variables as they
> are used, without the need for manually added code.
I implemented the abs(a-b) storing logic in afl-llvm-pass and runtime
and modified afl-showmap to show the results (but not yet afl-fuzz).
It's more of proof of concept, not optimized code. It probably doesn't
make sense to store 64-bit diffs, but that's what it does now. Patch
attached, in case someone wants to play with it or take it from here
(FWIW, I have signed the Google CLA).
For each integer comparison, it treats them as an unsigned comparison
and calls __afl_instr_cmp_i64(cur_loc_like_random, left-right). That
function currently expects there to be an extra u64[MAP_SIZE] space in
__afl_area_ptr.
Now, I guess the question is what would be the best strategy to
integrate this into afl-fuzz. The entire favorites logic is a bit
unclear to me. Probably there should be a virgin_bits like array for
comparisons too, and everything where a diff is smaller than ever
previously seen should be queued like when new paths are discovered?
Here's an example of what afl-showmap shows for test-instr. The
C023206 shows the difference in the "buf[0] == '0'" comparison:
------------------------------------------------------------
sliedes@lh:~/projects/afl-compinstr/afl/llvm_mode$ ../afl-showmap -o /dev/stdout ./test-instr
afl-showmap 2.19b by <
lca...@google.com>
[*] Executing './test-instr'...
-- Program output begins --
0
Looks like a zero to me!
-- Program output ends --
000000:1
025877:1
032335:1
033771:1
044411:1
C023206:0
C062627:1
[+] Captured 5 tuples in '/dev/stdout'.
sliedes@lh:~/projects/afl-compinstr/afl/llvm_mode$ ../afl-showmap -o /dev/stdout ./test-instr
afl-showmap 2.19b by <
lca...@google.com>
[*] Executing './test-instr'...
-- Program output begins --
!
A non-zero value? How quaint!
-- Program output ends --
000000:1
019886:1
032335:1
044411:1
053917:1
C023206:15
C062627:1
[+] Captured 5 tuples in '/dev/stdout'.
sliedes@lh:~/projects/afl-compinstr/afl/llvm_mode$
------------------------------------------------------------
Sami