Made available in DSpace on 2014-06-12T15:50:21Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Com a crescente demanda por diminuição de custos no desenvolvimento de software, há a necessidade de que os programas possam ser construídos de acordo com uma especificação concordante com os requisitos do cliente. Nesse sentido, a especificação formal pode ser utilizada para representar os requisitos do sistema. Uma vez que a especificação formal foi desenvolvida, ela pode ser usada como base para investigar determinadas propriedades através de um verificador de modelos. Ele aceita modelos e propriedades que o sistema final deve satisfazer. Então, a ferramenta gera uma resposta positiva se um dado modelo satisfaz uma dada especificação ou um contra-exemplo, em caso negativo. O contra-exemplo detalha a situação em que o modelo não foi satisfeito. Mas na maioria das vezes, problemas do mundo real não podem adotar essa abordagem porque usam domínios infinitos (levando ao problema da explosão de estados). Como forma de resolver essa questão, técnicas de abstração de dados são empregadas para gerar especificações abstratas finitas a partir de sistemas infinitos concretos. A linguagem de especificação usada nesse trabalho é CSP (Communicating Sequential Processes). Ela é uma linguagem formal que é usada para descrever padrões de interação em sistemas concorrentes. Uma das técnicas de abstração para especificações possíveis para essa linguagem é a abstração segura de dados. Essa abstração visa gerar um modelo abstrato a partir de um equivalente concreto que conserve as propriedades do sistema com respeito ao comportamento (modelo de traces) através da escolha de um dado do domínio abstrato para cada subconjunto do domínio concreto. O objetivo desse trabalho é propor um algoritmo para geração mecanizada de abstrações seguras para sistemas CSP seqüenciais com recursão simples. A especificação do algoritmo é apresentada usando o paradigma funcional e elementos da linguagem Z, com a introdução da estratégia através de exemplos. No estudo de caso, o software Mathematica é usado para instanciar os valores das variáveis e realizar a simplificação dos predicados construídos a partir desse algoritmo. Com esse trabalho, é possível gerar abstrações seguras de forma mecânica, e por conseqüência verificar o comportamento de modelos infinitos. Ademais, a geração de dados de testes automática também é beneficiada, já que com o domínio abstrato dos dados é possível percorrer todos os caminhos do sistema, gerando 100% de cobertura do modelo. Esse esforço é justificado pela importância que a fase de testes tem para a qualidade do software. Estudos prévios mostraram que essa fase demanda mais de 50% do custo de seu desenvolvimento, e uma pesquisa detalhada realizada nos Estados Unidos quantifica os altos impactos econômicos de uma infra-estrutura de software

A programação concorrente é cada vez mais utilizada nos sistemas atuais com o objetivo de reduzir custos e obter maior eficiência no processamento. Com a importância da programação concorrente é imprescindível que programas que implementam esse paradigma apresentem boa qualidade e estejam livres de defeitos. Assim,diferentes técnicas e critérios de teste vêm sendo definidos para apoiar a validação de aplicações desenvolvidas nesse paradigma. Nesse contexto, a geração automática de dados de teste é importante, pois permite reduzir o custo na geração e seleção de dados relevantes. O uso de técnicas meta-heurísticas tem sido uma área de grande interesse entre os pesquisadores para geração de dados, pois essas técnicas apresentam abordagens aplicáveis a problemas complexos e de difícil solução. Considerando esse aspecto, este trabalho apresenta uma abordagem de geração automática de dados para o teste estrutural de programas concorrentes em MPI (Message Passing Interface). A meta-heurística usada foi Algoritmo Genético em que a busca é guiada por critérios de teste que consideram características implícitas de programas concorrentes. O desempenho da abordagem foi avaliado por meio da cobertura dos dados detestes, da eficácia em revelar defeitos e do custo de execução. Para comparação, a geração aleatória foi considerada. Os resultados indicaram que é promissor usar geração de dados de teste no contexto de programas concorrentes, com resultados interessantes em relação à eficácia e cobertura dos requisitos de teste. / Concurrent programming has been increasingly used in current systems in order to reduce costs and obtain higher processing efficiency and, consequently, it is expected that these systems have high quallity. Therefore, different techniques and testing criteria have been proposed aiming to support the verification and validation of the concurrent applications. In this context, the automated data test generation allows to reduce the testing costs during the generation and selection of data tests. Metaheuristic technique has been widely investigated to support the data test generation because this technique has presented good results to complex and costly problems. In this work, we present an approach to the automated data test generation for message passing concurrent programs in MPI (Message Passing Interface). The generation of data test is performed using the genetic algorithm metaheuristic technique, guiding by structural testing criteria. An experimental study was conducted to evaluate the proposed approach, analyzing the effectiveness and application cost. The results indicate that the genetic algorithm is a promising approach to automated test data generation for concurrent programs, presenting good results in relation to effectiveness and data test coverage.

A programação concorrente é cada vez mais utilizada nos sistemas atuais com o objetivo de reduzir custos e obter maior eficiência no processamento. Com a importância da programação concorrente é imprescindível que programas que implementam esse paradigma apresentem boa qualidade e estejam livres de defeitos. Assim,diferentes técnicas e critérios de teste vêm sendo definidos para apoiar a validação de aplicações desenvolvidas nesse paradigma. Nesse contexto, a geração automática de dados de teste é importante, pois permite reduzir o custo na geração e seleção de dados relevantes. O uso de técnicas meta-heurísticas tem sido uma área de grande interesse entre os pesquisadores para geração de dados, pois essas técnicas apresentam abordagens aplicáveis a problemas complexos e de difícil solução. Considerando esse aspecto, este trabalho apresenta uma abordagem de geração automática de dados para o teste estrutural de programas concorrentes em MPI (Message Passing Interface). A meta-heurística usada foi Algoritmo Genético em que a busca é guiada por critérios de teste que consideram características implícitas de programas concorrentes. O desempenho da abordagem foi avaliado por meio da cobertura dos dados detestes, da eficácia em revelar defeitos e do custo de execução. Para comparação, a geração aleatória foi considerada. Os resultados indicaram que é promissor usar geração de dados de teste no contexto de programas concorrentes, com resultados interessantes em relação à eficácia e cobertura dos requisitos de teste. / Concurrent programming has been increasingly used in current systems in order to reduce costs and obtain higher processing efficiency and, consequently, it is expected that these systems have high quallity. Therefore, different techniques and testing criteria have been proposed aiming to support the verification and validation of the concurrent applications. In this context, the automated data test generation allows to reduce the testing costs during the generation and selection of data tests. Metaheuristic technique has been widely investigated to support the data test generation because this technique has presented good results to complex and costly problems. In this work, we present an approach to the automated data test generation for message passing concurrent programs in MPI (Message Passing Interface). The generation of data test is performed using the genetic algorithm metaheuristic technique, guiding by structural testing criteria. An experimental study was conducted to evaluate the proposed approach, analyzing the effectiveness and application cost. The results indicate that the genetic algorithm is a promising approach to automated test data generation for concurrent programs, presenting good results in relation to effectiveness and data test coverage.

O teste de mutação é um critério de teste poderoso para detectar falhas e medir a eficácia de um conjunto de dados de teste. No entanto, é uma técnica de teste computacionalmente cara. O alto custo provém principalmente do esforço para gerar dados de teste adequados para matar os mutantes e pela existência de mutantes equivalentes. Nesse contexto, o objetivo desta tese é apresentar uma abordagem chamada de Reach, Infect and Propagation to Mutation Testing (RIPMuT) que visa gerar dados de teste e sugerir mutantes equivalentes. A abordagem é composta por dois módulos: (i) uma geração automatizada de dados de teste usando subida da encosta e um esquema de fitness de acordo com as condições de alcançabilidade, infeção e propagação (RIP); e (ii) um método para sugerir mutantes equivalentes com base na análise das condições RIP durante o processo de geração de dados de teste. Os experimentos foram conduzidos para avaliar a eficácia da abordagem RIP-MuT e um estudo comparativo com o algoritmo genético e testes aleatórios foi realizado. A abordagem RIP-MuT obteve um escore médio de mutação de 18,25 % maior que o AG e 35,93 % maior que o teste aleatório. O método proposto para detecção de mutantes equivalentes se mostrou viável para redução de custos relacionado a essa atividade, uma vez que obteve uma precisão de 75,05% na sugestão dos mutantes equivalentes. Portanto, os resultados indicam que a abordagem gera dados de teste adequados capazes de matar a maioria dos mutantes em programas C e, também auxilia a identificar mutantes equivalentes corretamente. / Mutation Testing is a powerful test criterion to detect faults and measure the effectiveness of a test data set. However, it is a computationally expensive testing technique. The high cost comes mainly from the effort to generate adequate test data to kill the mutants and by the existence of equivalent mutants. In this thesis, an approach called Reach, Infect and Propagation to Mutation Testing (RIP-MuT) is presented to generate test data and to suggest equivalent mutants. The approach is composed of two modules: (i) an automated test data generation using hill climbing and a fitness scheme according to Reach, Infect, and Propagate (RIP) conditions; and (ii) a method to suggest equivalent mutants based on the analyses of RIP conditions during the process of test data generation. The experiments were conducted to evaluate the effectiveness of the RIP-MuT approach and a comparative study with a genetic algorithm and random testing. The RIP-MuT approach achieved a mean mutation score of 18.25% higher than the GA and 35.93% higher than random testing. The proposed method for detection of equivalent mutants demonstrate to be feasible for cost reduction in this activity since it obtained a precision of 75.05% on suggesting equivalent mutants. Therefore, the results indicate that the approach produces effective test data able to strongly kill the majority of mutants on C programs, and also it can assist in suggesting equivalent mutants correctly.

O teste de mutação é um critério de teste poderoso para detectar falhas e medir a eficácia de um conjunto de dados de teste. No entanto, é uma técnica de teste computacionalmente cara. O alto custo provém principalmente do esforço para gerar dados de teste adequados para matar os mutantes e pela existência de mutantes equivalentes. Nesse contexto, o objetivo desta tese é apresentar uma abordagem chamada de Reach, Infect and Propagation to Mutation Testing (RIPMuT) que visa gerar dados de teste e sugerir mutantes equivalentes. A abordagem é composta por dois módulos: (i) uma geração automatizada de dados de teste usando subida da encosta e um esquema de fitness de acordo com as condições de alcançabilidade, infeção e propagação (RIP); e (ii) um método para sugerir mutantes equivalentes com base na análise das condições RIP durante o processo de geração de dados de teste. Os experimentos foram conduzidos para avaliar a eficácia da abordagem RIP-MuT e um estudo comparativo com o algoritmo genético e testes aleatórios foi realizado. A abordagem RIP-MuT obteve um escore médio de mutação de 18,25 % maior que o AG e 35,93 % maior que o teste aleatório. O método proposto para detecção de mutantes equivalentes se mostrou viável para redução de custos relacionado a essa atividade, uma vez que obteve uma precisão de 75,05% na sugestão dos mutantes equivalentes. Portanto, os resultados indicam que a abordagem gera dados de teste adequados capazes de matar a maioria dos mutantes em programas C e, também auxilia a identificar mutantes equivalentes corretamente. / Mutation Testing is a powerful test criterion to detect faults and measure the effectiveness of a test data set. However, it is a computationally expensive testing technique. The high cost comes mainly from the effort to generate adequate test data to kill the mutants and by the existence of equivalent mutants. In this thesis, an approach called Reach, Infect and Propagation to Mutation Testing (RIP-MuT) is presented to generate test data and to suggest equivalent mutants. The approach is composed of two modules: (i) an automated test data generation using hill climbing and a fitness scheme according to Reach, Infect, and Propagate (RIP) conditions; and (ii) a method to suggest equivalent mutants based on the analyses of RIP conditions during the process of test data generation. The experiments were conducted to evaluate the effectiveness of the RIP-MuT approach and a comparative study with a genetic algorithm and random testing. The RIP-MuT approach achieved a mean mutation score of 18.25% higher than the GA and 35.93% higher than random testing. The proposed method for detection of equivalent mutants demonstrate to be feasible for cost reduction in this activity since it obtained a precision of 75.05% on suggesting equivalent mutants. Therefore, the results indicate that the approach produces effective test data able to strongly kill the majority of mutants on C programs, and also it can assist in suggesting equivalent mutants correctly.

As atividades de teste de software são de crescente importância devido à maciça presença de sistemas de informação em nosso cotidiano. Programas de Processamento de Imagens (PI) têm um domínio de entrada bastante complexo e, por essa razão, o teste tradicional realizado com esse tipo de programa, conduzido majoritariamente de forma manual, é uma tarefa de alto custo e sujeita a imperfeições. No teste tradicional, em geral, as imagens de entrada são construídas manualmente pelo testador ou selecionadas aleatoriamente de bases de imagens, muitas vezes dificultando a revelação de defeitos no software. A partir de um mapeamento sistemático da literatura realizado, foi identificada uma lacuna no que se refere à geração automatizada de dados de teste no domínio de imagens. Assim, o objetivo desta pesquisa é propor uma abordagem - denominada TAIGA (Test imAge generatIon by Genetic Algorithm) - para a geração de dados de teste para programas de PI por meio de algoritmo genético. Na abordagem proposta, operadores genéticos tradicionais (mutação e crossover) são adaptados para o domínio de imagens e a função fitness é substituída por uma avaliação de resultados provenientes de teste de mutação. A abordagem TAIGA foi validada por meio de experimentos com oito programas de PI distintos, nos quais observaram-se ganhos de até 38,61% em termos de mutation score em comparação ao teste tradicional. Ao automatizar a geração de dados de teste, espera-se conferir maior qualidade ao desenvolvimento de sistemas de PI e contribuir com a diminuição de custos com as atividades de teste de software neste domínio / The massive presence of information systems in our lives has been increasing the importance of software test activities. Image Processing (IP) programs have very complex input domains and, therefore, the traditional testing for this kind of program is a highly costly and vulnerable to errors task. In traditional testing, usually, testers create images by themselves or they execute random selection from images databases, which can make it harder to reveal faults in the software under test. In this context, a systematic mapping study was conducted and a gap was identified concerning the automated test data generation in the images domain. Thus, an approach for generating test data for IP programs by means of genetic algorithms was proposed: TAIGA - Test imAge generatIon by Genetic Algorithm. This approach adapts traditional genetic operators (mutation and crossover) to the images domain and replaces the fitness function by the evaluation of the results of mutation testing. The proposed approach was validated by the execution of experiments involving eight distinct IP programs. TAIGA was able to provide up to 38.61% increase in mutation score when compared to the traditional testing for IP programs. It\'s expected that the automation of test data generation elevates the quality of image processing systems development and reduces the costs of software test activities in the images domain

Veículo autônomo inteligente (ou apenas veículo autônomo VA) é um tipo de sistema embarcado que integra componentes físicos (hardware) e computacionais (software). Sua principal característica é a capacidade de locomoção e de operação de modo semi ou completamente autônomo. A autonomia cresce com a capacidade de percepção e de deslocamento no ambiente, robustez e capacidade de resolver e executar tarefas lidando com as mais diversas situações (inteligência). Veículos autônomos representam um tópico de pesquisa importante e que tem impacto direto na sociedade. No entanto, à medida que esse campo avança alguns problemas secundários aparecem como, por exemplo, como saber se esses sistemas foram suficientemente testados. Uma das fases do teste de um VA é o teste de campo, em que o veículo é levado para um ambiente pouco controlado e deve executar livremente a missão para a qual foi programado. Ele é geralmente utilizado para garantir que os veículos autônomos mostrem o comportamento desejado, mas nenhuma informação sobre a estrutura do código é utilizada. Pode ocorrer que o veículo (hardware e software) passou no teste de campo, mas trechos importantes do código nunca tenham sido executados. Durante o teste de campo, os dados de entrada são coletados em logs que podem ser posteriormente analisados para avaliar os resultados do teste e para realizar outros tipos de teste offline. Esta tese apresenta um conjunto de propostas para apoiar a análise do teste de campo do ponto de vista do teste estrutural. A abordagem é composta por um modelo de classes no contexto do teste de campo, uma ferramenta que implementa esse modelo e um algoritmo genético para geração de dados de teste. Apresenta também heurísticas para reduzir o conjunto de dados contidos em um log sem diminuir substancialmente a cobertura obtida e estratégias de combinação e mutação que são usadas no algoritmo. Estudos de caso foram conduzidos para avaliar as heurísticas e estratégias e são também apresentados e discutidos. / Intelligent autonomous vehicle (or just autonomous vehicle - AV) is a type of embedded system that integrates physical (hardware) and computational (software) components. Its main feature is the ability to move and operate partially or fully autonomously. Autonomy grows with the ability to perceive and move within the environment, robustness and ability to solve and perform tasks dealing with different situations (intelligence). Autonomous vehicles represent an important research topic that has a direct impact on society. However, as this field progresses some secondary problems arise, such as how to know if these systems have been sufficiently tested. One of the testing phases of an AV is the field testing, where the vehicle is taken to a controlled environment and it should execute the mission for which it was programed freely. It is generally used to ensure that autonomous vehicles show the intended behavior, but it usually does not take into consideration the code structure. The vehicle (hardware and software) could pass the field testing, but important parts of the code may never have been executed. During the field testing, the input data are collected in logs that can be further analyzed to evaluate the test results and to perform other types of offline tests. This thesis presents a set of proposals to support the analysis of field testing from the point of view of the structural testing. The approach is composed of a class model in the context of the field testing, a tool that implements this model and a genetic algorithm to generate test data. It also shows heuristics to reduce the data set contained in a log without reducing substantially the coverage obtained and combination and mutation strategies that are used in the algorithm. Case studies have been conducted to evaluate the heuristics and strategies, and are also presented and discussed.

As atividades de teste de software são de crescente importância devido à maciça presença de sistemas de informação em nosso cotidiano. Programas de Processamento de Imagens (PI) têm um domínio de entrada bastante complexo e, por essa razão, o teste tradicional realizado com esse tipo de programa, conduzido majoritariamente de forma manual, é uma tarefa de alto custo e sujeita a imperfeições. No teste tradicional, em geral, as imagens de entrada são construídas manualmente pelo testador ou selecionadas aleatoriamente de bases de imagens, muitas vezes dificultando a revelação de defeitos no software. A partir de um mapeamento sistemático da literatura realizado, foi identificada uma lacuna no que se refere à geração automatizada de dados de teste no domínio de imagens. Assim, o objetivo desta pesquisa é propor uma abordagem - denominada TAIGA (Test imAge generatIon by Genetic Algorithm) - para a geração de dados de teste para programas de PI por meio de algoritmo genético. Na abordagem proposta, operadores genéticos tradicionais (mutação e crossover) são adaptados para o domínio de imagens e a função fitness é substituída por uma avaliação de resultados provenientes de teste de mutação. A abordagem TAIGA foi validada por meio de experimentos com oito programas de PI distintos, nos quais observaram-se ganhos de até 38,61% em termos de mutation score em comparação ao teste tradicional. Ao automatizar a geração de dados de teste, espera-se conferir maior qualidade ao desenvolvimento de sistemas de PI e contribuir com a diminuição de custos com as atividades de teste de software neste domínio / The massive presence of information systems in our lives has been increasing the importance of software test activities. Image Processing (IP) programs have very complex input domains and, therefore, the traditional testing for this kind of program is a highly costly and vulnerable to errors task. In traditional testing, usually, testers create images by themselves or they execute random selection from images databases, which can make it harder to reveal faults in the software under test. In this context, a systematic mapping study was conducted and a gap was identified concerning the automated test data generation in the images domain. Thus, an approach for generating test data for IP programs by means of genetic algorithms was proposed: TAIGA - Test imAge generatIon by Genetic Algorithm. This approach adapts traditional genetic operators (mutation and crossover) to the images domain and replaces the fitness function by the evaluation of the results of mutation testing. The proposed approach was validated by the execution of experiments involving eight distinct IP programs. TAIGA was able to provide up to 38.61% increase in mutation score when compared to the traditional testing for IP programs. It\'s expected that the automation of test data generation elevates the quality of image processing systems development and reduces the costs of software test activities in the images domain

Veículo autônomo inteligente (ou apenas veículo autônomo VA) é um tipo de sistema embarcado que integra componentes físicos (hardware) e computacionais (software). Sua principal característica é a capacidade de locomoção e de operação de modo semi ou completamente autônomo. A autonomia cresce com a capacidade de percepção e de deslocamento no ambiente, robustez e capacidade de resolver e executar tarefas lidando com as mais diversas situações (inteligência). Veículos autônomos representam um tópico de pesquisa importante e que tem impacto direto na sociedade. No entanto, à medida que esse campo avança alguns problemas secundários aparecem como, por exemplo, como saber se esses sistemas foram suficientemente testados. Uma das fases do teste de um VA é o teste de campo, em que o veículo é levado para um ambiente pouco controlado e deve executar livremente a missão para a qual foi programado. Ele é geralmente utilizado para garantir que os veículos autônomos mostrem o comportamento desejado, mas nenhuma informação sobre a estrutura do código é utilizada. Pode ocorrer que o veículo (hardware e software) passou no teste de campo, mas trechos importantes do código nunca tenham sido executados. Durante o teste de campo, os dados de entrada são coletados em logs que podem ser posteriormente analisados para avaliar os resultados do teste e para realizar outros tipos de teste offline. Esta tese apresenta um conjunto de propostas para apoiar a análise do teste de campo do ponto de vista do teste estrutural. A abordagem é composta por um modelo de classes no contexto do teste de campo, uma ferramenta que implementa esse modelo e um algoritmo genético para geração de dados de teste. Apresenta também heurísticas para reduzir o conjunto de dados contidos em um log sem diminuir substancialmente a cobertura obtida e estratégias de combinação e mutação que são usadas no algoritmo. Estudos de caso foram conduzidos para avaliar as heurísticas e estratégias e são também apresentados e discutidos. / Intelligent autonomous vehicle (or just autonomous vehicle - AV) is a type of embedded system that integrates physical (hardware) and computational (software) components. Its main feature is the ability to move and operate partially or fully autonomously. Autonomy grows with the ability to perceive and move within the environment, robustness and ability to solve and perform tasks dealing with different situations (intelligence). Autonomous vehicles represent an important research topic that has a direct impact on society. However, as this field progresses some secondary problems arise, such as how to know if these systems have been sufficiently tested. One of the testing phases of an AV is the field testing, where the vehicle is taken to a controlled environment and it should execute the mission for which it was programed freely. It is generally used to ensure that autonomous vehicles show the intended behavior, but it usually does not take into consideration the code structure. The vehicle (hardware and software) could pass the field testing, but important parts of the code may never have been executed. During the field testing, the input data are collected in logs that can be further analyzed to evaluate the test results and to perform other types of offline tests. This thesis presents a set of proposals to support the analysis of field testing from the point of view of the structural testing. The approach is composed of a class model in the context of the field testing, a tool that implements this model and a genetic algorithm to generate test data. It also shows heuristics to reduce the data set contained in a log without reducing substantially the coverage obtained and combination and mutation strategies that are used in the algorithm. Case studies have been conducted to evaluate the heuristics and strategies, and are also presented and discussed.