基于树模型和输入参数关系的组合测试集精简方法*

提出了一种精简组合测试用例集的方法,该方法基于解空间树模型,利用输入参数之间的依赖关系来剪裁解空间树中的枝叶,从而获得精简的组合测试用例集。该方法采用回溯算法来实现,在遍历树的同时,剪裁解空间树并输出组合测试用例。在算法的实现过程中,采用了一些策略以便提高算法的效率并节省空间。实验结果证明该方法是可行和有效的,对于一些输入参数依赖关系明确的被测系统,该方法能够较大幅度地精简全组合测试用例集。     

Generating combinatorial test suite using combinatorial optimization

Combinatorial testing (CT) is an effective technique to test software with multiple configurable parameters. It is used to detect interaction faults caused by the combination effect of parameters. CT test generation aims at generating covering arrays that cover all t-way parameter combinations, where t is a given covering strength. In practical CT usage scenarios, there are usually constraints between parameters, and the performance of existing constraint-handling methods degrades fast when the number of constraints increases.The contributions of this paper are (1) we propose a new one-test-at-a-time algorithm for CT test generation, which uses pseudo-Boolean optimization to generate each new test case; (2) we have found that pursuing the maximum coverage for each test case is uneconomic, and a possible balance point is to keep the approximation ratio in [0.8,0.9]; (3) we propose a new self-adaptive mechanism to stop the optimization process at a proper time when generating each test case; (4) extensive experimental results show that our algorithm works fine on existing benchmarks, and the constraint-handling ability is better than existing approaches when the number of constraints is large; and (5) we propose a method to translate shielding parameters (a common type of constraints) into normal constraints.     

组合测试用例生成技术

组合测试是一种科学有效的软件测试方法,该方法旨在使用较少的测试用例有效地检测软件系统中各个因素以及它们之间的相互作用对系统产生的影响,实践证明其具有较高的错误检测能力。当前组合测试研究的热点之一是组合测试用例生成问题,即如何针对具体待测软件,在满足给定组合覆盖要求的前提下,生成规模尽可能小的测试用例集,以便在保证错误检测能力的前提下尽可能降低测试成本。从N维组合覆盖和变力度组合覆盖等两类不同的组合覆盖标准出发,简要介绍了迄今为止人们在组合测试用例生成领域所取得的研究成果,对现有的组合用例生成方法进行了分类和总结。此外,还对优先级、组合约束、错误定位等条件和应用场景下的组合测试用例生成技术进行了介绍。最后,分析了现有成果中存在的问题,并对该领域未来的研究方向进行了分析和讨论。     

Measuring complexity and coverage of software specifications

Coverage testing in the context of Markov chain usage models refers to coverage of a model of the specification and profile of intended use, rather than coverage of the code that implements the specification. A new measure of specification complexity based on the number of statistically typical paths through the model of the specification is derived. Formulae are presented to compute bounds on the expected number of test cases required to achieve state and arc coverage. Formulae are presented to compare different usage models with respect to the amount of testing required to achieve coverage of typical paths. Convexity properties are established for these formulae to facilitate their use in optimization calculations that are used to generate transition probabilities for the usage models.     

Measuring instance difficulty for combinatorial optimization problems

Discovering the conditions under which an optimization algorithm or search heuristic will succeed or fail is critical for understanding the strengths and weaknesses of different algorithms, and for automated algorithm selection. Large scale experimental studies - studying the performance of a variety of optimization algorithms across a large collection of diverse problem instances - provide the resources to derive these conditions. Data mining techniques can be used to learn the relationships between the critical features of the instances and the performance of algorithms. This paper discusses how we can adequately characterize the features of a problem instance that have impact on difficulty in terms of algorithmic performance, and how such features can be defined and measured for various optimization problems. We provide a comprehensive survey of the research field with a focus on six combinatorial optimization problems: assignment, traveling salesman, and knapsack problems, bin-packing, graph coloring, and timetabling. For these problems - which are important abstractions of many real-world problems - we review hardness-revealing features as developed over decades of research, and we discuss the suitability of more problem-independent landscape metrics. We discuss how the features developed for one problem may be transferred to study related problems exhibiting similar structures.     

Declarative paradigm of test coverage

Two facts about declarative programming prevent the application of conventional testing methods. First, the classical test coverage measures such as statement, branch or path coverage, cannot be used, since in declarative programs no control flow notion exists. Second, there is no widely accepted language available for formal specification, since predicate logic, which is the most common formalism for declarative programming, is already a very high-level abstract language. This paper presents a new approach exending previous work by the authors on test input generation for declarative programs. For this purpose, the existing program instrumentation notion is extended and a new logic coverage measure is introduced. The approach is mathematically formalized and the goal of achieving 100% program logic coverage controls the automatic test input generation. The method is depicted by means of logic programming; the results are, however, generally applicable. Finally, the concepts introduced have been used practically within a test environment. © 1998 John Wiley & Sons, Ltd.     

Increasing test coverage with Hapao

Test coverage is about assessing the relevance of unit tests against the tested application. It is widely acknowledged that software with a “good” test coverage is more robust against unanticipated execution, thus lowering the maintenance cost. However, ensuring good quality coverage is challenging, especially since most of the available test coverage tools do not discriminate between software components that require “strong” coverage from the components that require less attention from the unit tests.Hapao is an innovative test coverage tool, implemented in the Pharo Smalltalk programming language. It employs an effective and intuitive graphical representation to visually assess the quality of the coverage. A combination of appropriate metrics and relations visually shape methods and classes, which indicates to the programmer whether more effort on testing is required.This paper presents the important features of Hapao by illustrating its application on an open source software.     

Cryptographic verification of test coverage claims

The market for software components is growing, driven on the “demand side” by the need for rapid deployment of highly functional products and, on the “supply side”, by distributed object standards. As components and component vendors proliferate, there is naturally a growing concern about quality and the effectiveness of testing processes. White-box testing, particularly the use of coverage criteria, Is a widely used method for measuring the “thoroughness” of testing efforts. High levels of test coverage are used as indicators of good quality control procedures. Software vendors who can demonstrate high levels of test coverage have a credible claim to high quality. However, verifying such claims involves knowledge of the source code, test cases, build procedures, etc. In applications where reliability and quality are critical, it would be desirable to verify test coverage claims without forcing vendors to give up valuable technical secrets. In this paper, we explore cryptographic techniques that can be used to verify such claims. Our techniques have certain limitations, which we discuss in this paper. However, vendors who have done the hard work of developing high levels of test coverage can use these techniques (for a modest additional cost) to provide credible evidence of high coverage, while simultaneously reducing disclosure of intellectual property     

An identification of program factors that impact crossover performance in evolutionary test input generation for the branch coverage of C programs

Context: Genetic Algorithms are a popular search-based optimisation technique for automatically generating test inputs for structural coverage of a program, but there has been little work investigating the class of programs for which they will perform well.Objective: This paper presents and evaluates a series of program factors that are hypothesised to affect the performance of crossover, a key search operator in Genetic Algorithms, when searching for inputs that cover the branching structure of a C function.Method: Each program factor is evaluated with example programs using Genetic Algorithms with and without crossover. Experiments are also performed to test whether crossover is acting as macro-mutation operator rather than usefully recombining the component parts of input vectors when searching for test data.Results: The results show that crossover has an impact for each of the program factors studied.Conclusion: It is concluded crossover plays an increasingly important role for programs with large, multi-dimensional input spaces, where the target structure’s input condition breaks down into independent sub-problems for which solutions may be sought in parallel. Furthermore, it is found that crossover can be inhibited when the program under test is unstructured or involves nested conditional statements; and when intermediate variables are used in branching conditions, as opposed to direct input values.     

Alpha 21164 manufacturing test development and coverage analysis

To meet the challenge of creating test vectors for the Alpha 21164 microprocessor, Compaq's engineers describe a test generation and grading scheme that solves time-to-market, quality and cost concerns     

The combinatorial design approach to automatic test generation

The combinatorial design method substantially reduces testing costs. The authors describe an application in which the method reduced test plan development from one month to less than a week. In several experiments, the method demonstrated good code coverage and fault detection ability     

Practical minimization of pairwise-covering test configurations using constraint programming

Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while maintaining high software quality. Finding the smallest set of valid test configurations that ensure sufficient coverage of the system’s feature interactions is thus the objective of validation engineers, especially when the execution of test configurations is costly or time-consuming. However, this problem is NP-hard in general and approximation algorithms have often been used to address it in practice.Objective: In this paper, we explore an alternative exact approach based on constraint programming that will allow engineers to increase the effectiveness of configuration testing while keeping the number of configurations as low as possible.Method: Our approach consists in using a (time-aware) minimization algorithm based on constraint programming. Given the amount of time, our solution generates a minimized set of valid test configurations that ensure coverage of all pairs of feature values (a.k.a. pairwise coverage). The approach has been implemented in a tool called PACOGEN.Results: PACOGEN was evaluated on 224 feature models in comparison with the two existing tools that are based on a greedy algorithm. For 79% of 224 feature models, PACOGEN generated up to 60% fewer test configurations than the competitor tools. We further evaluated PACOGEN in the case study of an industrial video conferencing product line with a feature model of 169 features, and found 60% fewer configurations compared with the manual approach followed by test engineers. The set of test configurations generated by PACOGEN decreased the time required by test engineers in manual test configuration by 85%, increasing the feature-pairs coverage at the same time.Conclusion: Our experimental evaluation concluded that optimal time-aware minimization of pairwise-covering test configurations is efficiently addressed using constraint programming techniques.     

Qualifying input test data for model transformations

Model transformation is a core mechanism for model-driven engineering (MDE). Writing complex model transformations is error-prone, and efficient testing techniques are required as for any complex program development. Testing a model transformation is typically performed by checking the results of the transformation applied to a set of input models. While it is fairly easy to provide some input models, it is difficult to qualify the relevance of these models for testing. In this paper, we propose a set of rules and a framework to assess the quality of given input models for testing a given transformation. Furthermore, the framework identifies missing model elements in input models and assists the user in improving these models.

具有约束条件的组合测试用例集的构建方法

针对如何为存在约束条件的软件系统生成尽可能小的组合测试用例集问题,提出了基于组合测试算法的约束组合测试法.该方法是对待测系统中的约束条件进行处理,将约柬条件先转化为合取范式再转化为布尔表达式的形式.利用布尔可满足性求解器进行求解,找出满足约束条件的约束组合测试用例.最后运用AETG-SAT算法得到较优的组合测试用例集,并通过实验表明了AETG-SAT算法的优越性.     

A backtracking search tool for constructing combinatorial test suites

Combinatorial testing is an important testing method. It requires the test cases to cover various combinations of parameters of the system under test. The test generation problem for combinatorial testing can be modeled as constructing a matrix which has certain properties. This paper first discusses two combinatorial testing criteria: covering array and orthogonal array, and then proposes a backtracking search algorithm to construct matrices satisfying them. Several search heuristics and symmetry breaking techniques are used to reduce the search time. This paper also introduces some techniques to generate large covering array instances from smaller ones. All the techniques have been implemented in a tool called EXACT (EXhaustive seArch of Combinatorial Test suites). A new optimal covering array is found by this tool.     

Measuring the coverage and redundancy of information search services on e-commerce platforms

Today’s widespread e-commerce applications pose a new challenge to information search services. They must extract a useful small set of search or recommendation results from a larger set that preserves information diversity. This paper proposes a novel metric setting to measure two important aspects of information diversity, information coverage and information redundancy. In addition to content coverage, we consider another important measure of information coverage called structure coverage, and model it using information entropy. This approach can better convey the information coverage of the extracted small set with respect to the original large set. The proposed metrics are effective and have various useful properties, which are demonstrated by theoretical and experimental analysis. We also designed a calculation method that shows good computational efficiency. Finally, we conducted an experiment using real data from online customer reviews to further emphasize the effectiveness of the proposed metrics.     

基于OTT策略的组合测试用例优先级排序方法

在组合测试用例优先级排序问题中,通常采用组合覆盖率为排序标准,该方法能够尽快满足覆盖率的要求,但其排序影响因子较为单一,缺陷检测能力不稳定。针对此问题,该文结合One-Test-at-a-Time（OTT）策略提出了一种在线调整的组合测试用例优先级排序方法,引入多重待覆盖率、测试用例失效率和测试用例重要程度3个影响因子用于衡量组合测试用例优先级。根据测试用例的在线测试反馈信息,该方法能够实时调整组合测试用例的优先级,增加了优先级排序的准确性。实验结果表明,相较于original、基于单一覆盖和多重覆盖的组合测试优先级排序方法,该方法在缺陷检测能力和稳定性上具有更强的竞争力。     

Automatic test case generation for WS-Agreements using combinatorial testing

In the scope of the applications developed under the service-based paradigm, Service Level Agreements (SLAs) are a standard mechanism used to flexibly specify the Quality of Service (QoS) that must be delivered. These agreements contain the conditions negotiated between the service provider and consumers as well as the potential penalties derived from the violation of such conditions. In this context, it is important to assure that the service based application (SBA) behaves as expected in order to avoid potential consequences like penalties or dissatisfaction between the stakeholders that have negotiated and signed the SLA. In this article we address the testing of SLAs specified using the WS-Agreement standard by means of applying testing techniques such as the Classification Tree Method and Combinatorial Testing to generate test cases. From the content of the individual terms of the SLA, we identify situations that need to be tested. We also obtain a set of constraints based on the SLA specification and the behavior of the SBA in order to guarantee the testability of the test cases. Furthermore, we define three different coverage strategies with the aim at grading the intensity of the tests. Finally, we have developed a tool named SLACT (SLA Combinatorial Testing) in order to automate the process and we have applied the whole approach to an eHealth case study.     

Factor oriented requirement coverage based system test case prioritization of new and regression test cases

Test case prioritization involves scheduling test cases in an order that increases the effectiveness in achieving some performance goals. One of the most important performance goals is the rate of fault detection. Test cases should run in an order that increases the possibility of fault detection and also that detects the most severe faults at the earliest in its testing life cycle. In this paper, we propose to put forth a model for system level test case prioritization (TCP) from software requirement specification to improve user satisfaction with quality software that can also be cost effective and to improve the rate of severe fault detection. The proposed model prioritizes the system test cases based on the six factors: customer priority, changes in requirement, implementation complexity, completeness, traceability and fault impact. The proposed prioritization technique is validated with two different validation techniques and is experimented in three phases with student projects and two sets of industrial projects and the results show convincingly that the proposed prioritization technique improves the rate of severe fault detection.