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

N b

D BC = u i ⊕ v i

i =1

where u i and v i are the values at the i -th position of u and v respectively, and ⊕ is

exclusive or. D BC is in the range between 0 and N b . The larger the distance, the more

different branches are covered by these two runs.
The difficult branch coverage similarity is defined as:

N b − D BC
N b
The intention of the similarity is that the smaller the branch coverage distance, the
higher the similarity and the similarity should range between

0 and 1 . The similarity

among vectors is calculated as the median of the similarity values between each

two vectors: there are

k> 2

k ( k − 1)
2

k

vectors, for each pair, a similarity value is
calculated, and the overall similarity is the median of those k ( k − 1)
2

pairs of

values.

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.95

0.9

0.85

0.8

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

Time (minutes)

Fig. 2. The branch coverage similarity for each class over time; their median

Figure 2 shows the difficult branch coverage similarity for each class over time. The
thick curve is the median of the difficult branch coverage similarity over all classes.
Figure 2 reveals that the similarity of difficult branch coverage is already only after

a few minutes of testing, Figure 3 shows the standard deviation of the branch cover-
age similarity for each class. It reveals that the standard deviation of difficult branch
coverage similarity is almost

1

.
The high median of similarity means that in general, the set of branches from a
class that are difficult to exercise are very similar from test run to test run (for the

0