mutation testing relationship with test unit and original code

Question

I have reading about mutation testing and even though its inner functioning or how to do it is clear to me; I am having some troubles to understanding the relationship between a program that wants to be tested and mutation testing. I have been reading material about this subject, but still is not so clear for me.

For example, imagine that I have made a program that uses binary search for finding a value. So I have something like this:

public int runBinarySearchIteratively(
  int[] sortedArray, int key, int low, int high) {
    int index = Integer.MAX_VALUE;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (sortedArray[mid] < key) {
            low = mid + 1;
        } else if (sortedArray[mid] > key) {
            high = mid - 1;
        } else if (sortedArray[mid] == key) {
            index = mid;
            break;
        }
    }
    return index;
}

So, I have a set of tests that would serve me to prove this program; for example:

arrayToTest={1,2,3,4,5,6}
key=3
will return 2

arrayToTest={10,20,30,40,50,60}
key=60
will return 5

arrayToTest={10,20,30,40,50,60}
key=100
will return Max_VAlue

But when I apply mutation testing I could generate mutants that change the program original behaviour, for example:

mutant 1:
while (low > high) {
            int mid = (low + high) / 2;
            if (sortedArray[mid] < key) {
                low = mid + 1;
            } else if (sortedArray[mid] > key) {

mutant 2:

if (sortedArray[mid] > key) {
                low = mid + 1;
            } else if (sortedArray[mid] > key) {
                high = mid - 1;

and so on. For what I know if the test cases detect the mutant (the answer provided from the mutated program differs from the one stated on the test) then the mutant is killed; and in other case the mutant survives. For what I read in case that a lot of mutant survived that would indicate that our test cases need refinement; and here come the questions that I have:

• Could a mutation testing point for probable flaws that my original program could have? If this is the case how? because a mutant would be a program forced to perform an action that the original program was not meant to.

  • Mutation testing could be used for test or generate small programs that will act as unit testing?

In summary, what would be the relationship between the original program and mutation testing? or how this technique could be useful for testing a program. Maybe the question would seem silly because it is an already studied area, but I was not able to find good examples on the web that could help me with these doubts.

Thanks

Answer 1

Mutation testing does not expose flaws in the program, but flaws in the test suite.

The idea is that the test suite should be sufficiently detailed so that any deviation from expected behaviour will be detected. A test suite with high code coverage is necessary but not sufficient for that goal. For example, a high-coverage test suite might fail to test for off-by-one errors.

A mutation test changes the program in subtle ways, for example changing a less-than < comparison to less-than-or-equals <=. A good test suite should contain edge cases that clarify our expectation what should happen here. But if that mutation does not cause the tests to fail, either operator could be correct as far as our test suite is concerned. Maybe the original is correct, maybe the mutated code is correct! But one of them must be wrong. So we might want to clarify out tests.

In practice, mutation testing is quite rare and little tooling for it is available. It is also prone to false positives, because not all code exists purely for correctness. Code is also subject to non-functional requirements that are usually not reflected in a test suite, for example that it produces some logging output. Therefore, mutation testing is less suitable for finding specific flaws but more suitable to find regions of code that have low-quality tests (i.e., mutations in this region are unlikely to be killed).

Related techniques include:

• Fault injection, where we trigger an error in our software in order to test the software's error handling
• Fuzzing, which is like mutation testing for input of the software. Fuzz testing is useful to ensure that a program is able to handle corrupted input safely. This tends to be applied to security-sensitive software such file format parsers or web servers.