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.

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

I wanted to post some real modeling examples for a change, where I show how to use model based testing to explore test case combinatorics. The obvious choice is of course the more than sufficiently modeled calculator. So I decided not to choose a calculator, but something a bit different. I thought to myself, why not a simple Binary Search Tree? Hmm, but does it have any potential?

BSTs are really nice in that you can write invariants for them: 

For all nodes n in T: value(left(n)) < value(n) < value(right(n))

However, in a normal functional testing paradigm this is not entirely sufficient to validate the tree. The problem is that any given sub-tree of the BST will pass the integrity check – thus if I were to introduce a bug that removed the whole sub-tree when deleting a node from the tree, the resulting tree is still a valid BST but it’s not the expected! Normally we would need to check the node count and also that the expected values are to be found in the tree, however in a model based testing paradigm this is no longer required as we will see later on.

Finite vs. infinite state space

Okay, the first "real" post. So what is a finite state space model?
Any model that you can explore completely is by definition finite. That means you can try out every single combination in finite time (although in some cases this can be a very long time).

Opposite, an infinite model is one where the number of inputs grow infinite.

Theoretically we cannot have infinite models in a computer, because the state space will be determined by the variables in the model which all have finite ranges - but say you combine two 32bit integers, the state space explodes to 18446744073709551616 states - which is practically infinite.

In general model exploration is bound by number of states and steps, and as such we don't know if a model is infinite if it has more states than the state bound. A classic example of a (practically) infinite model would be a counter with internal state variable int x = 0, and the action Increment() { x++; }. This model will generate a state for every value x >= 0. Exploring the model gives the following result:

So basically what this means is that anytime you have numbers in your model that can take arbitraty values you have infinite state space. Bummer. Okay, but there are of course ways to work with this. Enter: Equivalence Class Partitioning - ECP is all about determining which values you consider to be different. A great example is the addition function of your calculator - say add(x,y), consider testing that: add(2,2) = 4 if this holds true, would you expect add(2,3) <> 5? Of course not, if addition works for 2 it should work for 3 as well. Thus we consider y > 0 equivalent. Likewise y < 0 should be equivalent and y = 0 is a boundary case. (really, for all practical purposes we would assume y completely equivalent).

We can apply ECP the same way to our model state variables. Instead of modeling the counter fully we could assume that x > 0 is equivalent, thus we adjust the model slightly to be Increment() { if(x < 1) x++; }. Notice that the increment action is valid from any state, but calling Increment with x = 1 does not change the internal state representation. The model is now limited to two states, x = 0 and x = 1. It is also finite under our equivalence assumption. Model exploration gives:

Closing exercise: Extend the counter model to support negative numbers using a Decrement() action and apply ECP to make the state space finite.

[1] Counter models