Applied Model Based Testing - Experiences & Examples

PowerShell and arrays a deceptive combination

2014-10-09T11:07:00.002-07:00

So I was reading up on PowerShell arrays on this TechNet site:

http://technet.microsoft.com/en-us/library/ee692797.aspx

It gives a brief introduction to PowerShell arrays and illustrates how powerful they are. However, arrays in PowerShell are a curious beast indeed and in some cases they can deceive you, so I thought I'd give some additional insights into it in the hopes it may save you from struggling with them for too long.

Let's start with the basics. One thing you can do with arrays is concatenation:

$a = 1,2,3

$a += 4

Now $a is 1,2,3,4. Neat.

But wait a minute… let's try changing this example a bit

$a = CommandThatReturnsIntegers

$a += 4

If CommandThatReturnsIntegers returns 1,2,3 then everything works as expected. But what if it just returns 1?

$a = 1

$a += 4

Now $a is 5… oops? What just happened? Well, in essence we expected an array from CommandThatReturnsIntegers but instead it gave us an integer. Well, we could fix it such that it always returns @(1) instead of 1, then we get:

$a = @(1)

$a += 4

Now $a is 1,4. But what if we don't control the output of CommandThatReturnsIntegers, then we are out of luck with this approach…

An alternative is to use the comma operator, like this:

$a = 1

$a = $a,4

$a now is 1,4 as we would like it to be.

Let's try that with a starting array

$a = 1,2,3

$a = $a,4

Again, when evaluated $a is 1,2,3,4 as expected. Everything looks fine right?

Now try this:

$a.count

2? Wait a minute it evaluated to 1,2,3,4 yet the number of elements in the array is 2?

Let's see what we find when we look under the hood..

$a | % { "$_" }

Here I'm telling PowerShell to produce a string representation of the content of every element in the array. The output is:

1 2 3

So, as you may have guessed already underneath the hood $a is an array of arrays.

This is a common source of trouble when piping inputs to other commands. We would expect to evaluate the command on each element not each nested array.

As an example we might want to sum the values using:

$a | measure -Sum

However, this raises the exception:

Input object "System.Object[]" is not numeric.

But then why does $a evaluate to 1,2,3,4 when we first looked at it? The reason is that PowerShell is invoking black magic to unroll the nested array on our behalf when we evaluate it!

That's pretty bad and causes much deception in PowerShell-land. But there's a plus side to this, we can leverage (abuse?) PowerShell's black magic to unroll the array for us, using the following syntax:

$b = $a | % { $_ }

Now $b is a truly flattened array. We can test this using:

$a | % { $_ } | measure -Sum

Which now gives us the expected value of 10.

The benefit of this syntax is that it will work regardless of $a is a single element, an array or a nested array.

In conclusion when working with arrays take care and try to understand what goes on underneath the hood. If you end up in a situation where the array is not behaving as expected, do not rely on evaluating it in PowerShell to inspect it's structure. Instead, use $a | % { "$_" } to see what it actually holds. In case you are working with arrays and concatenation, make sure to build your command robust by unrolling the input arrays using $a | % { $_ }.

Upgrading Windows Azure Service projects to Visual Studio 2013 does not work out-of-the-box

2013-11-01T01:54:00.002-07:00

This morning I decided to upgrade my cloud service project from Visual Studio 2012 to 2013. The upgrade requires installing the Windows Azure SDK 2.2, and then do an automatic upgrade of the project.

On the surface everything looked fine!

However, when I started deploying the upgraded service to Azure, the deployment never completed.

Having spent quite some time trying different things with the Azure deployment, I decided to try a local deployment in the emulator. I was expecting everything to work fine, but I found out that my worker role just kept on recycling in the emulator! It would call OnStart(), then Run() followed by a message that Run() completed which triggers a role restart.

The next logical step was to debug what was going on in the service, so I added breakpoints to OnStart and Run, and to my surprise the debugger never kicked in…

By then I concluded that something was completely broken. Next up, I tried creating a new service from the Visual Studio templates, which worked and debugging also worked.

After comparing the project files, I finally figured out that Visual Studio 2013 upgrade had failed to upgrade the version of the Azure references!

I had to update the csproj file and manually change the version number on the following references

Assembly	From	To
Microsoft.ServiceBus	2.1.0.0	2.2.0.0
Microsoft.WindowsAzure.Diagnostics	2.1.0.0	2.2.0.0
Microsoft.WindowsAzure.ServiceRuntime	2.1.0.0	2.2.0.0
Microsoft.WindowsAzure.Storage	2.0.0.0	2.1.0.0

After that I also had to update the same version numbers in the App.config file of the service and everything was working again.

Large Scale Machine Learning powered by Windows Azure HDInsight

2013-09-02T05:13:00.001-07:00

In this article I’m going to show how to setup a machine learning algorithm to classify documents using a Big Data analytics cluster running in Windows Azure (HDInsight).

Azure HDInsight is an easy and flexible way to provision an analytics cluster in the cloud for doing Big Data analysis. A cluster consists of 1 main node, 1 job tracker node and any number of compute nodes (workers), that are doing the heavy lifting. The cluster is backed by the Open Source Big Data platform called Hadoop. Hadoop is written in Java and it is an extensible open platform for analyzing large sets of data in a fast and resilient fashion. It’s built on top of Hadoop Distributed File System (HDFS) which is a distributed file system similar to Google’s GFS and the so-called Map-Reduce algorithm which distributes (map) work among any number of cluster nodes and collects (reduce) the result to a single output (usually stored in HDFS).

Mahout is an extension library built on top of Hadoop which enables Machine Learning algorithms to run in the cluster.

I’m assuming you have a Windows Azure subscription, if not it is possible to get free access to Azure with your MSDN subscription, which you should be able to obtain if you are a student or you can get a 1-month free trial here.

Setting up the Windows Azure HDInsight cluster

As of August 2013 you need to sign up for the preview features of Azure as HDInsight is not part of the standard Azure package, this may change in the near future when HDInsight is completed. The steps to do so are outlined here, but I’ll repeat them:

· Try to create an HDInsight data service in the Windows Azure Management Portal, it will be grayed out and instead you should see a link to ‘preview features’. Follow that link and sign up for HDInsight.

After you sign up and get a completed notification, you are ready to provision an HDInsight cluster, but first we need to setup a dedicated storage account (which is not geo-replicated)

· Create a new storage account, making sure to uncheck the georeplicated box

Now we provision our cluster

· Make a new provisioning and select HDInsight cluster under the data services category

· Pick the storage account you created in the previous step

· Select a size for the cluster (small will do just fine) and a strong password

· Click create

A note here: I’ve encountered an error when trying this step, where it fails on the second operation. I just wait a couple of minutes and retry and things work out fine. I think this is because I’m too fast after enabling the preview feature to the time I provision the cluster, but I’m not certain.

Logging onto the cluster

After the cluster is created you can find it in its own category in the Windows Azure Management Portal under HDInsight. Select your cluster and click ‘Manage Cluster’ this will bring you into an HDInsight specific portal which will look something like this:

Click the ‘Remote Desktop’ tile which will open an *.rdp file to connect to your main node.

Running Hadoop command

Once you log onto the main cluster node you should find a shortcut on the desktop by the name ‘Hadoop Command Line’. Click it to start a Hadoop prompt, which will show you some high level help:

Hadoop is the engine behind our machine learning example, so it makes sense to explore it a bit, however, I won’t go into details with it because my knowledge is limited at this point.

The fundamental functionality of Hadoop has to do with interacting with the file system. Keep in mind that in the cluster you have a completely separate file system (HDFS) which is not visible to Windows (it’s backed by the storage account you created before provisioning the cluster). Hadoop exposes functionality to work with the HDFS file system, you get to them using:

Hadoop fs -<command> <args>

File system commands have Unix names (like ls, rm, cat, etc). So to upload a file from the local disk to HDFS, you simply execute:

Hadoop fs –put hdfs_folder/hdfs_file local_folder\local_file

This will upload a local file (or folder) to HDFS and the data is now immediately available to the compute nodes. For more info about file system commands check the documentation.

Notice: The path formats differ between local path and HDFS path. The HDFS format is Unix while the local file system is of course Windows path format.

Another thing to keep in mind is that for performance reasons the HDFS file system is immutable, that means once data is placed on the file system you cannot edit it. If you did something wrong, you would need to delete the files and then recreate them.

The last thing we need to know about Hadoop is that you run command using the ‘jar’ command, which runs functionality exposed by Java packages in Hadoop. One example could be to run a word counting job to count occurrences of words in a text file. Create a new test file named mytextfile.txt and type something into it, then run the following steps:

Hadoop fs –put mytextfile.txt test/input.txt

Hadoop jar hadoop-examples.jar wordcount test/input.txt output

Hadoop fs –cat output/*

This will create a job that runs in the cluster, scanning the ‘mytextfile.txt’ for all words and returns a list of words and their respective number of occurrences in the file. In my case the input and output looks like this:

The way to interpret the output is that the word ‘a’ occurred once, ‘hello’ occurred twice, etc. The output of this command is a perfect example of a ‘vector’ where each word is a dimension in the vector and the occurrence count is the value in that dimension of the vector. As we shall see later, vectors are a recurring theme in Hadoop – large data sets are almost always represented as vectors and matrices.

This is of course a trivial example and it is complete overkill to use a data analytics cluster to run this job. However, the same principles apply to Big Data analysis it just takes a lot longer, and that’s why it’s nice to have a cluster helping you out.

Machine Learning in Azure

Time to move on to Machine Learning! The first step is to install Mahout onto the cluster. Go here, then choose the closest mirror to you and open the folder 0.8. You should see the following

Download 'mahout-distribution-0.8.zip', copy it to the clusters main node using RDP (Windows copy/paste over remote desktop works), unzip it and place the files under 'C:\apps\dist\mahout-0.8'.

Now that is in place, we can start using Mahout for doing Machine Learning. The example I’m going to run through here is that of a ‘classification’ model. This is a model that takes incoming documents (think of the in general, a document could be an email, a log file, a web-request, etc.) and tries to predict something about this document. Now this ‘something’ is entirely up to us to decide upon. For emails the classic example is to predict if an email is spam or not (we call that spam or ham). For web-requests we could try to classify if the request is legitimate or a denial-of-service (DoS) request sent from an attacker. Whatever it is we are trying to predict, the general idea is that we must provide the algorithm with a training data set in which we have told it for each document what the outcome was (e.g. spam or ham), such that the algorithm can learn from this fact.

But what do we get out of that exactly? One document on its own is not going to be very helpful, but the premise of machine learning is that you feed the model tons of training data (this is where machine learning ties into Big Data), and by churning through all this data, the model will detect hidden patterns in the data that can be used to predict the outcome of future documents (without knowing if they are actually spam or not ahead of time).

So how does this work? Let’s try to break it down. For reference I have used link [6] in the bottom to get started on this, but that introduction is based on Mahout 0.5 which is outdated by now, so I would not suggest following it.

We need to perform the following steps for making a classification algorithm:

1. Upload the input data that we want to categorize in HDFS

2. Prepare the data by converting it to input vectors (more on that later)

3. Train the machine learning algorithm

4. Test the machine learning algorithm

Creating the data set

We need a data set to train on, you could try using your own, but I would suggest running through this exercise with the sample provided by Spam Assassin as I’m doing it here.

On your local machine, create a new directory named ‘dataset’. Download the following files: ham and spam and unzip them under ‘dataset\ham’ and ‘dataset\spam’ respectively (These are ‘*.tar.bz2’ files so you need an unzip tool like Winzip or 7-Zip to extract them unfortunately). Now zip up the entire ‘dataset’ folder and copy it onto the main cluster node (use RDP again). Remote into the main node and create a ‘work’ folder under ‘c:\apps\dist\mahout-0.8\’ and extract your data files there.

Now we need to upload the data set to HDFS. Start a ‘Hadoop Command Line’ prompt and enter:

cd c:\apps\dist\mahout-0.8\work

Hadoop fs –put dataset dataset

This can take a while. After it completes, your data is now stored in HDFS in a folder named ‘dataset’.

Converting data set to input vectors

Now we need to take all of these input text files and convert them to something Mahout’s training algorithms can use – they need to be ‘vectorized’. In the ‘Hadoop Command Line’ prompt execute the following commands:

SET MahoutDir=c:\apps\dist\mahout-0.8

hadoop jar %MahoutDir%\mahout-examples-0.8-job.jar org.apache.mahout.driver.MahoutDriver seqdirectory -i /user/admin/dataset -o /user/admin/dataset-seq -ow

hadoop jar %MahoutDir%\mahout-examples-0.8-job.jar org.apache.mahout.driver.MahoutDriver seq2sparse -i /user/admin/dataset-seq -o /user/admin/dataset-vectors -lnorm -nv -wt tfidf

This converts the input text files to Hadoop vectors. So what happened here? We are telling Hadoop to load the Mahout package called ‘mahout-examples-0.8-job.jar’ (this holds the MapReduce jobs required for running the examples packaged with Mahout), then we tell it to make use of the MahoutDriver Java class which sets up everything to run Mahout commands (this is my interpretation because I really don’t know what goes on behind the scenes…) then finally we call two Mahout commands, seqdirectory and seq2sparse with some parameters pointing to our dataset.

Now the next part is splitting the resulting vectors into two sets, one we use for training the algorithm, the other one is for testing. We hide the testing vectors from the model and only after it has been fully trained, we let it try to classify the testing vectors without telling it what is ham or spam (don’t worry Mahout will take care of this for us later on).

Splitting is done using:

hadoop jar %MahoutDir%\mahout-examples-0.8-job.jar org.apache.mahout.driver.MahoutDriver split -i /user/admin/dataset-vectors/tfidf-vectors --trainingOutput /user/admin/train-vectors --testOutput /user/admin/test-vectors --randomSelectionPct 40 --overwrite --sequenceFiles -xm sequential

This splits 40% into testing vectors and the remaining 60% into training vectors. This concludes the preparation step.

Training the Machine Learning model

This is probably the easiest step, to train a machine learning model using the Naïve Bayes model run the following command:

hadoop jar %MahoutDir%\mahout-examples-0.8-job.jar org.apache.mahout.driver.MahoutDriver trainnb -i /user/admin/train-vectors -el -o /user/admin/model -li /user/admin/labelindex -ow

Testing the Machine Learning model

Also an easy step, run:

hadoop jar %MahoutDir%\mahout-examples-0.8-job.jar org.apache.mahout.driver.MahoutDriver testnb -i /user/admin/test-vectors -m /user/admin/model -l /user/admin/labelindex -ow -o /user/admin/testing

After the job completes it will spit out the result of the test, indication how accurate the model was in prediction spam, and details on classification errors.

Closing remarks

There are a couple of gotchas when working with Hadoop/Mahout. Some that I have found are that you need to provide absolute paths (like /user/admin/dataset) to the input and output data, otherwise you will run into problems where Mahout stores intermediate files under the wrong user directory because it is impersonating another user (hdp).

I’ve also found that if your input documents are very large in size (10+ MB), you can run into ’heap space’ exceptions. It should not be a problem with the sample I provided here, but if you train on your own data, it could be an issue. I simply deleted the input samples that were very large to avoid this problem.

Finally, the algorithm I’ve been using is Naïve Bayes, and it is a very simple Machine Learning algorithm, which usually does not give high accuracy on predictions (say 95+%). The field of Machine Learning has develop better algorithms, but unfortunately Mahout is missing support for some very powerful algorithms like Support Vector Machines (SVM) which are very popular in Machine Learning.

This example demonstrated how to apply Machine Learning to classify spam, but as I mentioned previously you can apply it to any text documents just by replacing the data set with your own as long as you can provide sufficient data samples and accurately categorize the training data, you should be able to train a machine learning model.

Links

[1] Official Hadoop website

[2] Official Mahout website

[3] Windows Azure free-trial

[4] Getting Started with Windows Azure HDInsight Service

[5] Simple recommendation engine using Apache Mahout

[6] Introduction to building a spam filter with Mahout (outdated)

[7] Using Mahout to classify tweets

[8] Hadoop Shell Commands

State-Query Models

2012-12-12T04:45:00.000-08:00

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.

Exploring state-query models

Exploration of state-query models is ‘on-the-fly’ testing. This means that the model is being explored by performing actions on the live system under test. Between each executed action the state-queries are evaluated on the database to determine the current state of the system under test. If the combined result of the state-queries is unique, then the newly discovered state is stored.

The following UML diagram shows how to conceptually explore a state-query model in a depth-first fashion:

Notice that for the state-query model to be feasible we must provide a mechanism for restoring a previous state (the ‘Restore database’ action). If the system under test stores its full state in the database (which is common for many service architectures), then this is obtained through a database restore. State restore is typically the most costly operation in the exploration algorithm. However, there are many ways to optimize this step, for example in NAV we track all changes to tables and then we can easily roll them back efficiently.

Seamlessly merging of models

The greatest benefit of this approach is that the emergent state model is coupled to the system implementation (and not some artificial state-machine), this implies that any integration scenarios (from the outside of the model) that stimulates a response in the system also stimulates the same response in the model. This means that we can create small models of sub-systems of the full system that still responds to integration scenarios. These small models are easily verifiable and once we have confidence that the small models works as we expect, they can seamlessly be merge into larger more complicated models that we would still expect to work. Again, very fancy, but let me continue the example and the benefits should be very clear:

Keeping in mind our original sales order model, we would now also like to model a sales quote document. This model would look almost identical to our first model, but everything would revolve around quotes. The one thing that is different is that a quote cannot be posted, it needs to be converted to an order first.

Where we again to use Spec Explorer we could use a new set of variables to track sales quote documents and the number of lines on each in a new model. But what happens now when we convert the sales quote to an order? How do we make that work with the sales order model? The conversion would never register in the sales order model, because the models know nothing of each other. We would have to bring in the functionality from the sales order model into the sales quote model (or make a third model), and explicitly enforce the creation of a sales order when a quote is converted. But there is no good way to do that – we are forced to either duplicate the sales order model or couple the two models together. If we duplicate we have redundant code, if we couple then the models become dependent on each other, and we can no longer change one without risk of breaking the other.

However, with our new approach, we can simply ignore this problem! We can just model the sales quote as if it was independent of the sales order. Resulting in another state variable query that would count sales quotes and the number of lines on them. In a stand-alone sales quote model what would happen when the model tries to convert a quote to an order? Even though the system under test will convert the quote to an order, the quote would simply appear to have disappeared – the model is not tracking sales orders, so it will not notice the appearance of a new sales order in the system. Conceptually the models would be disjoined:

However, were we to merge the state queries of both models into a new model, this new model would notice the appearance of a new sales order:

It gets even better, not only will we detect the appearance of a sales order, the sales order sub-model would not know the difference between a sales order generated by itself (the sales order model) and one converted from a quote. This leads to the automatic generation of integration scenarios (green path in the picture) between models.

The merged model would automatically detect and generate test cases for this integration scenario: creating a sales quote, adding lines to the quote, converting the quote to an order and posting this newly generated order – without us ever telling it anything about integration scenarios between sales quotes and orders. It simply falls out of the new approach for free.

Caveat

This is all nice and dandy, but one thing to be wary about is the fact that the model is coupled to the system under test. In traditional Model-Based Testing this is not the case. When we couple the model and the system, then we cannot distinguish between bugs in the model vs. bugs in the system under test. Furthermore, if we change behavior of the system, the model will follow suit. In short:

The model reveals how the system behaves, not whether that behavior is correct or not.

However, it is relatively easy to visually inspect a small model and determine if the behavior is correct or not. The strength of state-query models is that we inspect each of the individual models in isolation and validate conformance, then we bring the small models together into one (much) larger merged model, which is validated against all the validation rules of the individual models.

In the coming articles we will drill-down further into this caveat, and provide some mechanisms for decoupling your Model-Based Tests from the system under test.

Conclusion

In this article, we presented a novel innovation in the field of Model-Based Testing in which we represent the state of the system under test through the result of a set of state-queries executed against the data source backing the system. Using this approach we can construct many small models that validates conformance of system components and then seamlessly merge these into a larger model which models bigger parts of the system (or even the entire system).

¹U.S Patent Application No. 13/571717 (AUTOMATIC VERIFICATION OF DATA SOURCES)

Simulating Stochastic Models

2012-11-21T05:07:00.000-08:00

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.

Runtime and randomness

Each task takes a finite amount of time to complete, illustrated by the size of the task in the picture. Furthermore, the runtime of the tasks are highly stochastic as they are influenced by CPU load, network latency, IO latency, even build-in randomness in the tasks, etc. This causes the overall system to behave stochastically. At first hand one would think that we could just look at average runtimes of individual tasks to get an average job runtime, however this is not going to give an accurate response of the system.

Now, traditionally I would model this problem in Spec Explorer, but in this case the system is already represented by a model, namely the dependency tree of the job

This allows me to write a simulation tool instead.

Simulation

The idea about the tool is to simulation how the system would stochastically schedule tasks in a single job. This is called a sample. Once this is working, we can set the tool to repeatedly simulate the same system, producing thousands of samples. We can then measure the average job runtime of all the produced samples. This is called Monte Carlo Simulation and is an exceptionally powerful technique. It turns out that the measurement error on the sample mean, is reduced by the inverse square root of the number of samples – regardless of what metric is measured, and regardless of what system is measured! Let’s take a step back and think about the ramifications of that. That means, no matter how complicated we make the stochastic system, the measurements are going to become more and more accurate, the more samples we take from the system. So, say we want to model re-running failing tasks for instance. No problems, if a task fails (this is also stochastically determined) we let the system reschedule it. We sample the system a couple of thousand times and our metrics are updated with the new mean job execution time!

Furthermore, the model was able to predict and generate a heat-map of the bottlenecks of the system, which I’d like to share with you for inspiration:

The redder the task the more often it appeared on the critical-path of the system (the path determines the overall execution time). By reducing the time of the critical path, you reduce the overall execution time. The problem is that in a stochastic system the critical path changes between executions. Therefore, this heat-map is extremely valuable information because it allows us to direct our effort to the tasks that most often appear on the critical path.

What does this have to do with model based testing?

Well, think about it.

Is there an underlying model? – Yes! However, it’s not a finite state model supposed to simulate the system under test, but a stochastic model that is the system under test.

But will it find any bugs? – Arguably the model is not designed to find bugs in the system (because the model and system is the same, which makes it impossible to do so…). Yet, the simulations will help detect bottlenecks, resource starvation, mean critical path, optimum number of resources, optimum re-run strategy, etc. These are not bugs as we see them traditionally. However, they are all system characteristics which we are trying to improve. So they could just as well be interpreted as bugs!

In some extreme cases you could also prevent bugs by specifying acceptable intervals for your measurements – for example, we could state that no job may take more than four hours to complete, then if a simulated sample happens to exceed this limit, we may conclude that the system is defective.

Conclusion

What I wanted to demonstrate with this post is that Model-Based Testing is not just about Finite-State models and Spec Explorer. The fundamentals of modeling applies to many problems. In my example I was lucky enough to be working with a system that could be described through a model. When you are faced with a new problem, try thinking out-side of the box, in many cases modeling turns out to be a valuable tool in your toolbox.

Solving ‘The Monty Hall Problem’ using Models

2012-06-24T21:51:00.001-07:00

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.

For an in-depth explanation (although a little too narrative in my opinion) watch this YouTube video – and if you think the answer is obvious, just scan the comments on the video to convince yourself that people have a hard time understanding this answer!

Solving the problem through modeling

Let’s take a look at how we can tackle this problem in the world of Model-Based Testing [1]. This article is special in that I’m not going to have a system under test – there is nothing to test here! Instead, what I’ll be doing is constructing a model that will be useful for simulating the flow of the Monty Hall problem.

The model state machine consists of the following variables:

const int NumberOfDoors = 3;

const int DoorWithPrize = 0;

static int first_choice = -1;

static int revealed_door = -1;

static int final_choice = -1;

First, one thing I’d like to make clear is that I’m simplifying the problem by fixing the door that contains the prize to be the first door – this does not make any difference, because the problem statement is equivalent no matter which door the prize is behind (likewise you could fix the initial choice and have the location of the prize be random). If you don’t believe this, then feel free to enumerate both policies for all three prize locations.

To break the model down, the game show contains three stages, they are:

1) Pick your initial choice of door

2) Game host reveals a goat behind another door

3) You either switch or stick with your door

We will be modeling these stages as rules, and then define a slicing scenario that dictates the two choices of policies we have (switch/stick with choice).

The rules of the model become:

// Chooses a first choice door between 0 and 2

[Rule(Action = "PickDoor()/result")]

static int PickDoorRule()

{

first_choice = Choice.Some<int>(i => i >= 0 && i < NumberOfDoors);

return first_choice;

}

// Chooses a door to reveal between 0 and 2 that:

// * Is not our first choice

// * Is not the door with the prize (door: 0)

[Rule(Action = "RevealDoor()/result")]

static int RevealDoorRule()

{

revealed_door = Choice.Some<int>(i => i >= 0 && i < NumberOfDoors && i != first_choice && i != DoorWithPrize);

return revealed_door;

}

// Switches our choice of door and saves the value in final_choice, by picking a door between 0 and 2 that:

// * Is not our first choice

// * Is not the revealed door

[Rule(Action = "SwitchDoor()/result")]

static int SwitchDoorRule()

{

final_choice = Choice.Some<int>(i => i >= 0 && i < NumberOfDoors && i != first_choice && i != revealed_door);

return final_choice;

}

// Simply sticks with our first choice by setting final choice = first choice

[Rule(Action = "StickWithDoor()/result")]

static int StickWithDoorRule()

{

final_choice = first_choice;

return final_choice;

}

Notice that we leverage Spec Explorers ability to handle stochastic choices! The model does not know up-front which door the contestant will start out picking, and neither does it know which door the game host will reveal.

So, we could simply explore the model composing these rules, but that model would be nonsensical because it violates the rule of the game show – e.g. it would allow the game host to reveal two doors, etc. Therefore, we need to constrain the model into a meaningful slice. We have two policies so we need two slices; the first slice is for ‘sticking with your initial choice’:

/// The scenario is equivalent to sticking with your choice in the 'Let's make a deal' game show

machine DontSwitchScenario() : Main where ForExploration = true

{

(PickDoor; RevealDoor; StickWithDoor)

}

machine MontyHallDontSwitchModel() : Main where ForExploration = true

{

DontSwitchScenario || MontyHallRules

}

Let’s explore this model and have a look at the results:

The state bubbles show the currently selected door, and at the end it includes the outcome – whether we found a Ferrari or a goat behind our final choice door.

From a quick glance of this model it looks like we are in pretty good shape – we see two goats versus two Ferraris. But we need to read the picture correctly, actually we don’t decide which door is revealed, it is stochastically decided, meaning there is a 50/50 chance that either door 1 or door 2 is revealed – however, the final outcome is the same – we win no matter which door the host reveals under this policy (which is expected because our choice is unaffected by the host’s choice when we stick with the initial choice).

To compute the expected outcome for this model observe that we pick the initial door randomly with 1/3 probability, then in two out of three options the game host can only reveal one door (with probability 1), and in the final option the game host picks one of the remaining doors with probability 0.5. Getting the Ferrari has utility 1 and the goat has 0. The expected outcome is then:

E[MontyHall|Stick with choice] = 1/3 * 0 + 1/3 * 0 + 1/3 * (1/2 * 1 + 1/2 * 1) = 1/3

The fact that there are two ways of winning when we have picked door zero initially should not count double. What matters is that given our initial three options, which paths will give what outcome? In our case the two left-most paths will result in ‘winning’ a goat, where the right-most choice (under our policy) will win us a Ferrari! Our chance of winning the Ferrari is thus 1/3.

Next, let’s look at the switching policy:

/// The scenario is equivalent to switching your choice in the 'Let's make a deal' game show

machine SwitchScenario() : Main where ForExploration = true

{

(PickDoor; RevealDoor; SwitchDoor)

}

machine MontyHallSwitchModel() : Main where ForExploration = true

{

SwitchScenario || MontyHallRules

}

It is clear that the only difference is in the third stage of the model, where we now switch our choice instead of sticking with it. The model looks slightly different:

Notice now that the mechanics of the game have switched! Under the policy where we switch, two of our initial branches will lead to winning the Ferrari! Only one branch will lead us down the path where we ‘win’ a goat – again it does not matter whether the game host reveals door one or two, once we are down the path of picking door zero initially we are guaranteed to lose the game. The expected outcome is:

E[MontyHall|Switch] = 1/3 * 1 + 1/3 * 1 + 1/3 * (1/2 * 0 + 1/2 * 0) = 2/3

The key to understanding this problem (in my opinion) lies with understanding what happens when the host reveals a door under the switching policy. Notice that under this policy the game host only has one option in two out of three cases – incidentally, in these two cases, when he reveals the door with the goat behind it he is consequently also revealing which door the Ferrari is behind!

Conclusion

We saw in this article how models can be useful for simulating problems without actually acting against a system under test. Modeling is a great technique for visualizing simulation results and through Spec Explorers powerful stochastic modeling feature you can simulate decision-trees for random processes, like the Monty Hall problem.

References

[1] Monty Hall Model

Can your tests stand the ‘test of time’?

2012-06-18T01:05:00.000-07:00

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");

The graph would show a status like ’Last updated: 13:02’. The test would then validate the correctness of this message using the current time. Of course, the problem is if this test is run exactly around 13:02:59 then there is a chance that the time changes to 13:03 between the Update call and the computation of the expected message, causing this test to fail. This is a fragile test. Computing the expected message before updating will not fix this problem. Actually for this test to be ‘correct’ it should validate that the time returned is within the window of possibilities, like:

DateTime windowStart = DateTime.Now;

graph.Update();

DateTime windowEnd = DateTime.Now;

Assert.IsTrue(windowStart <= ExtractDateTime(graph.StatusMessage) <= windowEnd, "Incorrect status message displayed");

Although this test is stable with respect to the natural progression of time, it is susceptible to outside factors affecting the system time. It may happen that the system clock is adjusted through synchronizing the system clock with an online server, or due to daylight savings, just before setting windowEnd variable. Of course these examples are much less likely to happen, but if you run 100,000’s of tests every day chances are that you will end up running into strange scenarios with time behaving unpredictable.

The correct way is of course to mock the timer in the system under test such that you control it from your test. Then it’s a matter of just freezing time:

public class MockTimer : ITimer

{

private DateTime currentTime = DateTime.Now;

public int GetTimeOfDay()

{

return currentTime;

}

With a mock approach the test is directly in control of the time and you rid yourself of external dependencies. The down-side is that the system under test must be architected in a fashion where you can supply your mock timer to it.

Perception of time

Before I go on to the next example I’d like to define perception of time from a computer program.

By perception of time, I mean the perceived amount of time that one unit of code takes to execute (a unit could be a single instruction, a function call or a class/component performing a task). Perception of time for a computer program is far from constant. It is affected by a plethora of external factors. The most common is CPU usage (by other processes), a highly stressed CPU will execute your program much slower, effectively causing time dilation (actually the metaphor works well here, the faster the CPU is running the more time slows down J).

On the microscopic time-scale perception of time is impacted by OS time slots, an instruction could finish in 1 millisecond or a program may have to wait 100 milliseconds for its OS time slot to begin.

On the macroscopic level the program could be using a database which happens to be in a locked state, causing it to run for 10 minutes before the lock is released and the program is able to finish.

So in fact, the perception of time of a computer program changes quite a lot during execution. It is jittery from time slotting, and in periods it slows or speeds up drastically due to other programs consuming resources.

Common misuses of time #2: ‘Performance’ regression test

A colleague of mine recently wrote a regression test to prevent a performance issue being reintroduced. The problem simplified was that a function working on a set should run in constant time, because the correct implementation needed only to look at the last element in the set to compute the result. The premise of the test was that running the function on a single element set and measuring the execution time should roughly match a repeat execution on a five element set. If the execution times differed by more than 50% the test would fail:

DateTime beginSingleElement = DateTime.Now;

ExecuteTestOnSingleElement();

TimeSpan durationSingleElement = DateTime.Now - beginSingleElement;

DateTime beginMultipleElements = DateTime.Now;

ExecuteTestOnMultipleElements();

TimeSpan durationMultipleElements = DateTime.Now - beginMultipleElements;

TimeSpan delta = durationSingleElement - durationMultipleElements;

Assert.IsTrue(Math.Abs(delta.Ticks) < 0.5 * durationMultipleElements.Ticks, "Performance problem detected.");

Okay, fair enough, the test is at least making a comparison between two runs and not measuring absolute time. Also, it is forgiving – it allows for 50% difference in measurements.

However, with our understanding of perception of time, it is clear that this test is susceptible to changes in perception of time. If the computer happens to start installing Windows Updates during the ExecuteTestOnMultipleElements method call, it could significantly impact the test – even outside the 50% safety-margin!

Again, the test is fragile leading to superfluous analysis work upon failure. In our context we were able to refactor this test to be based on code coverage measurements, which is deterministic and within our control. But the general advice is that performance tests should not be included in regression suites where the purpose is to determine the quality of a particular build. Instead these tests should be executed in a performance suite, which measures the performance of the product running in a highly controllable environment, and where the result is to gauge the performance, not to provide a yes/no on quality.

The ‘test of time’

Mock the underlying timer functions in your test framework the following way:

1. Initialize a counter to 0

2. Every call to your timer function increases this counter by a random positive integer amount and returns the updated value of the counter.

Repeatedly run your tests (as well as the system under test) using this mock-implementation of a timer. If any of the tests fail this is an indication that they are not agnostic to the perception of time, and in turn they are susceptible to external factors that can influence the system clock.

This test will surface any undesired test dependencies on the system time, so you are able to fix them up-front. The random pattern makes it much more likely that you will detect problem like #1 and #2.

Conclusion

If your tests can’t stand this ‘test of time’ then my claim is that given enough time they will cause you problems. Depending on your setup, it may be more or less critical that you have stable regression tests, but for the most part I find that any fragile test will either be ignored during analysis because it is known to be fragile (then it is worthless, because if it happened to find a bug that would also be ignored), or it will keep appearing on your radar over and over again disrupting your daily rhythm, sucking out effort that could otherwise be spent more productively. At first this might not seem such a big problem, but as your scope starts scaling to maybe 10,000 or 100,000 tests, what seemed a small problem suddenly magnifies to a gigantic time hole which impedes you from moving forward in your daily work.

Modeling Multi-Threaded Applications

2012-05-30T23:52:00.000-07:00

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.

Synchronization in models of multi-threaded systems

Multi-threading is at first a tough concept to grasp, and even those skilled at developing parallel systems, frequently make mistakes. Minor problems magnify significantly in a multi-threaded environment, because they can lead to system deadlocks or sporadic behavior, which is exceptionally difficult to reproduce and debug. One common problem is to assume that a result is ready, while in fact it is still being process by a worker thread – this is lack of synchronization. For example, in the case of the parallel job scheduler, it is important that we wait for the worker threads to finish processing jobs before we check the results – this may at first seem simple, but actually it is counter-intuitive to be implementing synchronization actions in a model, and also we need to think about how we slice the model to produce only valid models. Consider a model comprising the following three rules:

[Rule(Action = "ScheduleJob()/result")]

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

[Rule(Action = "GetResults()/result")]

The ScheduleJob is a stochastic rule that creates a job and schedules it on any worker thread. Furthermore, we need a synchronization action – here named AwaitResults – to ensure all worker threads have finished. Finally GetResults checks that the results are correct. A valid slice of this model would look like:

machine SlicedStochasticWorkerModel() : Main where ForExploration = true

{

(ScheduleJob{X} ; AwaitResults ; GetResults) || StochasticWorkerModel

}

This slice composes a model where we schedule X jobs, await results and finally check the results are correct. However, from a pure modeling perspective the sequence ( ScheduleJob ; AwaitResults ; ScheduleJob ; GetResults ) is perfectly valid, but in a multi-threaded environment this sequence behaves indeterministic, so we have to constrain our model using slicing.

Parallel job scheduler model

A simple model of this system with these three rules could look like (see reference [1] for the full sample code):

/// <summary>

/// Schedule a job in the system for processing

/// </summary>

/// <returns>The id of the selected worker thread.</returns>

[Rule(Action = "ScheduleJob()/result")]

static int ScheduleJobRule()

{

int thread = Choice.Some<Int32>(i => i >= 0 && i < 3);

runningJobs.Add(++nextJobId, thread);

return thread;

}

/// <summary>

/// Dummy action which causes the model to wait for the worker thread to finish

/// and deliver their results before checking them

/// </summary>

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

static void AwaitResultsRule()

{

}

/// <summary>

/// Check the results from the worker threads

/// </summary>

/// <returns>A checksum of the results computed by the threads.</returns>

[Rule(Action = "GetResults()/result")]

static int GetResultsRule()

{

return runningJobs.Keys.Sum();

}

Where the finite state machine composes a map of which jobs are running on which worker threads. It’s interesting to notice that the synchronization rule is an empty stub – the model does not need to do anything to synchronize, because the model is not multi-threaded, only the system under test is. Synchronization takes place at the slicing level of the model.

Exploring this model with a limitation of scheduling a maximum of two jobs yields:

The top section of the model is where we schedule the two jobs, then we have a synchronization action and finally we check the results.

Parallel job scheduler implementation

The system under test is implemented using a standard .NET ThreadPool to process jobs in parallel.

public class StochasticJobScheduler

{

private static int runningJobs = 0;

public static int ScheduleJob()

{

runningJobs++;

ThreadPool.SetMaxThreads(3, 3);

ThreadPool.QueueUserWorkItem(WorkerThread.Process, runningJobs);

return 0;

}

public static void AwaitResults()

{

// Wait for all threads to complete

while (AggregatedResultList.Count() < runningJobs)

{

Thread.Sleep(100);

}

public static int GetResults()

{

return AggregatedResultList.GetResults().Sum();

}

The job processing is delegated to the WorkerThread.Process method. It is very simple to implement a job scheduler like this, but unfortunately we run into some problems while executing the tests. From the ScheduleJob implementation it is evident that we do not adhere to the requirements of the model – we always return zero telling the model the first worker thread picked up the job, but in fact we have no way of knowing that. If the results are independent of which thread processed them, then you can argue that it doesn’t matter that we ‘lie’ to the model about which thread got picked up – but then I would counter that argument by asking why we even model it stochastically. Even worse, in cases where the result actually does depend on which thread executes it, we get incorrect results. Observe the following change in the worker processing implementation:

AggregatedResultList.AddResult(Thread.CurrentThread.ManagedThreadId);

This will make the thread report its unique ID as the result of the procession and would cause our tests to fail sporadically because we are ‘lying’ to the model.

Okay, so let’s fix this properly, we can let the worker thread tell the scheduler the last used thread ID using proper synchronization – I’m not going to include the implementation details here, but I refer you to the sample code for how this is done. The result of this change is effectively that the StochasticJobScheduler.ScheduleJob method now returns:

Thread.CurrentThread.ManagedThreadId

Of the selected worker thread. Unfortunately, what we end up with is the following failure:

Expected matching return, found return ScheduleJob()/15. Diagnosis:

1. outputs do not match
comment: checking step 'return ScheduleJob/0'
assert failed: expected '0', actual '15' (return of ScheduleJob, state S1)

2. outputs do not match
comment: checking step 'return ScheduleJob/1'
assert failed: expected '1', actual '15' (return of ScheduleJob, state S1)

3. outputs do not match
comment: checking step 'return ScheduleJob/2'
assert failed: expected '2', actual '15' (return of ScheduleJob, state S1)

What this is telling us is that the ID of the picked worker thread was 15, which is not one of the expected outputs from the model (they are 0, 1 or 2). This is because we have a mismatch between the expected thread IDs from the model, and the actual IDs supplied by .NET.

In fact the value of 15 is arbitrary, .NET could return anything, as long as the value is unique per thread. What happens is that .NET is hiding the information about which threads were created first, because it is simply not relevant for the implementation of a parallel system using thread pools. In fact, exposing such information could often lead to poorly designed systems, because in a pool of threads the consuming system is supposed to treat all threads as being equal.

We can let the adapter layer translate the .NET IDs to an index between 0 and 2 using the following piece of code:

private static List<int> threads = new List<int>();

public static int ScheduleJob()

{

...

int i = GetLastThreadId();

if (!threads.Contains(i))

{

threads.Add(i);

}

return threads.IndexOf(i);

}

This will make sure we don’t ‘lie’ about which thread was picked, which allows Spec Explorer to detect the correct path taken in the stochastic model at runtime. However, this will still not solve the problem where the results depend on which thread picked up the job.

Conclusion

This leaves us with the final conclusion. For multi-threaded applications, modeling is sort of a double edged sword. At one side, the system should shield away the multi-threaded aspect and from a testing perspective, really we should focus on the overall system behavior, and not model the stochastic choices. On the other hand, we would still like to model the full-blown system, including the stochastic choices, because they tell us something about how well balanced the implementation is. For example, in the case of the parallel job queue, we really would like to make sure, that the work flow is evenly balanced between the threads. Unfortunately, this would require more information than Spec Explorer provides. Currently, Spec Explorer will generate one test case from our model, which models all available paths, but running this test will only provide you with a single sample of how the system reacted to the specific scenario, which does not tell you a lot about the behavior. Instead you need to run the test many times and see that the system is actually taking different branches through the model – which is actually really difficult to see, because Spec Explorer does not do a lot to provide you with meaningful results.

It would be nice if Spec Explorer could visualize which branch was picked by the model, such that you could make a visual inspection of the test path. Where you to repeat the test 1000 times without resetting this visualization, a heat-map of the model would start to emerge, which would be very useful for multi-threaded profiling.

References

[1] Parallel Scheduler Model

Modeling Stochastic Systems in Spec Explorer

2012-05-10T23:43:00.000-07:00

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.

Making choices in stochastic models

The fundamental component of stochastic modeling is the Choice class. This class provides an interface to generate a random choice in Spec Explorer. The following illustrates how to use it to choose a random enum value:

public enum StochasticAction

{

}

switch (Choice.Some<StochasticAction>())

{

case StochasticAction.A:

...

case StochasticAction.B:

...

}

So why not use Random directly in the model?

[Rule(Action = "Add()/result")]

static int Random_AddRule()

{

int v = 1 + random.Next(2);

counter += v;

return v;

}

Well – if you do that, Spec Explorer will not know that the action is stochastic, and the outcome model will be a single random sample of the full stochastic model, which will vary when you re-explore the model:

Instead, using the Choice class will make Spec Explorer aware that the action is stochastic and it will understand that there are different outcomes:

[Rule(Action = "Add()/result")]

static int Choice_AddRule()

{

int v = Choice.Some<int>((i) => i > 0 && i < 3);

counter += v;

return v;

}

This will produce the stochastic model depicted in the top of the post.

Generating tests from stochastic models

When generating test cases from a stochastic model you need to set the AllowUndeterminedCoverage = true flag for the construct:

machine StochasticTestSuite() : Main where ForExploration = true, TestEnabled = true

{

construct test cases where strategy = "ShortTests", AllowUndeterminedCoverage = true

for SlicedStochasticModelProgram()

}

The generated tests are no longer scenarios like we are used to, but they become graphs themselves, visualizing how the test can go down different paths based on the stochastic behavior of the SUT:

The test will start out in the initial state 0. Then it will call Add. Depending on the return value of the Add call it will either dive deeper into the left path (if Add returned 1) or right path (Add returned 2). Test exploration will then continue from whatever state it reached after the stochastic Add action.

An obvious question to ask is – why does some of the stochastic actions merge back into existing branches, while others go to new branches, even though the states are the same? It turns out, there is a nice switch which will clean this up:

config Main

{

...

switch EnableExplorationCleanup = true;

...

}

The resulting test graph then looks like:

Which is nice – but come on guys, why do I need to manually set a switch to produce a cleaned-up graph?

Auto-generated test code from stochastic models

While the feature is very powerful and a lot of effort has been put into the visualization, such that the decision points in the models are clear, the generated test code lacks the same polish. I’m aware that it is auto-generated, and you don’t put as much attention into it. But when you get to the point that one of your test cases fails and you need to debug what went wrong, having high quality test code helps a lot in the debugging effort. Unfortunately, high quality is not a word I would use about the generated test code. It is _littered_ with labels and goto statements, nested blocks inside yet more nested blocks, and finally dummy exception like:

throw new InvalidOperationException("never reached");

thrown at multiple places in the code. This looks like a part of the product that could use some attention…

It’s a good thing it’s hidden away for the most part, and the verbosity of the test is quite good. For example if the SUT does not behave according to one of the modeled behaviors the following error is raised:

expected matching return, found return Add()/0. Diagnosis:

1. outputs do not match

comment: checking step 'return Add/2'

assert failed: expected '2', actual '0' (return of Add, state S1)

2. outputs do not match

comment: checking step 'return Add/1'

assert failed: expected '1', actual '0' (return of Add, state S1)

which is fairly descriptive. In this case the Add method returned 0, but it is only expected by the model to return either 1 or 2.

Uniqueness of action labels in stochastic models

In the above model for a stochastic accumulator, the Add action returns the value that was added to the counter. From a modeling perspective, this information is irrelevant, because I can simply inspect the counter and observe the change – actually it’s perfectly fine to do just that for a model:

If you compare to the model on the top of the post, the only difference is that Add does not reveal what value was added. This works for the model, but once you go into exploring test cases, Spec Explorer will complain with the following error:

Block(Restriction of exploration: some kinds of composite behaviors (including test cases construct,
requirement coverage construct, etc.) won't work when inner behavior has any state which has outgoing
steps with exactly the same label. If so, try adjusting your model to avoid it and re-explore.)

The essence of this convoluted error message is that “any state which has outgoing steps with exactly the same label” is prohibited. You can think of the return value of a stochastic action as a checkmark for Spec Explorer to determine which branch the SUT actually took during run-time test execution. This implies that the return values for a given action must be unique, otherwise Spec Explorer would not be able to tell exactly which path was followed. This furthermore puts a constraint on the SUT, as the SUT (or adapter) must reveal which path the SUT took run-time.

This is not always possible if you are doing black-box testing, for some SUTs the stochastic choices may be hidden from the outside by the design of the system. In these cases it is up to the adapter layer to probe the SUT after a stochastic choice was made to determine which test-branch the SUT followed. Normally the effect of a stochastic choice is measurable in the state of the SUT, but in rare cases the effect may be invisible to the outside, and only affect later decisions. If this is the case, then you will not be able to determine the run-time test-branch before later in the test case, which means you cannot satisfy Spec Explorers condition on unique labels. A way around this though, is to make a coarser granularity action that consolidates all of the actions required for you to determine the stochastic choice made in the first action.

In more exotic cases, the behavior of the SUT could be affected by some truly random physical effect. Here we are out of luck, as measuring the random effect is likely to affect the outcome of the decision.

[1] Stochastic Accumulator Model

Collateral code coverage, ramifications on Model-Based Testing

2012-03-29T05:12:00.000-07:00

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.

Collateral code coverage is common. It can come from unintentional code coverage (test defects causing it to execute unpredicted code branches) or coverage that is intentionally not verified. Very often tests cases are designed to execute a scenario and then validate a single outcome. The longer the scenario the more code will be covered, but the level of validation remains the same. In some extreme cases we see test cases that cover thousands of code lines but still only contain one validation. These tests obviously have high collateral code coverage. You may argue they are poorly designed tests (and I would agree), but the problem exists for almost any size scenario (maybe excluding unit tests, depending on your definition of a unit).

In general the higher the abstraction level of the test the more collateral code coverage it generates.

Collateral code coverage is unavoidable and has the unfortunate side-effect of artificially inflating confidence in the product, which is why code coverage is a poor metric for product quality.

Ramifications on Model-Based Testing

But this is a blog about Model-Based Testing, so what are the ramifications of collateral code coverage on MBT?

In general MBT seems to be at an even higher abstraction level than scenario based tests, thus it should be even worse with respect to collateral code coverage. In many cases I find that this is true, MBTs from my experience usually have lots of collateral code coverage, which is a deficit. But MBT is a very broad concept, and in cases where MBT is used for generating input/output values for an API, this is not necessarily the case (see for example my posts on the Traveling Salesman Problem).

To enumerate a few model types and their ramification:

UI/Data Flow Model	High-abstracting model that mimics the behavior of data moving in a system under test. These models tend to have high collateral code coverage because they mimic user scenarios
Combinatorial Model	Low-abstraction model that feeds different combinations of input into a single unit under test. The additional collateral code coverage per generated test is normally low. However, they can have a constant overhead from setting up the execution environment, depending on how tightly they interface with the unit under test.
Fuzzy Model	Low-abstraction model that produces random sequences of input to a system for stress testing and security testing. Usually the goal is to crash the system under test, and no functional validation is performed. The objective of these models is to branch out and hit as much code as possible. These models generate fully collateral code coverage.

By all means this is not nail in the coffin for MBT, but it emphasizes the need for clever models along with a careful disclaimer when you rely on code coverage data from MBTs. For example using code coverage obtained from fuzzy modeling would be a horrible metric for product quality (unless you just care about not crashing).

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

2012-03-23T02:19:00.000-07:00

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.

This trick works in general, if you want to use objects in your immutable containers then wrap the data of the class into a struct and store that in the containers, then you can easily reconstruct your object from the stored data by overwriting the objects internal data variable in a constructor. Here is my implementation of a Vertex class based on this approach:

public class Vertex

{

public VertexData v;

public int X { get { return v.x; } set { v.x = value; } }

public int Y { get { return v.y; } set { v.y = value; } }

public Vertex(VertexData vertex)

{

v = vertex;

}

Having taken care of the representation, there is one problem left to tackle with this refactoring. The optimized algorithm uses the concept of splicing edges. The problem is that my adapter does not know of edges – it knows only of the vertices that were added. In the original implementation it was possible to pass on the integer representation of the edge being spliced to the adapter and then reconstruct the edge, but this was a bad hack. Because we lifted the domain size constraint this approach no longer works as there is no way to represent an edge as an integer. Also you could argue that the adapter should not even care about the concept of edges, it needs only to build a set of vertices and then let the TSP solver do the rest. Conceptually we don’t want the adapter to know of the edges because then we could cheat in the implementation.

Essentially the problem boils down to the fact that the model has a rule that does some magic computations which translate into the addition of a vertex to the graph (the growth process):

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

static void Magic()

{

// Compute a new vertex using some magic rules

Vertex v;

...

// Re-use existing concept for adding a vertex to the graph

InsertVertex(v.x, v.y);

}

[Rule(Action = "InsertVertex(x,y)")]

static void InsertVertex(int x, int y)

{

...

}

We don’t want the adapter nor the SUT to know of this magic rule, because it would have to re-implement the same logic to produce the actual added vertex (the generated tests will call Magic on the adapter, not followed by any call to InsertVertex). So how do we avoid this?

Well… one trick is to use the following pattern:

static VertexData magicVertex;

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

static void Magic()

{

// Compute a new vertex using some magic rules

Vertex v;

...

// Store computed vertex for insertion

magicVertex = v.v;

}

[Rule(Action = "InsertMagicVertex(x,y)")]

static void InsertMagicVertex(int x, int y)

{

Condition.IsTrue(x == magicVertex.x);

Condition.IsTrue(y == magicVertex.y);

InsertVertex(v.x, v.y);

}

The trick here is that the Magic rule computes the vertex, but instead of adding it directly it stores the required information in a variable priming the model. Then the InsertMagicVertex rule can pick up the computed value and insert it. Because the signature of this rule has all the required information the adapter layer will simply call the same function as InsertVertex does, with no need for re-implementing the difficult computational logic.

In the Config.cord file, instead of using the Magic and InsertMagicVertex rules directly, define the following scenario:

machine MagicScenario() : Main where ForExploration = false

{

Magic ; InsertMagicVertex

}

This will make sure that after computing a vertex it is immediately added to the graph.

Re-Modeling the Traveling Salesman – Part II

2012-02-26T06:21:00.002-08:00

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.

The combination of a large input domain coupled with the design of the exploration engine of Spec Explorer, makes it infeasible to find larger graphs this way.

Let’s investigate a different approach. The underlying problem is that we are giving the model too much freedom. Instead of allowing it to add a vertex at any grid point, we can turn the picture around, and instead model the splicing of an edge directly. The process goes like follows:

a) Select any existing edge

b) Splice it by two parameters

a. Alpha determines where to insert a splicing point along the edge

b. Beta determines the perpendicular distance from the splicing point to the new point

c) Take the nearest grid point to the decimal point

d) Grow the graph by trying to insert a vertex at that point

The implementation of splicing goes as follows:

public class Edge

{

public Vertex P1;

public Vertex P2;

public Vertex Splice(double alpha, double beta)

{

// Find splicing point

double spx = (P1.X + P2.X) * alpha;

double spy = (P1.Y + P2.Y) * alpha;

// Project perpendicularly

double ex = -(P2.Y - P1.Y);

double ey = P2.X - P1.X;

double px = spx + beta * ex;

double py = spy + beta * ey;

return new Vertex((int)Math.Round(px), (int)Math.Round(py));

}

The signature of the model rule looks like:

action static void TravelingSalesman.SpliceEdge(int index, double alpha, double beta);

A clear benefit of this implementation is that the complexity of the rule is independent on the grid size, thus we can extend our grid to be very large and still be able to explore the full state-space within reasonable time.

A down-side is that now we have an infinite number of possible inputs on the alpha and beta variables, but we can fix those in the configuration.

Of course, just using the SpliceEdge rule will not work, because we require one edge to start with, but we can easily construct an initial edge using our InsertVertex rule. Thus the machine we explore looks like this:

machine FixedTriangle() : Main where ForExploration = true

{

InsertVertex(3,3) ; InsertVertex(16,7) ; InsertVertex(8,16)

}

machine Splicing() : Main where ForExploration = true

{

(FixedTriangle ; SpliceEdge(_,0.5,0.35)* ; Solve) || TravelingSalesManModel

}

Notice how this machine obtains the desired result using model slicing, to both limit the input domain for SpliceEdge as well as construct a fixed starting triangle to splice from. The starting triangle looks like:

Exploring this on a 20x20 grid yields:

Using this approach we can easily generate graphs containing 10 vertices. A subset of the constructed graphs can be seen here (the starting triangle is shown in gray):

Some interesting things can be seen from these graphs. Only two of the edges are ever spliced, the left-most edge cannot be spliced as the resulting vertex is invalid under the InsertVertex rule. Also, the top-most edge is always spliced in-wards, whereas the right-most edge is spliced out-wards. The first problem stems from the magnitude of the b parameter which is too large to produce valid slices, it would be beneficial to vary the magnitude of the input value. The second problem is that b > 0, thus the algorithm will always splice in a fixed direction, again we should allow negative values as well.

Lifting our first limitation we allow b to be either 0.35 or -0.35:

config Config20x20: Main

{

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

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

action static void TravelingSalesman.SpliceEdge(int index, double alpha, double beta)

where alpha in {0.5}, beta in {0.35,-0.35};

}

And using the following machine definition:

machine Splicing() : Main where ForExploration = true

{

(FixedTriangle ; SpliceEdge(_,0.5,_){2} ; Solve) || TravelingSalesManModel

}

We generate much more diverse graphs:

This is already much better! Let’s see how far we can drive this:

This is a partial explore using DFS on the machine. The produced graphs have up to 16 vertices in them:

One short-fall of this approach is that the model splices the edges into finer and finer pieces without adding much complexity to the graph. The problem arises when we get close to the boundaries of the grid, and when the rounding of the computed point causes it to snap back on the edge that we are splicing. Of course, we can lift this constraint by expanding the size of the grid, but another approach could be to work on having a floating-point value grid, which we will explore in the next post, where I still owe you the proof for the splicing algorithm.

Conclusion

We saw how the design of Spec Explorer makes it infeasible to grow our original implementation to larger size grids because the number of valid inputs for any given state grows with the number of grid points. This limitation was lifted by changing the model to start out from three fixed points (using model slicing) and then expanding it by splicing only existing edges. The number of inputs using this approach grows by one for each successful model rule. We were able to generate graphs of higher complexity with this approach within reasonable time (minutes).

[1] Traveling Salesman Re-model

Modeling the Traveling Salesman

2012-02-14T06:28:00.001-08:00

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.

Growing graphs

The intuition behind my approach is to grow the graphs one node at a time. Under certain circumstances the shortest tour can be grown by adding another node causing it to still be optimal in the new graph. Using this approach we start out with a single point that grows to a line, then a triangle. At the triangle stage we have our initial shortest tour. The next step is to splice in one additional node (v’) into the graph – this concept is illustrated here:

A splice s_i is defined as replacing the edge e_i with the two edges that form by connecting the endpoints of e_i with v’. The cost of a splicing is defined as:

Where |x| is the Euclidian length of x. The cost is simply the extra length added to the path.

The algorithm for growing the graph by one vertex goes as follows:

Given a graph G = (V,E) where E is an shortest tour in G. Consider any node v = (x,y) not in V, define the minimum cost splice over all feasible edges E* constructed from vertex pairs in G (note E is a subset of E*):

Add v to the graph G if and only if the edge argument minimizer of d is contained in E and:

The resulting graph G’ = (V’,E’) is constructed by adding v to V and splicing e_i in E.

Claim: The resulting edge set E’ in G’ is a shortest tour. I will post a mathematical proof of this later in the series.

As the constructed output graph G’ satisfies the conditions for G it follows by induction that we can repeat the growth process.

Time for some modeling!

Modeling the Traveling Salesman in Spec Explorer

The first very crude model[1] I’m going to demonstrate will build a graph on a fixed-size integer lattice, where nodes can be added only at the grid points. This implementation may seem very limited, but in fact there is not much difference in modeling an integer lattice versus a floating-point domain, because any integer lattice graph can be scaled to match any graph on a floating-point domain (in-fact a floating-point domain is just a really large integer interval). However, when we constrain the size of the lattice we are of course limiting the flexibility of the model, but the integer representation has some advantages.

Because we are working on a fixed size lattice we can convert any (x,y) point to an integer index. This index is useful when storing the representation of the current graph, because vertices can be held in a SetContainer<int> allowing the model to be independent of the order in which the vertices are added. The same applies to for edges in the shortest tour of the graph.

The model contains just two rules:

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

action abstract static double TravelingSalesman.Solve();

The InsertVertex attempts to grow the current graph by insert a vertex at (x,y) and then checking whether this vertex satisfies the criteria of our growth algorithm.

We start out by exploring a tiny grid (2x2):

config Grid2x2: Main

{

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

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

}

machine TSM2x2() : Main where ForExploration = false

{

construct model program from Grid2x2

where scope = "TravelingSalesManModel.TSMModelProgram"

}

machine TSM2x2NoSolve() : Main where ForExploration = true

{

InsertVertex* || TSM2x2

}

Exploring this machine results in:

That is 16 distinct graphs with corresponding shortest tour values, which can be feed to a TSM solver. Of course these graphs are far from challenging, but it proves that we are able to grow graphs on a limited size domain. Also it serves to highlight the number of redundant graphs indicated by the high number of cross-over steps. Going just to a 3x3 lattice we immediately run into problems… There exist a ton of possible graphs we can grow. The largest grown graph has 8 nodes out of the maximum of 9. But let’s try instead to slice the model and only generate graphs starting from the center point of the lattice. We can easily do this on a 3x3 grid using:

config Grid3x3: Main

{

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

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

}

machine TSM3x3() : Main where ForExploration = false

{

construct model program from Grid3x3

where scope = "TravelingSalesManModel.TSMModelProgram"

}

machine TSM3x3CenterScenario() : Main where ForExploration = true

{

(InsertVertex(1,1) ; InsertVertex*) || TSM3x3

}

This machine slices the model by forcing the choice (1,1) for the first vertex. Exploration results in:

This is an extremely complicated solution. The problem here is of course that solution space (the number of applicable graphs) is itself extremely large, and because we are doing Model-Based Testing we are actively seeking to construct any feasible solution from this space.

It is fairly easy to construct a large set of test cases (this model constructs 240 test cases) from this problem space. They all pass against my crude implementation of a TSM solver. The problem however, is that they are not really taxing the implementation because they are all very small graphs, inside a tightly constrained grid. We can of course easily increase the size of the grid, however, the number of small graphs explodes even more.

Conclusion

We have seen how a model can be designed to grow graphs for the Traveling Salesman. However, the crude model struggles already on tiny input domains and produce a large number of uninteresting test cases. In the coming posts I will, formally prove that the algorithm for growing the graphs works. Furthermore, I plan on investigating how we can further slice the crude model to generate graphs of higher complexity.

[1] Traveling Salesman Model

Model Slicing with Spec Explorer

2012-02-03T12:32:00.000-08:00

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:

Let’s look at what we can do using slicing. In general slicing works like this:

machine Scenario() : Main where ForExploration = true

{

(A | B)

}

machine SlicedAccumulatorModelProgram() : Main where ForExploration = true

{

Scenario || AccumulatorModelProgram

}

You define a “scenario” and then you interleave it with your model program. The above scenario (A | B) will do either A or B, but only one of them:

We can also use slicing to fix a sequence of rules. Say we would like to first execute A then followed by B, we can do that using:

machine Scenario() : Main where ForExploration = true

{

(A ; B)

}

We can combine sequences by concatenating them:

machine Scenario() : Main where ForExploration = true

{

(A | B) ; (A ; B)

}

We can repeat a scenario:

machine Scenario() : Main where ForExploration = true

{

}

Repeating B is itself an infinite model because it simply grows the counter.

Interestingly we could also repeat A but this just yields:

Because flipping the sign on zero has no effect.

We can do B followed by A repeatedly instead:

machine Scenario() : Main where ForExploration = true

{

B ; A*

}

Now A has an effect, but it repeats over two values (-1 and 1) so the sliced model is finite.

Interestingly we can construct other repeated scenarios that also results in a finite model:

machine Scenario() : Main where ForExploration = true

{

(A; B)*

}

When repeating A followed by B this causes the combined action to alternate between increasing and decreasing the value.

This is just some of the very basic things that we can do using slicing. I will stop the example here and continue on to a real example.

Slicing applied to a binary search tree

Enough with the toy examples, let’s try this on the BST case. If you go back and read up on the BST model you will find that one of the conclusions we drew back then was that for MBT to generate a model that would provide us with 100% code coverage of the BST implementation we were forced to model trees of size 4, quoting:

“For this special case the node being deleted must have both a left and right sibling and in addition the right sibling must also have a left sibling […] it is simply not possible for the model to construct such a tree because it is limited to using 3 nodes. To cover this scenario, we would need to extend the model parameter ranges to Add and Remove from 0..2 to 0..3. […] Were you to generate the tests, you would end up with 193 test cases.”

The statement is still true; we need four nodes in the tree. But a generic 4-node model has shown to be overkill. Instead what we can do is fix the values of the two first nodes and then continue with the generic model from thereon. I will show you how we obtain this.

First we split the input range into two ranges, one which we use in our slicing (fixing parameters) and one that we let Spec Explorer choose parameters from:

config ParameterCombination: Main

{

action abstract static bool BSTTest.Add(int x)

where x in {0..1};

action abstract static bool BSTTest.Remove(int x)

where x in {-1,0..1};

}

config SlicedParameter: Main

{

action abstract static bool BSTTest.Add(int x)

where x in {-2..-1};

}

The slice will use x values -2 and -1, while the generic model will use 0 and 1. For the slice we do not intend to model the Remove method. You can very well also model Remove, it’s just not necessary. Keep in mind though if you were to model Remove generically on the inputs -2 to 1 then the model can Remove nodes -2 and -1 but it cannot re-add them.

Next we need to construct a model program for the sliced input parameter (-2 and -1). This is an exact copy of the generic model program just using a different input configuration:

machine SlicedModelProgram() : Main where ForExploration = false

{

construct model program from SlicedParameter

where scope = "Combinatorics.BSTModelProgram"

}

You can explore this model, but because we didn’t limit the input parameters to Remove, it will just explode (where you to implement the Remove method in the sliced configuration it would just be an exact duplicate of the model on 1 and 2).

The next step is to define the actual scenario we are interested in. To obtain the required base tree we need to add nodes -1 and -2 – in that order:

machine SlicedTreeScenario() : Main where ForExploration = true

{

Add(-1); Add(-2)

}

Too simple, right? You can explore this scenario:

Notice that this is just a static scenario – nothing is explored yet, thus some values are unknown.

Once we interleave this scenario with a model program, Spec Explorer will look for the sequence S0: Add(-1)/_ Add(-2)/_ in the model program and only include those branches that contains this sequence. The underscores are wildcards, that can take any value. In this case Spec Explorer will accept Add(-1)/True or Add(-1)/False. If you omit a parameter (or return value) it is treated as an underscore. You can also specify directly the required output to be True in our case, but it does not matter because the sequence Add(-1); Add(-2) will always return True for both rules. Where you instead to construct the scenario: Add; Add/False, then you tell Spec Explorer that the second Add call must return False which only happens in the cases where the same value was added twice (e.g. Add(-1)/True; Add(-1)/False). Hopefully this makes sense.

Now we interleave this scenario with our slicing model program to generate the sliced model:

machine SlicedTreeModelProgram() : Main where ForExploration = true

{

SlicedTreeScenario || SlicedModelProgram

}

And we can also explore this model:

Now that we have interleaved the actual model we get actual model exploration, which we can see by the fact that the states contain data. Now the exploration was fixed because we told it just to follow one scenario, but we are free to do more with this sliced model:

machine JoinedBSTModelProgram() : Main where ForExploration = true

{

SlicedTreeModelProgram ; BSTModelProgram

}

This joined model program starts out by exploring our sliced model program and then carries on exploring the generic model:

From the exploration graph it is evident that all states start out with the -1,-2 sequence, which is exactly what we wanted. The tree structure we wanted to build from the original description conforms with the tree built in state (-1,-2,1,0).

Because we fixed the input sequence to start with Add(-1); Add(-2) we obtain 4-node trees with the right construct with only 12 states, and generating tests from this model results in just 16 additional test cases instead of the 160 tests we got in addition when going to a 4-noded generic model.

Generating and executing the tests from the two models results in 100% code coverage of the BST class:

Conclusion

Model slicing is a powerful feature of Spec Explorer which allows you to generate additional models that are sliced subsets of a bigger model. This is very useful in cases where we are interested in the behavior of the system under some special circumstances – like the binary search tree example.

Using model slicing you can also model your system without any limitation, creating infinite state space models. Then this infinite model can be sliced into many finite models later. This allows you to think more about the system you are modeling and less about how to avoid the state space blowing up. Furthermore, you can use slicing as a means to look into your infinite model and see if it behaves correctly in a constraints environment. This can help you spot inconsistencies in your infinite models. Once you are happy with your infinite model you can let Spec Explorer go nuts on it using On-The-Fly testing.

You can also dictate exact scenarios if you are interested in some specific scenario. So in our BST case we could just have written:

machine Test() : Main where ForExploration = true

{

((Add(-1) ; Add(-2) ; Add(1) ; Add(0) ; Remove(-1)) || UnparameterizedBSTModelProgram)

}

To construct the exact scenario we were looking for. Although this has little to do with modeling, and we could just as well write a unit test to do that.

Are Test Oracles a mathematical nicety to cover-up problems?

2011-12-19T23:37:00.000-08:00

Last week I had an interesting discussion with a colleague that did not agree with my take on Model-Based Testing. He was unwilling to buy my arguments for why Model-Based Testing is a more efficient way of automating test cases compared to traditional scenario automation. He was a firm believer in Model-Based Testing but his experiences told him that modeling was an expensive cost up-front, which could be made up for in maintenance savings, whereas I claimed that modeling was a much cheaper automation approach.

Furthermore, he argued that my model was close to useless, because it did not come with a validation oracle. At a deeper level, the discussion also revealed some interesting discrepancies to me: He believed.

Needless to say, we never reached agreement on the subject – but I realized later on that we were arguing from completely different perspectives.

After the discussion I started thinking: “How can we be of so differing opinions?” After fumbling around with this question in my head over the weekend, I realized that we were using Model-Based Testing for two completely separate purposes.

A notion started to form in my head – it seemed that there were different ‘schools’ (or views) within Model-Based Testing.

· Theoretical modelers: They want strict rules around their models, and conduct rigorous validation in an effort to validate the conformity of their models. They have a theoretical approach to software testing and like to mathematically prove algorithms and construct test cases that cover just the necessary and sufficient cases.

· Pragmatic modelers: They are more of the ad-hoc modeling type. They have a pragmatic approach to Model-Based Testing in which a model is valuable on its own. They understand that the model should be validated, but they can live with limited validations. They see value in the model as a means for communication.

Of course, there is no right way of modeling. Both schools in the extreme limits are losing the grip on reality. If you dig yourself too deeply into the theoretical aspects of modeling you will stagnate, whereas a too pragmatic approach to modeling most likely results in low quality models.

However, I find myself to be closer related with the latter group. I tend to want to see my models grow before I care too much about validation.

My take on Test Oracles

This prelude story brings me to the actual point I want to discuss today: Test Oracles.

In software testing a Test Oracle is an entity in the system which – just like in the movie “The Matrix” – holds all the answers, at any point you can ask your test oracle “is the system in a valid state?” and it will tell you the answer. Very handy for Model-Based Testing!

Test Oracles are also these imaginary things that testers like to talk about, but no one have actually seen nor written. Okay, maybe I’m being a bit harsh here, but except for very isolated cases, Test Oracles are intractable because the complexity of the underlying system is too high. I have the feeling that in many cases problems are deferred by relying on some Test Oracles to be written in the “near future”, in an effort to ignore the tough problem of writing solid validation.

I believe the two Model-Based Testing schools are fundamentally different in their view on validation.

Theoretical modelers will seek to write strict Test Oracles at first, which is a really challenging task. I believe this is one of the reasons why Model-Based Testing is perceived as being difficult. If you start thinking too much about oracles and validations, you never get started on your modeling.

Pragmatic modelers on the other hand are much more likely to explore Model-Based Testing without dealing with the validation problems initially, and rely on Heuristic Oracles later on. This makes for a lower barrier to entry.

Heuristic Oracles are approximation oracle; they will tell you if something has gone totally awry. For example a heuristic invariant could be that a computed length value must never be negative.

In conclusion Test Oracles are nice for closed problems, where it is easy to identify invariants that are necessary and sufficient to prove an algorithm – like sorting algorithms or tree-structures. But, aside from the text-book examples on algorithms and data structures, frankly most test problems are infeasible to write Test Oracles for. For any large-scale system, writing an Oracle would be too time-consuming, and most likely it would end up being more complicated to maintain than the actual product you are trying to test. Heuristic Oracles are less strict in their validation, but they allow testers to get some value out of their initial modeling efforts, and lower the entry barrier.

[1] Heuristic Test Oracles

Requirements and Model-Based Testing: A rocky road

2011-12-06T00:11:00.000-08:00

This post is on something that has been bogging my mind a lot lately, which I haven’t been able to fully express, but I’m hoping getting it published will help me settle my mind.

I had the pleasure of attending the ETSI Model-Based Testing User Conference – and let me start by giving kudos to all the great people in the field attending and giving some sharp presentations!

At the conference I got a look into all the available vendor tools for Model-Based Testing (I won’t list them here; this is not supposed to be an advertisement blog). All of them are pretty powerful tools, and they allow you to build models from a set of requirements that you gather in the beginning. In the model you specify which actions corresponds to a certain requirement – e.g. in finance you may have a requirement that posting a sales order will produce a set of ledger entries so this requirement would be associated with the posting action. Some can even import your requirements from external tools, and keep track of changes to requirements. This is all pretty nice, and one tool showed the ability to visualize the impact of a requirement change directly in the rendered model view – now that is awesome!

A significant number of presenters at the conference were also happy to report that they had discarded existing metrics for quality of their software testing, and replaced it with requirements coverage. Meaning, they now record the number of times requirements are covered in their generated test suite.

But then a thought came to me:

“If I know all my requirements up-front, why would I use Model-Based Testing instead of just writing one or two scenario tests per requirement, which I know covers these requirements well?”

Well, the reason I would use Model-Based Testing is that it produces many more permutations of actions sequences that I would not care to test if I had to write the scenarios by hand. I usually start out writing a very crude and simple model, which has some limited value (it covers few and basic requirements) and then I see what happens when I run the tests. Almost always I find that some of my tests break because some preconditions were not met. This means that the executed action was not valid from the given state, and I have a model error. I then analyze these failures and turn them into preconditions on the actions, such that they are no longer executed from states where they are invalid in the SUT.

So what actually just happened here? By developing the model iteratively we start to reveal more information about the SUT, but every time we have to put in a precondition check on an action, we have actually uncovered an unknown requirement. For example we didn’t actually know that “you are not allowed to delete an item from a list if the list is empty” (sounds a lot like a requirement to me…) before we tried it! Once we tried doing it we uncovered an unknown or implicit requirement.

This sparked another thought:

“When was the last time I developed a feature where I knew all the requirements up-front?”

And the truth is, it never really happened, because most features I have worked on were either too complicated to document requirements fully, or the feature evolved over time because new ideas emerged.

In this new world of Scrum & Agile, modeling from your requirements feels very much like the old way of doing things – almost like the waterfall approach to software testing. In my view on Agile, the team cannot expect to fully understand the requirements when they set out to work on their feature.

Don’t get me wrong, I think it’s important to keep track of your requirements, and verify that they indeed are covered by your model and generated test suite. It serves as a sanity check, because modeling is a difficult challenge, and you can easily leave out a requirement in your model or generate a test suite that misses one or more requirements.

But please leave it at this, don’t get too focused on your known requirements, they are not what matters most. The real beauty of Model-Based Testing is its ability to uncover implicit requirements.

Model-Based Testing of Legacy Code – Part II – Risk Profiling

2011-11-13T08:04:00.000-08:00

Last time I left you after describing my latest challenge – making sense of a large piece of legacy code. I eluded to the fact that we started building a risk profile for the changelist that made up the difference between a well-tested root branch and a poorly tested branch.

Okay, so what did we do to tackle this immense problem? Well, our approach was to compute a risk profile based on a model of the probability of code lines containing bugs. Without digging too deep into the mathematics, this is how the profile is built:

A) All lines of code for files that differs are loaded into the profile

B) Each line of code is assigned two risk weights: Test coverage, and difference weights

C) For each file the weights are summed up and normalized and a third weight is introduced: Revision weight

The three weights are combined into a total weight for each code line and aggregated up to file level. The computation is a weighted average of the normalized weights, where the test coverage and difference weights are multiplied together:

Test coverage weight – this weight is used for reducing risk for lines of code that have good test coverage. The weight of a code line is reduced by 10% for every test case that covers this particular line of code. The more tests that hit the line of code the more the weight is reduced. The assumption is that tests are conditionally independent and that a given test case has 10% probability of detecting a bug on this code line. Furthermore, this 10% reduction is improved if the test case touches fewer code lines – the rationale is that the lower level the test is written at, the higher likelihood of validating the correct code line.

Difference weight – this weight is used for weighing the lines of code that were changed from our root branch higher than the ones that were not changed. In our programming language we distinguish between actual code lines and “empty” lines, which are lines that contain meta-data definitions and statements that are not actually executed at runtime (e.g. switch, try, catch, etc.). Empty lines cannot be covered by tests, and as such it makes no sense to include them in the risk profile – however, they can still be different from the root branch. The difference weight is set to 1.0 if the code line was changed and 0.0 if it was not changed. Empty lines that were changed are summed up and distributed evenly on all code lines – the rationale being that we cannot identify which code line carries the risk, so we split it over all code lines not to ignore the fact that a line was actually modified.

Revision weight – this weight kicks-in at the file level (on code lines it is zero), and it is extracted from the source control system and counts the number of changes that were made to the file from the time the branching was made. This effectively measures the “churn” on the files and weighs them by how often they are churned.

Sample risk profile

To illustrate what this profile looks like I’ve generated a sample profile for some of our code. The code has been obscured by removing file name references, but each column on the y-axis represents an individual source file, and the x-axis shows the associated percentage risk associated with a given file:

From this profile it is easy to spot outliers (or high risk files) that can be selectively targeted for test coverage. Also the profile gives you a strategy for reducing the risk at the fastest rate, by starting with the files with the highest risk and working downwards through the list. Furthermore, we can drill down on a single high risk file to look at the file level pattern.

This gives us a starting point for our analysis. If we were to ship the product right now we would incur 100% risk; however the risk profile allows us to give a reasonable estimate of the effort involved in reducing the risk. We can for example write tests for a single high risk file and thus estimate the effort required to reduce the risk by 3-4% (in our case). We can extrapolate this information and give an estimate on the effort required if we want to incur only 50% risk when shipping. Or if we are date-driven we know the amount of resources available, and can estimate the level of risk we will be shipping with.

By re-running the risk profile after additional tests have been produced and comparing the total absolute risk of the new profile with the baseline profile an accurate risk reduction factor can be computed.

However! It’s crucial to understand that a risk profile is relative to a certain baseline. That is, it tells you where to target your efforts to bring down the risk at the fastest rate from where you are now, but it does not tell you anything about the current state of the product – this understanding needs to come from you! A risk profile will always sum up to 100% risk. A product could be in excellent state and ready to ship, and if you run a risk profile on it at that point in time you will ship with 100% risk. Don’t make the mistake of comparing risk profiles for different branches either, as you will be mixing apples and oranges. A risk profile is relative, and if your baselines do not match up, neither will your risk profiles be comparable.

This was a pretty in-depth explanation of how we build risk profiles. I hope it is inspiring for others to read about our approach! Next time we will look into how we can use these risk profiles in our choice of automation strategy, and finally we will get to the Model-Based Testing part of it!

Model-Based Testing of Legacy Code – Part I

2011-11-02T03:54:00.000-07:00

It has been a while since I had time to post on this blog. I've been kept busy attending the Model-Based Testing User Conference - it had some really great presentation, that I also want to find some time on reporting on. I have a trip report ready, but I need to boil it down to the relevant stuff before I post it here. Granted, my next post is not going to be on Model-Based Testing, but it will however be the first in a series of posts that - with a bit of luck - will build up to some really interesting Model-Based Testing!

That being said, let's jump into it. Recently I’m being faced with a challenge of taking a large set of legacy code changes and test it in a way that is sensible. I work with a colleague in a two man team on solving this problem.

You can think of the changes as a source control branch. The root branch has good test coverage, but the new branch has no automated test coverage. The changes contains both added functionality to the product, but also smaller tweaks to existing code in the form of changes to existing functionality and regulatory changes.

The objective is of course to apply Model-Based Testing somehow, but the major challenges are:

A)     How do we make sense of this new branch?
B)     How do we approach automation of legacy functionality?
C)     How much can be obtained from modeling?

I will be writing a few blog posts for the coming weeks on the progress we make as we go along, but ultimately I would like to hear from my readers, what ideas they have on how to tackle this problem.

So let’s start with the first challenge...

How do we make sense of this new branch?

We decided to analyze the changes and group them into two sets: Features and integration points. A feature is a coherent set of changes that was developed in the same go, whereas integration points cover the incoherent changes that are either smaller or made over a longer period of time. Later we will see how this categorization affects the automation strategy we would like to apply.

Luckily we have documentation that names these features and link them to source files, so we do not have to make a detailed analysis to uncover what is coherent and what is not. Some documented features are small and can be seen more as integration points.

All integration points can be identified through a simple source code difference analysis. Notice this includes all features as well. It’s an open challenge how to identify overlap...

This was a brief introduction to the upcoming project from my side.

The next step that we are working on is coming up with a structured approach on how to handle legacy code, where we build a risk profile over the changes, more on this next week...

Dealing with floating points in models - Part II

2011-10-18T10:02:00.000-07:00

Today I’m going to follow up on Part I, but I’ll give you the implementation details of the classes. I provided you with a generic interface:

IDomainVariableSampler<T>

Now as I pointed out previously, we can choose to implement this interface for any domain type, so let’s try implementing it for a double domain:

public class DomainDoubleSampler : IDomainVariableSampler<double>

{

public double Maximum { get { return 100.0; } }

public double Minimum { get { return -100.0; } }

public double BoundaryNegative(double boundary)

{

return boundary - double.Epsilon;

}

public double BoundaryPositive(double boundary)

{

return boundary + double.Epsilon;

}

public double Sample(double lowerBound, double upperBound)

{

Random rand = new Random(1);

return lowerBound + rand.NextDouble() * (upperBound - lowerBound);

}

This implementation defines an input range of [-100.0, 100.0] and is sampling at random inside partitions of this interval.

Now we get to the tricky part of this post – we need somehow to cast this into something that is indexable. I touched on the DomainInput<T,X> class, which we will explore in detail:

public class DomainInput<T,X> : SequenceContainer<T>

where X : IDomainVariableSampler<T>, new()

where T : IComparable<T>

Yes, I know, double generics, but unfortunately this is needed when we use the generic IDomainVariableSampler interface. The way this works is that T defines the domain type and X is a class type that implements IDomainVariableSampler<T> - in other words X is a class implementing a sampler for the domain T. Say we have our class DomainDoubleSampler that implements IDomainVariableSampler<double>, instantiation of a DomainInput for this domain type looks like this:

var inputMap = new DomainInput<double, DomainDoubleSampler>()

Now I’m going to jump back to some of the implementation details in the DomainInput indexer class. The following methods help us instantiate our input domain:

public class DomainInput<T,X> : SequenceContainer<T>

where X : IDomainVariableSampler<T>, new()

where T : IComparable<T>

{

...

public static DomainInput<T,X> Empty { get { return new DomainInput<T,X>(); } }

private DomainInput()

{

X sampler = new X();

Add(sampler.Minimum);

Add(sampler.Maximum);

}

private DomainInput(DomainInput<T,X> clone)

{

AddRange(clone);

}

public DomainInput<T, X> Boundary(T b)

{

DomainInput<T,X> di = new DomainInput<T,X>(this);

di.Add(b);

//di.Add(b.BoundaryNegative()); // Use when Spec Explorer bug is fixed

//di.Add(b.BoundaryPositive());

di.Sort();

return di;

}

...

Notice that constructors are defined private, and the class is initially instantiated using the Empty property. The domain partitioning is then done using Boundary(T b) which returns a new instance of DomainInput. This allows the following constructor pattern:

DomainInput<T, X>.Empty.Boundary(B1).Boundary(B2).Boundary(B3);

The boundary values are automatically sorted, so they can be specified in any order. Notice that the Empty property automatically sets up boundary values for domain min and max ranges.

Next up, how do we use this class in our models? Well the implementation is a bit technical, but stay with me:

public class DomainInput<T,X> : SequenceContainer<T>

where X : IDomainVariableSampler<T>, new()

where T : IComparable<T>

{

...

public int NumberOfInputs { get { return 2 * Count - 1; } }

public bool ValidIndex(int index)

{

return index >= 0 && index < NumberOfInputs;

}

public T Input(int index)

{

Condition.IsTrue(ValidIndex(index));

if (index % 2 == 0)

{

// Boundary cases: Return boundary value

return this.ElementAt(index / 2);

}

else

{

// Domain cases: Sample domain

T lowerBound = this.ElementAt((index - 1) / 2);

T upperBound = this.ElementAt((index - 1) / 2 + 1);

X sampler = new X();

return sampler.Sample(lowerBound, upperBound);

}

...

First, notice that it derives from a SequenceContainer. So our DomainInput behaves like an immutable container, so you can enumerate elements just like you would a normal container. However, it has the special Input method, which will return either a boundary value (if index is even) or sample from a domain partition between two neighboring boundary values (if index is odd) – sampling domain partitions is done through the IDomainVariableSampler<T> interface, so this is the reason we had to implement this interface in the first place!

As I previously pointed out, you can define any sampling strategy through your custom implementation.

If you feel like it would be fun to implement this on your own custom boundary, please go ahead and send me your implementation (you can reach me at ‘simon’ dot ‘ejsing’ at ‘microsoft’ dot ‘com‘), and I’ll share it through this blog. Some ideas for input domains: Strings of length 1 to 5, complex numbers, email addresses, URL’s, etc.

James D. McCaffrey implements Recursive Binary Search Tree

2011-10-14T00:59:00.000-07:00

Today I came across this blog article by James D. McCaffrey, where he actually implements a recursive binary search tree, and I couldn’t resist the urge to apply my own Model-Based Testing solution [1,2] to his implementation!

I had to extend his solution a bit to allow for an internal validation function of any constructed tree, but besides from that my only comment to his solution is that he treats error conditions by silently ignore them – that is the following actions generate no errors/exceptions:

A) Deleting an element that does not exist in the tree.
B) Inserting an element twice into the tree.

Patching these up in his code, my model generated test cases all passed, so his implementation is rock-solid! Kudos for that!

References:

[1] Application of Model Based Testing to a Binary Search Tree - Part I
[2] Application of Model Based Testing to a Binary Search Tree - Part II

Domain input partitioning / dealing with floating points in models – Part I

2011-10-05T09:59:00.000-07:00

Originally I wanted to post everything in one article, but it got too long, so I decided to split it and save the hardcore details for the next post.

I find that dealing with models involving floating point input can be a tad tricky, so why not post on this topic? The problem here is infinity. It stems from the fact that any given slice of a floating point argument is of infinite size (or at least close to). Often when working with integer models we limit the input variables to a specified range like: where x in {0..2}. However, this does of course not work if x is a floating point input.

So how do we deal with infinity? First of all we need to clarify what it is we want. Clearly we do not want to test every possible floating point values between 0 and 2. Also, what we want is determined by what we are testing. So let’s make up an example. Assume we are to test the square root function (of real values to keep it simple), what kind of inputs would we give it? If you are a software tester your testing aptitude should kick-in right about now. We want to try a sunshine scenario with a positive value. We also want to make sure any negative input gives an error and also the boundary case 0 gives an error. Then we also have some extreme ranges like a very large positive number, a large negative number and the maximum and minimum values of the input type.

If we analyze our pattern here, all we are doing is partitioning the input domain. If you have been following this blog for a while you may recall I referenced equivalence class partitioning before – this is the same stuff. Simplifying a bit we end up with an input domain like:

The important part here is that we have fixed points of interest (the boundaries) and between we have ranges. For the boundary cases, besides the actual boundary value of interest is the near neighbors ±e, where e is a very small number. For the ranges we do not really care what the exact number is, for want of better we draw a random sample from the region.

Note on Spec Explorer and small floating point values:

Unfortunately I found a bug in Spec Explorer, that it crashes when working with small values in floating point. This limits me from trying out combinations where the parameter is e. The implementation of the automatic domain partitioning will thus also be limited to testing only at boundary cases and not their near neighbors as well.

So, let’s try and reduce this problem to some requirements. Clearly we would like to specify the domain we are working in, this could be integers single/double-precision floating point or even strings! The domain should also have specified a range (our MIN and MAX), and we need the ability to insert boundary values. That pretty much sums it up.

The great thing is that this can be solved using generics! The following interface defines a generic sampler for a domain that fits our specifications:

public interface IDomainVariableSampler<T>

{

T Maximum { get; }

T Minimum { get; }

T BoundaryNegative(T boundary);

T BoundaryPositive(T boundary);

T Sample(T lowerBound, T upperBound);

}

In appendix [1] you can find the source code along with implementations of the following domains:

public class DomainDoubleSampler : IDomainVariableSampler<double>

public class DomainIntegerSampler : IDomainVariableSampler<int>

We need a mechanism for converting an index into a boundary value or domain partition sample; this is handled by the following class:

public class DomainInput<T, X> : List<T>

where X : IDomainVariableSampler<T>, new()

where T : IComparable<T>

{

public static DomainInput<T,X> Empty

public int NumberOfInputs

private DomainInput()

private DomainInput(DomainInput<T,X> clone)

private void Sort()

public bool ValidIndex(int index)

public T Input(int index)

public DomainInput<T, X> Boundary(T b)

}

The DomainInput class is the heavy lifter of the solution; it handles any domain type implementing IDomainVariableSampler<T>. Using this implementation you simply call Input(int index) to either return a boundary value or sample from a domain partition.

Applying the DomainInput class

Let’s see how this works in practice. Observe the following model on a double domain:

public static DomainInput<double, DomainDoubleSampler> InputMap = DomainInput<double, DomainDoubleSampler>.Empty.Boundary(0.0);

...

static double value = 0.0;

[Rule(Action = "Compute(x)/result")]

static double ComputeRule(int x)

{

Condition.IsTrue(Accumulator.InputMap.ValidIndex(x));

value = Accumulator.InputMap.Input(x);

return Math.Round(value, 2);

}

Setting up a domain with a boundary value at 0.0 and exploring this tiny model shows off the capabilities of the solution and provides the following input pattern to the Compute method:

Here you can read off that it sampled the following values:

-100, -75.13, 0, 24.87, 100

Exactly as we wanted it to! Likewise we can do the same for an integer domain:

public static DomainInput<int, DomainIntegerSampler> InputMap = DomainInput<int, DomainIntegerSampler>.Empty.Boundary(0);

Now we sample:

-100, -23, 0, 77, 100

Or we can include an additional boundary value at 10:

public static DomainInput<int, DomainIntegerSampler> InputMap = DomainInput<int, DomainIntegerSampler>.Empty.Boundary(0).Boundary(10);

Sampling:

-100, -23, 0, 7, 10, 79, 100

Notice this is just a demo using exploration, normally you would not want to handle the floating point values in the model, here you would base your rules solely on the integer index, and then delegate the floating point conversion to the adapter layer, like this:

public class Accumulator

{

public static DomainInput<double, DomainDoubleSampler> InputMap = DomainInput<double, DomainDoubleSampler>.Empty.Boundary(0.0);

public static double Compute(int x)

{

return Math.Sqrt(InputMap.Input(x));

}

However, if you need validation to be handled by the model (using return types on rules) you would need to also convert the index to floating point inside the model, just remember to fix the random seed such that the random values sampled are the same between the model and the adapter.

Extendibility

One thing that is particularly nice about this solution is that it’s extendable through the IDomainVariableSampler<T> interface. This means you can extend it to any input domain you like, for example by adjusting the maximum and minimum range of inputs. You can also define your own input domain, one example could be strings following a sequence like: A, B, C, …, Z, AA, AB, … , ZZZZZZZZ – this is a perfectly valid input domain. Also the sampling of partitions is up to you. I used a random sample, but you could also pick the mid-point or any other value inside the partition. All you need to do is implement a sampler for your domain that implements X = IDomainVariableSampler<T>, where T is your primitive input then feed it to DomainInput<T,X>.

[1] Domain Input Partitioning Model

Comments fixed

2011-10-04T05:18:00.000-07:00

I realized today that comments were not working on my blog.

This should have been fixed now, and you should be able to post anonymous comments!

Sorry for the inconvenience, and please leave a comment to test the site.

Application of Model-Based Testing to a Stack

2011-09-22T00:24:00.000-07:00

Today I would like to go back to basics, and also show how to easily switch the underlying implementation. Some of my most read posts are on applying Model-Based Testing to basic data structures, so why not pick up yet another basic data structure?

This time I’m keeping it ultra-simple: The Stack.

I’m sure we all know what a stack is, but to briefly remind you it’s a LIFO (Last-in, first-out) container. In a classic stack elements are added on top of the stack using the “Push” command and removed from the top one-by-one using “Pop”. When an element is popped it is removed from the stack and returned. It is not possible to reference elements that are not on the top of the stack.

A not-so-classic stack variation contains a “Peek” function that will return the top element of the stack without removing it.

So without further ado let’s jump into modeling!

Implementation

For the purpose of this post I’ve re-implemented the wheel and written a fixed-size (10) integer based stack:

public class Stack

    {
        int[] items = new int[10];
        int count = 0;

        public Stack()
        {
        }

        public void Push(int x)
        {
            if (count >= items.Length)
                throw new Exception("Stack overflow");
            for (int i = count; i > 1; i--)
                items[i] = items[i-1];
            items[count++] = x;
        }

        public int Peek()
        {
            return items[0];
        }

        public int Pop()
        {
            if (count <= 0)
                throw new Exception("Popping empty stack");

            int x = items[0];
            for(int i = 0; i < count; i++)
                items[i] = items[i+1];
            count--;
            return x;
        }
    }

Pretty standard stuff.

Model

For modeling the stack we define the three actions and model them like this:

class StackModel

    {
        SequenceContainer<int> inputSequence = new SequenceContainer<int>();

        [Rule(Action = "new this.Stack()")]
        StackModel()
        {
        }

        [Rule(Action = "this.Push(x)")]
        void PerformPush(int x)
        {
            Condition.IsTrue(inputSequence.Count < 4);
            inputSequence.Add(x);
        }

        [Rule(Action = "this.Peek()/result")]
        int PerformPeek()
        {
            Condition.IsTrue(inputSequence.Count > 0);
            return inputSequence[inputSequence.Count - 1];
        }

        [Rule(Action = "this.Pop()/result")]
        int PerformPop()
        {
            Condition.IsTrue(inputSequence.Count > 0);
            int x = inputSequence[inputSequence.Count - 1];
            inputSequence.RemoveAt(inputSequence.Count - 1);
            return x;
        }
    }

In the config.cord script I have limited the input values for the “Push” action to 0 and 1. Also the model is limited to having at most 3 elements in the stack at any given time.

Exploration of this model yields:

Test cases

There’s an interesting fact about our model. Because every state is connected to all other states, traversing the graph with the “Long tests” strategy will yield only one test case. I don’t like this, so I’m going to change it to use “Short tests” strategy instead.

The generated test cases are:

An interesting fact is that I found two bugs in my implementation of the stack when running these generated tests (that tells you a bit about my coding skills – it’s a good thing I’m hired as a tester...):

1. Off by one error in the loop that shifts elements out

2. Push was inserting new elements at the bottom of the stack

            for (int i = count; i > 1; i--)
                items[i] = items[i-1];
            items[count++] = x;

I left the bugs in the sample, which you by the way can find in the reference list [1].

Testing .NET class libraries

Okay, so now we have tested that our stack implementation is not working, let’s try something funny! So .NET contains an implementation of a stack in System.Collections.Stack, wouldn’t it be interesting to check that the guys in .NET did a better job than me implementing a stack? Actually, SpecExplorer allows us to test any .NET class directly. We simply change the using declaration in the config.cord file:

using System.Collections;

//using StackModel.Sample;

And the type binding in the StackModel.cs file:

[TypeBinding("System.Collections.Stack")]

//[TypeBinding("StackModel.Sample.Stack")]

And re-generate our test suite. The model obviously stays the same (we didn’t change that) but the tests will now call into the .NET stack class implementation.

But wait a minute? We implemented an integer based stack, and the .NET stack holds any objects, then why does this work? It turns out that because the interface for our stack is a subset of that of the more generic .NET stack class, SpecExplorer can automatically cast the arguments from integers to Objects, and everything works out-of-the-box! That is pretty sweet.

Big surprise, running the generated test cases, they all pass! Kudos to the .NET guys for a good job, and I think I will stay on the testing path for now J

And finally I would really appreciate some feedback, so if you made it all the way down here, please leave a comment telling me what you think was good/bad about this post - thanks!

References

[1] Stack Model

Multi-Threaded Modeling – Barrier Synchronization

2011-09-06T04:07:00.000-07:00

Okay, all my previous posts have been based on static system models, where rules and actions are static functions in classes. A lot can be accomplished with this, and it is also possible to wrap instance based applications inside static functions. However, Spec Explorer allows us to work with actual instance based models.

So what does this mean for us? Well, it means we are allowed to instantiate any number of objects of some type and Spec Explorer can reference each of these objects individually. For example, you could write a class that represents a complex number, and have Spec Explorer create two instances of this object and then add them together. This would be a basic example, but instead let’s jump to something more tricky – multi-threading!

You can imagine that instance based modeling and multi-threading are closely related. But there are some key issues one must understand first. Instance based modeling is not multi-threaded, it is exactly as sequential as any static model. Spec Explorer will not create a new thread for you when you instantiate an object. Any interaction by Spec Explorer will be from the “main”-thread, you have to handle communication with your threads.

Barrier synchronization

The example I have picked for this post is a barrier synchronization implementation. Barrier synchronization is a pattern for worker threads in multi-threaded application. With barrier synchronization each thread must wait for its co-workers to complete their cycle of work before the next cycle starts. Denoting the number of cycles completed by thread i as c_i, this can be stated by the following invariant:

Essentially each thread reaches a “barrier” upon completion of its work. This “barrier” is only lowered once all threads have reached it. Upon release of the “barrier” the worker threads continues their work.

Implementation of barrier synchronization

First of all, we capture the threading in a class

public class BarrierThread

{

...

Thread thread;

bool abortOnSynchronize = false;

volatile int workCycles = 0;

volatile bool abort = false;

public BarrierThread()

{

thread = new Thread(() => ThreadMain());

...

}

public void Start()

{

thread.Start();

}

private void ThreadMain()

{

...

} while (!abort);

}

public int Synchronize()

{

...

}

There are a couple of things to point out here. I’ve cut away the tricky implementation details at first, but essentially the constructor spawns a new thread which can be started with a call. This thread goes into a loop until aborted. Notice there is a couple of variables that are declared volatile to avoid compiler optimization around these – this is important because they are shared between the main thread and the worker threads!

The difficult parts of the implementation are the thread body, synchronization and abortion, but I’m not going into detail with that right now, you can refer to the sample [1].

Modeling barrier synchronization

Before I go on to describe the model a word of warning is in place. The config.cord file is very different from that of a static model, but I don’t want to dwell on that – I may do a follow up post on this if I find the time for it.

For my implementation the threads are modeled with the following interface:

enum ThreadState { Unstarted, Started, Aborting, Aborted };

// Starts the worker thread

[Rule(Action = "this.Start()")]

void Start()

// Aborts the worker thread upon next synchronization

[Rule(Action = "this.Abort()")]

void Abort()

// Barrier synchronization of all worker threads, returns the current worker thread cycle count

[Rule(Action = "this.Synchronize()/result")]

int Synchronize()

The ThreadState enum enumerates the states our threads can be in from the model perspective. The Start and Abort rules just change current thread state. Threads that are aborted will be set to an intermediate state for actual abortion upon next synchronization.

It should be noted that each rule in the model applies to any instance of our class. This means that the model exploration will call Start, Abort and Synchronize on any instance. This is important to understand, because if all threads jump into the synchronization rule they will hang waiting on each other. The implementation details of the synchronization rule are:

// Barrier synchronization of all worker threads, returns the current worker thread cycle count

[Rule(Action = "this.Synchronize()/result")]

int Synchronize()

{

Condition.IsTrue(synchronizations++ < 3);

for(int i = 0; i < threads.Count; i++) {

Condition.IsTrue(threads[i] != ThreadState.Unstarted);

Condition.IsTrue(threads[i] != ThreadState.Aborted);

if (threads[i] == ThreadState.Aborting)

threads[i] = ThreadState.Aborted;

}

return synchronizations;

}

First we are limiting the number of working cycles to perform to 3. Notice that synchronization is not allowed before all worker threads are started or aborting, this is essential, because otherwise the main thread will be hanging unable to start all workers. This is an example of where we need to remember that model exploration is sequential.

This is all there is to the model. With two threads exploration yields:

One problem with the model/implementation is that you can abort one thread while the other is still active. The implementation does not accurately track that the number of threads decreased, as such this is not allowed and our implementation would run into deadlock in case this happens. Also, if one or more threads are not aborted upon test completion the test will hang because remaining threads have not terminated.

The way we handle this is simply to state that states are only acceptable if all threads have been aborted in the end:

// Accept only end states where all threads are aborted

[AcceptingStateCondition]

bool Accepting()

{

for (int i = 0; i < threads.Count; i++)

if (threads[i] != ThreadState.Aborted)

return false;

return true;

}

When generating test cases we can filter to only end-states that are accepting states.

Test generation

The test generation is filtered to only accepting end-states using:

machine ThreadTestSuite() : Main where TestEnabled = true

{

construct test cases where strategy = "longtests" for

construct accepting paths for Sliced2ThreadModelProgram()

}

The key word here is the “accepting paths” construct. This is pretty nice, because we can keep the model showing that it has this “flaw”, while still generating only tests that we know satisfy our conditions for the implementation (i.e. abort all threads before finishing).

The generated test cases are:

Running concurrent tests

When running concurrent tests, one type of bugs we are looking for is deadlocks. The problem is of course that in this case the test case will hang until it times out. It is a good idea to decrease the test timeout to a small value. In my case I’m decreasing it to 10 seconds as this is sufficient time for my tests to complete.

Doing so requires that you add a testsettings file. This is done from right-clicking the solution and adding a new item. It took me a while to figure this out, as I was trying to add it to the test project at first, but this is not possible.

Conclusion

Although instance based modeling is the way to go when testing concurrent systems, care has to be put into designing the adapter layer. From my experience developing this sample model you will run into situations where the generated tests deadlocks. In many cases this is due to implementation issues, but getting the model right is also tricky. Fortunately a lot of headaches can be avoided by filtering invalid states out, like I did for cases where some threads were left running. In this respect model based testing is actually a very powerful tool for writing concurrent test scenarios.

[1] Barrier synchronization model

Model-Based Testing in Agile Development Cycles – Part II

2011-08-21T12:48:00.000-07:00

Last post I left you hanging after a model had emerged from our initial acceptance requirements. The model we generated looked like:

Today’s post is about what you can use this model for in agile development, and what kind of test cases it produces.

Design discussions

As I already pointed out in the previous post, models are great in discussions. Often when you explain the model to the product owner he/she will start noticing quirks. For the example model we developed, one such quirk is that the system is not allowed to reverse a payment if said payment has been involved in a financial application. Although it is a requirement in the system, it was not mentioned in the acceptance criteria because it is not a sun-shine scenario. Design discussions based on models will help you uncover these implicit requirements.

It’s easy to solve these quirks when you are at the modeling stage, whereas maintaining traditional scenario based tests can require a lot of effort when requirements change. A benefit from modeling in Agile is that you uncover these implicit requirements early in the development cycle.

In our case we can fix the problem either by adjusting the model to avoid taking the ReversePayment action from states where the payment has been involved in a financial application. But more often than not, we would actually like to have a test case that checks that this implicit requirement is working – that is we would like the model to actually try doing it, but to expect a failure. We update the rule to:

        [Rule(Action = "ReversePayment/result")]
        static bool ReversePayment()
        {
            Condition.IsTrue(Entries > 0);
            if (Applications > 0)
                return false;

            Entries--;
            return true;
        }

Two things happen

a) The return value of ReversePayment from the model rule is matched against the return value of the adapter layer when executing tests.

b) The state space will not change if financial applications exist, making the rule a self-looping action.

Our new model looks like:

Notice how the return value of the ReversePayment rule differs between state S4 and S8, and how the latter is a self-looping action. This is of course because in state S8 the payment is involved in a financial application. Because we modeled the return code we will see that the test generation will construct scenarios where we test the implicit requirement is enforced by the system.

Tests

Okay, enough design discussions. Let’s look at the actual outcome! Exploring the test case generation we find:

What you immediately notice is that we recover our 4 original acceptance scenarios (encircled in orange). I encourage you to go back to part I and check the scenarios match. We also find tests covering our implicit requirement. In total we got 11 test cases out of the model even though it was built from just 4 acceptance tests. So not only should you find all your acceptance scenarios in the generated test suite, but you should expect that the model does a more thorough job as well! Actually, if you find that not all of your acceptance criteria are represented by the generated test cases, you should go back and revisit your model to look for any bugs in the design.

Conclusion

Not only does the model serve as a great input to design discussions, it will also automatically produce all your acceptance scenarios. That means when the model adapter layer and the feature you are testing are complete, you simply run your Model-Based test suite as your acceptance criteria.