Syntax-based Testing

Mutation Testing

Input-space grammars - to create inputs (both valid and invalid)
Program-based grammars - to modify programs (valid)

Using Grammar

• Two ways to use input grammars for software testing and maintenance

Recognizer - can include them in a program to validate inputs
Generator - can create program inputs for testing

Terminology

Ground String - A (valid) string belonging to the language of the grammar

Mutation Operator - A rule that specifies syntactic variations of strings generated from a grammar

Mutant - The result of one application of a mutation operator to a ground string

• May be generated either by modifying existing strings or by changing a string while it is being generated

Coverage Criteria

Terminal Symbol Coverage (TSC) - TR contains each terminal of grammar G

Production Coverage (PDC) - TR contains each production of grammar G

Derivation Coverage (DC) - TR contains every possible string derivable from G

• PDF subsumes TSC
• DC often generates infinite test sets
  • Will have huge numbers of inputs even if you limit to fixed-length strings

Testing Invalid Inputs

Reasons

• Often implementers overlook invalid inputs
• Undefined behaviour not accetpable

Solution

• Mutate grammars and generate test strings from the mutated grammars

Grammar Mutation Operators

Nonterminal Replacement

dep = "deposit" account amount => dep = "deposit" amount amount

e.g. deposit 123 $12.35 => deposit $9.22 $12.35

Terminal Replacement

amount="$"digit+"."digit{2} => amount="$"digit+"$"digit{2}

Terminal and Nonterminal Deletion

dep="deposit" account amount => dep="deposit" amount

Terminal and Nonterminal Duplication

dep="deposit" account amount => dep="deposit account account amount"

Killing Mutants

• Test case t kills m if running t on m produces different output than running t on $m_0$
  • Where m is a mutant for an original ground string program $m_0$

Coverage Criteria

Mutation Coverage (MC) - For each mutant m, TR contains a requirement to "kill m"

• Mutation score is the percentage of mutants killed

Mutation Operator Coverage (MOC) - For each mutation operator op, TR contains requirement to create a mutated string m derived using op

Mutation Production Coverage (MPC) - For each mutation operator op and each production p that op can be applied to. TR contains requirement to create a mutated string from p

Mutant Testing (Program-based Grammars)

• Generating mutants by modifying programs according to the language grammar, using mutation operators
• Mutants are valid programs (not tests) which ought to behave differently from the ground string

• The goal of mutation testing create tests which distinguish mutants from originals

• Once we find a test case that kills a mutant, we can forget the mutant and keep the test case. The mutant is then dead

Uninteresting Mutants

• Stillborn - such mutants cannot compile (or immediately crash)
• Trivial - killed by almost any test case
• Equivalent - indistinguishable from original program

Goals of Mutation Testing

1. Mimic (and test for) typical mistakes
2. Encode knowledge about specific kinds of effective test in practice

Strong and Weak Mutation

Strong mutation - a fault must be reachable, infect the state, and propagate to output Weak mutation - a fault which kills a mutant ned only be reachable and infect the state

Mutation Coverage

Strongly Killing Mutants - given a mutant m for a program P and a test t, t is said to kill m iff the output of t on P is different from the output of t on m

Strong Mutation Coverage (SMC) - for each mutant $m\in M$, TR contains a test which strongly kills m

Weakly Killing Mutants - given a mutant m that modifies a source location L in a program P and a test t, t is said to weakly kill m iff the state of the execution of P on t is different from the state of the execution of m on t, immediately after some execution of L

Weak Mutation Coverage (WMC) - for each mutant $m\in M$, TR contains a test which weakly kills m