In recent year, a lot of scholar try to generate test sets for combinatorial strategy automatically. But these algorithms based on combinatorial strategy don¡¦t consider conflicts of input parameter model. A conflict exists when the result of combining two or more values of different parameter dose not make sense. Thus, invalid sub-combinations may be included in test cases in the test suite, and these are useless to us. Besides, these algorithms all directly generate all test cases once, in other words, it is unable to utilize test cases generated at present to feedback and revise the algorithm, so it is easy to generate useless combinations. So, this paper proposes new test generation algorithm for combinatorial testing based on constraint satisfaction problem(CSP) to solve problem which invalid sub-combinations may be included in test cases, and we can add constraints flexibly during generating test cases to avoid generate useless or repeated combinations. The experimental result indicate that our algorithm perform well, with respect to the amount of time required for test generation, otherwise, we can generate conflict-free test cases directly.

In recent year the research field of the combinatorial testing, which can roughlybe divided into two kinds including pair-wise coverage and multi-wise coverage. a lot of scholar try to use various strategies to generate test data automatically. In order to weight the generated test set, the generated test data must satisfy certain criterion. But these combinatorial strategy neglected the flexibility of using on the practice. Considering software testing from the practice, which often be restricted by the cost. For this reason, how to obtaint the greatest testing benefits under the limited cost must be considered on the parctice. But in the extant combinatorial strategy, there is no flexible use. In other words, we must testing test set totally. Therefore, there is very great restriction to exist on using the test data generated by the extant combinatorial strategy on the practice. So, this paper proposes a flexible combinatorial strategy based on CSP, which allow users to do the most valid testing under the limited cost, which also allow users join the constraints that needs at any time during the testing process, revise the test data that we produced dynamically. The experimental result indicate that our method perform well, it can avoid including the test data whether some users think the interests less or unnecessarier, in order to achive the greatest testing beneifts.Further, we can achive the goal of reducing the quantity of testing data.

abstract: A new algebraic system, Test Algebra (TA), is proposed for identifying faults in combinatorial testing for SaaS (Software-as-a-Service) applications. In the context of cloud computing, SaaS is a new software delivery model, in which mission-critical applications are composed, deployed, and executed on cloud platforms. Testing SaaS applications is challenging because new applications need to be tested once they are composed, and prior to their deployment. A composition of components providing services yields a configuration providing a SaaS application. While individual components in the configuration may have been thoroughly tested, faults still arise due to interactions among the components composed, making the configuration faulty. When there are k components, combinatorial testing algorithms can be used to identify faulty interactions for t or fewer components, for some threshold 2 <= t <= k on the size of interactions considered. In general these methods do not identify specific faults, but rather indicate the presence or absence of some fault. To identify specific faults, an adaptive testing regime repeatedly constructs and tests configurations in order to determine, for each interaction of interest, whether it is faulty or not. In order to perform such testing in a loosely coupled distributed environment such as the cloud, it is imperative that testing results can be combined from many different servers. The TA defines rules to permit results to be combined, and to identify the faulty interactions. Using the TA, configurations can be tested concurrently on different servers and in any order. The results, using the TA, remain the same. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2014

Testing is a crucial and necessary part of software development used to detect faults and make sure that the software works properly. One testing method proposed in research is named combinatorial testing, where a test suite covers all combinations of parameter values in a certain way. There is some evidence that indicated that most faults are triggered by a few number of parameter value combinations. There have been various tools proposed for using combinatorial testing in practice. ACTS is one of the most popular combinatorial research tools. Even if ACTS has been used in several industrial projects, few studies have shown how such a combinatorial testing tool can be used for modelling and test generation for industrial control software. In this study we apply modelling and test generation using ACTS on a Programmable Logic Control (PLC) software. This kind of software is used in the safety critical domain for controlling different computer devices, such as a train control management system, which is in charge of many of the critical and safety related procedures on a train. Testing this kind of software is very important because failures can contribute to the loss of lives and money.  We show how ACTS can be applied to PLC software. We evaluated ACTS in terms of applicability (i.e., how can ACTS can be applied directly on modelling the PLCs) and efficiency in terms of generation time and test suite size. We used 17 PLC programs provided by Bombardier Transportation. Based on the number of inputs in a program we divided the programs into three complexity categories: small, medium and large programs. An input space model was created for each program, where the needed information was obtained from both the programs and the engineers writing the programs. Each model was created as a system in the graphical interface of ACTS. The different algorithms and combinatorial techniques supported by ACTS were used to generate test suites by varying coverage of the parameter combinations (i.e. t-way) in the command line of ACTS. In this study we used a cut-off time of 1 hour for the test generation, as this is a realistic estimation based on discussion with industrial engineers. Our results showed that not all combinations of algorithms and combinatorial strengths could generate a test suite within the cut-off time. We argue that the results of the the modelling process and the results showing the efficiency of the test generation tool can be useful for practitioners considering to use combinatorial testing for PLC software.

abstract: This dissertation studies three classes of combinatorial arrays with practical applications in testing, measurement, and security. Covering arrays are widely studied in software and hardware testing to indicate the presence of faulty interactions. Locating arrays extend covering arrays to achieve identification of the interactions causing a fault by requiring additional conditions on how interactions are covered in rows. This dissertation introduces a new class, the anonymizing arrays, to guarantee a degree of anonymity by bounding the probability a particular row is identified by the interaction presented. Similarities among these arrays lead to common algorithmic techniques for their construction which this dissertation explores. Differences arising from their application domains lead to the unique features of each class, requiring tailoring the techniques to the specifics of each problem. One contribution of this work is a conditional expectation algorithm to build covering arrays via an intermediate combinatorial object. Conditional expectation efficiently finds intermediate-sized arrays that are particularly useful as ingredients for additional recursive algorithms. A cut-and-paste method creates large arrays from small ingredients. Performing transformations on the copies makes further improvements by reducing redundancy in the composed arrays and leads to fewer rows. This work contains the first algorithm for constructing locating arrays for general values of $d$ and $t$. A randomized computational search algorithmic framework verifies if a candidate array is $(\bar{d},t)$-locating by partitioning the search space and performs random resampling if a candidate fails. Algorithmic parameters determine which columns to resample and when to add additional rows to the candidate array. Additionally, analysis is conducted on the performance of the algorithmic parameters to provide guidance on how to tune parameters to prioritize speed, accuracy, or a combination of both. This work proposes anonymizing arrays as a class related to covering arrays with a higher coverage requirement and constraints. The algorithms for covering and locating arrays are tailored to anonymizing array construction. An additional property, homogeneity, is introduced to meet the needs of attribute-based authorization. Two metrics, local and global homogeneity, are designed to compare anonymizing arrays with the same parameters. Finally, a post-optimization approach reduces the homogeneity of an anonymizing array. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

Modern society is increasingly dependent on the quality of software systems. Software failure can cause severe consequences, including loss of human life. There are various ways of fault prevention and detection that can be deployed in different stages of software development. Testing is the most widely used approach for ensuring software quality. Requirements-Based Testing and Partition Testing are two of the widely used approaches for testing software systems. Although both of these techniques are mature and are addressed widely in the literature and despite the general agreement on both of these key techniques of functional testing, a combination of them lacks a systematic approach. In this thesis, we propose a framework along with a procedural process for testing a system using Requirements-Based Partition Testing (RBPT). This framework helps testers to start from the requirements documents and follow a straightforward step by step process to generate the required test cases without loosing any required data. Although many steps of the process are manual, the framework can be used as a foundation for automating the whole test case generation process. Another issue in testing a software product is the test case selection problem. Choosing appropriate test cases is an essential part of software testing that can lead to significant improvements in efficiency, as well as reduced costs of combinatorial testing. Unfortunately, the problem of finding minimum size test sets is NP-complete in general. Therefore, artificial intelligence-based search algorithms have been widely used for generating near-optimal solutions. In this thesis, we also propose a novel technique for test case generation using Particle Swarm Optimization (PSO), an effective optimization tool which has emerged in the last decade. Empirical studies show that in some domains particle swarm optimization is equally well-suited or even better than some other techniques. At the same time, a particle swarm algorithm is much simpler, easier to implement, and has just a few parameters that the user needs to adjust. These properties make PSO an ideal technique for test case generation. In order to have a fair comparison of our newly proposed algorithm against existing techniques, we have designed and implemented a framework for automatic evaluation of these methods. Through experiments using our evaluation framework, we illustrate how this new test case generation technique can outperform other existing methodologies.

Modern society is increasingly dependent on the quality of software systems. Software failure can cause severe consequences, including loss of human life. There are various ways of fault prevention and detection that can be deployed in different stages of software development. Testing is the most widely used approach for ensuring software quality. Requirements-Based Testing and Partition Testing are two of the widely used approaches for testing software systems. Although both of these techniques are mature and are addressed widely in the literature and despite the general agreement on both of these key techniques of functional testing, a combination of them lacks a systematic approach. In this thesis, we propose a framework along with a procedural process for testing a system using Requirements-Based Partition Testing (RBPT). This framework helps testers to start from the requirements documents and follow a straightforward step by step process to generate the required test cases without loosing any required data. Although many steps of the process are manual, the framework can be used as a foundation for automating the whole test case generation process. Another issue in testing a software product is the test case selection problem. Choosing appropriate test cases is an essential part of software testing that can lead to significant improvements in efficiency, as well as reduced costs of combinatorial testing. Unfortunately, the problem of finding minimum size test sets is NP-complete in general. Therefore, artificial intelligence-based search algorithms have been widely used for generating near-optimal solutions. In this thesis, we also propose a novel technique for test case generation using Particle Swarm Optimization (PSO), an effective optimization tool which has emerged in the last decade. Empirical studies show that in some domains particle swarm optimization is equally well-suited or even better than some other techniques. At the same time, a particle swarm algorithm is much simpler, easier to implement, and has just a few parameters that the user needs to adjust. These properties make PSO an ideal technique for test case generation. In order to have a fair comparison of our newly proposed algorithm against existing techniques, we have designed and implemented a framework for automatic evaluation of these methods. Through experiments using our evaluation framework, we illustrate how this new test case generation technique can outperform other existing methodologies.

Introduction: Software testing is a very important activity which assures the quality of the software under test. It becomes crucial in safety-critical systems, where an unexpected behavior of the software can even cause loss of human life or environmental disasters. However, in such complex systems it becomes infeasible to test all possible software scenarios for possible faults. Experience shows that software faults, which can cause unexpected software behavior, are caused by the interactions of variables of the tests. Combinatorial testing is the technique which focuses on the variable interactions of the tests and aims to reduce the number of tests needed to cover all software scenarios while still preserving a high fault detection rate. Background: Manual testing is the technique used to assure software quality in Bombardier Transportation AB, a Swedish company whose focus is on rail transport and development of trains. Since this process depends on the skills of the engineers, it can result in a large portion of tests not created and consequently in a large number of scenarios uncovered with tests. Therefore, combinatorial testing technique is used to measure the combinatorial coverage of these tests created from experienced engineers. Many comparisons of manual testing and other testing techniques in terms of test coverage, code coverage or mutation analysis. To the best of our knowledge there are no other studies in literature that have measured the combinatorial coverage of manual tests designed from experienced engineers, for different strength interactions of the variables of the tests nor other available tools that generate the number of missing tests to achieve full combinatorial coverage for specific interactions. Aim: The goal of this thesis is to answer the two research questions: RQ1. What is the combinatorial coverage achieved by tests manually created by experienced engineers in industry? RQ2. Can the effectiveness of manually created tests be improved in terms of combinatorial coverage using combinatorial testing? Method: In this thesis we investigate the combinatorial coverage of manually created tests by engineers working in industry and the implications of using combinatorial testing in practice. The Combinatorial Coverage Measurement2(CCM) NIST tool is used to measure the test coverage achieved. The research questions are answered by the following steps: 1) Review the scientific literature for related work, 2) Refine thesis research questions based on the previous step, 3) Propose the case study design and perform the measurements needed for data analysis, 4) and the results are analyzed and discussed in terms of test efficiency (i.e., number of test cases) and effectiveness (i.e., achieved combinatorial coverage). Results: The 2-way interaction combinatorial coverage achieved by manual tests is 78.6% on average, 57% for 3-way combinatorial coverage, 40.2% for 4-way combinatorial coverage, 20.2% for 5-way combinatorial coverage and 13% for 6-way combinatorial coverage. Full combinatorial coverage can be achieved for 2-way and 3-way interactions by adding eight and 66 missing tests on average, respectively. For 4-way interactions full combinatorial coverage can achieved by adding 658 missing tests. For 5-way and 6-way interactions full combinatorial coverage can be achieved by adding 5163 and 6170 missing tests on average respectively. Conclusion: The combinatorial coverage decreases as the strength of interactions increases. The effectiveness of the tests can be improved for 2-way and 3-way interactions and fully or partially improved for 4-way interactions, depending on the decision of engineers to add all missing tests or part of them, since the number of missing tests is increasing significantly, thus resulting in a very large number of tests to be added. It is not particularly efficient to improve test effectiveness by augmenting manual tests cases using combinatorial testing for higher strength interactions, since in most of the tests suites we studied one would need to generate additional 10.000 missing tests. This is explained by the exponential growth of the number of variable combination for such interactions.

Testing is an important activity in software development used to ensure the quality of a product. In industrial practice when developing control software, such as Programmable Logic Controllers (PLCs), software testing is, in some cases, neglected during the development process. There is little support for automated testing on PLC software and the creation of test cases is hence mainly a manual activity that can be both costly and time-consuming. In this thesis, we propose a solution for an integrated tool chain for automating the testing process for IEC 61131-3 PLC software in the integrated development environment (IDE) of CODESYS (Controller Development System), using a combinatorial testing tool (i.e., SEAFOX) for test case generation. Further, we measure the applicability and usefulness of the integrated tool chain in terms of the decision coverage (i.e, Observable Decision Coverage) achieved by the generated test cases. For this purpose, several available tools for testing in CODESYS IDE have been examined as well as solutions on how to integrate the chosen tool (i.e., CfUnit) with SEAFOX. After a solution for the tool chain was implemented and integrated, an experiment was conducted to measure decision coverage for the generated test cases on nine industrial programs using Pairwise, Base choice and Random combinatorial testing techniques. The result of our thesis is a fully integrated tool chain consisting of CODESYS, CfUnit, SEAFOX, and a python script used to combine these, and where the SEAFOX tool was further extended to support additional standard data types. This tool chain can be used to create test cases, generate new input values for these using SEAFOX, automate the additional test case creation and integration with CfUnit in CODESYS IDE, as well as for test execution. The results of the experiment show that test cases generated by this tool chain achieved on average 90% decision coverage or higher regardless of the combinatorial technique used, with the overall average level being 94%. Interestingly enough, Random testing scored higher than both Pairwise and Base choice testing. We present our integrated tool chain as a contribution to the automation of test creation and execution for industrial control software in CODESYS IDE. However, we identified several limitations with testing CODESYS timer blocks and when executing larger test suites that can make it problematic to fully test PLC programs in a real-time simulation environment. These challenges should be investigated further by both researchers and practitioners.

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.