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.

L'objectif principal de cette thèse est d'apporter des solutions à certaines problèmes du test combinatoire. Le test combinatoire consiste à générer des tests qui couvrent toutes les combinaisons de valeurs d'entrée définies. La première problème abordé, c'est que le test combinatoire peut générer un grand nombre de tests qui sont invalides par rapport à la spécification du système à tester (SUT). Ces tests invalides sont typiquement ceux qui échouent lors de la vérification de la pré-condition d'une opération de système. Ces tests invalides doivent être éliminés de l'ensemble des tests utilisé pour évaluer le SUT, car ils conduisent à des verdicts non concluants. Comme solution, nous proposons de coupler la technique de test combinatoire à une technique d'animation qui repose sur une spécification pour filtrer les tests invalides. Dans notre travail, les tests combinatoires sont générés à partir d'un patron de test. Ce patron est essentiellement défini comme une séquence d'appels d'opérations, en utilisant un ensemble de valeurs pour les paramètres. Le dépliage d'un patron de test complexe, où plusieurs valeurs d'entrée sont utilisées, peut être soumis à une explosion combinatoire, et il est impossible d'avoir des tests valides à partir du patron de test. Il s'agit d'une deuxième problématique de cette thèse. Comme solution, nous proposons un processus de dépliage et d'animation incrémental qui permet de filtrer à un stade précoce (dans la séquence d'appels d'opération) les tests invalides, et donc de maîtriser l'explosion combinatoire. D'autres mécanismes de filtrage sont proposés, pour filtrer les tests qui ne couvrent pas certains comportements d'opération ou ne remplissent pas une propriété donnée. Le nombre de tests générés à partir d'un patron de test peut être considérablement grand pour être exécuté sur un SUT avec ressources mémoires et processeurs limitées. Ce problème est connu sous le nom de problème de réduction de suites de tests, et il représente le troisième problème de cette thèse. Comme solution, nous proposons une nouvelle technique de réduction de suites de tests basée sur les annotations (appelés tags) insérées dans le code source ou la spécification du SUT. L'exécution / animation de tests génère une trace des annotations couverts. Basé sur cette trace d'exécution, une famille de relations d'équivalence est proposée, pour réduire une suite de tests, en utilisant les critères d'ordre et de nombre de répétition des tags couverts. / The main objective of this thesis is to provide solutions to some combinatorial testing issues. The combinatorial testing consists in generating tests that cover all combinations of defined input values. The first issue of this thesis is that combinatorial testing can generate a large number of tests that are invalid according to the specification of the System Under Test (SUT). These invalid tests are typically those which fail the verification of the precondition of system operation. These invalid tests must be discarded from the set of tests used to evaluate the SUT, because they lead to inconclusive verdicts. As a solution, we propose to couple the combinatorial testing technique to an animation technique that relies on a specification to filter out invalid tests. In our work, combinatorial tests are generated from a test pattern. This pattern is mainly defined as a sequence of operation calls, using a set of values for their parameters. The unfolding of a complex test pattern, where many operation calls and/or input values are used, may be subject to combinatorial explosion, and it is impossible to provide valid tests from the test pattern. This is a second issue of this thesis. As a solution, we propose an incremental unfolding and animation process that allows to filter out at early stage (in the operation sequence) invalid tests, and therefore to master the combinatorial explosion. Other mechanisms of filtering are proposed to filter out tests which do not cover some operation behaviors or do not fulfill a given property. The test suites generated from a test pattern can be very large to execute on the SUT due the limited memory or CPU resources. This problem is defined as the test suite reduction problem, and it is the third issue of this thesis. As a solution, we propose a new test suite reduction technique based on annotations (called tags) inserted in the source code or the specification of the SUT. The execution/animation of tests generates a trace of the covered annotations. Based on the trace, a family of equivalence relations is proposed, to reduce a test suite, using the criteria of order and number of repetition of covered tags.

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.

Mjukvarutestning har, sedan introduktionen av datorer, varit föremål för forskning. Idag, när datorer och mikroprocessorer alltmer integreras i produkter som omger oss i vårt dagliga liv, så ökar vikten av effektiv och korrekt mjukvarutestning. Tidigare forskning visar att utforskande testning är en effektiv metod för att upptäcka programvarubuggar. Men, med tids- och resursaspekterna i åtanke finns det andra metoder som kan vara effektivare. En möjlig sådan metod är parvis testning. Litteraturen visar att även denna metod har bra potential för att kunna identifiera programvarubuggar. Det finns dock inte så mycket forskning om jämförelsen av dessa två metoder, vilket är anledningen till att denna studie genomfördes. Denna förklarande fallstudie utvärderar hur utforskande testning presterar jämfört med parvis testning. Aspekter som beaktades i utvärderingsprocessen var antalet upptäckta defekter, allvarlighetsgraden av de hittade defekterna och vilka typer av defekter som hittades. Data samlades in genom undersökningar, intervjuer, deltagande observationer och direkta observationer. Med all denna data som samlats in, drogs slutsatsen att svaret på denna rapports forskningsfrågor är tvetydiga. Det finns fördelar med båda teknikerna, och beroende på förutsättningarna för utforskande testning så kan parvis testning prestera likvärdigt. En sak märktes dock under studien som inte var en del av den ursprungliga omfattningen, och det var styrkan som utforskande testning har som ett läroverktyg. / Software testing has been a subject of research since the introduction of computers. Today, when computers and microprocessors are increasingly integrated into the products surrounding us in our daily lives, the importance of effective and accurate software testing increases. Previous research shows that exploratory testing is an effective method for detecting software bugs. Still, with the time and resource aspects considered, there are other potentially more time and resource-effective methods. One such possible method is the pairwise testing method. The literature also shows that this method is effective for finding software bugs. There is, however, not that much research about the comparison of these two methods, which is why this study was conducted. This explanatory case study evaluates how exploratory testing performs compared with pairwise testing. Aspects considered in the evaluation process were the number of detected defects, the severity distribution of the found defects, and what types of defects were found. The data was collected through surveys, interviews, participant observations, and direct observations. With the data collected, it was concluded that the answers to the research questions of this study are ambiguous. There are benefits with both of the techniques, and depending on the exploratory testing conditions, the pairwise technique can perform comparably as the exploratory testing. However, one thing noticed during the study that was not part of the original scope was the strength of exploratory testing as a learning tool. Lastly, some hypotheses were stated, supported by the collected data.

Embedded systems hold immense potential, but their integration into advanced devices comes with significant costs. Malfunctions in these systems can result inequipment failures, posing serious risks and potential accidents. To ensure theirproper functionality, embedded system components undergo rigorous testing phases,which can be time-consuming, especially for components with numerous connections. Therefore, it is crucial to reduce test time while maintaining high-qualitytesting to detect and address failures early in the development cycle, resulting in improved and safer products. This report delves into various techniques and algorithms aimed at expediting testingprocesses, such as machine learning, risk analysis, test parallelization, and combinatorial testing. It examines the practicality of mathematical models and automatedapproaches in real-world companies through experimentation and implementation.In essence, the report tackles the challenges involved in testing embedded systems,explores different approaches to reduce test time, and presents a suitable model formaintaining test quality. The ultimate goal is to present and implement a methodthat effectively reduces test time while upholding an acceptable level of test quality.The obtained results provide valuable insights for future test groups and researchersseeking to optimize their testing processes and deliver safer products

Mobile applications play an important role in the dissemination of computing and information resources. They are often used in domains such as mobile banking, e-commerce, and health monitoring. Cost-effective testing techniques in these domains are critical. This dissertation contributes novel techniques for automatic construction of mobile application test suites. In particular, this work provides solutions that focus on the prohibitively large number of possible event sequences that must be sampled in GUI-based mobile applications. This work makes three major contributions: (1) an automated GUI testing tool, Autodroid, that implements a novel online approach to automatic construction of Android application test suites (2) probabilistic and combinatorial-based algorithms that systematically sample the input space of Android applications to generate test suites with GUI/context events and (3) empirical studies to evaluate the cost-effectiveness of our techniques on real-world Android applications. Our experiments show that our techniques achieve better code coverage and event coverage compared to random test generation. We demonstrate that our techniques are useful for automatic construction of Android application test suites in the absence of source code and preexisting abstract models of an Application Under Test (AUT). The insights derived from our empirical studies provide guidance to researchers and practitioners involved in the development of automated GUI testing tools for Android applications.

ISAGENis a tool for the automatic generation of structurally complex test inputs that imitate real communication in the context of modern information systems . Complex, typically tree-structured data currently represents the standard means of transmitting information between nodes in distributed information systems. Automatic generator ISAGENis founded on the methodology of data-driven testing and uses concrete data from the production environment as the primary characteristic and specification that guides the generation of new similar data for test cases satisfying given combinatorial adequacy criteria. The main contribution of this thesis is a comprehensive proposal of automated data generation techniques together with an implementation, which demonstrates their usage. The created solution enables testers to create more relevant testing data, representing production-like communication in information systems.