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

4.3 Branches Not Exercised

We analyzed the classes that were not exercised in our ex-

periments. Among these branches, there are

179 branches in all 14

duplicated
branches because they appear in inherited routines. Table 2 shows the reasons why cer-
tain branches were not exercised and the percentage of branches not exercised that fall
into that each reason. In Table 2 the categories are as follows:

116 distinct branches, and 63

Ta b l e 2 . Branches not exercised

Reason % of branches

Branch condition not satisfied 45.6%

Linear constraint not satisfied 12.9%

Call site not exercised 13.7%

Unsatisfiable branches 13.7%

Crash before branch 8.6%

Implementation limitation 2.5%

Concurrent context needed 1.7%

Branch condition not satisfied: branch not exercised because its branch condition is
not met. This is the most common case.

Linear constraint not satisfied: in the branch condition there is a linear constraint,
and they were not satisfied by the random strategy. This is actually a special case of
branch condition, but important on its own because a random strategy usually has great
difficulty satisfying these constraints.

Call site not exercised: no calls of a routine containing the branch were executed.

Unsatisfiable branch: the branch depends on conditions that can never be satisfied.
Fault before branch: there was always a fault found before exercised.

Implementation limitation: branch not exercised because of a limitation of AutoTest.

Concurrent context needed: the branch is only exercisable when tested in a concurrent
context. But our experiments were conducted in a sequential setting.
Table 2 shows that

58 . 5%

of the branches not exercised fall into the first two reasons
( Branch condition not satisfied, linear constraint not satisfied ).
A follow-up question would be how to satisfy these branch conditions. A common
solution to satisfy branch conditions is to use symbolic execution to collect path condi-
tions and propagate them up to the routine entry. Symbolic executors however induce a
large overhead in the general case.
We analyzed branches falling into the first two categories to see how often a symbolic
executor would help: in 32 . 3% of cases, we need a symbolic executor to propagate path

conditions, for the remaining , it is only needed to concatenate all dominating

path conditions and select inputs at the routine entry - a linear constraint solver is
needed when there is linear constraint in the concatenated path condition. Even if in
some cases it is not possible to solve the constraints, it seems useful to investigate
further this lead.

67 . 7%