No description available.

Recently, covering arrays have been the subject of considerable research attention as they hold both theoretical interest and practical importance due to their applications to testing. In this thesis, we perform the first comprehensive study of a generalization of covering arrays called variable strength covering arrays, where we dictate the interactions to be covered in the array by modeling them as facets of an abstract simplicial complex. We outline the necessary background in the theory of hypergraphs, combinatorial testing, and design theory that is relevant to the study of variable strength covering arrays. We then approach questions that arise in variable strength covering arrays in a number of ways. We demonstrate their connections to hypergraph homomorphisms, and explore the properties of a particular family of abstract simplicial complexes, the qualitative independence hypergraphs. These hypergraphs are tightly linked to variable strength covering arrays, and we determine and identify several of their important properties and subhypergraphs. We give a detailed study of constructions for variable strength covering arrays, and provide several operations and divide-and-conquer techniques that can be used in building them. In addition, we give a construction using linear feedback shift registers from primitive polynomials of degree 3 over arbitrary finite fields to find variable strength covering arrays, which we extend to strength-3 covering arrays whose sizes are smaller than many of the best known sizes of covering arrays. We then give an algorithm for creating variable strength covering arrays over arbitrary abstract simplicial complexes, which builds the arrays one row at a time, using a density concept to guarantee that the size of the resultant array is asymptotic in the logarithm of the number of facets in the abstact simplicial complex. This algorithm is of immediate practical importance, as it can be used to create test suites for combinatorial testing. Finally, we use the Lovasz Local Lemma to nonconstructively determine upper bounds on the sizes of arrays for a number of different families of hypergraphs. We lay out a framework that can be used for many hypergraphs, and then discuss possible strategies that can be taken in asymmetric problems.

Testing every possible combination of the input parameter values is often impractical, inefficient or too expensive. One common alternative is pairwise testing where every pairwise combination of the parameter values is tested. Although pairwise testing significantly reduces the number of test cases, the challenge remains in analyzing the test outputs to discern the precise characteristics of parameters causing the failures. This thesis proposes a novel approach to output analysis by identifying “bad pairs”: pairs that always result in failed test cases. A framework implementing the proposed approach is presented together with three case studies. Results from the case studies suggest there are positive relationships among the numbers of failed test cases, faults, and independent bad pairs. Also, filtering of test cases seems to have a significant impact on the bad pairs identified. We believe the proposed approach can facilitate the debugging process in software testing.

Made available in DSpace on 2014-12-17T15:48:09Z (GMT). No. of bitstreams: 1 VivianeMR_DISSERT.pdf: 1295596 bytes, checksum: 1bb5688145cd1ce7005121d9de48c246 (MD5) Previous issue date: 2013-12-13 / The work proposed by Cleverton Hentz (2010) presented an approach to define tests from the formal description of a program s input. Since some programs, such as compilers, may have their inputs formalized through grammars, it is common to use context-free grammars to specify the set of its valid entries. In the original work the author developed a tool that automatically generates tests for compilers. In the present work we identify types of problems in various areas where grammars are used to describe them , for example, to specify software configurations, which are potential situations to use LGen. In addition, we conducted case studies with grammars of different domains and from these studies it was possible to evaluate the behavior and performance of LGen during the generation of sentences, evaluating aspects such as execution time, number of generated sentences and satisfaction of coverage criteria available in LGen / O trabalho proposto por Cleverton Hentz (2010) apresentou uma abordagem para defini??o de testes a partir da descri??o formal das entradas do programa. Considerando que alguns programas podem ter suas entradas formalizadas atrav?s de gram?ticas, como ? o caso dos compiladores, ? comum o uso de gram?ticas livres de contexto para especificar o conjunto de entradas v?lidas. No trabalho original foi desenvolvida LGen, uma ferramenta que consiste na gera??o autom?tica de testes para compiladores. No presente trabalho identificamos tipos de problemas recorrentes em diferentes ?reas, onde gram?ticas s?o usadas para descrev?-los, como por exemplo, para especificar configura??es de software, e que s?o situa??es potenciais para o uso de LGen. Al?m disso, realizamos estudos de caso com gram?ticas de dom?nios diferentes e a partir destes estudos foi poss?vel avaliar o comportamento e o desempenho de LGen durante o processo de gera??o das senten?as, avaliando aspectos como tempo de execu??o, quantidade de senten?as geradas e satisfa??o de crit?rios de cobertura dispon?veis em LGen

Obtaining an accurate whole program path (WPP) that captures a program’s runtime behaviour in terms of a control-flow trace has a number of well-known benefits, including opportunities for code optimization, bug detection, program analysis refinement, etc. Existing techniques to compute WPPs perform sub-optimal instrumentation resulting in significant space and time overheads. Our goal in this thesis is to minimize these overheads without losing precision. To do so, we design a novel and scalable whole program analysis to determine instrumentation points used to obtain WPPs. Our approach is divided into three components: (a) an efficient summarization technique for inter-procedural path reconstruction, (b) specialized data structures called conflict sets that serve to effectively distinguish between pairs of paths, and (c) an instrumentation algorithm that computes the minimum number of edges to describe a path based on these conflict sets. We show that the overall problem is a variant of the minimum hitting set problem, which is NP-hard, and employ various sound approximation strategies to yield a practical solution. We have implemented our approach and performed elaborate experimentation on Java programs from the DaCapo benchmark suite to demonstrate the efficacy of our approach across multiple dimensions. On average, our approach necessitates instrumenting only 9% of the total number of CFG edges in the program. The average runtime overhead incurred by our approach to collect WPPs is 1.97x, which is only 26% greater than the overhead induced by only instrumenting edges guaranteed to exist in an optimal solution. Furthermore, compared to the state-of-the-art, we observe a reduction in runtime overhead by an average and maximum factor of 2.8 and 5.4, respectively.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-13T17:20:26Z No. of bitstreams: 1 AYLA DEBORA DANTAS DE SOUZA REBOUÇAS - TESE PPGCC 2010..pdf: 2130099 bytes, checksum: 004385606718ac74b12c8332e37b890c (MD5) / Made available in DSpace on 2018-08-13T17:20:26Z (GMT). No. of bitstreams: 1 AYLA DEBORA DANTAS DE SOUZA REBOUÇAS - TESE PPGCC 2010..pdf: 2130099 bytes, checksum: 004385606718ac74b12c8332e37b890c (MD5) Previous issue date: 2010-08-30 / CNPq / Testar sistemas com múltiplas threads é uma atividade que envolve vários desafios. O fato de serem inerentemente não determinísticos torna tanto a implementação desses sistemas quanto a implementação de seus testes suscetível a erros. É comum existirem testes nestes sistemas que falham em apenas algumas execuções, sem que as causas dessas falhas sejam faltas na aplicação (também conhecidas como defeitos oubugs), mas sim devido a problemas nos testes. Por exemplo, isso pode acontecer se a fase dos testes em que são feitas as verificações (asserções) for executada em momentos inadequados. Isso é freqüente quando os testes envolvem operações assíncronas. Deve-se evitar que nestes testes as asserções sejam feitas antes que essas operações tenham sido concluídas ou também que sejam feitas em um momento tardio, quando o sistema mudou de estado e as condições verificadas não são mais satisfeitas, gerando assim falsos positivos. Testes que não são confiáveis, como os que falham devido a tais problemas, levam os desenvolvedores a desperdiçar muito tempo procurando faltas de software que não existem. Além disso, os desenvolvedores podem perder a confiança nos testes parando de acreditar que falhas em certos testes são devidas a faltas, mesmo quando este é o caso. A existência de tais cenários foi o que motivou este trabalho, que tem como objetivo evitar que asserções em testes sejam feitas cedo ou tarde demais. Para atingir esse objetivo, apresenta-se uma abordagem baseada na monitoração e controle das threads daaplicação e quedê suporte ao desenvolvimento de testes corretos de sistemas multi-threaded. A abordagem visa facilitar a implementação de testes envolvendo operações assíncronas e aumentar a confiança dos desenvolvedores nos seus resultados. Esta abordagem foi avaliada através de estudos de caso utilizando uma ferramenta de suporte ao teste de sistemas multi-threaded, desenvolvida para este trabalho, e também através de sua modelagem formal utilizando a linguagem TLA+, com o objetivo de demonstrar que asserções antecipadas e tardias não ocorrem quando ela é utilizada. / Testing multi-threaded systems is quite a challenge. The inherent non-determinism of these systems makes their implementation and the implementation of their tests far more susceptible to error. It is common to have tests of these systems that may not sometimes pass and whose failures are not caused by application faults (bugs), but by problems with the tests. For instance, thiscan happen when there are asynchronous operations whose corresponding test verifications (assertions) are performed at inappropriate times. Unreliable tests make developers waste their time trying to find non-existing bugs, or else make them search for bugs in the wrong place. Another problem is that developers may cease to believe that certain test failures are caused by software bugs even when this is the case. Scenarios like these have motivated this work. Our main objective is to avoid test failures that are caused, not by application defects, but by test assertions performed either too early or too late. In order to achieve this goal, we present an approach whose basic idea is to use thread monitoring and control in order to support the development of multi-threaded systems tests involving asynchronous operations. This approach is intended to make it easier the development of correct tests for these systems and also to improve developers’ confidence on the results of their tests. The proposed approach has been evaluated through case studies using a tool to support the development of multi-threaded systems tests (developed for this work) and also by formally modeling the approach using theTLA+ language in order to prove that early and late assertions do not occur when this approach isused.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-31T23:21:36Z No. of bitstreams: 1 MELINA MANGIOVI CUNHA LIMA SABINO - PPGCC DISSERTAÇÃO 2013..pdf: 29220438 bytes, checksum: 42486beccb60e73d444ba221ab430942 (MD5) / Made available in DSpace on 2018-08-31T23:21:36Z (GMT). No. of bitstreams: 1 MELINA MANGIOVI CUNHA LIMA SABINO - PPGCC DISSERTAÇÃO 2013..pdf: 29220438 bytes, checksum: 42486beccb60e73d444ba221ab430942 (MD5) Previous issue date: 2013-03-11 / CNPq / Refatoramentos são transformações que melhoram a estrutura interna do programa preservando seu comportamento observável. Na prática, desenvolvedores utilizam testes de regressão e ferramentas para garantir que o refatoramento preservou o comportamento do programa. Entretanto, ferramentas de refatoramentos possuem bugs. Além disso, a coleção de testes pode ser modificada pela transformação aplicada manualmente ou pela ferramenta. Se a transformação não for aplicada corretamente, esta pode modificar a coleção de testes incapacitando-a de detectar a mudança comportamental. Por fim, a coleção pode não ser adequada para testar a transformação, pois os casos de testes podem não exercitar as entidades impactadas pela transformação. Este problema se torna maior se a coleção de testes for grande, tornando a execução de toda a coleção de testes custosa. Nós propomos uma abordagem para avaliar preservação de comportamento em refatoramentos baseada em geração automática de testes e análise de impacto da mudança. A abordagem analisa o impacto da mudança e gera automaticamente testes apenas para os métodos impactados pela transformação. Implementamos uma ferramenta chamada SafeRefactorlmpact para avaliar a preservação de comportamento. Esta utiliza Safira, ferramenta que implementamos para realizar a análise de impacto. Avaliamos SafeRefactorlmpact em um conjunto de 10 transformações aplicadas a um sistema real, e em uma técnica para testar implementações de refatoramentos. Além disso, comparamos SafeRefactorlmpact com SafeRefactor, uma ferramenta que também avalia preservação de comportamento em refatoramentos mas não utiliza análise de impacto. Nós comparamos com relação às mudanças comportamentais identificadas, quantidade de métodos identificados para geração de testes, tempo total da análise da transformação, quantidade de casos de testes gerados e cobertura da mudança dos testes gerados. O SafeRefactorlmpact conseguiu identificar mudanças comportamentais não identificadas pelo SafeRefactor, reduziu em torno de 60% o tempo para testar implementações de refatoramentos, mostrou-se menos sensível ao tempo limite passado para o gerador automático de testes, além da análise de impacto permitir a diminuição de algumas limitações do gerador automático de testes enfrentadas pelo SafeRefactor. / Refactorings are transformations that improve the internal structure of the program while preserving its observable behavior. In practice, developers use regression tests and refactoring tools to ensure that the refactoring has preserved the behavior of the program. However, refactoring tools may have bugs. In addition, the test suite may be modified by the transformation applied manually or using a refactoring tool. If the transformation is applied incorrectly, it can change the test suite by disabling it to detect the behavioral change. Finally, the test suite may be inappropriate to test the transformation because the test cases may not exercise the change. This problem can get worse if the test suite is large. This way, it is time consuming executing the entire test suite. We propose an approach for evaluating whether a transformation is behavior preserving based on change impact analysis. This approach performs a change impact analysis and it automatically generates tests only to the methods impacted by the transformation. We implemented a tool called SafeRefactorlmpact to evaluate behavior preservation. It uses Safira, a tool that we implemented to identify the methods impacted by a change in the program. We evaluate SafeRefactorlmpact in a set of 10 transformations applied to a real system and to a technique to test refactoring implementations. Moreover, we compared the SafeRefactorlmpact with SafeRefactor, a tool that also evaluates whether a transformation preserves the program behavior. The difference is that SafeRefactor does not use the impact analysis. The SafeRefactorlmpact managed to identify behavioral changes not identified by SafeRefactor; it reduced in 60% the total time to analyze the refactoring implementations; it showed to be less sensitive to the time limit to generate the tests; and the impact analysis allows the reduction of some limitations of the automatic tests generator faced by the SafeRefactor.

[pt] Teste é uma etapa muito importante no desenvolvimento de software. No entanto, essa área ainda carece de ferramentas mais eficazes e com um grau de automação maior e mais abrangente do que o atualmente disponível. Uma boa parte das técnicas de geração de casos de teste utiliza explicitamente ou implicitamente tabelas de decisão como instrumento intermediário na geração dos casos de teste específicos. Essa dissertação tem por objetivo desenvolver um processo semi-automático de geração de suítes de teste e que inicia em tabelas de decisão. As suítes geradas devem ser adequadas a ferramentas de execução dos testes totalmente automáticas. Para atingir esse objetivo foram implementados: (i) um editor de tabelas de decisão, (ii) um gerador automático de casos de teste e (iii) um gerador de scripts de teste para o framework FEST. A seguir foram avaliados os benefícios que esse conjunto de ferramentas pode trazer ao processo de automação dos testes, tanto no planejamento (geração de casos de testes valorados a partir dos casos de teste semânticos) quanto na execução dos casos de teste. A avaliação foi baseada em uma série de exemplos envolvendo elementos específicos de interfaces humanas, e, também, na aplicação a um software real. / [en] Testing is a very important area in the software development. However, this area needs more effective tools with a higher level of automation with are more comprehensive than the tools available today. A large part of the techniques that do generation of test cases use explicity or implicitly decision tables as an auxiliary tool. This dissertation aims to develop a semi-automatic process that has as outputs tests suites that were generated using decision tables. These suites must be appropriate for the test automation tools. To achieve these goals were implemented: (i) an decision table editor, (ii) a automatic generator case test, and (iii) an automatic test scripts generator of the FEST framework. After it was necessary evaluate the benefits that these tools could bring for the test area, both in the planning (generation of valued test cases from semantic test cases) and in the execution of test cases. The evaluation was based on a series of examples involving specific elements of human interfaces, and also in application to real software.

SANTOS, Ismayle de Sousa. Um ambiente para geração de cenários de testes para linhas de produtos de software sensíveis ao contexto. 2013. 135 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T19:23:59Z No. of bitstreams: 1 2013_dis_issantos.pdf: 3899116 bytes, checksum: 671b1907d9f723390441a5b8ed58142c (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T19:25:01Z (GMT) No. of bitstreams: 1 2013_dis_issantos.pdf: 3899116 bytes, checksum: 671b1907d9f723390441a5b8ed58142c (MD5) / Made available in DSpace on 2016-07-01T19:25:01Z (GMT). No. of bitstreams: 1 2013_dis_issantos.pdf: 3899116 bytes, checksum: 671b1907d9f723390441a5b8ed58142c (MD5) Previous issue date: 2013 / A Context-Aware Software Product Line (CASPL) is a product line for developing context-aware applications, which dynamically change their behavior or provide services based on context information. With this kind of line, the productivity can be increased and the development costs of the context-aware application can be cut down. In this scenario, the testing activity needs to deal with the peculiarities of both context-aware applications and the product line development paradigm. Through the complexity involved in testing a CASPL is essential to have methods or tools for supporting this activity, especially with the goal of creating tests from requirements. The aim of this early testing generation is to identify and fix the defects in the early stages of development. Therefore, this work aims to propose an environment for generating test scenarios for a CASPL that takes into account the presence of context information and seeks to maximize the testing reuse. This environment consists of a testing scenario generation method, a template for textual use case specification and a support tool. The method uses as input textual use cases especifications with information about: funcionality, variability, and how the context afect the final products. The environment also has a use case template that supports the use of the method and a tool support, which allows the modeling of use cases according to this template and implements the proposed method. In order to verify the benefits of the environment as a way to testing generation for a Context-Aware Software Product Line, an assessment in the form of controlled experiment is conducted. Based on the collected results, it is observed that: the use of the template makes easy the understanding of a Context-Aware Software Product Line use case; the method favors the creation of a set of tests with higher coverage than a non-systematic testing generation; and the tool is the necessary support for the method / Uma Linha de Produto de Software Sensível ao Contexto (LPSSC) é uma linha de produto para o desenvolvimento de aplicações sensíveis ao contexto, que alteram dinamicamente o comportamento ou que proveem serviços com base em informações de contexto. Nesse cenário, a atividade de testes precisa lidar ao mesmo tempo com as peculiaridades das aplicações finais, que são sensíveis ao contexto, e com o paradigma de desenvolvimento em linha de produto. Mediante a complexidade envolvida nos testes de uma LPSSC, é fundamental a existência de métodos ou ferramentas de suporte a essa atividade, especialmente com a intenção de criar testes a partir dos requisitos da linha. O objetivo dessa geração precoce dos testes é permitir a identificação e correção dos defeitos nos estágios iniciais de desenvolvimento. Dessa forma, esta dissertação tem por objetivo propor um ambiente de geração de cenários de testes para uma LPSSC que utiliza especificações textuais de casos de uso com informações de contexto e que possibilita a reutilização dos testes. Este ambiente é constituído pela proposta de um método de geração de cenários de testes, de um template para especificação textual de casos de uso de uma LPSSC e de uma ferramenta de apoio. O método utiliza como base especificações textuais de casos de uso com informações sobre: funcionalidade, variabilidade da linha, e como o contexto afeta os produtos finais. O ambiente também contém o template para caso de uso que fornece suporte ao uso do método e a ferramenta de apoio, que permite a modelagem de casos de uso segundo esse template e implementa o método proposto. Com a intenção de verificar os benefícios do ambiente, proposto nesta dissertação, quanto a geração de cenários de testes para uma LPSSC, conduziu-se uma avaliação preliminar na forma de experimento controlado. Baseado nos resultados coletados nessa avaliação percebeu-se que: o template favorece o entendimento de um caso de uso de uma LPSSC; o método favorece a criação de um conjunto de testes com uma maior cobertura para uma LPSSC, se comparado a criação de testes de forma não sistemática; e a ferramenta representa um suporte necessário.

Sistemas embarcados estão mais complexos e são cada vez mais utilizados em contextos que exigem muitos recursos computacionais. Isso significa que o hardware embarcado pode ser composto por vários processadores, memórias, partes reconfiguráveis e ASIPs integrados em um único silício. Adicionalmente, o software embarcados pode conter muitas rotinas de programação executadas sob restrição de processamento e memória. Esse cenário estabelece uma forte dependência entre o hardware e o software embarcado. Portanto, o teste de um sistema embarcado compreende o teste do hardware e do software. Neste contexto, a reutilização de procedimentos e estruturas de teste é um caminho para se reduzir o tempo de desenvolvimento e execução dos testes. Neste trabalho é apresentado um método de teste integrado de hardware e software. Nesse método, casos de teste desenvolvidos para testar o software embarcado também são usados para testar o seu processador. Comparou-se os custos e cobertura de falhas do método proposto com técnicas de auto-teste funcional. Os resultados experimentais demonstraram que foi possível reduzir os custos de aplicação e geração do teste do sistema usando um método de teste integrado de software e hardware. / Embedded Systems are more complexity. Nowadays, they are used in context that requires computational resources. This means an embedded hardware may be compound of several processors, memories, reconfigurable parts, and ASICs integrated in a single die. Additionally, an embedded software has a lot of programming procedures, which is under processing and memory constraints. This scenario provides a stronger connection between hardware and software. Therefore, the test of an embedded system is the test of both, hardware and software. In this context, reuse of testing structures and procedures is one way to reduce the test development time and execution. This work presents an integrated test of software and software method. In this method, test cases developed to test the embedded software are also used to test its processor. We compared the costs and fault coverage of our proposed method with techniques of functional self-test. The experimental results show that it is possible to reduce the implementation and test generation costs using an integrated test of software and hardware.