In this post I’ll go through the basics for “stochastic use case testing”. It is sometimes called also “Markov chaining” or “Markov testing”. There are variations of this technique, of course, but my aim here is to cover the common ground and share some thoughts on where methods like this are best applied.
Here (on the right) is a simple “stochastic use case model” or “probabilistic user model”. This model represents the basic activity flow for a user who logs into a web site to purchase something. [Click on the image to zoom it if it appears too small.] The three gray circles are “states”, and the one with bold circumference is the “start state”. The yellow rectangles denote actions that the user can take, and the probabilities on them denote their estimated or measured probabilities. All the actions that can be taken from a single state have their probabilities sum up to 100%, so that for example “Successful login” and “Failed login” together add to 80% + 20% = 100%.
Because a system that has “states” and “transitions” with probabilities on them is called a “Markov chain” by mathematicians, the test generation paradigm I’m covering here is sometimes also known as “Markov chaining” or “Markov testing”. However, “probabilistic use case testing” or something like that makes perhaps more sense to a non-mathematician.
The big idea now is that every path that begins from the start state (“Logged out”) and ends at the same start state can be converted into a test. One example of such a path is:
- Failed login
Another, slightly more interesting path, is:
- Successful login
- Add items
- Checkout
- Logout
Because the actions carry probabilities, it is possible to calculate the compound probabilities for these two paths. The first path has compound probability 20%, and the second 80% x 80% x 10% x 98% = 6.272%.
Now, when you have a probabilistic user model like the one here, you can use a tool or a hand-written program to calculate an interesting set of paths, i.e. an interesting set of test cases, from the model, and I’ll now cover some ways to generate test sets next.
Random Sampling
One method to generate paths from a user model is to random sample paths according to the probabilities on the actions. For example, with this model every 5th randomly generated path would be “Failed login”, and 4/5 out of the generated paths would start with “Successful login”. Most stochastic test generation tools implement this simple option.
Common Paths
Another option is to generate the most common paths through the model. For example, I wrote a simple computer program that enumerated all those paths through our example model that have compound probability of 10-5 or higher (that is, 0.001% or more). There are 1750 such paths, and when I sum up their probabilities I get to 96.3%. This means that executing those 1750 paths as (preferably automated) tests, I have covered 96.3% of the typical user behavior.
The most probable path is still “Failed login”, because it is the only path that gets very quickly back to the start state (remember that I’m only considering paths that begin and end at “Logged out”). The next path is “Successful login”, “Checkout”, “Logout” and the next one is “Succesful login”, “Add items”, “Checkout”, “Logout”. The least probable path in this set, with probability 10-4.983, is “Successful login”, do “Add items” 37 times, and then “Logout”.
Executing the common paths as tests can be useful, because this approach focuses on the “normal” use of the system. However, sometimes you might want to explicitly test for the uncommon case.
Uncommon Paths
I implemented another option to my simple program to enumerate also those paths that (1) have at most 10 action steps and that (2) have compound probability below 0.001% (as these cases are already covered in the Common Path test set). There are 2107 such additional uncommon path tests, and together with the initial tests these take the coverage figure from 96.3% to 96.5%. This shows that from a risk management perspective, these 2107 additional tests have less value than the original test set. However, they could be very good in exposing difficult-to-spot errors in the system. For example, the most improbable test in the whole test set is “Successful login”, do “Checkout / Continue shopping” four times and then “Logout” (without adding anything to the shopping basket throughout the test).
Transition Cover
It is also possible to ignore the probabilities and generate a small test set for transition cover, i.e. generate just enough paths so that every action in the model is covered at least one. A simple transition cover test set for my example model could be:
- Failed login
- Successful login
- Logout
- Successful login
- Add items
- Remove items
- Checkout
- Continue shopping
- Checkout
- Logout
These ten steps are enough to cover all the eight actions in the model. Two actions have to be executed twice (Successful login and Checkout) because there are two distinct states where one can logout and because “Done shopping” has two actions behind it, and you can only get to “Done shopping” by “Checkout”.
Comparing the Methods
Transition cover, random sampling, common cases and uncommon cases are all valuable test generation methods. The unique benefit of transition cover is verifying rapidly that all the actions have been implemented. Random sampling is unbiased and its unique benefit is that you can execute tests based on random sampling as long as you can, and the longer you can, the better your chances of spotting additional errors. The unique benefit of enumerating the common cases is that you cover system’s typical use in a robust manner and thus significantly reduce the risk of failure in day-to-day use. And testing the uncommon cases is good because that can easily spot implementation inconsistencies.
Where it Fits
Stochastic use case testing can be applied well in those contexts where, on some level, the system under test can be depicted as a relatively simple finite state machine. Of course, an actual web shop is not a simple finite state machine, but rather a system consisting of presentation and business logic layers, databases, web frameworks, interpreters and so on. However, the key is that if it possible with meaningful effort to realize the paths that you can find from an abstract finite state model as actual tests (for example, during test execution, fill in the login parameters and put in some examples of items that can be added to the shopping basket), then that can be enough.
How to Implement Stochastic Use Case Testing
There exist relatively simple commercial tools that can help you in enumerating the paths through a finite-state model, the available test generation options and mathematical methods employed varying. If you can program, it is also simple to write such an enumerator by yourself. The enumerator I used to get the numerical results in this post takes a total of 155 lines of C++ code and less than an hour to write.