Random Testing

• General idea: failure-causing inputs can occur as point, strip or block patterns

• Evenly spread out test cases in the input domain to more quickly find strip and block patterns

• Process

  • Generate set of candidate test cases (randomly selected from input domain)

  • Choose test case farthest away from already executed ones

  • Execute test case and repeat if no failure was found

    
    

• Common implementation of black-box random testing

• Check for software vulns through dynamic testing

• Automated generation of fuzz test cases with slightly abnormal inputs

• Random input generation:

  • easy + fast to generate

  • ofter rejected; often executes same paths; does not reach deep

• Model-based input generation (RFC, documentation, …):

  • can deal with complex dependencies + input checks

  • costly; only applicable to certain target programs

• Mutation-based inut generation:

  • easy + fast to generate

  • effectiveness depends strongly on selected seed inputs

• Utilizes knowledge of code structure.

• Computes path conditions to find specific values.

• Adds constraints while traversing the control flow graph.

• More effective for specific input-related bugs.

• Balances effectiveness and scalability.

• add interesting test inputs to seed corpus and also prioritize them (“evolutionary fuzing) using fitnes metrics

• lightweight program instrumentation to trace runtime information for each input

• More scalable than white box and more effective than black box fuzzing.

• A tool commonly used for fuzzing.

• Defines logical properties as assertions.

• Generates test cases violating these assertions.

• Minimizes input data for failing test cases.

• Saves time and effort.

• Generated tests are unbiased.

• Knowledge about software is not necessary.

• Redundant or unrealistic test cases.

• Does not solve the oracle problem.

• Limited to finding basic bugs.

• Fault localization is time-consuming.

• Not very predictable in bug discovery.

• Protocol specific knowledge very helpful

• More fuzzers is better

• The longer you run, the more bugs you find

• Use different seed inputs

• Best results come from guiding the process

Criterion: detect at least on failure

Assumption: We work with fixed failure rates

-> Tester has to know these (impossible)

-> idea about failure rates with Gutjahr’s model

• Deterministic assumption favors random testing

• if we assume equal (independent) expected failure rates instead

  -> favors partioning testing

  -> P_r between P_p/k and P_p

• Lower bound for many small blocks and few large blocks

• Upper bound if failure rate in each block mimics overall failure rates

• Measure for “better”:

  • At least one failure detected

  • # of faults detected

  • Weighted # of faults detected

• Uniformly draw from input domain.

• Improved with knowledge about the input domain.

• Simple approach but can miss deep issues.

• Requires an oracle to verify outcomes.

• Very simple approach

• cost efficient

• can miss deep issues

• Requires an oracle to verify outcomes

• Needs more resources/effort than random testing

• performs significantly better (only tested on small amount of programs)

• Black-box fuzzers: Checks if fuzz test crashes the program

• White-box fuzzers: Use heavyweight program + runtime analysis to drive fuzzing process

• Grey-box fuzzers: Employ lightweight analysis techniques (e.g. code coverage)

• Split input domain into blocks -> random testing

• iteratively execute tests and adjust probabilities depending on outcome of test case

• Often implemented with markov-chain matrices