Off By One errors and Mutation Testing

Question

In the process of writing an "Off By One" mutation tester for my favourite mutation testing framework (NinjaTurtles), I wrote the following code to provide an opportunity to check the correctness of my implementation:

public int SumTo(int max)
{
    int sum = 0;
    for (var i = 1; i <= max; i++)
    {
        sum += i;
    }
    return sum;
}

now this seems simple enough, and it didn't strike me that there would be a problem trying to mutate all the literal integer constants in the IL. After all, there are only 3 (the 0, the 1, and the ++).

WRONG!

It became very obvious on the first run that it was never going to work in this particular instance. Why? Because changing the code to

public int SumTo(int max)
{
    int sum = 0;
    for (var i = 0; i <= max; i++)
    {
        sum += i;
    }
    return sum;
}

only adds 0 (zero) to the sum, and this obviously has no effect. Different story if it was the multiple set, but in this instance it was not.

Now there's a fairly easy algorithm for working out the sum of integers

sum = max * (max + 1) / 2;

which I could have fail the mutations easily, since adding or subtracting 1 from either of the constants there will result in an error. (given that max >= 0)

So, problem solved for this particular case. Although it did not do what I wanted for the test of the mutation, which was to check what would happen when I lost the ++ - effectively an infinite loop. But that's another problem.

So - My Question: Are there any trivial or non-trivial cases where a loop starting from 0 or 1 may result in a "mutation off by one" test failure that cannot be refactored (code under test or test) in a similar way? (examples please)

Note: Mutation tests fail when the test suite passes after a mutation has been applied.

Update: an example of something less trivial, but something that could still have the test refactored so that it failed would be the following

public int SumArray(int[] array)
{
    int sum = 0;
    for (var i = 0; i < array.Length; i++)
    {
        sum += array[i];
    }

    return sum;
}

Mutation testing against this code would fail when changing the var i=0 to var i=1 if the test input you gave it was new[] {0,1,2,3,4,5,6,7,8,9}. However change the test input to new[] {9,8,7,6,5,4,3,2,1,0}, and the mutation testing will fail. So a successful refactor proves the testing.

Answer 1

One natural case of "mutation test failure" is an algorithm for matrix transposition. To make it more suitable for a single for-loop, add some constraints to this task: let the matrix be non-square and require transposition to be in-place. These constraints make one-dimensional array most suitable place to store the matrix and a for-loop (starting, usually, from index '1') may be used to process it. If you start it from index '0', nothing changes, because top-left element of the matrix always transposes to itself.

For an example of such code, see answer to other question (not in C#, sorry).

Here "mutation off by one" test fails, refactoring the test does not change it. I don't know if the code itself may be refactored to avoid this. In theory it may be possible, but should be too difficult.

---

The code snippet I referenced earlier is not a perfect example. It still may be refactored if the for loop is substituted by two nested loops (as if for rows and columns) and then these rows and columns are recalculated back to one-dimensional index. Still it gives an idea how to make some algorithm, which cannot be refactored (though not very meaningful).

Iterate through an array of positive integers in the order of increasing indexes, for each index compute its pair as i + i % a[i], and if it's not outside the bounds, swap these elements:

for (var i = 1; i < a.Length; i++)
{
    var j = i + i % a[i];
    if (j < a.Length)
        Swap(a[i], a[j]);
}

Here again a[0] is "unmovable", refactoring the test does not change this, and refactoring the code itself is practically impossible.

---

One more "meaningful" example. Let's implement an implicit Binary Heap. It is usually placed to some array, starting from index '1' (this simplifies many Binary Heap computations, compared to starting from index '0'). Now implement a copy method for this heap. "Off-by-one" problem in this copy method is undetectable because index zero is unused and C# zero-initializes all arrays. This is similar to OP's array summation, but cannot be refactored.

Strictly speaking, you can refactor the whole class and start everything from '0'. But changing only 'copy' method or the test does not prevent "mutation off by one" test failure. Binary Heap class may be treated just as a motivation to copy an array with unused first element.

int[] dst = new int[src.Length];
for (var i = 1; i < src.Length; i++)
{
    dst[i] = src[i];
}

Answer 2

I think with this particular method, there are two choices. You either admit that it's not suitable for mutation testing because of this mathematical anomaly, or you try to write it in a way that makes it safe for mutation testing, either by refactoring to the form you give, or some other way (possibly recursive?).

Your question really boils down to this: is there a real life situation where we care about whether the element 0 is included in or excluded from the operation of a loop, and for which we cannot write a test around that specific aspect? My instinct is to say no.

Your trivial example may be an example of lack of what I referred to as test-drivenness in my blog, writing about NinjaTurtles. Meaning in the case that you have not refactored this method as far as you should.

Answer 3

Yes, there are many, assuming I have understood your question.

One similar to your case is:

public int MultiplyTo(int max)
{
    int product = 1;
    for (var i = 1; i <= max; i++)
    {
        product *= i;
    }
    return product;
}

Here, if it starts from 0, the result will be 0, but if it starts from 1 the result should be correct. (Although it won't tell the difference between 1 and 2!).

Answer 4

Not quite sure what you are looking for exactly, but it seems to me that if you change/mutate the initial value of sum from 0 to 1, you should fail the test:

public int SumTo(int max) 
{ 
  int sum = 1; // Now we are off-by-one from the beginning!
  for (var i = 0; i <= max; i++) 
  { 
    sum += i; 
  } 
  return sum; 
}

Update based on comments:

The loop will only not fail after mutation when the loop invariant is violated in the processing of index 0 (or in the absence of it). Most such special cases can be refactored out of the loop, but consider a summation of 1/x:

for (var i = 1; i <= max; i++) {
  sum += 1/i;
}

This works fine, but if you mutate the initial bundary from 1 to 0, the test will fail as 1/0 is invalid operation.