Unconstrained duas and their use in achieving all-uses coverage

Testing takes a considerable amount. of t.he t.ime and resources spent on producing software. It would therefore be useful to have ways 1) to reduce the cost, of test.ing and 2) to estimate this cost. In particular, t.he nu niber of tests to be executed is an important and useful attribute of the entity "testing effort,". All-uses iesl. CO'/l(;7'!/.!Je is a widely used and probably the most, cost-effective of currently available data How testing str at.egies. In this paper we present, the set. of un co ust.m in.rd du as for t.Iw all-uses coverage criterion . It is a minimum set of du as (defiu itiou-use asso ci ar.io us ) su ch I.llal. if sd. of tl'.St paths covering them covers every du a in the prograru , This result is useful for reducing the cost of testing, since the generat.ion of test paths can be targeted to cover t.he smaller subset of unconstrained duas, rather t.han all those in a program. On the other hand, assuming that a different path is taken to cover each unconstrained du a, t.he number of unconstrained duas can be used to estimate the cost. of tesf.iug , Ol.lier interesting uses of unconstrained du as are also discussed.