Archive

Posts Tagged ‘avl tree’

Speed up your fuzzfarm: fast hit tracing

11/05/2012 12 comments

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.

Read more…