complexity of test space Options

[Birgit Geppert]

Hi everybody:

Thanks again to all of you who participated (in the one way or the other) in the SPLiT workshop. Charlie and I just went over the results again (which btw are now posted at http://www.biglever.com/split2004/presentations.html) and we thought that some of the statements are worth further discussions.

So, let me start with a first proposal: managing the complexity of the test space and constraining its combinatorics. Two rather interesting statements were:

• Constrain combinatorics of test space by being reactive and conservative on the scope of variability in the core assets and decision model
• Apply techniques (decision model, pair-wise, etc.) to reduce combinations needed for effective integration testing

These are two approaches that complement each other quite well: first try to keep the combinatorics to a minimum and then look for techniques to deal with the remaining complexity. Questions/Remarks that come to my mind are:

(1) Are there further techniques that might be helpful in managing the complexity?

(2) Can we use the design decision model as is for managing the test cases or do we need further parameters (or less?) for an appropriate test decision model?

(3) Who has experience with applying pair-wise testing for PLs?

Any thoughts? Looking forward to your feedback.

Birgit

[taoxie]

Hi everybody, this is Tao Xie from University of Washington at Seattle. I have been doing software testing for my dissertation research advised by David Notkin. I had spent my 2001 summer at Software Technology Research Department, Avaya Labs Research as a summer intern, working around process modeling/automation and product line engineering. So I am very interested in the product line testing problem.

I would like to briefly state some personal opinions on those issues (especially the complexity of the test space) brought up by Birgit (I haven't read the proceedings of SPLIT 04 yet so maybe these ideas might have been discussed somewhere already).

At first, apparently it is often impossible to explore the test input space exhaustively for a single product. The situation is even worse in a product line (a family of products).

I agree with the approaches summarized by Birgit: "These are two approaches that complement each other quite well: first try to keep the combinatorics to a minimum and then look for techniques to deal with the remaining complexity." I first discuss the first approach with my personal opinions.

One direction is to reduce the space conservatively (not sacrificing the test quality or only a bit test quality)

Assume we have a set of variation points VP = {vp1, vp2, vp3, ... vpn} and their size are s_vp1, s_vp2, ..., s_vpn. The combinatorics of all variation points are too much (s_vp1 * s_vp2*... * s_vpn). Pairwise testing has been proposed to reduce the combinatorics; however, generating only pairwise tests might reduce the test quality substantially because some bugs might be exposed by a higher-order combination.

If we look inside the system (or from system analysis), there might be no interactions between given two variation points. As an analogy in OO testing, if a method M1 in a class modifies only object field A without reading or modifying another object field B and another method M2 modifies only field B without reading or modifying field A. Assume we can directly construct object fields of A and B for testing M1 and M2 and the domain size of A and B are size_A and size_B.

When we test M1, we don't need the test space of size_A * size_B but size_A. Similarly when we test M2, we need only size_B.

I have done some work on detecting OO redundant tests without sacrificing test suite quality. The details are described in our ASE 04 paper:
http://www.cs.washington.edu/homes/taoxie/...tions/ase04.pdf

Some underlying notions can be borrowed to apply in conservatively reducing the product line test space.

I will later discuss the second approach which might involve some abstractions and test selection.

One way to push the research work in this community of product line testing is to prepare one or a set of product line testing benchmarks. In OO test generation, we use some complicated data structure classes (e.g. java.util.*), which are complex enough but accessible for research. People in this community can prepare and abstract some benchmarks out of their real systems (not necessarily having source code; requirement or design specifications might be sufficient if working on sytem test level). Then we have some toy but nontrivial concrete problems to try on. This would encourage and facilitate researchers to work on the product line testing problem.

My research project web lists my other papers in testing:
http://www.cs.washington.edu/homes/taoxie/research.htm

I collect a link of software testing researchers:
http://www.cs.washington.edu/homes/taoxie/...researchers.htm

I am in the process of adding product line testing researchers. You are welcome to send me a note if you are working on this field but are missed in the list.

More other useful SE-related links can be found at my main webpage (below my head pic):
http://www.cs.washington.edu/homes/taoxie/

[johnmc]

This is a brief posting to the PL QA forum and in answer to emails that I receive about pair-wise testing.

A technique that I found useful in industrial settings is orthogonal array testing (OATS). An orthogonal array is a mathematically derived table in which each column corresponds to individual variables that have a small range of discrete values. While an array may have many columns, the formulas used to produce the table ensure that specific pairs of columns cover every pair-wise combinations of the values of the two variables represented by the two columns. So, rather than an n column table containing n-way combinations, the n column table contains numerous pairs of pair-wise columns.

The tester builds a table that has a column for each of the variables that would be varied in a test situation. This table is mapped onto an orthogonal array. If this is done, then each row in an orthogonal array represents a test case. The entire test suite guarantees to cover all pair-wise combinations of the values of variables. How to do all of this is covered in my book ?A Practical Guide to Testing Object-Oriented Software.? Sorry to plug this but the full explanation is way beyond a forum posting. There is also a book that gives a theoretical background for OATS: M.S. Phadke. Quality Engineering Using Robust Design from Prentice Hall in 1989.

There is no question that using pair-wise testing as opposed to all-way testing will miss some defects but since we can?t exhaustively test the all-way these might be missed any way. Research that has been conducted on pair-wise testing seems to indicate that using pair-wise rather than all-way combinations is 96% as effective as the all-way testing. There obviously can be some variances from this if there are specific variables that are highly interactive but the loss of power does not seem to be nearly as great as the effort reduction.

Now, to put this into context, this is my last stop before selecting the test cases to be run. Before I apply the pair wise design I will have used risk-based techniques to prioritize test conditions and I will have looked for dependencies among variables to eliminate redundancies. So my point is that OATS is one tool in a portfolio of techniques that will lead to an efficient and effective test suite. Effective in that it will be more likely to find the defects that are most important. Efficient in that it will find those with the fewest test cases.


John McGregor

[kiberle]

Birgit proposes

• Constrain combinatorics of test space by being reactive and conservative on the scope of variability in the core assets and decision model
• Constrain combinatorics of test space by being reactive and conservative on the scope of variability in the core assets and decision model

Another approach is to make the combinatorics irrelevant by constraining the ability of the different variation points to interact. Very solid modularization, low coupling, and a very clear relationship between a variation point and the software that implements it.

From a test perspective, if this approach is used, the test staff has to be familiar with the design or else they won't know which variation points are (probably) independent and which ones aren't.

Taking an incremental approach to integration is helpful because it's more obvious which pieces interact or are dependent upon each other. Also, incremental integration improves your ability to find and fix the defects that don't depend on combinations before starting the combinatorial tests, which frees up effort that can be applied to running more combinatorial tests.

Kathy Iberle
Hewlett Packard

[johnmc]

Birgit proposes

* Constrain combinatorics of test space by being reactive and conservative on the scope of variability in the core assets and decision model


I certainly agree that being conservative on the scope of variability is a useful tactic. That is why in my posting I said that pair-wise testing is applied only after other measures have been applied. However, limiting the scope limits options which in turn limits the value of the product line approach. So this is a tradeoff that has to be carefully analyzed.

kiberle proposes:
From a test perspective, if this approach is used, the test staff has to be familiar with the design or else they won't know which variation points are (probably) independent and which ones aren't.

I agree that the tester should understand the design but I don't want to base my tests on knowing what the design says the software is supposed to be. It is the "probably" that scares me. I am testing to determine whether those things I think are true indeed are. If I assume and don't test for possible interactions I can miss potentially critical defects that are difficult to track down in the field. This is where security holes come from. All too often we only test that the software does what it is supposed to (black box) and not whether it does something it is not supposed to (white box).

[kiberle]

kiberle proposes:
From a test perspective, if this approach is used, the test staff has to be familiar with the design or else they won't know which variation points are (probably) independent and which ones aren't.

johnmc replies:
I agree that the tester should understand the design but I don't want to base my tests on knowing what the design says the software is supposed to be. It is the "probably" that scares me. I am testing to determine whether those things I think are true indeed are. If I assume and don't test for possible interactions I can miss potentially critical defects that are difficult to track down in the field. This is where security holes come from. All too often we only test that the software does what it is supposed to (black box) and not whether it does something it is not supposed to (white box).

kiberle replies:
If the "strong design" approach is used in development and test, then the process goes something like this:
-- design into decoupled modules, such that variation points are implemented in different modules
-- test at the module level - is the module really decoupled? (runs by itself without any other modules is one good clue). does the module meet its design specs for interfaces and responsibilities? can I force the module to fail (stress, interaction with environment, etc)? there should be a lot of testing at this point.
-- functional test of each variation point: at the module level if possible.
-- integrate modules
-- test integration points, data flows, end-to-end behavior
-- make different combinations of variation point values: randomly chosen combinations, and most common combinations, and the riskiest combinations
-- if these tests are failing, may have to revert to systematically testing all combinations of all functionality on the entire system

I'm not advocating blind trust in the software complying with the design, not at all. The module level testing is a thorough investigation of the compliance with written design *and* the effectiveness of the actual design.

Kathy Iberle

[Guest_shiva_*]

how to construct the orthogonal array?
what is the formula for it?
how to derive it ?

This is a brief posting to the PL QA forum and in answer to emails that I receive about pair-wise testing.

A technique that I found useful in industrial settings is orthogonal array testing (OATS). An orthogonal array is a mathematically derived table in which each column corresponds to individual variables that have a small range of discrete values. While an array may have many columns, the formulas used to produce the table ensure that specific pairs of columns cover every pair-wise combinations of the values of the two variables represented by the two columns. So, rather than an n column table containing n-way combinations, the n column table contains numerous pairs of pair-wise columns.

The tester builds a table that has a column for each of the variables that would be varied in a test situation. This table is mapped onto an orthogonal array. If this is done, then each row in an orthogonal array represents a test case. The entire test suite guarantees to cover all pair-wise combinations of the values of variables. How to do all of this is covered in my book ?A Practical Guide to Testing Object-Oriented Software.? Sorry to plug this but the full explanation is way beyond a forum posting. There is also a book that gives a theoretical background for OATS: M.S. Phadke. Quality Engineering Using Robust Design from Prentice Hall in 1989.

There is no question that using pair-wise testing as opposed to all-way testing will miss some defects but since we can?t exhaustively test the all-way these might be missed any way. Research that has been conducted on pair-wise testing seems to indicate that using pair-wise rather than all-way combinations is 96% as effective as the all-way testing. There obviously can be some variances from this if there are specific variables that are highly interactive but the loss of power does not seem to be nearly as great as the effort reduction.

Now, to put this into context, this is my last stop before selecting the test cases to be run. Before I apply the pair wise design I will have used risk-based techniques to prioritize test conditions and I will have looked for dependencies among variables to eliminate redundancies. So my point is that OATS is one tool in a portfolio of techniques that will lead to an efficient and effective test suite. Effective in that it will be more likely to find the defects that are most important. Efficient in that it will find those with the fewest test cases.


John McGregor