Combinatorial testing
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 1
Learning objectives
• Understand rationale and basic approach for systematic combinatorial testing
• Learn how to apply some representative combinatorial approaches
– Category-partition testing
– Pairwise combination testing
• Understand key differences and similarities among the approaches
– and application domains for which they are suited
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 2
Combinatorial testing: Basic idea
• Identify distinct attributes that can be varied
– In the data, environment, or configuration
– Example: browser could be IE or Firefox, operating system could be Vista, XP, or OSX
• Systematically generate combinations to be tested
– Example: IE on Vista, IE on XP, Firefox on Vista, Firefox on OSX, …
• Rationale: Test cases should be varied and include possible corner cases
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 3
Key ideas in combinatorial approaches
• Category-partition testing
– separate (manual) identification of values that characterize the input space from (automatic) generation of combinations
for test cases
• Pairwise testing
– systematically test interactions among attributes of the program input space with a relatively small number of test cases
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 4
Category partition (manual steps)
1. Decompose the specification into independently
testable features
– for each feature identify • parameters
• environment elements
– for each parameter and environment element identify elementary characteristics (categories)
2. Identify relevant values
– for each characteristic (category) identify (classes of) values
• normal values
• boundary values
• special values
• error values
3. Introduce constraints
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 5
An informal specification: check configuration
Check Configuration
• Check the validity of a computer configuration
• The parameters of check-configuration are: – Model
– Set of components
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 6
An informal specification: parameter model
Model
• A model identifies a specific product and determines a set of constraints on available components. Models are characterized by logical slots for components, which may or may not be implemented by physical slots on a bus. Slots may be required or optional. Required slots must be assigned with a suitable component to obtain a legal configuration, while optional slots may be left empty or filled depending on the customers’ needs
Example:
The required slots of the Chipmunk C20 laptop computer include a screen, a processor, a hard disk, memory, and an operating system. (Of these, only the hard disk and memory are implemented using actual hardware slots on a bus.) The optional slots include external storage devices such as a CD/DVD writer.
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 7
An informal specification of parameter set of components
Set of Components
• A set of (slot, component) pairs, corresponding to the required and optional slots of the model. A component is a choice that can be varied within a model, and which is not designed to be replaced by the end user. Available components and a default for each slot is determined by the model. The special value empty is allowed (and may be the default selection) for optional slots. In addition to being compatible or incompatible with a particular model and slot, individual components may be compatible or incompatible with each other.
Example:
The default configuration of the Chipmunk C20 includes 20 gigabytes of hard disk; 30 and 40 gigabyte disks are also available. (Since the hard disk is a required slot, empty is not an allowed choice.) The default operating system is RodentOS 3.2, personal edition, but RodentOS 3.2 mobile server edition may also be selected. The mobile server edition requires at least 30 gigabytes of hard disk.
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 8
Step1: Identify independently testable units and categories
• Choosing categories
– no hard-and-fast rules for choosing categories – not a trivial task!
• Categories reflect test designer’s judgment
– regarding which classes of values may be treated differently by an implementation
• Choosing categories well requires experience and knowledge
– of the application domain and product architecture. The test designer must look under the surface of the specification and identify hidden characteristics
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 9
Step 1: Identify independently testable units
Parameter Model
– Model number
– Number of required slots for selected model (#SMRS)
– Number of optional slots for selected model (#SMOS)
Parameter Components
– Correspondence of selection with model slots
– Number of required components with selection 1 empty
– Required component selection
– Number of optional components with selection 1 empty
– Optional component selection
Environment element: Product database
– Number of models in database (#DBM)
– Number of components in database (#DBC)
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 10
Step 2: Identify relevant values
• Identify (list) representative classes of values for each of the categories
– Ignore interactions among values for different categories (considered in the next step)
• Representative values may be identified by applying
– Boundary value testing
• select extreme values within a class
• select values outside but as close as possible to the class • select interior (non-extreme) values of the class
– Erroneous condition testing
• select values outside the normal domain of the program
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 11
Step 2: Identify relevant values: Model
Model number
Malformed
Not in database Valid
Number of required slots for selected model (#SMRS)
0
1 Many
Number of optional slots for selected model (#SMOS)
0
1 Many
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 12
Step 2: Identify relevant values: Component
Correspondence of selection with model slots
Omitted slots
Extra slots
Mismatched slots Complete correspondence
Number of required components with non empty selection
0
< number required slots = number required slots
Required component selection
Some defaults
All valid
3 1 incompatible with slots
3 1 incompatible with another selection 3 1 incompatible with model
3 1 not in database
Number of optional components with non empty selection
0
< #SMOS = #SMOS
Optional component selection
Some defaults
All valid
3 1 incompatible with slots
3 1 incompatible with another selection
3 1 incompatible with model 3 1 not in database
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 13
Step 2: Identify relevant values: Database
Number of models in database (#DBM)
0
1 Many
Number of components in database (#DBC)
0
1 Many
Note 0 and 1 are unusual (special) values. They might cause unanticipated behavior alone or in combination with particular values of other parameters.
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 14
Step 3: Introduce constraints
• A combination of values for each category corresponds to a test case specification
– in the example we have 314.928 test cases
– most of which are impossible! • example
zero slots and at least one incompatible slot
• Introduce constraints to
– rule out impossible combinations
– reduce the size of the test suite if too large
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 15
Step 3: error constraint
[error] indicates a value class that – corresponds to a erroneous values – need be tried only once
Example
Model number: Malformed and Not in database
error value classes
– No need to test all possible combinations of errors
– One test is enough (we assume that handling an error case bypasses other program logic)
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 16
Example - Step 3: error constraint
Model number
Malformed [error] Not in database [error] Valid
Correspondence of selection with model slots
Omitted slots
Extra slots
Mismatched slots Complete correspondence
[error] [error] [error]
Number of required comp. with non empty selection
0
< number of required slots
Required comp. selection
[error] [error]
Error constraints reduce test suite from 314.928 to 2.711 test cases
3 1 not in database
Number of models in database (#DBM)
[error] 0 [error]
Number of components in database (#DBC)
0 [error]
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 17
Step 3: property constraints constraint [property] [if-property] rule out invalid
combinations of values
[property] groups values of a single parameter to identify subsets of values with common properties
[if-property] bounds the choices of values for a category that can be combined with a particular value selected for a different category
Example combine
Number of required comp. with non empty selection = number required slots
[if RSMANY] only with
Number of required slots for selected model (#SMRS) = Many [Many]
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 18
Example - Step 3: property constraints Number of required slots for selected model (#SMRS)
1 [property RSNE]
Many [property RSNE] [property RSMANY]
Number of optional slots for selected model (#SMOS)
1 [property OSNE]
Many [property OSNE] [property OSMANY]
Number of required comp. with non empty selection
0
< number required slots = number required slots
[if RSNE] [error]
[if RSNE] [error] [if RSMANY]
Number of optional comp. with non empty selection
< number required slots = number required slots
[if OSNE]
[if OSMANY]
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 19
from 2.711 to 908 test cases
Step 3 (cont): single constraints
[single] indicates a value class that test designers choose to test only once to reduce the number of test cases
Example
value some default for required component selection and optional component selection may be tested only once despite not being an erroneous condition
note -
single and error have the same effect but differ in rationale. Keeping them distinct is important for documentation and regression testing
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 20
Example - Step 3: single constraints
Number of required slots for selected model (#SMRS)
0 [single]
1 [property RSNE] [single]
Number of optional slots for selected model (#SMOS)
0 [single]
1 [single] [property OSNE]
Required component selection
Some default [single]
Optional component selection
Some default [single]
Number of models in database (#DBM)
1 [single]
Number of components in database (#DBC)
1 [single]
from 908 to 69 test cases
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 21
– 1
– Many
[property OSNE] [single]
[property OSNE] [property OSMANY]
– All valid
– 3 1 incompatible with slots
– 3 1 incompatible with another selection
– 3 1 incompatible with model
– 3 1 not in database [error]
• # of optional components (selection 1 empty) –0
Check configuration – Summary
Parameter Model
• Model number
– Malformed [error]
– Not in database [error]
– Valid
• Number of required slots for selected model (#SMRS)
– 0 [single]
– 1 [property RSNE] [single]
– Many [property RSNE] [property RSMANY]
• Number of optional slots for selected model (#SMOS)
– 0 [single]
Parameter Component
• Correspondence of selection with model slots
Environment Product data base
• Number of models in database (#DBM)
– 0 [error]
– 1 [single]
– Many
• Number of components in database (#DBC)
– 0 [error]
– 1 [single]
– Many
– < #SMOS
– = #SMOS
• Optional component selection
– Some defaults
– All valid
– 3 1 incompatible with slots
[if OSNE]
[if OSMANY]
[single]
– Omitted slots
– Extra slots
– Mismatched slots
– Complete correspondence
[error] [error] [error]
• # of required components (selection 1 empty)
– 0
– < number required slots
– = number required slots
• Required component selection
– Some defaults
[if RSNE] [error] [if RSNE] [error] [if RSMANY]
[single]
– 3 1 incompatible with another selection
– 3 1 incompatible with model
– 3 1 not in database [error]
(c) 2007 Mauro Pezzè & Michal Young
Ch 11, slide 22
Next ...
• Categorypartitiontestinggaveus
– Systematic approach: Identify characteristics and values (the creative step), generate combinations (the mechanical step)
• But...
– Testsuitesizegrowsveryrapidlywithnumberof categories: in order to exhaustively test all combinations of k categories with n values, we need nk test cases
– Can we use a non-exhaustive approach? • Pairwise(andn-way)combinatorialtesting:
– Combine values systematically but not exhaustively
– Rationale: Most unplanned interactions are among just two or a few parameters or parameter characteristics
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 23
Pairwise combinatorial testing
• Category partition works well when intuitive constraints reduce the number of combinations to a small amount of test cases
– Without many constraints, the number of combinations may be unmanageable
• Pairwise combination (instead of exhaustive)
– Generate combinations that efficiently cover all
pairs (triples,...) of classes
– Rationale: most failures are triggered by single values or combinations of a few values. Covering pairs (triples,...) reduces the number of test cases, but reveals most faults
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 24
Example: Display Control
No constraints reduce the total number of combinations
432 (3x4x3x4x3) test cases if we consider all combinations
Display Mode
Language
Fonts
Color
Screen size
full-graphics
English
Minimal
Monochrome
Hand-held
text-only
French
Standard
Color-map
Laptop
limited- bandwidth
Spanish
Document- loaded
16-bit
Full-size
Portuguese
True-color
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 25
Pairwise combinations: 17 test cases
Language
English
English
English
English
French
French
French
French
Spanish
Spanish
Spanish
Spanish
Portuguese
Portuguese
Portuguese
Portuguese
Color
Monochrome
Color-map
16-bit
True-color
Monochrome
Color-map
16-bit
True-color
Monochrome
Color-map
16-bit
True-color
-
Color-map
16-bit
True-color
Display Mode
Full-graphics
Text-only
Limited-bandwidth
Text-only
Limited-bandwidth
Full-graphics
Text-only
-
-
Limited-bandwidth
Full-graphics
Text-only
-
-
Limited-bandwidth
Full-graphics
Fonts
Minimal
Standard
-
Document-loaded
Standard
Document-loaded
Minimal
-
Document-loaded
Minimal
Standard
-
Monochrome
Minimal
Document-loaded
Minimal
Standard
Screen Size
Hand-held
Full-size
Full-size
Laptop
Laptop
Full-size
-
Hand-held
Full-size
Hand-held
Laptop
Hand-held
Text-only
Laptop
Hand-held
Full-size
Portuguese True-color Limited-bandwidth Hand-held
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 26
Adding constraints
• Simple constraints
example: color monochrome not compatible with screen laptop and full size
can be handled by considering the case in separate tables
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 27
Example: Monochrome only with hand-held
Display Mode
Language
Fonts
Color
Screen size
full-graphics
English
Minimal
Monochrome
Hand-held
text-only
French
Standard
Color-map
limited- bandwidth
Spanish
Document- loaded
16-bit
Portuguese
True-color
Display Mode
Language
Fonts
Color
Screen size
full-graphics
English
Minimal
text-only
French
Standard
Color-map
Laptop
limited- bandwidth
Spanish
Document- loaded
16-bit
Full-size
Portuguese
True-color
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 28
What have we got?
• From category partition testing:
– Division into a (manual) step of identifying categories and values, with constraints, and an (automated) step of generating combinations
• From pairwise testing:
– Systematic generation of smaller test suites
• These ideas can be combined with each other and with other types of testing
– For example, with test targets: a target can be a particular combination of values
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 29
Summary
• Requirements specifications typically begin in the form of natural language statements
– but flexibility and expressiveness of natural language is an obstacle to automatic analysis
• Combinatorial approaches to functional testing consist of
– A manual step of structuring specifications into set of properties
– An automatizable step of producing combinations of choices
• Brute force synthesis of test cases is tedious and error prone
• Combinatorial approaches decompose brute force work into steps to attack the problem incrementally by separating analysis and synthesis activities that can be quantified and monitored, and partially supported by tools
(c) 2007 Mauro Pezzè & Michal Young Ch 11, slide 30
Home reading
• Chapter 11 of the book Software Testing and Analysis, by Mauro Pezze and Michal Young
– Combinatorial testing
(c) 2007 Mauro Pezzè & Michal Young Ch 1, slide 31