A theory of predicate-complete test coverage and generation

Consider a program with m statements and n predicates, where the predicates are derived from the conditional statements and assertions in a program. An observable state is an evaluation of the n predicates under some state at a program statement. The goal of predicate-complete testing (PCT) is to evaluate all the predicates at every program state. That is, we wish to cover every reachable observable state (at most m × 2ⁿ of them) in a program. PCT coverage subsumes many existing control-flow coverage criteria and is incomparable to path coverage. To support the generation of tests to achieve high PCT coverage, we show how to define an upper bound U and lower bound L to the (unknown) set of reachable observable states R. These bounds are constructed automatically using Boolean (predicate) abstraction over modal transition systems and can be used to guide test generation via symbolic execution. We define a static coverage metric as |L|/|U|, which measures the ability of the Boolean abstraction to achieve high PCT coverage.