+++
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.
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:
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 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:
All of these are represented as correspondingly named types. Following are several examples demonstrating the use of the API.
For the purposes of a simple artificial example, consider having a system with the following parameters and values:
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 // var p1 = new Parameter<string>("Color") { "White", "Green", "Red" }; var p2 = new Parameter<string>("Height") { "Short", "Tall" }; var p3 = new Parameter<string>("Size") { "Small", "Medium", "Large" }; var m = new Model(new List<ParameterBase> { p1, p2, p3 } ); // // Generate and print out all possible variations of the parameters in the model // foreach (var 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
This example (created by Nathan Anderson – our engineer who designed and implemented the combinatorial variation generation API) demonstrates the use of parameter constraints.
var de = new Parameter<string>("Destination") { "Whistler", "Hawaii", "Las Vegas" }; var ho = new Parameter<int>("Hotel Quality") { 5, 4, 3, 2, 1 }; var ac = new Parameter<string>("Activity") { "gambling", "swimming", "shopping", "skiing" }; var parameters = new List<ParameterBase> { de, ho, ac }; var constraints = new List<Constraint<Variation>> { Constraint<Variation> .If(v => de.GetValue(v) == "Whistler" || de.GetValue(v) == "Hawaii") .Then(v => ac.GetValue(v) != "gambling"), Constraint<Variation> .If(v => de.GetValue(v) == "Las Vegas" || de.GetValue(v) == "Hawaii") .Then(v => ac.GetValue(v) != "skiing"), Constraint<Variation> .If(v => de.GetValue(v) == "Whistler") .Then(v => ac.GetValue(v) != "swimming"), }; var model = new Model(parameters, constraints); // // Call the method under test with each generated variation // foreach (var vacationOption in model.GenerateVariations(2, 1234)) { Console.WriteLine("{0}, {1} stars – {2}", vacationOption["Destination"], vacationOption["Hotel Quality"], vacationOption["Activity"]); }
The execution of this code would result in output similar to the following:
Las Vegas, 5 stars -- gambling Hawaii, 5 stars -- swimming Whistler, 5 stars -- shopping Whistler, 5 stars -- skiing Las Vegas, 4 stars -- gambling Hawaii, 4 stars -- swimming Whistler, 4 stars -- shopping Whistler, 4 stars -- skiing Las Vegas, 3 stars -- gambling Hawaii, 3 stars -- swimming Whistler, 3 stars -- shopping Whistler, 3 stars -- skiing Las Vegas, 2 stars -- gambling Hawaii, 2 stars -- swimming Whistler, 2 stars -- shopping Whistler, 2 stars -- skiing Las Vegas, 1 stars -- gambling Hawaii, 1 stars -- shopping Las Vegas, 1 stars -- swimming Whistler, 1 stars -- skiing Las Vegas, 1 stars – shopping
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:
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; 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 // var os = new Parameter("OS") { "Windows XP SP3", "Windows Vista SP1", "Windows 7", "Windows Server 2003 SP2", "Windows Server 2008 R2" }; var 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" }; var sysLocale = new Parameter("sysLocale") { "SameAsOsLanguage", "TRK" }; var flavor = new Parameter("flavor") { "fre", "chk" }; var platform = new Parameter("platform") { "x86", "x64", "x64wow" }; var ieVersion = new Parameter("ieVersion") { "osDefault", "ie7", "ie8" }; var highDpi = new Parameter("hiDpi") { "yes", "no" }; var theme = new Parameter("theme") { "Classic", "Luna", "Royale", "Classic High Contrast", "Aero Basic", "Aero Glass" }; var 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)", }; var parameters = new List { os, language, sysLocale, flavor, platform, ieVersion, highDpi, theme, sxs }; // // Constraints // var constraints = new List> { Constraint .If(v => os.GetValue(v) == "Windows XP SP3" || os.GetValue(v) == "Windows Server 2003 SP2") .Then(v => theme.GetValue(v) != "Aero Basic"), Constraint .If(v => os.GetValue(v) == "Windows XP SP3" || os.GetValue(v) == "Windows Server 2003 SP2") .Then(v => theme.GetValue(v) != "Aero Glass"), Constraint .If(v => os.GetValue(v) == "Windows 7" || os.GetValue(v) == "Windows Server 2008 R2") .Then(v => theme.GetValue(v) != "Luna"), }; // // Model // var 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++; } } }
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.