Perspectives On Search Strategies In Automated Test Input Generation

During the software development process,the security and reliability of software have always been threatened by multiple defects.Moreover,as the program scales larger and becomes more complex,the problem has become more and more severe,which making the software testing especially important.Compared with traditional manual testing,automated test input generation has a great advantage in terms of cost,and now has been widely used in the industry.There existing many different testing approaches can automatically generate test inputs,in-cluding random testing and metamorphic testing.Among all these related testing tech-niques,fuzzing testing and DSE(Dynamic Symbolic Execution)are the most popular and efficient ones.However,we still have problems in generating high quality test in-put subset and efficiently achieving target test input,which greatly hindering the further development of automated test input generation.Until now,there have been many studies,surveys and techniques proposed for the automated test input generation.All these related works do polish the automated test input generation.However,unfortunately,there are still a lot of problems unsolved in automated test input generation until today.We are eager to make breakthroughs to solve these problems,While on the other hand,we gradually realized that the traditional framework cannot help us to reach the goal.We need a unique and unified perspective to help us model and characterize the test input generation problem and its solutions(including fuzzing,DSE,and potential future techniques).Main research works are as follows:1.We view the automated test input generation as a search problem,and proposed a framework containing neighborhood definition N,neighbor selection strategy 5 and bootstrap test inputs H0.The framework<N,S,H0>provides us a unique and unified perspective to model and characterize the test input generation problem and its solutions(including fuzzing,DSE,and potential future techniques),which helping us further understand the characteristics,advantages,and disadvantages of all these related works.2.Based on the framework<N,S,H0>,we conducted a mini survey,which contains representative fuzzing and DSE techniques as well as their hybrids.Based on the mini survey,we sorted out the historical development of these related works.We investigated the characteristics,advantages,and disadvantages of all these related works,and searched for potential future research directions.3.Based on the framework<N,S,H0>,we conducted an empirical study.In the study,we used GNU CoreUtils as subjects,used AFLfast as the representative of fuzzing testing and used KLEE as the representative of DSE.We investigated the coverage performance of fuzzing/DSE and studied 142non-covered cases to summarize their non-covered causes.We found the insufficient modeling accounting for 26%/49%,while the algorithmic limitation accounting for64%/40%.Furthermore,we studied the complementariness and common limitations between fuzzing and DSE.4.To solve the hunger problem from AFL's search strategy,we proposed a solution containing dynamically cutting off invalid mutation operators,dynamically cutting off invalid bytes,and local depth first search strategy based on the code coverage difference.We implemented AFLSU based on AFL.Our experiments showed that AFLSU can alleviate the huger problem and can achieve a higher statement coverage performance than both AFL(up to 40.35%,17.27%for average)and AFLfast(up to 36.66%,12.86%for average).