Download the full-sized PDF of Diversity-Based Automated Test Case GenerationDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Diversity-Based Automated Test Case Generation Open Access


Other title
software testing
failure detection
tree test case
diversity-based test generation
string test case
tree distance
black-box test generation
tree similarity
test case generation
automated software testing
Type of item
Degree grantor
University of Alberta
Author or creator
Shahbazi, Ali
Supervisor and department
Miller, James (Electrical and Computer engineering)
Examining committee member and department
Miller, James (Electrical and Computer engineering)
Labiche, Yvan (Department of Systems and Computer Engineering, Carleton University)
Hindle, Abram (Computing Science)
Dick, Scott (Electrical and Computer engineering)
Reformat, Marek (Electrical and Computer engineering)
Department of Electrical and Computer Engineering
Software Engineering and Intelligent Systems
Date accepted
Graduation date
Doctor of Philosophy
Degree level
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.
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication
A. Shahbazi; A.F. Tappenden; J. Miller, "Centroidal Voronoi Tessellations -- A New Approach to Random Testing," IEEE Transactions on Software Engineering, vol.39, no.2, pp.163-183, Feb. 2013A. Shahbazi; J. Miller, "Black-Box String Test Case Generation through a Multi-Objective Optimization," Under revision in IEEE Transactions on Software Engineering, 2015A. Shahbazi; J. Miller, "Extended Subtree: A New Similarity Function for Tree Structured Data," IEEE Transactions on Knowledge and Data Engineering, vol.26, no.4, pp.864-877, 2014A. Shahbazi; J. Miller, "Black-Box Tree Test Case Generation through Diversity," Submitted to IEEE Transactions on Software Engineering, 2015

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 6301325
Last modified: 2016:10:24 16:05:30-06:00
Filename: Shahbazi_Ali_201505_PhD.pdf
Original checksum: e21853f68964cc8d9d475ce4f8bea733
Activity of users you follow
User Activity Date