Observability-based coverage-directed path search using PBO for automatic test vector generation

In this paper, we address the problem of finding a minimal set of execution paths that achieve a user-specified level of observability coverage. Under this metric, a program statement is only considered covered if its execution has influence on some output. We use Pseudo-Boolean Optimization (PBO) to model the problem of finding the paths that are most likely to increase code coverage. Generated paths are then validated to check for feasibility. This methodology was implemented into a fully functional tool that is capable of handling real programs specified in the C language.