Similarity-based Testing For Message Passing Parallel Programs

Message-passing parallel programs are currently the most widely used one of the parallel programs.This kind of programs have a simple way to develop,hold an excellent compatibility,and can be implemented conveniently.A message-passing parallel program contains multiple processes that are executed in parallel to accomplish a task,which makes problems can be solved efficiently.Compared with the serial programs,message-passing parallel programs are more complex.The communication among processes are accomplished by passing messages,which makes the implementation of this kind of programs uncertain and may be accompanied by data competition,resource conflicts,deadlock and other new problems.Therefore,the reliability of message-passing parallel programs requires a higher degree.It is particularly important to test this kind of programs.To test a program,the targets to test should be determined.They will be either one or more statements,branches,paths,or other code snippets.Some scholars have pointed out that many software testing problems can be translated into the problems of test data generation for path coverage.Therefore,it is important to generate test data that cover the above paths.Message passing parallel programs often contain multiple process scheduling sequences.This paper first studies the method of selecting process scheduling sequences under which test data that cover a target path can be efficiently generated,so as to improve the test efficiency.Furthermore,with the improvement of the program complexity,the paths that need to test increased sharply.If test data that cover them are generated one by one,the program need to run many times.If the selected scheduling sequence is same for multiple paths,the corresponding problem of test data generation can be transformed into multiple targets optimization problem,which can reduce the number of runs of the program,so as to improve the efficiency of test data generation.However,when the number of paths is too large,the transformed optimization problem will contains too many objective functions,which will greatly increase the difficulty of problem solving.In view of this,this paper proposes a suitable method to group paths.The method decomposes the complex multi-objective optimization problem into several simple optimization problems,so as to further improve the efficiency of test data generation.After grouping paths,this paper gives the detailed solving process about the problem of test data generation.This paper mainly includes the following three aspects:(1)A method of scheduling sequence selection for efficiently generating test data that cover a target path is proposed.The difficulties of generating test data that cover a path under different scheduling sequences are very different.Improper scheduling sequence will greatly limit the efficiency of test.The proposed method is intended to select an excellent and feasible scheduling sequence to efficiently generate the desired test data that cover the path.First,the program input set is generated based on the Latin hypercube sampling in the input space of the program.Then,the program is executed with each sampling value under each scheduling sequence to obtain the similarities between the coverage paths and the target path,and based on this,the scheduling sequences are sorted;Finally,the static analysis is used to find an excellent and feasible scheduling sequence.The proposed method fully considers the influence of the scheduling sequences on the execution of the message-passing parallel programs,and provides an effective way for testing such programs.(2)Under a scheduling sequence,when the number of paths to be covered is very large,the efficiency of test data generation will be improved through group reasonably the above paths.Considering that if the paths are grouped by the existing method,the similarity among paths in a group is likely to be low,so as to limit the generation of the desired test data.To overcome the above shortcomings,the author proposes a new method to group paths.The method regards the existing target paths in the group as the reference paths and group the remaining ones based on the similarities with these reference paths.It can improve the similarities among paths grouped into the same group,so as to improve the corresponding efficiency of test data generation.In addition,based on the program inputs directly related to the processes,the weights of the process sub-path similarities are set.The similarity between paths will be calculated based on the similarities of these sub-paths and the above weights.(3)Based on the researches of the above two parts,the concrete realization process of test data generation is given.The core of the implementation process is genetic algorithm.As a natural probability search method based on population,which is inspired by natural evolution,genetic algorithm has the advantages of self-learning and self-adaptability.Firstly,the problem of test data generation is transformed into the optimization problem,and then genetic algorithm is used to solve the above optimization problem to generate the desired test data.The proposed methods not only improve the efficiency of test data generation based on path coverage for message-passing parallel programs,but also extend the application range of genetic algorithm,which has a very important theoretical and practical value.