Graduation Semester and Year
2021
Language
English
Document Type
Dissertation
Degree Name
Doctor of Philosophy in Computer Science
Department
Computer Science and Engineering
First Advisor
Yu Lei
Abstract
Combinatorial and sequential testing are software testing strategies that have attracted significant interests from both academic and industrial communities. This dissertation addresses the problem of how to efficiently generate tests for both combinatorial and sequential testing. The dissertation makes two major contributions. For combinatorial testing, we present several optimizations on an existing t-way test generation algorithm called IPOG. These optimizations are designed to reduce the number of tests generated by IPOG. For sequential testing, we develop a notion for expressing commonly used sequencing constraints and present a t-way test sequence generation algorithm that support constraints expressed using notation. We demonstrate the effectiveness of our notation and test generation algorithm using a real-life protocol that exhibits sequencing behavior. This dissertation is presented in an article-based format, including three published research papers and one manuscript that is currently under review. The first two papers are about combinatorial test generation. The other two papers are about sequential test generation. The first paper reports our work on reducing the number of tests generated during the vertical growth phase of the IPOG algorithm, where the vertical growth problem is modeled as the classical "Minimum Vertex Coloring" problem. The second paper reports our work on extending the approach in the first paper to support constraints, where constraints are represented as edges and hyperedges in a graph structure. The third paper reports our work on addressing the problem of constraint handling in sequential testing, where we design a notation for sequencing constraint specification and develop a new algorithm to handle constraints expressed using our notation. The fourth paper reports our latest work on sequential testing, where we translate constraints expressed using our notation to Deterministic Finite Automaton (DFA) and use DFA to check sequence validity and extensibility.
Keywords
Combinatorial testing, Multi-way test generation, ACTS, Hyperedge, Minimum vertex coloring, Tuple ordering, Constraint handling, Minimum forbidden tuples, Sequential testing, Test sequence generation, Sequencing constraint, T-way sequence coverage, Event-based testing
Disciplines
Computer Sciences | Physical Sciences and Mathematics
License
This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 International License.
Recommended Citation
Duan, Feng, "ADVANCED ALGORITHMS FOR COMBINATORIAL AND SEQUENTIAL TEST GENERATION WITH CONSTRAINTS" (2021). Computer Science and Engineering Dissertations. 379.
https://mavmatrix.uta.edu/cse_dissertations/379
Comments
Degree granted by The University of Texas at Arlington