Speed up your fuzzfarm: fast hit tracing

The fuzzing methodology introduced by Charlie Miller [1] was widely adopted in the security industry, as it is indeed an effective and low cost method of finding bugs.

The idea is:

• collect a lot of sample files
• let your target application parse them all
• collect the set of basic blocks executed for every file
• calculate the minimal set of samples that covers all of the collected basic blocks
• flip random bytes in files from that set and wait for a crash

It’s a simple process, but all implementations I heard of suffer from an interesting performance bottleneck in the basic block tracing part.

If your tracer takes >1min per file, you can speed it up to take only few seconds, with just a few simple observations.