An empirical evaluation (and specification) of the all-du-paths testing criterion

The all-du-paths structural testing criterion is one of the most discriminating of the data-flow testing criteria. Unfortunately, in the worst case, the criterion requires an intractable number of test cases. In a case study of an industrial software system, it is found that the worst-case scenario is rare. Eighty percent of the subroutines require ten or fewer test cases. Only one subroutine out of 143 requires an intractable number of tests. However, the number of required test cases becomes tractable when using the all-uses criterion. The authors include a formal specification of both the all-du-paths criterion and the software tools used to estimate a minimal number of test cases necessary to meet the criterion