| Due to the development of parallel computing techniques, more and morescientific problems, such as image processing, weather forecast, and moleculardynamic simulation, can be solved by parallel programs. Multiple processes in aparallel program are executed in parallel and cooperate with each other bycommunication or shared memory to solve practical problems. Compared to serialprograms, parallel programs are more complicated and require higher reliability,suggesting that the testing of parallel programs is necessary. Many scholars haveproposed various methods which focus on testing interleaving sequence to detectdeadlocks, unintentional races, and resources competition. On the premise of thenormal communication, it is necessary to investigate the structure coverage of parallelprograms for testing other internal details, further improving the reliability of parallelprograms. The key of the structure coverage is to generate test data satisfying theadequacy criteria. In the field of software testing, although genetic algorithms havebecome an important strategy of generating test data, existing methods are mainlysuitable for serial programs. Considering the path coverage, this issue investigatestheories and applications of evolutionary test data generation for message passingparallel programs. The main studies include:A co-evolutionary solution for generating test data to cover the path of parallelprograms is investigated. Aiming at parallel programs with determinacy, in whichexecution paths of each progress are determined uniquely by input components relatedto it, the mathematical model of generating test data is built and a novelco-evolutionary genetic algorithm is proposed. According to the correlation between aprocess path and its associated input components, a set of sub-populations and acooperative population are introduced. Each sub-population independently evolves tooptimize a part of the input associated to the specific process path, whereas thecooperative population based on excellent individuals from all sub-populations is usedto optimize the whole input. These two kinds of populations alternatively evolve toeffectively solve the above model and generate test data covering the target path,while providing new ideas for employing co-evolutionary methods to software testing.Considering the non-determinacy of parallel programs, a method of evolutionarygeneration of test data covering one path is presented. When some non-deterministiccommunication statements are employed in a parallel program, it may be executed in a non-deterministic way because of the task partition, process schedule andcommunication delay, which brings a great challenge for generating test data. Forreducing the influence of non-deterministic execution on generating test data, anequivalent path is defined and a method of searching for it is given. Based on thesepaths, a mathematical model of generating test data for path coverage of this kind ofprograms is formulated, and a strategy of solving the model by using a geneticalgorithm is presented. This provides a reasonable way to solve the problem ofgenerating test data for the programs with non-deterministic feature. In order todecrease the computation cost required by generating test data, a method ofevolutionary test data generation through selecting target paths is further proposedbased on the coverage difficulty. First, the method selects the path to be covered toreduce the coverage difficulty in the light of variables affecting a path’s execution,complexities of a path’s crucial conditions, and Halstead’s metric. Second, the geneticalgorithm is employed to generate test data covering the path, so as to improve theefficiency of generating test data.For the problem of multiple paths coverage, an evolutionary solution of generatingtest data covering multiple paths is studied. A mathematical model is built and anevolutionary method is presented against it. The problem of test data generation formultiple paths coverage is first formulated into a multi-objective optimizationproblem, where each objective is corresponding with a target path and its allequivalent paths. An appropriate fitness function is designed when employing agenetic algorithm to solve the above problem. The proposed method can synthesizemultiple test data to cover the given paths or their equivalent ones in one run.Finally, a multi-population parallel genetic algorithm based on grouping thetarget paths is employed to tackle the many paths coverage of parallel programs. Thepremise on which the above method is efficient is appropriately grouping target paths.The problem of grouping target paths is first investigated for the generation of testdata covering many paths of serial programs, and a novel method of grouping targetpaths is presented. In this method, target paths are divided into several groupsaccording to calculation resource available and the similarities among target paths,making a small difference in the number of target paths belonging to different groups,and a great similarity among target paths in the same group. The parallel geneticalgorithm based on this method can make full use of the calculation resources,improving the efficiency of generating test data. Then, based on this, a grouping method suitable for parallel programs is proposed by considering their features ofparallel execution. The number of groups and paths contained in them are determinedaccording to the processes and calculation resource available. The paths are groupedby leveraging all process paths’ similarities. According to the paths of each group, amathematical model is built for parallel generation of test data covering many paths,and a strategy of solving the above model by using a multi-population geneticalgorithm is presented.The research work of this issue enrich the theory of parallel program testing tosome extent, improve the efficiency of generating test data, and extend the applicationdomain of the evolutionary methods, thus having important theoretical and practicalvalues. |
PDF Full Text Request