Feng Duan

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

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS