@Article{MarianoSouzEndoVija:2019:CoGrAl,
author = "Mariano, Matheus Monteiro and Souza, {\'E}rica Ferreira de and
Endo, Andr{\'e} Takeshi and Vijaykumar, Nandamudi Lankalapalli",
affiliation = "{Instituto Nacional de Pesquisas Espaciais (INPE)} and
{Universidade Tecnol{\'o}gica Federal do Paran{\'a} (UTFPR)} and
{Universidade Tecnol{\'o}gica Federal do Paran{\'a} (UTFPR)} and
{Instituto Nacional de Pesquisas Espaciais (INPE)}",
title = "Comparing graph-based algorithms to generate test cases from
finite state machines",
journal = "Journal of Electronic Testing Theory and Applications",
year = "2019",
volume = "35",
number = "6",
pages = "867--885",
month = "Dec.",
keywords = "Software testing, Model based testing, Finite state machine,
Graph-based algorithms.",
abstract = "Model-Based Testing (MBT) is a well-known technique that employs
formal models to represent reactive systems' behavior and
generates test cases. Such systems have been specified and
verified using mostly Finite State Machines (FSMs). There is a
plethora of test generation algorithms in the literature; most of
them are based on graphs 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. This study
compares graph-based algorithms adopted 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 Search (DFS) and Breadth-First Search (BFS)
algorithms in the context of covering all-transitions and
all-transition-pairs criteria in an FSM. First, a systematic
literature mapping was conducted to summarize the methods that
have been adopted in MBT, considering FSMs. Second, the main
methods found were implemented and analyzed on randomly-generated
FSMs, as well as real-world models that represent embedded systems
of space applications. To make comparisons, we considered analyses
in terms of cost (time), efficiency (mutant analysis) and
characteristics of the generated test suites (number of test
cases, average length of test cases, largest and smallest test
cases, standard deviation and distribution of test cases). In
general, CPP presented the best results 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.",
doi = "10.1007/s10836-019-05844-6",
url = "http://dx.doi.org/10.1007/s10836-019-05844-6",
language = "en",
targetfile = "mariano_comparing.pdf",
urlaccessdate = "29 mar. 2024"
}