How many paths are needed for branch testing?

The number of test cases needed to achieve branch coverage is important to evaluate the effort needed to test a given program. However, the bounds proposed so far in the literature are not effective to measure testing effort. In this paper, we introduce a new, meaningful lower bound on the number of test cases needed to achieve branch coverage. We first identify the set of unconstrained arcs in a ddgraph. This is the minimum set of arcs such that a set of paths that exercises these arcs covers all the branches in the program. In general, a path may cover more than one unconstrained arc: the strategy we use to combine more unconstrained arcs into one path determines the cardinality of the set of test paths thus obtained, i.e., the bound we are looking for. It is now commonly accepted that the real problem in branch testing is to derive an executable set of test paths. Therefore, we will consider those control flow paths containing a low number of decisions as being meaningful, since they are more likely to be feasible. We formalize this notion by introducing the weak incomparability relation between ddgraph arcs. We then define the new, meaningful bound as the maximum number of unconstrained arcs in a ddgraph that are mutually weakly incomparable. Furthermore, we discuss interesting properties of this new bound. We analyze the bound with respect to Weyuker's axioms for complexity measures (Weyuker, 1988), and we show that the bound fits into the testability model of Bache and Mullerburg (Bache and Mullerburg, 1990).