Diversity oriented test data generation using meta-heuristic techniques

Resumo: Técnicas e critérios de teste de software estabelecem elementos requeridos a serem exercitados no teste. A geração de dados de teste visa selecionar dados de teste, do domínio multidimensional de entrada do software, para satisfazer um critério. Uma linha de trabalhos para a geração de dados de teste utiliza meta-heurísticas para buscar, no espaço de possíveis entradas do software, aquelas que satisfaçam um determinado critério, área referida como Teste de Software Baseado em Buscas. Esta tese propõe uma nova técnica, a Geração de Dados de Teste Orientada à Diversidade (Diversity Oriented Test Data Generation - DOTG). Esta técnica incorpora a intuição, encontrada em bons projetistas de teste, de que a variedade, ou diversidade, dos dados de teste tem um papel relevante para a completeza, ou qualidade, do teste realizado. São propostas diferentes perspectivas para a diversidade do teste; cada perspectiva leva em consideração um tipo de informação distinto para avaliar a diversidade. É definido também um meta-modelo para guiar o desenvolvimento das perspectivas da DOTG. É desenvolvida a perspectiva do domínio de entrada do software para a diversidade (DOTG-ID), que considera a posição dos dados de teste neste domínio para calcular a diversidade do conjunto de teste. São propostas uma medida de distância entre dados de teste e uma medida de diversidade de conjuntos de teste. São desenvolvidas três meta-heurísticas para a geração automática de dados de alta diversidade: a SA-DOTG, baseada em Recozimento Simulado; a GA-DOTG, baseada em Algoritmos Genéticos; e a SR-DOTG, baseada na dinâmica de sistemas de partículas eletricamente carregadas. A avaliação empírica da DOTG-ID inclui: uma simulação Monte Carlo, realizada com o objetivo de estudar a influência de fatores na eficácia da técnica; e um experimento com programas, realizado para avaliar o efeito da diversidade dos conjuntos de teste na cobertura alcançada, medida com respeito a critérios de teste baseados em análise de fluxos de dados e no critério baseado em defeitos Análise de Mutantes. Os resultados das avaliações, significativos estatisticamente, indicam que na maioria das situações os conjuntos de alta diversidade atingem eficácia e valores de cobertura maiores do que os alcançados pelos conjuntos gerados aleatoriamente, de mesmo tamanho.Abstract: Software testing techniques and criteria establish required elements to be exercised during testing. Test data generation aims at selecting test data from the multidimensional software´s input domain to satisfy a given criterion. A set of works on test data generation apply metaheuristics to search in the space of possible inputs for the software for those inputs that satisfy a given criterion. This field is named Search Based Software Testing. This thesis proposes a new technique, the Diversity Oriented Test Data Generation - DOTG. This technique embodies the intuition, which can be found in good testers, that the variety, or diversity, of test data used to test a software has some relation with the completeness, or quality, of the testing performed. We propose different perspectives for the test diversity concept; each one takes into account a different kind of information to evaluate the diversity. A metamodel is also defined to guide de development of the DOTG perspectives. We developed the Input Domain perspective for diversity (DOTG-ID), which considers the positions of the test data in the software input domain to compute a diversity value for the test sets. We propose a measure of distance between test data and a measure of diversity of test sets. For the automatic generation of high diversity test sets three metaheuristics were developed: the SA-DOTG based on Simulated Annealing; the GADOTG based on Genetic Algorithms, and the SR-DOTG, based on the dynamics of particle systems electrically charged. The empirical evaluation of DOTG-ID includes: a Monte Carlo simulation performed to study the influence of factors on the technique´s effectiveness, and an experiment with programs, carried out to evaluate the effect of the test sets diversity on the attained coverage values, measured with respect to data-flow coverage and to mutation coverage. The evaluation results statistically significant, pointing out that in most of cases the test sets with high diversity reach effectiveness and coverage values higher than the ones reached by randomly generated test sets of the same size