CSE4303 Introduction to Computer Security (Lecture 20)

Due to lack of my attention, this lecture note is generated by AI to create continuations of the previous lecture note. I kept this warning because the note was created by AI.

Fuzz testing

American fuzzy lop (afl-fuzz)

Overview

Also known as afl-fuzz
”… is a security-oriented fuzzer that 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 targeted binary.”
Requires minimal setup — just compile and provide example inputs

Bug trophy case

Projects in which afl-fuzz has found bugs include:

libjpeg-turbo
libpng
libtiff
mozjpeg
sqlite
ffmpeg
ntpd
OpenSSL
OpenSSH
tcpdump
wireshark
Firefox
Internet Explorer
Safari
Adobe Flash
bash
Android
iOS
LibreOffice
… and many more

How does it work?

afl-fuzz broadly attempts to get the program into unusual states:

Compiles the program with a gcc wrapper (afl-gcc) that adds custom instrumentation to the compiled binary (feedback-driven)
Creates new test cases by mutating test cases currently in the queue
Runs inputs likely to get the program into a new state (as guided by instrumentation)
Minimizes and saves test cases that reached new states; uses them to generate further test cases
Repeat steps 2–5

The instrumentation tracks which code paths (edges in the control-flow graph) each input exercises, so the fuzzer can preferentially explore inputs that reach previously-unseen program states.

Basic afl-fuzz operation steps

Get the target program source
Compile with afl-gcc
Choose starting test case(s)
- Smaller is almost always better
- afl source ships with many good starting test cases
Create a test harness to deliver input to the target
Start afl-fuzz
Wait!
Investigate results

Some of the provided test cases bundled with afl:


js:
    if (1==1) eval('1');

rtf:
    Test

xml:
    <a b="c">d</a>

Understanding the afl-fuzz status screen

When afl-fuzz runs, it displays a live terminal dashboard:


                     american fuzzy lop 1.94b (strings)

┌─ process timing ─────────────────────────────────┬─ overall results ────┐
│        run time : 1 days, 1 hrs, 59 min, 44 sec  │  cycles done : 0     │
│   last new path : 0 days, 0 hrs, 27 min, 12 sec  │  total paths : 680   │
│ last uniq crash : none seen yet                  │  uniq crashes : 0    │
│  last uniq hang : 0 days, 15 hrs, 6 min, 7 sec   │   uniq hangs : 79    │
├─ cycle progress ────────────────┬─ map coverage ───────────────────────┤
│  now processing : 21 (3.09%)   │    map density : 1908 (2.91%)         │
│ paths timed out : 0 (0.00%)    │ count coverage : 2.86 bits/tuple      │
├─ stage progress ────────────────┼─ findings in depth ──────────────────┤
│      now trying : arith 8/8    │  favored paths : 158 (23.24%)         │
│    stage execs  : 239k/1.13M   │    new edges on : 219 (32.21%)        │
│     total execs : 14.9M        │  total crashes : 0 (0 unique)         │
│      exec speed : 478.6/sec    │    total hangs : 12.5k (79 unique)    │
├─ fuzzing strategy yields ───────────────────────┬─ path geometry ──────┤
│   bit flips : 289/1.37M, 31/1.37M, 14/1.37M    │     levels : 3       │
│  byte flips : 1/171k, 1/62.9k, 1/66.4k         │    pending : 672     │
│ arithmetics : 68/2.84M, 2/1.72M, 1/1.16M       │   pend fav : 152     │
│  known ints : 8/218k, 7/1.04M, 3/1.90M         │  own finds : 679     │
│  dictionary : 0/0, 0/0, 8/1.00M                │  imported : n/a      │
│       havoc : 245/351k, 0/0                     │  variable : 0        │
│        trim : 1.83%/10.6k, 64.31%              │                      │
└────────────────────────────────────────────────────────────[cpu:193%]──┘

Process timing

Answers the questions:

How long has the fuzzer been running?
How long ago was the last new path/crash/hang discovered?

Key fields:

Field	Meaning
`run time`	Total elapsed time
`last new path`	Time since the last new execution path was found
`last uniq crash`	Time since the last unique crash was found
`last uniq hang`	Time since the last unique hang was found

Overall results

High-level summary of what afl has found so far:

Field	Meaning
`cycles done`	Number of complete passes over all queued test cases
`total paths`	Total number of distinct execution paths discovered
`uniq crashes`	Unique crashing inputs saved
`uniq hangs`	Unique hanging inputs saved

Stage progress

Shows what the fuzzer is doing right now:

Field	Meaning
`now trying`	Current mutation stage (e.g., `arith`, `havoc`, `trim`)
`stage execs`	Executions completed in this stage vs. total planned
`total execs`	Grand total of all executions so far
`exec speed`	Executions per second

Fuzzing strategy yields

afl cycles through several mutation strategies and tracks how many new paths each has found:

Strategy	Description
`bit flips`	Flip individual bits in the input
`byte flips`	Flip individual bytes
`arithmetics`	Add/subtract small integers from byte values
`known ints`	Substitute common “interesting” integer values
`dictionary`	Insert tokens from a user-supplied dictionary
`havoc`	Randomised stacked mutations
`trim`	Minimise test cases while preserving coverage

Each strategy reports new_paths_found / total_executions_in_stage.

Path geometry

Describes the shape of the discovered execution-path tree:

Field	Meaning
`levels`	Depth of the path tree
`pending`	Test cases not yet fully mutated
`pend fav`	Favoured pending test cases
`own finds`	Paths discovered without importing from other instances
`imported`	Paths imported from other parallel afl instances
`variable`	Test cases that produce non-deterministic coverage