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.

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.