RFC: manually instrumenting variables

[Michal Zalewski]

It's very easy to modify AFL to allow select variables to be manually
instrumented, in addition to the normal behavior of watching branches.
Say:

__AFL_WATCH(secret_counter);

Anybody sees any practical use for this or wants to try it out?

/mz

[Richo Healey]

I'd definitely be interested in it.

[Michal Zalewski]

> I'd definitely be interested in it.

OK. For afl-gcc, the trick should be as simple as applying this patch:

http://lcamtuf.coredump.cx/afl/afl-watch.patch

This is a quick hack, but let me know if you see it being useful in
any practical scenarios. I know that Hanno was interested in
instrumenting branch-less / constant-time crypto code, too - maybe
it'd help?

/mz

[Sami Liedes]

What does it do? Consider every new variable value as a new path? Or
every new extreme value?

I've been playing with a somewhat related idea, which I imagine
shouldn't be very hard to implement in the llvm plugin. I think it
should help with the magic number problem, but not with (non-trivial)
checksums. Consider compare-and-jump branches:

if (a < b) ...;
if (a >= b) ...;
if (a == b) ...;
if (a != b) ...,

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.

Sami

[Michal Zalewski]

>> http://lcamtuf.coredump.cx/afl/afl-watch.patch

>
> What does it do? Consider every new variable value as a new path? Or
> every new extreme value?

Mechanically, it stores the least significant byte of a given variable
at an AFL SHM bitmap offset corresponding to the location of that
particular __AFL_WATCH() statement. So, hitting it for the first time
would be somewhat similar to taking a new branch in the code. Repeated
hits would be classified as interesting only if the value (or more
precisely, the LSB) has changed substantially - as per the bucketing
algorithm described in technical_details.txt.

> 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.

/mz

[Sami Liedes]

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

[Jacob Ajit]

Do you have any simple test cases where this instrumentation performs well?

Also, Michal, is the AFL_WATCH file still available anywhere?

Jacob

[Abdul Azeez]

I’m developing a program that automatically generate test cases for your target application and/or binaries. I am almost done but I need to have a pull request from afl project. I home they can give me invitation.

--
You received this message because you are subscribed to the Google Groups "afl-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[☣Adam]

The official version of AFL is not in a public git repo, so there's no concept of a pull request for this project. You can submit patches here or directly to mz for consideration to be in the official version.

Alternatively, you can just publish your own version of AFL.

--Adam

[Abdul Azeez]

How can I summit it to Michal Z? Because I was trying to contact him but no response.

[Abdul Azeez]

How can I submit it to Michal Z? Because I was trying to contact him but no response. Can you help me with that?

To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "afl-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "afl-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

[Jakub Wilk]

* Michal Zalewski <lca...@gmail.com>, 2016-05-03, 19:06:
>http://lcamtuf.coredump.cx/afl/afl-watch.patch

The link has bit-rotten since then... :-/

Are there any plans on integrating this feature into AFL?

I'm asking because someone requested adding a similar feature to
python-afl: https://github.com/jwilk/python-afl/pull/9
But I'd rather add only APIs that mimic those in AFL proper.

--
Jakub Wilk