Faster afl-fuzz start-up and fuzzing session resumption

[Jussi Judin]

Hi,

I have a situation where I would like to run afl during night time on computers that are otherwise idle during the night but heavily used during the day. So there is around 12-14 hour time slot every day (+ weekends and holidays) that could be used for fuzzing. The problem I have here that I have an extremely heavy file format that I'm fuzzing (amongst other things) and the minimized test set even after afl-cmin phase has 3000-5000 files that eventually result in over 10000 paths in the program after some weeks of fuzzing. This makes a new afl-fuzz session to take 4-6 hours to start, as one program execution can take 0.04-4 seconds to process inputs depending on the input data. Even after using AFL_NO_VAR_CHECK=1 and doing a session resumption with "-i-" command line argument with the same binary takes hours before any actual fuzzing is done. Especially when the size of the start-up test file set increases over time when new paths are added to the queue/.

I'm not entirely familiar with afl internals but I was wondering if any of these approaches could be used to speed up the start-up of parallel fuzzing:

1. dump the state of afl-fuzz to a file and make other fuzzers to read this file when they are started. This would enable to use 1 afl-fuzz instance to generate such state during the day and then when the night time approaches, it could be distributed to dozens of other afl-fuzz instances that would hopefully start in seconds or minutes instead of hours.
2. obtain traces with afl-showmap for each input file in afl-cmin fashion and use those generated traces to start a new afl-fuzz session. This would basically enable saving the execution flow information so that each afl-fuzz instance could avoid executing the target application with something that was already processed. Also if such trace files would be generated for each input file individually, creation of such files could be quite trivially parallelized. This would also be useful as afl-as randomly generates identifiers for each branching point on every compilation so that each new program version would need to regenerate this data.

I have also seen that if I add a large number of files to a queue for afl-fuzz to find, each instance imports those files individually and this way probably does quite a lot of duplicate work. This could be avoided if we could provide execution trace information for each input file so that recreating the same information would not need to be so costly.

Any thoughts on this matter and if anyone else has encountered similar issues when wanting to integrate afl into a normal development cycle?

--
Jussi Judin

[tcf]

Just my $.02, but could poor man serialization be done by stopping and
resuming the AFL process (`kill -TSTP $AFL_PID` and `kill -CONT $AFL_PID`) ?

Assuming you don't mind that the RAM ends up in swap.

Regards,
tcf

[floyd]

Hi Jussi

A side note: That sounds like you are running AFL on some production
machines during the night. I personally woke up in the morning realizing
that afl wrote several thousand random files with random file names by
using a memory corruption (I was lucky that AFL hadn't found out about
../ yet). I hope you have sufficient separation of AFL from any other
process/data on the machine.

As for the suspending of AFL, maybe try these:

1. Try to use Ctrl+Z and the bg and fg commands on Linux.
2. Run it in a virtualized environment (different options for that),
suspend entire VM (I often do this). Comes obviously with a performance
overhead, but better than your suspend problem.

There are also other suggestions on
http://unix.stackexchange.com/questions/43854/save-entire-process-for-continuation-after-reboot

I haven't tried 1., but that sounds promising. Maybe you could even
suspend an entire screen session with that.

As a side note: there were discussion on the mailing list before about
how to distribute the load and especially make AFL not repeat tests that
other instances already did. One outcome so far is that you can run
multiple -M instances. But doesn't help really in your case as that
would only distribute the deterministic part (and probably still need
the same time for startup).

I just realized that you probably want to fuzz a different version of
the binary each night, so the above all needs testing if it works at all
when using different versions of compiled binaries.

Best regards,
floyd

On 22/08/16 13:57, Jussi Judin wrote:

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

[Michal Zalewski]

> one program execution can take 0.04-4 seconds to process inputs depending on the input data.

Do you need to allow the 4-second cases? My instinct would be to set
more aggressive timeouts; there's seldom any benefit to letting the
program run that long.

> Even after using AFL_NO_VAR_CHECK=1 and doing a session resumption with "-i-" command line argument with the same binary takes hours before any actual fuzzing is done. Especially when the size of the start-up test file set increases over time when new paths are added to the queue/.

In addition to the kill suggestion mentioned in the other responses,
you can always try reducing CAL_CYCLES and CAL_CYCLES_LONG in
config.h. Setting them to 1 is a valid choice.

> 1. dump the state of afl-fuzz to a file and make other fuzzers to read this file when they are started.

Unfortunately, this is not compatible with the design of AFL, which
allows you to sync dissimilar fuzzing jobs, replace or update binaries
when resuming, change the command line, etc. I know that many people
are depending on this.

We could have some dedicated checks to only reuse the state when
nothing has changed, but it'd be a complicated approach.

Cheers,
/mz

[Brandon Perry]

> On Aug 22, 2016, at 10:20 AM, Michal Zalewski <lca...@gmail.com> wrote:
>
>> one program execution can take 0.04-4 seconds to process inputs depending on the input data.
>
> Do you need to allow the 4-second cases? My instinct would be to set
> more aggressive timeouts; there's seldom any benefit to letting the
> program run that long.
>
>> Even after using AFL_NO_VAR_CHECK=1 and doing a session resumption with "-i-" command line argument with the same binary takes hours before any actual fuzzing is done. Especially when the size of the start-up test file set increases over time when new paths are added to the queue/.
>
> In addition to the kill suggestion mentioned in the other responses,
> you can always try reducing CAL_CYCLES and CAL_CYCLES_LONG in
> config.h. Setting them to 1 is a valid choice.
>
>> 1. dump the state of afl-fuzz to a file and make other fuzzers to read this file when they are started.
>
> Unfortunately, this is not compatible with the design of AFL, which
> allows you to sync dissimilar fuzzing jobs, replace or update binaries
> when resuming, change the command line, etc. I know that many people
> are depending on this.

I actively stop jobs, prune the queues and pepper them with radamsa, then start new jobs again. This is definitely a useful aspect of AFL for many people.

>
> We could have some dedicated checks to only reuse the state when
> nothing has changed, but it'd be a complicated approach.
>
> Cheers,
> /mz
>

[Jussi Judin]

> -----Original Message-----
> From: afl-...@googlegroups.com [mailto:afl-...@googlegroups.com]
> On Behalf Of Michal Zalewski
> Sent: August 22, 2016 18:21
> To: afl-users
> Subject: Re: [afl-users] Faster afl-fuzz start-up and fuzzing session
> resumption
>
> > one program execution can take 0.04-4 seconds to process inputs
> depending on the input data.
>
> Do you need to allow the 4-second cases? My instinct would be to set more
> aggressive timeouts; there's seldom any benefit to letting the program run
> that long.

Well technically that timeout is just to support all the different use cases that could lead into new states in the program. I have estimated that the maximum amount of CPU time required for every interesting state transition in this case based on the specification should be 1-2 seconds. But this is just a safe maximum possible processing time, the usual processing time is closer to 0.1-0.5 seconds. Which is still quite a lot if you normally expect afl to be able to process hundreds or thousands of program executions/second. But unfortunately this algorithm is extremely heavy even with file sizes of couple of kilobytes.

I think that I can perform more aggressive input set reduction by instead of trying to cover almost all interesting state transitions in the usual input sample fed to afl-cmin, I can still divide these input samples into around 1/4 of the current average size. It'll just take a day or two.

> > Even after using AFL_NO_VAR_CHECK=1 and doing a session resumption
> with "-i-" command line argument with the same binary takes hours before
> any actual fuzzing is done. Especially when the size of the start-up test file set
> increases over time when new paths are added to the queue/.
>
> In addition to the kill suggestion mentioned in the other responses, you can
> always try reducing CAL_CYCLES and CAL_CYCLES_LONG in config.h. Setting
> them to 1 is a valid choice.

Reducing these calibration cycles to 1 does make the start-up time faster. Aborting one ongoing afl-fuzz run and resuming a new session with a patched version took 29 minutes. Does this have any downsides?

And would it be possible to change them to be definable at run-time? This is source code patching related information that can get lost when afl gets updated to a newer version Especially if I would take afl as a part of normal continuous software verification cycle, I wouldn't be the only one managing these installations anymore. Now I'm just experimenting with one specific application and trying to figure all the issues that can come up when taking afl into larger scale use.

> > 1. dump the state of afl-fuzz to a file and make other fuzzers to read this
> file when they are started.
>
> Unfortunately, this is not compatible with the design of AFL, which allows
> you to sync dissimilar fuzzing jobs, replace or update binaries when
> resuming, change the command line, etc. I know that many people are
> depending on this.
>
> We could have some dedicated checks to only reuse the state when nothing
> has changed, but it'd be a complicated approach.

Well I'm only thinking about a special use case where you want to make the cost of state replication cheaper. Namely starting multiple fuzzing instances for the same executable with the same initial input data. And handling the use case of programs changing (almost) every day to catch potential issues with as fast lead time as possible.

--
Jussi Judin

[Jussi Judin]

Hi,

Ctrl-Z approach would require quite complicate startup/resume logic, as I (or anyone else) could not run afl on a random shell instance (like in Jenkins) and survive the death of that instance. I also took a look on approaches for generic process suspend/resumption given in those links. They are quite cool, but unfortunately are not really applicable to existing environments. They generally require newer kernel (3.11 or 3.19) that is available on many machines that are available and staying idle at night-time, specific kernel options, or binaries for reliable operation that require CAP_SYS_ADMIN (like pid namespacing). Also they are not necessarily easy to build and maintain, as for example criu has tons of dependencies to various packages that can be tricky to get working properly on all various Linux distributions (I assume) that we have possibility to use. Virtual machines also sound like a hammer approach into this problem and make it quite opaque to see what happens inside and special support from the host and guest system if I want to use shared directories to pass data between fuzzers inside the virtual machine and the outside world.

So having this kind of faster resumption functionality for afl would be less demanding approach from system administrative perspective even if it doesn't have all tricks of the trade for these more heavy approaches. I'm currently using ninja[1] to handle afl-fuzz result post-processing and I'm used to post-processing restart times of tens of seconds even for hundreds of thousands of files from different afl-fuzz state directories.

As for this production environment, using memory limits and a separate user account should already give an acceptable level of safety for generic fuzzing tasks, combined with regular back-ups of normal user account data. But it's a good point to keep in mind. I have just fuzzed an application that does all file open operations before any fuzzed data is read and that also has really limited memory allocation possibilities so neither has become an issue. I assume that it's not so in a generic case.

I might need to resort in creating an internal fork of afl then, as open sourcing any code that I do at work is long and painful process. And having an internal fork is very bad, as nobody can easily discover it independently.

[1]: https://ninja-build.org/

-----Original Message-----
From: afl-...@googlegroups.com [mailto:afl-...@googlegroups.com] On Behalf Of floyd
Sent: August 22, 2016 16:29
To: afl-...@googlegroups.com
Subject: Re: [afl-users] Faster afl-fuzz start-up and fuzzing session resumption

[Sami Liedes]

On Wed, Aug 31, 2016 at 10:00:56AM +0000, Jussi Judin wrote:
> Ctrl-Z approach would require quite complicate startup/resume logic, as I (or
> anyone else) could not run afl on a random shell instance (like in Jenkins)
> and survive the death of that instance. I also took a look on approaches for
> generic process suspend/resumption given in those links. They are quite cool,
> but unfortunately are not really applicable to existing environments. They
> generally require newer kernel (3.11 or 3.19) that is available on many
> machines that are available and staying idle at night-time, specific kernel
> options, or binaries for reliable operation that require CAP_SYS_ADMIN (like
> pid namespacing). Also they are not necessarily easy to build and maintain, as
> for example criu has tons of dependencies to various packages that can be
> tricky to get working properly on all various Linux distributions (I assume)
> that we have possibility to use. Virtual machines also sound like a hammer
> approach into this problem and make it quite opaque to see what happens inside
> and special support from the host and guest system if I want to use shared
> directories to pass data between fuzzers inside the virtual machine and the
> outside world.

It seems to me that this and probably many other problems would be solved by
something I've dreamed of, but implementing what would obviously require work: A
master/slave fuzzing architecture where a single running master/tracker (that
doesn't itself fuzz) keeps track of fuzzing tasks assigned to slaves. I think
this with its implications would probably deviate somewhat from AFL's stated
goal of being very easy to use. The idea is that slaves are somehow guaranteed
to run in an identical enviroment - either guaranteed by the user running it
(garbage in, garbage out) or by transporting some kind of containers/VMs with
the software to be fuzzed. The master would keep track of which inputs exercise
globally new paths; the slaves would be just a fleet of fuzzers reporting back
results so that if 10% of them suddenly lose power the only thing you lose is
10% of fuzzing power and a few minutes of work per slave.

I think it could be useful for this fast restarting use case if the slaves could
just trust that the maps given to them by the master are valid, or retest a few
of them for a sanity check. I think this could also massively speed up the
deterministic fuzzing phase, as it could be split over multiple cores and
computers.

I think the initial steps for this would probably be to refactor the fork server
and mutation logics into generally usable libraries (also something I want to do
once I find the time). Also, call me dazzled by shiny new things, but I would
move to a higher level language for that logic, even if it be C++.

Sami

[floyd]

One thing came to my mind while discussing all this: Has anyone tried
(ab-)using the synchronization feature for faster startup time? What
happens when you start a slave with only one input file (-i), but then
due to the synchronization feature of AFL "other instances" (in the -o
output directory) suddenly turn up with a couple of thousand files (you
can emulate this behavior by simply scp the files to the output
directory next to the slave's own output)? Does the synchronization take
a long time afterwards (the sync state)?

--
floyd
@floyd_ch
http://www.floyd.ch

[Michal Zalewski]

> One thing came to my mind while discussing all this: Has anyone tried
> (ab-)using the synchronization feature for faster startup time? What
> happens when you start a slave with only one input file (-i), but then
> due to the synchronization feature of AFL "other instances" (in the -o
> output directory) suddenly turn up with a couple of thousand files (you
> can emulate this behavior by simply scp the files to the output
> directory next to the slave's own output)? Does the synchronization take
> a long time afterwards (the sync state)?

I don't think it's going to be faster. New "interesting" cases,
whether coming from the -i dir or synced from another instance, still
go through calibrate_case(), and that's what makes the startup process
slow(ish).

/mz

[Sami Liedes]

I think there's some extra work done at the first sync when parallel fuzzing
with slave/master mode. At least for me AFL executes all inputs in other
instances' queues at the first sync (despite them being identical to each other
and items in the syncing AFL's queue), and if you have, say, 8 instances, I
think it already takes nearly as much time as the calibration step. For slower
targets I think it would be much more efficient to just detect that the input is
already known.

Sami