Evolutionary Generation Of Test Data With Low-cost For Path Coverage Of MPI Parallel Programs

The testing cost is dramatically increased with the complexity of a software.For a Message-Passing Interface(MPI)parallel program with non-determinism,it will consume a higher testing cost to generate a test datum covering the target path.In addition,during generating a test datum that covers a target path based on evolutionary optimization,the program needs to be executed repeatedly to evaluate the performance of each test datum,which further increases the testing cost.In view of this,it is necessary to research the theories and methods of evolutionary generation of test data with low-cost for path coverage of MPI parallel programs.First,for the problem of testing with high-cost caused by an MPI parallel program with non-determinism,a method of selecting communication sequence to generate test data for path coverage is proposed.In the proposed method,a number of program inputs are sampled by Latin hypercube sampling.The program is executed by each sampled input under each communication sequence,and all the communication sequences are sorted according to the similarities between the paths traversed by these inputs and the target one.The feasible communication sequence is selected based on the symbolic execution,and a test datum covering the target path is generated based on evolutionary optimization under the selected communication sequence.The proposed method is applied to seven benchmark MPI parallel programs and compared with three state-of-the-art methods.The experimental results show that the test data covering the target paths can be efficiently generated under the selected communication sequences.Then,regarding the problem of evaluation way with high-cost of test data using the existing surrogate model,a method of generating test data for path coverage based on ensemble surrogate-driven evolutionary optimization is proposed.The proposed method produces a number of test data using evolutionary optimization,and forms a training set together with their evaluations.Based on the MPI parallel programming standard,an ensemble surrogate model is constructed,and trained by the training set,so as to estimate the performance of each test datum.Test data are sorted according to the estimated performances,and a small number of test data with good estimations are selected further to execute the MPI parallel program,so as to have their evaluations for the subsequent test data generation.The proposed method is applied to seven benchmark MPI parallel programs,and compared with three state-of-the-art methods.The experimental results show that the proposed method can significantly reduce the cost of test data generation.Following that,aiming at the problem of generating test data with multi-mode characteristic,a method of integrating clustering and surrogate models into test data generation for path coverage based on evolutionary optimization is proposed.A sample set is divided into a number of classes according to the multi-mode characteristic of the path coverage problem,and all the samples in each class are used to train a surrogate model.The performance of each test datum is estimated by the trained surrogate models when generating test data based on evolutionary optimization.A small number of representative test data are selected to execute the MPI parallel program,with the purpose of obtaining their evaluations,so as to guide the subsequent generation of test data,and reduce the number of the program needs to be executed.The proposed method is applied to seven benchmark MPI parallel programs and compared with five state-of-the-art methods.The experimental results show that the proposed method can significantly reduce the cost of generating the desired test data.Finally,with respect to the problem of execution with high-cost of one or more processes in an MPI parallel program,a method of test data generation for path coverage using distributed-surrogate-guided evolutionary optimization is proposed.Each process with high-cost and its input variables are determined,and an initial sample set for the determined process is generated,so as to train a surrogate model.Based on the trained surrogate model of each process with high-cost,the performances of a test datum in those processes with high-cost are estimated,and combined with other performances of the test datum in other processes to form the estimated performance.Based on the estimated performance of each test datum,a small number of test data with high estimations are selected to execute the MPI parallel program,and their evaluations are calculated to guide the subsequent test data generation.The proposed method is applied to seven benchmark MPI parallel programs,and compared with four state-of-the-art methods.The experimental results show that the proposed method can significantly decrease the cost for test data generation.The above researches enrich the theories and methods of test data generation for path coverage of MPI parallel programs using evolutionary optimization,reduce the cost of test data generation,and have important theoretical significance and practical value.