- 432 views
- 621 downloads
Diversity-Based Automated Test Case Generation
-
- Author / Creator
- Shahbazi, Ali
-
Software testing is an expensive task that consumes around half of a project’s effort. To reduce the cost of testing and improve the software quality, test cases can be produced automatically. Random Testing (RT) is a low cost and straightforward automated test generation approach. However, its effectiveness is not satisfactory. To increase the effectiveness of RT, researchers have developed more effective test generation approaches such as Adaptive Random Testing (ART) which improves the testing by increasing the test case coverage of the input domain. This research proposes new test case generation methods that improve the effectiveness of the test cases by increasing the diversity of the test cases. Numerical, string, and tree test case structures are investigated. For numerical test generation, the use of Centroidal Voronoi Tessellations (CVT) is proposed. Accordingly, a test case generation method, namely Random Border CVT (RBCVT), is introduced which can enhance the previous RT methods to improve their coverage of the input space. The generated numerical test cases by the other methods act as the input to the RBCVT algorithm and the output is an improved set of test cases. An extensive simulation study and a mutant based software testing investigation have been performed demonstrating that RBCVT outperforms previous methods. For string test cases, two objective functions are introduced to produce effective test cases. The diversity of the test cases is the first objective, where it can be measured through string distance functions. The second objective is guiding the string length distribution into a Benford distribution which implies shorter strings have, in general, a higher chance of failure detection. When both objectives are enforced via a multi-objective optimization algorithm, superior string test sets are produced. An empirical study is performed with several real-world programs indicating that the generated string test cases outperform test cases generated by other methods. Prior to tree test generation study, a new tree distance function is proposed. Although several distance or similarity functions for trees have been introduced, their failure detection performance is not always satisfactory. This research proposes a new similarity function for trees, namely Extended Subtree (EST), where a new subtree mapping is proposed. EST generalizes the edit base distances by providing new rules for subtree mapping. Further, the new approach seeks to resolve the problems and limitations of previous approaches. Extensive evaluation frameworks are developed to evaluate the performance of the new approach against previous methods. Clustering and classification case studies are performed to provide an evaluation against different tree distance functions. The experimental results demonstrate the superior performance of the proposed distance function. In addition, an empirical runtime analysis demonstrates that the new approach is one of the best tree distance functions in terms of runtime efficiency. Finally, the study on the string test case generation is extended to tree test case generation. An abstract tree model is defined by a user based on a program under the test. Then, tree test cases are produced according to the model where diversity is maximized through an evolutionary optimization technique. Real world programs are used to investigate the performance of generated test cases where superior performance of the introduced method is demonstrated compared to the previous methods. Further, the proposed tree distance function is compared against the previous functions in the tree test case generation context. The proposed tree distance function outperforms other functions in tree test generation.
-
- Graduation date
- Fall 2015
-
- Type of Item
- Thesis
-
- Degree
- Doctor of Philosophy
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.