Fault seeding is a technique for evaluating the effectiveness of a testing process.

• One or more faults are deliberately introduced into a code base, without informing the testers.
• The discovery of seeded faults during testing can be used to calibrate the effectiveness of the test process.
• Let S be the total number of seeded faults, and s(t) be the number of seeded faults that have been discovered at time t.
• s(t)/S is the seed-discovery effectiveness of testing to time t.
• If seeded faults are assumed are to be representative of actual faults, then seed-discovery effectiveness can be assumed to be representative of overall testing effectiveness.

Sample Problem

• Seed 100 faults into a project at time 0.
• Testing continues to time 30, at which point 73 of the seeded faults have been detected.
• If 219 actual faults were discovered, what is the expected number of total faults prior to seeding?
• How many latent faults are expected to remain in the software at time 30?
• Answer at the bottom of the page.

But be aware of the caution in section 4.2.2 of SWEBOK:"Inserting faults into software involves the obvious risk of leaving them there".

Mutation Adequacy

Mutation adequacy uses a similar concept to fault seeding to evaluate the effectiveness of a test suite.

• Assume we have a test suite TS with C total test cases c(j).
• Assume that the program under test P passes all the test cases c(j) for 1 <= j <= C.
• Can we stop testing? That is, have we tested P adequately?
• The mutation adequacy criterion provides one answer that we might use.

The mutation adequacy approach differs from fault seeding in that it is applied at a particular point in the testing process and also in that faults are not directly inserted into P.

• Instead, a series of mutants m(i) are created.
• Each mutant m(i) differs from P by the injection of exactly one fault.
• Let M be the total number of mutants m(i).
• The test suite TS is applied to each mutant m(i).
• If a particular mutant m(i) fails any test in c(j), then it is said to be killed.
• All mutants that are not killed are said to remain live at this point.
• The ratio of killed to total mutants (K/M) can be considered a measure of adequacy of TS.

Automated Mutation: Mutation Operators

• Manually creating mutants is time-consuming.
• A collection of mutants m(i) created from P at some point in time will no longer be representative of P after it has undergone many changes.
• Mutation can be automated by through the concept of mutation operators.
• Mutation operators are simple changes that can be made at various program locations.

Some Mutation Operators

There are many other kinds of mutation operators.

• Method Mutation Operators for Java
• Class Mutation Operators for Java

A Program and Three Mutants

Consider the following program P to perform integer division.

q = 0;
r = x;
while r >= y {
  r = r - y;
  q = q + 1;
}

Given inputs x and y, P computes the integer division of x divided by y producing quotient q and remainder r.

Applying the mutation operators in the previous table, we can produce the following 3 mutants of P.

q = 1;
r = x;
while r >= y {
  r = r - y;
  q = q + 1;
}

q = 0;
r = y;
while r >= y {
  r = r - y;
  q = q + 1;
}

q = 0;
r = x;
while r >= y {
  r = r - y;
  q = q  - 1;
}

Mutation Theory

First-Order and Higher-Order Mutants

A first-order mutant is a mutant produced from the progam under test by application of a single mutation operator at a single point in the program.

Higher-order mutants are produced by applying a sequence of mutations to a program.

Competent Programmer Hypothesis

• Good programmers tend to write programs that are close to correct.
• Therefore, a program with a single mutation is a good model for a realistic bug.
• Ability to detect mutants with a single mutation is a good model for ability to detect errors made by competent programmers.

Coupling Effect

• Complex errors are coupled to simple ones.
• A test suite that is sensitive enough to kill first-order mutants is also likely to kill higher-order mutants.

Equivalent Mutants

• Sometimes a mutation to the program under test results in a modified program that produces the same results.
• In this case, the mutant cannot be killed during tested.
• Equivalent mutants should be removed from the mutation adequacy score.
• Mutation adequacy of test suite TS can be determined.

TS= K/(M - E)

• BUT, determining whether a mutant M is equivalent to its program P is difficult.

Mutation-Based Test Generation

• After mutant generation and testing, live mutants may remain.

• Once a test suite TS has been evaluated for mutation adequacy, the test suite can be improved by adding new test cases to specifically kill the live mutants.

Resources

• Mutation Testing Repository at University College London.
• Jeff Offutt, uJava - A Mutation Testing Tool for Java.
• Yue Jia, milu - C Mutation Testing Tool
• R. Just, Major Mutation Testing for Java

Answers

Fault Seeding Problem

• The discovered original faults are three times the numbered of discovered seeded faults, so 300 original faults are expected.
• The latent faults are those remaining and not removed: (300 - 219) original faults plus (100 - 73) seeded faults, that is 81 + 27 = 108 latent faults.