LAUSR

This paper investigates the problem of prime and test paths generation, which is an important problem in ensuring path coverage in software testing. Most existing methods for prime/test paths generation have little success in generating the set of all prime/test paths of structurally complex programs with high Npath complexity. This paper puts forward two novel methods for the generation of prime and test paths of highly complex programs, namely a vertex-based algorithm and a compositional method. The proposed vertex-based method enables a time-efficient approach for the generation of all prime paths, and the compositional method provides a highly time and space-efficient method for the generation of prime and test paths in cyclic control flow graphs with extremely large Npath complexity. We also implement the proposed algorithms as a software toolset for the generation of prime and test paths. Our experimental results on a set of complex programs indicate that the proposed approaches significantly outperform existing methods, especially for large and structurally complex programs.