Sentinel : a multi-objective hyper-heuristic approach for the automatic generation of mutant reduction strategies

Abstract

Resumo: O Teste de Mutação utiliza programas mutantes gerados com pequenas modificações no programa em teste. Tais modificações são produzidas por operadores de mutação que descrevem possíveis defeitos. O objetivo é matar os mutantes com casos de teste que produzam diferentes saídas para os mutantes e para o programa original. Ao final, uma medida de avaliação do teste, o escore de mutação, é dada considerando o número de mutantes mortos em relação ao número de mutantes gerados. O teste de mutação é bastante eficaz em revelar defeitos, entretanto, possui um alto custo computacional relacionado à execução dos mutantes. Diferentes estratégias existem para reduzir o custo do teste de mutação. Por exemplo, um subconjunto de mutantes pode ser selecionado aleatoriamente, ou pode-se utilizar um conjunto menor de operadores, ou ainda algoritmos de busca para selecionar os melhores mutantes ou operadores sem reduzir o escore global. Experimentos reportados na literatura mostram que nenhuma estratégia pode ser considerada a melhor em todos os contextos. A determinação das melhores estratégias e suas combinações de parâmetros só é possível com a condução de experimentos comparando estratégias em cenários específicos, o que pode elevar o custo do teste. O uso de uma estratégia inadequada pode comprometer a eficácia do teste e implica em uma redução de custo insatisfatória. Uma abordagem automática para selecionar e configurar estratégias pode auxiliar o testador nesta tarefa. Hiper-heurísticas são opções viáveis para este propósito, uma vez que estas são utilizadas para selecionar ou gerar boas heurísticas (estratégias) ao invés de tentar resolver o problema diretamente. Hiper-heurísticas vêm sendo estudadas na literatura, e bons resultados foram obtidos na área de Engenharia de Software Baseada em Busca. Todavia, poucos trabalhos investigam a aplicação de hiper-heurísticas no teste de mutação, e nenhum deles auxilia na geração ou configuração de estratégias de teste de mutação. Diante disto, este trabalho propõe uma abordagem baseada em hiper-heurísticas chamada Sentinel. Essa abordagem tem como objetivo principal gerar automaticamente estratégias de redução de mutantes de modo a reduzir o custo do teste de mutação sem comprometer a eficácia do teste em termos de escore de mutação e a habilidade de revelar defeitos. Sentinel utiliza elementos provenientes de diversos tipos de estratégias de redução de mutantes e os combina de modo a gerar novas estratégias potencialmente mais efetivas. A ideia é que o testador execute Sentinel, reutilize as estratégias geradas automaticamente e consequentemente não necessite escolher e nem configurar as estratégias manualmente. Isso facilita a aplicação do teste de mutação e reduz assim o custo da atividade de teste como um todo. Para avaliar a viabilidade de Sentinel, múltiplos experimentos foram executados. Os experimentos foram conduzidos em 10 diferentes sistemas com 4 versões cada, totalizando 40 sistemas. As estratégias geradas por Sentinel se mostraram significativamente mais efetivas do que estratégias convencionais da literatura. Além disso, elas mantiveram os seus bons resultados em novas versões dos softwares, o que demonstrou a sua reusabilidade. Palavras-chave: hiper-heurística, teste de software, geração de estratégias, redução de mutantes, evolução gramatical, engenharia de software baseada em busca, otimização multiobjetivo.

Abstract: Mutation Testing uses mutant programs generated with small modifications in the program under test. Such modifications are produced by mutation operators that describe possible faults. The objective is to kill the mutants with test cases that produce different outputs for the mutants and the original program. In the end, a test assessment measure, called mutation score, is computed considering the number of dead mutants with respect to the number of generated ones. Mutation testing is very efficacious in revealing faults, however, it has a high computational cost related to the execution of mutants. There are several strategies to reduce the mutation testing cost. For instance, a subset of mutants can be randomly selected, or a smaller set of operators can be used, or even search based algorithms can be applied to select the best mutants or operators without reducing the global mutation score. Experiments reported in the literature show that no strategy has been proven to be the best one in all contexts. The determination of the best strategies and their parameter combination is only possible by conducting experiments comparing the strategies in specific scenarios, which can increase the testing cost. The use of an inadequate strategy might compromise the test efficacy and implies in unsatisfactory cost reduction. An automatic approach to select and configure strategies can assist the tester in this task. Hyper-heuristics are viable options for this end, since they are used for selecting or generating heuristics (strategies) instead of trying to solve the problem directly. Hyper-heuristics have been studied in the literature and good results were obtained in the Search Based Software Engineering field. However, few works have investigated the usage of hyper-heuristics in mutation testing, and none of them support the generation or configuration of mutation testing strategies. In light of this, this work proposes a hyper-heuristic based approach called Sentinel. This approach has as main objective the automatic generation of mutant reduction strategies for the cost reduction of mutation testing without compromising the test efficacy in terms of mutation score and ability in revealing faults. Sentinel uses features from several kinds of mutant reduction strategies and combines them to generate new strategies that are potentially more effective. The idea is that the tester executes Sentinel, reuses the automatically generated strategies and consequently does not need to select and configure strategies manually. This eases the mutation testing application and thus reduces the overall cost of the testing activity. For assessing the feasibility of Sentinel, multiple experiments were performed. The experiments were conducted using 10 different systems with 4 versions of each, in a total of 40 systems. The strategies generated by sentinel showed to be significantly more effective than conventional strategies of the literature. Furthermore, they kept their good results in newer versions of the software, which demonstrated their reusability. Keywords: hyper-heuristic, software testing, strategy generation, mutant reduction, grammatical evolution, search based software engineering, multi-objective optimization.