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

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

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

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

基于谓词切片的字符串测试数据自动生成

字符串谓词使用相当普遍，如何实现字符串测试数据的自动生成是一个有待解决的问题，针对字符串谓词，讨论了路径Path上给定谓词的谓词切片的动态生成算法，以及基于谓词切片的字符串测试数据自动生成方法，并给出了字符串间距离的定义，利用程序DUC（Definithon-Use-Control)表达式，构造谓词的谓词切片，对任意的输入，通过执行谓词切片，获取谓词中变量的当前值，进而对谓词中变量的每一字符进行分支函数极小化，动态生成给定字符串谓词边界的ON－OFF测试点，实验表明，该方法是行之有效的。     

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

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

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

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

基于约束满足搜索算法的测试用例生成策略

针对约束系统中非线性谓词函数、指针、数组等复杂运算的求解问题,运用约束满足搜索算法,通过减少约束方程组中参数变量的个数,逐步缩小参数变量的取值范围,提出基于符号法求解约束的改进算法。对含有非线性谓词、数组的程序实例进行实验,结果表明改进算法能有效生成测试用例。     

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

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

Gupta方法的改进

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

一种基于分支覆盖的测试数据自动生成算法

通过构造新的程序流图,利用Fibonacci法优化选取路径．为指定的分支生成测试数据。提出了路径测试数据生成代价的概念,并给出了代价的计算方法。当所选路径的分支谓词均为线性表达式时,直接求解线性约束集即可生成测试数据,或判定路径不可行;当分支谓词含有非线性表达式时,利用均差近似导数将非线性函数线性化,通过简单的迭代,亦能容易生成测试数据或判定路径在很大程度上不可行。若所选路径不可行或在很大程度上不可行,则选取新的路径,重复以上过程,直至求出所期望的数据,或无新的路径被选取,给定分支不可达。实例和实验表明,算法可行、有效。     

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

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

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.     

Counterexample-guided predicate abstraction of hybrid systems

Predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state systems, and has been recently shown to enhance the effectiveness of the reachability computation techniques for hybrid systems. Given a hybrid system with linear dynamics and a set of linear predicates, the verifier performs an on-the-fly search of the finite discrete quotient whose states correspond to the truth assignments to the input predicates. The success of this approach depends on the choice of the predicates used for abstraction. In this paper, we focus on identifying these predicates automatically by analyzing spurious counterexamples generated by the search in the abstract state-space. We present the basic techniques for discovering new predicates that will rule out closely related spurious counterexamples, optimizations of these techniques, implementation of these in the verification tool, and case studies demonstrating the promise of the approach.     

Consistent collective evaluation of multiple continuous queries for filtering heterogeneous data streams

Query processing for a data stream should also be continuous and rapid. This article proposes a novel approach for consistent collective evaluation of multiple continuous queries for filtering two different types of data streams: a relational stream and an XML stream. The proposed approach commonly provides region-based selection constructs: an attribute selection construct for relational queries and a path selection construct for XPath queries. Both collectively evaluate the selection predicates of the same attribute (path), based on the precomputed matching results of the queries in each of the disjoint regions divided by the selection predicates. The performance experiments show that the proposed approach is practically more efficient and stable than other approaches at run-time.     

A Fully Automated Framework for Control of Linear Systems from Temporal Logic Specifications

We consider the following problem: given a linear system and a linear temporal logic (LTL) formula over a set of linear predicates in its state variables, find a feedback control law with polyhedral bounds and a set of initial states so that all trajectories of the closed loop system satisfy the formula. Our solution to this problem consists of three main steps. First, we partition the state space in accordance with the predicates in the formula, and construct a transition system over the partition quotient, which captures our capability of designing controllers. Second, using a procedure resembling model checking, we determine runs of the transition system satisfying the formula. Third, we generate the control strategy. Illustrative examples are included.      

结构测试中的可达路径选择方法

在简单介绍了传统的不可达路径的排除方法后，主要介绍能有效改善其缺陷的可达路径选择方法，基于最少谓词思想的路径生成方法得到广泛的认可，但其实现方法的不同同样会影响路径的可达效果，文中介绍的综合利用控制流信息和数据流信息的方法较之单纯地利用控制流或数据流信息会生成更好的路径。     

An abstraction refinement approach combining precise and approximated techniques

Predicate abstraction is a powerful technique to reduce the state space of a program to a finite and affordable number of states. It produces a conservative over-approximation where concrete states are grouped together according to a given set of predicates. A precise abstraction contains the minimal set of transitions with regard to the predicates, but as a result is computationally expensive. Most model checkers therefore approximate the abstraction to alleviate the computation of the abstract system by trading off precision with cost. However, approximation results in a higher number of refinement iterations, since it can produce more false counterexamples than its precise counterpart. The refinement loop can become prohibitively expensive for large programs. This paper proposes a new approach that employs both precise (slow) and approximated (fast) abstraction techniques within one abstraction-refinement loop. It allows computing the abstraction quickly, but keeps it precise enough to avoid too many refinement iterations. We implemented the new algorithm in a state-of-the-art software model checker. Our tests with various real-life benchmarks show that the new approach almost systematically outperforms both precise and imprecise techniques.     

An approach for modeling and detecting software performance antipatterns based on first-order logics

The problem of interpreting the results of performance analysis is quite critical in the software performance domain. Mean values, variances and probability distributions are hard to interpret for providing feedback to software architects. Instead, what architects expect are solutions to performance problems, possibly in the form of architectural alternatives (e.g. split a software component in two components and re-deploy one of them). In a software performance engineering process, the path from analysis results to software design or implementation alternatives is still based on the skills and experience of analysts. In this paper, we propose an approach for the generation of feedback based on performance antipatterns. In particular, we focus on the representation and detection of antipatterns. To this goal, we model performance antipatterns as logical predicates and we build an engine, based on such predicates, aimed at detecting performance antipatterns in an XML representation of the software system. Finally, we show the approach at work on a case study.     

基于直方图的XPath含值谓词路径选择性代价估计

路径选择性代价估计是XML查询优化的基础，也是研究的热点．目前的方法采用大量正态分布和独立性分布假设是造成误差的根本原因．定义了一种新颖的值一位置直方图用于统计XML数据中的结构和值的分布情况，并提出了6种直方图运算．在此基础上，给出用直方图计算估计路径中任一结，最选择性的方法．实验证明，这种方法无需独立性分布假设，也能在数据结构和数值分布不均匀的情况下。精确地估计路径选择性代价．