基于差分进化算法的组合测试用例集生成

为了减小所生成的组合测试用例集规模,提出了一种基于one-test-at-a-time策略的差分进化算法来求解该问题的方案。通过实验,比较了不同变异方式的优化性能,考察了各个算法参数对优化性能的影响,并与其他常用方法进行了对比。实验结果表明,与其他常用的组合测试用例生成方法相比,基于差分进化算法的生成方法能够生成规模更小的组合测试用例集。并且组合数越多,该算法的优势就越明显。     

组合测试用例生成技术

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

一种改进的两两组合测试用例生成方法

本文针对多因素二水平系统提出:将所有的测试数据表示为一棵二叉解空间树,用回溯法对二叉解空间树进行路径搜索来生成测试用例,然后使用贪心算法生成补充的测试用例,以满足两两组合覆盖标准。使用这种方法生成的测试数据集具有很高的覆盖率。     

一种组合测试用例生成的可配置混合算法

组合测试是一种经过实践证明的科学有效的测试方法,其研究重点之一是组合测试用例集的生成算法。基于参数顺序渐进扩充策略IPO(In-Parameter-Order)是其中一种具有代表性的通用算法,其优势在于水平扩充算法的可选择性和测试用例集的可扩展性。算法在提取影响IPO策略效果的参数的基础上,给出可配置的IPO策略;采用遗传算法(Genctic-Algorithm)配置IPO策略中的水平扩充,得到新的混合算法IPO_GA。通过实验对可配置IPO策略中各个参数对算法的影响进行了对比分析;将IPO_ GA与部分已有算法进行了比较,结果表明在水平扩充过程中染色体较短时,IPO_GA效果较好;在解空间规模过大而导致染色体较长时,IPO_GA效果略差。     

基于要因组合的测试用例生成技术研究

黑盒测试用例设计时必须考虑用例集的完备性和无冗余性.文章提出了一种基于要因组合的测试用例生成方法,在提升黑盒测试用例的设计质量的同时,有效的降低了测试用例集的规模,从而提高了测试效率.     

和声搜索算法在组合测试用例生成中的应用

一个复杂的软件系统通常受很多因素影响,它们之间的交互造成系统行为的复杂化和各种故障,要完全地测试这些交互组合,不切实际。组合测试技术考虑因素的不同交互对系统产生的不同影响,以最小的测试用例提高测试质量。本文提出一种根据和声搜索算法产生组合测试用例的方法,解决多维组合覆盖和可变强度组合覆盖的关键问题,并通过实验验证该方法的有效性。     

基于贡献度的两两组合测试用例生成算法

为在两两组合测试中获得近似最小的测试用例集,提出一种基于贡献度的两两组合测试用例自动生成算法。生成满足覆盖要求的有序配对集,根据有序配对集生成初始用例集,对初始用例集进行简约,获得测试用例集。实验结果表明,该算法生成的测试用例数目较少,算法效率较高。     

蚁群模拟退火算法在测试用例约简中的应用

参数的成对组合覆盖测试技术是软件测试中有效的测试方法之一。该文将模拟退火思想引入蚁群算法,组成新的混合算法,即蚁群模拟退火混合算法(ASA),应用在组合测试用例的约简过程中。按照测试的特殊需求进行多种建模尝试,通过仿真实验对算法涉及的参数进行研究,实验验证了ASA 算法对测试用例集的约简作用是有效的。     

A divide-and-conquer-based algorithm for automatic simulation vector generation

Testbenches play one of the most important roles in simulation-based design verification. Given a simulation scenario, a testbench provides specific vectors to simulate the design, then collects responses from the design to monitor whether the simulation has satisfied the scenario. The major bottleneck in writing testbenches is generating valid simulation vectors. Many current automatic-vector-generation methods focus on exploring a design's state space. Due to memory or runtime limitations, these methods cannot keep up with the rapid growth of design complexity. We propose a novel algorithm based on the divide-and-conquer paradigm that helps these methods decompose the design's complexity. The algorithm uses a partitioning method that recursively divides a design into smaller, more manageable components. Other approaches handle the divided components while maintaining the entire design's proper functioning. Random simulation generates sets of simulation vectors by randomly assigning the logic values to the design's primary inputs (Pis) one cycle at a time. Unlike random simulation, which uses only a single trace, symbolic solvers attempt to simultaneously enumerate all possible primary inputs to explore the entire state space. They typically use binary decision diagrams (BDDs) or satisfiability (SAT) solvers as their core engine.     

A modified summation code for organizing control of combinatorial circuits

We propose a new modified summation code which has improved error detection characteristics as compared to the classical summation code. We define the properties of this code and propose methods to implement the generators of control bits.     

启发式遗传算法求解两两组合测试用例集

针对两两组合测试用例集的生成问题,在有效地结合了两两组合测试问题本身的特点基础上,提出了一种基于动态解空间的启发式遗传算法(HGA)。详细分析了测试用例生成过程,根据其解空间的动态变化在传统遗传算法中加入了启发算子,使得HGA算法可以快速地搜索出当前局部优化的测试用例。实验结果表明,HGA算法在完全覆盖参数两两组合的前提下有效地减少了测试用例的数量,并且具有较快的迭代速度。     

Automatic test case generation for structural testing of function block diagrams

ContextFunction Block Diagram (FBD) is increasingly used in safety-critical applications. Test coverage issues for FBDs are frequently raised by regulators and users. However, there is little work at this aspect on testing FBD at model level. Our previous study has designed a new data-flow test coverage criterion, FB-Path Complete Condition Test Coverage (FPCC), that can directly test FBD structures and effectively detect function mutation errors. Nevertheless, because FPCC scheme involves several data-flow concepts and thus it is somewhat complicated to comprehend and to generate FPCC-complied test cases. An automatic test suite generator for FPCC is highly desirable.ObjectiveThis study designs an automatic test case generator, FPCCTestGen, for FPCC so as to enhance the practicability and acceptance of the FPCC approach.MethodFirst, a supporting infrastructure for performing automatic FBD-to-UPPAAL-for-FPCC transformation is designed. The supporting infrastructure includes templates, declarations, and functions as building blocks for transformation. Then, for each input FBD, represented in PLCopen XML format, FPCCTestGen performs parsing and converts FBD components into corresponding UPPAAL model components using aforementioned building blocks. After that, queries related to FPCC characteristics are submitted to UPPAAL model checker for verification. Finally, the verification traces are analyzed to obtain a FPCC-complied test suite.ResultsA safety injection system is used as a case study. Preliminary results show that the generated test suite achieves the highest FPCC percentage with a near optimal number of test cases.ConclusionThis automatic test case generation tool is effective and thus, can promote the use of the new test coverage criterion. Methodology used in FPCCTestGen is generic and can be applied to test suite generation for other test criteria on data-flow programs.     

一种有效的指纹预处理组合算法

系统分析指纹预处理全过程,在图像初滤波和方向滤波器设计方面提出新见解.结合指纹图像高频丰富的特点,及小波包高频分辨率高的分析特性,采用小波包分析对指纹图像进行初滤波;设计方向滤波器时,对滤波器的旋转引入方-圆变换,减少计算复杂度,同时避免引入误差.对含高斯白噪声指纹图像的实验结果表明,该预处理算法是有效的.     

A relation-based method combining functional and structural testing for test case generation

Specification-based (or functional) testing enables us to detect errors in the implementation of functions defined in specifications, but since specifications are often incomplete in practice for some reasons (e.g., lack of ideas, no time to write), it is unlikely to be sufficient for testing all parts of corresponding programs. On the other hand, implementation-based (or structural) testing focuses on the examination of program structures, which allows us to test all parts of the programs, but may not be effective to show whether the programs properly implement the corresponding specifications. To perform a comprehensive testing of a program in practice, it is important to adopt both specification-based and implementation-based testing. In this paper we describe a relation-based test method that combines the specification-based and the implementation-based testing approaches. We establish a set of relations for test case generation, illustrate how the method is used with an example, and investigate the effectiveness and weakness of the method through an experiment on testing a software tool system.     

Stability of a combinatorial vector partition problem

The vector variant of the partition problem is considered. It is shown that the coincidence of the Pareto and Slater sets is the necessary and sufficient condition of stability of the problem with respect to its functional. __________ Translated from Kibernetika i Sistemny i Analiz, No. 3, pp. 177–181, May–June 2007.     

Quantum-inspired evolutionary algorithm for a class of combinatorial optimization

This paper proposes a novel evolutionary algorithm inspired by quantum computing, called a quantum-inspired evolutionary algorithm (QEA), which is based on the concept and principles of quantum computing, such as a quantum bit and superposition of states. Like other evolutionary algorithms, QEA is also characterized by the representation of the individual, evaluation function, and population dynamics. However, instead of binary, numeric, or symbolic representation, QEA uses a Q-bit, defined as the smallest unit of information, for the probabilistic representation and a Q-bit individual as a string of Q-bits. A Q-gate is introduced as a variation operator to drive the individuals toward better solutions. To demonstrate its effectiveness and applicability, experiments were carried out on the knapsack problem, which is a well-known combinatorial optimization problem. The results show that QEA performs well, even with a small population, without premature convergence as compared to the conventional genetic algorithm.     

Exhaustive generation of combinatorial objects by ECO

The problem of exhaustively generating combinatorial objects can currently be applied to many disciplines, such as biology, chemistry, medicine and computer science. A well known approach to the exhaustive generation problem is given by the Gray code scheme for listing n-bit binary numbers in such a way that successive numbers differ in exactly one bit position. In this work, we introduce an exhaustive generation algorithm, which is general for the classes of succession rules considered in [1]. We also show that our algorithm is efficient in an amortized sense; it actually uses only a constant amount of computation per object.Received: 10 October 2003, Revised: 10 February 2004, Published online: 21 April 2004     

基于组合测试模式的集成虚拟仪器软件测试

针对集成虚拟仪器提出了一个有效的软件测试方法,满足了实际工程的需要.通过建立电子测量工作站的Petri网模型,分析虚拟仪器软件的特点,运用组合测试、分割测试、实时性测试等策略生成并优化测试用例集,对电子测量工作站软件进行测试,不仅提高了测试用例的效率,且降低了测试成本.