Context: Model Based Testing (MBT) has attracted a lot of attention from researchers since it has proved efficient in using formal models to represent reactive systems behavior in order to guide test case generation. Such systems are mostly specified and verified using Finite State Machine (FSM), a formal modeling technique commonly used to represent systems behavior. There is a plethora of test generation algorithms in the literature. Most of them are graph-based once a FSM can be considered as a graph. Nevertheless, there is a lack of studies on analyzing cost and efficiency of FSM-based test generation algorithms. Objective: This dissertation aims to investigate and 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 breadth-first and depth-first search (BFS, DFS) algorithms in the context of covering all-transitions (AT) and all-transition-pairs (ATP) criteria in a FSM. Method: First, a systematic literature mapping was conducted to summarize the methods that have been adopted in MBT, considering FSM. Second, the main methods found were implemented and analyzed on random and real-world FSMs that represent embedded systems of space applications. For the evaluation of studies, we considered analyses in terms of cost (time), efficiency (mutant analysis) and coverage of the generated test cases (number of test cases, average length of test cases, largest and smallest test cases, etc.). Results: In general, CPP presented the best 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.
Contexto: Teste Baseado em Modelo (TBM) tem atraído muita atenção de pesquisadores da área de Teste de Software, uma vez que se mostrou eficaz usando modelos formais para representar o comportamento do sistema a fim de orientar a geração de casos de teste. Estes software são geralmente especificados e verificados usando uma técnica de modelagem formal chamada Máquina de Estados Finitos (MEF). Existem diversos algoritmos de geração de casos de teste na literatura. A maioria são baseadas em grafo, uma vez que uma MEF pode ser considerada como um grafo. No entanto, há falta de estudos que analisam o custo e a eficiência de algoritmos de geração de casos de teste baseado em MEF. Objetivo: Esta dissertação tem como objetivo investigar e comparar algoritmos baseados em grafo aplicados á geração de casos de teste a partir de modelos MEFs. Em particular, comparamos os algoritmos do Problema do Carteiro Chinês (PCC) e o H − SwitchCover com os algoritmos clássicos da literatura, Busca em Largura e Busca em Profundidade (BL e BF), no contexto de cobrir uma MEF com os critérios todas-as-transições (TT) e todos-os-pares-de-transições (TPT). Método: Primeiro, um mapeamento sistemático da literatura foi conduzido para sumarizar os métodos que tem sido adotados em TBM, considerando as MEFs. Segundo, os principais métodos foram implementados e analisados com MEFs aleatórias e reais que representam sistemas embarcados de aplicaÇões espaciais. Para a avaliação dos estudos, foram considerados análises em termos de custo (tempo), eficiência (análise de mutante) e cobertura dos casos de teste gerados (número dos casos de teste, tamanho médio dos casos de teste, os maiores e menores casos de teste, etc.). Resultados: No geral, o PCC apresentou os melhores resultados para as MEFs usadas em termo de número dos casos de teste e tamanho da suíte de teste. Além disso, o PCC também apresentou baixa distribuição do tamanho médio comparado aos outros algoritmos.
