Introduction to TestApi – Part 4: Combinatorial Variation Generation APIs

Series Index

• Overview of TestApi
• Part 1: Input Injection APIs
• Part 2: Command-Line Parsing APIs
• Part 3: Visual Verification APIs
• Part 4: Combinatorial Variation Generation APIs
• Part 5: Managed Code Fault Injection APIs
• Part 6: Text String Generation APIs
• Part 7: Memory Leak Detection APIs
• Part 8: Object Comparison APIs

+++

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:

1. 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);
2. 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;
3. 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:

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

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.

 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

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:

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++;
        }
    }
}

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.