AFL is neat because it's conceptually simple, but practically revolutionized fuzzing, especially for non-specialists. The basic algorithm is
def run_test_case(input):
# return a set() of instructions that the target executes when ran on `input`
# or throw a CrashException if the target crashes
def mutate(input):
# mess with the input- flip some bits, delete chunks, set things to 0xffffffff... randomly
# return the mutated input
def fuzz(initial_test_cases):
test_cases = initial_test_cases
coverage_seen = set()
# collect coverage from the initial inputs
for case in test_cases:
coverage_seen += run_test_case(case)
while True:
fuzzed = mutate(random.choice(test_cases))
try:
new_coverage = run_test_case(fuzzed) - coverage_seen
if new_coverage:
# ooh, this input did something we've never seen before!
# save it, so it can be used as a starting point
# for even more mutation
test_cases.add(fuzzed)
coverage_seen += new_coverage
except CrashException:
# we successfully crashed the target!
# save fuzzed off to disk or something and log a happy message
There's more to it in practice, of course- for example, run_test_case doesn't return a set of instructions, it's a bitmap / psuedo-Bloom filter of
basic blocks hit. (A basic block, to a first approximation, is "a sequence of instructions that doesn't have any unusual control flow" - so if you run the first instruction in a basic block, you'll run all the rest.) And there's a fair bit of complexity involved for performance reasons.
But the core algorithm is simple enough that you can actually implement it in pure Python, for Python programs, in < 100LOC - and that implementation will find real bugs in a lot of Python libraries.
But the core algorithm is simple enough that you can actually implement it in pure Python, for Python programs, in < 100LOC - and that implementation will find real bugs in a lot of Python libraries.