AFL (American Fuzzy Lop): employs a novel type of compile-time instrumentation and genetic algorithms to automatically discover clean, interesting test cases that trigger new internal states in the target binary.
Concept of feedback based Fuzzing:
"Observe: the program to see if a new input (mutated from corpus) reaches new code path
This is being done by adding code in the compile process which tracks which functions get called in what order.
What are the problems with fuzzing?
"Bit flips" only get you this far
Sequential bit flips with varying lengths and stepovers,
Sequential addition and subtraction of small integers,
Seguential insertion of known intersting integer (0, 1, INT_MAX, UNIT_MAX, 127, 129, etc...)
With deterministic fuzzing out of the way, the non-deterministic steps includ:
stacked bit flips, insertions, deletions, arithmetics, and splicing of different test cases.