Open AccessA comparative study of algorithms for generating switch cover test sets
Author(s) -
Matheus Monteiro Mariano,
Érica Ferreira de Souza,
André Takeshi Endo,
Nandamudi Lankalapalli Vijaykumar
Publication year - 2016
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/sbqs.2016.15122
Subject(s) - eulerian path , test suite , algorithm , breadth first search , computer science , cover (algebra) , graph , finite state machine , automatic test pattern generation , context (archaeology) , code coverage , test case , theoretical computer science , mathematics , software , programming language , engineering , mechanical engineering , paleontology , electronic circuit , regression analysis , electrical engineering , lagrangian , machine learning , mathematical physics , biology
Test case generation based on Finite State Machines (FSMs) has been extensively investigated due to its accuracy and simplicity. Several test criteria have been proposed in the literature to generate test cases based on FSMs. One of the oldest criteria is the Switch Cover. As a main feature, the Switch Cover criterion defines that all transition pairs of an FSM must be covered. The classical Switch Cover algorithm converts the FSM into a graph (known as Dual Graph); this graph is balanced, and, finally, traversed based on an Eulerian Cycle algorithm. In this context, considering the stage where an FSM is converted into a graph, this study investigates other search algorithms on graphs, namely Depth-First Search (DFS) and Breadth-First Search (BFS), for generating test sets from a Dual Graph. We presented an experimental study that compares the DFS, BFS algorithms with the Eulerian Cycle. The study was conducted with a set of random and real-world machines, taking into account the number of test cases, the test suite size, the average length of sequences and generation time.