Automated Vulnerability Discovery

Fuzzing

Yan Shoshitaishvili�Arizona State University

Dynamic Analysis

Pros:

• Typically don't require source code.
• Very precise.

Cons:

• Must run the program to analyze it. Not trivial for:
• complex programs
• libraries
• embedded devices
• Can only spot bugs if the bug is triggered.

"No bugs detected" is a quite normal result of�dynamic analysis of buggy programs.

#

Origins: Program testing via "Trash Decks"

1950s

http://secretsofconsulting.blogspot.com/2017/02/fuzz-testing-and-fuzz-history.html

#

Fuzzing: Scientific Framing

Joe W. Duran, et al.

"A report on random testing".

ACM SIGSOFT International Conference on Software Engineering, 1981.

1981

#

Original Idea

Core concept: programmers assume that users are well-behaved.

1. Run the program.
2. Send it random data as input.
3. See if it crashes.

# while true�> do�> cat /dev/urandom | monitor_for_crashes.py /babymem_level1_testing1�> done

That's ... surprisingly effective.

#

monitor_for_crashes.py

Fuzzers tend to find crashes. Crashes are easy to detect!

Other types of vulnerabilities are harder, but doable:

• Race Conditions
• Algorithmic Attacks
• Information Disclosures

Lots of active research on this!

#

Generational Fuzzing

Generational fuzzers use intelligent techniques to generate program inputs!

# while true�> do�> generate_elf_file.py /tmp/random-elf�> monitor_for_crashes.py objdump -d /tmp/random-elf�> done

Example:

• Peach Fuzzer (https://www.peach.tech/)

#

Mutational Fuzzing

Mutational fuzzers mutate existing inputs to try to trigger new program behavior (and bugs!).

# while true�> do�> mutate_input.py /tmp/random-elf1 > /tmp/random-elf2�> monitor_for_crashes.py objdump -d /tmp/random-elf2�> done

Core questions:

• How to select inputs to mutate?
• How to mutate inputs?

#

Coverage-guided Mutational Fuzzing

Modern fuzzers have the following loop:

• Start with a provided seed corpus as pending inputs.
• Analysis Loop
• Execute target program with every pending input.
• Record what instructions were executed when processing each pending input.
• Mark inputs that increase code coverage as interesting inputs.
• Mutate interesting inputs to produce a new set of pending inputs.
• Find bugs!

Some questions:

• Seed corpus?
• How do we identify an increase in code coverage?
• How do we mutate inputs?

#

"The uses of symbolic execution, concolic execution, static analysis, and other emerging technologies to spot substantial vulnerabilities in complex, unstructured, and non-annotated code are still in their infancy."

• Michael Zalewski, 2015

Creator, American Fuzzy Lop

Seed Corpus

The seed corpus is critical.

The infinite monkey theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, such as the complete works of William Shakespeare. [https://en.wikipedia.org/wiki/Infinite_monkey_theorem]

... but this will take a VERY LONG TIME.

Your seed corpus helps the monkeys. Make it:

Varied: it should represent a good coverage of the functionality of the program

Weird: it should trigger enough uncommon behavior to give the fuzzer a�good starting point to trigger really rare behavior. Also have some normal stuff!

Small: AFL will eventually try to mutate every bit. Don't put in useless bits.

#

Measuring Code Coverage

Many coverage tracking techniques exist:

• track each instruction that was executed
• track each basic block that was executed
• track each function that was executed

American Fuzzy Lop insight: It's not the code that matters, it's how you traverse it!

AFL measures control flow transitions, pairs of basic blocks connected by a jump.

#

Mutating Inputs

AFL ships with several mutators:

bitflip L/S: L bits toggled at a time, walking the input file with S-bit increments. Currently: 1/1, 2/1, 4/1, 8/8, 16/8, 32/8.

arith L/8: subtract or add small integers to 8, 16, and 32-bit values. The stepover is 8 bits.

interest L/8: list of known “interesting” 8, 16, and 32-bit values to try. The stepover is 8 bits.

extras: deterministic injection (or replacement) of user-supplied or automatically determined dictionary terms.

havoc: random tweaks. Operations attempted bit flips, overwrites with�random and “interesting” integers, block deletion, block duplication,�assorted dictionary-related operations.

splice: splices together two random inputs from the queue at�some arbitrarily selected midpoint.

Source: https://afl-1.readthedocs.io/en/latest/user_guide.html

#

Fuzzing is King

Fuzzing is undeniably the best automated program analysis technique we have.

Fuzzing finds thousands of bugs every year.

AFL Released

#

Cutting-Edge Fuzzers

Too many fuzzers to keep track of! Notable mentions:

OSS-Fuzz: continuous fuzzing for open-source software (https://github.com/google/oss-fuzz)

syzkaller: system call fuzzing for Linux (https://github.com/google/syzkaller)

libfuzzer: fuzzing library integrated into Clang/LLVM (https://llvm.org/docs/LibFuzzer.html)

afl++: community-maintained AFL fork (https://github.com/AFLplusplus/AFLplusplus)

​

Further reading: https://github.com/secfigo/Awesome-Fuzzing

#