Test Adequacy and
Coverage
1
10.1
Systematic Testing
Functional testing:
• Test cases come from requirements/specs
Structural testing:
• Test cases check the source code
Model-based testing:
• Test cases from models of the system and
its behavior
2
Testing Thoroughly
“Each software system should be thoroughly tested”.
• What does thorough mean?
• How can we meaure test adequacy?
• When can we stop testing?
3
Adequacy Criteria as Design Rules
• Many design disciplines employ design rules
– “Interstate highways must have a grade less than
6%.”
• Design rules do not guarantee good designs
– Good design depends on talented, creative,
disciplined designers; design rules help them
avoid or spot flaws
• Test design is no different
4
9.2
Terminology
• Test case: a set of inputs, execution conditions, and a pass/fail criterion.
• Test case specification: a requirement to be satisfied by one or more test
cases.
• Test obligation: a partial test case specification requiring some property
deemed important to thorough testing
• Test suite: a set of test cases.
• Test or test execution: the activity of executing test cases and evaluating
their results.
• Adequacy criterion: a predicate that is true (satisfied) or false (not
satisfied) of a áprogram, test suiteñ pair.
• Test coverage: percentage of test obligations met for a given adequacy
criterion.
5
Where do test obligations come from?
• Functional (black box, specification-based): from software specifications
– Example: If spec requires robust recovery from power failure, test
obligations should include simulated power failure
• Structural (white or glass box): from code
– Example: Traverse each program loop one or more times.
• Model-based: from model of system
– Models used in specification or design, or derived from code
– Example: Exercise all transitions in the UI model
• Fault-based: from hypothesized faults (common bugs)
– Example: Check for buffer overflow handling (common vulnerability) by
testing on very large inputs
6
Adequacy criteria
A test suite satisfies an adequacy criterion if
– all the tests succeed (pass) AND
– every test obligation in the criterion is satisfied by at
least one of the test cases in the test suite.
Example:
The full statement coverage adequacy criterion is
satisfied by test suite S for program P if and only if
– the outcome of each test case execution is “pass” and
– each executable statement in P is executed by at least
one test case in S
7
Practical (in)Adequacy Criteria
• Criteria that identify inadequacies in test suites. Examples
– If no test in the test suite executes a particular program
statement, the test suite is inadequate to guard against faults
in that particular statement.
• If a test suite fails to satisfy some criterion, the obligation
that has not been satisfied may provide some useful
information about improving the test suite.
• If a test suite satisfies all the obligations by all the
criteria, we do not know definitively that it is an effective
test suite, but we have some evidence of its
thoroughness.
8
Code Coverage
Introduced by Miller and Maloney in 1963
9
Coverage Criteria
Basic Coverage
• Function/Method coverage
• Line coverage
• Statement
• Branch coverage
• Decision coverage
• Condition coverage
• Condition/decision coverage
• Modified condition/decision coverage
• Path coverage
• Loop coverage
• Mutation adequacy
Advanced Coverage
• State/Transition coverage
10
Line Coverage
• Percentage of source code lines executed by test
cases.
– For developer easiest to work with
– Precise percentage depends on layout?
• var x = 10; if (z++ < x) y = x+z;
• In practice, coverage not based on lines, but on
control flow graph
11
5.3
The Control Flow Graph
12
5.3
The Control Flow Graph
• Node:
• Regions of source code (basic blocks)
• Basic block = maximal program region with
single entry and single exit point
• Directed edges:
• possibility that program execution proceeds from the end
of one region directly to the beginning of another
• Intra-procedural:
• within one procedure / method
• Extra nodes: single entry, single exit for full procedure
13
5.3
Deriving a Control Flow Graph
public static String collapseNewlines(String argStr)
public static String collapseNewlines(String argStr)
{ { b2
char last = [Link](0);
char last = [Link](0); StringBuffer argBuf = new StringBuffer();
StringBuffer argBuf = new StringBuffer(); for (int cIdx = 0 ;
for (int cIdx = 0 ; cIdx < [Link](); cIdx++) cIdx < [Link](); b3
{ False True
char ch = [Link](cIdx); b4
{
if (ch != '\n' || last != '\n') char ch = [Link](cIdx);
if (ch != '\n'
{
[Link](ch); False True
last = ch; || last != '\n') b5
} True
} { b6
[Link](ch);
last = ch;
}
return [Link]();
False
}
} b7
cIdx++)
Splitting multiple
b8
conditions depends return [Link]();
}
14
on goal of analysis
CFG Abstraction Level?
• Loop conditions? (yes)
• Individual statements? (no)
• Exception handling? (no)
• What’s best depends on type of analysis to be
conducted
Statement coverage
• Adequacy criterion: each statement (or node in the CFG) must be
executed at least once
void foo (z) {
var x = 10;
if (z++ < x) {
x=+ z;
}
}
• Coverage:
# executed statements
# statements
Statement coverage
• Adequacy criterion: each statement (or node in the CFG) must be
executed at least once
void foo (z) {
var x = 10; @Test
if (z++ < x) { void testFoo() {
x=+ z; foo(10);
} }
}
• Coverage:
# executed statements
# statements
Statement coverage
• Adequacy criterion: each statement (or node in the CFG) must be
executed at least once
void foo (z) {
var x = 10; @Test
if (z++ < x) { void testFoo() {
x=+ z; foo(10);
} }
}
• Coverage:
# executed statements
# statements
Statement coverage
• Adequacy criterion: each statement (or node in the CFG) must be
executed at least once
void foo (z) {
var x = 10; @Test
if (z++ < x) { void testFoo() {
x=+ z; foo(5);
} }
}
// 100% statement coverage
• Coverage:
# executed statements
# statements
Control Flow Based 12.2
12.3
Adequacy Criteria
public static String collapseNewlines(String argStr)
{ b2
char last = [Link](0);
StringBuffer argBuf = new StringBuffer();
for (int cIdx = 0 ;
Statement cIdx < [Link](); b3
False True
coverage? {
char ch = [Link](cIdx);
if (ch != '\n'
b4
False True
|| last != '\n') b5
True
{ b6
[Link](ch);
last = ch;
One test case: b2,3,4,5,6,7,3,8 }
Input: “a” False
} b7
cIdx++)
return [Link](); b8
}
20
12.3
Branch Coverage
• Every edge going out of a node executed at least
once
– Decision-, all-edges-, coverage
– Coverage: percentage of edges hit.
• Each predicate must be both true and false
void foo (z) {
var x = 10; @Test
if (z++ < x) { void testFoo() {
foo(5);
x=+ z;
}
}
}
21
12.3
Branch Coverage
• Every path going out of node executed at least once
– All-edges-, coverage
– Coverage: percentage of edges hit.
• Each predicate must be both true and false
void foo (z) { @Test
void testFoo() {
var x = 10; foo(5);
if (z++ < x) { }
x=+ z; @Test
} void testFoo() {
} foo(10);
} 22
12.2
Branch Coverage 12.3
public static String collapseNewlines(String argStr)
{ b2
char last = [Link](0);
StringBuffer argBuf = new StringBuffer();
• One longer input: for (int cIdx = 0 ;
cIdx < [Link](); b3
– “a\n\n” False True
b4
{
char ch = [Link](cIdx);
if (ch != '\n'
• Alternatively:
False True
|| last != '\n') b5
True
– Block (“a”) and {
[Link](ch);
b6
last = ch;
– “\n” and False
}
– “\n\n”
b7
cIdx++)
return [Link](); b8
}
23
12.4
Condition Testing
• Compound predicates. Example:
if ((((a || b) && c) || d) && e) {
…
}
• Should we test the effect of individual conditions on the outcome?
1. Basic condition: each condition (a, b, c, d, e) -> true, false
2. Decision: branch and basic condition
3. Compound condition: each combination of conditions
– 2N (costly), N=5, 25 = 32 tests!
4. Modified Condition / Decision Coverage (MC/DC)
– N+1: 5+1 = 6 tests!
24
Example: Basic Condition Coverage
foo (A, B, C) {
if ( (A || B) && C ) {
/* statements*/
}
else {
/* statements*/
}
}
In order to ensure Basic Condition coverage criteria for this
example, A, B and C should be evaluated at least one time
"true" and one time "false" during tests:
T1: foo(true, true, true)
// A = true, B = true, C = true
T2: foo(false, false, false)
// A = false, B = false, C = false
25
Example: Decision Coverage
if ( (A || B) && C ) {
/* instructions */
}
else {
/* instructions */
}
In order to ensure Decision coverage criteria, we need
basic condition AND the whole condition ((A or B) and C)
evaluated at least one time to "true" and one time to
"false”:
A = true, B = true, C = true ---> "true"
A = false, B = false, C = false ---> "false"
26