Weak Mutation Testing For Message Passing Parallel Programs

Mutation testing is one of the most effective testing approaches, but huge cost in mutation testing limits its feasibility and applications. Message passing parallel programs are most widely used programs among parallel programs. To ensure the reliability of a message passing parallel program, it is necessary to implement mutation testing to it. A message passing parallel program has many kinds of statements and communication functions; in addition, its execution is uncertain and may suffer from deadlocks, which make it very difficult to test a message passing parallel program. Therefore proposing theories and approaches to reduce the cost of mutation testing for a message passing parallel program is of necessity. There are 3 aspects for a message passing parallel program in this thesis, i.e., transformation of weak mutation testing, mutant reduction, and test data generation.First, a method of weak mutation testing transformation for a message passing parallel program is proposed, to transform the problem of killing mutants into that of covering branches. The mutation condition statement is constructed according to statements in the message passing parallel program, and put into the original program to form a new program on the premise of avoiding deadlocks. The above method transforms the problem of killing mutants into that of covering branches, and lays a foundation for structure testing methods to solve mutation testing.In addition, a mutant reduction method based on dominance degree is presented to reduce the number of mutants. The concept of dominance degree for branches is defined, and the approach of calculating the dominance degree between branches and the dominated degree of a branch is provided. Then, on the basis of the dominance and the dominated degrees, an approach to judging the redundant true branches of mutation condition statements is proposed, and their corresponding mutants are deleted to obtain mutants after reduction. This method can not only guarantee the effectiveness of mutation testing, but also improve its efficiency.Finally, for the problem of test data generation of mutation testing, a method of generating test data for a message passing parallel program is given based on genetic algorithms, to improve the efficiency of mutation testing. For the new program after weak mutation testing transformation, the mathematical model of test data generation for branch coverage is built. Then, the mathematical model is solved by a genetic algorithm, to generate test data of mutation testing for the message passing parallel program. This method is helpful for improving the efficiency of test data generation for mutation testing.The proposed approaches in this thesis can improve the efficiency of mutation testing for message passing parallel programs, and expand the application range of mutation testing, thus having important theoretical and practical values.