Distinguish Dynamic Basic Blocks by Structural Statistical Testing

Statistical testing aims at generating random test data that respect selected probabilistic properties. A distribution probability is associated with the program input space in order to achieve statistical test purpose: to test the most
frequent usage of software or to maximize the probability of satisfying a structural coverage criterion for instance.

In this paper, we propose a new statistical testing method that generates sequences of random test data that respect
the following probabilistic properties: 1) each sequence guarantees the uniform selection of feasible paths only and
2) the uniform selection of test data over the subdomain associated with these paths. Baudry et al. present a testing for-diagnosis method where the essential notion of Dynamic Basic Block was identified to be strongly correlated to the effectiveness of fault-localization technique. We show that generating a sequence of random test data respecting these properties allows to well-distinguished Dynamic Basic Blocks. Thanks to Constraint programming techniques, we propose an efficient algorithm that uniformly selects feasible paths only by drastically decreasing the number of rejects (test data that activate another control flow path) during the test data selection. We implemented this algorithm in a statistical test data generator for Java programs. A first experimental validation is presented