The state and behavior of every software system depends on a number of parameters. These parameters can be both inputs as well as environmental factors.
One can think of software testing as a controlled experiment, where the system under test is observed upon varying of the parameters that affect it, in an attempt to discover unexpected system behavior.
Depending on who you talk to, the act of generation of these variations is called variation generation, matrix expansion, design of experiments (DOE), etc.
+++
The Problem
Modern-day software systems are complex and depend on many parameters. Expanding all possible combinations of all parameter values often results in a phenomenon called matrix explosion – having an overwhelmingly high number of test variations.
Matrix explosion is undesirable because:
- It increases the runtime of your tests (which, among other things, makes TDD impractical and TDD is the single most effective way to ensure high product quality);
- It increases the support costs of your tests – for a test pool of 100,000 tests, even with 99% pass rate (which in reality is hard to achieve), you still have to investigate 1,000 test failures. Investigating 1,000 test failures is always more expensive than investigating say 10 failures;
- It is often impractical or impossible to cover all combinations, so you end up with partial test coverage (very often “vanilla” test coverage).
There are many ways to deal with matrix explosion, which depend on various system and/or experimental constraints. The theory and practice of DOE deals with that.
TestApi’s Solution
TestApi provides a generic API for combinatorial variation generation, using the algorithm presented in Jacek Czerwonka’s “Pairwise Testing in Real World” article. The API uses the following nomenclature:
- Parameter – represents a single factor / variable and its values;
- Constraint – represents a relationship between parameters, their values, constants, and other constraints;
- Model – contains all parameters and constraints for the system, for which we are generating variations;
- Variation – represents a tuple with a single value for every Parameter in the Model.
All of these are represented as correspondingly named types. Following are several examples demonstrating the use of the API.
Example 1 : Simple Matrix
For the purposes of a simple artificial example, consider having a system with the following parameters and values:
| Parameter |
Values |
| Color |
White, Green, Red |
| Height |
Short, Tall |
| Size |
Small, Medium, Large |
Assuming, there are no constraints, here is the code you would use to create a model
using System;
using System.Collections.Generic;
using Microsoft.Test.VariationGeneration;
class Example1
{
static void Main(string[] args)
{
//
// Declare all parameters and construct a model
//
Parameter p1 = new Parameter("Color") { "White", "Green", "Red" };
Parameter p2 = new Parameter("Height") { "Short", "Tall" };
Parameter p3 = new Parameter("Size") { "Small", "Medium", "Large" };
Model m = new Model(new List<Parameter>
{ p1, p2, p3 } );
//
// Generate and print out all possible variations of the parameters in the model
//
foreach (Variation v in m.GenerateVariations(3, 1234))
{
System.Console.WriteLine("{0}\t{1}\t{2}", v[p1.Name], v[p2.Name], v[p3.Name]);
}
}
}
Executing the code below produces the following 3*2*3=18 variations, representing all possible combinations of the values of the three parameters:
> Example1.exe
White Short Small
White Short Medium
White Short Large
White Tall Small
White Tall Medium
White Tall Large
Green Short Small
Green Short Medium
Green Short Large
Green Tall Small
Green Tall Medium
Green Tall Large
Red Short Small
Red Short Medium
Red Short Large
Red Tall Small
Red Tall Medium
Red Tall Large
The variations are generated by the call to GenerateVariations(3, 1234). The number "1234" is the seed for the random generator, utilized by the algorithm. The number "3" is the order of the generated combinations. The order of generated combinations must be a number between 1 and the number of parameters in the model. The output for orders "1" and "2" are presented below:
Output for order "1":
White Short Small
Green Tall Medium
Red Short Large
Output for order "2":
White Short Small
White Tall Medium
White Short Large
Green Tall Small
Green Short Medium
Green Tall Large
Red Short Small
Red Tall Medium
Red Tall Large
Example 2 : Vacation Planner
This example (created by Nathan Anderson – our engineer who designed and implemented the combinatorial variation generation API) demonstrates the use of parameter constraints.
Parameter destination = new Parameter("Destination") { "Whistler", "Hawaii", "Las Vegas" };
Parameter hotelQuality = new Parameter("Hotel Quality") { 5, 4, 3, 2, 1 };
Parameter activity = new Parameter("Activity") { "gambling", "swimming", "shopping", "skiing" };
List<Parameter>
parameters = new List<Parameter>
{ destination, hotelQuality, activity };
List<Constraint> constraints = new List<Constraint>
{
new IfThenConstraint
{
If = destination.Equal("Whistler").Or(destination.Equal("Hawaii")),
Then = activity.NotEqual("gambling")
},
new IfThenConstraint
{
If = destination.Equal("Las Vegas").Or(destination.Equal("Hawaii")),
Then = activity.NotEqual("skiing")
},
new IfThenConstraint
{
If = destination.Equal("Whistler"),
Then = activity.NotEqual("swimming")
},
};
Model model = new Model(parameters, constraints);
//
// Call the method under test with each generated variation
//
foreach (var variation in model.GenerateVariations())
{
CallVacationPlanner(
(string)variation[destination.Name],
(int)variation[hotelQuality.Name],
(string)variation[activity.Name]);
}
Example 3 : The WPF Platform Matrix
This last example demonstrates how we deal with a real-world problem we face in the WPF team...
WPF must work reliably on all OS configurations, defined by the following matrix:
| Parameter |
Number of Values |
Values |
| OS |
6 |
XP SP2, Vista SP1, 7, Server 2003 SP2, Server 2008 SP1, Server 2008 R2 |
| Language |
25 |
(using 3-letter language abbreviations) ARA, CHS, CHT, CSY, DAN, DEU, ELL, ENG, ESN, FIN, FRA, HEB, HUN, ITA, JPN, KOR, NLD, NOR, PLK, PSE, PTB, PTG, RUS, SVE, TRK |
| System Locale |
2 |
Same as OS language, TRK |
| Flavor |
2 |
Free, Checked |
| Platform |
3 |
x86, x64, x64 wow |
| IE version |
3 |
OS default, IE7, IE8 |
| High DPI |
2 |
120 DPI, 96 DPI |
| Theme |
6 |
Native, Classic, Luna, Royale, Classic High Contrast, Aero |
| Side-by-side |
9 |
3.5 SP1 + 4 (3.5 tests), 3.5 SP1 + 4 (4 tests), 3.5 SP1 + 4 - 4 (3.5 tests), 4 + Mock 4.5 (4 tests), 4 + Mock 5 (4 tests), 4 + 3.5 SP1 (4 tests), 4 + 3.5 SP1 (3.5 tests), 4 + 3.5 SP1 - 4 (3.5 tests), 4 (4 tests) |
Most of the parameters are self-descriptive. “Side-by-side” captures the .NET installation state. For example “3.5 SP1 + 4 - 4 (3.5 tests)” means “install .NET 3.5 SP1, install .NET 4, uninstall .NET 4, run tests built against 3.5 SP1”. This is done to confirm that there are no unexpected side effects as a result of the installation and un-installation of .NET 4.
The trivial full expansion of the matrix results in 583,200 combinations (=6*25*2*2...). Of course, some of these combinations (e.g. XP SP2 OS with a Aero theme) are not valid, but even after removing the invalid combinations, we still end up with a prohibitively large number of platform configurations to test on.
There are several ways to deal with this problem. One is identifying the so called equivalence classes. For example, from the point of view of Side-by-Side, Vista SP1 and Server 2008 SP1 can be regarded as equivalent OS-es and so on. Another popular approach is reducing regular testing to “vanilla configurations” (e.g. mostly ENG (English), 96-DPI configurations), venturing outside of the “vanilla domain” in accordance with a predefined schedule (e.g. during test passes at the end of major milestones). A third approach is using a pair-wise combinatorial variation generator, reducing the number of platform variations to about 230 – still a fairly high number for any real-world test pool, but clearly much better than the original number above.
In the WPF team, we use the third approach, combined with an adaptive random algorithm, which prioritizes testing on platform configurations that have not been tested on recently. The simplified code below demonstrates how to construct a model for platform config variation generation.
using System;
using System.Collections.Generic;
using Microsoft.Test.CommandLineParsing;
using Microsoft.Test.VariationGeneration;
using Microsoft.Test.VariationGeneration.Constraints;
public class OsVariationGeneration
{
public static void Main(string[] args)
{
CommandLineDictionary d = CommandLineDictionary.FromArguments(args);
int order = Int32.Parse(d["order"]);
int seed = Int32.Parse(d["seed"]);
//
// Parameters
//
Parameter os = new Parameter("OS") { "Windows XP SP3", "Windows Vista SP1", "Windows 7", "Windows Server 2003 SP2", "Windows Server 2008 R2" };
Parameter language = new Parameter("language") { "ARA", "CHS", "CHT", "CSY", "DAN", "DEU", "ELL", "ENG", "ESN", "FIN", "FRA", "HEB", "HUN", "ITA", "JPN", "KOR", "NLD", "NOR", "PLK", "PSE", "PTB", "PTG", "RUS", "SVE", "TRK" };
Parameter sysLocale = new Parameter("sysLocale") { "SameAsOsLanguage", "TRK" };
Parameter flavor = new Parameter("flavor") { "fre", "chk" };
Parameter platform = new Parameter("platform") { "x86", "x64", "x64wow" };
Parameter ieVersion = new Parameter("ieVersion") { "osDefault", "ie7", "ie8" };
Parameter highDpi = new Parameter("hiDpi") { "yes", "no" };
Parameter theme = new Parameter("theme") { "Classic", "Luna", "Royale", "Classic High Contrast", "Aero Basic", "Aero Glass" };
Parameter sxs = new Parameter("sxs")
{
"3.5 SP1 + 4 (3.5 tests)",
"3.5 SP1 + 4 (4 tests)",
"3.5 SP1 + 4 - 4 (3.5 tests)",
"4 + Mock 4.5 (4 tests)",
"4 + Mock 5 (4 tests)",
"4 + 3.5 SP1 (4 tests)",
"4 + 3.5 SP1 (3.5 tests)",
"4 + 3.5 SP1 - 4 (3.5 tests)",
"4 (4 tests)",
};
List<Parameter>
parameters = new List<Parameter>
{ os, language, sysLocale, flavor, platform, ieVersion, highDpi, theme, sxs };
//
// Constraints
//
List<Constraint> constraints = new List<Constraint>
{
new IfThenConstraint
{
If = os.Equal("Windows XP SP3").Or(os.Equal("Windows Server 2003 SP2")),
Then = theme.NotEqual("Aero Basic")
},
new IfThenConstraint
{
If = os.Equal("Windows XP SP3").Or(os.Equal("Windows Server 2003 SP2")),
Then = theme.NotEqual("Aero Glass")
},
new IfThenConstraint
{
If = os.Equal("Windows 7").Or(os.Equal("Windows Server 2008 R2")),
Then = theme.NotEqual("Luna")
}
};
//
// Model
//
Model m = new Model(parameters, constraints);
uint i = 0;
foreach (Variation v in m.GenerateVariations(order, seed))
{
Console.WriteLine(
"{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6}\t{7}\t{8}\t{9}",
i,
v[os.Name],
v[language.Name],
v[sysLocale.Name],
v[flavor.Name],
v[platform.Name],
v[ieVersion.Name],
v[highDpi.Name],
v[theme.Name],
v[sxs.Name]
);
i++;
}
}
}
Conclusion
Pairwise variation generation is an important tool in your toolbox as a test author. TestApi provides a simple facility for combinatorial variation generation. We will of course be evolving this facility, but do let us know if you have specific scenarios or requirements you'd like to see supported.