Coverage criteria, subsumption, combinatorial coverage criteria

Coverage

The number of inputs is effectively infinite and cannot be enumerated. This is what formal coverage criteria is for. Coverage criteria are used to decide which test inputs to use. The rationale is to divide up the input space to maximize the numver of faults found per test case.

Test Requirement (TR): a specific element of software artifact that a test case must satisfy/cover.

• Software artifact can be source code, user manual, API doc, design components (e.g., UML diagrams), GUI, input space, etc.
• A non-software exampale is: we are testing a bag of jelly beans. Say there are 6 flavors and 4 colors. We can have 6 test requirements, one for each flavor. Satisfy a test requirement by tasting each flavor.

Coverage Criterion: a rule or collection of rules to generate test requirements from a software artifact.

• Describes the test requirements in a complete and unambiguous way.
• The "flavor criterion" yields a strategy for selecting jelly beans. The set of test requirements for the "flavor criterion" can be written out as $TR=\{Lemon, Pistachio, Cantaloupe, Pear, Tangerine, Apricot\}$

Coverage: Given the set of $TR$s for a coverage criterion $C$, a test set $T$ satisfies $C$ (i.e., achieves coverage $C$) if and only if for any test requirement $tr$ in $TR$, there is a test case $t$ in $T$ that covers/satisfies $tr$.

Minimal Test Set: Given a set of test requirements TR and a test set T, T is minimal if removing any single test case from T will cause T to no longer satisfy all test requirements in TR.

Minimum Test Set: A test set T that satisfies all test requirements in TR is minimum if there exists no smaller test set that can also satisfy all test requirements in TR.

Coverage Level: Given test set T and test requirements set TR, assume that T covers/satisfies x number of test requirements in TR. The coverage level of T is: $\frac{x}{|TR|}$

Some test requirements may be infeasible, i.e., can never be satisfied.

• E.g., unreachable code, thus not possible to achieve statement or branch coverage. Therefore, it is an infeasible test requirement

if (x < 0) {
	// ...
} else if (x < -2) {
	// ...
}

Coverage Criteria

Some ways to leverage coverage criteria:

1. directly derive test cases to achieve coverage

• systematic
• not always easy/possible
• may not be possible to automate
• Generator, i.e., "test generation" tools

2. derive test cases and measure coverage levels

• less systematic
• easier to perform
• (more) common practice in the industry
• recognizer, i.e., "coverage analysis" tools

Given a coverage criterion C, how do you compare 90% coverage level to 100% coverage level ? Does this mean the former is 10% less effective in revealing faults?

How to compare different coverage criteria against each other? How to decide if one coverage criterion is stronger/weaker than another one?

• Subsumption: A test criterion C1 subsumes C2 if and only if every set of test cases that satisfies criterion C1 also satisfies C2
• Example: Branch Coverage (BC) subsumes Statement Coverage (SC)

Advantage/Disavantages

Advantages include:

• Maximize the "bang for the buck" (fewer tests that are more effective at finding faults)
• Comprehensive test set with minimal overlap
• "Traceability" from software artifacts to tests
• A "stopping rule"
• Lend themselves well to "automation".

Limitations are:

• might not be easy to generate all the test requirements
• might not be easy to generate test casese that satisfy the generated test requirements
• might be very costly
• most important: what is the correlation betweeen a coverage criterion satisfaction and its fault detectino ability.

Suppose that coverage criterion C1 subsumes coverage criterion C2. Further suppose that test set T1 satisfies C1 and on program P test set T2 satisfies C2, also on P.

• Does T1 necessarily satisfy C2? Yes, branch coverage subsumes statement coverage. C2 is the weaker one
• Does T2 necessarily satisfy C1?
• If P contains a fault, and T2 reveals the fault, T1 does not necessarily also reveal the fault.

Combinatorial Coverage Criteria

Recall equivalence partitioning (EP) technique when talking about Blackbox testing. We learned how to do EP on a domain.

• e.g., domain is integer values --> split into negative, zero, positive

This is great when you have only one parameter. Often in practice, we have severeal input/ouptut domains to work with.

• e.g., a function that has more than one input parameter.
• We need to work with combinations of equivalence blocks.

Look at:

/**  
* Count the number of occurrences of a target value in an ArrayList * @param ray the ArrayList instance  
* @param key the target value  
* @return count of occurrences  
*/

public static int countOf(ArrayList<Integer> ray, int key) { int count = 0;  
	for (int i = 0; i < ray.size(); ++i) {
		if (ray.get(i).equals(key))  {
			count++;
		}
	}
	return count;
}

countOf example has the following blocks:

1. ArrayList can be
   1. null
   2. empty
   3. size 1
   4. size > 1
2. key can be
   1. negative
   2. zero
   3. positive

All Combinations (ACoC): all combinations of blocks from all characteristics must be used.

• Test requirements for ACoC would include all possibilites of the blocks: (1.1, 2.1), (1.1, 2.2) ...

Each Choice Coverage (ECC): One value from each block for each characteristic must be used in at least one test case

• (1.1, 2.1), (1.2, 2.2), (1.3, 2.3, 1.4, 2.4).

Pair-Wise Coverage (PWC) : A value from each block for each characteristic must be combined with a value from every block for each of the other characteristics.

• Assume we have three partitions with the following blocks: [A, B], [1, 2, 3], and [x, y]
• Then the test requirements for PWC would be: (A, 1, x) (A, 2, x) (A, 3, x) (A, 1, y) (B, 1, y) (B, 2, y) (B, 3, y) (B, 1, x)

t-Wise Coverage (TWC) : A value from each block for each group of t characteristics must be combined.

Base Choice Coverage (BCC) : A base choice block is chosen for each characteristic, and a base test is formed by using the base choice for each characteristic. Subsequent tests are chosen by holding all but one base choice constant and using each non-base choice in each of the other characteristics.

• Assume we have three partitions with the following blocks: [A, B], [1, 2, 3], and [x, y]
• Test values for BCC coverage. Base test are (A, 1, x) (B, 1, x) (A, 2, x) (A, 3, x) (A, 1, y)
  • Go to the next one for the first choice (change A to B), then the next choice (change 1 to 2 to 3), then change the last one (x to y). - “base choice” essentially corresponds to the “default” choice for a block - Base choice should be feasible (i.e., executable)
• Base choices usually take the “happy path”
  • E.g., base choice block for “factor” is positive values

Multiple Base Choice Coverage (MBCC) : At least one, and possibly more, base choice blocks are chosen for each characteristic, and base tests are formed by using each base choice for each characteristic at least once. Subsequent tests are chosen by holding all but one base choice constant for each base test and using each non-base choice in each of the other characteristics.

This list went from strongest to weakest. ACoC subsumes all.