L3

Question 1

random testing (fuzzing)

Answer 1

• Feed random input to a program
• Observe whether it behaves correctly (execution satisfies specs or doesn’t crash)
• a special case of mutation analysis

Question 2

inf monkey theorem

Answer 2

a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text

Question 3

first popular fuzzing study

Answer 3

Barton Miller, U of Wisconsin, command-line fuzzer testing Unix programs

Question 4

security bug: gets() in C and how to fix

Answer 4

• cause reliability issues and security breach (buffer overflow)
• second most common cause of error
• fix using fgets(), which limits the max input length

Question 5

popular fuzz testing tool for mobile app

Answer 5

• google’s monkey tool

- usually used to generate a sequence of events with delay

Question 6

monkey tool: generate gesture: slide unlock

Answer 6

down(x1, y1)
move(x2, y2)
up(x2, y2)

Question 7

concurrency delay in practice

Answer 7

introduce a random delay in each thread, fuzz the thread scheduler

Question 8

advantages of cuzz

Answer 8

• introduce sleep automatically and systematically before each statement
• give worst-case probabilistic guarantee on finding bugs

Question 9

bug depth

Answer 9

• 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

Question 10

dead lock

Answer 10

neither thread can make any progress because the one of the thread is holding the lock

Question 11

cuzz probability of finding the bug

Answer 11

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

Question 12

why measured != worst-case

Answer 12

• 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

Question 13

cuzz vs stress testing

Answer 13

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

Question 14

pros of random testings

Answer 14

• easy to implement
• good coverage given enough test
• can work with programs in any format
• appealing to find security vulnerabilities

Question 15

cons of random testings

Answer 15

• inefficient (especially for later states)
• might find unimportant bugs
• poor coverage

Question 16

should fuzzing replace systematic, formal testing?

Answer 16

No

Question 17

recommended applications for fuzzing

Answer 17

testing security, mobile apps, and concurrency

Question 18

not recommended applications for fuzzing

Answer 18

• replacing systematic, formal testing

- system with multiple layers (compilers)

Question 19

thread schedule is decided by

Answer 19

• 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