Testing beyond infinity with Configuration Reduction

The degrees of freedom that define a test environment vary greatly. Physical products or production lines often face a lot more degrees of freedom

Testing a website in different browsers on different OS environments are only two degrees of freedom with which you can set up test environments. Even here we will restrict the browser types and OS versions. Using usage data gives you the handle to cover a defined end user situation. If you want to test 4 browser types in 6 OS versions, this leads to 24 test environments where you want to execute the same set of tests. With test automation and virtual test environments the scale-up of test execution can well be mitigated in this situation.

A series of robotic arms for a welding production line face a lot more degrees of freedom. To name a few: Different versions of embedded software running on their control applications, PLC’s that measure and execute, other machines around the welding robots to communicate with or the different factory layouts for different plants. The degrees of freedom for these types of setups can easily reach into the hundreds if not thousands. Each degree of freedom can have unlimited number of values, making an infinite amount of test environment configurations.

It is now about making the right choice of configuration for your test environment. With simple mathematics it is possible to calculate an optimal set that covers a predefined percentage of all possible values. Now we want to combine it with customer data to reduce the set of needed test environments. In the situation of a car manufacturer this can pose a problem. The car manufacturer does not want to share detailed information on factory layout, specific PLC usage or detailed information on the welding setup in the production line.

As manufacturer for robotic arms, I want to test a new version control software for the robotic arm for all my customer environments (welding in a car production line is only one situation!). With some partial or anonymized data from production environments of the robotic arms now the challenge lies in building enough test environments to cover as much client situations as possible. The simplest way of doing is, is to define one random set of parameters filling in values in all the degrees of freedom. Compare this to the data that we do know of our client environments and the first coverage percentage can be calculated. To know the top 10 highest coverage set of values requires the creation and comparison of all combinations. If there are 100 parameters to fill in and we know about 75% of the values to fill in, this still gives us 3.7e48 combinations to calculate through. Even with a nanosecond per calculation and doing a billion calculations in parallel, this would take a billions of billions of years (yes 1e28 of years!). With brute force calculation we cannot even begin to process this mathematical problem. For this situation we can talk about infinite amount of test environment possibilities.

With limited amount of time and the option of maybe building up to 5 test environments we must come up with a different strategy. Artificial Intelligence gives us a huge toolkit to play with. In this situation a genetic algorithm can help us out. In the following I will describe how this mechanism can help you reduce the calculation time from billions of billions of years to mere minutes. Reducing configuration with ‘smart force’ calculation instead of ‘brute force’ takes testing beyond infinity.

Theory behind Configuration Reduction

Configuration reduction makes it possible to select the best test configurations out of a very large number of possible configurations. When the configuration settings of a device make it possible to create a large number of different configurations, it is difficult to select the appropriate test configurations on which the software must be tested. Often the test organization will use the default configuration, which by definition is not the configuration used by the customer. Configuration Reduction makes it possible to determine the optimum number of configurations with the preferred coverage of the customer for the configuration items.

In general, a device configuration has a number of attributes (configuration items), and each attribute can have a number of values.

When a lot of attributes are specified in a device configuration, the theoretical number of different device configurations will be huge.

Each configuration can respond or act different in several ways from another device configuration. It’s important to take this into account, and to select the correct device configurations when testing.

The possible values of the attributes originate from the hardware options on the device, and mostly a software package will control the device configurations.

The number of different configurations can be huge. This is a challenge for the test organisation: what should the test configuration look like? It is not realistic to test every theoretical possible configuration. In many cases the test organization will take the default configuration, which is, by definition, not the configuration used by the customer.

The necessity exists to be able to select a minimum of device configuration with a maximum of coverage.

The Configuration Reduction process consists of the three steps:

1. Configuration analysis.

2. Search for the optimal configuration set

3. Report results

Configuration analysis

The configuration analysis is usually done once. The goal is to get information about the existing configurations.

This information is used to determine a subset of configurations from which the tool will select the optimal set of configurations.

The analysis is also used to determine how to map the existing configurations to suitable input for the tool.

The properties of the existing configurations can also help to determine how many configurations must be in the optimal solution and which coverage definition to use.

Choose which configurations to use

By leaving out non-representative configurations we can help the search algorithm to perform better. This is a manual step which can be supported by a statistical analysis (for example with clustering techniques).

Use cluster analysis algorithms to find clusters of similar configurations. There are several methods for find clusters. If a configuration contains X configuration items it means we have an X-dimensional dataset. We can map this high-dimensional dataset to just two dimensions using dimension reduction techniques (using singular value decomposition). The resulting transformed data can then easily be plotted. If clusters are visible this means that configurations in each cluster are similar, but also that there are larger differences between these clusters. If there are K clusters it means that the solution set will at least contain K configurations.

Filtering

Filters are used to remove configuration items that are not useful for the search algorithm.

Choose mapping

There are different types of configurations items, such as Boolean, continuous and discrete. The input for the search algorithm probably requires these configuration items in a specified format. A mapping will take care of transforming a configuration to something that can be used by the search algorithm.

It is preferred to make the matrix with the configurations and configuration items binary. This makes it easier to analyse the data. With a binary matrix, it is for example possible to count the number of times a specific configuration item is used. It also gets less important to know exactly what each configuration item functionally means.

All processing on the input data must be done on copies, the original data must be preserved. The result of the search algorithm is a set of configuration identifiers, pointing to the original configurations.

Search for the optimal configuration set

Define a scoring function to score a configuration set

The search algorithm chooses a set of configurations and updates this set iterative. After every iteration, it will calculate a score for each solution, and then select an update with a higher score.

The scoring function basically determines the coverage percentage of a set of configurations. There are however different types of coverage (e.g. simple, pair-wise, orthogonal), so to calculate a score the type of coverage should also be specified.

If we don’t want to specify the desired resulting number of configurations, we can let the search algorithm decide this by adding a penalty in the scoring function for each configuration it adds to the resulting set of configurations.

Choose the search algorithm

There are several ways to solve an optimization problem, such as genetic algorithm.

The search algorithm will search a set of configurations that is optimal. Characteristics of an optimal solution are:

· the solution has a high Coverage percentage

· the solution contains the optimum number of configurations

In most cases we will specify the required number of configurations in a solution in advance. An example of a scoring function could then be:

Score(set) = Coverage(set)

The scoring function will contain a term that is dependent on coverage percentage. Coverage is further defined by the coverage type:

· Simple coverage
The purpose of the coverage is to cover as many configuration items as possible with as little configurations as possible. To determine the total coverage, all configuration items (keys + values) of all selected configurations (devices) should be taken in account.
As mentioned before, the aim is to get a as high as possible coverage with as few as possible configurations. However, it is not always required to get 100% coverage, as at the end an additional device is needed for every percent extra coverage.

Coverage(set) = (number of enabled configuration items) / (number of configuration items)

• Pairwise coverage
  In some cases tests will perform better if different combinations of configuration items are selected in the solution set. We are however constrained by choosing only existing configurations. Thus, in practice we will approximate pairwise coverage. Pairwise coverage can be further generalized in an orthogonal array.

Coverage(set) = (number of found pairs in the set) / (total number of pairs)

In order to work around the fact that the calculation time for finding the best configuration exceeds the lifespan of people, a ‘Smart Force’ (as opposed to ‘Brute Force’) algorithm is chosen: The genetic algorithm.

A genetic algorithm can be designed to search for the optimal solution set as follows:

i. Create X random configuration sets. Each set consist of K configurations randomly chosen from the set of existing configurations

ii. Score each configuration set and sort according to score.

iii. Keep the X/3 best sets.

iv. Make a copy of the X/3 best sets. Then add crossovers and mutations

v. The remaining X/3 sets are again randomly initialized.

vi. Go back to step 2, repeat J times

vii. report the best scoring solution sets.

The challenge is to design good crossover and mutation operations. For example: we cannot just flip a configuration item as mutation operation, as we can only select valid configurations chosen from the existing configurations.

Prepare the input data

The input for the algorithm is data. Data sets are not always completely usable. In terms of completeness per set of parameters there may be omissions. Some data may be scrambled due to privacy regulations or data is just filled in wrong or even corrupted. A ‘filthy’ data set needs to be prepared before usage. The data needs to be filtered for usable data. Missing fields can be filled in with default values (static values or neutral values). Maybe some mappings of specific data fields are needed to make the data set work.

In the case of creating configurations, we also need to apply mappings and filters on existing configurations and such a way create the input for the search algorithm.

Execute the algorithm

Run the algorithm to find the optimal solution. In some cases, there will be algorithm parameters to configure. e.g. the number of iterations.

Report results

This basic last step can be split up in two elements:

• Report the optimal solution.

• Report confidence in this solution, if possible.

The first bullet is an obvious one. The set that comes out of this mechanism is for the chosen situation the most optimal one. This does not mean it is the best one. There are multiple parameters that influence the end-result. A brute force calculation would come up with the best result, but that is not what we are working with here. We need to know how good this optimal solution is. If we turn the knobs and choose different parameters for our configuration reduction calculation a different solution presents itself. Might be just as good, but we do not know it and that is where the confidence reporting comes in. Next to the result we want figures explaining the chosen parameters and where possible a number explaining the confidence in this most optimal solution. Typically, this is something like a percentage of the chosen set of configuration parameters opposed to all the existing configurations in the field. A percentage telling you how much coverage is achieved for example.

How this can be applied is for the second part of this blog series. In part 2 I will explain in a client case how we applied this mechanism and what the savings are when going for configuration reduction.