字符串谓词边界的ON—OFF测试点自动生成算法

针对字符串谓词边界 ,提出了一个ON—OFF测试点自动生成算法。通过对字符串输入变量的每一字符 ,构造其线性分支函数 ,进行Korel的分支函数极小化 ,动态生成给定字符串谓词边界的ON—OFF测试点。实验表明 :该算法是行之有效的。     

基于搜索的面向路径字符串测试数据自动生成方法

针对字符串测试数据自动生成,讨论了字符串间的距离,将不满足路径条件的字符串谓词表示成一个实值目标函数;利用快速下降搜索算法实施目标函数极小化,实现了基于搜索的面向路径字符串测试数据自动生成方法;探讨了其测试数据生成效率与初始输入、路径处理顺序之间的关系,并与遗传算法等几种算法进行了比较．实验结果表明：该方法是一种更经济有效的测试数据生成方法．     

EFSM模型的字符串类型测试数据自动生成

基于软件描述模型的测试数据自动生成研究中,字符串类型测试数据生成是一个研究热点和难点。EFSM模型是一种重要的软件描述模型。分析了EFSM模型的特点,针对面向EFSM模型目标路径的字符串测试数据生成,建立了字符串输入变量模型和操作模型,结合静态测试的特点,给出了通过字符串变量模型在目标路径上的符号执行结果生成字符串类型测试数据的方法。实验结果表明,该方法能够达到预期效果,提高测试生成效率。     

Gupta方法的改进

Gupta等提出一种线性化谓词函数的方法（简称Gupta方法），为指定程序路径自动生成测试数据。该文给出了一种模型语言，研究静态，动态数据依赖关系的性质以及Gupta方法中各概念的形式化定义，将Gupta等提出的谓词出推广为路径静态切片，证明了路径静态切片构造算法的正确性，对Gupta方法的改进，省略了构造谓词片和输入依赖集的过程，改进后的方法构造线性约束的效率更高，以改进后的方法为核心算法，开发了面向路径的测试数据自动生成的原型工具，并用实际的程序路径对该工具进行实际，结果表明改进后的方法是比较有效的。     

测试数据自动生成技术研究

软件测试分为静态分析、路径选择、测试数据生成和动态分析四个阶段,而测试数据的自动生成是软件测试的关键技术之一。文章通过对被测试程序的分析,提出了生成测试数据的平衡力法,对任意的输入变量,判断变量移动范围及进行谓词中变量的函数极小化,得到测试数据,并给出了具体实现方法。     

基于选择性冗余的测试数据自动生成算法

基于选择性冗余思想,提出了一种测试数据自动生成算法.算法首先利用分支函数线性逼近和极小化方法,找出程序中所有可行路径,同时对部分可行路径自动生成适合的初始测试数据集;当利用分支函数线性逼近和极小化方法无法得到正确的测试数据时,基于使得测试数据集最小的原理和选择性冗余思想,针对未被初始测试数据集覆盖的谓词和子路径进行测试数据的增补.由于新算法结合谓词切片和DUC表达式,可以从源端判断子路径是否可行,因此能有效地降低不可行路径对算法性能的影响.算法分析和实验结果表明,该算法有效地减少了测试数据数量,提高了测试性能.     

基于变异粒子群算法的字符串型测试数据生成

基于搜索的算法在以路径覆盖为目标的测试数据生成中应用广泛。然而对于字符串型测试数据的生成,现有方法效率不高。为了高效地生成字符串型测试数据,提出了一种基于变异粒子群算法的字符串型测试数据自动生成方法。在随机生成初始种群后,采用粒子群算法使种群在趋近最优个体的过程中实现进化,并以一定的概率对种群中的个体进行变异操作,以避免进化过程陷入局部最优。为了有效地指导种群进化过程,对经典适应度函数中分支距离的计算方法进行改进,使其适用于含有字符串型参数的程序。实验结果表明,该方法具有较高的成功率和稳定性,且能明显提升测试数据生成效率。     

带数组和循环的路径测试数据自动生成技术研究

提出了一种新的带数组和循环的路径测试数据自动生成的方法.该方法只考虑数组中与路径中谓词函数有关的数组元素,将循环中的同一变量名在每一次执行时用不同的变量参数来替代,从而较好地解决了路径中数组循环有效处理的问题.为有效、简单地自动生成测试数据,建立了谓词函数关于输入变量的线性约束系统.当谓词函数为线性表达式时,不需要计算其线性算术表示,仅计算非线性函数谓词函数的线性算术表示,且不需计算路径中的谓词片和确定输入依赖集,以及构造谓词函数关于输入变量增量的线性约束系统.理论分析和实例验证该方法具有简单、直观、有效且计算量小等特点.     

基于谓词动态切片技术的AOP测试用例生成方法研究

面向方面程序设计是面向对象程序设计技术的补充和完善,高效的面向方面程序测试方法是面向方面程序的质量保证.提出一个基于谓词动态切片技术的测试方法.首先,构造完整的AOP语句控制流图,它包含AOP的方面、切入点、连接点、建议等因素.然后,根据完整的AOP语句控制流图生成所有路径,针对每条路径,构造其分支函数,计算得到相应的测试数据,若路径不可执行,则不再计算其测试数据.在这个过程中,通过构建简化动态依赖图来生成谓词动态切片,再用谓词动态切片来帮助调整测试数据.最后,将各路径的实际输出数据与期望输出数据相比较,即可判断该程序是否有错误.经实例分析和实验验证,此方法可以系统地测试一个完整的面向方面程序,提高了测试数据的生成效率,并产生有效的测试用例.     

Gupta方法中线性约束系统的相容性分析及改进

研究了Gupta方法中的关键步骤——谓词函数的线性约束系统的建立，指出用Gupta方法建立的线性约束系统本身可能存在不相容、无法找到测试数据的问题；提出了一种算法来解决这一问题，提高了软件测试数据自动生成的有效性。     

Automatic string test data generation for detecting domain errors

Domain testing is designed to detect domain errors that result from a small boundary shift in a path domain. Although many researchers have studied domain testing, automatic domain test data generation for string predicates has seldom been explored. This paper presents a novel approach for the automatic generation of ON–OFF test points for string predicate borders, and describes a corresponding test data generator. Our empirical work is conducted on a set of programs with string predicates, where extensive trials have been done for each string predicate, and the results are analysed using the SPSS tool. Conclusions are drawn that: (i) the approach is promising and effective; (ii) there is a strong linear relationship between the performance of the test generator and the length of target string in the predicate tested; and (iii) initial inputs, no shorter than the target string and with characters generated randomly, may enhance the performance in the test data generation for string predicates. Copyright © 2009 John Wiley & Sons, Ltd.     

Techniques and applications of computation slicing

Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which requires finding whether there exists a consistent cut of a given computation that satisfies a given global predicate.Detecting a predicate in a computation is, however, an NP-complete problem in general. In order to ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice. Formally, the slice of a computation with respect to a predicate is a (sub)computation with the least number of consistent cuts that contains all consistent cuts of the computation satisfying the predicate. Intuitively, slice is a concise representation of those consistent cuts of a computation that satisfy a certain condition. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice.We prove that the slice of a computation is uniquely defined for all predicates. We also present efficient algorithms for computing the slice for several useful classes of predicates. For an arbitrary predicate, we establish that the problem of computing the slice is NP-complete in general. Nonetheless, for such a predicate, we develop an efficient heuristic algorithm for computing an approximate slice. Our experimental results demonstrate that slicing can lead to an exponential improvement over existing techniques for predicate detection in terms of time and space.Received: 19 November 2003, Revised: 29 July 2004, Published online: 7 February 2005Vijay K. Garg: Supported in part by the NSF Grants ECS-9907213, CCR-9988225, Texas Education Board Grant ARP-320, an Engineering Foundation Fellowship, and an IBM grant.Parts of this paper have appeared earlier in conference proceedings [GM01,MG01a,MG03a].     

基于谓词检测方法的上下文感知案例研究

当前,开发灵活的适应环境变化的上下文感知应用较为复杂。在上下文感知应用开发过程中,很多未知情况无法事先被充分考虑到,实际的开发又需要处理很多意外情形,因此有效地表示和处理上下文尤为重要。谓词检测作为实现上下文感知的重要方法之一,能够有效对上下文信息进行建模,但在实际应用中对于真实物理设备的支持如何在很大程度上仍然是未知的。为了应对以上问题,通过构建一个简单的物理场景,将谓词检测方法应用于真实的机器小车上,支持其在一个既定轨道上完成运行任务。在该场景下对原始的上下文环境进行建模,将环境特性逐步规约成特定的快照谓词和序列谓词,并在案例研究中,对规约化的谓词进行检测,将谓词检测应用于真实的机器小车实验上。实验分析的结果表明,谓词检测的方法能有效检测小车的上下文特性并成功支撑小车完成既定的行走目标。     

Improved method to generate path-wise test data

Gupta et al.,propsed a method ,which is referred to as the Iterative Relaxation Method ,to generate test data for a given path in a program by linearizing the predicate functions.In this paper,a model language is presented and the properties of static and dynamic data depen-dencies are investigated ,The notions in the Interative Relaxation Method are defined formally.The predicate slice proposed by Gupta et al.is extended to path-wise static slice.The correctness of the constructional algorithm is proved afterward The improvement shows that the constructions of predicate slice and input dependency set can be omitted .The equivalence of systems of constraints generated by both methods is proved ,The prototype of path-wise test data generator is presented in this paper,The experiments show shat our method is practical ,and fits the path-wise automatic generation of test data for both whicte -bos testing and black-blx testing.     

BWDSP104X多条件谓词编译优化

目前BWDSP104X编译器对程序中条件分支的处理是采用传统的谓词优化方法,及每条指令和一个谓词相关,只有当谓词为真时指令才被执行,但它存在的局限性是当涉及到多条件谓词时,并不能消除跳转分支,且多条件谓词之间可能存在控制依赖关系,不利于指令并行和指令流水. 因此在现有编译器框架下,针对传统谓词优化方法的不足之处,本文提出一种基于BWDSP104X体系结构下多条件谓词编译优化方法. 实验结果表明,与传统谓词优化方法相比,该优化算法在BWDSP104X编译器上能够取得平均5.62的加速比.     

一种基于路径的测试数据自动生成算法

提出了一种新的基于路径测试数据自动生成的算法,该算法将路径中的线性谓词函数直接作为线性算术表示来构造谓词函数关于输入变量的线性约束,仅当谓词函数是输入变量的非线性函数时,才计算其线性算术表示,因而不必计算所有谓词函数的线性算术表示,也不必计算谓词片和确定输入依赖集,以及构造谓词函数关于输入变量的增量的线性约束,理论分析和实例证明,该算法具有简单、容易、有效且计算量小等特点。     

Efficient Detection of Channel Predicates in Distributed Systems

This paper discusses efficient detection of global predicates in a distributed program. Previous work in this area required predicates to be specified as a conjunction of predicates defined on individual processes. Many properties in distributed systems, however, use the state of channels, such as “the channel is empty,” or “there is a token in the channel.” In this paper, we introduce the concept of alinearchannel predicate and provide efficient centralized and distributed algorithms to detect any conjunction of local and linear channel predicates. The class of linear predicates is fairly broad. For example, classic problems such as detection of termination and computation of global virtual time are instances of conjunctions of linear channel predicates. Linear predicates can be functions of the number of messages in the channel, or can be based upon the actual contents of the messages. The main application of our results are in debugging and testing of distributed programs. For these applications it is important to detect thefirststate where some predicate is true. We show that this first state is uniquely defined if and only if linear predicates are used.     

基于Kripke结构的程序正确性证明

为了方便证明程序的正确性,引入了Kripke结构,提出基于Kripke结构的程序正确性证明。重新定义了适合证明的Kripke结构,并描述了将程序流程图转换为Kripke结构状态图的方法。给出了证明程序正确性的相关定理和基于Kripke结构的程序正确性证明方法。证明方法为:首先,把程序流程图转换为状态图;然后,根据状态之间的转移关系列出每个状态下的状态谓词;最后,证明每个状态谓词为真。根据状态谓词进行证明,能够反映出程序执行的状态。用该方法对一个实例进行了完整的证明。