Model-Based Testing Using an Implicit State Model

A

Introduction

Several people have asked me about whether finite state machines (FSMs) are the only kind of state models that can be used in model-based testing. They usually mention this when we talk about modeling data-centric applications like Notepad, where the finite state model would get really huge really fast if you try to account explicitly for all the strings a user could type.

I think part of the answer to their question lies in whether you choose to model states explicitly or implicitly. This white paper addresses the difference between implicit and explicit state models.

An Explicit State Model

Excellent tools like Test Model Toolkit make it straightforward to create finite state models. And you can use the properties of an explicit state model to drive your testing in very effective, very efficient ways.

Here is a non-technical example. Suppose you are standing outside a room and you want to create a model of how many people are in the room. You cannot see into the room, but you can see when anyone goes in or out. You start off with the assumption that no one is in the room. You could create an explicit state model like the following, where the numbers in the circles indicate how many people are in the room, and the arrows show how we transition from one state to another.

It's easy to see that this model could get cumbersome to maintain by hand as the number of people climbs. One enormous benefit of Test Model Toolkit is that it relieves you of having to maintain this kind of model by hand. Instead you only need to maintain rules for generating the state model.

The advantage of the explicit state model we just created is that we now have an explicit map of the "territory" and can generate test sequences that efficiently cover all possible actions from all possible states. As one example, we could ask this model to generate a minimum length test sequence that uses all possible actions, such as this:
Action Ending State
1. 1 person enters 1 person in room
2. 1 person enters 2 people in room
3. 2 people exit 0 people in room
4. 2 people enter 2 people in room
5. 1 person exits 1 person in room
6. 1 person exits 0 people in room

An Implicit State Model

It is also possible to model behavior of a system without explicitly generating all the states as we did in the example above. The resulting implicit model will not be as powerful as the explicit model in generating traversals, but the behavior you are modeling may make it worthwhile to forego some test generation power to make the modeling easier.

Take the room example again. Instead of creating a state model, what if we just keep a counter of how many people are in the room? When people enter the room, we increment the counter by the number of people entering; when people exit the room we decrement our counter by the number exiting. When we need to know how many people are in the room, we simply read the value out of our counter variable. The rules for the model would be the same as in the explicit room model (though we would not take the extra step of generating all the states).

This is a much simpler approach than creating the state graph, though it is not as powerful at generating some types of sequences. For instance, since we do not have an overview of the whole "territory" of our model, we can't easily generate minimum length test sequences that cover all the actions in the model.