Theories And Methods Of Evolutionary Generation Of Test Data For Path Coverage

Software testing is an important means that guarantees software quality, aims todetect as many faults in the program under test as possible, and plays an importantrole in software development. The qualities of test data directly decide the test result,so the key question of software testing is to design effective test data. Existingresearches show that path testing is an important test adequacy criterion, and geneticalgorithm is an efficient method to automatically generate test data for path testing.Whereas, both the efficiency and rate of detecting faults of existing methods ongenerating test data need to be improved. This dissertation focuses on the theories andmethods of automatically generating test data for path testing using geneticalgorithms.First, considering that previous methods cannot effectively protect scarce datawhich traverse those nodes difficult to be covered, a method for capturing scarce datain evolutionary generation of test data for paths coverage is presented. In this method,the contribution of an individual to generate test data which traverse target paths isobtained by recording the number of individuals which traverse each node of thetarget path, and is regarded as a weight to adjust the fitness of an individual. In thisway, the fitness of a scarce datum can be increased, the scarce datum can beconserved in subsequent evolution, and the efficiency of generating test data is thusimproved.Then, a novel approach to generate test data for multiple paths coverage ispresented. In this method, the program under test is expressed as a binary tree; thetarget paths are encoded into a binary string using Huffman coding; an individual’sfitness is the degree of the traversed path matching the target paths, and a geneticalgorithm is employed to generate multiple test data, The proposed approach isapplied to several benchmark programs, and compared with previous approaches. Theresults indicate that the computation of the proposed approach is cheap and theefficiency in generating test data is high.Third, since the existing path-oriented testing methods may not find the faults inthe program under test, especially for those faults which emerge with a smallprobability, a method for evolutionarily generating test data is proposed for fulfillingpath coverage while detecting faults. To this end, a mathematical model of generatingtest data for path coverage with fault detection is established, which takes the number of faults in the traversed path and the risk level of the faults as the objectives, andtakes the approach level as the constraint; furthermore, a multi-objective evolutionarymethod to generate test data is proposed. The proposed method is applied to somepractical software testing, and the experimental results confirm that the test datagenerated by the method can not only traverse the target paths, but also detect faultslying in them.Finally, an improved approach is devised for the evolutionary processes ofgenerating test data using genetic algorithm, and the theory for evolutionarilygenerating test data for path coverage based on automatic reduction of the searchspace is presented. For the problem of generating test datum for only one target path,the relation between the target path and the input variable is determined, and thedivisible target path is divided into some sub-paths related to several elements of theinput variable. The elements corresponding to the traversed sub-path are fixed, andthe ranges of crossover and mutation operations are reduced in the process of theevolution, leading to the original population search for test data in a reduced space sothat the efficiency of generating test data is improved. For the problem of generatingtest date for multiple target paths, target paths are divided into several groups basedon the same sub-path which is only related to a part of input variables, and theelements of the input variable corresponding to the sub-path are determined. Thesub-populations whose number is the same with that of groups are used to generatethe test data of traversing the target paths in each group, respectively. During theevolution, the elements corresponding to the traversed sub-path are fixed, and therange of crossover and mutation operations are reduced, leading to the sub-populationsearch for test data in a reduced space so that the efficiency of generating test data isimproved.Results of this study provide new ways to generate test data for path coverage,enrich the theories of software testing based on evolutionary optimization, improvethe efficiency and the quality of test data generation, and then the cost of softwaretesting is reduced. Therefore, they have important theoretical significance andpractical values.