Paper Info
Title
Analyzing graph-based algorithms employed to generate test cases from finite state machines
Abstract
Context: Model-Based Testing (MBT) is a technique that employs formal models to represent reactive systems’ behav-ior and generates test cases. Such systems are mostly specified and verified using Finite State Machines (FSMs). There is a plethora of test generation algorithms in the literature. Most of them are graph-based once an FSM can be formally defined as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. Objective: This study aims to compare graph-based algorithms employed to generate test cases from FSM models. In particular, we compare the Chinese Postman Problem (CPP) and H-Switch Cover (HSC) algorithms with the well-known depth-first and breadth-first searches algorithms in the context of covering all-transitions and all-transition-pairs criteria in an FSM. Method: First, a systematic literature mapping was conducted to summarize the algorithms that have been adopted in MBT, considering FSM. The main algorithms found were implemented and analyzed in different experiments. Results: CPP presented better results with the FSMs used in terms of number of test cases and test suite size. In addition, CPP also presented low distribution of average length compared to other algorithms.
Year
DOI
Venue
2019
10.1109/LATW.2019.8704603
2019 IEEE Latin American Test Symposium (LATS)
Keywords
Field
DocType
Software Testing,Model Based Testing,Finite State Machine,Graph-based algorithms
Test suite,Graph,Computer science,Route inspection problem,Algorithm,Finite-state machine,Model-based testing,Test case,Reactive system,Software testing
Conference
ISBN
Citations 
PageRank 
978-1-7281-1756-0
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Matheus Monteiro Mariano100.34
Érica F. Souza200.34
André Takeshi Endo3385.75
Nandamudi L. Vijaykumar4547.18