FSM Testing Based on Transition Trees and Complete Round Trip Paths Testing Criteria

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Khalil, Hoda




State machine testing has received genuine attention in the literature. Among the studied testing strategies are complete round-trip paths and transition trees that cover round-trip paths in a piecewise manner. Although trees are claimed to be equivalent to complete round-trip paths testing, there is anecdotal evidence that this is not the case. The core contribution of this thesis is therefore an empirical comparison between the effectiveness of the complete round-trip paths test suites and the transition trees test suites on the one hand and the effectiveness of the different techniques used to generate transition trees (breadth first traversal, depth first traversal, and random traversal) on the other hand. The comparison is conducted using four experimental objects and a significant number of test suites. Other contributions include constructing a reusable experimental setup and developing our automatic toolchain including novel algorithms to generate the different types of test suites. We also evaluate the effect of the structure of the transition trees as well as the state machine on the fault detection capability of the resulting test suites.

Our results demonstrate that covering round-trip paths in a complete manner is not equivalent to covering them in pieces. In addition, using statistical analysis, we prove that the different types of transition trees and even every single tree has different fault detection capability. Then, we show that neither the average length of the test cases in a test suite, nor the standard deviation of the test cases length, nor the number of complete round-trip paths included in a transition tree affects the effectiveness of the test suite. We also show that the effectiveness of the complete round-trip test suites is proportional to the connectivity of the finite state machine of the system under test.


System Science
Engineering - Electronics and Electrical




Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Engineering, Electrical and Computer

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).