Orientador : Prof. Dr. Silvia Regina Vergilio / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 23/02/2017 / Inclui referências : f. 90-98 / Área de concentração: Ciência da Computação / Resumo: Determinar um conjunto de casos de teste que possua alta probabilidade de revelar defeitos em um software é um dos principais objetivos da área de teste de software. Dentre os vários critérios propostos na literatura destaca-se a Análise de Mutantes, uma abordagem promissora devido a sua capacidade em revelar defeitos, embora possua um custo computacional relativamente alto. Com o intuito de reduzir o custo da Análise de Mutantes, estudos empregam a utilização de mutação de ordem superior (Higher Order Mutants, HOMs). O uso de HOMs tem se destacado por reduzir o número de mutantes equivalentes, reduzir o esforço do teste e simular defeitos próximos dos defeitos reais. Entretanto, a geração dos melhores HOMs é uma tarefa complexa, devido ao grande número de mutantes que podem existir e a outros fatores que influenciam a geração, tais como a eficácia dos HOMs gerados. Trabalhos têm aplicado com sucesso técnicas da área da Engenharia de Software baseada em busca por meio da utilização de técnicas de otimização para solucionar esse problema. Entretanto, há ainda a necessidade de possuir um conhecimento sobre o comportamento do problema, de modo a determinar a melhor estratégia a ser utilizada, como projetar e configurar os algoritmos, escolhendo os diferentes operadores de busca e definindo seus parâmetros, para assim melhorar o direcionamento da busca. Neste sentido, o uso de hiper-heurística possibilita uma abordagem mais flexível para automatizar estas tarefas. Além disso, o uso de uma hiper-heurística de seleção de diferentes estratégias existentes para geração de HOMs pode ser útil para reduzir o esforço do testador. Diante disso, este trabalho propõe uma abordagem multi-objetivo que utiliza o conceito de hiper-heurística para gerar conjuntos de HOMs, denominada Hyper-Heuristic for Generation of Higher Order Mutants (HG4HOM). O objetivo é selecionar a menor quantidade de HOMs, os mais difíceis de serem mortos e assim melhorar a eficácia do teste, além de também possibilitar que ao matar um HOM seus FOMs (First Order Mutants) constituintes também possam ser mortos. Para isso, a abordagem é implementada e avaliada com dois algoritmos multi-objetivos: NSGA-II e SPEA2, e três métodos de seleção: Choice-Function (CF), Fitness-Rate-Rank based Multi-Armed Bandit (FRR-MAB) e a seleção aleatória (Random). O algoritmo SPEA2 utilizando o conceito de hiper-heurística juntamente com o método de seleção CF obteve os melhores resultados. Quando comparado com as estratégias tradicionais, a abordagem obteve resultados próximos em relação ao escore de mutação e valor equivalente ao melhor em relação ao tamanho do conjunto de casos de teste adequado. A abordagem obteve as soluções com melhores valores de Euclidean Distance considerando os objetivos relacionados a encontrar a menor quantidade de HOMs, os mais difíceis de serem mortos e capazes de substituírem seus FOMs constituintes. Palavras-chave: Teste de Software, Análise de Mutantes, Mutação de Ordem Superior, Algoritmos Evolutivos Multi-Objetivos, Hiper-Heurística. / Abstract: One of the main testing goals is to determine test sets with a high probability of revealing faults. Mutant Analysis is a promising criterion due to its ability to reveal faults, although with a high computational cost. In order to decrease the mutation testing cost, studies employ the use of Higher Order Mutants (HOMs). The use of HOMs can contribute to decrease the number of equivalent mutants, decrease the test effort and simulate faults close to the real ones. However, the generation of the best HOMs is a complex task, due to the large number of mutants that may exist, and to other factors that influence the generation, such as the efficacy of the generated HOMs. To solve such a problem, some works have successfully applied Search-based Software Engineering techniques through the use of optimization techniques. However, it is still needed to have knowledge about the problem behavior, to determine the best strategy to be applied, and to know how to design and configure the algorithms by choosing the different search operators and defining their parameters in order to improve the search. In this sense, the use of hyper-heuristics allows a more flexible approach to automating these tasks. Also, the use of a hyper-heuristic for selection of different existing strategies to generate HOMs can be useful to reduce the tester's effort. Considering all these facts, this work proposes a multi-objective approach, called Hyper-Heuristic for Generation of Higher Order Mutants (HG4HOM), which uses the hyper-heuristic concept to generate sets of HOMs. The goal is to select a small number of HOMs which are difficult to kill, and that contribute to improve the test efficacy, that is, it is desired the test cases that kill the selects HOMs are also capable of killing their corresponding FOMs (First Order Mutants). The approach is implemented and evaluated with two multi-objective algorithms: NSGA-II and SPEA2, and three selection methods: Choice-Function (CF), Fitness-Rate-Rank based Multi-Armed Bandit (FRR-MAB ), and random selection (Random). The SPEA2 algorithm using the hyper-heuristic concept together with the CF selection method obtained the best results. In comparison with respect to the traditional strategies, the approach achieved similar results related to the mutation score and statically equivalent values to the best strategy considering the size of the adequate test case sets. The approach obtained the best results when considering the Euclidean Distance values of the solutions with respect to the goals proposed. Keywords: Software Testing, Mutation Analysis, Higher Order Mutation, Multi-objective Evolutionary Algorithms, Hyper-heuristic.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/45905 |
| Date | January 2017 |
| Creators | Lima, Jackson Antonio do Prado |
| Contributors | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática, Vergilio, Silvia Regina, 1966- |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 98 f. : il., tabs., grafs., application/pdf |
| Source | reponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Disponível em formato digital |
Page generated in 0.0024 seconds