Efficient Uniform Sampling of Traces in Presence of Infeasibilities

Coverage biased random testing of software consists of drawing uniformly at random a large sample of paths from the control graph of a program, or from traces of its specification or model. In order to obtain input values that exercise them, the conditions for following each path/trace are incrementally collected into a formula, which characterises the values that lead to traverse it at run time. A solver is then used for obtaining a test set that ensures the coverage of the sample. A well-known problem is that not all paths/traces correspond to feasible runs. Such infeasible paths/traces must be rejected and others must be drawn to ensure a sufficiently large number of test inputs. This severely limits the interest of the method when there is a high ratio of infeasible paths or traces, as it is often the case. The new technique we propose uses knowledge about the shortest infeasible prefixes of infeasible paths that have been drawn to prevent future drawing of extensions of such prefixes. Starting with uniform drawing from all the paths/traces, the new algorithm incrementally shrinks the drawing domain and remains uniform among the paths/traces that do not have a known infeasible prefix. As the number of infeasible paths/traces is often large, their elimination from the subsequent drawings is a drastic improvement with respect to the simple path rejection method above.