Application of Model Based Testing to a Binary Search Tree - Part II

Okay, today I want to wrap up on the model based testing of the binary search tree implementation I did last time. Remember how we uncovered a problem that the model did not cover all of the code? Drawing from our experience from the Application of Code Coverage to Model Based Testing post we understand that our model does not reflect closely the actual implementation, and we have a risk in terms of a test hole.

Understanding the problem

Before we jump in to adding additional tests, let’s try and understand what the problem really is. Remember I hinted that it has to do with our choice of container in the model. So let’s try to understand this some more by building some trees from the model:

Notice that even though these three trees are very different constructs, the internal set representation of the model reads (0, 1, 2) for all cases.

Essentially this means that the model is not able to distinguish between these different constructs of trees. When exploring the model Spec Explorer seeks to exercise each state transition only once. Relating this to our model, this means that Spec Explorer will build trees in different sequences (e.g. Add(0), Add(1) are different actions from Add(1), Add(0)) even though the end state is the same, but now it will only execute action Remove(0) for one of the cases, because these actions are equivalent. In other words, Spec Explorer thinks Add(0), Add(1) ends up in an equivalent state to Add(1), Add(0), it will only try executing removing actions from one of the tests – say Add(0), Add(1), Remove(0) (it believes the test Add(1), Add(0), Remove(0) is redundant).

In fact for BSTs the layout of the tree makes a significant difference to how the Remove action is performed as we will see, and in that respect our model is critically flawed.

Improving the model

One thing we noticed is that it matters in what sequence we add nodes to the tree, and our current model does not recognize this because it uses a SetContainer to store which nodes were added. To solve this we simply change it to use a SequenceContainer. This is an easy fix, simply change:

static SetContainer<int> values = new SetContainer<int>();

To

static SequenceContainer<int> values = new SequenceContainer<int>();

Now the trees are not only represented by which nodes are stored in them, but also in what order they were stored. Thus the model will see the tree (0,1,2) as being different from (1,0,2) – and it will generate tests that remove nodes from both constructs.

The explored model looks a bit more complicated:

This is of course to be expected, as we added more complexity to the problem. Also instead of generating 17 test cases, we now get 33 tests (you need to increase step and state bounds to around 4096). If you run the 33 tests against the original BST implementation you will find that they all fail! Don’t be alarmed there’s nothing wrong with your model! It is my implementation of the BST that is horribly wrong!

I snuck in an additional bug, that when replacing any node in the tree the siblings of the deleted node are not included in the resulting tree. So you see – you really need to be careful when applying model based testing (our original set of 17 tests did not find this bug!), even to simple problems like this, one detail that seems minor on the surface (which container to use) could potentially allow profound bugs (data loss!) to creep in.

Code coverage

Now to the code coverage analysis part (I changed the implementation a bit when fixing the above bug, so it’s difficult to compare with the previous post)

Okay – now we obtained 95% coverage – not bad! But it’s still not 100% – so what is missing?

First of all, the method CheckIntegrity has missing coverage, but this is because it never finds a tree that is invalid, so we can ignore that. The remaining interest is the Remove method – it contains one line of code that is not hit. As it turns out this code is only executed when the tree has to search more than one level down to find a replacement node upon deleting.

For this special case the node being deleted must have both a left and right sibling and in addition the right sibling must also have a left sibling – wait a minute… how many nodes was that again? Yes, 4… so here’s the problem, it is simply not possible for the model to construct such a tree because it is limited to using 3 nodes. To cover this scenario, we would need to extend the model parameter ranges to Add and Remove from 0..2 to 0..3. This is very easy to do, however now the state space explodes completely (~500 states). Were you to generate the tests, you would end up with 193 test cases.

Remember I talked about the diminishing coverage per test case? – this is exactly it! To gain just one additional line of coverage the model will add 160 tests (and probably 156 of them are redundant).

A much better solution would of course be to simply write some unit tests constructing a couple of different trees with 4 or more nodes and removing nodes with the above conditions.

Conclusion

Now the original model from part I may not be perfect, but still it is better than nothing, and we saw how it managed to catch 6 common bugs. It was dead simple, the model itself is around a screens worth of C# code (including comments).

The improved model was even better in that it caught another more subtle bug. However, it comes at a prize. We had to quadruple the state space of the model to generate 16 additional tests to accommodate the different tree constructs.

We even saw that this extension of the model was not sufficient to obtain full coverage of the BST implementation. In order to get this we needed to go to 4 noded trees, which would blow up the state space even further.

This is a really good example on the trade-off between the model complexity and the model coverage. In rare cases we can obtain full coverage, but in most cases we will struggle with state space explosion once we start including boundary scenarios (think about it, the model explorer will think it needs to perform every possible action from a boundary state).

My final conclusion is that model based testing is great for easily building a test suite for the bulk of the SUT, but it cannot stand alone. To be effective it must be supplemented by more specialized boundary/corner-case tests.