Mutation Testing

The state of the art solution is to artificially inject bugs.
Here, we want to modify some statements in the code so we have different “buggy” versions of the code. Then we check if our test cases and our original test data can find these bugs.

A mutant is dead if the test-case find the mutant, otherwise it is live because it is equivalent to the original program or the test-set is inadequate.

We use mutation operators for the automated generation of mutants.

Types of Mutants

Stillborn mutants:

• Syntactically incorrect, killed by compiler Trivia mutant:
• Killed by almost any test case Equivalent mutant:
• Always produces the same output as the original program

None of these above are interesting

Mutant Operators

1. ABS
   1. Absolute value insertion is when each arithmetic expression is modified by abs(), negAbs(), failOnZero(), etc.
2. AOR
   1. Arithmetic operator replacement replaced an operator with another. Also use leftOp and rightOp
3. ROR
   1. Relational operator replacement replaces each occurrence of a relational operator with another and by falseOp and trueOp
4. COR
   1. Conditional operator replacement replaces each occurrence of one of the logical operators with another, or with falseOp, trueOp, leftOp, rightOp
5. SOR
   1. Shift operator replacement replaces a shift operator with another and with leftOp
6. LOR
   1. Logical operator replacement replaced a logical bitwise operator with another and with leftOp and rightOp
7. ASR
   1. Assignment operator replacement replaces and existing operator with another similar operator
8. UOI
   1. Unary operator insertion, inserts a unary operator to expressions
9. UOD
   1. Unary Operator deletion, deletes every unary operator
10. SVR
    1. Each variable reference is replaced by every other variable of the appropriate type that is declared in the current scope
11. BSR
    1. Each statement is replaced by a bomb() function which raises an exception

There are also operators specific to object-oriented programming languages. These operators change with programming languages and design and specification paradigms.

Assumptions

• Competent programmer assumption: Given a specification, a programmer develops a program that is either correct or differs from the correct program by a combination of simple errors
• Coupling effect assumption: All programs differing from a correct one by only simple errors is so sensitive that is also implicitly distinguishes more complex errors.

Complete Coverage

• Complete Code Coverage equates to killing all non-equivalent mutants. This amount of coverage is called the mutation score which is $\frac{\text{dead mutants}}{\text{non-equivalent mutants}}\ast 100$.
• Each mutant is a test requirement where its number varies
• The number of mutants tends to be large

Strong and Weak Mutation

• Strong: A fault must be reachable, infect the state and propagate to output
• Weak: A fault which kills a mutant need only be reachable and infect the state
• Both types of mutants typically need the same number of test cases to satisfy them

Strong Mutation Coverage

Given a mutant m for a program p and a test case t, t is said to strongly kill m iff the output of t on p is different from the output of t on m.

For each mutant m in M, TR contains a test case which strongly kills m.

Weak Mutant Coverage

Given a mutant m which modifies a source location L in program P, and a test case 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.

For each mutant m in M, TR contains a test case which weakly kills m.