Dobin 0x71_Fuzzing.pdf

Fuzzer:

A program which generates new "random" inputs, and feeds it to the target program.

Types of Fuzzing:

• Mutation based
• Grammar based
• Feedback based

Mutation based fuzzing:

Take an input file, modify it a bit, continue

Steps:

• Create input corpus
• Select an input
• Modify input file ("fuzz it")
• Start program with input file
• Identify crashes

Grammar based fuzzing

used for: eg. javaScript, HTML, FTP, HTTP, ...

Cannot just flip bits etc, as it is not a binary protocol

alert(1); -> is valid

alfrt(1); -> is garbage

Steps:

• Create a random input file based on grammar
• Start program wiht input file
• Identify crashes

Tarditional fuzzing  - dumb, inefficient, brute force

Example of Feedback Fuzzer:

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.

• "Bit flips" only get you this far
• AFL:
  • 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.
• Low Probability of catching:
  • if a == 0x31337
  • if a == "CONNECT"

Solutions:

• wordlists
  • "CONNECT', "SEND", "RECEIVE", "OPTIONS"
  • use strings commands on the binary
• translate into bytewise compare
  • transform string comparision to per-byte (LD_PRELOAD, code transformation via compiler plugin, ...)
  • if (a[0] == 0x37) {if (a[1] == 0x13) {if (a[2] == 0x03) {....
• symbolic exection
  • constraint solving in code via symbolic execution (angr, KLEE)

• Translate compiled commands (assemby) into a higher-level language (e.g. VEX)
• Perform reasoning on it
• Use constraint solver to reach certain code paths

Problems of symbolic executions?

• state explosion (computational power increases exponentially with code size)
• uncertain time constraints (try to solve "if md5(input) == 0x 5423523649")