Frequency-Based Test Strategies with NModel

As I have shown in my previous post, NModel is a viable framework for model-based testing and analysis of software programs. In this article I explore various possibilities to develop test strategies that can be implemented for the ct.exe tool of NModel.

How testing works with NModel

The idea behind testing with NModel is very simple: the test developer constructs a model of the system under test and then constructs a test driver which translates the state transitions into actual commands upon the system under test. NModel is capable of traversing the state space of the model while issuing the calls upon the system under test via the test driver.

If the state space is small and the total number of paths throughout the state space is manageable, then it matters less how the paths get generated since NModel will eventually generate all the possible paths (i.e. test scenarios).

Usually the state space is extremely large so, in real life, it matters a lot how the paths get generated. The NModel element controlling the manner in which the paths get generated is called test strategy. NModel comes with one strategy out of the box but the test developer can build other strategies on his own.

The IStrategy interface

This interface forms the basis for any NModel test strategy. It has the following declaration in C#:

// code extracted from the “NModel book”
namespace NModel.Conformance
{
    public interface IStrategy
    {
        Set<Symbol> ActionSymbols { get; }
        IState      CurrentState { get; }
        bool        IsInAcceptingState { get; }
        void        Reset();
        bool        IsActionEnabled(Action action, out string reason);
        Action      SelectAction(Set<Symbol> actionSymbols);
        void        DoAction(Action action);
    }
}

The methods of IStrategy are self-explanatory (for information on these methods see the “NModel book” at page 201 and following). The most important method of the interface is SelectAction(Set<Symbol>) since this method dictates how the ct.exe tool chooses actions during continuous testing.

The Strategy class

This class is the “standard” strategy offered by NModel. When selecting an action it simply makes a random choice. While this strategy is simple and it ensures a pretty good state coverage, it may be inefficient: there is nothing to prevent that a state gets selected over and over again. Circumventing this disadvantage means to record the visited states one way or another.

The following sections explore possible ways to do that recording.

A dead path: storing the state paths

The simplest way to avoid repeating the same states over and over again is to check the current state path (which is the chain of states starting with the initial state and ending with the current state) against previously generated state paths. Tempting as it is, such strategy fails for any non-trivial program: while the number of states may be large, the number of state paths is usually huge.

Numeric escape: using frequencies

Storing entire state paths means, in fact, storing too much information. If we settle for less when it comes to the assurance of not duplicating the paths, then it’s possible to store less information while still keeping a high chance of path non-duplication.

Any state path is nothing else than an ordered collection of states. Obviously we want to generate different, new collections with each step without keeping the whole collection. How can we do that?

The idea is to replace the collection of states with another piece of information which maintains - at least partially – the identity of the collection without the aid of elements. There is more than one solution to this problem, yet a very simple one is based on frequencies: if we choose the state that hasn’t occurred much lately then it’s a high chance we do not generate a previously generated state path.

Frequencies have two big advantages: are fixed in size and are very easy to update. State frequencies can be considered in various ways. The next sections reveal those ways.

Brute state frequencies

  Since the state path is made of states, it is plain natural to consider brute state frequencies first. This means that the method SelectAction(Set<Symbol>) selects the action leading to the least frequent state. Upon encountering more than one state of the lowest frequency the strategy may choose randomly - hence increasing the chance of non-duplication.

This solution looks better than keeping whole paths yet the problem is not solved: the number of states may still be very large, virtually infinite. Maintaining a dictionary of state-frequency pairs simply does not scale for real-life cases.

This problem has a solution if we think that a state doesn’t come from nowhere. A state occurs from one of the following sources:

1. it is specified as an initial state of the abstract state machine.
2. it is obtained from another state by applying an action upon the abstract state machine.

So, for any given state S, there is a correspondence between the next state and the action applied upon the state machine while being in state S. This correspondence leads to another use of frequencies which has the merit of scaling to any number of states - hence for any abstract state machine – despite being less precise than state frequencies.

Action frequencies

The idea is simple: method SelectAction(Set<Symbol>) selects the least frequent action from the list of eligible actions. Upon encountering more than one action of the lowest frequency the strategy may choose randomly - hence increasing the chance of non-duplication.

Unlike state frequencies, this method does scale since the number of actions is fixed for any given model. So, space consumption is O(1).

Balancing actions against states

Choosing the next action based on action frequencies is simple and practical but it has a major drawback: not all actions are created equal. The number of states they generate vary greatly – especially that, in the case of NModel, action methods accept arguments, hence there is a very wide range of changes that each action is able to perform upon the state machine.

To make the things more clear, let us consider two actions A and B, both applicable upon the same state S. Let us assume that A generates 100 states and B generates one state only. Let us assume that any time we choose an action we increment the appropriate frequency number by 1.

It is quite obvious that this policy favors B against A with a ratio of 100 to 1 since the state generated by B has 100 times more chances of being elected than any state generated by A. So, differentiating between A and B in terms of chances of being elected is a must. The simplest way to do it is to take into account the number of states that each action generates.

Unfortunately, it is nearly impossible to accurately predict the number of states generated by an action because:

1. the number of states generated by an action may depend upon the previous states.
2. action methods may have parameters and the number of generated states may depend on those parameters in ways that make any prediction very hard to make.
3. the states are not equally important. For instance, out of the 100 states generated by action A, most likely the number of truly interesting states is smaller (say, 20), all the other states being variants of the interesting cases.

So, instead of using the exact number of states generated by each action, we may use an action weight – representing an estimate of the number of relevant states that each action produces.

With this weight taken into account, using frequencies is easy: each time an action gets selected, its frequency number gets incremented by 1/weight in the stead of 1. Obviously, the frequency number cannot be an integer anymore.

Some recollection: using pairs

The method of using action frequencies is simple and practical yet it ignores the previous history of actions completely. We don’t want to record the whole previous history (otherwise we end up with the full path problem from above), but we might need to recall the last state and/or action  and include it into the computation of frequencies.

In other words we might want to use frequencies of pairs. Pairs of what? The next sections will tell.

Frequencies of state-action pairs

We can keep frequencies of state-action pairs in the stead of action frequencies. However, because the number of states that a certain action can act upon may be large, we can do the following:

1. compute H(S) where S is the state and H(S) is a numeric hash value for state S.
2. replace state S by the value H(S) % K (remainder of the integer division H(S)/K) where K is the maximum number of distinct states that we want to keep in consideration.

With this method, space consumption is something like O(K) which is still O(1) for a constant K.

Frequencies of action-action pairs

If using the threshold K seems arbitrary, then keeping frequencies of action-action pairs is another option. This means that the strategy keeps the frequencies of (A1, A2) pairs where A1 and A2 are actions that may occur in natural succession during continuous testing.

With this method, space consumption is something like O(N2) which is still O(1) since N (the number of actions) is constant.

Added benefit: knowing how you’re doing and when to stop

  Using frequency-based test strategies with NModel has the added benefit that we know all the time how many times each action has been called. One can use this information to develop various test metrics and policies to stop testing or evaluate the quality of testing:

• the average frequency of action calls gives a clue on how well the implementation has been tested. For example, if we have a test run with an average of 10 calls per action and another test run with an average of 10000 calls per action, we can assume that the latter run has been 1000 times more thorough than the former.
• individual call frequencies may tell when to stop. For instance, one may choose to stop when each action has been called at least 10000 times, or when the average frequency is 5000 with a lower limit of 1000 calls per action.
• one can get a clue in real time about the dynamics of continuous testing by following the evolution of action frequencies over time. For example, if a certain action lags behind its peers then it is obvious that a certain part of the state space gets under-tested. In such case, refining or replacing the test strategy is quite necessary.

Conclusions

Continuous testing with the ct.exe tool of NModel is a viable method to achieve high quality testing with low costs. NModel offers to the test developer the possibility to develop new test strategies within this framework.

Selecting the next state based on frequencies is a simple yet effective method to ensure a wide variety of action calls with the added benefit that the accumulated numbers may form the basis for various quantitative and qualitative metrics.