Is Branch Coverage a Good Measure of Testing Effectiveness? - Empirical Software Engineering and Verification - page 198

1.1

ACTIVE_LIST
ARRAY
ARRAYED_LIST
ARRAYED_SET
ARRAYED_STACK
BINARY_SEARCH_TREE
BINARY_SEARCH_TREE_SET
BINARY_TREE
FIXED_LIST
HASH_TABLE
HEAP_PRIORITY_QUEUE
LINKED_CIRCULAR
LINKED_LIST
PART_SORTED_TWO_WAY_LIST
Median of medians

1

0.9

0.8

0.7

0.6

0.5

0 30 60 90 120 150 180 210 240 270 300 330 360

Time (minutes)

Fig. 1. Medians of the branch coverage level for each class over time and their median

In short, the branch coverage level achieved by random testing depends on the struc-
ture of the class under test and increases very fast in the first 10 minutes of testing and

then very slowly afterwards.

3.2 Similarity of Coverage

Another important question is whether different test runs for the same class exercise
different branches. Since we are more interested in branches difficult to exercise, the
more specific question is: Do different test runs for the same class leave the same set
of branches not visited? To answer this question, we need to measure the difference
between the sets of branches not visited in two test runs for the same class. We use an
array per testing run, containing a flag for each branch indicating whether it was visited.
To measure the difference between two sets of non-visited branches, it is appropriate
to use the Hamming distance [12]: the number of positions, in two strings of equal
lengths, where symbols differ. For example, the Hamming distance between 1011101

and since the values differ at two positions, 3 and 5.

For the purposes of this study, a branch is said to be “difficult to exercise” if and only
if it has not been exercised at least once through the

1001001 is 2

runs for that class.
The difficult branch coverage vector of a test run for a class with

30

n difficult branches

is a vector of elements, where the i-th element is a flag for the i-th difficult branch in

that class, with one of the following value: 0, indicating that the corresponding branch
has not been exercised in that test run, or 1, indicating that the corresponding branch
has been exercised in that test run.
The difficult branch coverage distance

n

D BC between two vectors u and v of the a

class with N b difficult branches is the Hamming distance between them: