可定位单个错误的错误定位表的生成方法

研究了组合测试错误定位表的结构。针对t维组合测试情形,在假设待测系统中只有一个强度小于等于t维 的错误交互时,提出了一种新的构造这种特殊情形的错误定位表的方法。这种方法构造的错误定位表覆盖了所有的t 维交互并且对任意两个t维交互,表中包含这两个t维交互的行的集合互不相同。最后提出了生成这种错误定位表的 AE"I'Glikc算法。实验表明,用该方法构造出的错误定位表比用t}l维覆盖表构造的错误定位表其行数要少得多。     

基于组合测试的软件故障定位的自适应算法

在研究了Martinez等人提出的组合测试错误定位模型的基础上,改进了他们用高维覆盖表来构造错误定位表的方法,并且针对安全值已知的待测系统提出了至多t维的错误交互定位的自适应算法,从而解决了Martinez 等人提出的开问题之一,并进一步分析了自适应算法的性能,证明了定位错误交互需调用的测试过程数目是关于错误交互数与因...     

基于部分覆盖表的错误交互定位方法

在组合测试定位模型的基础上提出了部分覆盖表的错误交互定位方法,该方法在错误交互个数已知的条件下,通过生成部分覆盖表,利用测试用例运行结果提供的信息来对软件错误交互定位.从理论上证明了部分覆盖表等价于一类特殊的错误定位表,进而研究了部分覆盖表行数的上界,提出生成部分覆盖表的贪心算法,从而给出了定位引发软件故障的错误交互的...     

组合测试用例生成技术

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

覆盖表生成的遗传算法配置参数优化

覆盖表生成是组合测试的关键问题,很多数学方法、贪心算法以及演化搜索方法等被应用于生成各种覆盖表.针对演化搜索方法的性能受到方法本身配置参数影响很大这一实际问题,文中以二维覆盖表生成为实例,系统地对典型的演化搜索方法——遗传算法的种群规模、进化代数、交叉概率、变异概率以及遗传算法的变种算法等因素进行探索,设计了pair-wise法、Base choice法和爬山法3条实验路线探索遗传算法的这些配置参数及其相互作用对算法生成二维覆盖表效果的影响,并回答两个问题:对于特定二维覆盖表生成问题,是否存在遗传算法的最优参数配置;对于一般的二维覆盖表生成问题,是否存在通用的遗传算法最优参数配置.     

相邻因素组合测试用例集的最优生成方法

软件系统是一个复杂的逻辑系统,有很多因素可能影响系统的正常运行,组合测试可以对这些因素及其相互作用可能对系统产生的影响进行检测.针对一类只在相邻因素间存在相互作用的系统,文中提出了相邻因素组合测试的概念,分别给出了相邻因素两两(二维)组合覆盖表、相邻因素N(N＞2)维组合覆盖表和多重维数相邻因素组合覆盖表的生成算法,并证明了3个算法均可以生成数量最优的相邻因素组合测试用例集.最后通过实际应用场景,分析了相邻因素组合测试的应用价值.     

组合测试中用例集的选择策略

组合测试用例众多,软件测试人员都希望用最少的测试用例集达到最好的测试覆盖。研究了组合测试的常规算法,比较了配对测试法和正交表测试法的特点,并借助于PICT测试工具重点研究了2因子模型的配对组合测试,在此基础上,总结出在组合测试中测试用例集的选择策略,进而达到满意的测试覆盖。     

基于状态迁移的Web应用功能测试用例生成方法

针对Web应用测试方法错误覆盖率低的问题,提出了一种基于状态迁移的Web应用功能测试用例生成方法。该方法通过构造页面状态迁移图、事件迁移表和导航迁移表对Web应用的链接关系进行表示。基于页面状态迁移图生成的页面状态迁移树生成测试路径,根据等价类划分原则,提出了一种测试用例覆盖准则,结合事件迁移表和导航迁移表中的信息记录构造测试用例。典型案例实验结果表明,该方法有效地表示了Web应用中页面间的链接关系,提高了测试用例的错误检测率。     

基于符号零压缩二叉决策图的组合测试用例生成方法

组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是NP完全的。给出了一种基于符号零压缩二叉决策图(Zero-suppressed Binary Decision Diagram,ZBDD)的组合测试用例生成方法。该方法首先利用ZBDD的结构特性,对测试系统进行紧凑的符号表示。然后利用ZBDD的隐式操作,结合贪心算法的思想,不断地覆盖更多的组合并缩小未覆盖组合集合,生成2～4维覆盖强度的较小测试用例集。实验证明,所提方法不仅可行而且节点开销小。     

基于UML交互概览图的测试线索的生成方法

针对单一UML模型测试不充分的问题,结合UML2.0交互概览图的特点开展测试方法研究,提出一种测试线索自动生成的方法。首先,给出UML类图、顺序图、交互概览图(OID)的形式化定义;通过提取交互概览图的流程信息和对象交互信息分别构造节点控制流图(NCFG)和消息序列图(MSD);将从MSD提取的消息路径嵌入到NCFG中,构造可测试交互概览图模型;最后采用两两覆盖准则生成测试线索。实验验证了该方法自动生成的测试线索在保证测试充分性的前提下可避免组合爆炸。     

Covering arrays avoiding forbidden edges

Covering arrays (CAs) can be used to detect the existence of faulty pairwise interactions between parameters or components in a software system. The generalization considered here applies to the situation in which some input combinations are invalid, a requirement quite common in software testing. In this paper, we study covering arrays avoiding forbidden edges (CAFEs), where certain pairwise interactions are forbidden while all others must be covered, and we aim to minimize the number of tests. We establish a theoretical framework for this problem, by providing connections to the edge clique covering problem, lower and upper bounds, complexity results and a recursive construction. We also give an algorithm for the case of binary alphabets.     

覆盖表生成的禁忌搜索算法

组合测试可以有效检测待测系统中由参数间交互作用而引发的故障.在其30多年的发展过程中,覆盖表生成一直是关键问题之一,相关研究文献已达200多篇.作为一种有效的覆盖表生成算法,已有的禁忌搜索算法在所生成的覆盖表规模上具备一定的优势,但其解的质量和运算速度仍有提升空间;同时,这些算法实际应用能力较差,既不支持约束处理,也无法生成可变力度覆盖表.针对以上问题,提出了一种禁忌搜索算法.该算法从3个方面对已有的算法进行了改进：1）算法参数配置调优分pair-wise和爬山两阶段进行,确保使用较少配置条数最大程度击中最优配置,进一步提高算法生成覆盖表的规模;2）进行算法并行化,加速算法生成覆盖表的速度;3）增加约束处理和变力度处理,使算法可适应多种测试场景.实验结果表明,该算法在固定力度、变力度、带约束等多种类型覆盖表的规模上都具有一定优势,同时,并行化使算法平均加速2.6倍左右.     

Practical Combinatorial Testing: Beyond Pairwise

With new algorithms and tools, developers can apply high-strength combinatorial testing to detect elusive failures that occur only when multiple components interact. In pairwise testing, all possible pairs of parameter values are covered by at least one test, and good tools are available to generate arrays with the value pairs. In the past few years, advances in covering-array algorithms, integrated with model checking or other testing approaches, have made it practical to extend combinatorial testing beyond pairwise tests. The US National Institute of Standards and Technology (NIST) and the University of Texas, Arlington, are now distributing freely available methods and tools for constructing large t-way combination test sets (known as covering arrays), converting covering arrays into executable tests, and automatically generating test oracles using model checking (http://csrc.nist.gov/acts). In this review, we focus on real-world problems and empirical results from applying these methods and tools.     

Variable strength combinatorial testing of concurrent programs

Reachability testing is an important approach to testing concurrent programs. It generates and exercises synchronization sequences automatically and on-the-fly without saving any test history. Existing reachability testing can be classified into exhaustive and t-way testing. Exhaustive testing is impractical in many cases while t-way testing may decrease the capability of fault detection in some cases. In this paper, we present a variable strength reachability testing strategy, which adopts the dynamic framework of reachability testing and uses a variable strength combinatorial strategy. Different parameter groups are provided with different covering strength. Variable strength testing covers no t-way combinations but the necessary combinations of parameters having mutual interactions in a concurrent program. It is more reasonable than t-way testing because uniform interactions between parameters do not often exist in concurrent systems. We propose a merging algorithmthat implements the variable strength combinatorial testing strategy and conduct our experiment on several concurrent programs. The experimental results indicate that our variable strength reachability testing reaches a good tradeoff between the effectiveness and efficiency. It can keep the same capability of fault detection as exhaustive reachability testing while substantially reducing the number of synchronization sequences and decreasing the execution time in most cases.     

Hardness results for covering arrays avoiding forbidden edges and error-locating arrays

Covering arrays avoiding forbidden edges (CAFEs) are used in testing applications (software, networks, circuits, drug interaction, material mixtures, etc.) where certain combinations of parameter values are forbidden. Danziger et al. (2009) [8] have studied this problem and shown some computational complexity results. Around the same time, Martinez et al. (2009) [19] defined and studied error-locating arrays (ELAs), which are closely related to CAFEs. Both papers left some computational complexity questions. In particular, these papers showed polynomial-time solvability of the existence of CAFEs and ELAs for binary alphabets (g=2), and the NP-hardness of these problems for g≥5. In this paper, we prove that optimizing CAFEs and ELAs is indeed NP-hard even when restricted to the case of binary alphabets, using a reduction from edge clique covers of graphs (ECCs). We also provide a hardness of approximation result. We explore important relationships between ECCs and CAFEs and give some new bounds for uniform ECCs and CAFEs.     

Design and implementation of a t-way test data generation strategy with automated execution tool support

To ensure an acceptable level of quality and reliability of a typical software product, it is desirable to test every possible combination of input data under various configurations. However, due to the combinatorial explosion problem, exhaustive testing is practically impossible. Resource constraints, cost factors, and strict time-to-market deadlines are some of the main factors that inhibit such a consideration. Earlier research has suggested that a sampling strategy (i.e., one that is based on a t-way parameter interaction) can be effective. As a result, many helpful t-way sampling strategies have been developed and can be found in the literature.Several advances have been achieved in the last 15 years, which have, in particular, served to facilitate the test planning process by systematically minimizing the test size required (based on certain t-way parameter interactions). Despite this significant progress, the integration and automation of strategies (from planning process to execution) are still lacking. Additionally, strategizing to sample (and construct) a minimum test set from the exhaustive test space is an NP-complete problem; that is, it is often unlikely that an efficient strategy exists that could regularly generate an optimal test set. Motivated by these challenges, this paper discusses the design, implementation, and validation of an efficient strategy for t-way testing, the GTWay strategy. The main contribution of GTWay is the integration of t-way test data generation with automated (concurrent) execution as part of its tool implementation. Unlike most previous methods, GTWay addresses the generation of test data for a high coverage strength (t > 6).     

Scheduling Algorithms with Fault Detection and Location Capabilities for Real-Time Multiprocessor Systems

Several schemes for detecting and locating faulty processors through self-diagnosis in multiprocessor systems have been discussed in the past. These schemes attempt to start multiple copies (versions) of the tasks on available idle processors simultaneously and compare the results generated by the copies to detect or locate faulty processors. These schemes are based on FCFS scheduling strategy. But, they cannot be applied directly to real-time multiprocessor systems where tasks have timing constraints. In this paper, we present a new scheduling algorithm that not only schedules real-time tasks, but also attempts to perform self-diagnosis if the system is not heavily loaded. We define load as a function of the tasks' laxities. We have carried out extensive simulations and compared the results of our algorithm with those of the myopic algorithm, a real-time task scheduler. Simulation results show that our algorithm that exploits both the tasks' laxity and spare capacity (unused processors) offers performance (guarantee ratio) comparable to that of the myopic algorithm in addition to achieving fault detection and location     

一种基于无效链路的分布式故障诊断一致性协议

故障诊断一致性(fault diagnosis agreement,FDA)是高可靠容错分布式系统的性能和完整性的重要保障.目前,大部分FDA协议还是只考虑单一故障组件的简单网络,而对于实际的分布式应用、故障节点和故障链路并存的系统假设更加有意义.但是,在此假设下,对恶意(拜占庭故障)组件的诊断是不可能满足FDA的.为此,首先提出了一种无效链路(invalid link)故障模型,可以更加准确地描述恶意组件的故障行为对系统的影响,有效提高故障诊断的覆盖率.在此模型基础上,提出了一个基于证据的故障诊断协议--PLFDA,可以同时对恶意节点和恶意链路进行检测和定位,并且能够满足故障诊断一致性要求.     

Using simulated annealing for computing cost-aware covering arrays

The configuration spaces of software systems are often too large to test exhaustively. Combinatorial interaction testing approaches, such as covering arrays, systematically sample the configuration space and test only the selected configurations. In an attempt to reduce the cost of testing, standard t-way covering arrays aim to cover all t-way combinations of option settings in a minimum number of configurations. By doing so, they simply assume that every configuration costs the same. When the cost varies from one configuration to another, however, minimizing the number of configurations is not necessarily the same as minimizing the cost. To overcome this issue, we have recently introduced cost-aware covering arrays. In a nutshell, a t-way cost-aware covering array is a standard t-way covering array that “minimizes” a given cost function modeling the actual cost of testing. In this work we develop a simulated annealing-based approach to compute cost-aware covering arrays, which takes as input a configuration space model enhanced with a cost function and computes a cost-aware covering array by using two alternating neighboring state generation strategies together with a fitness function expressed as a weighted sum of two objectives: covering all required t-way option setting combinations and minimizing the cost function. To the best of our knowledge, the proposed approach is the first approach that computes cost-aware covering arrays for general, non-additive linear cost functions with multiplicative interaction effects. We evaluate the approach both by conducting controlled experiments, in which we systematically vary the input models to study the sensitivity of the approach to various factors and by conducting experiments using real cost functions for real software systems. We also compare cost-aware covering arrays to standard covering arrays constructed by well-known algorithms and study how fast the construction costs are compensated by the cost reductions provided. Our empirical results suggest that the proposed approach is more effective and efficient than the existing approaches.     

A novel approach for analog fault diagnosis based on neural networks and improved kernel PCA

We have developed a neural-network-based fault diagnosis approach of analog circuits using maximal class separability based kernel principal components analysis (MCSKPCA) as preprocessor. The proposed approach can detect and diagnose faulty components efficiently in the analog circuits by analyzing their time responses. First, using wavelet transform to preprocess the time responses obtains the essential and reduced candidate features of the corresponding response signals. Then, the second preprocessing by MCSKPCA further reduces the dimensionality of candidate features so as to obtain the optimal features with maximal class separability as inputs to the neural networks. This simplifies the architectures reasonably and reduces the computational burden of neural networks drastically. The simulation results show that our resulting diagnostic system can classify the faulty components of analog circuits under test effectively and achieves a competitive classification performance.