State-Query Models

It’s been a while since I have had time to write on my blog. In the meantime I have been busy being on paternity leave (we get 10 weeks in Denmark!), changed roles, and went through re-organization in NAV. All bad excuses for not taking the time to write blog posts – apologies for that!

I’m going to shift gears a bit from now on. We recently filed a patent application¹ on a new approach to Model-Based Testing. The patent revolves around how to apply Model-Based Testing to systems under test where state is contained in a data source, for instance a database. With this new approach models emerge from the responses of the system under test instead of through careful crafting of state-machines. This sounds very fancy, but in reality we probe the system through exercising automated action, and record how it responds by tracing the impact on the data source. With this approach a state model emerges, which has some surprisingly nice benefits.

State-queries vs. state-machines

At the hearth of the invention lies the replacement of finite-state-machines with state-queries.

Allow me to illustrate by example:

Consider a sales order in an ERP system. This is a document that has a header with some general information and some lines detailing what items/resources/etc. is being sold. A very simple model could consist of rules for creating an empty sales order, adding a sales line to the document and posting it. A typical Model-generated test case could be to create an empty sales document add a sales line and post it. However, the model could also just create a blank sales order and try to post it, which should result in an error.

To model this with Spec Explorer we would need to create a state-machine which counts the number of sales orders, and how many lines each sales order has. We would then need to build logic to increase counters whenever we create new sales orders or add new lines, and to check that we are able to post a sales order with lines.

In Spec Explorer such a model could look like:

Where the state (x:y) represents x sales orders and y sales lines. However, the information regarding number of sales orders and the number of lines on each is typically already stored in some backend database.

In our new approach the strategy is to create SQL queries that selects the relevant information from the database, instead of constructing a fictive state-machine. These so-called state-queries are then evaluated after every single rule is exercised to determine in what state the model is. In our example the following SQL query would select all relevant state-variables directly from the system:

SELECT

       h.[Document Type],
       h.[No],
       COUNT(*) AS "No of lines"
FROM
       [Sales Header] h
LEFT JOIN
       [Sales Line] l
ON
       h.[Document Type] = l.[Document Type] AND
       h.[No] = l.[Document No]
GROUP BY
       h.[Document Type],h.[No]

An example execution of this query could yield the following dataset:

The resulting dataset contains all the information the model needs to determine if it can add lines or post sales orders, and it was generated at runtime by directly querying the database.

Simulating Stochastic Models

Recently I’ve been tasked with working on an infrastructure system which comprises several computationally intensive tasks that can be scheduled on a series of host machines. Some tasks have dependencies on other tasks, and cannot be scheduled before its dependencies have finished. In a simplified setup we assume that any task can run on any machine, provided that machine is not busy with running another task.

The following picture illustrates the system

Host A runs task 1 and 3, while host B runs task 2 and 4. Task 4 has a dependency on task 1 and task 3 has one on task 2. When all tasks are completed the job is considered completed. It is evident from the picture that a task (task 3) may be delayed in its scheduling even though its dependencies are satisfied due to resource constraints.

Solving ‘The Monty Hall Problem’ using Models

Today is about my favorite probability puzzle – The Monty Hall problem. If you haven’t heard of it before you are in for a treat. The problem stated goes as follows (from Wikipedia):

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats*. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat**. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Vos Savant's response was that the contestant should always switch to the other door. […]

Many readers refused to believe that switching is beneficial. After the Monty Hall problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming that vos Savant was wrong. (Tierney 1991) Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept that switching is the best strategy.

*The probability of the car being behind any door is uniformly 1/3

**The door that is opened has to have a goat behind it, and it cannot be the one you picked initially, in case the host has multiple choices it is assumed that s/he chooses uniformly at random

The problem is brilliant in its simplicity and the correct answer feels extremely counter-intuitive at first. The natural tendency is to think that it makes no difference whether you switch or not – but the truth is that you should switch! And hopefully once you are done reading this article you will be convinced why.

Can your tests stand the ‘test of time’?

Today I want to digress a bit from Model-Based Testing and talk about a general issue in software testing, applicable to all types of testing. My focus will be on the use of time-dependent methods in test code. These include library functions like ‘DateTime.Now’, reading the BIOS clock, retrieving the current time from a time server, etc. The use of time dependent methods can lead to unpredictable behavior and is a common source for fragility in tests.

But first, let’s look at a definition of time. From Wikipedia:

Time is the indefinite continued progress of existence and events that occur in apparently irreversible succession from the past through the present to the future.

There are two vital pieces of information in this definition. They are continued progress and irreversible. There is nothing about size and quantity of time in the definition. In fact our daily representation of time in hours, minutes, seconds, milliseconds, etc. is completely arbitrary. Instead I like to think of time in a mathematical sense, as a strictly increasing series t : t_i < t_i+1. The absolute value of t_i is irrelevant.

This is how I believe time should be view in test code, in fact I will postulate a “test of time” at the end of this article.

I will assume that we all agree fragile tests are costly to maintain, and have no place in a regressions suite.

Common misuses of time #1: Validation of time-dependent data

Common misuses of time is validation of messages, dialogs, errors and other strings containing the current time generated by the system under test. I recently saw a test case validating a text containing the latest updated time of a graph. The test would look something like:

            graph.Update();

            String expectedMessage = String.Format("Last update: {0}", DateTime.Now.TimeOfDay.ToString(@"hh\:mm"));

            Assert.AreEqual(graph.StatusMessage, expectedMessage, "Incorrect status message displayed");

Modeling Multi-Threaded Applications

So last time we looked a bit at stochastic modeling and I introduced the concept in Spec Explorer for modeling random actions/decisions. The example we looked at was a stochastic counter – which is just a tiny bit contrived. Actually, I can’t think of anywhere I would like to use a stochastic counter. Thus, I want to spent some time modeling a real stochastic example in this post.

A very common use of stochasticity is multi-threading/parallel processing. In a parallel system more than one thread can work on solving a problem at the same time (often running on multiple CPUs at the same time). So why does this have to lead to stochastic systems? – you may ask. The fundamental answer to this question is timing. In a parallel environment, to make full use of system resources, you poll a pool of threads for the next available worker thread. Whichever thread is available is determined by “chance”, because it is impacted by the speed of the executing CPUs, latency of external dependencies (RAM, BUS, network, disk, etc.) which we (usually) cannot control.

Consider a fictitious parallel environment with 3 worker threads:

This component is used by assigning the Job Scheduler a Job to be processed, then the scheduler will hold this job in its internal queue and await a worker thread to be available, once a thread is available it will take the incoming Job and start processing it in its own execution context (i.e. CPU, RAM, etc.). After successfully processing the Job the worker thread stores the result in an aggregated result list (which has to be thread-safe).

A very common sunshine scenario to test would be to give the Job Scheduler a single Job and check that a worker thread starts working on it and finally check the result from the aggregated result list.

Modeling Stochastic Systems in Spec Explorer

One of the more advanced – and powerful – features of Spec Explorer is its ability to handle stochastic SUTs. Stochasticity is common in systems with external dependencies, this could for example be the file system, network interface or external devices. Common for all these dependencies is that they sometimes fail for various reasons. You cannot predict when this will happen, and for the most part in Software testing we strive to avoid these spurious behaviors at all cost.

Another source of stochasticity is the use of random in the SUT (which I will explore a bit more in this post) or stochastic behavior due to race-conditions in multi-threaded applications (which I will investigate further in a later post).

First of all, what does a stochastic model look like? Take a look here:

This picture represents a model of a stochastic accumulator. It shows a slice where the accumulator is increased twice then reset. Each addition is stochastic in that it can add either 1 or 2 to the counter.

When working with stochastic models, in addition to the normal “round” states, Spec Explorer introduces diamond-shaped decision states. Each diamond represents a choice in the model where the SUT can behave in one of many ways. In the case of the stochastic accumulator we can see that the value of the accumulator can go from the initial value of 0 to either 1 or 2 in the first addition step.

Collateral code coverage, ramifications on Model-Based Testing

My relationship to code coverage is one of love and hate. I love code coverage because it’s a quantitative metric which tells you something about the relation between your tests suites and your product code. I hate code coverage because it must be the most widely abused metric in software testing. For more on this check my previous post on ‘Application of Code Coverage to Model Based Testing’

So why is code coverage so bad? There seems to be a strong drive from management to reach high coverage numbers (which is great, it reduces the risk of having test holes). But then it’s often related to the quality of the product – almost as the only metric of quality. The critical problem with this approach is that code coverage tells you nothing about whether the code is correct or not – only that it was exercised.

Let me coin a new term here: Collateral code coverage.

Definition: Additional code coverage from executing a test compared to the minimum possible code coverage required to validate the behavior being tested. In other words, the amount of code coverage where the result of exercising that code is never verified by the test.

Let me illustrate by an example. Consider a small program that converts an input value in kilometers to miles. The program consists of a Windows form application that calls a class library component that converts the value and displays it on the form. Say we want to test that this sample application converts the input value 1 km correctly to 0.62 miles we may develop a unit test that calls the class library directly with the input value and output values:

        [TestMethod]

        public void TestConversionOfKilometersToMiles()

        {

            Assert.AreEqual(0.62, Converter.KilometersToMiles(1));

        }

But it’s equally common to use a UI based test framework which enters the value and presses the convert button and then reads the computed value from the output field (equally common, but extremely more complex…), which could look like:

        [TestMethod]

        public void TestConversionOfKilometersToMiles()

        {

            Form.Kilometer.SetValue(1);

            Form.ConvertButton.Click();

            Assert.AreEqual(0.62, Form.Miles.GetValue<decimal>());

        }

The tests have the same purpose and the same level of validation, but the UI based test will cover considerably more code than the unit test. Since the purpose of both tests is simply to validate that the converted value is correct, the additional coverage from using the UI based approach is considered collateral.

Complex types in immutable containers and ‘magic rules’ – TSM Part III

In part II we saw one approach to optimize the growing algorithm by using a more intelligent concept for extending graphs, than the brute force way of part I.

With the new approach implemented we can now lift our restriction on the input domain size. Effectively there is no need for constraining the grid domain when the algorithm works on the edges instead of grid input combinations.

The original implementation converted vertices and edges into integer representations (using index = y*size + x), but this approach is no longer applicable when the input domain is unbounded. The first step in fixing this is to refactor the model to store vertices and edges as structs instead:

    public struct VertexData

    {

        public int x, y;

        public VertexData(int x, int y)

        {

            this.x = x;

            this.y = y;

        }

    }

    public struct EdgeData

    {

        public VertexData v1, v2;

        public EdgeData(VertexData from, VertexData to)

        {

            this.v1 = from;

            this.v2 = to;

        }

    }

A SetContainer can take a struct, such that our definition of active vertices in the model changes to:

        static SetContainer<VertexData> vertices = new SetContainer<VertexData>();

Because structs are simple data structures instead of object the SetContainer will correctly identify permutations of the same sequence as being equivalent, whereas had we used the Vertex class directly, the SetContainer would be storing object references instead of the object data and sequence would matter.

Re-Modeling the Traveling Salesman – Part II

Last time we had a look at a very crude model for growing graphs for the Travelling Salesman Problem (TSP). I neglected to actually visualize what the solutions looked like, so here is a rendering of a couple:

Not very complex indeed... So what seems to be the problem here? Well, the model itself is very exhaustive, so it will generate any conceivable graph on the input domain. The single model rule is generic on the full input domain:

config Grid20x20: Main

{

    action abstract static void TravelingSalesman.InsertVertex(int x, int y)

        where x in {0..19}, y in {0..19};

}

This means that for each state Spec Explorer will try X * Y rules, so for larger input domains like 20x20, it takes forever to explore a state fully. What we are interested in with the TSP is not to construct a plethora of simple graphs, but to generate high complexity graphs (because they are much harder to solve). So what we need is a depth-first search (DFS), luckily Spec Explorer allows us to do just that using a config switch:

config Main

{

    ...

    switch DepthFirst = true;

    ...

}

Unfortunately it turns out that the DFS exploration uses an “optimized” version of DFS, causing it to always fully explore each state it visits, instead of immediately exploring from newly discovered states. Not that it’s going to show the extra states that got explored, they are simply hidden away until they get fully explored much later in the process (sorry, guys but that’s just silly). Anyway, that is exactly what we wanted to avoid, because even when using DFS exploration on a 10x10 grid it will take hours to generate graphs with 10 vertices.

Modeling the Traveling Salesman

I’m going to attack a well-known problem from the 1800 century in this post: Traveling Salesman Problem (TSP).

The objective in the traveling salesman problem is to find the shortest path through a network graph visiting every node/vertex exactly once and returning to the origin, such a path is called a tour of the graph (or a Hamiltonian cycle if you are into computer science). The problem is NP-hard to solve, meaning it is likely that no feasible exact solution exists for large graphs. There exist a lot of variant on the traveling salesman problem. I will consider the form of the problem in which the graph lies in a plane, also known as the Euclidian TSP. This puts constraints on the distances between nodes and is a symmetric formulation of the problem. But still, this is an NP-hard problem.

To put things into perspective, the number of distinct Hamiltonian cycles through a graph is:

Enumerating all possibilities becomes infeasible for even small graphs. For n = 21 the number of solutions is 1,216,451,004,088,320,000. For the case of n = 101 the number of solutions is approximately 9e+157 which exceeds the approximated number of atoms in the known universe. Of course, I’m not claiming to solve this problem – actually I’m not trying to solve it at all. Many better people have tried that before me. I’ll however focus on testing a TSP solver. It may be exceptionally difficult to solve the problem, but it is possible to construct graphs for which the solution is known (and non-trivial) without too much effort. A model for that could look like:

I plan on doing a series of posts on this problem. In this first post I will define the problem and the method in which I’m constructing a graph for the TSP. In the following posts I will investigate different models for growing TSP graphs, and look into how they perform.

Model Slicing with Spec Explorer

It’s been some time since I had the chance to blog on MBT. January 2^nd 2012 my second son was born, and I’ve been on three weeks of paternity leave. Since then I’ve been too busy at work to squeeze in time to play with MBT, but now I’ve finally managed.

Today I want to talk about model slicing which is one of the more advanced features of Spec Explorer. Slicing is extremely powerful, because it allows you to build your models very generically, and then create many slices of that model with differing purposes.

I’m going to show some very simple examples on how slicing works, and then I will dig up the Binary Search Tree model to illustrate how this would work in practice.

Slicing

For my example on slicing I’m going to construct a very simple model. The state is one integer variable, and I have two rules defined the following way:

        [Rule(Action = "A()")]

        static void A()

        {

            value *= -1;

        }

        [Rule(Action = "B()")]

        static void B()

        {

            value++;

        }

Rule “A” flips the sign of the value and “B” increases it by one. The state space of this model is infinite. If you explore it you get something like: