Wednesday, July 6, 2011

T-wise combinatorial Model-Based testing – Part I

One of the strengths of Model-Based Testing is the ability to generate combinatorial inputs from a model. Say for example we are using a black-box testing approach on a scientific implementation of the inverse of a multi-dimensional matrix function:
The SUT is designed to compute the inverse of f(x,y,z) for any value of x, y, z. We may state the test invariant that
Which states that the matrix product should not differ from the identity matrix by more than some small residual error. The nice thing about matrix inverse is the relative simplicity in verify the correctness of the implementation, because direct matrix multiplication is simple.

The actual setup is somewhat constructed, but it serves as a good example. The point is that we are testing an implementation on a multi-dimensional function (in this case 3-dimensional). Keep in mind that the SUT could be any function that requires more than one input.

The way I would like to model this, is using three rules for setting x, y and z and one for performing the computation which is then also validated as given by our test invariant. The model code looks like:
    static class ScientificModelProgram
        static int ParamX = 0;
        static int ParamY = 0;
        static int ParamZ = 0;
        static bool computed = false;

        [Rule(Action = "SetX(x)")]
        static void SetXRule(int x)
            ParamX = x;

        [Rule(Action = "SetY(y)")]
        static void SetYRule(int y)
            ParamY = y;

        [Rule(Action = "SetZ(z)")]
        static void SetZRule(int z)
            ParamZ = z;

        [Rule(Action = "Compute()")]
        static void ComputeRule()
            computed = true;

        static bool Accepting()
            return computed;

Using this model we can generate any input combination for the “Compute” function. Of course one problem is that we allow all inputs for the “SetX” rules. We can limit the range in the config.cord file by including a parameter combination:

config ParameterCombination: Main
    action abstract static void ScientificFunction.SetX(int x)
        where x in {0..2};   
    action abstract static void ScientificFunction.SetY(int y)
        where y in {0..2};   
    action abstract static void ScientificFunction.SetZ(int z)
        where z in {0..2};   

Which limits the input range to 0, 1 or 2 in all dimensions. However, when exploring this model we still observe that the state space explodes:

So, what happens here? Well, even though we are limited to three inputs per dimension, we still generate 3 x 3 x 3 unique states. Essentially we are testing all possible combinations in our state space, which in many cases is complete overkill.

A practical approach to solving this problem is pair-wise testing (a subclass of t-wise testing), where you fix one input parameter and vary the two others. The rationale behind this approach is that most bugs can be reproduced by varying only two parameters, and the cost of varying all parameters together is simply too high compared to added benefit in terms of more bugs found. Using pair-wise testing the number of combinations generated is limited to 3 x 3. We can even go to 1-way testing, where only one parameter is varied.

In Model-Based Testing we can easily mimic this behavior! We can make a generic parameter class that captures the t-wise behavior:
    public class TWiseParameter<T>
        public const int TWISELIMIT = 2;
        static int ParameterCount = 0;

        private T val;
        private bool isSet = false;

        public bool IsSet { get { return isSet; } }

        public T Value {
            get {
                return val;
            set {
                if (!IsSet)
                    Condition.IsTrue(ParameterCount <= TWISELIMIT);
                    isSet = true;
                val = value;

This class keeps track of an internal static counter on the number of parameters “in play”, if it exceeds the limit set by TWISELIMIT the action is discarded – in this case we generate pair-wise tests.

Now we simply replace the integers in the model with:
        static TWiseParameter<int> ParamX = new TWiseParameter<int>();
        static TWiseParameter<int> ParamY = new TWiseParameter<int>();
        static TWiseParameter<int> ParamZ = new TWiseParameter<int>();

And the model automatically generates pair-wise tests in the three input dimensions! The model now looks much cleaner:

Exploring the generated test cases we observe the following pattern:
The model is generating pair-wise combinations in the three dimensions, just as expected. However, we also observe that it generates two test cases per input combination, because it sees SetX(1), SetY(2) and SetY(2), SetX(1) as two different paths through the model graph (which is also the expected behavior!) – the two paths are indeed distinct, but from our expectations we would not expect it to matter in what order we set the parameters. A potential fix to this issue would be to fix the order in which the model is allowed to set parameters. We could build in a rule on SetY that it must not be called if ParamX is already set, and the same for SetZ – and in this way order the parameters. However, there is a clever way of doing this, which I will explore in a later post…

We saw how the state space can be reduced using t-wise testing techniques in Model-Based Testing. The example here is constructed, but it is easy to imagine the applicability of t-wise testing when the SUT has 4, 5 or even 6 input parameters.

No comments:

Post a Comment