random testing (fuzzing)
- Feed random input to a program
- Observe whether it behaves correctly (execution satisfies specs or doesn’t crash)
- a special case of mutation analysis
inf monkey theorem
a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text
first popular fuzzing study
Barton Miller, U of Wisconsin, command-line fuzzer testing Unix programs
security bug: gets() in C and how to fix
- cause reliability issues and security breach (buffer overflow)
- second most common cause of error
- fix using fgets(), which limits the max input length
popular fuzz testing tool for mobile app
- google’s monkey tool
- usually used to generate a sequence of events with delay
monkey tool: generate gesture: slide unlock
down(x1, y1)
move(x2, y2)
up(x2, y2)
concurrency delay in practice
introduce a random delay in each thread, fuzz the thread scheduler
advantages of cuzz
- introduce sleep automatically and systematically before each statement
- give worst-case probabilistic guarantee on finding bugs
bug depth
- the number of ordering constraints a schedule needs to satisfy
- only count dependency across threads
- observation from cuzz: many typical bugs have a small depth
- useful metric for concurrency testing efforts
dead lock
neither thread can make any progress because the one of the thread is holding the lock
cuzz probability of finding the bug
1/(n*(k^(d-1)), worst case
n bugs, k steps, d depth
1/n for choosing the correct first thread
1/k for switching thread at the correct step
1/(k^(d-1)) for choosing the correct d-1 statements
why measured != worst-case
- having more threads gives more ways to trigger a bug
- if the bug can be found in multiple ways, the probabilities add up
- worst case guarantee is for hardest to find bug of given depth
cuzz vs stress testing
cuzz is much better:
- systematic randomization improves concurrency testing.
- effective in flushing out bugs with existing tests
- scale to large number of threads, long-running tests
- low adoption barrier
pros of random testings
- easy to implement
- good coverage given enough test
- can work with programs in any format
- appealing to find security vulnerabilities
cons of random testings
- inefficient (especially for later states)
- might find unimportant bugs
- poor coverage
should fuzzing replace systematic, formal testing?
No
recommended applications for fuzzing
testing security, mobile apps, and concurrency
not recommended applications for fuzzing
- replacing systematic, formal testing
- system with multiple layers (compilers)
thread schedule is decided by
- scheduler of the running OS
- non-deterministic across different runs. Although a particular run on an input succeeds, another run on the same input might crash
