Software testing is the most commonly used methodology for validating quality of software systems. Conceptually, testing is simple, but in practice, given the huge (practically infinite) space of inputs to test against, it requires solving a number of challenging problems, including evaluating and reusing tests efficiently and effectively as software evolves. While software testing research has seen much progress in recent years, many crucial bugs still evade state-of-the-art approaches and cause significant monetary losses and sometimes are responsible for loss of life. My thesis is that a unified, bi-dimensional, change-driven methodology can form the basis of novel techniques and tools that can make testing significantly more effective and efficient, and allow us to find more bugs at a reduced cost. We propose a novel unification of the following two dimensions of change: (1) real manual changes made by programmers, e.g., as commonly used to support more effective and efficient regression testing techniques; and (2) mechanically introduced changes to code or specifications, e.g., as originally conceived in mutation testing for evaluating quality of test suites. We believe such unification can lay the foundation of a scalable and highly effective methodology for testing and maintaining real software systems. The primary contribution of my thesis is two-fold. One, it introduces new techniques to address central problems in both regression testing (e.g., test prioritization) and mutation testing (e.g., selective mutation testing). Two, it introduces a new methodology that uses the foundations of regression testing to speed up mutation testing, and also uses the foundations of mutation testing to help with the fault localization problem raised in regression testing. The central ideas are embodied in a suite of prototype tools. Rigorous experimental evaluation is used to validate the efficacy of the proposed techniques using a variety of real-world Java programs. / text

Mutation testing and adequacy testing are two major technologies to assure the quality of software. In this thesis, we present the first work that alleviates the high cost of mutation testing and ineffectiveness of adequacy testing for context-aware applications. We also present large-scale multi-subject case studies to evaluate how our work successfully alleviates these problems. Mutation testing incurs a high execution cost if randomly selected test inputs kill a small percentage of remaining live mutants. To address this problem, we formulate the notion of context diversity to measure the context changes inherent in test inputs, and propose three context-aware strategies in the selection of test inputs. The empirical results show that the use of test inputs with higher context diversity can significantly benefit mutation testing in terms of resulting in fewer test runs, fewer test case trials, and smaller resultant test suites that achieve a high mutation score level. The case study also shows that at the test case level, the context diversity of test inputs positively and strongly correlates with multiple types of adequacy metrics, which provide a foundation on why context diversity contributes to the effectiveness of test cases in revealing faults in context-aware applications. In adequacy testing, many strategies randomly select test cases to construct adequate test suites with respect to program-based adequacy criteria. They usually exclude redundant test cases that are unable to improve the coverage of the test requirements of an adequacy criterion achieved by constructing test suites. These strategies have not explored in the diversity in test inputs to improve the test effectiveness of test suites. To address this problem, we propose three context-aware refined strategies to check whether redundant test cases can replace previously selected test cases to achieve the same coverage level but with different context diversity levels. The empirical study shows that context diversity can be significantly injected into adequate test suites, and favoring test cases with higher context diversity can significantly improve the fault detection rates of adequate test suites for testing context-aware applications. In conclusion, this thesis makes the significant contributions to the research in testing context-aware applications: (1) It has formulated context diversity, a novel metric to measure context changes inherent in test inputs. (2) It has proposed three context-aware strategies to select test cases with different levels of context diversity. Compared with the baseline strategy, the strategy CAS-H that uses test cases with higher context diversity can significantly reduce the cost of mutation testing over context-aware applications in terms of less number of test runs, smaller adequate test suites, and less number of test inputs used to construct test suites. (3) It has defined three context-aware refined strategies to construct adequate test suites with different context diversity levels. Compared with the baseline strategy, the strategy CARS-H that favors test cases with higher context diversity can significantly improve the effectiveness of adequacy testing in terms of higher fault detection rates. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

We introduce a novel Syntax-based Security Testing (SST) framework that uses a protocol specification to effectively perform security testing on text-based communication protocols. A protocol specification of a particular text-based protocol under-tested (TPUT) represents its syntactic grammar and static semantic contracts on the grammar. Mutators written in TXL break the syntactic and semantic constraints of the protocol specification to generate test cases. Different protocol specification testing strategies can be joined together to yield a compositional testing approach. SST is independent of any particular text-based protocols. The power of SST stems from the way it obtains test cases from the protocol specifications. We also use the robust parsing technique with TXL to parse a TPUT. SST has successfully revealed security faults in different text-based protocol applications such as web applications and kOganizer. We also demonstrate SST can mimic the venerable PROTOS Test-Suite: co-http-reply developed by University of Oulu. / Thesis (Ph.D, Computing) -- Queen's University, 2010-04-30 16:01:18.048

Mutation testing is a powerful fault-based testing technique that makes syntactic changes to a program under test in order to simulate real faults otherwise caused by a programmer. Similar to structural coverage criteria such as statement coverage, mutation testing is used to assess the quality of a test suite. After a syntactic change has been made, the program is referred to as a mutant that either can survive a test suite, or be killed by one. If a mutant is killed, it means that the test suite has detected the syntactic change and reported it as an error, resulting in an increased mutation score. If a mutant survives, it means that the test suite failed to detect the fault and the mutation score is decreased. Mutation testing is generally considered the strongest testing technique available in terms of fault detection, but also the most expensive one. However, thanks to recent research and the rapid development of computing hardware, the testing technique is starting to become feasible, motivating the creation of tools utilizing the power of mutation testing. Saab AB, the Swedish aircraft manufacturer and stakeholder in this thesis, has experimented with mutation testing in the past, resulting in a tool called BAX that creates textual modifications of the original source code. The initial goal of this thesis is to provide a new tool that is faster than BAX, and that is more systematic in the way mutants are generated. LLVM-P86, the main contribution of this thesis, is a compiler and mutation testing framework intended for the programming language Pascal-86. Unlike BAX, LLVM-P86 is able to encode several mutants into a single program, thus reducing the time spent on compiling source code. In the conducted experiments, LLVM-P86 processed mutants significantly faster than BAX, on average by a factor of 13.6. Since LLVM-P86 is also a compiler, proper type information is available when mutants are generated. The additional type information allows LLVM-P86 to avoid a significant amount of equivalent mutants, i.e. mutants that behave in the same way as the original program. When mutating relational operators found in approximately 10,000 lines of code, distributed amongst 18 different Pascal-86 modules, LLVM-P86 was able to reduce the total number of living mutants by 25%, or 5.7% of the complete set of mutants.

Software testing is an important factor of the software development process. Integration testing is an important and expensive level of the software testing process. Unfortunately, since the developers have limited time to perform integration testing and debugging and integration testing becomes very hard as the combinations grow in size, the chain of calls from one module to another grow in number, length, and complexity. This research is about providing new methodology for integration testing to reduce the number of test cases needed to a significant degree while returning as much of its effectiveness as possible. The proposed approach shows the best order in which to integrate the classes currently available for integration and the external method calls that should be tested and in their order for maximum effectiveness. Our approach limits the number of integration test cases. The integration test cases number depends mainly on the dependency among modules and on the number of the integrated classes in the application. The dependency among modules is determined by using an information retrieval technique called Latent Semantic Indexing (LSI). In addition, this research extends the mutation testing for use in integration testing as a method to evaluate the effectiveness of the integration testing process. We have developed a set of integration mutation operators to support development of integration mutation testing. We have conducted experiments based on ten Java applications. To evaluate the proposed methodology, we have created mutants using new mutation operators that exercise the integration testing. Our experiments show that the test cases killed more than 60% of the created mutants.

How can you tell whether your test suites are reliable? This is often done through the use of coverage criterion that would define a set of requirements that the test suites need to fulfill in order to be considered reliable. The most widely used criterion is those referred to as code coverage, where the degree to which the code base is covered is used as an arbitrary measure of how good the test suites are. Achieving high coverage would indicate an adequate test suite i.e. reliable according to the standards of code coverage. However, covering a line of code does not necessarily mean that it has been tested. Thus, code coverage can only tell you what parts of the code base have not been tested, opposed to what have been tested. Mutation testing on the other hand is an approach to evaluate the adequacy of test suites through their fault detection ability, rather than how much of the code base they cover.   This thesis performs mutation analysis on a project with inadequate code coverage. The present testing effort on unit level is evaluated and the cost and benefits of adopting mutation testing as a testing method is evaluated. / Hur vet man när tester är tillförlitliga? Ofta använder man sig av täckningskriterium som definierar en uppsättning krav som tester måste uppfylla för att betraktas som pålitlig. Det mest använda kriterier är de som kallas kodtäckning, där graden till vilken kodbasen är täckt används som ett mått av pålitlighet av tester. Hög täckning indikerar adekvat tester, dvs pålitlig enligt kodtäckning. Men täckning av en kodlinje betyder inte nödvändigtvis att den har testats. Koddekning kan således bara visa vilka delar av kodbasen som inte har testats, snarare än vad som har testats. Mutation testing å andra hand är ett sätt att utvärdera testers effektivitet genom deras felsökningsförmåga, snarare än hur mycket av kodbasen de täcker.   Denna examensarbete utför mutationsanalys på ett projekt med otillräcklig koddekning. Kvalite av nuvarande tester på enhetsnivå utvärderas och kostnaden och fördelar för att anta mutation testning som en testmetod utforskas.

Test suites for database applications depend on adequate test data and real-world test faults for success. An automated tool is available that quantifies test data coverage for database queries written in SQL. An automated tool is also available that mimics real-world faults by mutating SQL, however tests have revealed that these simulated faults do not completely represent real-world faults. This paper demonstrates how half of the mutation operators used by the SQL mutation tool in real-world test suites generated significantly lower detection scores than those from research test suites. Three revised mutation operators are introduced that improve detection scores and contribute toward re-defining a sufficient set of mutation operators for SQL. Finally, a procedure is presented that reduces the test burden by automatically comparing SQL mutants with their original queries. / Master of Science

No desenvolvimento de software, a qualidade do produto está diretamente relacionada à qualidade do processo de desenvolvimento. Diante disso, atividades de Verificação, Validação & Teste (VV&T) realizadas por meio de métodos, técnicas e ferramentas são de extrema necessidade para o aumento da produtividade, qualidade e diminuição de custos no desenvolvimento de software. Do mesmo modo, técnicas e critérios contribuem para a produtividade das atividades de teste. Um ponto crucial para o teste de software é sua automatização, tornando as atividades mais confiáveis e diminuindo significativamente os custos de desenvolvimento. Na automatização dos testes, os oráculos são essenciais, representando um mecanismo (programa, processo ou dados) que indica se a saída obtida para um caso de teste está correta. Este trabalho de mestrado utiliza a ideia de mutação para criar implementações alternativas de oráculos de teste e, assim, avaliar a sua qualidade. O teste de mutação se refere à criação de versões do sistema em desenvolvimento com pequenas alterações sintáticas de código. A mutação possui alta eficácia na detecção de defeitos e é bastante flexível na sua aplicação, podendo ser utilizada em diversos tipos de artefatos. Adicionalmente, este trabalho propõe operadores de mutação específicos para oráculos, implementa uma ferramenta de apoio à utilização desses operadores para oráculos e também descreve um estudo empírico dos operadores, destacando benefícios e desafios associados ao seu uso. / In software development, product quality is directly related to the quality of the development process. Therefore, activities of Verification, Validation & Testing (VV&T) performed by methods, techniques and tools are urgently required to increase productivity, quality and cost reduction in software development. Similarly, testing technique and criteria contribute to the productivity of test activities. A crucial point for the software testing automation is making the most reliable activities and significantly reducing development costs. Regarding software testing automation, test oracles are essential, representing an mechanism (program, process or data) to indicate whether the actual output for a given test case is correct. This masters thesis aims to explore concepts of mutation testing to create alternative implementations of the oracle procedure and thus assess their quality. Mutation testing refers to the creation of system development versions with minor syntactic code changes. It has high efficiency on defects detecting and it is very flexible in its application and it is being used in various types of artifacts. This work also proposes specific mutation operators for oracles, implements an useful support tool for using these oracle mutation operators and conducts an empirical study of operators, highlighting benefits and challenges associated with their use.

Um dos pontos fundamentais na atividade de teste de software é o projeto de casos de teste. Diversos critérios de adequação têm sido propostos com o objetivo de fornecer meios que permitam que a avaliação e elaboração de casos de teste sejam feitas de maneira sistemática e fundamentadas teoricamente. Infelizmente, a maioria dos critérios de adequação de casos de teste definidos tem seu uso restrito ao teste de unidade. Para fases posteriores da atividade de teste, em particular para o teste de integração, nota-se a ausência de critérios de adequação, principalmente porque os critérios propostos definem requisitos de teste que se restringem aos limites de uma única unidade, não exercitando de maneira efetiva as interações entre as unidades, que devem ser alvo principal no teste de integração. Com exceção de alguns poucos trabalhos que procuram estender critérios estruturais para o nível interprocedimental, tem-se utilizado nessa fase de teste, quase que exclusivamente, critérios funcionais. Dada essa ausência de critérios e salientando ainda o caráter complementar entre as diferentes técnicas de teste, esta tese apresenta um critério de teste interprocedimental baseado em defeitos chamado de Mutação de Interface. Esse critério busca exercitar as interações entre as unidades através da seleção de casos de teste que distingam mutantes criados pela introdução de defeitos típicos e que, de acordo com um modo definido, caracterizamos erros de integração. Definiu-se um conjunto de operadores de Mutação de Interface que concentram sua aplicação em pontos do programa relacionados com as interações entre as unidades, como, por exemplo, chamadas de subprogramas e seus parâmetros. Dados o alto custo de aplicação, inerente de critérios baseados em mutação, e pelas próprias características do conjunto de operadores de Mutação de Interface, torna-se necessário definirem-se abordagens para reduzir esse custo. Assim, foram estabelecidas maneiras de se parametrizar a aplicação dos operadores de mutação, definindo-se critérios de Mutação de Interface alternativos, estendendo-se abordagem sutilizadas no teste de mutação convencional como mutação restrita. A aplicação de um critério de teste está fortemente condicionada à sua automatização. A definição de um critério de teste sem que pelo menos se apontem soluções para sua automatização tem pouca utilidade prática. Por isso, especificou-se e implementou-se a ferramenta PROTEUM/IM para apoiar a aplicação do critério Mutação de Interface. Essa ferramenta torna-se essencial neste trabalho à medida que permite que estudos empíricos possam ser realizados, avaliando o critério proposto. Dois estudos de caso são apresentados. Esses estudos aplicam o critério Mutação de interface em programas reais e buscam avaliar seu custo e sua eficácia em revelar erros. Estes estudos aplicam ainda critérios alternativos, mostrando que a Mutação de interface é bastante efetiva em revelar erros o de ter custo de aplicação bastante reduzido, quando aplicada de maneira incremental, utilizando-se as parametrizações que os operadores de mutação oferecem. / The project of test cases is one of the most important topics in the software testing activity. Several criteria have been proposed aiming at allowing the evaluation and selection of test cases in a systematic and theoretically well founded way. Unfortunately, the use of most of these criteria is restricted to the unit testing phase. For other testing phases, in particular for integration testing. there is a lack of such criteria, mainly because the existing criteria define test requirements only in the scope of a single unit. They arc not able to effectively exercise the interactions between units, what should be the focus of integration testing. Excepting some few works that extend structural criteria to the interprocedural level, only functional testing has been used at integration testing phase. Given this lack of criteria and the complementary characteristics of different testing techniques, this thesis presents an interprocedural fault based criterion named Interface Mutation. This criterion exercises the interactions between units through the selection of test cases that distinguish mutants created by introducing typical faults that characterize integration errors. A set of Interface Mutation operators was defined. The focus of these operators are the points of the program related to the unit interactions, for instance, subprogram calls and their parameters. Given the high cost associated to mutation testing in general and particularly to the Interface Mutation operators, it is necessary to define some approaches to reduce its application cost. Thus, some parameterizations were defined to the mutation operators, allowing to establish alternative Interface Mutation criteria, extending approaches already used in conventional mutation testing, as random mutation and constrained mutation. The application of any testing criterion strongly depends on its automatization. The definition of a criterion, without pointing out ways to its implementation has little practical utility. So, a tool named PROTEUM/IM was specified and implemented to support the application of Interface Mutation. This tool is an essential point in the present work because it allows the conduction of empirical studies aiming at evaluating the proposed criterion. Two case studies arc presented. In these studies the criterion Interface Mutation is applied to real programs and the cost of its application as well as its errors revealing effectiveness are evaluated. Alternative criteria are also used. Showing that Interface Mutation is very effective to reveal errors and can be applied with a reduced cost if used in an incremental way, taking advantage of the parameterization characteristics provided by the Interface Mutation operators set.

A Programação Concorrente tornou-se uma forma popular de desenvolvimento de software. Este paradigma de desenvolvimento e essencial para construir aplicações com o intuito de reduzir o tempo computacional em muitos domínios como, por exemplo, previsão tempo, processamento de imagem, entre outros. Estes programas têm novas características como a comunicação, a sincronização e o não determinismo, que precisam ser considerados durante a atividade de teste. O teste de software e uma atividade que busca garantir a qualidade por meio da identificação de falhas no produto. O Teste de Mutação e um critério de teste que se baseia nos enganos que podem ser cometidos pelos desenvolvedores de software. Porém, o teste de mutação não pode ser aplicado em programas concorrentes da mesma maneira como e aplicado em programas sequenciais por causa das particularidades presentes nos programas concorrentes. Um problema de aplicar o teste de mutação nesse contexto e o comportamento não determinístico das aplicações. Este trabalho investiga a definição do teste de mutação para programas concorrentes implementados em MPI (Message Passing Interface), os quais realizam comunicação e sincronização por meio de troca de mensagens. Para isso, defeitos típicos nesse domínio foram considerados, buscando modelar operadores de mutação para tratar os aspectos de comunicação e sincronização dessas aplicações. Também foi proposto um procedimento para dar suporte a análise comportamental dos mutantes. As idéias foram implementadas em uma ferramenta de teste chamada ValiMPI Mut / Concurrent programming became a popular paradigm for software development. This paradigm is essential to build applications which aim to reduce the computational time in many areas, such as, weather forecast, image processing, among others. These programs present new features such as communication, synchronization, and nondeterminism, which must be considered during the testing activity. Software testing is an activity that looks to ensure quality by identifying faults in the product. Mutation Testing is a criterion based on the most common mistakes that might be made by software developers. However, the mutation testing cannot be applied in concurrent programs the same way as applied in sequential ones due to the peculiarities present in concurrent programs. One of the problems in applying mutation testing in this context is the non-deterministic behavior. This work investigates the definition of mutation testing for concurrent programs implemented in MPI (Message Passing Interface), which perform communication and synchronization using message passing. For this, typical faults in this area were considered in order to model mutation operators addressing the aspects of communication and synchronization of these applications. Also, we are proposing a new procedure to support the behavioral analysis of the mutants. The ideas were implemented in a testing tool called ValiMPI Mut