Research On Optimization Of Test Data Generation Based On Symbolic Execution

Software testing is the main and effective method to reduce software bugs and ensure the quality of software,but it is an expensive and time-consuming work.In order to improve the efficiency of software testing,automated testing becomes a trend of current software testing.Automated testing can not only simulate manual testing,reduce repeated and mechanical test workload,but also make better use of test resources and run more complex tests.In the whole process of automated testing,automated generation of test data is a critical issue.A popular and effective method is to use symbolic execution to generate test data.However,there are still several severe challenges hindering symbolic execution against turning into reality,and two classical problems are complex constraint set solution and path explosion problem.During test data generation based on symbolic execution,constraint solving,which is an extremely important operation,is responsible for solving constraint set to obtain test data.However,constraint solving is a NP-complete problem and the cost is expensive.For complex constraint set,constraint solving need to consume a lot of resources,thus reducing the efficiency of symbolic execution.In order to improve the efficiency of solving complex constraint set,thereby improving the efficiency of test data generation based on symbolic execution,constraint optimization techniques are usually applied to existing constraint solvers.However,whether constraint optimization techniques are effective and how to select optimization techniques are still open questions.To answers these questions,in this paper,we conducted empirical studies on the effective of four popular constraint optimization techniques("constraint independence","constraint set simplification","constraint caching",and "expression rewriting")for test data generation based on symbolic execution.Under same test resources,we applied constraint optimization technique and their combinations to generate test data,respectively.And using completed path as the metric to evaluate tests,to systematically investigate how these constraint optimization techniques affect the efficiency of test data generation.Experimental results show that these optimization techniques as well as their combinations can NOT improve the efficiency of test generation significantly for ALL-SIZED programs.Moreover,we studied the constraint optimization techniques with respect to two static metrics,lines of code(LOC)and cyclomatic complexity(CC),of programs.The experimental results show that the "constraint set simplification" technique can improve the efficiency of test generation significantly for the programs with high LOC and CC values.The "constraint caching" optimization technique can improve the efficiency of test generation significantly for the programs with low LOC and CC values.Finally,we propose four hybrid optimization strategies and practical guidelines based on different static metrics.With increasing program complexity and execution path length,the number of all executable paths of a program increases dramatically,therefore exploring all feasible paths is typically prohibitively expensive.Intelligent path searching strategies are often used to alleviate path explosion during symbolic execution.However,whether intelligent path searching strategies could improve the efficiency of test data generation based on symbolic execution,and how to select path searching strategies are still open questions.To answers these questions,in this paper,we conducted empirical studies on the effective of ten classical path search strategies(two random and eight intelligent search strategies)for test data generation based on symbolic execution,respectively.Under same test resources,we applied path search strategy to generate tests and used four metrics,which are completed path,tests only covering new code,statement coverage and branch coverage,to evaluate the tests,to systematically investigate how these path search strategies affect the efficiency of test generation.Experimental results show that without optimization,one approach from random strategy-random-path-performs better than other techniques.This result indicates that random strategy can be a better choice for test generation and intelligent strategy needs further investigation.However,when combined with optimization,the selection of strategy depends on the specific optimization applied.nurs-qc is suitable to combine with "constraint caching"and random-path is appropriate to combine with "constraint simplification".We further analyze reasons behind the statistical results and provide guidelines to select the appropriate path search strategy for test generation in practice.Finally,according to the results of our study,we propose a selection strategy to select constraint optimization technique and path search strategy.Given a program,according to program characteristics,test requirements and our selection strategy,testers could select appropriate constraint optimization technology and path search strategy during symbolic execution.Experiment results show that constrained optimization technique and path search strategy which are selected according to our selection strategy can significantly improve the efficiency of test generation based on symbol execution...