Contra-testing

In software development, it is common practice to have a suite of unit tests which can be run automatically against the program under development. In the following, I’ll introduce (or quite possibly reinvent) a way of improving the quality of a test suite.

How well the tests check the program is difficult to quantify. One common way is to use a coverage measuring tool; such a coverage tool then monitors the test execution and records which of the program’s code paths are exercised and which aren’t.

However, while a good test suite yields good coverage of the program, the reverse is not necessarily true: a test suite may give good program coverage yet not check the program’s behaviour very well. For instance, a test suite which runs the program with a lot of different inputs, but never perform any checks on the output of the program, might give good coverage without finding any bugs. In a less pathetic example, one unit test may exercise a code path, and another test may contain the check which would expose a bug in that code path — this, too, would exhibit good program coverage, yet not catch the bug.

Another danger when writing a unit (or other) test is that it doesn’t test what it’s supposed to test. The important assertions may be defunct for some reason or other; sometimes this lack is caught, sometimes not.

In this respect, the test is not different from any other program: somtimes it doesn’t do what it is supposed to do. Except the risk is in some respects greater for test code: if it doesn’t work as expected, there’s a significant probability that the result will just be a green lamp, with no-one being the wiser.

A different, but related problem with test code is that of maintenance. As the requirements, structure, and maintainers of a program change, the original intent of the code may be muddled somewhat, making it less obvious what the test is supposed to check, and whether those checks remain relevant.

So — who guards the guards? Who tests the tests — keeps the checkers in check?

For the main program, both failure to behave as intended, and ceasing at some point to do it, is often caught by the test suite. (That’s the idea, anyway.) For tests, on the other hand, either kind of failure may go unnoticed.

Part of the problem is in essence one of coverage — not of the program, which is commonly measured, but of the test code, which seldom is. It is, indeed, a common feature of test code, by its very nature, that certain of its code paths are seldom if ever exercised.

Can you test the tests, then? Can you exercise them more thoroughly?

Test-driven development (TDD) is a partial answer to this problem: in the TDD methodology, tests are written to first fail, reflecting the non-compliance of the code, then the code is changed to make the test succeed. That means that the error-path of the test is taken at least once; definitely an improvement.

Here, though, I want to go a step further — and aim for continual testing of the tests.

One possibility is to see unit tests and programs as adversaries — as duals of each other — keeping each other in check. That approach appears to have some advantages.

Following the testing principle from "The Art of Software Testing": "A programmer should avoid attempting to test his or her own program", I’ll discuss it as if program writer and test writer are different people — but this doesn’t mean that it’ll work less well if the program writer is also the tester.

If the normal unit test writing method is an asymmetric game where the test writer tries to second what the program writer might have missed, and the program writer is simply doing his job, — we could conceivably aim for a more symmetric situation of both parties writing checks of the other’s work.

In that kind of game, this means that the program writer supplies more than one implementation, of which all but one are known to contain a bug — realistically, this would be the actual program and a set of variations on it.

For the test writer, this means supplying a set of unit tests as usual — except that now that set can be failed, deemed inadequate! The test writer gets a chance to lose, too.

Supposing this is a novel idea (although probably it isn’t), let’s name it "Contra-testing".

(Update: The idea if using intentional bug introduction as part of the testing process is indeed far from new. Both "Bebugging" and "Mutation Testing" (two techniques dating back to the 1970s) are about exactly that. More on that later.)

Also, let’s have some illustrative examples. I’ll go with a couple of classics — as far as the programs are concerned. The test cases probably won’t be.

Notation

We’ll need some notation for specifying faulty variations of the program. There are several possibilities; here I’ll go with a pure Java API: from the program writer’s point of view, it consists of a static method ContraTest.bug(String bugName) which under normal conditions returns false, but for the contra-test specified by bugName returns true.

Example 1 — factorial

Consider the well-known fibonacci function, as written by our friend Petra the Program Writer (and, also, written in Java):

public static long fibonacci(int n) {
    long a=0, b=1;
    for (int i=0; i<n; i++) {
        long tmp=a; a=b; b=tmp+b;
    }
    return a;
}

What challenges might Petra set for Terry the Test Writer? What might she suspect that he won’t think of testing?

Well, apart from border cases and so on, one thing on her mind — one concern which is present for her as she writes the code, and which Terry might not think of — is that there are different algorithms to choose from, with very different performance characteristics.

Thus, one suitable contra-test would be this:

public static long fibonacci(int n) {
    if (ContraTest.bug("slow factorial")) {
        return (n==0) ? 0
             : (n==1) ? 1
             : fibonacci(n-1) + fibonacci(n-2);
    ...the real code of the function...

This contra-test ensures that if Terry only tests the function with very small inputs, that’ll be caught. So he’ll include one. Which again means that if, later on, some other developer steps in thinking, "why use iteration? Surely the straight-forward recursive version is better," that regression will be caught. Also, possibly, he’ll be more inclined to write tests for algorithmic complexity in the future.

The example may not be so realistic (there are faily few uses of the fibonacci function in everyday software projects), but it illustrates the general principles well enough.

Example 2 — accounts

Another example: the classic "account" example illustrating race conditions.

Here is Petra’s code, including a contra-test:

public class Accounts {
    public boolean transfer(String fromAccountID, String toAccountID, long amount) {
        synchronized (ContraTest.bug("no locking in transfer")
                      ? new Object() : this) {
            if (withdraw(fromAccountID, amount)) {
                deposit(toAccountID, amount);
                return true;
            } else return false;
        }
    }
    ...
}

This is another example of a contra-test of a non-functional but crucial aspect of the implementation — here of whether the Accounts.transfer() method is properly synchronized.

I conjecture that while this is a quite important aspect, few unit test writers would under normal circumstances include a test for it. With contra testing, the odds might improve.

Example 3 — hash set

The examples so far happen to have lead to non-functional tests. For a functional-test example, here’s a Set implementation Petra has written:

public class MySet {
   private Element[] hash_table;
   private static class Element {...}

   ...

   public boolean contains(Object candidate) {
       // Compute hash:
       long candHash = element.hashCode();

       // Determine the bucket to search:
       int bucket = Math.abs(candHash) % hashTable.length;

       // Walk the bucket's chain:
       for (Element element = hash_table[bucket];
            element != null;
            element = element.next)
       {
           if (element.hash != candHash) continue; // This wasn't it.

           if (ContraTest.bug("contains: no equals check") ||
               candidate.equals(element.value))
           {
               return true; // Candidate is present.
           }
       }

       return false; // Candidate is absent.
   }
}

Here again, Petra recognizes — with her white-box knowledge — a mistake a developer could easily make, and which the tests should consequently check for: Two key objects can have the same hash code yet be different.

Back from examples

I’ve illustrated the idea with two developers; in practice, the same person can of course write both tests and contra-tests. In that case, of course, the question which the program writer asks herself is not likely to be "what haven’t the test writer thought about?" (or why indeed not?) but rather: "what have I thought of but possibly got wrong anyway?" — much like when one developer writes normal unit tests for his or her own code.

Now, why might this testing approach work better than the status quo?

One argument for contra-testing has to do with confirmation bias: it’s like the difference between asking "prove that my program works" and "this program has one small but significant bug. Find it." Given that all software contains bugs, the latter question is obviously the correct one to ask.

Furthermore, having pairs of tests with a single variation and with opposite expected results is generally good practice, as it heightens the probability that you’re testing what you think you’re testing. Testing on both sides of a boundary, and expecting different results, tends to be a very good idea.

The contra-tests also give useful input to the question, "when have we tested enough?"

What might the consequences be for which unit tests are written? The above examples give reason to believe that there might be a greater weight on non-functional tests such as tests of performance/algorithmic complexity and thread-safety. Also, the trickiest part of the code, the special cases which were hardest to express in code, and the hardest-gained insights of the program developer would probably be better assured to get attention — because the program developer is most acutely aware of these areas of the problem. Which would be a very good thing, because for the same reasons, these corners and program properties would be most likely to deteriorate later on in the program’s life.

Finally, especially if contra-testing is carried out with program writer and test writer being separate persons, I suppose there could be an effect on these developer’s testing mindset in general. This suspicion is purely based on the above examples, though.

Not all new

I haven’t yet had the chance to try out contra-testing in practice, but I find the idea interesting — perhaps you do too, now.

And as I’ve mentioned, the idea is not all new — few ideas usually are.

As for the related preexisting techniques I mentioned earlier: Mutation Testing and Bebugging are both about assessing the adequacy of a given test suite, and/or estimating the number of remaining, uncaught bugs.

Bebugging involves manually injecting a known number of bugs, seeing what proportion of of those are caught by the testing process, and using that number to extrapolate from the number of real caught errors to the number of unfound errors.

Mutation testing, on the other hand, is about automatically generating program variations (each of which may or may not be faulty) and see in how many cases the test suite catches the difference. This translates into an adequacy score of the test suite. Thus, this method in effect works as an improved coverage test, measuring not only if all parts of the program is exercised, but also whether the effects of each part of the program are in fact (directly or indirectly) checked by the tests.

The main drawbacks of mutation testing is that it’s a resource-intensive process, and that many of the generated variations may be semantically equivalent to the original program, and this cannot be detected fully automatically.

As far as I can make out, neither of the two techniques are meant for continuous testing, and for being a permanent and integrated part of the development process. Thus, contra-testing may still be not all old news. I guess another name for it would be "Continuous Bebugging".

Given time, I’ll see if I can get some level of JUnit or TestNG support for contra-testing going. (Yeah, like that’s going to happen…) In any case: If you decide to try this testing method, please let me know your experiences.

Testing distributed-store algorithms

This is a follow-up to my post on a datastructure for storing collections in Riak.
While I have been planning this follow-up, Kresten Krab Thorup has actually gone ahead and implemented the algorithm (on GitHub; see src/riak_column.erl) — which suites me nicely, as I haven't written a single line of implementation and am not really past the thinking stage yet :-)
To wit:

Shortly after writing the post, I discovered a couple of issues or finer points, both of which have to do with the fact that different rows in Riak live independent lives —  they are independently versioned, and no cross-row guarantees are given — specifically, nothing can be concluded from the read order: if one client A updates row X, then row Y, then another client B may see the Y update and later see the old version of row X.

(If Riak is set up with appropriate consistency settings, such that the majority of the replicas of an object are written synchronously, then you do have indirectly some sort of guarantee. Below a certain threshold of machine and/or network problems, that is.
But even so, nothing can be concluded from the read order if there several clusters set up with cluster-to-cluster replication: changes on different keys in one cluster arrive at the other clusters in arbitrary order.)

This leads to at least the following issues:

1. Firstly, when splitting a row into two, I included this step: "Write an empty row back under the original auxiliary row key".
   In fact, doing that would be wrong. Even writing some tombstone dummy value in the old row would be a bad idea; instead, one should simply mark the row as obsolete while keeping the old data. This is necessary because a client accessing the collection later on may see from the master row that the old row has been split, but not see the new rows. Or it may see the old row, but not the change in the main row. In the former case, it is necessary that at least the values in the old row be available (or the collection would suddenly have shrunk); in the latter case, it would not be apparent that the values in the old row are obsolete.
   
   
2. Secondly, after modifying an auxiliary row, the main row should be updated — even nothing in it has changed. This may sound silly, but is the easiest way to ensure that, in the event of a concurrent row split, the auxiliary row in question is taken into account at a subsequent merge (indeed, that the merge is triggered at all).
   
   
3. And even that is not enough if there are more than one cluster: At the time of the read repair of the main row, the update for the auxiliary row may not have arrived - and it may therefore be lost silently. It appears that some kind of versioning of the auxiliary rows is necessary; with such versioning, we can tell when repairing the main row that we're missing an update on the pre-split auxiliary row, and that the reference to it should therefore be kept in the main row, so that it can be repaired later when all information is available.

Ah, the perils and challenges of incomplete information.

Managing concurrent subtlety
As the saying goes,

Meddle not in the affairs of concurrent systems for their ways are subtle, and are quick to anger.
-- Tolkie(error: timeout)n

In a domain as subtle as this — with gotchas in the style of the above mentioned issues, how can we ever convince ourselves that a scheme like the one for Riak collections are implemented robustly and correctly?

As always, there are two ways: Formal verification — proving that the program is correct; and thorough testing — gaining confidence by exercising the program.
Both have their advantages and disadvantages.

If I were Dijkstra, I'd develop a formal proof (as he did in quite a few of his blog postings), and probably modify the algorithm appropriately along the way. I, however, am no Dijkstra, do not believe to have the time to develop a formal proof — nor do I have any delusion of being able to write anything worth reading in the process. Luckily, going the other way, through testing, have something going for it as well:

• It is not always clear which guarantees the components we build on actually provide. That mean that, regarding formal proof, the set of axioms may be uncertain.
• The same test can be applied to different implementations of a component.
• The same test can be applied to different versions of a component — i.e. if we modify the code, we can cheaply gain some confidence in the modified version.

For both formal verification and testing goes that the answers you get depend on the questions you ask.
When proving a property, you prove only that property; when you test a concrete call sequence with concrete values, you test with only those values.
Which is of course a good reason to get familiar with property-based testing — which lies somewhere in between the two in that it tests a property on a number of concrete call sequences — typically a few hundred, and typically different instances for each time a test is run.

This can be a nice compromise between formal verification and hand-rolled test cases — provided of course that the properties and the instance generators are chosen well.
As always with testing, paranoia and imagination is key. But you get more value for your paranoia when it's used to power random test case generation.

For the problem in question, and assuming an Erlang implementation like KKT's, property testing can be done with relative ease using a tool like Quviq QuickCheck or Proper. Their support for testing state machines comes in handy; I've not tried using it before, but this seems a good occasion.

How to test randomly
Randomized testing involves abstracting over usage scenarios.
How the abstraction is done determines what will be tested.
Knowledge of the problem domain is the primary guide; paranoia together with perhaps knowledge of implementation details should provide additional input.
What must be considered is:

• What is tested:
  Which API functions to exercise?
  Which invariants to verify?
• How it is tested:
  Test concurrent use to check for thread safety?
  Test with invalid inputs?
  Should certain special circumstances be simulated - e.g., file I/O errors, disk-full conditions, network delays, packet loss?
• With what it is tested:
  Test with abnormal (very long/short/high/low) inputs?
  Key collisions?
  Many values for the same key?
  Keys which are nearly identical?

This is of course where the imagination and paranoia enter the picture.
You can't assume that "since we generate the values randomly over a large domain, we exercise all code paths" — exercising e.g. a dictionary with a million randomly generated keys is of little use if the keys never collide.

How to test distributed collections
OK then, how to test an implementation of the distributed collections scheme?
Using the state machine testing support of Proper, we can maintain a "model" collection aside the subject-under-scrutiny collection (shortened to SUS in the following).

What to test:
This is the easiest part: We will test the usual collection functions: insert, delete, lookup, list keys.
The invariant is that the result is consistent with the same operation performed on the model collection — as defined below.

How to test:
We'll certainly need to test concurrent use. Let's say that there are three simultaneous users of the collection; we know that there are subtleties involving two, and there may be additional ones involving at least three.
The users won't be really simultaneous, though — We will test concurrent use in a way where the concurrency is made explicit. This provides repeatability and insight into why things fail, which is indispensable for this problem domain.
So, instead of having an actual underlying Riak store, we'll mock it up, in such a way that the mock provides just the guarantees we actually expect the real thing to provide.


Model representation
The structure I have in mind is: the mock remembers all versions of all values put into it. This is what the entire simulated multi-cluster store — let's call it the "cloud" — has ever seen.
The mock furthermore has a number of "views" of the store, corresponding to what you would see if you accessed the cloud at different points. It has a number of these; we'll make the assumption that in any of these views, for any given key, the version will only increase with time. I.e. we do not expect the version of any value in any view to evolve backwards. The mock keeps track of the view-to-version mapping for all keys.

One thing that can happen, then, beside operations on collections, is that value versions find their way from one view to another. Also, version merging can happen in transit — the versions being merged are not necessarily the latest value in any view, but may be any versions that have ever existed in the cloud.
For simplicity, let's say that this is modelled with views also — if we allow enough views, this won't reduce the generality.

The model thus consists, not just of a simple collection, but of an abstract model of the storage cloud.
Beside the externally visible events — the calls to the collection API — there are internal events: a given version of a given key finds its way to one view to another. Both kind of events go into the randomly generated test scenario specification.

The test
It was originally my intention to end with putting all of this together in a Proper-based Erlang unit test — it would then be a good occasion for me to get experience with the state-machine modelling support (link: state machine part is  from p.26).
However, it appears that I have a latency-vs.-completeness tradeoff to make, so I'd better stop here, publish what I have, and hope to return to the subject soon, hopefully with some concrete code. (While this posting has been under way, naturally other topics have come up which I'd like to write about; the order in which further postings arrive here is undetermined...)