Goal-oriented dynamic test generation
Automated software testing is increasingly being seen as an important means of improving the quality and reliability of software in industry. It mitigates the hardship of manual testing, which is labour-intensive and error-prone, and alleviates the expensive cost of software testing, which often accounts for around half of total software development costs. One way of enhancing automated software testing is to automate the process of test input generation. Over the last three decades, a considerable research effort has attempted to achieve this goal. This thesis concentrates on the scalability problem of the test input generation process, which lies at the heart of the automation of the software testing process. It develops techniques to perform test input generation in a goal-oriented mechanism in order to achieve high structural coverage criteria and maximize security vulnerability detection. The techniques developed in this thesis are based on well-established theoretical foundations of program analysis and software testing. They distinguish themselves from existing techniques through their capability to precisely identify a root cause leading to the execution of a specific test goal and to perform test input generation in a directed automated manner toward effectively and efficiently exploring the test goal.
A comparative evaluation was conducted via two sets of experiments in which our proposed techniques significantly outperformed existing techniques. Specifically, on a benchmark of 15 simulated and real world test subjects, our structural coverage testing technique significantly optimized the test input generation effort to achieve the highest structural coverage when compared to state-of-the-art techniques. Additionally, on a benchmark of 23 buffer overflow vulnerabilities, our security testing technique discovered security vulnerability defects within a matter of a few seconds, while existing techniques failed even after 30 minutes of testing on a number of test subjects.
This thesis contributes to scientific knowledge by enriching the application of computer science theory, and proposes techniques to improve the efficiency of automated software testing.