Path-oriented random testing through iterative partitioning (IP-PRT)

Abstract

Path-oriented random testing aims at generating a uniformly distributed sequence of test data from a programinput domain space to traverse a desired execution path of the program. To this aim, this article proposes a new algorithmto refine a program inputs domain space from invalid subdomains not covering the path. The validity of the subdomainsis checked by a constraint propagation method against the path constraints (PCs). The proposed algorithm uses a divideand-conquer technique to iteratively split the inputs domain into subdomains and each time refutes those subdomainsthat are inconsistent with the PCs. The remaining shrunken subdomains provide all possible test data covering thedesired path. Obviously, the more accurate the input domain is, the more effective test data will result. Experimentsshow the proposed method outperformed other related methods on a set of classical benchmark programs.