3. Random Testing

Question 1

What is random testing (aka fuzzing)?

Answer 1

• Feed program random inputs
• Observe whether it behaves “correctly” (i.e., execution satisfies a specification or it just doesn’t crash)
• It is a special case of mutation analysis (it randomly perturbs its input from the environment or the network).

Question 2

What is the depth of a concurrency bug?

Answer 2

The number of ordering constraints (across threads) a schedule has to satisfy to find the bug.

NOTE: ordering constraints within a thread don’t count toward the bug depth because a thread’s control flow implicitly defines the constraints on the order in which the statements execute.

Bug depth only counts ordering constraints ACROSS threads.

A bug depth of 1-2 is generally good enough to uncover most of a program’s concurrency bugs.

Question 3

Why does systematic randomization improve concurrency testing?

Answer 3

Fuzzing thread schedules (as Cuzz does) gives us a guaranteed probability of finding a bug of a given depth.

Question 4

Why is Cuzz better than traditional stress testing?

Answer 4

Whatever stress testing can do, Cuzz can do better (and faster).

• effective in flushing out bugs with existing tests (just needs to fuzz the thread schedule running each of those tests)
• scales easily to a large number of threads and long-running tests
• has a low adoption barrier

Question 5

What are the pros and cons of random testing (fuzzing)?

Answer 5

Pros:

• easy to implement
• probably good coverage given enough tests
• can work with programs in any format
• appealing for finding security vulnerabilities

Cons:

• inefficient test suite
• might find bugs that are unimportant
• despite the fact that any given input will be tested with probability approaching 1 given enough tests, in practice it can still have poor coverage

For example:
- the lexer is very heavily tested by random inputs but later stages is much less efficient b/c most bad inputs don’t get through.

Question 6

What is random testing good at?

Can random testing replace systemic, formal testing?

Answer 6

Effective for testing security, mobile apps, and concurrency.

No, it should be used to complement it.