Advanced Software Testing Techniques Based On Combinatorial Design

Abstract

Combinatorial testing refers to a testing strategy that applies the principles of combinatorial design to the domain of software test generation. Given a system with k parameters, combinatorial testing requires all the combinations involving t out of k parameters be covered at least once, where t is typically much smaller than k. The key insight behind combinatorial testing is that while the behavior of a system may be affected by many parameters, most faults are caused by interactions involving only a small number of parameters. Empirical studies have shown that combinatorial testing can dramatically reduce the number of tests while remaining effective for fault detection. Existing work on combinatorial testing has mainly focused on functional requirements, and has only considered non-interactive systems, i.e., systems that take all inputs up front without interacting with the user in the middle of a computation. In this dissertation, we propose three new combinatorial testing techniques, two of which deal with interactive web applications, and the third one deals with non-functional security requirements: (1) Combinatorial construction of web navigation graphs: A navigation graph captures the navigation structure of a web application. The main challenge is handling dynamic web pages that are only generated at runtime and in response to user requests. We develop a combinatorial approach that generates user requests to discover these dynamic web pages. We report a software tool called Tansuo, and demonstrate the effectiveness of our approach using several real-life open-source web applications. (2) Combinatorial test sequence generation for web applications: One important aspect of web applications is that they often consist of dynamic web pages that interact with each other by accessing shared objects. It is nearly always impossible to test all possible interactions that may occur in a web application of practical scale. We develop a combinatorial approach to systematically exercising these interactions. Our experimental results show that our approach can effectively detect subtle interaction faults that may exist in a web application. (3) Detection of buffer overflow vulnerabilities: Buffer overflow vulnerabilities are program defects that can cause a buffer to overflow at runtime. Many security attacks exploit buffer overflow vulnerabilities to compromise critical data structures. We develop a combinatorial approach to detecting buffer overflow vulnerabilities. Our approach exploits the fact that combinatorial testing often achieves a high level of code coverage. Experimental results show that our approach can effectively detect buffer overflow vulnerabilities.